USACO 22FEB Platinum 题解

#include#definerep(i,a,b) for(int i=(a);i<=(b);++i)#defineper(i,a,b) for(int i=(a);i>=(b);--i)#definepii pair#definevi vector#definefi first#definese second#definepb push_back#defineALL(x) x.begin(),x.end()#definesz(x) int(x.size())#definell long longusingnamespacestd;constintN=2e5+5;intn,T,op[N],L[N],R[N],t[N]; ll c[2];voidins(intx,intv){for(;x <= n + n;x += x & -x)t[x] += v; }intsum(intx){intres =0;for(;x;x -= x & -x)res += t[x];returnres; }voidwork(intx,inty){intcur = sum(x) &1,cnt =1+ sum(y) - sum(x);//start color & number of segsc[cur] += (cnt +1) /2,c[cur ^1] += cnt /2; }boolvis[N];structnode{intpos,val,id;booloperator<(constnode &a)const{returnpos < a.pos;} };set S;voidcheck(intx,inty){autocur = S.lower_bound({x,0,0});vector v;while(cur != S.end()){if((*cur).pos > y)break; v.pb(*cur);cur++; }if(v.empty())return; sort(v.begin(),v.end(),[](node x,node y){returnx.id < y.id;});intid = v[0].id;for(autot : v)if(t.id != id){//合并if(!vis[t.id]){ vis[t.id] =1,c[t.val]--; S.erase({L[t.id],0,0}),S.erase({R[t.id] +1,0,0}); } } }intmain(){cin.tie(0)->sync_with_stdio(0);cin>> n >> T; rep(i,1,n){intx,y,X,Y;cin>> x >> y >> X >> Y; op[x] =1,L[x] = y,R[x] = Y -1; op[X] =-1,L[X] = y,R[X] = Y -1; } rep(i,1,2*n){ ins(L[i],op[i]),ins(R[i] +1,op[i]); work(L[i],R[i]); check(L[i],R[i] +1);if(op[i] ==1){if(sum(L[i]) == sum(R[i])){//新连通块intw = (sum(L[i]) &1) ^1; c[w]++; S.insert({L[i],w,i}),S.insert({R[i] +1,w,i}); } }else{//减去多算的颜色c[sum(L[i] -1) &1]--,c[sum(R[i] +1) &1]--;autocur = S.lower_bound({L[i],0,0});if(cur != S.end() && (*cur).pos == L[i]){ S.erase(cur);S.erase({R[i] +1,0,0}); } } } c[0]++;if(T ==1)cout<< c[0] + c[1] <<'n';elsecout<< c[0] <<' '<< c[1] <<'n';return0; }

T2

#include#definerep(i,a,b) for(int i=(a);i<=(b);++i)#defineper(i,a,b) for(int i=(a);i>=(b);--i)#definepii pair#definevi vector#definefi first#definese second#definepb push_back#definedebug(...) fprintf(stderr, __VA_ARGS__)#defineALL(x) x.begin(),x.end()#definesz(x) int(x.size())#definell long longusingnamespacestd;inlinellread(){ ll x=0,f=1;charch=getchar();while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}returnx*f; }constintN=1e6+5;intn,q,pri[N],tot,flg;boolvis[N]; ll a[N],s[N];mapint,greater > mp;vector P;llgcd(ll x,ll y){return!y ? x : gcd(y,x % y);}intmain(){ n = read(); rep(i,2,1000000){if(!vis[i])pri[++tot] = i;for(intj =1;j <= tot && i * pri[j] <=1000000;j++){ vis[i * pri[j]] =1;if(i % pri[j] ==0)break; } } rep(i,1,n)a[i] = read(); rep(i,1,n)s[i] = s[i-1] + a[i]; ll S = s[n]; rep(i,1,tot){if(S % pri[i] ==0){while(S % pri[i] ==0)S /= pri[i]; P.pb(pri[i]); } } ll x =sqrt(S);if(x >1&& x * x == S)P.pb(S/x),flg =1; rep(i,1,n-1){ s[i] = gcd(s[i],s[n]); mp[s[i]]++;if(!flg){ ll x = s[i];for(ll p : P)while(x % p ==0)x /= p;if(x >1e6&& flg !=1){if(x < S){ P.pb(x),P.pb(S/x),flg =1; }elseflg =2; } } }if(flg ==2)P.pb(S);for(ll p : P){for(autoit = mp.begin();it != mp.end();it++){if(it->fi % p ==0)mp[it->fi / p] += it->se; } } q = read();while(q--){ ll k = read();if(s[n] % k !=0){puts("-1");continue; } ll ans = s[n] / k + n -2-2* mp[k];printf("%lldn",ans); }return0; }

