[2019 牛客CSP-S提高组赛前集训营1]仓鼠的石子游戏 + 乃爱与城市拥挤程度 + 小w的魔术扑克

前言

不知道为什么，比赛的时候数据好像很水，我隔壁大佬T2暴力过了八十？？！我码正解思路line2算错了？！！
这告诉我们什么？！！考试的时候，一定要积极地打暴力，码完“正解”也写个if判一判

友情链接：牛客CSP-S提高组赛前集训营1 ☜戳介里

T1.仓鼠的石子游戏

题目描述

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述
仓鼠和兔子被禁止玩电脑，无聊的他们跑到一块空地上，空地上有许多小石子。兔子捡了很多石子，然后将石子摆成n个圈，每个圈由a[i]个石子组成。然后兔子有两根彩色笔，一支红色一支蓝色。兔子和仓鼠轮流选择一个没有上色的石子涂上颜色，兔子每次可以选择一个还未染色的石子将其染成红色，而仓鼠每次可以选择一个还未染色的石子将其染成蓝色，并且仓鼠和兔子约定，轮流染色的过程中不能出现相邻石子同色，谁不能操作他就输了。假设他们两个都使用了最优策略来玩这个游戏，并且兔子先手，最终谁会赢得游戏？

输入描述
第一行输入一个正整数T，表示有T组测试案例。
每组测试案例的第一行输入一个n，表示有n圈石子。 第二行输入n个正整数a[i]，表示每个圈的石子数量。

输出描述
对于每组测试案例，如果兔子赢了，输出"rabbit"(不含引号)如果仓鼠赢了，输出"hamster"(不含引号)。
数据范围及提示
本题共有10组测试点数据。
对于前30%的数据，满足n = 1, 1 ≤ a[i] ≤ 7, 1 ≤ T ≤ 10。
对于前60%的数据，满足1 ≤ n ≤ 10³, 1 ≤ a[i] ≤ 7, 1 ≤ T ≤ 10²。
对于前100%的数据，满足1 ≤ n ≤ 10³,1 ≤ a[i] ≤ 10⁹, 1 ≤ T ≤ 10²。
对于测试点6，在满足前60%的数据条件下，额外满足a[i] = 1。

样例输入输出
Sample Input
4
1
3
1
1
2
1 3
3
999 1000 1000000000
Sample Output
hamster
rabbit
rabbit
hamster
样例解释
对于第一组案例：只有1圈石子，并且石圈的大小为3。
兔子先手，随便找了一个石子染成红色，接下来仓鼠后手找一个未染色的石子染成蓝色，此时结果如下图所示。

如果兔子将最后一个石子染成红色，这将导致相邻石子同色，根据规则，他输掉了比赛，所以仓鼠获得了最终的胜利。
对于第二组案例：只有1圈石子，并且石圈的大小为1。
兔子先手，将唯一的一个石子染成了红色，接下来由于没有未着色的石子，所以仓鼠由于无法操作而输掉了比赛，兔子取得了最终的胜利。
对于第三组案例：有两个石圈，大小分别为1,3，兔子首先将大小为1的石圈中唯一一个石子染成了红色，接下来仓鼠由于类似第一组案例中的原因输掉比赛，兔子取得了最终的胜利。

题解

（看巨佬们的博客，有说是SG函数的，然而本蒟蒻并不了解是怎么回事。。。）
这题一看就是一道博弈论，我也不知道该怎么说，在草稿纸上涂涂画画，自己推一下，就可以发现，除了石子数为一，其他情况都是先手必败

石子数为一先手必胜很好理解，那么我们接下来继续思考石子数不为一的情况：
想要让染色无法继续，有两种情况：
①.所有石子均被着色：
　a.石子数为偶数，那么最后一个着色的人会是后手，因此，先手必败；
　b.石子数为奇数，那么很容想到，不会出现全部着色的情况（颜色比冰交替出现），因此，先手必败。
②.再染任一一颗石子都会出现连续相同的颜色：
　那么所有此刻尚未着色的石子两边皆是颜色不同的两颗石子，由此易得，染色石子的出现必定是偶数
　个，那么最后一个着色的人也是后手，因此，先手还是必败
综上，先手好难啊 只有石子数为一的情况先手会赢
最后再判一下奇偶就好了

参考代码

#include <cstdio>
#include <iostream>
using namespace std;int T, n, ans;int main () {scanf ("%d", &T);while (T --) {scanf ("%d", &n);for (int i = 1, x; i <= n; ++ i) {scanf ("%d", &x);if (x == 1)++ ans;}if (ans & 1)printf ("rabbit\n");elseprintf ("hamster\n");}return 0;
} 

