Bronze

B1 / 843

模拟$100$次，似乎没发现简单的写法。

import sys
sys.stdin = open('mixmilk.in', 'r')
sys.stdout = open('mixmilk.out', 'w')
c = [0, 0, 0]
m = [0, 0, 0]
c[0], m[0] = map(int, raw_input().split())
c[1], m[1] = map(int, raw_input().split())
c[2], m[2] = map(int, raw_input().split())
for i in range(100):
    m[(i + 1) % 3] += m[i % 3]
    m[i % 3] = 0
    if m[(i + 1) % 3] > c[(i + 1) % 3]:
        m[i % 3] = m[(i + 1) % 3] - c[(i + 1) % 3]
        m[(i + 1) % 3] = c[(i + 1) % 3]
print m[0]
print m[1]
print m[2]

B2 / 844

每个牛相当于区间加一个数字。
注意到区间长度和操作次数都很少，暴力做，或者差分再前缀和都可以。

import sys
sys.stdin = open('blist.in', 'r')
sys.stdout = open('blist.out', 'w')
n = input()
a = [0 for i in range(1000)]
for i in range(n):
    s, t, b = map(int, raw_input().split())
    for j in range(s - 1, t):
        a[j] += b
print max(a)

B3 / 845

不需要考虑拿过去，再拿回来相同的桶的情况。
枚举两遍拿$0, 1, 2$个到对面，就可以了。
当然，拿两个过去的时候，不能拿相同的$2$个。

import sys
sys.stdin = open('backforth.in', 'r')
sys.stdout = open('backforth.out', 'w')
a = map(int, raw_input().split())
b = map(int, raw_input().split())
s = set([])
s.add(0)
for i in range(10):
    for j in range(10):
        s.add(a[i] - b[j])
for i in range(10):
    for j in range(10):
        for k in range(i):
            for l in range(j):
                s.add(a[i] + a[k] - b[j] - b[l])
print len(s)

Silver

S1 / 846

显然满足二分性质，二分一个时间$x$，每个车上的牛需要满足两个条件：
个数 <= $c$，最晚减去最早 <= $x$，计算出最小的车数，然后和$m$比较。

#include <bits/stdc++.h>
using namespace std;
int n, m, c;
int a[100020];
bool ok(int x) {
    int cnt = 0;
    for (int i = 0; i < n;) {
        int j = i;
        while (j < n && j - i < c) {
            if (a[j] - a[i] > x) {
                break;
            }
            j++;
        }
        cnt++;
        i = j;
    }
    return cnt <= m;
}
int main() {
    freopen("convention.in", "r", stdin);
    freopen("convention.out", "w", stdout);
    scanf("%d%d%d", &n, &m, &c);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    sort(a, a + n);
    int L = -1;
    int R = 1e9;
    while (L < R - 1) {
        int M = (L + R) / 2;
        if (ok(M)) {
            R = M;
        } else {
            L = M;
        }
    }
    printf("%d\n", R);
    return 0;
}

S2 / 847

优先队列（或set）贪心
第一次排序，按到达时间排。
然后一个while
如果有牛的到达时间小于等于当前时间，就加入进来。
特别的注意到加入到堆里之后，牛是按标号排的。
如果加了之后，集合还是空的，那么说明这段时间一个牛都没有，将时间设为下一头牛到达的时间即可，并且continue直接执行下一轮循环。
然后思考下一头开始的牛是谁，他应该是当前集合中标号最小的。
更新一下答案。
更新一下当前时间
把这头牛删掉，进入下一轮。

#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;
int n;
pair<pair<int, int>, int> a[100020];
int main() {
    freopen("convention2.in", "r", stdin);
    freopen("convention2.out", "w", stdout);
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d%d", &a[i].X.X, &a[i].Y);
        a[i].X.Y = i;
    }
    sort(a, a + n);
    int z = 0, i = 0, t = 0;
    set<pair<pair<int, int>, int> > s;
    while (true) {
        while (i < n && a[i].X.X <= t) {
            swap(a[i].X.X, a[i].X.Y);
            s.insert(a[i++]);
        }
        if (s.size() == 0) {
            if (i == n) {
                break;
            }
            t = a[i].X.X;
            continue;
        }
        z = max(z, t - s.begin()->X.Y);
        t += s.begin() -> Y;
        s.erase(s.begin());
    }
    printf("%d\n", z);
    return 0;
}

