D. Productive Meeting
贪心，STL
题意：
一共有n个人，每个人最多可以跟其他人交谈\(s_i\)次，问最多能让所有人交谈多少次。
思路：
一眼看出贪心，但在怎么贪的问题上出了问题。
一开始的想法是排序找到能跟他人交谈次数最多的那个人，优先满足他的所有交谈需求。打出来之后先WA再CE，非常崩溃。
最后去看了学长的代码，思路就是用堆来记录每个人当前剩余的交谈次数，每次取堆顶的两个元素让他们两个进行交谈，再将其交谈次数减一放回堆里，直到取出的第二个人的交谈次数为0结束。
反思：
有的时候虽然思路是对的但会在具体实现的时候出现问题，感觉还需要多练。
对于需要每次取最大值的贪心，特别是操作会改变其值的大小的类型，除了排序可以多考虑下用堆来存，方便后续拿取。
void QAQ() {
cin >> n;
queue<pii> q;
priority_queue<pii> heap;
for(int i = 1; i <= n; i++){
int x;
cin >> x;
heap.push({x, i});
}
while(1){
int x, xx, y, yy;
tie(x, xx) = heap.top();
heap.pop();
tie(y, yy) = heap.top();
heap.pop();
if(y == 0) break;
q.push({xx, yy});
heap.push({x - 1, xx});
heap.push({y - 1, yy});
}
cout << q.size() << endl;
while(!q.empty()){
pii x = q.front();
q.pop();
cout << x.first << " " << x.second << endl;
}
}
C. Strongly Composite
构造，数学
题意：
定义强合数为某数的全部因子中质数的个数小于等于非质数（注意1既不是质数也不是非质数）。我们有n个数，要求构造出一个新的数组使得数组内所有数都是强合数且他们的乘积和原来数组的乘积相同，求出新数组的最长长度。
思路：
当时比赛的时候看到数学就头疼然后跳了。赛后补题的时候感觉当时的自己脑子有问题，吸取教训以后不要畏惧数学
因为是乘积，可以很自然地想到质因数分解，也即是，只要几组数的每个质因数的个数之和都是一样的，那么这几组数的乘积一定相同。
那么思路就很简单了，对原数组里每个数进行质因数分解，记录每一个质因数的出现次数。然后我们再打一下表就可以发现，一个数如果有两个及以上相同的质因数，或是有三个不同的质因数，那么它就是一个强合数。
也就是说，对于出现的质因数p，统计其总共的出现次数，先尽可能地让它两个两个组队，再记录每个质因数最后剩下的个数（只可能是1或0），最后将剩下的个数三个三个组队，把两次组队个数相加就是最终的答案了。
void QAQ(){
cin >> n;
m = 1;
unordered_map<int, int> mp;
while(n --){
int x;
cin >> x;
for(int i = 2; i * i <= x; i ++){
if(x % i == 0){
while(x % i == 0) mp[i] ++, x /= i;
}
}
if(x != 1) mp[x] ++;
}
int ans = 0, tmp = 0;
for(auto x : mp){
ans += x.second / 2;
tmp += x.second % 2;
}
cout << ans + tmp / 3 << endl;
}
D. Unique Palindromes
构造
题意：
已知字符串长度为n，且在它第i个位置以前有j个不同的回文子串，对于这样的限制有m个，构造出一串字符使上述条件满足。
思路：
太妙了感觉自己很难想出来
很容易可以发现的一个性质是，由于题目要求得到的是不同的回文子串，所以假设有一个长度为a的字符串，能得到的最多的不同回文子串的个数只有a个（最简单的就是一整串全是同一个字母），在长度分别为a和b的串合并的时候，其合并后的回文子串个数一定小于等于a + b。
基于上面的性质，可以想到，如果字符串长度增加了t，回文子串个数增加了p
+ p > t，无法构造出满足条件的字符串。
+ p = t，让新增的子串全为之前没有出现过的某个字母
+ p < t，前面p个字母全为之前没有出现过的某个字母，后面重复之前出现过的字符串
看一眼题目的数据范围，发现每个字符串的限制条件个数最多只有20次，印证了上面想法的正确性。
但我们还会发现，如果设置第一段为"aaaaa"，第二段开头为"bb"，后面重复开头的"aaaaaaa"，一方面如果后面长度超过了第一段的长度，我们会产生新的回文串，另一方面如果最后得到的是"aaaaabbaa"，我们也会产生"abba"诸如此类的回文串，所以上面的想法还需要优化。
再注意下题目的数据范围，我们还可以发现第一个条件之前至少有3个字符串。这题最妙的想法就体现在这里了，将每个字符串开头的三个字母设为"abc"，要产生一个满足第一段的条件只需要在后续继续加"c"就可以了。第二段开头从"d"开始，满足条件后就用"abc"循环来补全。
还需要注意一点，假设上一节的末尾循环结束在"a"，那么下一节的循环要从"b"开始，否则也可能会产生新的回文子串。
void QAQ(){
cin >> n >> m;
for(int i = 1; i <= m; i ++) cin >> a[i];
for(int i = 1; i <= m; i ++) cin >> b[i];
for(int i = 1; i <= m; i ++){
if(a[i] - a[i - 1] < b[i] - b[i - 1]){
cout << "NO\n";
return ;
}
}
cout << "YES\n";
string ans;
char tmp = 'a';
for(int i = 1; i <= m ; i ++){
char k = 'a' + i + 1;
if(i == 1) b[i] -= 2, ans += "ab";
for(int j = 1; j <= b[i] - b[i - 1]; j ++) ans += k;
if(i == 1) b[i] += 2;
for(int j = 1; j <= (a[i] - a[i - 1]) - (b[i] - b[i - 1]); j ++){
if(tmp == 'd') tmp = 'a';
ans += tmp;
tmp ++;
}
}
cout << ans << endl;
}
D. Black Cells
贪心，决策
题意：
一共有编号1-1e9个格子，从0开始运动，有n段，当我们位于某一段内时，可以按下一个按钮，让我们从这格开始向后涂黑（注意向后涂黑时也是需要向后移动的，且不可以涂黑不属于任何段的格子），再次按下按钮将结束涂黑，问得到k个被涂黑的格子需要的最小操作次数。
思路：
一开始以为是个dp，看了题解发现是贪心，可惜还是想不出来。
一个很显然的决策就是，如果取t段能满足条件，这些段里有段没有全被涂黑且之前选的段里有长度为1的段，那么我们可以把没有涂黑的段涂黑，并将之前选的长度为1的段抛弃，这会让我们省掉1次操作次数。
首先，在不考虑向右移动的操作，只考虑选取区间的时候，我们很容易想到，每次选取最长的区间一定更优。对于从左到右的每个区间，我们选取长度 ≥ 2 的区间一定是不劣的。所以我们要尽可能地去选取。
假设我们在之前跳过了k个长度为1的区间，那么我们要考虑去把它补回来，最极限就是到当前节点之前的所有区间加起来正好等于k。为了尽可能多的那么对于它之后的区间，为了尽可能多地去选择长度大于等于2的区间，我们可以适当跳过一些长度为1的区间，以求出答案。特别的，当前面所有长度大于2的区间长度和大于k的时候，我们再选取后面的区间也不会更优，可以直接break掉。
那么就可以得到，假设当前枚举到第i段，之前跳过了cnt段，当前长度≥2的区间长度和为cur
if(cur + cnt <= k && cur <= k)
ans = min(ans, (i - cnt + k - cur) * 2 + edge[i].l)
else(cur > k)
ans = min(ans, edge[i].l - (cur - k) + (i - cnt)* 2)
//这一步做完就可以break了
void QAQ(){
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> num[i][1];
int cnt = 0;
for(int i = 1; i <= n; i++){
cin >> num[i][2];
num[i][0] = num[i][2] - num[i][1] + 1;
cnt += num[i][0];
}
if(cnt < m){
cout << "-1\n";
return ;
}
else if(cnt == m){
cout << num[n][2] + n * 2 << endl;
return ;
}
cnt = 0;
int cur = 0, ans = 0x3f3f3f3f3f3f3f3f;
for(int i = 1; i <= n; i++){
if(num[i][0] == 1){
cnt ++;
}
else{
cur += num[i][0];
}
if(cur >= m){
ans = min(ans, (i - cnt) * 2 + num[i][2] - (cur - m));
break;
}
else if(cur + cnt >= m){
ans = min(ans, num[i][2] + (i - cnt + m - cur) * 2);
}
}
cout << ans << endl;
}