【XJTU 2020暑期集训】Day5 - 2016-2017 ACM-ICPC, Asia Tsukuba Regional Contest

A - Rearranging a Sequence

签到题。从后到前遍历每个操作,如果当前操作数未输出,则输出并标记。最后遍历 1\dots n,输出未输出的数。

B - Quality of Check Digits

签到题。简单模拟即可。

C - Distribution Center

显然一条生产线能够收到的货物是来自连续的一段生产线,则只需要计算出能送到生产线 i 的最小生产线 \mathrm{up}_i 和 最大生产线 \mathrm{dn}_i,那么 i 能够收到的货物数量为 \mathrm{dn}_i-\mathrm{up}_i+1。初始 \mathrm{up}_i=\mathrm{dn}_i=i,将机械臂按 x 升序排序,更新 \mathrm{up}\mathrm{dn} 即可。

D - Hidden Anagrams

O(n) 枚举子串长度,对于每一个长度 O(n\log n)s_1 的该长度的所有子串的hash值存入一个set中,再枚举 s_2 中所有该长度的子串的hash并在set中查找。总复杂度 O(n^2\log n)

E - Infallibly Crack Perplexing Cryptarithm

F - Three Kingdoms of Bourdelot

G - Placing Medals on a Binary Tree

H - Animal Companion in Maze

I - Skinny Polygon

w,h 为给定边界。构造一:用三角形,三个点分别为 (0,0),(w,h),(x,y),则构成的三角形面积为 \frac{1}{2}|hx-wy|,令 g=\mathrm{gcd}(w,h),则用exgcd可解出方程 hx-wy=g 的非负整数解,此时三角形面积为 \frac{g}{2},当 g\le 50000 时满足题意。构造二:用凹四边形,四个点分别为 (0,0),(w-1,h),(w,h-1),(x,y),其中 x=\frac{w}{g},y=\frac{h}{g},此时四边形面积为 \frac{\sqrt{2}}{2}\sqrt{x^2+y^2}=\frac{\sqrt{2}}{2g}\sqrt{w^2+h^2},由于 w,h\le 10^9,该构造在 g\ge 40000 时满足题意。综上,根据 g 分情况讨论即可。

J - Cover the Polygon with Your Disk

K - Black and White Boxes

Code

A - Rearranging a Sequence

#include <iostream>
#include <stdio.h>
#include <string.h>
#define MAX_N 200005
#define MAX_M 100005

using namespace std;

int n, m;
int a[MAX_M];
bool vis[MAX_N];

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        scanf("%d", a + i);
    }
    for (int i = m; i >= 1; i--) {
        if (!vis[a[i]]) {
            printf("%d\n", a[i]);
            vis[a[i]] = true;
        }
    }
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            printf("%d\n", i);
        }
    }
}

B - Quality of Check Digits

#include <iostream>
#include <stdio.h>
#include <string.h>
#define MAX_N 15
#define MAX_L 10

using namespace std;

int ans = 0;
int a[MAX_L];
int w[MAX_N][MAX_N];

int gete() {
    int res = 0;
    for (int i = 1; i <= 4; i++) {
        res = w[res][a[i]];
    }
    return res;
}

bool check(int x) {
    for (int i = 4; i >= 1; i--) {
        a[i] = x % 10, x /= 10;
    }
    a[5] = gete();
    for (int i = 1; i <= 4; i++) {
        if (a[i] != a[i + 1]) {
            swap(a[i], a[i + 1]);
            if (w[gete()][a[5]] == 0) {
                return false;
            }
            swap(a[i], a[i + 1]);
        }
    }
    for (int i = 1; i <= 5; i++) {
        int t = a[i];
        for (int r = 0; r < 10; r++) {
            if (r != t) {
                a[i] = r;
                if (w[gete()][a[5]] == 0) {
                    return false;
                }
            }
        }
        a[i] = t;
    }
    return true;
}

int main() {
    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < 10; j++) {
            scanf("%d", &w[i][j]);
        }
    }
    for (int i = 0; i <= 9999; i++) {
        if (!check(i)) {
            ans++;
        }
    }
    printf("%d\n", ans);
}

C - Distribution Center

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define MAX_N 200005
#define MAX_M 100005
#define pii pair<int, int>

using namespace std;

int n, m;
int up[MAX_N];
int dn[MAX_N];
pii p[MAX_M];

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        scanf("%d%d", &p[i].first, &p[i].second);
    }
    sort(p + 1, p + 1 + m);
    for (int i = 1; i <= n; i++) {
        up[i] = dn[i] = i;
    }
    for (int i = 1; i <= m; i++) {
        int t = p[i].second;
        up[t + 1] = min(up[t + 1], up[t]);
        dn[t] = max(dn[t], dn[t + 1]);
    }
    for (int i = 1; i <= n; i++) {
        printf("%d ", dn[i] - up[i] + 1);
    }
    printf("\n");
}

