Overall

在比赛刚开始时，所有提交都是文件错误，耽误了一些时间。

Bronze

B1

#include <bits/stdc++.h>
using namespace std;
int x[120], y[120];
int n, ans;
int main()
{
    freopen("triangles.in", "r", stdin);
    freopen("triangles.out", "w", stdout);
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> x[i] >> y[i];
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (x[i] == x[j])
            {
                for (int k = 0; k < n; k++)
                {
                    if (y[i] == y[k])
                    {
                        ans = max(ans, abs((y[i] - y[j]) * (x[i] - x[k])));
                    }
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}

B2

#include <bits/stdc++.h>
using namespace std;
int n, z, l;
string a, b;
int main()
{
    freopen("breedflip.in", "r", stdin);
    freopen("breedflip.out", "w", stdout);
    cin >> n >> a >> b;
    for (int i = 0; i < n; i++)
    {
        if (a[i] == b[i])
        {
            l = 0;
        }
        else
        {
            if (l == 0)
            {
                z++;
            }
            l = 1;
        }
    }
    cout << z << endl;
    return 0;
}

B3

#include <bits/stdc++.h>
using namespace std;
int n, m, a1, b1, a2, b2;
int a[120];
bool ok()
{
    for (int i = 1; i <= n; i++)
    {
        if (a[i] != i)
        {
            return false;
        }
    }
    return true;
}
int main()
{
    freopen("swap.in", "r", stdin);
    FILE *fout = fopen("swap.out", "w");
    cin >> n >> m >> a1 >> b1 >> a2 >> b2;
    for (int i = 1; i <= n; i++)
    {
        a[i] = i;
    }
    for (int i = 1; i <= m; i++)
    {
        reverse(a + a1, a + b1 + 1);
        reverse(a + a2, a + b2 + 1);
        if (ok())
        {
            m %= i;
            m += i;
        }
    }
    for (int i = 1; i <= n; i++)
    {
        fprintf(fout, "%d\n", a[i]);
    }
    return 0;
}

S1

#include <bits/stdc++.h>
using namespace std;
int n, m, l;
int a[100020];
int b[100020];
int r[100020];
int c[100020];
void mul(int a[], int b[])
{
    for (int i = 1; i <= n; i++)
    {
        c[i] = a[b[i]];
    }
    for (int i = 1; i <= n; i++)
    {
        a[i] = c[i];
    }
}
int main()
{
    freopen("swap.in", "r", stdin);
    freopen("swap.out", "w", stdout);
    scanf("%d%d%d", &n, &m, &l);
    for (int i = 1; i <= n; i++)
    {
        a[i] = i;
        b[i] = i;
    }
    for (int i = 0; i < m; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        reverse(b + x, b + y + 1);
    }
    for (int i = 1; i <= n; i++)
    {
        r[b[i]] = i;
    }
    for (int i = 1; i <= n; i++)
    {
        b[i] = r[i];
    }
    for (; l > 0; l >>= 1)
    {
        if (l & 1)
        {
            mul(a, b);
        }
        mul(b, b);
    }
    for (int i = 1; i <= n; i++)
    {
        r[a[i]] = i;
    }
    for (int i = 1; i <= n; i++)
    {
        a[i] = r[i];
    }
    for (int i = 1; i <= n; i++)
    {
        printf("%d\n", a[i]);
    }
    return 0;
}

S2

#include <bits/stdc++.h>
using namespace std;
const int mod = 1000000007;
int sx[1000020];
int sy[1000020];
long long ans = 0;
map<int, vector<pair<int, int> > > xx, yy;
void gao(vector<pair<int, int> > &a, int s[])
{
    sort(a.begin(), a.end());
    long long s1 = 0, s2 = 0;
    for (int i = 0; i < a.size(); i++)
    {
        s2 += a[i].first;
    }
    for (int i = 0; i < a.size(); i++)
    {
        s[a[i].second] = (i * a[i].first - s1) + (s2 - (a.size() - i) * a[i].first);
        s1 += a[i].first;
        s2 -= a[i].first;
    }
}
int main()
{
    freopen("triangles.in", "r", stdin);
    freopen("triangles.out", "w", stdout);
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        xx[x].push_back(make_pair(y, i));
        yy[y].push_back(make_pair(x, i));
    }
    for (auto &i: xx)
    {
        gao(i.second, sx);
    }
    for (auto &i: yy)
    {
        gao(i.second, sy);
    }
    for (int i = 0; i < n; i++)
    {
        ans = (ans + (long long)sx[i] * sy[i]) % mod;
    }
    printf("%d\n", (int)ans);
    return 0;
}

S3

#include <bits/stdc++.h>
using namespace std;
int n;
int w[10020];
int c[2], s[2];
vector<int> a[10020];
void dfs(int x, int y, int d)
{
    s[d] = (s[d] + w[x]) % 12;
    c[d]++;
    for (int i: a[x])
    {
        if (i != y)
        {
            dfs(i, x, d ^ 1);
        }
    }
}
int main()
{
    freopen("clocktree.in", "r", stdin);
    freopen("clocktree.out", "w", stdout);
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &w[i]);
    }
    for (int i = 1; i < n; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        a[x].push_back(y);
        a[y].push_back(x);
    }
    dfs(1, 0, 0);
    if (s[0] == s[1])
    {
        printf("%d\n", n);
    }
    else if ((s[0] + 1) % 12 == s[1])
    {
        printf("%d\n", c[1]);
    }
    else if ((s[1] + 1) % 12 == s[0])
    {
        printf("%d\n", c[0]);
    }
    else
    {
        printf("0\n");
    }
    return 0;
}