S3 / 848

通过搜索（BFS或DFS）找到连通的区域，然后消去，然后模拟下落。
基本就是 mayan游戏难度
实现细节：
1. 一般来说DFS比BFS好写，如果可以选的话，建议DFS。
2. 计数和染色部分分开写，如果写在一起，非常麻烦。
3. 下落的部分，有不需要额外数组的写法，建议学习。

#include <bits/stdc++.h>
using namespace std;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int n, k;
char s[120][12];
bool v[120][12];
bool in(int x, int y) {
    return 0 <= x && x < n && 0 <= y && y < 10;
}
int dfs(int x, int y, char c) {
    v[x][y] = true;
    int re = 1;
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (in(nx, ny) && s[nx][ny] == c && !v[nx][ny]) {
            re += dfs(nx, ny, c);
        }
    }
    return re;
}
void color(int x, int y, char c) {
    s[x][y] = '0';
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (in(nx, ny) && s[nx][ny] == c) {
            color(nx, ny, c);
        }
    }
}
bool gao() {
    bool flag = false;
    memset(v, 0, sizeof v);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 10; j++) {
            if (!v[i][j] && s[i][j] != '0') {
                int sz = dfs(i, j, s[i][j]);
                if (sz >= k) {
                    flag = true;
                    color(i, j, s[i][j]);
                }
            }
        }
    }
    return flag;
}
void fall() {
    for (int j = 0; j < 10; j++) {
        int c = 0;
        for (int i = 0; i < n; i++) {
            if (s[i][j] != '0') {
                s[c++][j] = s[i][j];
            }
        }
        while (c < n) {
            s[c++][j] = '0';
        }
    }
}
int main() {
    freopen("mooyomooyo.in", "r", stdin);
    freopen("mooyomooyo.out", "w", stdout);
    scanf("%d%d", &n, &k);
    for (int i = n - 1; i >= 0; i--) {
        scanf("%s", s[i]);
    }
    while (gao()) {
        fall();
    }
    for (int i = n - 1; i >= 0; i--) {
        printf("%s\n", s[i]);
    }
    return 0;
}

Gold

G1 / 849

求每个点到终点的距离，显然是从终点反向dijkstra。
第二次把所有haybale的距离初始化为第一次的距离减去收益。
这个值可能是负数，再做一次dijkstra。（边和第一次是一样的）
第二次dijkstra的时候，相当于有多个起点。
如果第一次距离<第二次距离，那么不可能，否则可能。

输入非常给面子，haybale的所有信息都不需要存储，用后即弃。
dijk中，刚开始把所有点入队。

#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int> > a[50020];
int n, m, k;
int d1[50020];
int d2[50020];
set<pair<int, int> > s;
void dijk(int *d) {
    for (int i = 1; i <= n; i++) {
        s.insert(make_pair(d[i], i));
    }
    while (s.size()) {
        int u = s.begin() -> second;
        s.erase(s.begin());
        for (int i = 0; i < a[u].size(); i++) {
            if (d[a[u][i].first] > d[u] + a[u][i].second) {
                s.erase(make_pair(d[a[u][i].first], a[u][i].first));
                d[a[u][i].first] = d[u] + a[u][i].second;
                s.insert(make_pair(d[a[u][i].first], a[u][i].first));
            }
        }
    }
}
int main() {
    freopen("dining.in", "r", stdin);
    freopen("dining.out", "w", stdout);
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 0; i < m; i++) {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        a[x].push_back(make_pair(y, z));
        a[y].push_back(make_pair(x, z));
    }
    memset(d1, 0x3f, sizeof d1);
    d1[n] = 0;
    dijk(d1);
    memset(d2, 0x3f, sizeof d2);
    for (int i = 0; i < k; i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        d2[x] = d1[x] - y;
    }
    dijk(d2);
    for (int i = 1; i < n; i++) {
        printf("%d\n", d1[i] >= d2[i]);
    }
}

