NOIP2016题目整合

今天终于拿到官方数据，兴致勃勃地全 A 了。

Day 1 T1 toy

处理一下正负号加加减减取模乱搞就好了。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;

int read() {
    int x = 0, f = 1; char c = getchar();
    while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); }
    while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); }
    return x * f;
}

#define maxn 100010
int n, q;
struct Toy { int tp; char S[15]; } ts[maxn];

int main() {
	freopen("toy.in", "r", stdin);
	freopen("toy.out", "w", stdout);
    n = read(); q = read();
    for(int i = 0; i < n; i++) {
        int t = read(); scanf("%s", ts[i].S);
        if(!t) ts[i].tp = 1;
        else ts[i].tp = -1;
    }
    int p = 0;
    while(q--) {
        int a = read(), b = read();
        if(a) a = 1; else a = -1;
        p += a * ts[p].tp * b;
        p = (p % n + n) % n;
    }
    
    printf("%s
", ts[p].S);
    
    return 0;
}

Day 1 T2 running

受到“链”和“S 恒为 1”和“T 恒为 1”的特殊点的启发，我们发现可以将每条链 [S_i, T_i] 分成 [S_i, C_i] 和 [C_i, T_i] 两条，然后对于一个全部可观测到的链 [C_i, T_i] 将所有 W_i 减去深度是一个定值，对于 [S_i, C_i] 的部分所有 W_i 加上深度是一个定值。于是树链剖分再打打标记统计就好了。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;

int read() {
    int x = 0, f = 1; char c = getchar();
    while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); }
    while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); }
    return x * f;
}

#define maxn 300010
#define maxm 600010
#define maxs 12000010
int n, q, m, head[maxn], next[maxm], to[maxm], W[maxn];
struct Player {
    int s, t, c;
    Player() {}
    Player(int _, int __): s(_), t(__) {}
} ps[maxn];

void AddEdge(int a, int b) {
    to[++m] = b; next[m] = head[a]; head[a] = m;
    swap(a, b);
    to[++m] = b; next[m] = head[a]; head[a] = m;
    return ;
}

int fa[maxn], dep[maxn], siz[maxn], son[maxn], top[maxn], pos[maxn], pid[maxn], clo;
void build(int u) {
    siz[u] = 1;
    for(int e = head[u]; e; e = next[e]) if(to[e] != fa[u]) {
        fa[to[e]] = u;
        dep[to[e]] = dep[u] + 1;
        build(to[e]);
        siz[u] += siz[to[e]];
        if(siz[son[u]] < siz[to[e]]) son[u] = to[e];
    }
    return ;
}
void gett(int u, int tp) {
    top[u] = tp; pid[++clo] = u; pos[u] = clo;
    if(son[u]) gett(son[u], tp);
    for(int e = head[u]; e; e = next[e])
        if(to[e] != fa[u] && to[e] != son[u]) gett(to[e], to[e]);
    return ;
}
int lca(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];
    }
    return dep[a] < dep[b] ? a : b;
}

struct Info {
    int c, fir[maxn], aft[maxs], val[maxs];
    void clear() {
        c = 0;
        memset(fir, 0, sizeof(fir));
        return ;
    }
    void AddInfo(int x, int v) {
        val[++c] = v; aft[c] = fir[x]; fir[x] = c;
        return ;
    }
} add, del;
int tot[maxn<<1], ans[maxn];
void process(int x, int t, int a, int v) {
    int f = top[a];
    while(f != top[t]) {
        add.AddInfo(pos[f], v);
        del.AddInfo(pos[a], v);
        a = fa[f]; f = top[a];
    }
    add.AddInfo(pos[t], v);
    del.AddInfo(pos[a], v);
    return ;
}