G1

#include <bits/stdc++.h>
using namespace std;
int n, m, c, x, y, z;
vector<pair<int, int> > a[100020];
int d[100020];
int in[100020];
queue<int> q;
int main()
{
    freopen("timeline.in", "r", stdin);
    freopen("timeline.out", "w", stdout);
    scanf("%d%d%d", &n, &m, &c);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &d[i]);
    }
    for (int i = 0; i < c; i++)
    {
        scanf("%d%d%d", &x, &y, &z);
        a[x].push_back(make_pair(y, z));
        in[y]++;
    }
    for (int i = 1; i <= n; i++)
    {
        if (in[i] == 0)
        {
            q.push(i);
        }
    }
    while (q.size() > 0)
    {
        int u = q.front();
        q.pop();
        for (pair<int, int> i: a[u])
        {
            if (d[i.first] < d[u] + i.second)
            {
                d[i.first] = d[u] + i.second;
            }
            if (!--in[i.first])
            {
                q.push(i.first);
            }
        }
    }
    for (int i = 1; i <= n; i++)
    {
        printf("%d\n", d[i]);
    }
    return 0;
}

G2

#include <bits/stdc++.h>
using namespace std;
const int mod = 1000000007;
int n, x, y, z, c;
int a[200020];
int b[200020];
int main()
{
    freopen("help.in", "r", stdin);
    freopen("help.out", "w", stdout);
    scanf("%d", &n);
    for (int i = b[0] = 1; i <= n; i++)
    {
        b[i] = b[i - 1] * 2 % mod;
    }
    for (int i = 0; i < n; i++)
    {
        scanf("%d%d", &x, &y);
        a[x] = +1;
        a[y] = -1;
    }
    for (int i = 1; i <= 2*n; i++)
    {
        c += a[i];
        if (a[i] == 1)
        {
            z = (z + b[n - c]) % mod;
        }
    }
    printf("%d\n", z);
    return 0;
}

G3

#include <bits/stdc++.h>
using namespace std;
int n;
int s[100020];
vector<int> a[100020];
vector<int> b[100020];
void dfs(int x, int y)
{
    s[x] = 1;
    for (int i: a[x])
    {
        if (i != y)
        {
            dfs(i, x);
            b[x].push_back(s[i]);
            s[x] += s[i];
        }
    }
}
int ok(int l)
{
    if ((n - 1) % l != 0)
    {
        return 0;
    }
    for (int i = 1; i <= n; i++)
    {
        vector<int> c;
        for (int j: b[i])
        {
            j %= l;
            if (j > 0)
            {
                c.push_back(j);
            }
        }
        if ((s[i] - 1) % l > 0)
        {
            c.push_back(l - (s[i] - 1) % l);
        }
        sort(c.begin(), c.end());
        if (c.size() % 2 > 0)
        {
            return false;
        }
        for (int i = 0; i < c.size(); i++)
        {
            if (c[i] + c[c.size() - 1 - i] != l)
            {
                return false;
            }
        }
    }
    return true;
}
int main()
{
    freopen("deleg.in", "r", stdin);
    freopen("deleg.out", "w", stdout);
    scanf("%d", &n);
    for (int i = 1; i < n; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        a[x].push_back(y);
        a[y].push_back(x);
    }
    dfs(1, 0);
    for (int i = 1; i < n; i++)
    {
        printf("%d", ok(i));
    }
    printf("\n");
    return 0;
}