G2 / 850

注意到每个牛只有$5$个爱好的，枚举$32$个子集，容斥计数。
然后考虑每个集合出现多少次

如果一个大小为偶数（包括$0$）的集合出现$c$次，那么贡献是$c * (c – 1) / 2$
如果一个大小为奇数的集合出现$c$次，那么贡献是$-c * (c – 1) / 2$

如果交集非空，那么交集的子集中，大小为奇数和大小为偶数的个数相等，正负抵消。
如果交集为空，那么交集的子集中，只有一个空集，贡献恰好是$1$。

下面这份代码实现的不是很好，key的部分基本是乱写的。

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef pair<ull, ull> key;
map<key, int> g[2];
int n, a[5];
long long z;
int main() {
    freopen("cowpatibility.in", "r", stdin);
    freopen("cowpatibility.out", "w", stdout);
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 5; j++) {
            scanf("%d", &a[j]);
        }
        sort(a, a + 5);
        for (int j = 0; j < 32; j++) {
            key r;
            int c = 0;
            for (int k = 0; k < 5; k++) {
                if (j >> k & 1) {
                    r.first = r.first * 233412337 + a[k];
                    r.second = r.second * 318927319 ^ a[k];
                    c++;
                }
            }
            g[c % 2][r]++;
        }
    }
    for (pair<key, int> i: g[0]) {
        z += (long long)i.second * (i.second - 1) / 2;
    }
    for (pair<key, int> i: g[1]) {
        z -= (long long)i.second * (i.second - 1) / 2;
    }
    printf("%lld\n", z);
    return 0;
}

G3 / 851

$O(NK)$的DP。

f[i]表示前$i$个数字的最优解。
f[i] = f[i - j] + j * max(a[j + 1], a[j + 2], ..., a[i]); (1 <= j <= k)
然后$i – j \geq 0$即可。

import java.util.Scanner;
import java.io.File;
import java.io.IOException;
import java.io.PrintStream;

public class Main {
    static public void main(String[] args) throws IOException {
        Scanner in = new Scanner(new File("teamwork.in"));
        PrintStream out = new PrintStream(new File("teamwork.out"));
        int n = in.nextInt();
        int k = in.nextInt();
        int []a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = in.nextInt();
        }
        int []f = new int[n + 1];
        for (int i = 0; i < n; i++) {
            int mx = a[i];
            for (int j = 1; j <= k; j++) {
                f[i + j] = Math.max(f[i + j], f[i] + j * mx);
                if (i + j < n) {
                    mx = Math.max(mx, a[i + j]);
                } else {
                    break;
                }
            }
        }
        out.println(f[n]);
    }
}

Platinum

P1 / 852

凸包。
如果初始在$i (L \leq i \leq R)$，并且$a[L]$和$a[R]$均大于$a[i]$。
那么必然可以以$a[L]$或者$a[R]$结束。
如果从$i$出发，每次向左或向右走，走到$L$或$R$停止，那么
最终停在$R$的概率为$(i – L) / (R – L)$。
最终停在$L$的概率为$(R – i) / (R – L)$。
换句话说，设$p_i$是停在$R$的概率，显然有$p_L = 0, p_R = 1$。
中间的$p_i$是一个等差数列。

