【XJTU 2020暑期集训】Day3 - 2017 CCPC Final

A - Dogs and Cages

所求期望等于每一种情况走错笼子的狗的数量之和,再除以总情况数。

考虑每只狗对于答案的贡献。假设狗 i 走到了错误的笼子 1\dots i-1,i+1\dots n,共 n-1 种情况,对于每一种情况,剩下的 n-1 只狗可以排列出 (n-1)! 种情况。所以对于第 i 只狗,他对于分子的贡献为 (n-1)\cdot (n-1)!。总共有 n 只狗,所以分子等于 (n-1)\cdot n!。总情况数为总排列数 n!。所以答案为 n-1

B - Same Digit

C - Rich Game

如果 x\gt y,则熊猫可以在第一局“输一回合再赢一回合......”这样无限赚钱,所以可以赢下所有比赛。如果 x\le y,则贪心地考虑,每一局先输上9回合,如果此时的钱够赢11回合,那就赢下这一局,否则就再输2回合攒钱。

D - Mr. Panda and Circles

E - Evil Forest

签到题,答案为 \sum_{i=1}^n 1.1 a_i。注意浮点误差。

F - Fair Lottery

G - Alice's Stamps

f[i][j] 表示考虑位置 [1,i],选了 j 个区间,此时在 [1,i] 中的最大覆盖长度。假设当前已经考虑完位置 [1,i],现在考虑是否覆盖位置 i+1。如果决定不覆盖位置 i+1,则有转移方程 f[i+1][j]=\max(f[i+1][j],f[i][j]);如果决定覆盖位置 i+1,则一定会选择覆盖 i+1 且右端点最大的那个区间,所以我们可以先预处理出 r_1\dots r_n,其中 r_i 表示覆盖位置 i 的区间中右端点的最大值,则有转移方程 f[r[i+1]][j+1]=\max(f[r[i+1]][j+1],f[i][j]+(r[i+1]-i))。边界条件为 f[0][0]=0,最终答案为 \max_{j=1}^k f[n][j]。总复杂度 O(n^2)

H - Equidistance

I - Inkopolis

J - Subway Chasing

差分约束求可行解板题。设 f(i) 表示从第 1 站到第 i 站所需的时间。由于站与站之间需要花费时间,所以有约束条件 f(i+1)-f(i)>0。对于每次通讯,若 A=B,C=D,则表示站 A 到站 C 恰好需要花费时间 X,即约束条件 f(C)-f(A)=X;否则有 A,D 之间花费时间严格大于 XB,C 之间花费时间严格小于 X,即约束条件 f(D)-f(A)\gt Xf(C)-f(B)\lt X。若存在负环则无解,否则求出车站间差值即为答案。

K - Knightmare

找规律题。发现在 n 大到一定程度之后,答案的差值的差值均为28。小范围暴力,大范围用公式即可。记得开int128。

Code

A - Dogs and Cages

#include <stdio.h>
#include <string.h>
#include <iostream>

using namespace std;

int T, n;

int main() {
    scanf("%d", &T);
    for (int cas = 1; cas <= T; cas++) {
        scanf("%d", &n);
        printf("Case #%d: %d\n", cas, n - 1);
    }
}

C - Rich Game

#include <stdio.h>
#include <string.h>
#include <iostream>

using namespace std;

int T, x, y, K;

int main() {
    scanf("%d", &T);
    for (int cas = 1; cas <= T; cas++) {
        scanf("%d%d%d", &x, &y, &K);
        if (x > y) {
            printf("Case #%d: %d\n", cas, K);
        } else {
            int cur = 0, ans = 0;
            for (int i = 1; i <= K; i++) {
                cur += 9 * x;
                int cost = 11 * y;
                if (cur < cost) {
                    cur += 2 * x;
                } else {
                    ans++, cur -= cost;
                }
            }
            printf("Case #%d: %d\n", cas, ans);
        }
    }
}

E - Evil Forest

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#define MAX_N 1005
#define EPS 1e-6

using namespace std;

int T, n;
int a[MAX_N];

int main() {
    scanf("%d", &T);
    for (int cas = 1; cas <= T; cas++) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            scanf("%d", a + i);
        }
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            ans += ceil(a[i] * 1.1 - EPS);
        }
        printf("Case #%d: %d\n", cas, ans);
    }
}

G - Alice's Stamps

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

using namespace std;

int T, n, m, K;
int L[MAX_N];
int R[MAX_N];
int r[MAX_N];
int f[MAX_N][MAX_N];

void chkmax(int &x, int y) {
    x = max(x, y);
}

