## D1T1 玩具谜题

### 代码如下

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
char s[100003][11];
int a[100003];
int main(){
int i, j, n, m, t = 1, w;
scanf("%d%d", &n, &m);
for(i = 1; i <= n; i++){
scanf("%d%s", &a[i], s[i]);
}
for(i = 1; i <= m; i++){
scanf("%d%d", &j, &w);
if(!(j ^ a[t])) t = (t - w + n - 1) % n + 1;
else t = (t + w - 1) % n + 1;
}
printf("%s", s[t]);
return 0;
}


## D2T2 天天爱跑步

### 分析

$de{p}_{t}=de{p}_{i}+{w}_{i}$，这样一来我们统计每个观察员 $i$ 能观察到多少从下面上来的人只需要看 $i$ 的子树中有多少 $de{p}_{j}=de{p}_{i}+{w}_{i}$ 的即可。（被统计的前提当然是那条链经过 $i$

### 代码如下

#include <bits/stdc++.h>
#define lson l, m, lch[rt]
#define rson m + 1, r, rch[rt]
#define N 300005
using namespace std;
struct node{
int a, b, n;
}d[N * 2];
int h[N], cnt, ret, tot;
int fa[N], son[N], dfn[N], siz[N], dep[N], top[N], re[N], w[N];
int x[N], y[N], lca[N], len[N], ans[N];
int root[N * 10], lch[N * 30], rch[N * 30], sum[N * 30];
void cr(int a, int b){
d[++cnt].a = a; d[cnt].b = b; d[cnt].n = h[a]; h[a] = cnt;
}
void dfs1(int a){
int i, b;
siz[a] = 1;
for(i = h[a]; i; i = d[i].n){
b = d[i].b;
if(b == fa[a]) continue;
fa[b] = a;
dep[b] = dep[a] + 1;
dfs1(b);
siz[a] += siz[b];
if(siz[b] > siz[son[a]]) son[a] = b;
}
}
void dfs2(int a, int f){
int i, b;
top[a] = f;
dfn[a] = ++tot; re[tot] = a;
if(son[a]) dfs2(son[a], f);
for(i = h[a]; i; i = d[i].n){
b = d[i].b;
if(b != son[a] && b != fa[a]) dfs2(b, b);
}
}
int get(int a, int b){
int f1 = top[a], f2 = top[b];
while(f1 != f2){
if(dep[f1] < dep[f2]) swap(f1, f2), swap(a, b);
a = fa[f1], f1 = top[a];
}
if(dep[b] < dep[a]) return b;
return a;
}
void update(int l, int r, int &rt, int p,  int c){
if(!p) return;
if(!rt) rt = ++ret;
sum[rt] += c;
if(l == r) return;
int m = l + r >> 1;
if(p <= m) update(lson, p, c);
else update(rson, p, c);
}
int query(int l, int r, int rt, int a, int b){
if(!rt) return 0;
if(l >= a && r <= b) return sum[rt];
int m = l + r >> 1, ans = 0;
if(a <= m) ans += query(lson, a, b);
if(b > m) ans += query(rson, a, b);
return ans;
}
int main(){
int i, j, n, m, a, b;
scanf("%d%d", &n, &m);
for(i = 1; i < n; i++){
scanf("%d%d", &a, &b);
cr(a, b);
cr(b, a);
}
dfs1(1);
dfs2(1, 1);
for(i = 1; i <= n; i++) scanf("%d", &w[i]);
for(i = 1; i <= m; i++){
scanf("%d%d", &x[i], &y[i]);
lca[i] = get(x[i], y[i]);
len[i] = dep[x[i]] + dep[y[i]] - 2 * dep[lca[i]];
update(1, n, root[dep[x[i]]], dfn[x[i]], 1);
update(1, n, root[dep[x[i]]], dfn[fa[lca[i]]], -1);
}
//printf("---------\n");
//for(i = 1; i <= m; i++) printf("%d ", lca[i]);
for(i = 1; i <= n; i++) ans[i] += query(1, n, root[dep[i] + w[i]], dfn[i], dfn[i] + siz[i] - 1);
//for(i = 1; i <= m; i++) printf("%d ", len[i]);
//printf("\n");
memset(sum, 0, sizeof(sum));
memset(root, 0, sizeof(root));
memset(lch, 0, sizeof(lch));
memset(rch, 0, sizeof(rch));
for(i = 1; i <= m; i++){
update(1, n, root[len[i] - dep[y[i]] + N], dfn[y[i]], 1);
update(1, n, root[len[i] - dep[y[i]] + N], dfn[lca[i]], -1);
}
for(i = 1; i <= n; i++) ans[i] += query(1, n, root[w[i] - dep[i] + N], dfn[i], dfn[i] + siz[i] - 1);
for(i = 1; i <= n; i++) printf("%d ", ans[i]);
return 0;
}


