1007 Even Tree Split

题意：

给定一个有n个节点的树，保证n是偶数。 您将删除一些边（至少1条），并且必须让每个剩余的连通块具有偶数个顶点。求删除的方法数，模998244353。

思路： 一个节点的子树数目为偶数时可以删一条。用dfs求出最多删除的边数，每条边都是选或不选，最后的方法数即为：2cnt−12^{cnt}-1种情况。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10, M = N * 2,mod = 998244353;
int h[N], e[M], ne[M], idx, n;
ll  sizes[N], ans;
ll qk(ll a,ll b){
	ll ans=1;
	a%=mod;
	b%=mod;
	while(b){
		if(b&1) ans=ans*a%mod;
		a=a*a%mod;
		b>>=1;
		b%=mod;
	}
	return ans;
}
void add(int x, int y){
    e[idx] = y, ne[idx] = h[x], h[x] = idx ++;
}

void dfs(int x, int fa){
    for(int i = h[x]; ~i; i = ne[i])
    {
        int y = e[i];
        if(fa == y) continue;
        dfs(y, x);
        sizes[x] += sizes[y];
    }
    if(!(sizes[x] & 1)) ++ ans;
}

int main()
{
    int t;
    scanf("%d",&t);
    while(t--){
    	memset(h, -1, sizeof h);
    	memset(e, 0, sizeof e);
    	memset(ne, 0, sizeof ne);
    	idx=0;
    	ans=0ll;
    	memset(sizes,0,sizeof(sizes));
	    scanf("%d", &n);
	    for(int i = 1; i < n; i ++)
	    {
	        int x, y;
	        scanf("%d%d", &x, &y);
	        add(x, y), add(y, x);
	    }
	
	    for(int i = 1; i <= n; i ++) sizes[i] = 1ll;
	    dfs(1, 0);
	    ans = (qk(2,ans-1)%mod - 1 +mod)%mod;
	    printf("%lld\n",ans);
	}

    return 0;
}

1003 Wavy Tree

题意：

将一个数组变成波浪形的最少次数，每次操作将数组中的一个数加一或减一。

思路：

只有两种波浪形，"m"形和"w"形，取两者的小值。若要进行调整，让此时的数比上一个数大一或小一即可。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
int mod = 998244353;
int t,n;
ll b[N],a[N],c[N];

int main(){
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		ll ans1=0,ans2=0;
		for(int i=1;i<=n;i++){
			scanf("%lld",&b[i]);
			if(i==1) a[1]=b[1],c[1]=b[1];
			if(i>1){
				if(i%2==0){
					if(b[i]<=a[i-1]){
					a[i]=a[i-1]+1;
					ans1+=abs(b[i]-a[i]);
					}
					else a[i]=b[i];
						
					if(b[i]>=c[i-1]){
					c[i]=c[i-1]-1;
					ans2+=abs(b[i]-c[i]);
					}
					else  c[i]=b[i];
				}
			else 
			{
				if(b[i]>=a[i-1]){
					a[i]=a[i-1]-1;
					ans1+=abs(b[i]-a[i]);
				}
				else a[i]=b[i];
				
				if(b[i]<=c[i-1]){
					c[i]=c[i-1]+1;
					ans2+=abs(b[i]-c[i]);
				}
				else c[i]=b[i];
			}
				
				
			}

		}
		

		printf("%lld\n",min(ans1,ans2));
	}
}

1009 Painting Game

题意：

有一排n个白格子。Alice和Bob轮流行动。每次将剩余的一个空白格涂成黑色，同时保证没有两个黑色格子相邻。当一名玩家无法绘制任何网格时，游戏结束。

Alice想要涂黑格子最少，而Bob想要涂黑格子最多。 给定n和先手方，找出两人都足够聪明下最终涂黑了多少格子。

思路：

Alice要尽量少涂，第一步涂第二个格子，有两个格子不能涂；Bob尽量多涂，第一步涂第三个格子，第一格就必须要涂，这一格只能让第二个格子不能涂。此时不能直接dp,数据范围太大了

有n个格子*，先手方按上面的方法走，就转移到了另一方。转移两次到了自己手上，发现每七格一循环。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){

	int t;
	scanf("%d",&t);
	int d[9]={0,1,1,1,2,2,3,3};
	int p[9]={0,1,1,2,2,3,3,3};
	
	while(t--){
		int n;
		scanf("%d",&n);
		string a;
		cin>>a;
		if(a=="Bob"){
		printf("%d\n",p[n%7]+n/7*3);
		}
		else printf("%d\n",d[n%7]+n/7*3);
	}
}