这场好水啊。。。手速场，手速不够还是不行啊。
A - ABC Preparation
签到题，取四个值当中最小的即可。
#include <bits/stdc++.h>
using namespace std;
int main() {
int ans = 0x3f3f3f3f;
for (int i = 0; i < 4; i++) {
int x;
cin >> x;
ans = min(ans, x);
}
printf("%d", ans);
return 0;
}
B - Smartphone Addiction
直接模拟，对于每个充电和耗电的区间计算是否满足要求即可。
#include <bits/stdc++.h>
using namespace std;
int n, m, t, limit;
int a, b, lst;
int main() {
cin >> n >> m >> t;
limit = n;
for (int i = 1; i <= m; i++) {
cin >> a >> b;
n -= a - lst;
if (n <= 0) {
puts("No");
return 0;
}
n += b - a;
n = min(n, limit);
lst = b;
}
n -= t - lst;
if (n <= 0) {
puts("No");
return 0;
}
puts("Yes");
return 0;
}
C - Duodecim Ferra
直接背包dp，记 (f[i][j]) 代表用 (i) 个正整数凑出 (j) 的方案数，(f[i][j]+=f[i-1][j-k])，注意因为是正整数所以当 (j<i) 时 (f[i][j]=0)。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int L;
ll f[15][205];
int main() {
scanf("%d", &L);
f[0][0] = 1;
for (int i = 1; i <= 12; i++) {
for (int k = 1; k <= L; k++) {
for (int j = L; j >= max(k, i); j--) {
f[i][j] += f[i - 1][j - k];
}
}
}
printf("%lld", f[12][L]);
return 0;
}
D - Stamp
题意比较迷惑，看了样例才懂。
直接取每一段白色的长度的最小值，(k) 一定不能大于这个，而 (k) 越大越好，所以 (k) 一定等于这个。然后再对每一个空隙计算，设某一段是 (L)，则需 (lceilfrac{L}{k} ceil)。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m, a[200005];
ll ans;
int gcd(int x, int y) {
return y == 0 ? x : gcd(y, x % y);
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) scanf("%d", &a[i]);
sort(a + 1, a + 1 + m);
int lst = 0, g = 1e9 + 7;
a[++m] = n + 1;
for (int i = 1; i <= m; i++) {
if (a[i] - lst - 1 != 0) g = min(g, a[i] - lst - 1);
lst = a[i];
}
lst = 0;
for (int i = 1; i <= m; i++) {
if (a[i] - lst - 1 != 0) ans += (a[i] - lst - 1 + g - 1) / g;
lst = a[i];
}
printf("%lld", ans);
return 0;
}
E - Sequence Matching
思博dp题，记 (dp[i][j]) 为答案，有方程 (dp[i][j]=min(dp[i-1][j],dp[i][j-1])+1)，这是第一种转移，意义是删掉 (i) 或者 (j)。
若 (a[i]=b[j]) 则还可以从 (dp[i-1][j-1]) 转移，因为有 (a[i],b[j]) 这一对不会影响答案。若没有则还可以 (dp[i-1][j-1]) 意义也是不删但是 (y + 1)。
注意初始化 (dp[i][0]=i,dp[0][j]=j,dp[0][0]=0)。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m, a[1005], b[1005];
int dp[1005][1005];
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
for (int i = 1; i <= m; i++) scanf("%d", &b[i]);
memset(dp, 0x3f, sizeof(dp));
dp[0][0] = 0;
for (int i = 1; i <= n; i++) dp[i][0] = i;
for (int i = 1; i <= m; i++) dp[0][i] = i;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (a[i] == b[j]) dp[i][j] = min(dp[i][j], dp[i - 1][j - 1]);
dp[i][j] = min(dp[i][j], dp[i - 1][j] + 1);
dp[i][j] = min(dp[i][j], dp[i][j - 1] + 1);
dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + 1);
}
}
printf("%d", dp[n][m]);
return 0;
}
F - Range Xor Query
考虑第二种操作可以用前缀异或和做，(sum(l,r)=sum(1,r) ext{^}sum(1,l-1))，所以我们可以维护前缀和。对于第一种操作可以看成单调加（异或满足交换律），所以可以用树状数组维护，基本就是树状数组板子改几个运算符。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m;
int a[300005];
int BIT[300005];
void add(int x, int v) {
while (x <= n) {
BIT[x] ^= v;
x += (x & (-x));
}
}
int ask(int x) {
int ret = 0;
while (x) {
ret ^= BIT[x];
x -= (x & (-x));
}
return ret;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
add(i, a[i]);
}
for (int i = 1; i <= m; i++) {
int t, x, y;
scanf("%d%d%d", &t, &x, &y);
if (t == 1) {
add(x, y);
} else {
printf("%d
", ask(y) ^ ask(x - 1));
}
}
return 0;
}