int main() {
    scanf("%d", &T);
    for (int cas = 1; cas <= T; cas++) {
        scanf("%d%d%d", &n, &m, &K);
        for (int i = 1; i <= m; i++) {
            scanf("%d%d", L + i, R + i);
        }
        for (int i = 1; i <= n; i++) {
            r[i] = 0;
        }
        for (int i = 1; i <= m; i++) {
            for (int j = L[i]; j <= R[i]; j++) {
                r[j] = max(r[j], R[i]);
            }
        }
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= K; j++) {
                f[i][j] = 0;
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= K; j++) {
                chkmax(f[i + 1][j], f[i][j]);
                if (j < K) {
                    chkmax(f[r[i + 1]][j + 1], f[i][j] + r[i + 1] - i);
                }
            }
        }
        int ans = 0;
        for (int i = 0; i <= K; i++) {
            ans = max(ans, f[n][i]);
        }
        printf("Case #%d: %d\n", cas, ans);
    }
}

J - Subway Chasing

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

using namespace std;

struct Edge {
    int t, w;
    Edge() {}
    Edge(int _t, int _w) : t(_t), w(_w) {}
};

int T, n, m, X;
int dis[MAX_N];
int cnt[MAX_N];
bool vis[MAX_N];
vector<Edge> e[MAX_N];

void add(int x, int y, int z) {
    e[x].push_back(Edge(y, z));
}

bool spfa(int s) {
    memset(dis, 0x3f, sizeof(int) * (n + 5));
    memset(cnt, 0, sizeof(int) * (n + 5));
    memset(vis, false, sizeof(bool) * (n + 5));
    queue<int> q;
    dis[s] = 0, cnt[s]++;
    q.push(s), vis[s] = true;
    while (!q.empty()) {
        int x = q.front();
        q.pop(), vis[x] = false;
        for (int i = 0; i < e[x].size(); i++) {
            int t = e[x][i].t, w = e[x][i].w;
            if (dis[t] > dis[x] + w) {
                if (++cnt[t] > n + 1) {
                    return true;
                }
                dis[t] = dis[x] + w;
                if (!vis[t]) {
                    q.push(t), vis[t] = true;
                }
            }
        }
    }
    return false;
}

int main() {
    scanf("%d", &T);
    for (int cas = 1; cas <= T; cas++) {
        scanf("%d%d%d", &n, &m, &X);
        for (int i = 1; i <= n + 1; i++) {
            e[i].clear();
        }
        int a, b, c, d;
        for (int i = 1; i <= m; i++) {
            scanf("%d%d%d%d", &a, &b, &c, &d);
            if (a == b && c == d) {
                add(a, c, X), add(c, a, -X);
            } else {
                add(b, c, X - 1), add(d, a, -X - 1);
            }
        }
        for (int i = 1; i < n; i++) {
            add(i + 1, i, -1);
        }
        for (int i = 1; i <= n; i++) {
            add(n + 1, i, 0);
        }
        if (spfa(n + 1)) {
            printf("Case #%d: IMPOSSIBLE\n", cas);
        } else {
            printf("Case #%d:", cas);
            for (int i = 1; i < n; i++) {
                printf(" %d", dis[i + 1] - dis[i]);
            }
            printf("\n");
        }
    }
}

K - Knightmare

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <stack>
#include <set>
#include <map>
#define MAX_N 1000005
#define MAX_R 105
#define pii pair<int, int>
#define int __int128_t

using namespace std;

const int dx[] = {-1, -2, -2, -1, 1, 2, 2, 1};
const int dy[] = {-2, -1, 1, 2, 2, 1, -1, -2};

int T, n, r = 0, ans = 1;
int res[MAX_R];
set<pii> st[MAX_N];
map<int, map<int, int> > mp;

void upd(int x, int y, int i) {
    if (!mp[x][y]) {
        mp[x][y] = i;
        st[i].insert(pii(x, y));
        r = max(r, max(x, y));
        ans++;
    }
}

istream& operator>>(istream& in, int& x) {
    long long t;
    in >> t;
    x = t;
    return in;
}

ostream& operator<<(ostream& out, int x) {
    stack<signed> stk;
    while (x) {
        stk.push(x % 10);
        x /= 10;
    }
    while (!stk.empty()) {
        out << stk.top();
        stk.pop();
    }
    return out;
}

signed main() {
    ios::sync_with_stdio(false);
    st[0].insert(pii(0, 0));
    mp[0][0] = -1;
    res[0] = 1;
    for (int i = 1; i <= 20; i++) {
        for (auto p : st[i - 1]) {
            for (int j = 0; j < 8; j++) {
                int x = p.first + dx[j];
                int y = p.second + dy[j];
                upd(x, y, i);
            }
        }
        res[i] = ans;
    }
    cin >> T;
    for (int cas = 1; cas <= T; cas++) {
        cin >> n;
        if (n <= 10) {
            cout << "Case #" << cas << ": " << res[n] << endl;
        } else {
            int d = res[11] - res[10];
            int cnt = n - 10;
            int sum = (d + d + (cnt - 1) * 28) * cnt / 2;
            cout << "Case #" << cas << ": " << (res[10] + sum) << endl;
        }
    }
}
点赞

发表评论

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