若干比赛题目以及补题复盘

一些补题或者比赛中比较典型的问题

1.Problem - E - Codeforces

这道题有这几个点：

1.答案长度只有可能是因数

2.如果一个字符串k是答案，那么这个字符串满足k*x=s,差别不大于一，那么这x个字符串中与k不同的至多有一个，所以判断的时候最多只用考虑两倍长度的字符串。

赛时第二个点没有想到判断两个字符串，没做出来；

2、Problem - B - Codeforces

a,b为x最大的两个因数(a>b)，那么就有x%a==0,x%b==0;

设y为a，b的最小公倍数，那么很明显当

当a%b!=0，y=(a*b)/gcd(a,b),gcd(a,b)此时一定小于b,故y>a>b,显然y此时等于x

 对于a%b==0的情况，看了题解之后原来是设x=k*a((k∈N+,k>1))；所以可知k为x的一个因数，同时我们要确保b为次大的因数，那么当k大于b时，k=a，x=a^2;    当k小于b时，k*b为x的一个因数，且k*b>b,所以k*b=a;k=a/b;

3.Problem - 1922B - Codeforces

这是一道数学的题，基本的思路为：1.因为在本题组成一个三角形最少需要两个长度相等的木棍，（可以是两个，也可以是三个）2.求对应的组合数

我用的排序写的，但是看了下大佬的代码其实用一个map就可以了，可以少写许多代码，注意优化。

4.T431052 「SFOI Round 1」ChS - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

典型的组合数学，下次碰到同类型的题目应该要知道了

5.Problem - 1917B - Codeforces

每次操作只会删掉一个字符，而无论是删掉第一个还是第二个，就删掉后得到的字符串的第二个字符是固定的，所以种类数只与前面的字符的种类数有关，比如前面全是a,那么每次无论删掉第几个字符，其得到的字符串永远只有一种。