所以说，从$i$出发，每次向左或向右走，走到$L$或$R$停止，这个策略的收益是$(a[L] * (R – i) + a[R] * (i – L)) / (R – L)$
换句话说，如果点$(i, a_i)$在从$(L, a[L])$到$(R, a[R])$的下面，那么他就可以删去了，剩下的点恰好是一个凸包。

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
int n;
double a[100020];
int s[100020], ss;
long long xm(long long x1, long long y1, long long x2, long long y2) {
    return x1 * y2 - x2 * y1;
}
int main() {
    freopen("balance.in", "r", stdin);
    freopen("balance.out", "w", stdout);
    scanf("%d", &n);
    s[ss++] = 0;
    for (int i = 1; i <= n + 1; i++) {
        if (i <= n) {
            scanf("%lf", &a[i]);
        }
        while (ss >= 2 && xm(s[ss - 1] - s[ss - 2], a[s[ss - 1]] - a[s[ss - 2]],
            i - s[ss - 2], a[i] - a[s[ss - 2]]) > 0) {
            ss--;
        }
        s[ss++] = i;
    }
    int t = 0;
    for (int i = 1; i <= n; i++) {
        while (i > s[t]) {
            t++;
        }
        ull res = (ull)a[s[t]] * (i - s[t - 1]) + (ull)a[s[t - 1]] * (s[t] - i);
        res *= 100000;
        res /= s[t] - s[t - 1];
        printf("%llu\n", res);
    }
    return 0;
}

P2 / 853

显然剩下的部分相对顺序不会改变。
也就是剩下的部分必须是一个最长上升子序列。
要求操作的字典序第$k$小，也就是剩下的部分字典序第$k$大。
求字典序第k大的最长上升子序列。
分为两部分来思考。

如何求最长上升子序列的个数？
这是一个51nod上的题目，不要用传统的二分，贪心的思路。
换成按值，动态规划，最后用线段树优化的思路。
如何找到字典序最大的最长上升子序列？
对于每个数字，如果他能出现在最长上升子序列中，那么他的位置是唯一的。
倒着DP，从第一位向后一位一位的确定即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
ll k, inf = 4e18;
int a[262147];
vector<int> b[262147];
pair<int, ll> t[262147];
int v[262147];
pair<int, ll> add(pair<int, ll> a, pair<int, ll> b) {
    if (a.first > b.first) {
        return a;
    } else if (a.first < b.first) {
        return b;
    } else {
        return make_pair(a.first, min(a.second + b.second, inf));
    }
}

pair<int, ll> query(int l, int r, int x, int L, int R) {
    if (r < L || R < l) {
        return make_pair(-1, 0);
    }
    if (L <= l && r <= R) {
        return t[x];
    }
    int m = (l + r) / 2;
    return add(query(l, m, x * 2, L, R), query(m + 1, r, x * 2 + 1, L, R));
}

void change(int l, int r, int x, int p, pair<int, ll> w) {
    if (l == r) {
        t[x] = w;
        return;
    }
    int m = (l + r) / 2;
    if (p <= m) {
        change(l, m, x * 2, p, w);
    } else {
        change(m + 1, r, x * 2 + 1, p, w);
    }
    t[x] = add(t[x * 2], t[x * 2 + 1]);
}

int main() {
    freopen("itout.in", "r", stdin);
    freopen("itout.out", "w", stdout);
    scanf("%d%lld", &n, &k);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    change(1, n + 1, 1, n + 1, make_pair(0, 1));
    for (int i = n; i > 0; i--) {
        pair<int, ll> res = query(1, n + 1, 1, a[i], n + 1);
        res.first++;
        change(1, n + 1, 1, a[i], res);
    }
    for (int i = 1; i <= n; i++) {
        pair<int, ll> res = query(1, n + 1, 1, i, i);
        b[res.first].push_back(i);
    }
    pair<int, ll> ans = query(1, n + 1, 1, 1, n + 1);
    int st = 1;
    int last = 0;
    assert(k <= ans.second);
    for (int i = ans.first; i > 0; i--) {
        for (int jj = b[i].size() - 1; jj >= 0; jj--) {
            int j = b[i][jj];
//          if (j < last) {
//              continue;
//          }
            pair<int, ll> res = query(1, n + 1, 1, j, j);
//          printf("pre %d %d %d %lld\n", i, j, res.first, res.second);
            if (k > res.second) {
                k -= res.second;
            } else {
                v[j] = 1;
                last = j;
//              printf("choose %d\n", j);
                for (; a[st] != j; st++) {
                    change(1, n + 1, 1, a[st], make_pair(0, 0));
                }
                break;
            }
        }
    }
    printf("%d\n", n - ans.first);
    for (int i = 1; i <= n; i++) {
        if (!v[i]) {
            printf("%d\n", i);
        }
    }
    return 0;
}