int main() {
	freopen("running.in", "r", stdin);
	freopen("running.out", "w", stdout);
    n = read(); q = read();
    for(int i = 1; i < n; i++) {
        int a = read(), b = read();
        AddEdge(a, b);
    }
    for(int i = 1; i <= n; i++) W[i] = read();
    for(int i = 1; i <= q; i++) {
        int s = read(), t = read();
        ps[i] = Player(s, t);
    }
    build(1);
    gett(1, 1);
    
    for(int i = 1; i <= n; i++) W[i] -= dep[i];
    add.clear(); del.clear(); memset(tot, 0, sizeof(tot));
    for(int i = 1; i <= q; i++) {
        ps[i].c = lca(ps[i].s, ps[i].t);
        process(i, ps[i].c, ps[i].t, dep[ps[i].s] - dep[ps[i].c] - dep[ps[i].c]);
    }
    for(int i = 1; i <= n; i++) {
        for(int e = add.fir[i]; e; e = add.aft[e]) {
            int v = add.val[e] + n;
            tot[v]++;
        }
        int u = pid[i];
        ans[u] += tot[W[u]+n];
        for(int e = del.fir[i]; e; e = del.aft[e]) {
            int v = del.val[e] + n;
            tot[v]--;
        }
    }
    
    for(int i = 1; i <= n; i++) W[i] += (dep[i] << 1);
    add.clear(); del.clear(); memset(tot, 0, sizeof(tot));
    for(int i = 1; i <= q; i++)
        process(i, ps[i].c, ps[i].s, dep[ps[i].s]);
    for(int i = 1; i <= n; i++) {
        for(int e = add.fir[i]; e; e = add.aft[e]) {
            int v = add.val[e];
            tot[v]++;
        }
        int u = pid[i];
        ans[u] += tot[W[u]];
        for(int e = del.fir[i]; e; e = del.aft[e]) {
            int v = del.val[e];
            tot[v]--;
        }
    }
    
    for(int i = 1; i <= q; i++)
        if(W[ps[i].c] == dep[ps[i].s]) ans[ps[i].c]--;
    
    for(int i = 1; i <= n; i++) printf("%d%c", ans[i], i < n ? ' ' : '
');
    
    return 0;
}

Day 1 T3 classroom

这题我考场上想到正解但是因为邻接矩阵连边时忘记取 min 就 sb 了。。。。。

设 f[0][i][j] 表示前 i 条请求使用了 j 条，最后一条没取的最小期望距离；f[1][i][j] 表示前 i 条请求使用了 j 条，最后一条取了的最小期望距离。然后因为每次走哪条边是独立的，转移时直接乘上概率累加上就好了。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;

int read() {
    int x = 0, f = 1; char c = getchar();
    while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); }
    while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); }
    return x * f;
}

#define maxn 2010
#define maxv 310
#define oo 1000000000
int n, m, v, e, c[maxn], d[maxn], D[maxn][maxn];
double p[maxn], f[2][maxn][maxn];

void up(double& a, double b) {
    a = min(a, b);
    return ;
}

