本文最后更新于 108 天前，其中的信息可能已经有所发展或是发生改变。
写博客还是颇能倒逼自己学习的，终于让自己的训练步入正轨了，之后要越来越频繁的补题才可以。不过最近考试多起来了，要开始突击了。哎，上大学就是屁事多。
A.Two Screens.
签到题，有两种操作，一种操作是从头复制一个字符串，一种操作是在指定的字符串后面加字符串。不难发现最少的操作时间是求出最长公共前缀数量 – 1就好
void solve(){
std::string s1,s2;
cin >> s1 >> s2;
int len = std::min(s1.size(),s2.size());
int cnt = 0;
for(int i = 0;i < len;i++){
if(s1[i] == s2[i])cnt++;
else break;
}
if(cnt) cnt--;
cout << s1.size() + s2.size() - cnt << '\n';
}
B.Binomial Coefficients, Kind Of
模拟发现答案为$2^k$,直接输出
void solve(){
int n;
cin >> n;
for(int i = 1,x;i <= n;i++){
cin >> x;
}
for(int i = 1,x;i <= n;i++){
cin >> x;
cout << qpow(2,x) << ' ';
}
}
C.New Game
题意很明显，就是有n个卡牌，同一个数值的卡牌我可以任意选取，不同数值的卡牌我最多能选取k个，如果我第一回合拿的数量大小是x，则下一回合能拿的就是x + 1。考虑双指针做法。
每一个卡牌的数值都找到他能找到的最右端点，找完这个数值就让l向右移动找下一个数值，注意，一定要记得如果l比r大要把r置成l。
void solve(){
int n,k;
cin >> n >> k;
for(int i = 1;i <= n;i++){
cin >> a[i];
}
std::sort(a + 1,a + n + 1);
int ans = 0,l = 1,r = 1;
while(l <= n){
r = std::max(l,r);
while(r < n && a[r + 1] - a[r] <= 1 && a[r + 1] - a[l] < k) r++;
ans = std::max(ans,r - l + 1);
while(l < n && a[l + 1] == a[l]) l++;
l++;
}
cout << ans << '\n';
}
D. Attribute Checks
没做出来，参考了别人的代码
告诉你你总共有m个属性点，有n次的属性检查，分别检查的是力量和和智力，问最多通过检查的次数。
双指针做法，将非0的部分用前缀和表示
dp的状态用f[i]表示有i个点给力量n – i个点给智力，思路就是找中间出现的0，然后在力量和智力中间进行状态的转移无非是每一次出现非0的元素 {S,T}->{S,T+1} 或者 {S,T}->{S+1,T}，取max就好
void solve(){
int n,m;
cin >> n >> m;
for(int i = 0;i < n;i++){
cin >> a[i];
}
int x = 0,l = 0;
while(l < n && a[l] != 0) l++;
while(l < n){
int r = l + 1;
while(r < n && a[r] != 0){ //找下一个检查点
if(a[r] > 0) t[a[r]]++; //智力的前缀和
else s[-a[r]]++;
r++;
}
for(int i = 1;i <= m;i++){
s[i] += s[i-1];
t[i] += t[i-1];
}
for(int i = 0;i <= x + 1;i++){
g[i] = f[i];
g[i] = std::max(g[i],f[i - 1]); //每次加点有两种情况，一种是给智力加点，一种是给力量加点
}
x++;
//加上新增的0
for(int i = 0;i <= x;i++){
f[i] = g[i] + s[i] + t[x-i];
}
for(int i = 0;i <= m;i++) s[i] = t[i] = 0;
l = r ;
}
int ans = 0;
for(int i = 1;i <= m;i++){
ans = std::max(ans,f[i]);
}
cout << ans << '\n';
}