AtCoder Regular Contest 097
C - K-th Substring
题意:
求一个长度小于等于5000的字符串的第K小子串,相同子串算一个。
K<=5。分析:
一眼看上去可能不是特别好做,但是因为\(k\le5\),所以确实没啥难度了。把每个字符为首的前五个子串放进去,然后排个序直接找就行了,复杂度\(O(5*n*\log_2{5n})\)。
#include#include #include #include #include #include #include
D - Equals
题意:
给出一个n的排列,m个(x,y)的数对,你可以交换序列中位于x,y的数字。
可以进行若干次交换,问最多有多少个\(a_i=i\)。分析:
明显可以发现,一个联通块里的数字是可以任意交换的,所以并查集维护一下,\(O(n)\)即可求解。
#include#include #include #include #include #include #define re register#define max(a,b) ((a)>(b)?(a):(b))#define min(a,b) ((a)<(b)?(a):(b))using namespace std;typedef long long ll;typedef unsigned long long ull;#define ms(arr) memset(arr, 0, sizeof(arr))const int inf = 0x3f3f3f3f;int f[1000001],r1,r2,a[100001],b[100001],ans;inline int read(){ int x=0,c=1; char ch=' '; while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); while(ch=='-') c*=-1,ch=getchar(); while(ch<='9'&&ch>='0')x=x*10+ch-'0',ch=getchar(); return x*c;}int find(int x){ if(f[x]!=x) f[x]=find(f[x]); return f[x];}int main() { int n,m; n=read();m=read(); for(re int i=1;i<=n;i++) a[i]=read(),b[a[i]]=i; for(re int i=1;i<=n;i++) f[i]=i; for(re int i=1;i<=m;i++){ int x=read(),y=read(); r1=find(a[x]);r2=find(a[y]); if(r1!=r2) f[r2]=r1; } for(re int i=1;i<=n;i++){ r1=find(i),r2=find(a[i]); if(r1==r2) ans++; } cout<
E - Sorted and Sorted
题意:
有n个黑球和n个白球的乱序排列,它们的编号都是1~n。
可以交换相邻的两个球,要使这两种颜色的球编号均为1~n递增排列,求最少的交换次数。分析:
首先我们可以简单的思考,如果只有一种颜色,就是一逆序对裸题。那么两种颜色的球我们应该怎么办呢?
可以进行DP。 我们用\(f[i][j]\)表示已经放了编号为前i的白球和编号为前j的黑球,那么我们可以得到转移:\(f[i+1][j]=f[i][j]+(第i+1号白球前大于i+1的白球的个数)+(大于j的黑球的个数)\)
\(f[i][j+1]\)同理。
于是我们可以\(n^2\)预处理每个球前面的编号大于j的黑\白球的个数。
#include#include #include #include #include #include #include #include #include #include
F - Monochrome Cat
题意:
有一棵树,我们已知每个节点的颜色,现在可以任选一个起点开始,每一秒钟有两种选择:
1:选择一个与之相邻的节点并移动过去,同时翻转目标节点的颜色。
2:翻转当前所在节点的颜色。
问将整棵树都染成黑色所需要的最短时间是多少。
分析:
这道题真的不错。
首先我们可以确定这样一个点,如果某节点的某子树是全黑的,那么它就不会被遍历到,所以我们可以直接去掉这棵子树。
删掉所有这样的子树之后,我们就拥有了一棵所有叶子节点都是白色的树。
通过题意我们可以知道,我们必须完全的遍历这棵已经删过点的树。
然后我们先考虑一种简单的情况,就是我们起点和终点重合。那么我们每条边都要走两遍,也就是说我们只要找一个白点当起点,无论从哪一个白点开始都是一样的。
然后,我们又可以发现每个点经过的次数就是它的度数,这样我们可以直接凭空算出哪些点需要在原地停留一秒。
接下来我们思考起点不和终点重合。
那么明显的一点就是,从起点到终点的路径中,每条边只走了一遍,那么我们可以知道,这条路径中原来需要等待一秒使其翻转的点都不用了,原来不用翻转的现在需要翻转了。
这样这个题就变成了我们给出一个由0和1构成的树,现在从中找出一条路径,最大化点数+路径上1的个数-0的个数。
这样我们就可以进行DP。
设f[i]表示i到叶子的最大和,g[i]表示i到叶子的父亲的最大和(叶子是终点)。
#include#include #include #include #include #include #include #define re register#define max(a,b) ((a)>(b)?(a):(b))#define min(a,b) ((a)<(b)?(a):(b))#define MAXN 200007#define mo 19930726using namespace std;typedef unsigned long long ull;#define ms(arr) memset(arr, 0, sizeof(arr))const int inf = 0x3f3f3f3f;int head[MAXN],a[MAXN],c[MAXN],num,size[MAXN],f[MAXN],g[MAXN],si[MAXN],d[MAXN],ans,n;char s[MAXN];struct po{ int nxt,to;}edge[MAXN];inline int read(){ int x=0,c=1; char ch=' '; while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); while(ch=='-')c*=-1,ch=getchar(); while(ch<='9'&&ch>='0')x=x*10+ch-'0',ch=getchar(); return x*c;}inline void add_edge(int from,int to){ edge[++num].nxt=head[from]; edge[num].to=to; head[from]=num;}void dfs(int u,int fa){ size[u]=1;si[u]=c[u]; for(int i=head[u];i;i=edge[i].nxt){ int v=edge[i].to; if(v!=fa){ dfs(v,u); size[u]+=size[v];si[u]+=si[v]; if(si[v]!=size[v]) d[v]++,d[u]++; } }}void dfs2(int u,int fa){ int max1=0,max2=0; if(d[u]==1&&fa){f[u]=a[u],g[u]=-1<<30;return;} for(int i=head[u];i;i=edge[i].nxt){ int v=edge[i].to; if(v!=fa&&size[v]!=si[v]){ dfs2(v,u); ans=max(ans,f[v]+max2+a[u]); ans=max(ans,g[v]+max1+a[u]); max1=max(max1,f[v]); max2=max(max2,g[v]); } } f[u]=max1+a[u];g[u]=max2+a[u];}int main(){ n=read(); for(re int i=1;i<=n-1;i++){ int x=read(),y=read(); add_edge(x,y);add_edge(y,x); } scanf("%s",s+1); int root=0; for(re int i=1;i<=n;i++){ if(s[i]=='B') c[i]=1; else root=i; } if(root) dfs(root,0); else { cout<<"0"; return 0; } int sum=0; for(int i=1;i<=n;i++){ if(size[i]==si[i]) continue; sum+=d[i]; if((d[i]+c[i])%2==0) sum++,a[i]=2; } dfs2(root,0); cout<