D - Hidden Anagrams

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <set>
#define MAX_N 4005
#define MAX_A 30
#define MOD1 19260817
#define MOD2 19491001
#define BASE 233
#define pii pair<int, int>
#define LL long long

using namespace std;

int n, m;
int pw1[MAX_A];
int pw2[MAX_A];
int cnt[MAX_A];
char s[MAX_N];
char p[MAX_N];

int main() {
    pw1[0] = pw2[0] = 1;
    for (int i = 1; i < 26; i++) {
        pw1[i] = (LL)pw1[i - 1] * BASE % MOD1;
        pw2[i] = (LL)pw2[i - 1] * BASE % MOD2;
    }
    scanf("%s%s", s + 1, p + 1);
    n = strlen(s + 1), m = strlen(p + 1);
    for (int len = min(n, m); len >= 1; len--) {
        set<pii> st;
        for (int i = 0; i < 26; i++) {
            cnt[i] = 0;
        }
        for (int i = 1; i <= len; i++) {
            cnt[s[i] - 'a']++;
        }
        int hash1 = 0, hash2 = 0;
        for (int i = 25; i >= 0; i--) {
            hash1 = ((LL)hash1 * BASE + cnt[i]) % MOD1;
            hash2 = ((LL)hash2 * BASE + cnt[i]) % MOD2;
        }
        for (int l = 1, r = len; r <= n; l++, r++) {
            st.insert(pii(hash1, hash2));
            if (r < n) {
                int x = s[l] - 'a', y = s[r + 1] - 'a';
                hash1 = (hash1 - pw1[x] + MOD1) % MOD1;
                hash2 = (hash2 - pw2[x] + MOD2) % MOD2;
                hash1 = (hash1 + pw1[y]) % MOD1;
                hash2 = (hash2 + pw2[y]) % MOD2;
                cnt[x]--, cnt[y]++;
            }
        }
        for (int i = 0; i < 26; i++) {
            cnt[i] = 0;
        }
        for (int i = 1; i <= len; i++) {
            cnt[p[i] - 'a']++;
        }
        hash1 = 0, hash2 = 0;
        for (int i = 25; i >= 0; i--) {
            hash1 = ((LL)hash1 * BASE + cnt[i]) % MOD1;
            hash2 = ((LL)hash2 * BASE + cnt[i]) % MOD2;
        }
        for (int l = 1, r = len; r <= m; l++, r++) {
            if (st.count(pii(hash1, hash2))) {
                printf("%d\n", len);
                return 0;
            }
            if (r < m) {
                int x = p[l] - 'a', y = p[r + 1] - 'a';
                hash1 = (hash1 - pw1[x] + MOD1) % MOD1;
                hash2 = (hash2 - pw2[x] + MOD2) % MOD2;
                hash1 = (hash1 + pw1[y]) % MOD1;
                hash2 = (hash2 + pw2[y]) % MOD2;
                cnt[x]--, cnt[y]++;
            }
        }
    }
    printf("0\n");
}

E - Infallibly Crack Perplexing Cryptarithm


F - Three Kingdoms of Bourdelot


G - Placing Medals on a Binary Tree


H - Animal Companion in Maze


I - Skinny Polygon

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#define int long long

using namespace std;

int T, w, h;

int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}

void exgcd(int a, int b, int &x, int &y) {
    if (!b) {
        x = 1, y = 0;
        return;
    }
    exgcd(b, a % b, y, x);
    y -= a / b * x;
}

signed main() {
    scanf("%lld", &T);
    while (T--) {
        scanf("%lld%lld", &w, &h);
        int g = gcd(w, h);
        if (g <= 50000) {
            int x, y;
            exgcd(h, w, x, y);
            int A = h / g, B = w / g;
            int xmin = (x % B + B) % B;
            int ymax = (g - h * xmin) / w;
            if (ymax > 0) {
                int t = ceil((double)ymax / A);
                xmin += B * t, ymax -= A * t;
            }
            printf("3\n");
            printf("0 0\n");
            printf("%lld %lld\n", w, h);
            printf("%lld %lld\n", xmin, -ymax);
        } else {
            printf("4\n");
            printf("0 0\n");
            printf("%lld %lld\n", w - 1, h);
            printf("%lld %lld\n", w / g, h / g);
            printf("%lld %lld\n", w, h - 1);
        }
    }
}

J - Cover the Polygon with Your Disk


K - Black and White Boxes


点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注