跳过了一些困难的题开一场新的。看来2100的题还是要慢慢挑战，不能操之过急。
A - Prime Subtraction
题意：给两个数x,y，可以从x中减去任意个相同的质数p，问能不能与y相等。
题解：首先x>=y，然后差值不能为1，否则一定可以。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void test_case() {
ll x, y;
scanf("%lld%lld", &x, &y);
if(x < y || x == y + 1)
puts("NO");
else
puts("YES");
}
int main() {
#ifdef KisekiPurin
freopen("KisekiPurin.in", "r", stdin);
#endif // KisekiPurin
int t = 1;
scanf("%d", &t);
for(int ti = 1; ti <= t; ++ti) {
//printf("Case #%d: ", ti);
test_case();
}
}
B - Kill 'Em All
题意：x正半轴上有n个怪物，分别在xi处。每次可以发射一颗导弹，命中位置的怪物被秒杀，其他怪物会被推向两边（位移为r），被推到非负半轴的也会被秒杀。求最少的导弹。
题解：假如没有“被推到非负半轴的也会被秒杀”，那么数量就是怪物离散化坐标的数量，现在要充分利用这个条件，显然要把怪物从最右边开始推过去。记录累计的导弹数量就可以了。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e5;
int a[MAXN + 5];
void test_case() {
int n, r;
scanf("%d%d", &n, &r);
for(int i = 1; i <= n; ++i)
scanf("%d", &a[i]);
sort(a + 1, a + 1 + n);
n = unique(a + 1, a + 1 + n) - (a + 1);
int suml = 0, cnt = 0;
for(int i = n; i >= 1; --i) {
if(a[i] > suml) {
++cnt;
suml += r;
} else
break;
}
printf("%d
", cnt);
}
int main() {
#ifdef KisekiPurin
freopen("KisekiPurin.in", "r", stdin);
#endif // KisekiPurin
int t = 1;
scanf("%d", &t);
for(int ti = 1; ti <= t; ++ti) {
//printf("Case #%d: ", ti);
test_case();
}
}
C - Standard Free2play
题意：你的游戏角色站在h层高的平台，当你站在平台上时，你必须拉动开关使得当前平台及他的下一层平台的伸出/收起状态改变，然后你可以落下至多2层。你可以用水晶改变除了h层的每个平台的初始状态。求最少的水晶。
题解：看起来像dp，设dp[i]表示从h层下到第i层的需要的最小花费。转移非常显然。但是h太大了。然后显然的假如h下面一直都没有东西，角色可以一直拉动开关降到地面。但是当中间有至少一个平台时，会面临自己下方的平台x-1本身是伸出的情况，这时假如再下一层还有平台x-2就可以直接无视然后掉到x-2，否则就要花一颗水晶消除它。所以就是可以一次消灭两个连续的数字中的高的那个，然后从低的那个继续开始。简化问题可以把0层也作为一块伸出的平台。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 2e5;
int p[MAXN + 5];
void test_case() {
int h, n;
scanf("%d%d", &h, &n);
for(int i = 1; i <= n; ++i)
scanf("%d", &p[i]);
if(n == 1) {
printf("0
");
return;
}
int cnt = 0, cur = h;
p[n + 1] = 0;
for(int i = 2; i <= n; ++i) {
cur = p[i] + 1;
if(p[i] == p[i + 1] + 1) {
cur = p[i + 1];
++i;
} else
++cnt;
}
printf("%d
", cnt);
}
int main() {
#ifdef KisekiPurin
freopen("KisekiPurin.in", "r", stdin);
#endif // KisekiPurin
int t = 1;
scanf("%d", &t);
for(int ti = 1; ti <= t; ++ti) {
//printf("Case #%d: ", ti);
test_case();
}
}
D - AB-string
题意：一个只由AB组成的字符串s，定义一个字符串是好的，当它每个字母都至少属于一个长度>1的回文串。求s的好的子串的数量。
题解：模拟一下题意，发现不好的长度>1串必须满足这四种形式：
AA...AB
BB...BA
ABB...B
BAA...A
分几种情况统计，第一种统计连续A的数量，遇到B的时候统计；第二种同理；第三种，统计前一个字母是A的连续B的数量，在这个连续B结束（遇到A/遇到字符串结尾）时统计，第四种同理。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 3e5;
char s[MAXN + 5];
ll dp[MAXN + 5][4];
void test_case() {
int n;
scanf("%d%s", &n, s + 1);
if(n == 1) {
puts("0");
return;
}
ll cnt = 0;
dp[1][0] = (s[1] == 'A');
dp[1][1] = (s[1] == 'B');
dp[1][2] = 0, dp[1][3] = 0;
for(int i = 2; i <= n; ++i) {
if(s[i] == 'A') {
dp[i][0] = dp[i - 1][0] + 1;
dp[i][1] = 0;
dp[i][2] = dp[i - 1][2] ? dp[i - 1][2] + 1 : s[i - 1] != s[i];
dp[i][3] = 0;
cnt += dp[i - 1][1];
cnt += dp[i - 1][3] - (dp[i - 1][3] >= 1);
} else {
dp[i][0] = 0;
dp[i][1] = dp[i - 1][1] + 1;
dp[i][2] = 0;
dp[i][3] = dp[i - 1][3] ? dp[i - 1][3] + 1 : s[i - 1] != s[i];
cnt += dp[i - 1][0];
cnt += dp[i - 1][2] - (dp[i - 1][2] >= 1);
}
//printf("i=%d
cnt=%lld
",i,cnt);
}
cnt += dp[n][2] - (dp[n][2] >= 1);
cnt += dp[n][3] - (dp[n][3] >= 1);
printf("%lld
", 1ll * n * (n - 1) / 2 - cnt);
}
int main() {
#ifdef KisekiPurin
freopen("KisekiPurin.in", "r", stdin);
#endif // KisekiPurin
int t = 1;
//scanf("%d", &t);
for(int ti = 1; ti <= t; ++ti) {
//printf("Case #%d: ", ti);
test_case();
}
}
E - Keyboard Purchase
题意：你要输入一串n长包含前m个小写英文字母的密码，你要购买一种所有键是m种字母的一个排列的直线的键盘，手指移动的距离就是相邻两个字母的键盘距离的总和。求最小的手指移动距离。
题解：看见m<=20，假如m<=6岂不是枚举全排列然后暴力验证？可惜改不得。但是这个数据量暗示什么？暗示可以状压，于是口胡一种做法。dp[i][j]表示把状态j中选出的字母全部排在左边，顺序任意，解决前i位密码的最短距离？忽视了一点，这个是有后效性的，前面字母排列的顺序是会影响后面的手指距离的。不懂怎么写，看题解。
题解也是状压dp，但是是逐个字母加进来的而不是与密码的顺序有关，首先统计出每两个字母的相邻的对数，然后密码就没用了。设dp[j]为把状态j中选出的字母全部排在左边，顺序任意，形成的最短距离。显然的dp[0]=0。考虑加入一种字母x，遍历
参考资料：
Educational Codeforces Round 74 Editorial - Codeforces
Codeforces 1238E. Keyboard Purchase - LLTYYC - 博客园