P3 / 854

//（保证有解，虽然题目似乎没说）
//（无耻的USACO赛后改数据了，历史必将记下这一刻！）
大概就是LCA，如果x要先于y，那么以y为根，x整个子树（包括x）都不可能是解。
那么一个简单的写法就是，找到从x到y路径上的第一个点f。
然后以$f$为根，标记子树$x$中所有的点。

因为每个点至多标记一次，所以复杂度是$O(n)$的。
核心问题是从x到y路径上的第一个点f，这个就是LCA。

#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<int> a[100020];
vector<int> b[100020];
int deg[100020];
int in[100020];
int f[100020][18];
int d[100020];
int L[100020];
int R[100020];
int s[100020], ss;
int v[100020];
int c[100020];
void dfs(int x, int y) {
    L[x] = ss;
    s[ss++] = x;
    f[x][0] = y;
    d[x] = d[y] + 1;
    for (int i = 1; i < 18; i++) {
        f[x][i] = f[f[x][i - 1]][i - 1];
    }
    for (int i: a[x]) {
        if (i != y) {
            dfs(i, x);
        }
    }
    R[x] = ss;
}

int lca(int x, int y) {
    if (d[x] < d[y]) {
        swap(x, y);
    }
    int dd = d[x] - d[y];
    for (int i = 0; i < 18; i++) {
        if (dd >> i & 1) {
            x = f[x][i];
        }
    }
    if (x == y) {
        return x;
    }
    for (int i = 17; i >= 0; i--) {
        if (f[x][i] != f[y][i]) {
            x = f[x][i];
            y = f[y][i];
        }
    }
    return f[x][0];
}

bool ok() {
    queue<int> q;
    for (int i = 1; i <= n; i++) {
        if (deg[i] <= 1 && in[i] == 0 && v[i] == 0) {
            q.push(i);
            v[i] = 1;
        }
    }
    int cnt = 0;
    while (q.size()) {
        int u = q.front();
        q.pop();
        cnt++;
        for (int i: a[u]) {
            deg[i]--;
            if (deg[i] <= 1 && in[i] == 0 && v[i] == 0) {
                q.push(i);
                v[i] = 1;
            }
        }
        for (int i: b[u]) {
            in[i]--;
            if (deg[i] <= 1 && in[i] == 0 && v[i] == 0) {
                q.push(i);
                v[i] = 1;
            }
        }
    }
    return cnt == n;
}
int main() {
    freopen("gathering.in", "r", stdin);
    freopen("gathering.out", "w", stdout);
    scanf("%d%d", &n, &m);
    for (int i = 1; i < n; i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        deg[x]++;
        deg[y]++;
        a[x].push_back(y);
        a[y].push_back(x);
    }
    dfs(1, 0);
    for (int i = 0; i < m; i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        b[x].push_back(y);
        in[y]++;
        int l = lca(x, y);
        if (l == x) {
            c[0]++;
            c[n]--;
            if (l == y) {
                continue;
            }
            for (int i = 17; i >= 0; i--) {
                if (d[f[y][i]] > d[x]) {
                    y = f[y][i];
                }
            }
            c[L[y]]--;
            c[R[y]]++;
        } else {
            c[L[x]]++;
            c[R[x]]--;
        }
    }

    if (!ok()) {
        for (int i = 1; i <= n; i++) {
            printf("0\n");
        }
        return 0;
    }

    for (int i = 0; i < n; i++) {
        c[i + 1] += c[i];
    }
    for (int i = 1; i <= n; i++) {
        printf("%d\n", c[L[i]] == 0);
    }
    return 0;
}

2018-12-19 wwwwodddd Uncategorized USACO

USACO 2018 DEC