嘿嘿嘿，第一篇文章，感觉代码可以缩起来简直不要太爽
打个div2发挥都这么差...
平均一题fail一次，还调不出错，自闭了
又一次跳A开B，又一次B傻逼错误调不出来
罚时上天，E还傻逼了..本来这场应该很前的，最后只苟在rated的人里面50
A. Chunga-Changa
随便做就行了，因为CF似乎不可以print("%d",0);于是WA了一个样例
#include<cstdio> #include<algorithm> #include<iostream> #include<cstring> #include<vector> using namespace std; typedef long long LL; int main() { LL x,y,z; scanf("%lld%lld%lld",&x,&y,&z); if (x/z+y/z==(x+y)/z) printf("%lld 0\n",(x+y)/z); else { LL t=(z-y%z)%z; LL t1=(z-x%z)%z; LL ans=0; printf("%lld %lld\n",(x+y)/z,min(t,t1)); } return 0; }
B. Split a Number
显然取中间最优，但可能中间有0，那就往两边找
然后一开始有一个大于号写成小于号WA了一发，然后看了半天看不出，最后使得A和B都是30min过
#include<cstdio> #include<algorithm> #include<iostream> #include<cstring> #include<vector> using namespace std; typedef long long LL; const int N=100005; char ss[N]; int n; int cnt; bool tf=false; int len,a[N]; int b[N],len1; bool JD () { if (tf==false) return true; if (len<len1) return false; if (len>len1) return true; for (int u=1;u<=len;u++) { if (a[u]<b[u]) return false; if (a[u]>b[u]) return true; } return true; } void check (int x) { if (ss[x+1]==‘0‘) return ; cnt++; len1=max(x,n-x); memset(b,0,sizeof(b)); int i=x,j=n; for (int u=len1;u>=1;u--) { if (i>=1) b[u]=b[u]+ss[i]-‘0‘; if (j>x) b[u]=b[u]+ss[j]-‘0‘; i--;j--; } for (int u=len1;u>=1;u--) b[u-1]=b[u-1]+b[u]/10,b[u]%=10; if (b[0]!=0) { len1++; for (int u=len1;u>=1;u--) b[u]=b[u-1]; } if (JD()) { len=len1;tf=true; for (int u=1;u<=len;u++) a[u]=b[u]; } } int main() { scanf("%d",&n);scanf("%s",ss+1); cnt=0; for (int u=n/2;u>=1;u--) { check(u); if (cnt>=50) break; } cnt=0; for (int u=n/2;u<n;u++) { check(u); if (cnt>=50) break; } for (int u=1;u<=len;u++) printf("%d",a[u]); return 0; }
C. Flag
考虑枚举左上角，那么我们要知道的就是每个点往下多少个就不同D以及在这一段里面往右多少个就不同R
贡献就是三段R的min
前两段的D要一样，问题是第三段他只要比前两段的D大就好了
于是再倒着维护一个U，然后第三段跳到左下角查询，复杂度O(nm)
然后一个变量打错了，WA了两发
#include<cstdio> #include<algorithm> #include<iostream> #include<cstring> #include<vector> using namespace std; typedef long long LL; const int N=1005; char ss[N][N]; int n,m; int R[N][N]; int mn[N][N]; int D[N][N]; int mn1[N][N]; int main() { scanf("%d%d",&n,&m); for (int u=1;u<=n;u++) scanf("%s",ss[u]+1); for (int u=n;u>=1;u--) { for (int i=m;i>=1;i--) { if (ss[u][i]==ss[u][i+1]) R[u][i]=R[u][i+1]+1; else R[u][i]=1; } } for (int u=1;u<=n;u++) for (int i=1;i<=m;i++) { mn1[u][i]=R[u][i]; if (ss[u][i]==ss[u-1][i]) mn1[u][i]=min(mn1[u][i],mn1[u-1][i]); } for (int u=n;u>=1;u--) for (int i=1;i<=m;i++) { mn[u][i]=R[u][i]; if (ss[u][i]==ss[u+1][i]) { mn[u][i]=min(mn[u][i],mn[u+1][i]); D[u][i]=D[u+1][i]+1; } else D[u][i]=1; } int ans=0; for (int u=1;u<=n;u++) for (int i=1;i<=m;i++) { int x1,x2,x3; x1=u; x2=x1+D[x1][i]; x3=x2+D[x2][i]; if (D[x1][i]!=D[x2][i]) continue; if (D[x3][i]<D[x2][i]) continue; x3=x3+D[x2][i]-1; if (x3>n) continue; ans=ans+min(min(mn[x1][i],mn[x2][i]),mn1[x3][i]); //printf("%d %d %d %d %d\n",u,i,x1,x2,x3); } printf("%d\n",ans); return 0; }
D. Irrigation
模拟这个过程使得所有人一样
每一次把所有i的人变为i+1
发现要维护现在又多少人，以及第k大
开个线段树就好了
#include<cstdio> #include<algorithm> #include<iostream> #include<cstring> #include<vector> using namespace std; typedef long long LL; const LL N=500005; LL n,m,Q; LL a[N]; struct qt { LL l,r; LL c; LL s1,s2; }tr[N*2];LL num; void bt (LL l,LL r) { LL now=++num; tr[now].l=l;tr[now].r=r;tr[now].c=0; if (l==r) return ; LL mid=(l+r)>>1; tr[now].s1=num+1;bt(l,mid); tr[now].s2=num+1;bt(mid+1,r); } LL query (LL now,LL x) { if (tr[now].l==tr[now].r) return tr[now].l; LL mid=(tr[now].l+tr[now].r)>>1; LL s1=tr[now].s1,s2=tr[now].s2; if (tr[s1].c>=x) return query(s1,x); else return query(s2,x-tr[s1].c); } void add (LL now,LL c) { tr[now].c++; if (tr[now].l==tr[now].r) return ; LL mid=(tr[now].l+tr[now].r)>>1; LL s1=tr[now].s1,s2=tr[now].s2; if (c<=mid) add(s1,c); else add(s2,c); } vector<LL> vec[N]; LL ans[N]; struct qq { LL x,id; }q[N]; bool cmp (qq x,qq y) {return x.x<y.x;} int main() { scanf("%lld%lld%lld",&n,&m,&Q); for (LL u=1;u<=n;u++) {LL x;scanf("%lld",&x);a[x]++;} bt(1,m); for (LL u=1;u<=m;u++) vec[a[u]].push_back(u); for (LL u=1;u<=Q;u++) {scanf("%lld",&q[u].x);q[u].x-=n;q[u].id=u;} sort(q+1,q+1+Q,cmp); LL now=0,now1=1;//???????????? for (LL u=0;u<=n;u++) { while (now1<=Q&&now+tr[1].c>=q[now1].x) {ans[q[now1].id]=query(1,q[now1].x-now);now1++;} now=now+tr[1].c; LL siz=vec[u].size(); for (LL i=0;i<siz;i++) add(1,vec[u][i]); } while (now1<=Q) { LL t=q[now1].x-now; t=t%m;if (t==0) t=m; ans[q[now1].id]=t; now1++; } for (LL u=1;u<=Q;u++) printf("%lld\n",ans[u]); return 0; }
E1. A Story of One Country (Easy)
打的时候有点崩，不好意思说自己写了个什么傻吊玩意了
就是暴力枚举一个能切的地方就好了，递归处理，复杂度是O(n^2)的
#include<cstdio> #include<algorithm> #include<iostream> #include<cstring> #include<vector> using namespace std; typedef long long LL; const int N=1005; const int MAX=1e9; struct qq { int x1,y1,x2,y2; qq () {} qq (int a,int b,int c,int d) {x1=a;y1=b;x2=c;y2=d;} }; bool cmp (qq x,qq y) {return x.x1<y.x1;} bool cmp1 (qq x,qq y) {return x.y1<y.y1;} int n; bool solve (vector<qq> vec) { int siz=vec.size(); if (siz==1) return true; vector<qq> a,b;a.clear();b.clear(); sort(vec.begin(),vec.end(),cmp); for (int u=siz-1;u>=0;u--) b.push_back(vec[u]); int mx=0; for (int u=0;u<siz;u++) { b.pop_back();a.push_back(vec[u]);mx=max(mx,a[u].x2); if (u!=siz-1&&mx<=vec[u+1].x1) { //printf("%d %d\n",siz,u); return solve(a)&solve(b); } } sort(vec.begin(),vec.end(),cmp1); a.clear();b.clear(); for (int u=siz-1;u>=0;u--) b.push_back(vec[u]); mx=0; for (int u=0;u<siz;u++) { b.pop_back();a.push_back(vec[u]);mx=max(mx,a[u].y2); if (u!=siz-1&&mx<=vec[u+1].y1) return solve(a)&solve(b); } return false; } int main() { scanf("%d",&n); vector<qq> vec; for (int u=1;u<=n;u++) { int a,b,c,d; scanf("%d%d%d%d",&a,&b,&c,&d); vec.push_back(qq(a,b,c,d)); } if (solve(vec)) printf("YES\n"); else printf("NO\n"); return 0; }
E2. A Story of One Country (Hard)
考虑优化上面这个过程，其实只需要四个方向一起枚举就可以了
枚举到最小的一个就递归下去，复杂度是启发式分裂，也就是和启发式合并一样的复杂度nlogn
但是实现有点小技巧，因为你不可以扫全部元素，否则复杂度就退化了
那么就是要维护一个有序序列，还要支持删除，显然维护4个set就行了
#include<cstdio> #include<algorithm> #include<iostream> #include<cstring> #include<vector> #include<set> using namespace std; typedef long long LL; const int MAX=1e9; struct qq { int x1,y1,x2,y2; qq () {} qq (int a,int b,int c,int d) {x1=a;y1=b;x2=c;y2=d;} }; struct cmp1 { inline bool operator () (qq a,qq b) {return a.x1==b.x1?a.y1<b.y1:a.x1<b.x1;} }; struct cmp2 { inline bool operator () (qq a,qq b) {return a.y1==b.y1?a.x1<b.x1:a.y1<b.y1;} }; struct cmp3 { inline bool operator () (qq a,qq b) {return a.x2==b.x2?a.y2<b.y2:a.x2>b.x2;} }; struct cmp4 { inline bool operator () (qq a,qq b) {return a.y2==b.y2?a.x2<b.x2:a.y2>b.y2;} }; int n; bool solve (set<qq,cmp1> &s1,set<qq,cmp2> &s2,set<qq,cmp3> &s3,set<qq,cmp4> &s4) { int siz=s1.size(); if (siz==1) { s1.clear();s2.clear();s3.clear();s4.clear(); return true; } set<qq,cmp1> g1;g1.clear();set<qq,cmp1> :: iterator it1=s1.begin(); set<qq,cmp2> g2;g2.clear();set<qq,cmp2> :: iterator it2=s2.begin(); set<qq,cmp3> g3;g3.clear();set<qq,cmp3> :: iterator it3=s3.begin(); set<qq,cmp4> g4;g4.clear();set<qq,cmp4> :: iterator it4=s4.begin(); int mxx=0,mxy=0,mnx=MAX,mny=MAX; for (int u=0;u<siz-1;u++) { mxx=max(mxx,(*it1).x2);it1++; if (mxx<=(*it1).x1) { set<qq,cmp1> :: iterator now=s1.begin(); while (now!=it1) { qq xx=(*now);now++; s1.erase(xx);g1.insert(xx); s2.erase(xx);g2.insert(xx); s3.erase(xx);g3.insert(xx); s4.erase(xx);g4.insert(xx); } return solve(g1,g2,g3,g4)&solve(s1,s2,s3,s4); } mxy=max(mxy,(*it2).y2);it2++; if (mxy<=(*it2).y1) { set<qq,cmp2> :: iterator now=s2.begin(); while (now!=it2) { qq xx=(*now);now++; s1.erase(xx);g1.insert(xx); s2.erase(xx);g2.insert(xx); s3.erase(xx);g3.insert(xx); s4.erase(xx);g4.insert(xx); } return solve(g1,g2,g3,g4)&solve(s1,s2,s3,s4); } mnx=min(mnx,(*it3).x1);it3++; if (mnx>=(*it3).x2) { set<qq,cmp3> :: iterator now=s3.begin(); while (now!=it3) { qq xx=(*now);now++; s1.erase(xx);g1.insert(xx); s2.erase(xx);g2.insert(xx); s3.erase(xx);g3.insert(xx); s4.erase(xx);g4.insert(xx); } return solve(g1,g2,g3,g4)&solve(s1,s2,s3,s4); } mny=min(mny,(*it4).y1);it4++; if (mny>=(*it4).y2) { set<qq,cmp4> :: iterator now=s4.begin(); while (now!=it4) { qq xx=(*now);now++; s1.erase(xx);g1.insert(xx); s2.erase(xx);g2.insert(xx); s3.erase(xx);g3.insert(xx); s4.erase(xx);g4.insert(xx); } return solve(g1,g2,g3,g4)&solve(s1,s2,s3,s4); } } return false; } int main() { scanf("%d",&n); set<qq,cmp1> s1; set<qq,cmp2> s2; set<qq,cmp3> s3; set<qq,cmp4> s4; for (int u=1;u<=n;u++) { int a,b,c,d; scanf("%d%d%d%d",&a,&b,&c,&d); s1.insert(qq(a,b,c,d)); s2.insert(qq(a,b,c,d)); s3.insert(qq(a,b,c,d)); s4.insert(qq(a,b,c,d)); } if (solve(s1,s2,s3,s4)) printf("YES\n"); else printf("NO\n"); return 0; }
Codeforces Round #567 (Div. 2)自闭记
原文：https://www.cnblogs.com/Als123/p/11037265.html