int main() {
	freopen("classroom.in", "r", stdin);
	freopen("classroom.out", "w", stdout);
    n = read(); m = read(); v = read(); e = read();
    for(int i = 1; i <= n; i++) c[i] = read();
    for(int i = 1; i <= n; i++) d[i] = read();
    for(int i = 1; i <= n; i++) scanf("%lf", &p[i]);
    for(int i = 1; i <= v; i++) {
        D[i][i] = 0;
        for(int j = i + 1; j <= v; j++)
            D[i][j] = D[j][i] = oo;
    }
    for(int i = 1; i <= e; i++) {
        int a = read(), b = read(), c = read();
        D[a][b] = min(D[a][b], c);
        D[b][a] = min(D[b][a], c);
    }
    for(int k = 1; k <= v; k++)
        for(int i = 1; i <= v; i++)
            for(int j = 1; j <= v; j++)
                D[i][j] = min(D[i][j], D[i][k] + D[k][j]);
    
    for(int i = 0; i <= n; i++)
        for(int j = 0; j <= m; j++) f[0][i][j] = f[1][i][j] = 1e9;
    f[0][0][0] = 0.0;
    for(int i = 0; i <= n; i++)
        for(int j = 0; j <= min(i + 1, m); j++) {
            double P = p[i], np = p[i+1], p1 = 1.0 - P, np1 = 1.0 - np;
            up(f[0][i+1][j], f[0][i][j] + D[c[i]][c[i+1]]);
            up(f[1][i+1][j+1], f[0][i][j] + np * D[c[i]][d[i+1]] + np1 * D[c[i]][c[i+1]]);
            up(f[0][i+1][j], f[1][i][j] + P * D[d[i]][c[i+1]] + p1 * D[c[i]][c[i+1]]);
            up(f[1][i+1][j+1], f[1][i][j] + P * np * D[d[i]][d[i+1]] + P * np1 * D[d[i]][c[i+1]] + p1 * np * D[c[i]][d[i+1]] + p1 * np1 * D[c[i]][c[i+1]]);
        }
    
    double ans = 1e9;
    for(int i = 0; i <= m; i++) up(ans, min(f[0][n][i], f[1][n][i]));
    printf("%.2lf
", ans);
    
    return 0;
}

Day 2 T1 problem

用递推法求组合数，实时模 k。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;

int read() {
    int x = 0, f = 1; char c = getchar();
    while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); }
    while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); }
    return x * f;
}

#define maxn 2010
int C[2][maxn], f[maxn][maxn];

int main() {
	freopen("problem.in", "r", stdin);
	freopen("problem.out", "w", stdout);
    int size = 2000;
    bool cur = 0;
    int T = read(), k = read();
    for(int i = 0; i <= size; i++, cur ^= 1) {
        C[cur][0] = 1; C[cur][i] = 1;
        for(int j = 1; j < i; j++) C[cur][j] = (C[cur^1][j-1] + C[cur^1][j]) % k;
        for(int j = 0; j <= i; j++) {
            f[i][j] = (!C[cur][j]);
            int t = 0;
            if(j) f[i][j] += f[i][j-1], t++;
            if(j <= i - 1) f[i][j] += f[i-1][j], t++;
            if(t == 2 && i && j) f[i][j] -= f[i-1][j-1];
        }
    }
    while(T--) {
        int n = read(), m = read();
        printf("%d
", f[n][min(n,m)]);
    }
    
    return 0;
}

Day 2 T2 earthworm

受到 q = 0 即蚯蚓长度没有增加的数据启发，我们发现每次坎出的两条蚯蚓的长度一定是单调降的，于是可以 O(n) 做了。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;

int read() {
    int x = 0, f = 1; char c = getchar();
    while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); }
    while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); }
    return x * f;
}

#define maxn 100010
#define maxm 7100010
#define LL long long
int n, m, q, u, v, t, A[maxn], B[maxm], C[maxm], lb, rb, lc, rc, ans[maxm], cnt;

bool cmp(int a, int b) { return a > b; }

void process(int tmp, int i, int len) {
    int nb = (LL)tmp * u / v, nc = tmp - nb;
    B[++rb] = nb - len - q;
    C[++rc] = nc - len - q;
    if(i % t == 0) ans[++cnt] = tmp;
    return ;
}

