【XJTU 2020暑期集训】Day7 - 2017ACM-ICPC亚洲区沈阳站

A - BBP Formula

先将原式拆成四个级数,第一个级数为 \sum_1=\sum_{k=0}^\infty\frac{1}{16^k}\cdot\frac{1}{8k+1},其余三个同理,分别计算每个级数的答案,则最终 \pi=4\sum_1-2\sum_2-\sum_3-\sum_4。将 \sum_1 乘上 16^{n-1},即 \sum_{k=0}^\infty 16^{n-1-k}\cdot\frac{1}{8k+1},则乘完之后的第一位小数即为原来的第 n 位。由于我们只需要保留小数部分,所以将级数拆为两部分:\sum_1=\sum_{k=0}^{n-1} 16^{n-1-k}\cdot\frac{1}{8k+1}+\sum_{k=n}^\infty 16^{n-1-k}\cdot\frac{1}{8k+1},显然只有前半部分能对整数部分产生贡献,所以将前半部分的 16^{n-1-k}\bmod 8k+1 即可,用快速幂实现。最终就是先 O(n) 算出前半部分,由于后半部分的值非常小,算上20位就足够了,这样就算出了 \sum_1 将小数点右移 n-1 位后小数部分的结果,\sum_{2\dots4} 同理,最终将四个级数乘系数相加,取第一位小数即可。

B - Bridge

C - Empty Convex Polygons

D - Defense of the Ancients

E - Five-round Show Hand

F - Heron and His Triangle