T3

#include#definerep(i,a,b) for(int i=(a);i<=(b);++i)#defineper(i,a,b) for(int i=(a);i>=(b);--i)#definepii pair#definevi vector#definefi first#definese second#definepb push_back#definedebug(...) fprintf(stderr, __VA_ARGS__)#defineALL(x) x.begin(),x.end()#definesz(x) int(x.size())#definell long longusingnamespacestd;inlinellread(){ ll x=0,f=1;charch=getchar();while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}returnx*f; }constintN=1e5+5,P =1e9+7;intnum[2048];constintA[4] = {1<<1|1<<2|1<<4|1<<5,1<<2|1<<3|1<<5|1<<6,1<<4|1<<5|1<<7|1<<8,1<<5|1<<6|1<<8|1<<9};intsta4(inta,intb,intc,intd){return1<1<1<1<intsta2(inta,intb){return1<1<boolinsq(intS,intc,intsq){if((S & sq) != S)return0;if(num[S] != c)return0;if(find(A,A+4,sq) == A+4)return0;return1; }boolline(inta,intb){if(a != b)return0;if(a %9==0){//是否列相邻a /=9;return(a & (a-1)) ==0; }if(a %3==0){//行相邻a /=3;if(a & a-1)return0;if(a ==1<<3|| a ==1<<6)return0;return1; }return0; }structS{inta3,a2,a1,a0;booloperator< (constS &x)const{returna3 < x.a3 || a3 == x.a3 && (a2 < x.a2 || a2 == x.a2 && (a1 < x.a1 || a1 == x.a1 && a0 < x.a0)); } };chars[N];intn,a[N];inlineintc(charch){returnch -'0';}mapint> f,g;voidsolve(){scanf("%s",s+1);intn =0;while(s[n+1])n++; rep(i,1,n)a[i] = s[i] -'0'; f.clear(); f[(S){-1,-1,-1,0}] =1; rep(i,1,n){ g.clear();for(auto&pre : f){ S o = pre.fi; rep(x,1,9){ S nxt; nxt.a3 = o.a2 |1<< x; nxt.a2 = o.a1 |1<< x; nxt.a1 = o.a0 |1<< x; nxt.a0 =-1;if(o.a3 !=-1&& insq(o.a3 |1<< x,4,sta4(a[i-3],a[i-2],a[i-1],a[i])))nxt.a0 =0;if(nxt.a2 !=-1&& line(nxt.a2,sta2(a[i-1],a[i])))nxt.a0 =0;if(nxt.a1 == (1<0;if(nxt.a3 !=-1&& (i == n || !insq(nxt.a3,3,sta4(a[i-2],a[i-1],a[i],a[i+1]))))nxt.a3 =-1;if(nxt.a2 !=-1&& (i >= n-1|| !insq(nxt.a2,2,sta4(a[i-1],a[i],a[i+1],a[i+2]))))nxt.a2 =-1;if(nxt.a0 !=-1|| nxt.a1 !=-1|| nxt.a2 !=-1|| nxt.a3 !=-1){ g[nxt] = (g[nxt] + pre.se) % P; } } } f = g; } ll ans =0;for(auto&i : f)if(i.fi.a0 ==0)ans = (ans + i.se) % P;cout<< ans <<'n'; }intmain(){ rep(i,1,2047)num[i] = num[i>>1] + (i&1);intT = read();while(T--)solve();return0; }