NOIP2016题目整合

2023-08-11 12:22:46

今天终于拿到官方数据，兴致勃勃地全 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\n", 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 ? ' ' : '\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\n", 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\n", 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 ? ' ' : '\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 ? ' ' : '\n');

    if(!cnt) putchar('\n');

    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 ? ' ' : '\n');

    if(!cnt) putchar('\n');

    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\n", f[all]);

    }

    return 0;

}

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

码农公寓

相关文章