AtCoder Regular Contest 097
C - K-th Substring
题意：
求一个长度小于等于5000的字符串的第K小子串，相同子串算一个。
K<=5。
分析：
一眼看上去可能不是特别好做，但是因为(kle5)，所以确实没啥难度了。把每个字符为首的前五个子串放进去，然后排个序直接找就行了，复杂度(O(5*n*log_2{5n}))。
#include <iostream>
#include <cmath>
#include <string>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <map>
#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<string,int> 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<l-5;i++){
if(s[i]<minn){
minn=s[i];
o=i;
}
}
ch[0]=" ";
for(re int i=o; i<l; i++) {
for(re int j=i; j<min(i+k,l); j++) {
t+=s[j];
if(b[t]==1) continue;
b[t]=1;
if(num!=0) {
if(num<k) {
for(re int h=num; h>=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<<ch[k];
}
D - Equals
题意：
给出一个n的排列，m个（x，y）的数对，你可以交换序列中位于x，y的数字。
可以进行若干次交换，问最多有多少个(a_i=i)。
分析：
明显可以发现，一个联通块里的数字是可以任意交换的，所以并查集维护一下，(O（n）)即可求解。
#include <iostream>
#include <cmath>
#include <string>
#include <cstring>
#include <cstdio>
#include <algorithm>
#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<<ans;
return 0;
}
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 <iostream>
#include <cstdlib>
#include <cmath>
#include <string>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#define re register
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define MAXN 4000007
#define mo 19930726
using 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[n][n];
}
F - Monochrome Cat
题意：
有一棵树，我们已知每个节点的颜色，现在可以任选一个起点开始，每一秒钟有两种选择:
1:选择一个与之相邻的节点并移动过去，同时翻转目标节点的颜色。
2:翻转当前所在节点的颜色。
问将整棵树都染成黑色所需要的最短时间是多少。
分析：
这道题真的不错。
首先我们可以确定这样一个点，如果某节点的某子树是全黑的，那么它就不会被遍历到，所以我们可以直接去掉这棵子树。
删掉所有这样的子树之后，我们就拥有了一棵所有叶子节点都是白色的树。
通过题意我们可以知道，我们必须完全的遍历这棵已经删过点的树。
然后我们先考虑一种简单的情况，就是我们起点和终点重合。那么我们每条边都要走两遍，也就是说我们只要找一个白点当起点，无论从哪一个白点开始都是一样的。
然后，我们又可以发现每个点经过的次数就是它的度数，这样我们可以直接凭空算出哪些点需要在原地停留一秒。
接下来我们思考起点不和终点重合。
那么明显的一点就是，从起点到终点的路径中，每条边只走了一遍，那么我们可以知道，这条路径中原来需要等待一秒使其翻转的点都不用了，原来不用翻转的现在需要翻转了。
这样这个题就变成了我们给出一个由0和1构成的树，现在从中找出一条路径，最大化点数+路径上1的个数-0的个数。
这样我们就可以进行DP。
设f[i]表示i到叶子的最大和，g[i]表示i到叶子的父亲的最大和(叶子是终点)。
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
#define re register
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define MAXN 200007
#define mo 19930726
using 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<<sum-ans;
}