T2.乃爱与城市拥挤程度

题目描述

时间限制：C/C++ 2秒，其他语言4秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述
乃爱天下第一可爱！
乃爱居住的国家有n座城市，这些城市与城市之间有n-1条公路相连接，并且保证这些城市两两之间直接或者间接相连。
我们定义两座城市之间的距离为这两座城市之间唯一简单路径上公路的总条数。
当乃爱位于第x座城市时，距离城市x距离不大于k的城市中的人都会认为乃爱天下第一可爱！
认为乃爱天下第一可爱的人们决定到乃爱所在的城市去拜访可爱的乃爱。我们定义这些城市的拥挤程度为：
距离城市x距离不大于k的城市中的人到达城市x时经过该城市的次数。例如：

假设k=2，乃爱所在的城市是1号城市，树结构如上图所示时，受到影响的城市为1,2,3,4,5，因为五个城市距离1号城市的距离分别为：0,1,2,2,2，所以这五个城市都会认为乃爱天下第一。
1号城市到1号城市经过了1号城市。
2号城市到1号城市经过了1号、2号城市。
3号城市到1号城市经过了1号、2号、3号城市。
4号城市到1号城市经过了1号、2号、4号城市。
5号城市到1号城市经过了1号、2号、5号城市。
所以1号城市的拥挤程度是5，2号城市的拥挤程度是4，3号、4号、5号城市的拥挤程度都是1。
现在小w想要问你当乃爱依次位于第1、2、3、4、5…n座城市时，有多少座城市中的人会认为乃爱天下第一，以及受到影响城市的拥挤程度的乘积，由于这个数字会很大，所以要求你输出认为乃爱天下第一的城市拥挤程度乘积mod 10⁹+7后的结果。

输入描述
第一行是两个正整数n,k表示城市数目，以及距离乃爱所在城市距离不大于k的城市中的人认为乃爱天下第一！
接下来n-1行，每行两个正整数u,v，表示树上一条连接两个节点的边。

输出描述
输出两行。
第一行n个整数，表示当乃爱依次位于第1、2、3、4、5…n座城市时，有多少座城市中的人会认为乃爱天下第一。
第二行n个整数，表示当乃爱依次位于第1、2、3、4、5…n座城市时，受影响的城市拥挤程度乘积mod 10^9+7后的结果。

数据范围及提示
本题共有10组测试点数据。
对于前10%的测试点满足1 ≤ n ≤ 10，1 ≤ k ≤ 10，树结构随机生成。
对于前30%的测试点满足1 ≤ n ≤ 10³，1 ≤ k ≤ 10，树结构随机生成。
对于前70%的测试点满足1 ≤ n ≤ 10⁵，1 ≤ k ≤ 10，树结构随机生成。
对于前100%的测试点满足1 ≤ n ≤ 10⁵，1 ≤ k ≤ 10，树结构为手动构造。
对于测试点4，在满足其前70%的测试点条件下，额外满足k=1。
对于测试点5，在满足其前70%的测试点条件下，额外满足k=2。
对于测试点10，在满足其前100%的测试点条件下，额外满足树结构退化成一条链。

T2大样例下载连接：
https://pan.baidu.com/s/1AbBuEC8SmWlRMvtj6nLRkw
或者复制以下地址新建下载
https://uploadfiles.nowcoder.com/files/20191029/8030387_1572353828028_T2%20%E5%A4%A7%E6%A0%B7%E4%BE%8B.zip

样例输入输出
Sample Input
7 2
1 2
2 3
2 4
2 5
5 6
5 7
Sample Output
5 7 5 5 7 4 4
20 21 20 20 28 12 12

题解

首先锁定dp，然后思考状态转移方程式。。。
对于节点u而言，它的拥挤度来自它的祖先们，以及它的儿砸们；而祖先与儿子的拥挤度有事互不干扰，互不影响的，那么，我们可以定义一个$dp[u][i]$表示节点u影响向下i层一共可以提供的贡献。

首先考虑它的儿子们对于节点u的贡献。很容易发现，u节点往下的子树，不管向上转移多少层，它们子树内部的贡献总是不变的，因此，我们可以直接考虑节点u因此而造成的拥挤度而产生的贡献，即是它的儿子的个数，因此，我们得出状态转移方程式：
$$son[u][j]=\sum _{i=0}^{size()-1}$$