Codeforces Round #787 (Div. 3)

​🌲校赛前临时补题之 codeforces 马上要校赛了，太久没敲题，怕校赛被暴打，于是乎写了一套 div3，发现很多不会，然后写一下题解温顾一下，顺一顺思路。

A. Equidistant Letters 题意：比较简单的一个题意，要求两个相同的字母之间距离要相同，但是这个字符串中相同字母最多出现两次，那么把相同字母放一起不就行了，再看长度不是很大，不超过 52 个，所以直接排序 nlogn 可行。52*1e3，当然也有 O（n）的复杂度直接记录就行了

B. Minor Reduction 题意：在一个不包含前导 0 的数字字符串中，可以进行一次操作，将他们的数字和相加，然后替换两个数字就行。

思路：乍一看感觉还挺难的，但是操作只有一次，开始思考如何替换，首先如果两个数字加完之后可能获得的值在【0,18】中，而其中加完之后和有存在>=10，那么肯定是优于加完之后只有一位数，再仔细观察加完之后如果增加两个数字的话，其实并没有改变它本来的字符数量，而且两个数字最少也是大于等于 1 的，而新增的一定是 1x，肯定是变小了，所以从后往前找，第一个能到两个数字就是最优的，但是如果没有两个数字的情况，就把第一个求和应该是最优的，可以变大

C. Detective Task 题意：有一幅画,个人看,中间某一时刻被某一个人偷走了。问每个人他看的时候画还在不在,答案可能是有 (1) / 无 (0) / 忘记了 (?)。好人会说实话/忘记了,偷走的人会随机选一个回答。求最多会有多少个人可能是小偷

思路：一个比较好想的思路就是思考如果当前位置是小偷的话，那么它之前是一定不能出现 0 的（空），并且它之后也一定不能出现 1（有），所以不断的维护这段区间就行,可以双指针，也可以前缀和，我自己用的前缀和比较好想但是复杂了点。

//前面全是 yes，后面全是 no//前面没有 no，后面没有 yes

D. Vertical Paths 题意：给定一个数组 p[N],其中 p[i]为 i 的父节点，1.求得不重合，且覆盖所有结点的最小路径数，2,并分别输出该路径，从父节点到子节点的顺序输出该路径。

思路：覆盖所有节点的最小路径数，并且必须要满足从上层到下层这种顺序，不难想到，每个叶子节点都可以作为答案的端点，然后再想其实和 dfs 就非常像了，从起点开始 dfs 搜到底，也就是搜到第一个叶子结点，然后对这一条路直接染色，这种情况就是最优的。考的就是实现问题。

  }  dfs(-1,rt);  cout<<tot<<endl;  for(i=1;i<=tot;i++)  {    cout<<ans[i].size()<<endl;    for(j=ans[i].size()-1;j>=0;j--)    {      if(j!=0) cout<<ans[i][j]<<" ";      else cout<<ans[i][j]<<endl;    }  }    cout<<endl;  for(i=1;i<=n;i++) {    edges[i].clear();    ans[i].clear();  }}return 0;

}

E. Replace With the Previous, Minimize 题意：给定一个字符串，问在执行 k 次操作后字典序最小的字符串是什么？一次操作的定义：对于任意一个字符串中的字母 s，将字符串内所有为 s 的字母转换为 s-1 即 b 可以转换为 a，c 可以转换为 b，……，z 可以转换为 y。

思路：首先要求的是字典序最小的，所以肯定是从首位开始尽可能小，那么我就直接暴力跑，看首位能减低到字母几，然后标记一下，表示之后遇到这些走过的路都可以走，所以是个很简单的贪心。

​