1005 csp-s 60 凉凉
T1 嘟嘟噜
上来一看数据范围1e9就蒙蔽,然后不知所措的打了一个 $ O(n)$的无脑算法,由于本人真的脑小,导致O(n)的柿子推了好长时间,导致心态崩了,然后........ 今天能明白了log的算法,算是约瑟夫问题弄明白了,没有想到跳跃式的竟然可以log求。
#include<bits/stdc++.h> using namespace std; #define re register inline int read() { int x=0,f=1;char cc=getchar(); while(cc>'9'||cc<'0'){if(cc=='-')f=-1;cc=getchar();} while(cc>='0'&&cc<='9'){x=(x<<1)+(x<<3)+cc-'0';cc=getchar();} return x*f; } const int maxn=5000005; int n,k,m,S; int ans[maxn]; queue<int>q; set<int>pc,fc; stack<int>s; int main() { n=read(),k=read(),m=read(),S=read(); for(int i=1,u;i<=m;i++) { u=read(); ans[u]=-1; } q.push(S); for(re int i=1;i<=n;++i) if(i!=S&&ans[i]!=-1) { if(i&1)pc.insert(i); else fc.insert(i); } while(q.size()&&(!pc.empty()||!fc.empty())) { int x=q.front();q.pop(); if((x&1)==(k&1)) { for(auto it=pc.lower_bound(max(x-k+1,k-x));it!=pc.end()&&*it<x+k;++it) { int zz=(k-(abs(x-*it)+1))>>1; if(zz>n-max(*it,x))break; q.push(*it); ans[*it]=ans[x]+1; s.push(*it); } while(s.size())pc.erase(s.top()),s.pop(); continue; } for(auto it=fc.lower_bound(max(x-k+1,k-x));it!=fc.end()&&*it<x+k;++it) { int zz=(k-(abs(x-*it)+1))>>1; if(zz>n-max(*it,x))break; ans[*it]=ans[x]+1; q.push(*it); s.push(*it); } while(s.size())fc.erase(s.top()),s.pop(); } for(re int i=1;i<=n;++i) { if(!ans[i]&&(i!=S))ans[i]=-1; printf("%d ",ans[i]); } return 0; }
T2 天才绅士少女助手克里斯蒂娜
看题就发现是原题,然后想到当时自己连题解都没有颓,就崩了,然后想到当时就是wba大神造的数据,我就感到了一丝不妙,其实就是拆一下柿子就出来了!
然后我就怀着爆零的心情去看T3
#include<bits/stdc++.h> using namespace std; #define int long long inline int read() { int f=1,x=0;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } const int maxn=5000005; const int mod=20170927; int n,m; struct BIT { int tr[maxn]; inline int lowbit(int x){return x&(-x);} inline int query(int x) { int res=0; while(x) { (res+=tr[x]+mod)%=mod; x-=lowbit(x); } return res; } inline void update(int x,int val) { while(x<=n) { (tr[x]+=val+mod)%=mod; x+=lowbit(x); } return ; } }t1,t2,t3; int a1[maxn],a2[maxn],a3[maxn]; struct node { int x,y; inline void make(int _x,int _y){x=_x,y=_y;return ;} }s[maxn]; signed main() { //freopen("inputs2.in","r",stdin); n=read();m=read(); for(int i=1,x,y;i<=n;i++) { x=read(),y=read(); s[i].make(x,y); } for(int i=1;i<=n;i++) { a1[i]=(s[i].x*s[i].x%mod)%mod; a2[i]=(s[i].y*s[i].y%mod)%mod; a3[i]=(s[i].x*s[i].y%mod)%mod; t1.update(i,a1[i]); t2.update(i,a2[i]); t3.update(i,a3[i]); } int opt=0; while(m--) { opt=read(); if(opt==1) { int p=read(),x=read(),y=read(); s[p].x=x,s[p].y=y; int c1=a1[p],c2=a2[p],c3=a3[p]; a1[p]=x*x%mod,a2[p]=y*y%mod;a3[p]=x*y%mod; t1.update(p,a1[p]-c1); t2.update(p,a2[p]-c2); t3.update(p,a3[p]-c3); } else { int l=read(),r=read(); int ans=0; ans=((t1.query(r)-t1.query(l-1)+mod)%mod*(t2.query(r)-t2.query(l-1)+mod)%mod+mod)%mod; int tt=((t3.query(r)-t3.query(l-1)+mod)%mod+mod)%mod; ans=((ans-tt*tt%mod+mod)%mod+mod)%mod; printf("%lld ",ans); } } return 0; }