USACO 2018 DEC

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大的最长上升子序列。
分为两部分来思考。

  1. 如何求最长上升子序列的个数?
    这是一个51nod上的题目,不要用传统的二分,贪心的思路。
    换成按值,动态规划,最后用线段树优化的思路。

  2. 如何找到字典序最大的最长上升子序列?
    对于每个数字,如果他能出现在最长上升子序列中,那么他的位置是唯一的。
    倒着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;
}

1 thought on “USACO 2018 DEC

Leave a Reply

Your email address will not be published. Required fields are marked *