今天终于拿到官方数据，兴致勃勃地全 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”的特殊点的启发，我们发现可以将每条链 [Si, Ti] 分成 [Si, Ci] 和 [Ci, Ti] 两条，然后对于一个全部可观测到的链 [Ci, Ti] 将所有 Wi 减去深度是一个定值，对于 [Si, Ci] 的部分所有 Wi 加上深度是一个定值。于是树链剖分再打打标记统计就好了。

#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

最新文章

  1. 【目录】linux
  2. 【Android】做一款类似我要当学霸里的学习监督的APP
  3. canvas 实现 柱状图
  4. ssh 内在溢出
  5. win64安装及配置apache+php+mysql
  6. linux下静态链接库的用法
  7. frameset框架样式 加边框
  8. Java集合：HashMap源码剖析
  9. python之使用单元测试框架unittest执行自动化测试
  10. python编写接口初识一
  11. Annotation(注解)介绍
  12. js调用后台方法
  13. nginx高级用法汇总
  14. JAVA二分搜索树
  15. java 标准输入输出System.in与System.out
  16. ubuntu14.04安装jupyter notebook
  17. Azure虚机磁盘容量警报（邮件提醒）
  18. iOS UI基础-1.0加法计算器
  19. bzoj2014
  20. mybatis之insert语句报错Cause: java.sql.SQLException: sql injection violation, syntax error: ERROR. token : WHERE,

热门文章

  1. 自然语言20_The corpora with NLTK
  2. NLTK中文语料库sinica_treebank
  3. js字符串RTrim方法（right trim）
  4. Java 创建文件夹和文件
  5. Java多线程——线程范围内共享变量
  6. Set接口
  7. Linux学习笔记（二）2015.4.14
  8. 关于软件工程个人作业 Word frequency program 的总结
  9. Entity Framework - Using Transactions or SaveChanges(false) and AcceptAllChanges()?
  10. springmvc请求参数获取的几种方法