[SinGuLaRiTy] NOIP模拟赛(TSY)-Day 1

游戏 (game)

题目描述

A和B在玩游戏。桌子上有n个格子，其中一些格子放有棋子‘x’，空格子用‘o’表示。A和B轮流进行以下操作中的任何一种。
1>当某一个棋子右边有空格时，将该棋子向右移动一位。
ooxoo -> oooxo
2>当某一个棋子右边恰好是连续的两个棋子时，将该棋子直接跳过连续的两个棋子。
ooxxxoo -> oooxxxo
当棋子到达终点(最右端的格子)时，棋子将消失。当某一方不能移动时，这方输。A先走。请问A是否必胜？

输入

多组测试数据。
对于每一组测试数据：
第一行输入一个整数n，表示格子数量。
第二行输入长度为n的‘x’‘o’串。

输出

对于每一组测试数据，输出一行“YES”或者“NO”。

样例数据

样例输入	样例输出
4 ooxo 4 xxxo 5 oxxxo	YES NO NO

<数据范围>

对于30%的数据，n<=20。
对于100%的数据，n<=10^6 ，测试数据组数 T<=5。

解析

这道题其实考点是博弈论(还不了解博弈论?阅读一下这些论文吧。[点击下载]) ，不过由于策略比较简单，可以通过找规律来得到答案。

考虑所有棋子到终点的距离和sum，观察无论哪一种操作都恰好改变了sum的奇偶性。若sum为奇数，则A必胜；否则A必败。

时间复杂度：O(n)。

Code

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define N 1000005

#define ll long long

char S[N];

int t,n;

ll k;

int main()

{

    while(scanf("%d",&n)==)

    {

        scanf("%s",S+);

        k=;

        for(int i=;i<=n;i++)

        if(S[i]=='x')

            k+=n-i;

        if(k&)

        printf("YES\n");

        else

        printf("NO\n");

    }

    return ;

}

轰炸 (bomb)

题目描述

A国和B国开战。B国国王痴迷于树，所以B国的城市道路是一棵树的形状。A国情报局通过B国地下组织获取了该消息……给力的地下党还窃取了B国每一个城市的火药储备量m[i]，即轰炸城市i可以同时炸掉距离城市i在m[i]之内的其他城市。
由于A国国力有限，A国情报局局长想知道至少需要炸几次才能把B国所有城市都炸掉……

输入

第一行输入一个整数n，表示B国的城市数量。
第二行输入n个整数，第i个整数m[i]表示城市i的火药储备量。
接下来的n-1行，每一行输入两个整数u、v，表示一条连接城市u、v长度为1的城市道路。

输出

输出一行一个整数，即最少轰炸次数。

样例数据

样例输入	样例输出
5 1 1 1 1 1 1 2 2 3 3 4 4 5	2

<数据范围>

对于10%的数据，n<=10 。
对于30%的数据，n<=1000 。
对于100%的数据，n<=10^5 , m[i]<=100 。

解析

一看这道题，就感觉有点像战略游戏这道题，于是就想到了用树形DP。

好吧，这就是一道典型的树形DP。

令f[u][i]表示以u为根的子树被完全破坏，同时还能向上延伸i的最小值。

令g[u][i]表示以u为根的子树未被完全破坏，还应向下延伸i的最小值。

转移方程式：

1.不轰炸u节点