P1

#include <bits/stdc++.h>
using namespace std;
int n, x, y, z, M, flag;
vector<int> a[100020];

int dfs(int x, int y) {
    multiset<int> b;
    for (int i = 0; i < a[x].size(); i++) {
        if (a[x][i] != y) {
            int l = dfs(a[x][i], x);
            b.insert(l + 1);
            if (!flag)
            {
                return 0;
            }
        }
    }
    int only = 0;
    while (b.size() > 1)
    {
        int u = *b.begin();
        b.erase(b.begin());
        if (u < M)
        {
            multiset<int>::iterator it = b.lower_bound(M - u);
            if (it == b.end())
            {
                if (only == 0)
                {
                    only = u;
                    continue;
                }
                flag = false;
                return 0;
            }
            if (b.size() == 1 && *it >= M)
            {
                return *b.begin();
            }
            b.erase(it);
        }
    }
    if (b.size() == 0)
    {
        return only;
    }
    else
    {
        if (only > 0)
        {
            flag = false;
            return 0;
        }
        return *b.begin();
    }
}
bool ok() {
    flag = true;
    int res = dfs(1, 0);
    return flag && (res >= M || res == 0);
}
int main() {
    freopen("deleg.in", "r", stdin);
    freopen("deleg.out", "w", stdout);
    scanf("%d", &n);
    for (int i = 1; i < n; i++) {
        scanf("%d%d", &x, &y);
        a[x].push_back(y);
        a[y].push_back(x);
    }
    int L = 1, R = n;
    while (L < R - 1) {
        M = (L + R) / 2;
        if (ok()) {
            L = M;
        } else {
            R = M;
        }
    }
    printf("%d\n", L);
    return 0;
}

P2

