cf798

A.给你两个字符串，a,b和两种操作
1.从字符串a中选择任意一个字符，将其从a中移除，并将其添加到c的末尾。

2.从字符串b中选择任意一个字符，将其从b中移除，并将其添加到c的末尾。

但是你不能连续进行k次相同操作。

输出可以得到的最小字典序字符串c。

思路：给两个串排序，记录上一操作的类型和已经连续操作的次数，模拟一下即可。

B.给定一个 n排列p，构造出一个新的字典序最小的n排列q,，使得对于任意i，pi！=qi

用一个 set记录当前还有哪些数没有填，每次填最小即可。

我用O（n*n）也能做，就是效率低。

#include
using namespace std;
const int N=2e5+10;
int a[N];
bool used[N];
int b[N];
int find(int x,int  n){
    for(int i=1;i<=n;i++){
        if(!used[i]&&i!=x){
        	used[i]=1;
            return i;
        }
    }
}
signed main(){
    int tt;
    cin>>tt;
    while(tt--){
          int n;
          cin>>n;
          for(int i=1;i<=n;i++) used[i]=0;
          for(int i=1;i<=n;i++)
          { 
            cin>>a[i];
          }
          if(n==1) cout<<-1< 
C - Infected Tree 
题意： 
给定一个二叉树，从根节点开始感染病毒，每次可以选择删去一个未被感染的点，使得该点的子树不被感染，求最多的不被感染的节点的个数（删去节点的不算）。
 
思路： 
观察到一个节点最多只有两个儿子，如果有两个儿子，我们可以枚举删掉哪个收益更大。 dp[u] 表示 u 节点感染时最大的答案，f[u]表示以 u 为根的子树的节点个数(包括其本身）。那么如果有两个儿子, d p [ u ] = m a x ( d p [ s o n 1 ] + f [ s o n 2 ] − 1 , d p [ s o n 2 ] + f [ s o n 1 ] − 1 ) dp[u]=max(dp[son1]+f[son2]-1,dp[son2]+f[son1]-1) .做一遍树形dp即可。
 
树形dp不太熟，两次dfs，自己都看不下去了。。。
 
记得双向边开两倍数组，不小心RE了。。。
 
#include
using namespace std;
const int N=6e5+10;
#define me(a,b) memset(a,b,sizeof a)
int e[N],h[N],ne[N],idx;
int d[N];//记录所有以u为根节点子树的节点数
int son[N][2];//n记录左右儿子
int f[N];//dp
int cnt[N];//记录儿子数
void add(int a,int b){
	e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int  dfs(int u,int fa){
	
		cnt[u]=0;
	for(int i=h[u];~i;i=ne[i]){
		if(e[i]==fa) continue;
		son[u][cnt[u]]=e[i];
		cnt[u]++;
		int t=dfs(e[i],u);
		d[u]+=t;
	}
    return d[u];
}
//f[u]=max(f[l]+d[r]-1,f[r]+d[l]-1);
int ans=0;
int  fds(int u){//表示u结点被感染时最多能保护f[j]个节点。
	int t=0;
	int l=son[u][0],r=son[u][1];
	if(cnt[u]==0){
		return f[u]=0;
	}else if(cnt[u]==1){
		return f[u]=d[l]-1;
	}else {
		int d1=fds(l)+d[r]-1;
		int d2=fds(r)+d[l]-1;
		return f[u]=max(d1,d2);
	}
	
	ans=max(f[u],ans);
}
void solve(){
	int n;
	cin>>n;
	for(int i=0;i<=n;i++)
	{
		h[i]=-1;
		e[i]=ne[i]=idx=0;
		d[i]=1;
		
	}
	for(int i=1;i<=n-1;i++){
		int a,b;
		cin>>a>>b;
		add(a,b),add(b,a);
	}
      dfs(1,-1);
      fds(1);
      cout<>tt;
    while(tt--){
       solve();
    }

    return 0;
}