博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
AtCoder Regular Contest 097
阅读量:4669 次
发布时间:2019-06-09

本文共 5992 字,大约阅读时间需要 19 分钟。

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
#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;string s,t,ch[101];map
b;char minn;int l,num,k,flag,o;int main() { cin>>s; cin>>k; l=s.length(); minn='{'; for(re int i=0;i
=0; h--) { if(t>ch[h]) { ch[h+1]=t; break; } else { ch[h+1]=ch[h]; } } num++; } else { for(re int h=num; h>=0; h--) { if(t>ch[h]) { ch[h+1]=t; flag=h; break; } else { ch[h+1]=ch[h]; } } if(flag==num) { flag=0; break; } } } else ch[++num]=t; } t=""; } cout<

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
#define re register#define max(a,b) ((a)>(b)?(a):(b))#define min(a,b) ((a)<(b)?(a):(b))#define MAXN 4000007#define mo 19930726using namespace std;typedef unsigned long long ull;#define ms(arr) memset(arr, 0, sizeof(arr))const int inf = 0x3f3f3f3f;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 n,m,a[4001],f[2005][2005],cw[4001][2002],cb[4002][2001],pos[2][2001],col[4001];char s[2];int main(){ n=read(); for(re int i=1;i<=n<<1;i++){ scanf("%s",s); a[i]=read(); col[i]=(s[0]=='B'); pos[col[i]][a[i]]=i; } memset(f,100,sizeof(f)); f[0][0]=0; for(re int i=1;i<=n<<1;i++) for(re int j=0;j<=n;j++){ cw[i][j]=cw[i-1][j]; cb[i][j]=cb[i-1][j]; if(a[i-1]>j) col[i-1]?cb[i][j]++:cw[i][j]++; } for(re int i=0;i<=n;i++){ for(re int j=0;j<=n;j++){ int x=pos[0][i+1],y=pos[1][j+1]; f[i+1][j]=min(f[i+1][j],f[i][j]+cw[x][i+1]+cb[x][j]); f[i][j+1]=min(f[i][j+1],f[i][j]+cw[y][i]+cb[y][j+1]); } } cout<

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<

转载于:https://www.cnblogs.com/victorique/p/9550421.html

你可能感兴趣的文章
linux中cat、more、less命令区别详解
查看>>
java读写文件总结
查看>>
阿里题目:明星群众问题
查看>>
为什么SQL用UPDATE语句更新时更新行数会多3行有触发器有触发器有触发器有触发器有触发器有触发器...
查看>>
关于hist
查看>>
Xtrareport 交叉报表
查看>>
谭浩强C语言第四版第九章课后习题7--9题(建立,输出,删除,插入链表处理)...
查看>>
20145101 《Java程序设计》第7周学习总结
查看>>
P2678 跳石头
查看>>
Alpha阶段项目复审
查看>>
ArrayQueue详解(待解决)
查看>>
ASP.NET 安全认证(四)
查看>>
IE9+下如何让input的placeholder样式生效
查看>>
使用 web storage 制作简单留言本
查看>>
61组第二次团队作业
查看>>
利用jsonp实现跨域请求
查看>>
查看Oracle表中的指定记录在数据文件中的位置
查看>>
ServicePointManager.ServerCertificateValidationCallback 冲突的解决
查看>>
Notes on UNPv1 Ch.5
查看>>
Dubbo实战快速入门 (转)
查看>>