## D1T3 换教室

### 代码如下

#include <bits/stdc++.h>
#define N 2005
#define maxn 90000000
#define inf 2147483647
using namespace std;
int c[N], d[N], mp[305][305];
double k[N], f[N][N][2], ans = inf;
int main(){
int i, j, t, n, m, v, e, a, b;
for(i = 1; i <= 300; i++){
for(j = 1; j <= 300; j++){
mp[i][j] = 30000000;
}
}
scanf("%d%d%d%d", &n, &m, &v, &e);
for(i = 1; i <= n; i++) scanf("%d", &c[i]);
for(i = 1; i <= n; i++) scanf("%d", &d[i]);
for(i = 1; i <= n; i++) scanf("%lf", &k[i]);
for(i = 1; i <= e; i++){
scanf("%d%d%d", &a, &b, &t);
if(mp[a][b] > t) mp[a][b] = mp[b][a] = t;
}
for(i = 1; i <= v; i++) mp[i][i] = 0;
for(t = 1; t <= v; t++){
for(i = 1; i <= v; i++){
for(j = 1; j <= v; j++){
mp[i][j] = min(mp[i][j], mp[i][t] + mp[t][j]);
}
}
}
for(i = 0; i <= 2000; i++)
for(j = 0; j <= 2000; j++) f[i][j][0] = f[i][j][1] = maxn;
f[1][0][0] = f[1][1][1] = 0;
for(i = 2; i <= n; i++){
f[i][0][0] = f[i - 1][0][0] + mp[c[i - 1]][c[i]];
for(j = 1; j <= m; j++){
f[i][j][0] = min(f[i - 1][j][0] + mp[c[i - 1]][c[i]], f[i - 1][j][1] + k[i - 1] * mp[d[i - 1]][c[i]] + (1 - k[i - 1]) * mp[c[i - 1]][c[i]]);
f[i][j][1] = min(f[i - 1][j - 1][0] + k[i] * mp[c[i - 1]][d[i]] + (1 - k[i]) * mp[c[i - 1]][c[i]], f[i - 1][j - 1][1] + k[i] * k[i - 1] * mp[d[i - 1]][d[i]] + k[i] * (1 - k[i - 1]) * mp[c[i - 1]][d[i]] + (1 - k[i]) * k[i - 1] * mp[d[i - 1]][c[i]] + (1 - k[i]) * (1 - k[i - 1]) * mp[c[i - 1]][c[i]]);
}
}
for(i = 0; i <= m; i++) ans = min(ans, min(f[n][i][0], f[n][i][1]));
printf("%.2lf", ans);
return 0;
}


## D2T1 组合数问题

### 分析

$k$ 的倍数，然后用二维前缀和即可 $O\left(1\right)$ 回答询问。

### 代码如下

#include <bits/stdc++.h>
#define N 2005
using namespace std;
int c[N][N], s[N][N];
int main(){
int i, j, n, m, t, k;
scanf("%d%d", &t, &k);
for(i = 0; i <= 2000; i++){
c[i][0] = 1;
for(j = 1; j <= i; j++){
c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % k;
if(!c[i][j]) s[i][j] = 1;
//printf("%d %d %d\n", i, j, s[i][j]);
}
if(i > 1)
for(j = 1; j <= 2000; j++){
s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
}
}
while(t--){
scanf("%d%d", &n, &m);
if(m > n) m = n;
printf("%d\n", s[n][m]);
}
return 0;
}


## D2T2 蚯蚓

### 代码如下

