Finally, another China Round 😛 Solved A to C during the contest, and fail to submit problem D
A. An abandoned sentiment from past
We are required to use elements from B to replace zeros in A, to form an array that is not increasing. First, since all elements are unique, if the zero number is more than 2, there must be a solution. If we can form an increasing array but replace more or equal than 2 zeros. We can exchange them to form a valid one. So, what we need do is check if there are only one zero if it is valid.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
//This sourcecode is under GPLv3 //http://yeguanghao.xyz #include <bits/stdc++.h> #define rep(name,start,end,step) for(int name=start;name<=end;name+=step) using namespace std; #define Pn(x) printf("%d\n",x) #define Ps(x) printf("%d ",x) #define mp make_pair #define pb push_back #define fi first #define se second #define PROB inline void R(int &x) { x=0; int f=1; 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();} x*=f; } void Redirect() { freopen(PROB".in","r",stdin); #ifndef YGHDEBUG freopen(PROB".out","w",stdout); #endif } typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pii; typedef pair<ll,ll> pll; int n,m; int a[105]; int cn=0; int cnt[205]; bool check() { for(int i=1;i<=n;++i) { if(a[i]<a[i-1]) { return 1; } } return 0; } int main() { R(n); R(m); for(int i=1;i<=n;++i) { R(a[i]); if(!a[i]) cn++; } for(int j=1;j<=m;++j) { int t;R(t); cnt[t]++; } for(int i=1;i<=n;++i) { if(a[i]) continue; int cur; for(int j=200;j;--j) { if(cnt[j]) { cur=j; cnt[j]--; break; } } a[i]=cur; } puts(((cn==m)&&check())?"Yes":"No"); return 0; } |
B. An express train to reveries
You are given two different arrays which are both an element different from a permutation. Â You are asked to compute the original permutation. Since there are only one element different, so if there are different in the same position, we can just check which number is missing. Otherwise, we are choosing a number from two in each two positions. I used next_permutation and check to solve this problem.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 |
//This sourcecode is under GPLv3 //http://yeguanghao.xyz #include <bits/stdc++.h> #define rep(name,start,end,step) for(int name=start;name<=end;name+=step) using namespace std; #define Pn(x) printf("%d\n",x) #define Ps(x) printf("%d ",x) #define mp make_pair #define pb push_back #define fi first #define se second #define PROB inline void R(int &x) { x=0; int f=1; 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();} x*=f; } void Redirect() { freopen(PROB".in","r",stdin); #ifndef YGHDEBUG freopen(PROB".out","w",stdout); #endif } typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pii; typedef pair<ll,ll> pll; int n; int a[1005]; int b[1005]; set<int> s; vector<int> x[3]; bool check() { if(x[1]==x[0]) return 0; else if(x[2]==x[0]) return 0; int qwq=0,qaq=0; for(int i=0;i<x[0].size();++i) { if(x[0][i]!=x[1][i]) qwq++; if(x[0][i]!=x[2][i]) qaq++; } if((qwq!=1)||(qaq!=1)) return 0; return 1; } int cn[1005]; int main() { R(n); for(int i=1;i<=n;++i) { R(a[i]); } for(int i=1;i<=n;++i) { R(b[i]); if(a[i]!=b[i]) { x[1].pb(a[i]); x[2].pb(b[i]); s.insert(a[i]); s.insert(b[i]); } else { cn[b[i]]++; } } int ovo=0; for(int i=1;i<=n;++i) { if(!cn[i]) ovo++; } if(ovo==1) { for(int i=1;i<=n;++i) { if(a[i]==b[i]) { Ps(a[i]); } else { for(int i=1;i<=n;++i) { if(!cn[i]) { Ps(i); } } } } puts(""); return 0; } int cnt=0; for(auto i:s) { if(!cn[i]) x[0].pb(i); } do { if(check()) { for(int i=1;i<=n;++i) { if(a[i]==b[i]) { Ps(a[i]); } else { Ps(x[0][cnt++]); } } puts(""); return 0; } else { next_permutation(x[0].begin(),x[0].end()); } }while(1); } |
C. An impassioned circulation of affection
You are required to compute the longest segment of the array, after modify at most k numbers. There are queries and the max number of the array is less than 27. Â So we can use a prefix array to store how much steps we need to do to make the array from 1 to i are all the same. Then we use a binary search to find the answer. Â The overall complexity is
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 |
//This sourcecode is under GPLv3 //http://yeguanghao.xyz #include <bits/stdc++.h> #define rep(name,start,end,step) for(int name=start;name<=end;name+=step) using namespace std; #define Pn(x) printf("%d\n",x) #define Ps(x) printf("%d ",x) #define mp make_pair #define pb push_back #define fi first #define se second #define PROB inline void R(int &x) { x=0; int f=1; 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();} x*=f; } void Redirect() { freopen(PROB".in","r",stdin); #ifndef YGHDEBUG freopen(PROB".out","w",stdout); #endif } typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pii; typedef pair<ll,ll> pll; int pre[1505][27]; int ans[1505][27]; int n; int a[1505]; bool check(int col,int pos,int l,int cost) { if(pos+l-1>n) return 0; return (pre[min(pos+l-1,n)][col]-pre[pos-1][col])<=cost; } int main() { memset(ans,-1,sizeof ans); R(n); for(int i=1;i<=n;++i) { char ch=0; while(!isalpha(ch))ch=getchar(); a[i]=ch-'a'+1; } for(int i=1;i<=n;++i) { for(int j=1;j<=26;++j) { if(a[i]==j) { pre[i][j]=pre[i-1][j]; } else { pre[i][j]=pre[i-1][j]+1; } } } int t; R(t); while(t--) { int p,c; R(p); char ch=0; while(!isalpha(ch)) ch=getchar(); c=ch-'a'+1; if(ans[p][c]!=-1) { Pn(ans[p][c]); continue; } if(check(c,1,n,p)) { for(int i=p;i<=n;++i) { ans[i][c]=n; } Pn(ans[p][c]); continue; } else { int an=0; for(int i=n;i;--i) { int l=0,r=n; while(r-l>1) { int mid=(l+r)>>1; if(check(c,i,mid,p)) l=mid; else r=mid; } an=max(an,l); } ans[p][c]=an; Pn(ans[p][c]); } } } |
D. An overnight dance in discotheque
Give you circles, and you need to divide them into two categories. And you are asked to calculate the maximum sum of xor-sum of these circles. Since there are only 2000 circles, so we can easily build the tree with brute force. Then the greedy strategy is that divide all the son of root to another category, and others remain the same. The complexity is
. It is noticeable that we can do this problem in
complexity with scanning lines and use a balanced tree to maintain them.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 |
//This sourcecode is under GPLv3 //http://yegunanghao.xyz #include <bits/stdc++.h> #define rep(name,start,end,step) for(int name=start;name<=end;name+=step) using namespace std; #define Pn(x) printf("%d\n",x) #define Ps(x) printf("%d ",x) #define mp make_pair #define pb push_back #define fi first #define se second #define PROB inline void R(int &x) { x=0; int f=1; 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();} x*=f; } void Redirect() { freopen(PROB".in","r",stdin); #ifndef YGHDEBUG freopen(PROB".out","w",stdout); #endif } #define rank rax #define x first.first #define y first.second #define r second typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pii; typedef pair<ll,ll> pll; typedef pair<pii,int> Cir; typedef vector<int> node; const int maxn=1005; node s[1005]; Cir c[1005]; int rank[1005]; bool AinB(Cir a, Cir b) { ll k=1ll*(a.x-b.x)*(a.x-b.x)+1ll*(a.y-b.y)*(a.y-b.y)-1ll*(b.r-a.r)*(b.r-a.r); if(k!=0) { return k<0; } else { return b.r>a.r; } } bool AinB(int u,int w) { return AinB(c[u],c[w]); } bool cmr(const Cir &a,const Cir &b) { return a.se>b.se; } void dfs(int k) { for(int i=0;i<s[k].size();++i) { rank[s[k][i]]=rank[k]+1; } for(int i=0;i<s[k].size();++i) { if(rank[s[k][i]]!=rank[k]+1) continue; for(int j=i+1;j<s[k].size();++j) { if((rank[s[k][j]]==rank[k]+1)&&AinB(s[k][j],s[k][i])) { s[s[k][i]].pb(s[k][j]); } } dfs(s[k][i]); } } int n; int main() { R(n); for(int i=1;i<=n;++i) { int xi,yi,ri; R(xi); R(yi); R(ri); c[i]=mp(mp(xi,yi),ri); } sort(c+1,c+n+1,cmr); for(int i=1;i<=n;++i) { if(!rank[i]) { rank[i]=1; for(int j=i+1;j<=n;++j) { if(i==j) continue; if(!rank[j]) { if(AinB(j,i)) { s[i].pb(j); } } } dfs(i); } } ll ans=0; for(int i=1;i<=n;++i) { if((rank[i]<=2)||(rank[i]%2==0)) { ans+=(ll)c[i].r*c[i].r; } else { ans-=(ll)c[i].r*c[i].r; } // printf("%d %d %d %d\n",c[i].x,c[i].y,c[i].r,rank[i]); } printf("%.10f\n",3.1415926535*ans); } |
E. An unavoidable detour for home
This problem is rather interesting to think, but boring to code. I think the original editorial is clearly enough. Carefully classification, and then do the normal DP. There are total 10 situations.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 |
//This sourcecode is under GPLv3 //http://yeguanghao.xyz #include <bits/stdc++.h> #define rep(name,start,end,step) for(int name=start;name<=end;name+=step) using namespace std; #define Pn(x) printf("%d\n",x) #define Ps(x) printf("%d ",x) #define mp make_pair #define pb push_back #define fi first #define se second #define PROB inline void R(int &x) { x=0; int f=1; 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();} x*=f; } void Redirect() { freopen(PROB".in","r",stdin); #ifndef YGHDEBUG freopen(PROB".out","w",stdout); #endif } typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pii; typedef pair<ll,ll> pll; #define dp f ll dp[2][55][55][55][55]; int a[55]; int n; #define cur c const int mod=(int)1e9+7; int main() { R(n); for(int i=1;i<=n;++i) R(a[i]); int c=1,nex=0; dp[1][a[1]==2][a[1]==3][a[2]==2][a[2]==3]=1; for(int i=2;i<n;++i) { memset(dp[nex],0,sizeof dp[nex]); for(int p1=0;p1<=n;++p1) { for(int p2=0;p1+p2<=n;++p2) { for(int c1=0;p1+p2+c1<=n;++c1) { for(int c2=0;p1+p2+c1+c2<=n;++c2) { ll v=dp[cur][p1][p2][c1][c2]; // new level if(p1+p2==0) { dp[cur][c1][c2][0][0]+=v; dp[cur][c1][c2][0][0]%=mod; continue; } // stay on for(int lc=1;lc<=2;++lc) {// we solve a 1plug or 2plug ? int cnt; if(lc==1) { cnt=p1; if(p1<=0) { continue; } p1--; } else { cnt=p2; if(p2<=0) continue; else { ++p1; p2--; } } // let's dicuss type of new vertex if(a[i+1]==2) { f[nex][p1][p2][c1+1][c2]+=v*cnt; f[nex][p1][p2][c1+1][c2]%=mod; if(c1>=1) { f[nex][p1][p2][c1-1][c2]+=v*cnt*c1; f[nex][p1][p2][c1-1][c2]%=mod; } if(c2>=1) { f[nex][p1][p2][c1+1][c2-1]+=v*cnt*c2; f[nex][p1][p2][c1+1][c2-1]%=mod; } } else { f[nex][p1][p2][c1][c2+1]+=v*cnt; f[nex][p1][p2][c1][c2+1]%=mod; //1 plug*1 if(c1>=1) { f[nex][p1][p2][c1][c2]+=v*cnt*c1; f[nex][p1][p2][c1][c2]%=mod; } // 1 plug2 if(c2>=1) { f[nex][p1][p2][c1+2][c2-1]+=v*cnt*c2; f[nex][p1][p2][c1+2][c2-1]%=mod; } //2 plug1 if(c1>=2) { f[nex][p1][p2][c1-2][c2]+=v*cnt*(c1)*(c1-1)/2; f[nex][p1][p2][c1-2][c2]%=mod; } //1 plug1 1plug2 if(c1>=1&&c2&&1) { f[nex][p1][p2][c1][c2-1]+=v*cnt*(c1)*c2; f[nex][p1][p2][c1][c2-1]%=mod; } //2 plug2 if(c2>=2) { f[nex][p1][p2][c1+2][c2-2]+=v*cnt*c2*(c2-1)/2; f[nex][p1][p2][c1+2][c2-2]%=mod; } } if(lc==1) p1++; else { p2++;p1--; } continue; } } } } } c^=1; nex^=1; } std::cout<<dp[cur][0][0][0][0] <<endl; } |