USACO 2020 JAN

Bronze

B1

import sys
sys.stdin = open('word.in', 'r')
sys.stdout = open('word.out', 'w')
n, m = map(int, input().split())
l = 0
for s in input().split():
    # print(l, s, len(s))
    if l + len(s) > m:
        print()
        l = 0
    if l > 0:
        print(' ', end='')
    print(s, end='')
    l += len(s)
print()

B2

import sys
sys.stdin = open('photo.in', 'r')
sys.stdout = open('photo.out', 'w')
n = int(input())
a = list(map(int, input().split()))
def F(s):
    b = [s]
    for i in range(len(a)):
        b.append(a[i] - b[i])
    if len(set(b)) == n and max(b) == n and min(b) == 1:
        return ' '.join(map(str, b))
    return None
for i in range(1, n):
    if F(i):
        print(F(i))

B3

import sys
import math
sys.stdin = open('race.in', 'r')
sys.stdout = open('race.out', 'w')
def F(t, x):
    if t <= x:
        return t * (t + 1) // 2
    t += x - 1
    t1 = t // 2
    t2 = t - t1
    return t1 * (t1 + 1) // 2 + t2 * (t2 + 1) // 2 - x * (x - 1) // 2
k, n = map(int, input().split())
for i in range(n):
    x = int(input())
    L = 0
    R = k
    while L < R - 1:
        M = (L + R) // 2
        if F(M, x) >= k:
            R = M
        else:
            L = M
    print(R)

Silver

S1

#include <bits/stdc++.h>
using namespace std;
int n, k;
int a[1020];
int b[1020];
int main()
{
    freopen("berries.in", "r", stdin);
    freopen("berries.out", "w", stdout);
    cin >> n >> k;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    sort(a, a + n);
    int ans = 0;
    for (int i = 1; i <= a[n - 1]; i++)
    {
        int cnt = 0;
        for (int j = 0; j < n; j++)
        {
            b[j] = a[j] % i;
            cnt += a[j] / i;
        }
        sort(b, b + n);
        int sum = 0;
        if (cnt >= k)
        {
            sum = i * k / 2;
        }
        else if (cnt >= k / 2)
        {
            sum = (cnt - k / 2) * i;
            if (n - (k - cnt) < 0)
            {
                continue;
            }
            for (int j = n - (k - cnt); j < n; j++)
            {
                sum += b[j];
            }
        }
        else
        {
            int kk = k / 2 - cnt;
            if (n - kk - k / 2 < 0)
            {
                continue;
            }
            for (int j = n - kk - k / 2; j < n - kk; j++)
            {
                sum += b[j];
            }
        }
        ans = max(ans, sum);
    }
    cout << ans << endl;
    return 0;
}

S2

import sys
sys.stdin = open('loan.in', 'r')
sys.stdout = open('loan.out', 'w')
n, k, m = map(int, input().split())
L = 1
R = n + 1
def ok(n, x):
    s = 0
    kk = 0
    while kk < k:
        d = (n - s) // x
        if d <= m:
            return (n - s + m - 1) // m + kk <= k
        t = (n - s - d * x) // d + 1
        t = min(t, k - kk)
        kk += t
        s += t * d
    return s == n
while L < R - 1:
    M = (L + R) // 2
    if ok(n, M):
        L = M
    else:
        R = M
print(L)

S3

#include <bits/stdc++.h>
using namespace std;
int n, m;
int p[100020];
int x[100020];
int y[100020];
int z[100020];
int f[100020];
int F(int x)
{
    return f[x] != x ? f[x] = F(f[x]) : x;
}
void U(int x, int y)
{
    x = F(x);
    y = F(y);
    f[x] = y;
}
bool ok(int M)
{
    for (int i = 1; i <= n; i++)
    {
        f[i] = i;
    }
    for (int i = 0; i < m; i++)
    {
        if (z[i] >= M)
        {
            U(x[i], y[i]);
        }
    }
    for (int i = 1; i <= n; i++)
    {
        if (F(i) != F(p[i]))
        {
            return false;
        }
    }
    return true;
}
int main()
{
    freopen("wormsort.in", "r", stdin);
    freopen("wormsort.out", "w", stdout);
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &p[i]);
    }
    for (int i = 0; i < m; i++)
    {
        scanf("%d%d%d", &x[i], &y[i], &z[i]);
    }
    int L = 0;
    int R = 1000000001;
    while (L < R - 1)
    {
        int M = (L + R) / 2;
        if (ok(M))
        {
            L = M;
        }
        else
        {
            R = M;
        }
    }
    if (L == 1000000000)
    {
        L = -1;
    }
    printf("%d\n", L);
    return 0;
}