int main() {
	freopen("earthworm.in", "r", stdin);
	freopen("earthworm.out", "w", stdout);
    n = read(); m = read(); q = read(); u = read(); v = read(); t = read();
    for(int i = 1; i <= n; i++) A[i] = read();
    sort(A + 1, A + n + 1, cmp);
//    for(int i = 1; i <= n; i++) printf("%d%c", A[i], i < n ? ' ' : '
');
    
    lb = 1; rb = 0; lc = 1; rc = 0;
    int pa = 1, len = 0;
    for(int i = 1; i <= m; i++, len += q) {
        int a, b, c;
        a = (pa <= n) ? A[pa] + len : -1;
        b = (lb <= rb) ? B[lb] + len : -1;
        c = (lc <= rc) ? C[lc] + len : -1;
        if(a >= b && a >= c) {
            pa++;
            process(a, i, len);
        }
        else if(b >= a && b >= c) {
            lb++;
            process(b, i, len);
        }
        else {
            lc++;
            process(c, i, len);
        }
    }
    for(int i = 1; i <= cnt; i++) printf("%d%c", ans[i], i < cnt ? ' ' : '
');
    if(!cnt) putchar('
');
    cnt = 0;
    for(int i = 1; i <= n + m; i++) {
        int a, b, c;
        a = (pa <= n) ? A[pa] + len : -1;
        b = (lb <= rb) ? B[lb] + len : -1;
        c = (lc <= rc) ? C[lc] + len : -1;
        if(a >= b && a >= c) {
            pa++;
            if(i % t == 0) ans[++cnt] = a;
        }
        else if(b >= a && b >= c) {
            lb++;
            if(i % t == 0) ans[++cnt] = b;
        }
        else {
            lc++;
            if(i % t == 0) ans[++cnt] = c;
        }
    }
    for(int i = 1; i <= cnt; i++) printf("%d%c", ans[i], i < cnt ? ' ' : '
');
    if(!cnt) putchar('
');
    
    return 0;
}

Day 2 T3 angrybirds

状压 dp，设 f[S] 表示干掉集合 S 的猪需要的最少抛物线条数，转移时找到第一个没有被干掉的猪，再枚举另一头猪，两点确定一条过 (0, 0) 的抛物线，然后转移到当前集合与抛物线经过猪的集合的并集。注意到每条抛物线经过猪的集合是可以预处理的。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <cmath>
using namespace std;

int read() {
    int x = 0, f = 1; char c = getchar();
    while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); }
    while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); }
    return x * f;
}

#define maxn 23
#define maxs 362154
const double eps = 1e-6;
struct Point {
    double x, y;
    Point() {}
    Point(double _, double __): x(_), y(__) {}
    bool operator < (const Point& t) const { return x != t.x ? x < t.x : y < t.y; }
} ps[maxn];
int f[maxs], ls[maxn][maxn];

bool on(double a, double b, Point p) {
    return fabs(a * p.x * p.x + b * p.x - p.y) <= eps;
}

void up(int& a, int b) {
    if(a < 0) a = b;
    else a = min(a, b);
    return ;
}

int main() {
	freopen("angrybirds.in", "r", stdin);
	freopen("angrybirds.out", "w", stdout);
    int T = read();
    while(T--) {
        int n = read(); read();
        for(int i = 0; i < n; i++) scanf("%lf%lf", &ps[i].x, &ps[i].y);
        sort(ps, ps + n);
        memset(f, -1, sizeof(f));
        memset(ls, 0, sizeof(ls));
        f[0] = 0;
        for(int i = 0; i < n; i++)
        	for(int j = 0; j < n; j++) if(i != j) {
                double x1 = ps[i].x, y1 = ps[i].y, x2 = ps[j].x, y2 = ps[j].y;
                double b = (x1 * x1 * y2 - x2 * x2 * y1) / (x1 * x1 * x2 - x2 * x2 * x1);
                double a = (y1 - b * x1) / (x1 * x1);
                if(a >= 0.0) continue;
                int S = 0;
                for(int k = 0; k < n; k++) if(((S >> k & 1) ^ 1) && on(a, b, ps[k]))
                    S |= (1 << k);
        		ls[i][j] = S;
        	}
        int all = (1 << n) - 1;
        for(int S = 0; S <= all; S++) if(f[S] >= 0)
            for(int j = 0; j < n; j++) if((S >> j & 1) ^ 1) {
                int tS = S | (1 << j);
                up(f[tS], f[S] + 1);
                for(int i = j + 1; i < n; i++) if((tS >> i & 1) ^ 1)
                    up(f[tS | ls[i][j]], f[S] + 1);
                break;
            }
        printf("%d
", f[all]);
    }
    
    return 0;
}

这次 NOIP 为什么都是第二题最难 TAT