#include <bits/stdc++.h>

#define N 7000005
#define LL long long
#define inf 2147483647
using namespace std;
LL a[N], b[N], c[N];
int p1, q1, p2, q2, p3, q3;
LL z = 1, maxn;
int cmp(int x, int y){
return x > y;
}
int main(){
int i, j, n, m, q, u, v, t;
int p;
scanf("%d%d%d%d%d%d", &n, &m, &q, &u, &v, &t);
for(i = 1; i <= n; i++) scanf("%lld", &a[i]);
sort(a + 1, a + i, cmp);

p1 = p2 = p3 = 1, q1 = n;
for(i = 1; i <= m; i++){
maxn = -inf;
if(p1 <= q1 && maxn < a[p1]) p = 1, maxn = a[p1];
if(p2 <= q2 && maxn < b[p2]) p = 2, maxn = b[p2];

if(p3 <= q3 && maxn < c[p3]) p = 3, maxn = c[p3];
maxn += (i - 1) * q;
if(i % t == 0) printf("%lld ", maxn);
b[++q2] = maxn * u / v - i * q;
c[++q3] = maxn - maxn * u / v - i * q;
if(p == 1) p1++;
if(p == 2) p2++;
if(p == 3) p3++;
//printf("%d %d %d\n", p1, p2, p3);
}
//printf("====%d %d\n====%d %d\n====%d %d\n", p1, q1, p2, q2, p3, q3);
printf("\n");
for(i = 1; ; i++){
if(p1 > q1 && p2 > q2 && p3 > q3) break;

maxn = -inf;
if(p1 <= q1 && maxn < a[p1]) p = 1, maxn = a[p1];
if(p2 <= q2 && maxn < b[p2]) p = 2, maxn = b[p2];

if(p3 <= q3 && maxn < c[p3]) p = 3, maxn = c[p3];
if(i % t == 0) printf("%lld ", maxn + m * q);
if(p == 1) p1++;
if(p == 2) p2++;
if(p == 3) p3++;
}
return 0;
}


## D2T3 愤怒的小鸟

### 分析

$f\left[s\right]=min\left(f\left[s$^ $\left(s$& $g\left[i\right]\left[j\right]\right)\right]+1\right)$，就是先取 $s$ $g\left[i\right]\left[j\right]$ 的交集，然后咔咔掉。这样子复杂度时 $O\left({n}^{2}\ast {2}^{n}\right)$的，能不能更优呢？当然可以。

### 代码如下

//f[s] = min(f[s ^ g[i][j]] + 1)
#include <bits/stdc++.h>
#define eps 1e-6
using namespace std;
int f[1 << 20], g[20][20], re[1 << 20];
double a, b, x[20], y[20];
double get(double x1, double y1, double x2, double y2){
return (y1 - y2 * x1 / x2) / (x1 * x1 - x1 * x2);
}
int main(){
int i, j, k, n, m, T, s;

for(i = 0; i < 20; i++) re[1 << i] = i;
//printf("%d", re[4]);
scanf("%d", &T);
while(T--){
memset(f, 1, sizeof(f));
memset(g, 0, sizeof(g));
scanf("%d%d", &n, &m);
for(i = 0; i < n; i++) scanf("%lf%lf", &x[i], &y[i]);
for(i = 0; i < n; i++){
for(j = i + 1; j < n; j++){
if(fabs(x[i] - x[j]) < eps) continue;
a = get(x[i], y[i], x[j], y[j]);
if(a > -eps) continue;
b = (y[i] - a * x[i] * x[i]) / x[i];
for(k = 0; k < n; k++){
if(fabs(y[k] - a * x[k] * x[k] - b * x[k]) < eps) g[i][j] |= (1 << k);
}
//printf("%d %d %d\n", i, j, g[i][j]);
}
}
f[0] = 0;
for(s = 1; s < (1 << n); s++){
j = re[s&-s];
f[s] = min(f[s], f[s ^ (1 << j)] + 1);
for(i = j + 1; i < n; i++){
if(1 << i & s) f[s] = min(f[s], f[s ^ (s & g[j][i])] + 1);
}
}
printf("%d\n", f[(1 << n) - 1]);
}
return 0;
}