Gold

G1

#include <bits/stdc++.h>
using namespace std;
int n, m, c;
int w[1020];
int d[1020][1020];
vector<int> a[1020];
priority_queue<pair<int, int> > q[1020];
int main()
{
    freopen("time.in", "r", stdin);
    freopen("time.out", "w", stdout);
    cin >> n >> m >> c;
    int l = 0;
    for (int i = 1; i <= n; i++)
    {
        cin >> w[i];
        l = max(l, w[i]);
    }
    for (int i = 0; i < m; i++)
    {
        int x, y, z;
        cin >> x >> y;
        a[x].push_back(y);
    }
    q[0].push(make_pair(0, 1));
    for (int x = 0; x < 1000; x++)
    {
        while (q[x].size() > 0)
        {
            int z = q[x].top().first;
            int y = q[x].top().second;
            q[x].pop();
            if (z != d[x][y])
            {
                continue;
            }
            for (int i : a[y])
            {
                if (d[x + 1][i] < d[x][y] + w[i])
                {
                    d[x + 1][i] = d[x][y] + w[i];
                    q[x + 1].push(make_pair(d[x + 1][i], i));
                }
            }
        }
    }
    int ans = 0;
    for (int i = 0; i < 1001; i++)
    {
        ans = max(ans, d[i][1] - c * i * i);
    }
    cout << ans << endl;
    return 0;
}

G2

#include <bits/stdc++.h>
using namespace std;
int n, q;
int v[3000020];
int a[5020];
long long z[5020][5020];
int main()
{
    freopen("threesum.in", "r", stdin);
    freopen("threesum.out", "w", stdout);
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= i; j++)
        {
            v[a[j] + 1000000] = 0;
        }
        for (int j = i - 1; j > 0; j--)
        {
            z[j][i] = z[j + 1][i] + z[j][i - 1] - z[j + 1][i - 1];
            if (1000000 - a[i] - a[j] >= 0)
            {
                z[j][i] += v[1000000 - a[i] - a[j]];
            }
            v[1000000 + a[j]]++;
        }
    }
    for (int i = 0; i < q; i++)
    {
        int l, r;
        cin >> l >> r;
        cout << z[l][r] << endl;
    }
    return 0;
}

G3

注意选择的2个矩形不能有任何重叠的部分。
这样预处理出来前后几行的结果,前后几列的结果。枚举分割线即可。

#include <bits/stdc++.h>
using namespace std;
pair<pair<int, int>, int> a[200020];
int m, n;
int l[200020], lc;
long long f[200020];
long long c[200020];
long long G(int x)
{
    long long re = 0;
    for (int i = x; i > 0; i -= i & -i)
    {
        re = min(re, c[i]);
    }
    return re;
}
void R(int x, long long y)
{
    for (int i = x; i <= lc; i += i & -i)
    {
        c[i] = min(c[i], y);
    }
}
int Q(int y)
{
    return lower_bound(l, l + lc, y) - l + 1;
}
int main()
{
    freopen("boards.in", "r", stdin);
    freopen("boards.out", "w", stdout);
    scanf("%d%d", &m, &n);
    long long ans = 0;
    for (int i = 0; i < n; i++)
    {
        scanf("%d%d", &a[i].first.first, &a[i].first.second);
        a[i].second = i + 1;
        l[lc++] = a[i].first.second;
        scanf("%d%d", &a[i + n].first.first, &a[i + n].first.second);
        a[i + n].second = -i - 1;
        l[lc++] = a[i + n].first.second;
    }
    sort(a, a + 2 * n);
    sort(l, l + lc);
    lc = unique(l, l + lc) - l;
    for (int i = 0; i < 2 * n; i++)
    {
        if (a[i].second > 0)
        {
            f[a[i].second] = G(Q(a[i].first.second));
            f[a[i].second] += a[i].first.first + a[i].first.second;
        }
        else
        {
            f[-a[i].second] -= a[i].first.first + a[i].first.second;
            R(Q(a[i].first.second), f[-a[i].second]);
            ans = min(ans, f[-a[i].second]);
        }
    }
    printf("%lld\n", ans + 2 * m);
    return 0;
}

Platinum

P1

