1、Necklace Assembly
给一个长度为(n)的字符串，从中挑选出一些字符然后按照你想要的顺序排成一个环，这个环顺时针旋转(k)次后与原来的环相同，问环的最大长度。
(1<=n,k<=2000)
题解
旋转(k)次后依然相同，说明这个环的循环节是(k)的因数。
由于(n,k) 比较小，可以枚举循环节的长度和环的最大长度，复杂度(O(n^2))
int main()
{
int n, k, t;
int cnt[40], tot[2005];
string s;
cin >> t;
while(t--) {
memset(cnt, 0, sizeof(cnt));
cin >> n >> k >> s;
_myfor(i, 0, n) cnt[s[i] - 'a']++;
int ans = 0;
myfor(i, 1, min(n, k)) if (k % i == 0) { // 枚举循环节的长度
for (int le = n; le > 0; le--) if (le % i == 0) { // 枚举环的最大长度
int t = le / i, tot = 0;
_myfor(j, 0, 26) if (cnt[j] >= t) tot += (cnt[j] / t);
if (tot >= i) {
ans = max(ans, le);
break;
}
}
}
cout << ans << endl;
}
return 0;
}
2、Task On The Board
给一个字符串(s)，长度为(m)的整数序列(b)，请构造出满足如下条件的字符串(str)：
- (b[i] = sum_{str[i] < str[j]}|i-j|)
(1 <= m <= len(s) <= 50)
题解
显然，如果(b[i] = 0) 说明第 (i) 位置的字符在字符串(str)中的字典序最大。
所以我们可以不断找出(b[i])为(0)的位置，然后依次填入相应的字符。
根据已知的(b[i] = 0)的位置（原始序列(b)），不断减去这些位置上字符的贡献：(b[j] = b[j] - sum_{str[j] < str[i]}|i - j|)，就能得到下一轮哪些位置((b[some\_{positon}] = 0))可以填。
倒推
sort(s.begin(), s.end());
int n = s.size();
vector<int> id;
while(true) {
id.clear();
// 找b[i] == 0的位置
myfor(i, 1, m) if (!b[i] && !use[i]) {
id.push_back(i);
use[i] = 1;
}
if ((int)id.size() <= 0) break;
// 填入字符
char tp;
for (int i = n - 1; i >= 0; i--) {
if (cnt[s[i] - 'a'] >= (int)id.size()) {
tp = s[i];
cnt[tp - 'a'] = 0;
break;
}
else cnt[s[i] - 'a'] = 0;
}
// 减去上一轮那些位置的贡献
for (auto i: id) {
ans[i] = tp;
myfor(j, 1, m) if (b[j]) b[j] -= abs(j - i);
}
}
myfor(i, 1, m) cout << ans[i];
cout << endl;
3、Two Divisors
给(n)个数，问每个数((a_i))是否存在两个因数(d_1)和(d_2)，使得(gcd(d_1 + d_2,a_i) = 1)。
(1<=n<=5*10^5,2<=a_i<=1*10^7)
题解
已知，任意一个数都可以写成几个质因数的乘积，比如(8 = 2^3,6 = 2 * 3。)
那么将这些质因数分成两个不相交的集合(s_1)和(s_2)，令(d_1= s1)中所有数的乘积，(d_2)同理，
有(gcd(d_1 + d_2, a_i) = 1) ，所以该问题等价于求(a_i)的两个不同的质因数。
最好用线性筛，在筛的同时求出每个合数的最小质因数。
/*
time:1800ms
*/
void Inite() {
prime[1] = 1;
for (int i = 2; i * i <= 10000009; i++) if (!prime[i]) {
p.push_back(i);
for (int j = i + i; j < N; j += i) prime[j] = 1;
}
}
int main()
{
Inite();
cin >> n;
myfor(i, 1, n) cin >> a[i];
vector<pair<int, int> > ans;
myfor(i, 1, n) {
int tp = a[i];
bool flag = false;
for (auto x: p) if (a[i] % x == 0) {
while(a[i] % x == 0) a[i] /= x;
if (a[i] != 1) ans.push_back(make_pair(tp / a[i], a[i]));
else ans.push_back(make_pair(-1, -1));
flag = true;
break;
}
if (!flag) ans.push_back(make_pair(-1, -1));
}
for (auto &x: ans) cout << x.first << " ";
cout << endl;
for (auto &x: ans) cout << x.second << " ";
cout << endl;
return 0;
}
4、Ehab and Prefix MEXs（好题）
给一个长度为(n)的序列(a)，求满足如下条件且长度为(n)的序列(b):
- 对于任意一个(i(1<=i<=n))，(MEX({b_1,b_2,···,b_i}) = a_i)
(MEX({···}))是指：不在给定集合的最小非负数，比如(MEX({1,2,3}) = 0)、(MEX{0,1,3} = 2)
(a_i <= a_{i + 1})，(0<=a_i<=i)
题解
构造方法：假设(a)中有(x)个不同的数（去重后统计）。如果(a[i] != a[i - 1])，那么(b[i] = a[i - 1])，因为(b[1],b[2],···,b[i - 1])都取不到(a[i -1])。这就填了(x - 1)个位置，然后剩下的(n - x + 1)个位置从小到大依次填入(a)中没有出现的数((n + 1 - x)个)，刚好填完。
困难在于怎么处理(a[i] ==a[i -1])的情况
//code_source: https://blog.csdn.net/qq_45458915/article/details/106822285
5、Game On Leaves
张三和李四在玩游戏：给一颗有(n)个节点的无根树，和特定的节点(x)。每轮的玩家选定一个(degree <= 1)的节点并将其移除，同时删除以该节点为端点的所有边。谁先移除节点(x)，则其成为赢家。在游戏过程中，他们都采取了最优的策略。问最后谁赢？（张三先手）
题解
Select any leaf node in the tree and remove it together with any edge which has this node as one of its endpoints. A leaf node is a node with degree less than or equal to 1.
无根树的叶子节点的度怎么等于0？ 估计是(n)可能为1吧，费解
两个人的最优策略是：优先删除其他无关的节点，尽量将(x)留在最后。又因为每次只删除叶子节点，所以判断一下(n - 1)的奇偶性就行。