这次模考拿了 200 分，排名第 7 可以原地 AFO。
T1
这道题目蒟蒻一开始写成了 while 循环加 getchar() 结果写爆了。
于是蒟蒻改成了 for 循环，还是挺简单的一道签到题，学过分支结构就能做。
题解：
网页版： 普及模考T1 题解 - 经验分享区 - 信友队论坛
这道题目是一道红题！
首先我们输入字符串 a 然后遍历 a 的每一位，如果存在 i(0≤i≤a.size()) 使得 a[i]='6' 那么直接输出 Alice 。
考虑还有一种赢的方式所以我们在遍历的时候记录有多少位为 0 多少位为 1 最后判断如果 0 的个数大于 1 的个数则就 Alice 赢，否则 Bob 赢。
代码太简单不放！
T2
这道题目蒟蒻首先想到的是数学，用瞪眼法瞪了半天，没有瞪出来，于是想到了 dp，但是蒟蒻感觉 dp 内存会超限，所以写了又改。
一开始写的是三维，肯定会爆，所以改成了二维。
当听到老师说这道题目用 dp 我就将代码提交上去了！
题解：
这道题目有人往数学去想了……但是正解是 dp 哦~
我们来讲解 dp 的要素！
- 定义： dp[i][j] 为当数码和为 i 时，模 z 余 j 时有几个满足要求的数。
- 遍历：三层循环，第一层，枚举数码和，第二层枚举余数，第三层枚举新添加在末尾的数。
- 状态转移：设 i 为当前的数码和 j 为当前的余数 k 为要新添加的数字。那么
dp[i+k][(j\times 10+k)\ \mathrm{mod}\ z]=(dp[i+k][(j\times 10+k)\ \mathrm{mod}\ z]+dp[i][j])\ \mathrm{mod} \ 1000000007
因为我们将当数码和为 i 余数为 j 的数在末尾添加一个数 k 的时候数码和变为 i+k 余数变为 (j\times 10+k)\ \mathrm{mod}\ z 。 - 初始化： dp[0][0] 只有一种情况所以将它初始化为 1 。
- 答案： dp[y][0] 。
伪代码：
dp[0][0]=1;//初始化
for(int i=0;i<y;i++){//枚举数码和
for(int j=0;j<z;j++){//枚举余数
if(dp[i][j]==0)continue;//若没有可能直接跳过
for(int k=1;k<=9;k++){//因为没有 0 所以只能枚举 1~9
if(i+k<=y){//判断会不会超出边界
//状态转移
}
}
}
cout<<dp[y][0];//输出答案
代码时间复杂度：时间主要开销在三层循环所以时间复杂度为 O(y\times z\times 9) 。
代码空间复杂度：主要用于存储 dp 数组空间复杂度为 O(50005\times 500) 。
T3
这道题目蒟蒻花了很长的时间 qwq
一开始蒟蒻写 dfs 很流畅结果发现判断结束语句不知道怎么写。
想到当 g 数组中没有元素时结束即 g[u].empty()。
后来一测样例这根本判断不了哇，所有的点都不满足这个条件！
于是蒟蒻想到在枚举联通点的时候，当所有点都被标记过后，for 循环会自动退出，那么就可以直接在 for 循环后面 return 就行了，每次 dfs 的时候计算 ans 。
结果发现样例还是过不了！后来考虑到在国家与国家之间穿梭的时候是可以走重复的国家的，于是将 vis 数组删掉了，但是众所周知这样会无限递归 qwq
后来发现每次回溯的时候不应该删去之前的 step 于是回溯的 step 删除，结果发现这样会重复统计同一个国家！于是想到在 while 循环中最后输出 ans 的时候判断是否 ans>n 如果是直接输出 n 否则输出 ans 。
但是众所周知这道题目用 dfs 会超时！
题解：
这道题目大家首先想到的应该是直接搜索，但是这道题目需要用并查集优化否则会 TLE 哦！
首先发现我们其实每个答案就是以 x 为起点，所有权都小于等于 w 的一个连通块中点的个数。
首先我们用并查集的基本思路为：
- 首先初始化每个点的父亲为它自己，每个集合的元素个数都初始化为 1 。
- 输入。
- 先暂且隐藏：一个神秘优化。
- 遍历 x ，如果有联通的并且权小于等于 w 则就将这两个集合合并。
- 最后输出答案。
我们先给出每个部分的伪代码：
- 首先初始化每个点的父亲为它自己，每个集合的元素个数都初始化为 1 。
for(int i=1;i<=n;i++)f[i]=i,cnt[i]=1;
- 输入
for(int i=1;i<=m;i++)cin>>a[i].u>>a[i].v>>a[i].w;
for(int i=1;i<=q;i++){
cin>>b[i].x>>b[i].w;
b[i].i=i;//记录每个起点的 id
}
- 遍历 x ，如果有联通的并且权小于等于 w 则就将这两个集合合并。
for(int i=1;i<=q;i++){
int w=b[i].w;
while(/*满足条件*/){
l++;
join(a[l].u,a[l].v);//合并函数
}
ans[b[i].i]=cnt[find(b[i].x)];//记录答案
}
- 输出
for(int i=1;i<=q;i++)cout<<ans[i]<<endl;
那么我们之前提到的神秘优化是什么呢？就是优化遍历顺序
我们注意到当英雄攻击力越小连通块的点的个数也就越少，为了不重复计算，我们可以从最小的开始遍历到最大的。
也就是我们要通过攻击力将每个单独的问题排序。
同样的我们也需要将每个路径按照边权的大小升序排序，这样就可以 AC此题啦。
T4
这道题目最后半个小时急急忙忙地敲代码。
其他思路想不出来了直接模拟！
于是成功地模拟失败了 qwq
发现输出和样例刚好相反，于是将输出反过来想要骗分，结果提交上去 TLE 了 qwq
赛后发现输出样例有 5 分？如果我直接输出样例排名就进前 5 了 qwq
题解：
这道题目一开始大家肯定想到树，但是这道题目还是要一些思维量的。
首先我们考虑一个点的权值 a_i 和它在图中的深度 dep_i 。
我们可以考虑他们的差 c_i=a_i-dep_i 我们注意到 c_i 的值是不会变的！因为当它向上一位的时候 dep_i 和 a_i 都同时加一，同样的道理，如果向下值也是不变的。
接下来考虑这个 c_i 要比模拟 a_i 的变化要简单多了！
我们尝试联系出 c_i 与 a_i 的关系，我们会发现若 c_i<c_{f(i)} 那么 a_i≤a_{f(j)} 因为 c_i=a_i-dep_i=a_{f(i)}-dep_i-1<a_{f(i)}-dep_i=a_{f(i)} ！即 a_{f(i)}≥a_i 。
那么容易发现每个点都可以移动到树上的任意一个点！那么我们只需要考虑如何将 c_i 填入树种即可。
首先我们先确定唯一的最大值填在根节点上。
填充完毕后，我们便将除根节点以外的子树，变为链。
由贪心我们先填充 c_i 出现次数多的，并且先从长的链开始填充。
反思
这次考试比上一次进步了 1 名（呵呵
这次考试整体还不错，在写完代码的时候要仔细分析复杂度查看是否超时！也可以下载大样例检查！
我的时间分配
第一题我花了大约 10 分钟，然后直接去看第二题。
第二题我首先想到了数学瞪眼没有瞪出来，于是先跳过去看第三题。
第三题死磕了一个多小时，经理了种种样例过不了的痛苦 qwq
重新回来看第二题，想到 dp
首先写三维，感觉会爆空间，优化为二维。
最后半个小时看第四题，没有什么正解思路，直接模拟循环。