5.8-5.14
C1. Pokémon Army (easy version)
Problem - 1420C1 - Codeforces
线性dp
呃啊啊啊啊啊啊啊太久没写dp了，下周开始要把重点放到算法上
意识到是个dp后就很简单了，状态转移方程也很好写出
然后就快乐地开始dp吧~
int n, m, f[N][2], num[N];
void QAQ(){
cin >> n >> m;
for(int i = 1; i <= n; i ++) cin >> num[i];
f[0][0] = f[0][1] = 0;
for(int i = 1; i <= n; i ++){
f[i][0] = max(f[i - 1][0], f[i - 1][1] + num[i]);
f[i][1] = max(f[i - 1][1], f[i - 1][0] - num[i]);
}
cout << max(f[n][0], f[n][1]) << endl;
}
A. Banana
Problem - 335A - Codeforces
构造
读了假题
注意到题目中每次购买的贴纸数可以是不连续的，这为我们省下了很多功夫。
其次注意到题目字符串长度小于1000，那么我们可以暴力枚举要买贴纸的次数，反推出需要原始子串的长度，看是否符合要求，符合要求就输出。
当然，如果使用二分会是更优的解法。（虽然最后运行时间没有差很多）
int n, k;
map<char, int> mp;
string s;
void QAQ(){
cin >> s >> k;
n = s.size();
int cnt = 0;
for(auto ch : s){
if(!mp[ch]) cnt ++;
mp[ch] ++;
}
if(cnt > k) {
cout << "-1\n";
return ;
}
int ans;
for(int i = 1; i <= 1000; i ++){
int sum = 0;
for(char j = 'a'; j <= 'z'; j ++){
sum += (mp[j] + i - 1) / i;
}
if(sum <= k){
ans = i;
break;
}
}
cout << ans << endl;
int len = 0;
for(char i = 'a'; i <= 'z'; i ++){
int t = (mp[i] + ans - 1) / ans;
len += t;
while(t --){
cout << i;
}
}
while(len < k){
cout << 'a';
len ++;
}
cout << endl;
}
int n, m;
map<char, int> mp;
string s;
//二分
bool check(int x){
int res = 0;
for(int i = 'a'; i <= 'z'; i ++){
res += (mp[i] + x - 1) / x;
}
return res > m;
}
void QAQ(){
cin >> s;
n = s.size();
s = " " + s;
cin >> m;
int cnt = 0;
for(int i = 1; i <= n; i++){
if(!mp[s[i]]) cnt ++;
mp[s[i]] ++;
}
if(cnt > m){
cout << "-1\n";
return ;
}
int r = n + 1, l = 0;
while(l + 1 < r){
int mid = l + r >> 1;
if(check(mid)){
l = mid;
}
else{
r = mid;
}
}
cout << r << endl;
cnt = 0;
for(int i = 'a'; i <= 'z'; i++){
int tmp = (mp[i] + r - 1) / r;
cnt += tmp;
while(tmp --){
cout << (char)i;
}
}
while(cnt < m){
cout << "a";
cnt ++;
}
cout << endl;
}
C. Element Extermination
Problem - 1375C - Codeforces
构造，结论
结论就是如果队头元素大于队尾元素，就一定不可以。
在洛谷上看到的题解，感觉相对比较好理解，记录一下。
假设当前有\(a_1,...,a_n\)个数，由于每次删去的条件是\(a_i<a_{i + 1}\)，所以为了增加删去最后一个元素的可能性，我们要尽可能地在前面删去的时候留下靠前面且较小的数。
那么对于第1个数，如果\(a_1<a_2\)，那么删去\(a_2\)，留下\(a_1\)，反之我们只可能尝试替换\(a_2\)，也将留下\(a_1\)，所以在最后一次操作之前，\(a_1\)始终能被保留。
同理，对于最后一个数，如果\(a_{n-1}<a_n\)，为了让最后一个数尽可能大，我们选择保留\(a_n\)，反之，我们就尝试替换\(a_{n-1}\)，使得之前能被满足，所以\(a_n\)也会被一直保留。
那么按照上面的思路，不考虑中间的元素是否能被删完，一串数能否被删完的关键在于它的首元素和尾元素能否被删去（即我们现在只关注每次操作的最后一步）
最终得到结论，如果\(a_1<a_n\)，那么就可以删完，否则就不能删完。
代码很简单就不给出了。
B. Find The Array
Problem - 1463B - Codeforces
构造
有两种不同的思路（当然都是看了题解后得到的思路）
-
变1构造
什么样的串符合它的所有相邻的数都能被彼此整除呢？我们能想到的最简单的数组就是一串全为1的数列，但是很明显，由于题目有着\(2\sum_{i=1}^n|a_i-b_i|\leq\sum_{i=1}^na_i\)，所以我们不可能让所有元素都变成1。
那么该怎么去构造呢？既然不能让所有元素都变成1，事实上间隔地把数变成1也是可以满足我们的要求的。那么这种方法是否符合我们上面的式子呢？我们会很惊奇地发现，如果偶数位上数的和较小，我们就把偶数位变成1，否则就把奇数位变成1，最终都是可以满足题目的要求的。
int n, num[N]; void QAQ(){ cin >> n; int a = 0, b = 0; for(int i = 1; i <= n; i++){ cin >> num[i]; if(i & 1) a += num[i] - 1; else b += num[i] - 1; } if(a < b){ for(int i = 1; i <= n; i ++){ if(i & 1) cout << "1" << " "; else cout << num[i] << " "; } } else{ for(int i = 1; i <= n; i ++){ if(i & 1) cout << num[i] << " "; else cout << "1" << " "; } } cout << endl; } -
2的k次方构造
我们仍然着眼于题目给出的第二个性质，即\(2\sum_{i=1}^n|a_i-b_i|\leq\sum_{i=1}^na_i\)。
如果我们一项项来看这条式子，那么就会得到\(2*|a_i-b_i|\leq a_i\)，也即是\(b_i \sub [\frac{a_i}2,\ 2a_i]\)。仔细推一下就会发现，一定存在一个\(2^k\)在上面的范围内，使得上面的等式成立。而且对于每一对\(2^t\)和\(2^k\)，它们两个一定可以满足整除的关系。
由于\(2^k\)次方可以简单地通过1左移k次得到，我们就不用预处理。只需要从小到大枚举k，找到第一个 能使上述等式成立的输出就可以了。
int n, num[N]; void QAQ() { cin >> n; for(int i = 1; i <= n; i ++) cin >> num[i]; for(int i = 1; i <= n; i ++){ int k = 1; while(2 * abs(k - num[i]) > num[i]) k <<= 1; cout << k << " "; } cout << endl; }
C. 0689
题目详情 - 4128 0689 (pintia.cn)
题意：
有一串子串只包含'0'，'6'，'8'，'9'四种字符。可以选择任意长度的子串进行180°翻转，使得其左右位置调换的同时'0'->'0'，'6'->'9'，'9'->'6'，'8'->'8'。问每次进行一次上述操作，最多可以得到多少个不同的字串。
思路：
一开始以为是找回文子串，跟队友口胡了一个Manacher的做法感觉很合理，但是WA了，后面被另一个队友批判原来做法没有排除改变后相同的情况。最后看了题解，感觉想法非常玄妙啊。
如果不考虑重复的情况，那么对于长度为n的字符串，可以选择左右区间产生子串的个数就是\(\frac{n(n + 1)}{2}\)。对于选择的子串，如果我们选择如"0xxxx0"、"6xxxx9"、"8xxx8"等翻转后不会变化的数字为左右开头，实际上会与我们选择其除去两端后的字符串翻转后重复。为了排除这些重复，我们需要减去以上述情况开头的选择。
void QAQ() {
string s;
cin >> s;
n = s.size();
int a = 0, b = 0, c = 0, d = 0;
for(auto x : s){
if(x == '0') a ++;
else if (x == '6') b ++;
else if(x == '8') c ++;
else if(x == '9') d ++;
}
int ans = n * (n + 1) / 2 + 1;
ans -= a * (a + 1) / 2;//以0为左右端点的重复选择
ans -= b * d;//以69为左右端点的重复选择
ans -= c * (c + 1) / 2;//以8为左右端点的重复选择
if(b == n || d == n) ans --;
//如果全为'6'或'9'，无法构造出原串，所以要减去
cout << ans << endl;
}
特别的，需要注意实际上原串并不是答案的一部分，除非我们能通过翻转构造回原串（即选择翻转后不变的子串），但这些子串在后面去重的时候会被丢弃，所以实际上我们需要在计算结果时+1。但是当一串里面只存在'6'或是'9'时，无论我们怎么选择都无法得到原来的串，所以需要减去之前加上的1。