A：顯然應該讓未確定的大小盡量大。不知道寫了啥就wa了一發。

#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; #define ll long long #define N 200010 #define inf 1000000010 char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;} int gcd(int n,int m){return m==0?n:gcd(m,n%m);} int read() {int x=0,f=1;char c=getchar();while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();return x*f; } int n,p[N],fa[N],a[N],s[N],t,ans; bool flag=1; struct data{int to,nxt; }edge[N]; void addedge(int x,int y){t++;edge[t].to=y,edge[t].nxt=p[x],p[x]=t;} void dfs(int k) {if (!flag) return;for (int i=p[k];i;i=edge[i].nxt){int x=edge[i].to,son=0;for (int j=p[x];j;j=edge[j].nxt) son++;if (son==0) a[x]=0;else{int y=inf;for (int j=p[x];j;j=edge[j].nxt)y=min(y,s[edge[j].to]);if (y<s[k]) {flag=0;break;}a[x]=y-s[k];s[x]=s[k]+a[x];for (int j=p[x];j;j=edge[j].nxt)a[edge[j].to]=s[edge[j].to]-s[x],dfs(edge[j].to);}} } signed main() { #ifndef ONLINE_JUDGEfreopen("a.in","r",stdin);freopen("a.out","w",stdout);const char LL[]="%I64d\n"; #endifn=read();for (int i=2;i<=n;i++){int x=read();fa[i]=x;addedge(x,i);}for (int i=1;i<=n;i++) s[i]=read();a[1]=s[1];dfs(1);if (flag){ll ans=0;for (int i=1;i<=n;i++) ans+=a[i];cout<<ans;}else cout<<-1;return 0;//NOTICE LONG LONG!!!!! } View Code

　　B：快1.5h時才想到一個不太靠譜的做法，然后交一發就wa on 4了。拍了好一會才發現做法假掉了，內心崩潰。花40min換了一個做法，寫的時候就感覺這怎么這么簡單肯定是假的，然后就wa on 7了，根本都不用拍就發現做法假掉了，內心崩潰。最后終于發現最開始的做法是能搶救一下的，把第二種做法合并上去就行了，然后就沒時間了。

　　考慮枚舉左上角的2*2方格怎么填。然后考慮前兩列，如果將左上角直接向下復制，后面的每一列都只有不相關的兩種填法，即兩字母交替出現，取最優值即可；如果對左上角復制后進行一些同行內的交換，那么顯然會有同一列的連續三行出現不同的字母，這樣就固定了每一行都只能是將該行前兩個字母復制。

　　事實上更優美的想法是最終填法要么每行內兩字母交替出現，要么每列內兩字母交替出現。根本想不到啊。

#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<algorithm> #include<vector> using namespace std; #define ll long long #define N 300010 char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;} int gcd(int n,int m){return m==0?n:gcd(m,n%m);} int read() {int x=0,f=1;char c=getchar();while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();return x*f; } int n,m,tot,v=N; vector<char> a[N],b[N],ans[N]; char c[4]={'A','C','G','T'}; bool flag[4]; void check() {//cout<<b[0][0]<<b[0][1]<<endl<<b[1][0]<<b[1][1]<<endl;tot=0;for (int i=2;i<n;i++)b[i][0]=b[i-2][0],b[i][1]=b[i-2][1];for (int j=2;j<m;j++){int ans1=0,ans2=0;for (int i=0;i<n;i++)ans1+=(a[i][j]!=b[i%2][j%2]),ans2+=(a[i][j]!=b[i%2^1][j&1]);if (ans1<ans2){for (int i=0;i<n;i++)b[i][j]=b[i%2][j&1];}else{for (int i=0;i<n;i++)b[i][j]=b[i%2^1][j&1];}}for (int i=0;i<n;i++)for (int j=0;j<m;j++)tot+=a[i][j]!=b[i][j];if (tot<v) {v=tot;for (int i=0;i<n;i++)for (int j=0;j<m;j++)ans[i][j]=b[i][j];}for (int i=2;i<m;i++) b[0][i]=b[0][i&1],b[1][i]=b[1][i&1];for (int i=2;i<n;i++){int ans1=0,ans2=0;for (int j=0;j<m;j++)ans1+=a[i][j]!=b[i%2][j&1],ans2+=a[i][j]!=b[i%2][j&1^1];if (ans1<ans2){for (int j=0;j<m;j++) b[i][j]=b[i%2][j&1];}else{for (int j=0;j<m;j++) b[i][j]=b[i%2][j&1^1];}}tot=0;for (int i=0;i<n;i++)for (int j=0;j<m;j++)tot+=a[i][j]!=b[i][j];if (tot<v) {v=tot;for (int i=0;i<n;i++)for (int j=0;j<m;j++)ans[i][j]=b[i][j];} } void dfs(int x,int y) {if (x>1) {check();return;}for (int i=0;i<4;i++)if (!flag[i]){b[x][y]=c[i];flag[i]=1;if (y==1) dfs(x+1,0);else dfs(x,1);flag[i]=0;} } signed main() { #ifndef ONLINE_JUDGEfreopen("a.in","r",stdin);freopen("a.out","w",stdout);const char LL[]="%I64d\n"; #endifn=read(),m=read();for (int i=0;i<n;i++)for (int j=0;j<m;j++)a[i].push_back(getc());for (int i=0;i<n;i++)for (int j=0;j<m;j++)b[i].push_back(' '),ans[i].push_back(' ');dfs(0,0);for (int i=0;i<n;i++){for (int j=0;j<m;j++)putchar(ans[i][j]);printf("\n");}return 0;//NOTICE LONG LONG!!!!! } View Code