#include <bits/stdc++.h>
using namespace std;
int n, m;
char s[1020][1020];
vector<int> a[1000020];
int cnt;
const int mod = 1000000007;
int f[1000020];
int c[1000020];
int v[1000020];
int F(int x)
{
    return f[x] != x ? f[x] = F(f[x]) : x;
}
void U(int x, int y)
{
    x = F(x);
    y = F(y);
    if (x > y)
    {
        f[x] = y;
    }
    else
    {
        f[y] = x; 
    }
}
int G(int x)
{
    int re = 1;
    for (int i: a[x])
    {
        re = (long long)re * G(i) % mod;
    }
    return (re + 1) % mod;
}
int main()
{
    freopen("cave.in", "r", stdin);
    freopen("cave.out", "w", stdout);
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++)
    {
        scanf("%s", s[i]);
    }
    for (int i = 0; i < n * m; i++)
    {
        f[i] = i;
    }
    for (int i = n - 1; i >= 0; i--)
    {
        for (int j = 0; j < m; j++)
        {
            if (s[i][j] == '.' && s[i + 1][j] == '.')
            {
                U(i * m + j, (i + 1) * m + j);
            }
        }
        for (int j = 1; j < m; j++)
        {
            if (s[i][j - 1] == '.' && s[i][j] == '.')
            {
                U(i * m + j - 1, i * m + j);
            }
        }
        for (int j = 0; j < m; j++)
        {
            if (s[i][j] == '.')
            {
                if (F(i * m + j) == i * m + j)
                {
                    c[i * m + j] = ++cnt;
                }
                else
                {
                    c[i * m + j] = c[F(i * m + j)];
                }
            }
        }
        for (int j = 0; j < m; j++)
        {
            if (s[i][j] == '.' && s[i + 1][j] == '.')
            {
                a[c[i * m + j]].push_back(c[(i + 1) * m + j]);
                v[c[(i + 1) * m + j]] = 1;
            }
        }
    }
    for (int i = 1; i <= cnt; i++)
    {
        sort(a[i].begin(), a[i].end());
        a[i].resize(unique(a[i].begin(), a[i].end()) - a[i].begin());
    }
    int ans = 1;
    for (int i = 1; i <= cnt; i++)
    {
        if (v[i] == 0)
        {
            ans = (long long)ans * G(i) % mod;
        }
    }
    printf("%d\n", ans);
    return 0;
}

P2

#include <bits/stdc++.h>
using namespace std;
int n, m;
const int mod = 1000000007;
int p[50020][20][20], q[50020][20][20];
int f[20][20][20];
int g[20][20][20];
void amul(int a[20][20], int b[20][20], int c[20][20])
{
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < m; j++)
        {
            c[i][j] = 0;
        }
    }
    for (int i = 0; i < m; i++)
    {
        for (int k = 0; k < m; k++)
        {
            if (a[i][k] == 0)
            {
                continue;
            }
            for (int j = 0; j < m; j++)
            {
                c[i][j] = (c[i][j] + (long long)a[i][k] * b[k][j]) % mod;
            }
        }
    }
}
void bmul(int a[20][20], int b[20][20], int c[20][20])
{
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < m; j++)
        {
            c[i][j] = 0;
        }
    }
    for (int j = 0; j < m; j++)
    {
        for (int k = 0; k < m; k++)
        {
            if (b[k][j] == 0)
            {
                continue;
            }
            for (int i = 0; i < m; i++)
            {
                c[i][j] = (c[i][j] + (long long)a[i][k] * b[k][j]) % mod;
            }
        }
    }
}
int a[200020];
int main()
{
    freopen("nondec.in", "r", stdin);
    freopen("nondec.out", "w", stdout);
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < m; j++)
        {
            f[i][j][j] = 1;
            g[i][j][j] = 1;
        }
        for (int j = 0; j <= i; j++)
        {
            f[i][j][i] += 1;
            g[i][j][i] = (g[i][j][i] + (mod - 1) / 2) % mod;
        }
    }
    for (int i = 0; i < m; i++)
    {
        p[0][i][i] = 1;
        q[0][i][i] = 1;
    }
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        a[i]--;
        bmul(p[i - 1], f[a[i]] , p[i]);
        amul(g[a[i]] , q[i - 1], q[i]);
    }
    int t, l, r;
    scanf("%d", &t);
    for (int i = 0; i < t; i++)
    {
        scanf("%d%d", &l, &r);
        l--;
        int ans = 0;
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < m; j++)
            {
                ans = (ans + (long long)q[l][0][i] * p[r][i][j]) % mod;
            }
        }
        printf("%d\n", ans);
    }
    // fprintf(stderr, "cnt=%d\n", cnt);
    return 0;
}

