AtCoder Beginner/Regular Contest 097
2月 7, 2020
Colorful Transceivers
题意
给出 \(a,b,c\) 的坐标，距离 \(\le k\) 的能沟通，问 \(a,c\) 能否沟通。
分析
沟通的方式只有两种：
- \(a,c\) 直接沟通， \(|a-c|\le k\) ；
- \(a,c\) 通过 \(b\) 沟通， \(|a-b|,|c-b|\le k\) 。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
#include<bits/stdc++.h> #define LL long long #define inf 0x3fffffffffffffff using namespace std; int a,b,c,d; bool check(int x,int y) { return abs(x-y)<=d; } int main() { scanf("%d%d%d%d",&a,&b,&c,&d); if (check(a,c)||check(a,b)&&check(b,c)) puts("Yes"); else puts("No"); return 0; } |
Exponential
题意
找一个 \(b^p\le x\) 其中 \(b\ge 1,p\ge 2\) 。
分析
因为 \(x\le 1000\) ，暴力枚举 \(b,p\) 即可。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
#include<bits/stdc++.h> #define LL long long #define inf 0x3fffffffffffffff using namespace std; int n; int main() { cin>>n; int ans=1; for (int i=2;i<=n;i++) { int x=i*i; for (;x<=n;x*=i) if (x<=n) ans=max(ans,x); } cout<<ans<<endl; return 0; } |
K-th Substring
题意
将字符串的所有子串去重排序，求字典序第 \(k\) 小的子串。
分析
因为 \(k\le 5\) ，考虑字典序 \(k\) 小的，长度一定不会超过 \(k\) （即使全部一样，也可以通过某一位开始截取 \(k\) 个不同的得到）。
于是从每一位开始分别截取长度 \(\le k\) 的子串，去重排序输出字典序 \(k\) 小的即可。
|
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 |
#include<bits/stdc++.h> #define LL long long #define inf 0x3fffffffffffffff using namespace std; int n,m; char s[5010]; struct data { int len; char s[10]; }a[50010]; bool cmp(data x,data y) { int len=min(x.len,y.len); for (int i=1;i<=len;i++) if (x.s[i]!=y.s[i]) return x.s[i]<y.s[i]; return x.len<y.len; } bool com(data x,data y) { int len=min(x.len,y.len); if (x.len!=y.len) return false; for (int i=1;i<=len;i++) if (x.s[i]!=y.s[i]) return false; return true; } int main() { scanf("%s%d",s+1,&m); n=strlen(s+1); string x; int p=0; for (int i=1;i<=n;i++) { for (int j=1;j<=2*m;j++) { if (i+j-1>n) break; p++;a[p].len=j; for (int k=1;k<=j;k++) a[p].s[k]=s[i+k-1]; } } sort(a+1,a+1+p,cmp); m--; if (m==0) { for (int i=1;i<=a[1].len;i++) putchar(a[1].s[i]); puts(""); return 0; } else { for (int i=2;i<=p;i++) if (!com(a[i],a[i-1])) { m--; if (m==0) { for (int j=1;j<=a[i].len;j++) putchar(a[i].s[j]); puts(""); return 0; } } } return 0; } |
Equals
题意
允许交换其中的一些位置，要求任意交换以后最大化 \(p_i=i\) 的位置。
分析
因为可以任意交换，所以如果存在 \((a,b)\) 可以交换、\((b,c)\) 可以交换，则显然 \(a,b,c\) 可以任意的互换位置。
于是对于给出的关系，我们相当于可以得到，好几类的位置，同一类中的位置可以任意交换。
而对于同一类中的位置，我们有两个信息，一个是位置信息，一个是位置上的排列信息，我们可以用一个 set 来帮助获得最大的匹配量。
|
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 |
#include<bits/stdc++.h> #define LL long long #define inf 0x3fffffffffffffff using namespace std; int n,m,p[100010],v[100010]; vector<int> e[100010]; set<int> id,pe; void dfs(int x) { v[x]=1; id.insert(x); pe.insert(p[x]); for (auto y:e[x]) if (!v[y]) dfs(y); } int main() { scanf("%d%d",&n,&m); for (int i=1;i<=n;i++) scanf("%d",&p[i]); int x,y; for (int i=1;i<=m;i++) scanf("%d%d",&x,&y), e[x].push_back(y), e[y].push_back(x); memset(v,0,sizeof(v)); int ans=0; for (int i=1;i<=n;i++) if (!v[i]) { id.clear();pe.clear(); dfs(i); for (auto x:id) if (pe.find(x)!=pe.end()) ans++; } printf("%d\n",ans); return 0; } |
Sorted and Sorted
题意
每次可以交换任意的两个相邻位置。要求在全部交换完成后，同一种颜色的信息要保证相对有序。
分析
我们可以知道，如果只有一种颜色的话，其实就是求逆序对的个数。
而且如果要输出方案的话，暴力的从前往后将每一个数回归到他所在的位置即可。
我们可以观察到，暴力的从前往后将每一个数归位，一定是将一个数从口后的位置依次相邻交换到他所在的位置上，而其中，除了正在向前挪动的数，其余数的相对顺序是不会变化的。也就是说，如果我们确定了两种颜色的数分别已经排列到了哪里，下一个数要归位的，我们可以通过排在之前数直接得到。
我们用 \(f[i][j]\) 表示当前处理到第 \(i\) 个位置，且黑色的排列到 \(j\) 号。显然，此时白色的排列到 \(i-j\) 号。
每次我们可以放入黑色的 \(j+1\) 号或者白色的 \(i-j+1\) 号。
对于即将放入的黑色的 \(j+1\) 号，需要挪动的位置为下列两个之和：
- 黑色的，需要 \(> j+1\) 的且排在 \(j+1\) 号之前的；
- 白色的，需要 \(> i-j\) 的且排在 \(j+1\) 号之前的。
这两个信息，显然可以通过预处理得到，于是就可以 \(O(1)\) 转移了。
|
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 |
#include<bits/stdc++.h> #define LL long long #define inf 0x3fffffff using namespace std; int n,b[2010],w[2010],f[4010][2010],frontw[2010][2010],frontb[2010][2010]; int main() { scanf("%d",&n); char ch;int x; for (int i=1;i<=2*n;i++) { ch=getchar(); while(ch!='B'&&ch!='W') ch=getchar(); scanf("%d",&x); if (ch=='B') b[x]=i; else w[x]=i; } for (int i=1;i<=n;i++) { int sum=0; for (int j=i+1;j<=n;j++) if (b[j]<b[i]) sum++; frontb[i][n+1]=sum; for (int j=n;j>=1;j--) if (w[j]<b[i]) frontb[i][j]=frontb[i][j+1]+1; else frontb[i][j]=frontb[i][j+1]; frontb[i][0]=frontb[i][1]; } for (int i=1;i<=n;i++) { int sum=0; for (int j=i+1;j<=n;j++) if (w[j]<w[i]) sum++; frontw[i][n+1]=sum; for (int j=n;j>=1;j--) if (b[j]<w[i]) frontw[i][j]=frontw[i][j+1]+1; else frontw[i][j]=frontw[i][j+1]; frontw[i][0]=frontw[i][1]; } for (int i=1;i<=2*n;i++) for (int j=0;j<=n;j++) f[i][j]=inf; f[0][0]=0; for (int i=1;i<=2*n;i++) for (int j=max(0,i-n);j<=min(i,n);j++) { if (j>0) f[i][j]=min(f[i][j],f[i-1][j-1]+frontb[j][i-j+1]); if (i-j>0) f[i][j]=min(f[i][j],f[i-1][j]+frontw[i-j][j+1]); } /*for (int i=1;i<=2*n;i++) for (int j=0;j<=min(i,n);j++) cout<<i<<" "<<j<<" "<<f[i][j]<<endl;*/ printf("%d\n",f[2*n][n]); return 0; } |
Monochrome Cat
题意
给一棵树，树的每个节点是白色或者是黑色。
可以选择一个位置出发，有以下两种操作：
- 反转当前所在位置的颜色；
- 走到一个相邻的位置，并改变其颜色。
求最小的操作次数，使得整棵树变成黑色。
分析
显然，如果节点是黑色的而且是叶子结点，可以直接删除。
经过一些叶子结点删除以后，可能会产生新的黑色的叶子结点，循环删除，直到不存在这样的黑色叶子结点。
对于剩下的树，如果要求出发结点和结束节点必须要相同的话，可以发现，因为要遍历到所有的叶子结点，所以最小的次数就是把整棵树的所有边和节点遍历一遍。
那么对于度数为偶数的节点，会经过偶数次，如果这个点是白色的话，则需要依次额外的操作反转。
度数为奇数的节点，因为经过奇数次，本来为黑色的，现在需要额外的一次反转让其恢复黑色。
那么现在是可以其实节点和最终节点不同的，也就是相当于在之前的基础上，删除一条从起点到终点的路径。
相当于路径上的点，都少经过一次：
- 对于本来需要一次额外操作反转的点，少经过一次，且不在需要额外的反转，则从原来的答案中 \(-2\) ；
- 对于本来不需要额外反转的点，少经过一次，但需要一次额外的反转来还原状态，则所需要的操作不变。
现在的问题就变成了要找一条链，包含最多的本来需要一次额外操作反转的点。
显然就是求树上的带权直径，两次 dp 即可。
|
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 |
#include<bits/stdc++.h> #define LL long long #define inf 0x3fffffff using namespace std; int n,d[100010],val[100010],f[100010][2],v[100010]; char c[100010]; vector<int> e[100010]; struct edge { int x,y; }a[100010]; void dfs(int x,int fa) { int cnt=0; for (auto y:e[x]) if (y!=fa) { dfs(y,x); if (f[y][0]>f[x][0]) f[x][1]=f[x][0],f[x][0]=f[y][0]; else if (f[y][0]>f[x][1]) f[x][1]=f[y][0]; cnt++; } if (cnt<=1) f[x][0]+=val[x],f[x][1]=0; else { f[x][1]+=val[x]; f[x][0]+=val[x]; } //cout<<x<<" "<<f[x][0]<<" "<<f[x][1]<<endl; } void dfs2(int x,int fa) { if (fa!=0) { if (f[fa][0]==f[x][0]+val[fa]) { if (f[fa][1]+val[x]>f[x][0]) f[x][1]=f[x][0],f[x][0]=f[fa][1]+val[x]; else if (f[fa][1]+val[x]>f[x][1]) f[x][1]=f[fa][1]+val[x]; } else { if (f[fa][0]+val[x]>f[x][0]) f[x][1]=f[x][0],f[x][0]=f[fa][0]+val[x]; else if (f[fa][0]+val[x]>f[x][1]) f[x][1]=f[fa][0]+val[x]; } } //cout<<x<<" "<<fa<<endl; // cout<<x<<" "<<f[x][0]<<" "<<f[x][1]<<endl; for (auto y:e[x]) if (y!=fa) dfs2(y,x); } int main() { scanf("%d",&n); memset(d,0,sizeof(d)); for (int i=1;i<n;i++) scanf("%d%d",&a[i].x,&a[i].y), d[a[i].x]++,d[a[i].y]++, e[a[i].x].push_back(a[i].y), e[a[i].y].push_back(a[i].x); scanf("%s",c+1); queue<int> q; for (int i=1;i<=n;i++) if (c[i]=='B'&&d[i]==1) q.push(i); while(!q.empty()) { int x=q.front();q.pop(); v[x]=1; for (auto y:e[x]) { d[y]--; if (d[y]==1&&c[y]=='B') q.push(y); } } int x,y; for (int i=1;i<=n;i++) e[i].clear(); for (int i=1;i<n;i++) { x=a[i].x,y=a[i].y; if (v[x]||v[y]) continue; e[x].push_back(y); e[y].push_back(x); //cout<<x<<" "<<y<<endl; } int ans=0,root; for (int i=1;i<=n;i++) if (!v[i]) { ans+=d[i]; if (d[i]%2==0&&c[i]=='W'||d[i]%2==1&&c[i]=='B') ans++,val[i]=2; //cout<<i<<" "<<val[i]<<endl; root=i; } if (ans==1){printf("%lld\n",ans);return 0;} dfs(root,0); dfs2(root,0); int res=0; for (int i=1;i<=n;i++) res=max(res,f[i][0]); printf("%d\n",ans-res); return 0; } |