#include <bits/stdc++.h>
using namespace std;
int n;
char s[320][320];
int ul[320][320];
int ur[320][320];
long long ans = 0;
bool in(int x, int y)
{
    return 0 < x && x <= n && 0 < y && y <= n;
}
int UL(int x, int y)
{
    int d = max(x - n, y - n);
    if (d > 0)
    {
        x -= d;
        y -= d;
    }
    if (x < 0 || y < 0)
    {
        return 0;
    }
    return ul[x][y];
}
int UR(int x, int y)
{
    int d = max(x - n, 1 - y);
    if (d > 0)
    {
        x -= d;
        y += d;
    }
    if (x < 0 || y > n)
    {
        return 0;
    }
    return ur[x][y];
}
void bf()
{
    int ans = 0;
    for (int i = 0; i < n * n; i++)
    {
        int x1 = i / n + 1;
        int y1 = i % n + 1;
        if (s[x1][y1] != '*')
        {
            continue;
        }
        for (int j = i + 1; j < n * n; j++)
        {
            int x2 = j / n + 1;
            int y2 = j % n + 1;
            if (s[x2][y2] != '*')
            {
                continue;
            }
            for (int k = j + 1; k < n * n; k++)
            {
                int x3 = k / n + 1;
                int y3 = k % n + 1;
                if (s[x3][y3] != '*')
                {
                    continue;
                }
                if (abs(x1 - x2) + abs(y1 - y2) != abs(x1 - x3) + abs(y1 - y3))
                {
                    continue;
                }
                if (abs(x1 - x2) + abs(y1 - y2) != abs(x2 - x3) + abs(y2 - y3))
                {
                    continue;
                }
                // cout << i << ' ' << j << ' ' << k << endl;
                ans++;
            }
        }
    }
    cout << ans << endl;
}
int main()
{
    freopen("triangles.in", "r", stdin);
    freopen("triangles.out", "w", stdout);
    // srand(time(0));
    scanf("%d", &n);
    // n = 10;
    for (int i = 1; i <= n; i++)
    {
        scanf("%s", s[i] + 1);
        // for (int j = 1; j <= n; j++)
        // {
        //  s[i][j] = rand() & 1 ? '*' : '.';
        // }
    }
    // bf();
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            ul[i][j] = ul[i - 1][j - 1] + (s[i][j] == '*');
            ur[i][j] = ur[i - 1][j + 1] + (s[i][j] == '*');
        }
    }
    for (int x1 = 1; x1 <= n; x1++)
    {
        for (int y1 = 1; y1 <= n; y1++)
        {
            if (s[x1][y1] != '*')
            {
                continue;
            }
            for (int k = 1; k <= n; k++)
            {
                int x2 = x1 + k;
                int y2 = y1 - k;
                if (in(x2, y2))
                {
                    if (s[x2][y2] == '*')
                    {
                        // cout << x1 << ' ' << y1 << ' ' << x2 << ' ' << y2 << ' ' << ans << endl;
                        ans += UR(x2 + k, y2 + k) - UR(x1 + k - 1, y1 + k + 1);
                        // cout << x1 << ' ' << y1 << ' ' << x2 << ' ' << y2 << ' ' << ans << endl;
                        ans += UR(x2 - k, y2 - k) - UR(x1 - k - 1, y1 - k + 1);
                        // cout << UR(x2 - k, y2 - k) << ' ' << UR(x1 - k - 1, y1 - k + 1) << endl;
                        // cout << x1 << ' ' << y1 << ' ' << x2 << ' ' << y2 << ' ' << ans << endl;
                    }
                }
                else
                {
                    break;
                }
            }
            for (int k = 1; k <= n; k++)
            {
                int x2 = x1 + k;
                int y2 = y1 + k;
                if (in(x2, y2))
                {
                    if (s[x2][y2] == '*')
                    {
                        ans += UL(x2 + k - 1, y2 - k - 1) - UL(x1 + k, y1 - k);
                        ans += UL(x2 - k - 1, y2 + k - 1) - UL(x1 - k, y1 + k);
                    }
                }
                else
                {
                    break;
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}

P3

#include <bits/stdc++.h>
#include <random>
using namespace std;
const int mod = 1000000007;
int n, m;
pair<int, int> a[100020];
int pos[200020];
int s[20][20];
int fac[20];
void bf()
{
    int ans = 0;
    int v[100];
    for (int i = 0; i < 1 << n; i++)
    {
        memset(v, 0, sizeof v);
        for (int j = 0; j < n; j++)
        {
            if (i >> j & 1)
            {
                for (int k = a[j].first; k < a[j].second; k++)
                {
                    v[k] = 1;
                }
            }
        }
        int cnt = 0;
        for (int j = 0; j < 2 * n; j++)
        {
            if (v[j] == 0 && v[j + 1] == 1)
            {
                cnt++;
            }
        }
        long long tmp = 1;
        for (int j = 0; j < m; j++)
        {
            tmp = tmp * cnt % mod;
        }
        ans = (ans + tmp) % mod;
    }
    printf("%d\n", ans);
    return;
}
long long f[100020][12];
void work()
{
    //f[i][j]=sum{f[k][j-1]*2^sum{[r[o]<l[i]]}(k<o<i)}(r[k]<l[i])
    memset(f, 0, sizeof f);
    f[0][0] = 1;
    for (int j = 1; j <= m + 1; j++)
    {
        for (int i = 0; i <= n + 1; i++)
        {
            long long b = 1;
            for (int k = i - 1; k >= 0; k--)
            {
                if (a[k].second < a[i].first)
                {
                    f[i][j] = (f[i][j] + f[k][j - 1] * b) % mod;
                    // cout << i << ' ' << j << ' ' << k << ' ' << b << endl;
                    b = b * 2 % mod;
                }
            }
            // printf("f1 %d %d %lld\n", i, j, f[i][j]);
        }
    }
    long long ans = 0;
    for (int j = 0; j <= m + 1; j++)
    {
        // for (int i = 0; i <= n + 1; i++)
        // {
        //  printf("%lld ", f[i][j]);
        // }
        // printf("\n");
        // printf("%d %lld\n", j, f[n + 1][j]);
    }
    for (int j = 1; j <= m; j++)
    {
        ans = (ans + f[n + 1][j + 1] * fac[j] % mod * s[m][j] % mod);
    }
    printf("%lld\n", ans);
    return;
}

long long g[300020];
long long h[300020];

void build(int x, int l, int r)
{
    h[x] = 1;
    g[x] = 0;
    if (l == r)
    {
        return;
    }
    int mid = (l + r) / 2;
    build(x * 2, l, mid);
    build(x * 2 + 1, mid + 1, r);
}

void change(int x, int l, int r, int p, int v)
{
    if (l == r)
    {
        g[x] = v;
        return;
    }
    int mid = (l + r) / 2;
    if (p <= mid)
    {
        change(x * 2, l, mid, p, v);
    }
    else
    {
        change(x * 2 + 1, mid + 1, r, p, v);
    }
    g[x] = (g[x * 2] * h[x * 2] + g[x * 2 + 1] * h[x * 2 + 1]) % mod;
}

void modify(int x, int l, int r, int p)
{
    if (l > p)
    {
        return;
    }
    if (r <= p)
    {
        h[x] = h[x] * 2 % mod;
        return;
    }
    int mid = (l + r) / 2;
    modify(x * 2, l, mid, p);
    modify(x * 2 + 1, mid + 1, r, p);
    g[x] = (g[x * 2] * h[x * 2] + g[x * 2 + 1] * h[x * 2 + 1]) % mod;
}

long long query(int x, int l, int r, int p)
{
    if (l > p)
    {
        return 0;
    }
    if (r <= p)
    {
        return g[x] * h[x];
    }
    int mid = (l + r) / 2;
    return (query(x * 2, l, mid, p) + query(x * 2 + 1, mid + 1, r, p)) * h[x] % mod;
}

void work2()
{
    //f[i][j]=sum{f[k][j-1]*2^sum{[r[o]<l[i]]}(k<o<i)}(r[k]<l[i])
    memset(f, 0, sizeof f);
    f[0][0] = 1;
    for (int j = 1; j <= m + 1; j++)
    {
        build(1, 0, n + 1);
        for (int i = 0; i <= n + 1; i++)
        {
            for (int k = i == 0 ? 0 : (a[i-1].first + 1); k < a[i].first; k++)
            {
                if (pos[k] >= 0)
                {
                    change(1, 0, n + 1, pos[k], f[pos[k]][j - 1]);
                    modify(1, 0, n + 1, pos[k] - 1);
                }
            }
            f[i][j] = query(1, 0, n + 1, i - 1);
            // printf("f2 %d %d %lld\n", i, j, f[i][j]);
        }
    }
    long long ans = 0;
    for (int j = 0; j <= m + 1; j++)
    {
        // for (int i = 0; i <= n + 1; i++)
        // {
        //  printf("%lld ", f[i][j]);
        // }
        // printf("\n");
        // printf("%d %lld\n", j, f[n + 1][j]);
    }
    for (int j = 1; j <= m; j++)
    {
        ans = (ans + f[n + 1][j + 1] * fac[j] % mod * s[m][j] % mod);
    }
    printf("%lld\n", ans);
    return;
}
int data[200020];
int main()
{
    freopen("help.in", "r", stdin);
    freopen("help.out", "w", stdout);
    srand(time(0));
    scanf("%d%d", &n, &m);
    s[0][0]=1;
    for (int i = 1; i <= m; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            s[i][j] = ((long long)s[i - 1][j] * j + s[i - 1][j - 1]) % mod;
        }
    }
    fac[0] = 1;
    for (int i = 1; i <= m; i++)
    {
        fac[i] = (long long)fac[i - 1] * i % mod;
    }
    for (int i = 0; i < 2 * n; i++)
    {
        data[i] = i;
    }
    random_device rd;
    mt19937 randomizer(rd());
    shuffle(data, data + 2 * n, randomizer);
    for (int i = 0; i < n; i++)
    {
        a[i].first = data[2 * i] + 1;
        a[i].second = data[2 * i + 1] + 1;
        if (a[i].first > a[i].second)
        {
            swap(a[i].first, a[i].second);
        }
        scanf("%d%d", &a[i].first, &a[i].second);
    }
    // bf();
    a[n] = make_pair(-1, 0);
    a[n + 1] = make_pair(2 * n + 1, 2 * n + 2);
    sort(a, a + n + 2);
    for (int i = 1; i <= n; i++)
    {
        pos[a[i].first] = -i;
        pos[a[i].second] = i;
    }
    work();
    work2();
    return 0;
}