Codeforces Round #291 (Div.2)
这套比赛是从冬令营后开始做的，做到现在大概有一个星期了，主要是由于春节期间各种颓+拖延整晚期。本来按照计划，这套比赛应该在前天完成，结果被我拖到了昨天，昨天又在搞翻墙的事情，就拖到今天了，今天下午，突然想起来这套试卷还没有做完，觉得不能再拖下去了，这才终于讲这套水题给刷完了。
题目都比较水，讲的不算很详细，还不懂的话可以找我或者看官方的英文题解。
Problem 2A
直接一位一位判断过去，假设有一位是x，如果9-x比x小的话，就用9-x替换该位，要注意的是不能有前导零，要特判（我在特判的时候出了错也是醉了）。
Problem 2B
这题坑了我很久，因为我莫名其妙地想歪了。题目大意是这样的，有很多不会动的怪物，位于平面直角坐标系上，你有一个两头同时可以发射激光的激光炮，也就是说，激光炮一次性可以将一条直线上的所有怪物都杀死，激光炮也不能动，现在询问杀死所有怪物需要几次。很明显，以激光炮的位置为原点，接着枚举每个点，看看其所在的直线有没有被枚举过就行了。
结果我想成了这个样子：激光炮是可以移动的（虽然我看到题目里面说激光炮是不会动的，但还是莫名其妙地想成了会动），那么就等于找到最少的直线，使得这些直线覆盖所有点，然后我就不会做的。。到后来才想起来，原来这题很水。
Problem 2C
这道题目是整套比赛中，我花的时间最长的一道题。给出n条字符串，接着是m次查询，每次查询给出一条字符串，询问给出的n条字符串中，是否存在一条长度相同且只有一个字符不一样的字符串。结果我开始的时候看成了“是否存在一条字符串，使其某子串和询问串恰有一个字符不同”，然后我就思密达了。
后来才发现题目没看完，然后想出了一种奇葩的做法，首先，把所有串都连起来，求出后缀数组和LCP，然后对于询问串，我们一位一位判断过去，对于第i位，判断一下有没有一个串和该询问串的LCP是i-1，且第i+1位开始都是一样的，实现起来似乎很麻烦的样子。然后我就无耻地看了题解，这才知道题目中竟然还有一个条件，保证只出现a、b、c三个字符，所以对于每一位都三种情况枚举过去，然后求hash就行了（实际上好像字符集是26的话也是能过的），题解中用的是排序后再二分判断，我偷懒用了map，最后再出现了各种莫名其妙的错误（我的DEVC++真高级呵，cstring都给自己加上了）。
Problem 2D
这道题的题目看了我好久，因为懒得开翻译就直接看，看了好几遍才大致明白是怎么回事。就是有很多物品（就是题目中的droids，大概是士兵神马的，这些细节不用在意），每个物品都有m种属性（m很小，最大只有5），第i种属性有ai条，然后你有m种机器，第i种机器恰好可以将所有物品的第i条属性消去一条（如果没有第i条属性的话当然什么事情都不会发生），一个物品如果所有属性都没有了，那么该物品就会消失。然后，你一共可以动用m种机器一共最多k次，询问你能够消去的最长的区间长度是多少，要求输出第i种机器的使用次数。
题目看明白了，这道题目就好做了，首先，要想消去一个区间中所有物品的第i条属性，那么一共要动用第i种机器的次数等于这个区间所有物品中，第i条属性条数的最大值，即[tex]max_{k=l}^{r}ai_k[/tex]，所以，问题就转化成求区间最大值了，因为最后要求，消去的区间长度最长，所以我们可以对每一个位置都向右二分出一个答案，然后再更新最终答案就行了。因为要多次查询区间最大值，所以最好打个ST表，线段树也可以，不过应该是可以卡的？当然，CF上不能卡，这题时限是2s，用线段树只要没有打萎，也是能过去的，但速度从理论上讲是要比ST表慢的。
Problem 2E
这道题是我这套比赛AC的第二道题我会说？这道题明显可以通过数据范围判断出做法，关键在于x，x是十亿，所以主体部分的做法要么是[tex]O(\sqrt x)[/tex]，要么是O(log x)。O(1)一般来说非数学题或结论题是不可能做到的。
很快，可以发现这道题目可以用DP搞，最暴力的DP当然是O(nx)的了，十万*十亿，挺吓人的。其实还有一个关键，那就是di<=100。我们用fk表示等于k的di的树目，我们就能够成功将n从十万变成一百了，但是，很明显，这样还是跑不出来的，我们必须要把可恶的x给变小，要用矩乘优化DP。
单次矩乘是[tex]100^3[/tex]即一百万的，但是我们一共只需要矩乘log x次，所以最后还是能够跑出来的。
Code:
2022年8月25日 18:55
Meghalaya Board Model Paper 2023 Class 9 Pdf Download with Answers for Bengali Medium, English Medium, Hindi Medium, Urdu Medium & Students for Small Answers, Long Answer, Very Long Answer Questions, and Essay Meghalaya Board Model Paper Class 9 Type Questions to Term1 & Term2 Exams at official website. New Exam Scheme or Question Pattern for Sammittive Assignment Exams (SA1 & SA2): Very Long Answer (VLA), Long Answer (LA), Small Answer (SA), Very Small Answer (VSA), Single Answer , Multiple Choice and etc.
2023年1月24日 20:05
Congratulations on finally completing this set of water questions! It's not an easy feat having to procrastinate due to various delays and having seo company in cochin to overcome the wall. It's commendable that you persevered and achieved a successful outcome. If you are still having trouble understanding the water questions, contact me or read the official English solution. Best of luck!