　　然后就墊底了。感覺應該早點棄掉這個毒瘤B去看C。哎還是菜爆。

　　大號終于變小號了。result：rank 341 rating -39

　　C：顯然所有點的子樹大小之和=所有點的深度之和，那么設度數限制為d，只要找到一組x_i滿足∑ix_i=s且x_i>=dx_i+1即可。顯然度數限制d越大，能構造出s的下界就越小，且增加的這部分邊界應該是一段連續區間（因為只要度數限制不為1，就可以找到深度最大且不止一個點的一層，將其中一個點往下拉，使得總深度+1）。于是先找到最小的度數限制，這個隨便都能求。然后考慮構造x_i，先構造出這個s的下界，再逐漸將其增大。只需要暴力模擬上述證明的過程即可。當然，不能一次只增大1，而是應該直接拉到最底端，以保證復雜度。（雖然事實上只有度數限制<=2時每次增大1的復雜度會出現問題）感覺還是做的太麻煩了。

#include<bits/stdc++.h> using namespace std; #define P 1000000007 #define N 100010 #define ll long long int read() {int x=0,f=1;char c=getchar();while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();return x*f; } int n,ans,fa[N],a[N],size[N],deep[N];ll m; void dfs(int k,int n,int x) {size[k]=1;a[deep[k]]++;if (1ll*(k-1)*x+2>n) return;for (int i=(k-1)*x+2;i<=min(n,k*x+1);i++){deep[i]=deep[k]+1;dfs(i,n,x);size[k]+=size[i];} } ll check(int n,int k) {deep[1]=1;memset(a,0,sizeof(a));dfs(1,n,k);ll s=0;for (int i=1;i<=n;i++) s+=size[i];return s; } void build(int d) {int s=1;for (int i=2;i<=n;i++){for (int j=s+1;j<=s+a[i];j++)fa[j]=s-a[i-1]+(j-s-1)/d+1;s+=a[i];} } int main() { #ifndef ONLINE_JUDGEfreopen("c.in","r",stdin);freopen("c.out","w",stdout); #endifcin>>n>>m;int l=1,r=n-1;if ((1ll*n*(n+1)>>1)<m) {cout<<"NO";return 0;}if ((1ll*n*(n+1)>>1)==m){cout<<"YES\n"; for (int i=1;i<n;i++) printf("%d ",i);return 0;}while (l<=r){int mid=l+r>>1;if (check(n,mid)<=m) ans=mid,r=mid-1;else l=mid+1;}if (!ans) {cout<<"NO";return 0;}ll s=check(n,ans);int cur=n;while (cur&&a[cur]<=1) cur--;int maxdeep;for (maxdeep=1;maxdeep<=n;maxdeep++) if (a[maxdeep]==0) break;maxdeep--;for (;;){if (m==s) break;while (a[cur]==1) cur--;if (maxdeep+1-cur>=m-s) a[cur]--,a[cur+m-s]++,m=s;else a[++maxdeep]++,a[cur]--,s+=maxdeep-cur;}build(ans);cout<<"YES\n";for (int i=2;i<=n;i++) printf("%d ",fa[i]);return 0; } View Code

?

轉載于:https://www.cnblogs.com/Gloid/p/10227097.html

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的Codeforces Round #530 Div. 1 自闭记的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。