由海伦公式可得三角形面积 S=\frac{t\sqrt{3(t^2-4)}}{4}。当 t=2k+1 时,易证 S 不可能为整数;当 t=2k 时,S=k\sqrt{3(k^2-1)},则 3(k^2-1) 应为完全平方数 3\cdot 3T^2,可得 k^2-3T^2=1,为一个佩尔方程(Pell's equation),其最小解为 x_1=2,y_1=1,由佩尔方程解的递推式 x_{i+1}=x_1x_i+ny_1y_i,y_{i+1}=x_1y_i+y_1x_i,可得其所有解,且解的增长速度为指数级别。所以利用递推式找到 t=2k 恰好大于等于 n 的解即可。总复杂度 O(\log n)

G - Infinite Fraction Path

当一条路径的长度大于等于 n 时,一定已经包含了循环节。所以问题就转换成了,有 n 个长度为 n 的字符串,让你找出字典序最大的那个,类似后缀数组倍增即可,总复杂度 O(n\log n)。具体实现的时候,先 O(n\log n) 预处理出 \mathrm{next}[i][j],表示从 i 开始跳 2^j 步会跳到哪里;然后这里的后缀数组与一般字符串处理中后缀数组的不同在于,在计算tsa时,不能通过后半段字符串的sa直接求出,因为本题中字符串不是线性的,而是以基环内向树森林的形式构成的,可能存在多个前半段与同一个后半段对应,所以用基数排序第一步求出tsa即可。

H - Legends of the Three Kingdoms

I - Little Boxes

签到题。注意当四个数均等于 2^{62} 时,和为 2^{64} 恰好会爆unsigned long long,特判一下就好。

J - New Self-describing Sequence

K - Rabbits

注意到当左右两端其中某一端存在连续的两只兔子时,答案为此时所有兔子之间的空位数之和。所以当当左右两端均不存在连续的两只兔子时,左右两端哪边的空位少,就跳哪只兔子。所以答案就是总空位数减去左右两端空位数的最小值。

L - Tree

当某一条边两边的节点数都大于等于 k 时,这条边一定会被加入到答案中。所以dfs统计一下这样的边的个数就是答案。总复杂度 O(n)

M - Wandering Robots

Code

A - BBP Formula

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

using namespace std;

int T, n;

int fpow(int x, int k, int p) {
    int ans = 1;
    while (k) {
        if (k & 1) {
            ans = ans * x % p;
        }
        x = x * x % p, k >>= 1;
    }
    return ans;
}

char getc(int x) {
    if (x < 10) {
        return x + '0';
    }
    return x - 10 + 'A';
}

signed main() {
    scanf("%lld", &T);
    for (int cas = 1; cas <= T; cas++) {
        scanf("%lld", &n);
        double s1 = 0, s2 = 0, s3 = 0, s4 = 0;
        for (int i = 0; i < n; i++) {
            s1 += (double)fpow(16, n - 1 - i, 8 * i + 1) / (8 * i + 1);
            s2 += (double)fpow(16, n - 1 - i, 8 * i + 4) / (8 * i + 4);
            s3 += (double)fpow(16, n - 1 - i, 8 * i + 5) / (8 * i + 5);
            s4 += (double)fpow(16, n - 1 - i, 8 * i + 6) / (8 * i + 6);
        }
        for (int i = n; i <= n + 20; i++) {
            s1 += pow(16, n - 1 - i) / (8 * i + 1);
            s2 += pow(16, n - 1 - i) / (8 * i + 4);
            s3 += pow(16, n - 1 - i) / (8 * i + 5);
            s4 += pow(16, n - 1 - i) / (8 * i + 6);
        }
        double res = 4 * s1 - 2 * s2 - s3 - s4;
        int ans = ((int)floor(res * 16) % 16 + 16) % 16;
        printf("Case #%lld: %lld %c\n", cas, n, getc(ans));
    }
}

B - Bridge


C - Empty Convex Polygons


D - Defense of the Ancients


E - Five-round Show Hand


F - Heron and His Triangle

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stack>
#define int __int128_t

using namespace std;

int T, n;

istream& operator>>(istream& in, __int128_t& x) {
    string s;
    in >> s;
    x = 0;
    for (int i = 0; i < s.size(); i++) {
        x = x * 10 + s[i] - '0';
    }
    return in;
}

ostream& operator<<(ostream& out, __int128_t x) {
    if (x == 0) {
        out << "0";
        return out;
    }
    stack<signed> st;
    while (x) {
        st.push(x % 10), x /= 10;
    }
    while (!st.empty()) {
        out << st.top();
        st.pop();
    }
    return out;
}

signed main() {
    ios::sync_with_stdio(false);
    cin >> T;
    while (T--) {
        cin >> n;
        int x = 2, y = 1;
        while (x * 2 < n) {
            int nx = 2 * x + 3 * y;
            int ny = 2 * y + x;
            x = nx, y = ny;
        }
        cout << x * 2 << endl;
    }
}

G - Infinite Fraction Path

#include <iostream>
#include <stdio.h>
#include <string.h>
#define MAX_N 150005
#define MAX_L 20
#define sqr(x) ((long long)(x) * (x))

using namespace std;

int T, n;
int cnt[MAX_N];
int sa[MAX_N], tsa[MAX_N];
int rk[MAX_N], trk[MAX_N];
int nxt[MAX_N][MAX_L];
char d[MAX_N];

int mov(int x) {
    return (sqr(x) + 1) % n;
}

void getnxt() {
    for (int i = 0; i < n; i++) {
        nxt[i][0] = mov(i);
    }
    for (int j = 1; j < MAX_L; j++) {
        for (int i = 0; i < n; i++) {
            nxt[i][j] = nxt[nxt[i][j - 1]][j - 1];
        }
    }
}

void suffix() {
    int mx = max(n, 10);
    for (int i = 0; i < mx; i++) cnt[i] = 0;
    for (int i = 0; i < n; i++) cnt[rk[i] = d[i]]++;
    for (int i = 1; i < mx; i++) cnt[i] += cnt[i - 1];
    for (int i = n - 1; i >= 0; i--) sa[--cnt[rk[i]]] = i;
    for (int j = 0; (1 << j) < n; j++) {
        for (int i = 0; i < mx; i++) cnt[i] = 0;
        for (int i = 0; i < n; i++) cnt[rk[nxt[i][j]]]++;
        for (int i = 1; i < mx; i++) cnt[i] += cnt[i - 1];
        for (int i = n - 1; i >= 0; i--) tsa[--cnt[rk[nxt[i][j]]]] = i;
        for (int i = 0; i < mx; i++) cnt[i] = 0;
        for (int i = 0; i < n; i++) cnt[rk[i]]++;
        for (int i = 1; i < mx; i++) cnt[i] += cnt[i - 1];
        for (int i = n - 1; i >= 0; i--) sa[--cnt[rk[tsa[i]]]] = tsa[i];
        for (int i = 0; i < n; i++) trk[i] = rk[i];
        int tot = 0;
        rk[sa[0]] = tot;
        for (int i = 1; i < n; i++) {
            if (trk[sa[i]] != trk[sa[i - 1]] ||
                (trk[sa[i]] == trk[sa[i - 1]] && trk[nxt[sa[i]][j]] != trk[nxt[sa[i - 1]][j]])) {
                rk[sa[i]] = ++tot;
            } else {
                rk[sa[i]] = tot;
            }
        }
        if (tot == n - 1) {
            break;
        }
    }
}

int main() {
    scanf("%d", &T);
    for (int cas = 1; cas <= T; cas++) {
        scanf("%d%s", &n, d);
        for (int i = 0; i < n; i++) {
            d[i] = 9 - (d[i] - '0');
        }
        getnxt();
        suffix();
        printf("Case #%d: ", cas);
        for (int i = 1, t = sa[0]; i <= n; i++, t = mov(t)) {
            printf("%d", (int)(9 - d[t]));
        }
        printf("\n");
    }
}

H - Legends of the Three Kingdoms


I - Little Boxes

#include <iostream>
#include <stdio.h>
#include <string.h>
#define MX (1ULL << 62)
#define int unsigned long long

using namespace std;

int T, a, b, c, d;

signed main() {
    ios::sync_with_stdio(false);
    cin >> T;
    while (T--) {
        cin >> a >> b >> c >> d;
        if (a == MX && b == MX && c == MX && d == MX) {
            cout << "18446744073709551616" << endl;
        } else {
            cout << a + b + c + d << endl;
        }
    }
}

J - New Self-describing Sequence


K - Rabbits

#include <iostream>
#include <stdio.h>
#include <string.h>
#define MAX_N 505

using namespace std;

int T, n;
int a[MAX_N];
int sp[MAX_N];

int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            scanf("%d", a + i);
        }
        int sum = 0;
        for (int i = 1; i < n; i++) {
            sp[i] = a[i + 1] - a[i] - 1;
            sum += sp[i];
        }
        printf("%d\n", sum - min(sp[1], sp[n - 1]));
    }
}

L - Tree

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

using namespace std;

int T, n, K, ans;
int siz[MAX_N];
vector<int> e[MAX_N];

void dfs(int x, int p) {
    siz[x] = 1;
    for (int i = 0; i < e[x].size(); i++) {
        int t = e[x][i];
        if (t != p) {
            dfs(t, x);
            siz[x] += siz[t];
            if (siz[t] >= K && n - siz[t] >= K) {
                ans++;
            }
        }
    }
}

int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &K);
        for (int i = 1; i <= n; i++) {
            e[i].clear();
        }
        int x, y;
        for (int i = 1; i < n; i++) {
            scanf("%d%d", &x, &y);
            e[x].push_back(y);
            e[y].push_back(x);
        }
        ans = 0;
        dfs(1, 0);
        printf("%d\n", ans);
    }
}

M - Wandering Robots


点赞

发表评论

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