P3

#include <bits/stdc++.h>
using namespace std;
int n;
pair<pair<int, int>, pair<int, int> > a[200020];
int z[200020];
int y[200020];
int p[200020];
pair<int, int> s[200020];
int ss;
bool judge(pair<int, int> a, pair<int, int> b, pair<int, int> c)
{
    // cout << "judge" << endl;
    // cout << a.first << ' ' << a.second << endl;
    // cout << b.first << ' ' << b.second << endl;
    // cout << c.first << ' ' << c.second << endl;
    // cout << "return " << ((long long)(b.first - a.first) * (a.second - c.second) <= (long long)(c.first - a.first) * (a.second - b.second)) << endl;
    return (long long)(b.first - a.first) * (a.second - c.second) <= (long long)(c.first - a.first) * (a.second - b.second);
}
int gcd(int x, int y)
{
    return y ? gcd(y, x % y) : x;
}
int main()
{
    freopen("falling.in", "r", stdin);
    freopen("falling.out", "w", stdout);
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &a[i].first.first);
        a[i].first.second = -i - 1;
    }
    for (int i = 0; i < n; i++)
    {
        a[i].second.first = i;
        scanf("%d", &a[i].second.second);
        a[i].second.second--;
    }
    sort(a, a + n);
    for (int i = 0; i < n; i++)
    {
        p[a[i].second.first] = i;
        y[a[i].second.first] = 1;
    }
    ss = 0;
    for (int i = 0; i < n; i++)
    {
        while ((ss >= 1 && s[ss - 1].second < a[i].first.second) || (ss >= 2 && judge(s[ss - 2], s[ss - 1], a[i].first)))
        {
            ss--;
        }
        s[ss++] = a[i].first;
        if (p[a[i].second.second] > i)
        {
            int L = 0;
            int R = ss;
            pair<int, int> u = a[p[a[i].second.second]].first;
            while (L < R - 1)
            {
                int M = (L + R) / 2;
                // cout << "binary search before " << L << ' ' << R << endl;
                if ((ss >= 1 && s[M].second < u.second) || (M >= 1 && judge(s[M - 1], s[M], u)))
                {
                    R = M;
                }
                else
                {
                    L = M;
                }
                // cout << "binary search after " << L << ' ' << R << endl;
            }
            // cout << "query "  << L << endl;
            if (s[L].second < u.second)
            {
                z[a[i].second.first] = -1;
            }
            else
            {
                z[a[i].second.first] = (u.first - s[L].first);
                y[a[i].second.first] = (s[L].second - u.second);
            }
        }
        // for (int i = 0; i < ss; i++)
        // {
        //  cout << s[i].first << ' ' << s[i].second << endl;
        // }
        // cout << endl;
    }
    ss = 0;
    for (int i = n - 1; i >= 0; i--)
    {
        a[i].first.first = -a[i].first.first;
        a[i].first.second = -a[i].first.second;
    }
    for (int i = n - 1; i >= 0; i--)
    {
        while ((ss >= 1 && s[ss - 1].second < a[i].first.second) || (ss >= 2 && judge(s[ss - 2], s[ss - 1], a[i].first)))
        {
            ss--;
        }
        s[ss++] = a[i].first;
        if (p[a[i].second.second] < i)
        {
            int L = 0;
            int R = ss;
            pair<int, int> u = a[p[a[i].second.second]].first;
            while (L < R - 1)
            {
                int M = (L + R) / 2;
                if ((ss >= 1 && s[M].second < u.second) || (M >= 1 && judge(s[M - 1], s[M], u)))
                {
                    R = M;
                }
                else
                {
                    L = M;
                }
            }
            if (s[L].second < u.second)
            {
                z[a[i].second.first] = -1;
            }
            else
            {
                z[a[i].second.first] = (u.first - s[L].first);
                y[a[i].second.first] = (s[L].second - u.second);
            }
        }
    }
    for (int i = 0; i < n; i++)
    {
        if (z[i] == -1)
        {
            printf("%d\n", z[i]);
        }
        else
        {
            int g = gcd(z[i], y[i]);
            z[i] /= g;
            y[i] /= g;
            printf("%d/%d\n", z[i], y[i]);
        }
    }
    return 0;
}

Leave a Reply

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