【XJTU 2020暑期集训】Day4 - 2019 CCPC 哈尔滨站

A - Artful Paintings

显然答案满足二分性质,所以先二分答案 x,原问题就转化成了:染色 x 个格子,能否满足所有条件。

考虑差分约束。设 f(x) 表示 1\dots x 中的染色格子个数,特别地,f(0)=0。由于每个格子只能染或不染,所以有约束条件 f(x+1)-f(x)\in [0,1]。由于总染色数为 x,所以有约束条件 f(n)-f(0)=x。对于第一类条件,约束为 f(r)-f(l-1)\gt k;对于第二类条件,约束为 f(r)-f(l-1)\lt x-k。跑一遍spfa判负环,如果没有负环,则当前答案可行。

需要注意的是,由于有约束条件 f(x+1)-f(x)\in [0,1],构成的图一定联通,不需要建立新起始点,直接从 dis[0]=0 开始即可。另外有剪枝:当出现 dis[i]\lt 0 时,一定无解。

B - Binary Numbers

题意有点难懂,先翻译下:将 0\dots 2^m-1 切成 n 个区间 [L_i,R_i]。一个合法的序列 a_1\dots a_n 满足 a_i\in[L_i,R_i] 且对于每个 i\forall k\in[L_i,R_i],\mathrm{LCP}(a_i,k)\ge\mathrm{LCP}(a_j,k),其中 j=1\dots n\mathrm{LCP}(x,y) 表示 m 位二进制数 x,y 的最长公共前缀。一个序列的价值定义为 V(a)=\prod_{i=1}^n a_i。现在让你求出所有合法序列的价值之和。

可以发现性质:对于一个数 x,如果 x\lt y,则 y 越小 \mathrm{LCP}(x,y) 越大;如果 x\gt y,则 y 越大 \mathrm{LCP}(x,y) 越大。所以在决定 a_i 时只需要考虑 a_{i-1}a_{i+1} 是否满足这两个条件:\mathrm{LCP}(a_i,L_i)\ge\mathrm{LCP}(a_{i-1},L_i)\mathrm{LCP}(a_i,R_i)\ge\mathrm{LCP}(a_{i+1},R_i)

f[i][j][k] 表示已经定下了 a_1\dots a_i,且 \mathrm{LCP}(a_i,L_{i+1})=j,\mathrm{LCP}(a_i,R_i)=k 时的合法序列价值总和。枚举 a_i 的值并计算出当前的 j,k 的值,则 f[i][j][k] 可以由 f[i-1][j'][k'] 转移而来,其中 j'\in[0,\mathrm{LCP}(a_i,L_i)],k'\in[\mathrm{LCP}(a_i,R_{i-1}),m],即转移方程 f[i][j][k]=\sum_{i=L_i}^{R_i}f[i-1][j'][k']\cdot a_i。边界条件为 f[0][0][m]=1,\text{others}=0,最终答案为 \sum_{k=0}^m f[n][0][k]。总复杂度 O(2^m\cdot m)

C - Competition in Swiss-system

D - Driverless Car

E - Exchanging Gifts

设最终序列中,数量最多的一种礼物的数量为 x,其余的礼物总数为 y。若 x\le y,则所有人都可以快乐,否则至少会有 x-y 个人不快乐。所以现在就是要求最终序列中最多的礼物个数,以及礼物总数。

最终的 s_n 一定可以写成 s_n=\sum a_{k_i}s_{k_i} 的形式,其中 \lbrace k_i\rbrace 表示直接给出的序列的编号。若有 s_i=s_j+s_k 则建边 j\rightarrow ik\rightarrow i,那么这样就构成了一个在数轴上的DAG,且 a_i 就等于从点 i 到点 n 的路径条数,从后往前dp即可。总复杂度 O(n\log n),这样的复杂度需要卡常,用了unordered_map和fread就过了。

F - Fixing Banners

签到题,暴力即可。

G - Game Store

H - Highway Buses

I - Interesting Permutation

首先,h 一定非严格单增,且一定有 h_1=0,h_n=n-1,否则无解。

然后考虑如何生成一个排列。在 s_1\dots s_n 这些空位上,依次填入 1\dots n,若 s_i=j,则表示排列的第 j 个数 p_j 等于 i。显然 s_1\dots s_n 为一个排列,且 sp 为一一对应的关系。那么原问题就是问你有多少个这样的排列 s,使得由 s 生成的排列 p 满足给定序列 h

考虑依次填入 1\dots n 生成合法的 s 的过程:首先填入1,且当前方案数为1。之后,当 i 应该被填入时,如果 h_{i-1}\lt h_i,则 i 会成为当前填入数字的最大值或最小值,所以当前答案乘2,并新增 h_i-h_{i-1}-1 个空位;如果 h_{i-1}=h_i,则 i 只能填在原有的空位中,所以当前答案乘上空位数,并减少一个空位,若原本没有空位,则无解。总复杂度 O(n)

J - Justifying the Conjecture

n\le 5 时显然无解。当 n\ge 6 时,若 n 为偶数,则可分解为 (n-2)+2;若 n 为奇数,则可分解为 (n-3)+3,均为合数加质数的形式。

K - Keeping Rabbits

由于每只兔子抢到萝卜的概率是根据自身体重分配的,所以每一步之后每只兔子的期望体重之比不变。另外,最终兔子的总重一定为初始总重加上萝卜的数量。所以每只兔子的最终体重就是最终总重按照每只兔子初始重量分配。

L - LRU Algorithm

使用链表 O(n) 模拟出容量无限制时的情况,对于每一步模拟之后,O(n) 统计每个前缀的hash值。对于每个询问,先计算出该询问的hash,然后 O(n) 遍历每步模拟之后,对应长度的前缀的hash是否等于询问的hash。总复杂度 O(n^2+nm)

Code

A - Artful Paintings

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

using namespace std;

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

int T, n, m1, m2;
int L[2][MAX_M];
int R[2][MAX_M];
int K[2][MAX_M];
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 false;
                }
                dis[t] = dis[x] + w;
                if (dis[t] < 0) {
                    return false;
                }
                if (!vis[t]) {
                    q.push(t), vis[t] = true;
                }
            }
        }
    }
    return true;
}

bool check(int x) {
    for (int i = 0; i <= n + 1; i++) {
        e[i].clear();
    }
    for (int i = 0; i < n; i++) {
        add(i, i + 1, 1);
        add(i + 1, i, 0);
    }
    add(0, n, x), add(n, 0, -x);
    for (int i = 1; i <= m1; i++) {
        add(R[0][i], L[0][i] - 1, -K[0][i]);
    }
    for (int i = 1; i <= m2; i++) {
        add(L[1][i] - 1, R[1][i], x - K[1][i]);
    }
    return spfa(0);
}

int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d%d", &n, &m1, &m2);
        for (int i = 1; i <= m1; i++) {
            scanf("%d%d%d", L[0] + i, R[0] + i, K[0] + i);
        }
        for (int i = 1; i <= m2; i++) {
            scanf("%d%d%d", L[1] + i, R[1] + i, K[1] + i);
        }
        if (check(0)) {
            printf("0\n");
            continue;
        }
        int l = 0, r = n;
        while (r - l > 1) {
            int m = (l + r) >> 1;
            if (check(m)) {
                r = m;
            } else {
                l = m;
            }
        }
        printf("%d\n", r);
    }
}

B - Binary Numbers

#include <iostream>
#include <stdio.h>
#include <string.h>
#define MAX_N 140000
#define MAX_M 20
#define MOD 100000007
#define int long long

using namespace std;

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

int getlcp(int x, int y) {
    if (x >= (1 << m) || y >= (1 << m)) {
        return 0;
    }
    int ans = 0;
    for (int i = m - 1; i >= 0; i--) {
        if (((x >> i) & 1) != ((y >> i) & 1)) {
            break;
        }
        ans++;
    }
    return ans;
}

signed main() {
    scanf("%lld", &T);
    while (T--) {
        scanf("%lld%lld", &m, &n);
        for (int i = 1; i <= n; i++) {
            scanf("%lld%lld", L + i, R + i);
        }
        L[n + 1] = R[0] = (1 << m);
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                for (int k = 0; k <= m; k++) {
                    f[i][j][k] = 0;
                }
            }
        }
        f[0][0][m] = 1;
        for (int i = 1; i <= n; i++) {
            for (int t = L[i]; t <= R[i]; t++) {
                int nj = getlcp(t, L[i + 1]), nk = getlcp(t, R[i]);
                int mj = getlcp(t, L[i]), mk = getlcp(t, R[i - 1]);
                for (int j = 0; j <= mj; j++) {
                    for (int k = mk; k <= m; k++) {
                        f[i][nj][nk] = (f[i][nj][nk] + f[i - 1][j][k] * t) % MOD;
                    }
                }
            }
        }
        int ans = 0;
        for (int k = 0; k <= m; k++) {
            ans = (ans + f[n][0][k]) % MOD;
        }
        printf("%lld\n", ans);
    }
}

E - Exchanging Gifts

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <unordered_map>
#define MAX_N 1000005
#define LL long long

using namespace std;

char B[1 << 26], *S = B;
int read() {
    for (; *S < '-'; S++)
        ;
    register int x = *S++ - '0';
    for (; *S >= '0'; x = (x << 3) + (x << 1) + *S++ - '0')
        ;
    return x;
}
char U[1 << 26], *O = U, stk[20];
#define PuT(b)                                  \
    register signed i = 0;                      \
    for (; b; stk[++i] = x % 10 + '0', x /= 10) \
        ;                                       \
    for (; i; *O++ = stk[i--])                  \
        ;
void pri(register int x) {
    if (!x)
        *O++ = '0';
    else {
        PuT(x)
    };
}
void pr9(register int x) { PuT(i < 9); }
#define MoD 1000000000
#define pr(x, c) (x < 0 ? * O++ = '-', x = -x : 1, x >= MoD ? pri(x / MoD), pr9(x % MoD) : pri(x), *O++ = c)

int T, n;
int deg[MAX_N];
LL cnt[MAX_N];
bool flag[MAX_N];
vector<int> e[MAX_N];
unordered_map<int, int> mp[MAX_N];
unordered_map<int, LL> mmp;

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

void getcnt() {
    cnt[n] = 1;
    for (int i = n - 1; i >= 1; i--) {
        for (int j = 0; j < e[i].size(); j++) {
            int t = e[i][j];
            cnt[i] += cnt[t];
        }
    }
}

LL getans() {
    for (int i = 1; i <= n; i++) {
        if (flag[i]) {
            for (auto it = mp[i].begin(); it != mp[i].end(); it++) {
                mmp[it->first] += it->second * cnt[i];
            }
        }
    }
    LL mx = 0, sum = 0;
    for (auto it = mmp.begin(); it != mmp.end(); it++) {
        mx = max(mx, it->second);
        sum += it->second;
    }
    if (mx <= sum - mx) {
        return sum;
    }
    return (sum - mx) << 1LL;
}

signed main() {
    fread(B, 1, 1 << 26, stdin);
    T = read();
    while (T--) {
        n = read();
        for (int i = 1; i <= n; i++) {
            mp[i].clear();
            e[i].clear();
            deg[i] = cnt[i] = 0;
            flag[i] = false;
        }
        mmp.clear();
        int op, x, y;
        for (int i = 1; i <= n; i++) {
            op = read();
            if (op == 1) {
                x = read();
                for (int j = 1; j <= x; j++) {
                    y = read();
                    mp[i][y]++;
                }
                flag[i] = true;
            } else {
                x = read(), y = read();
                add(x, i), add(y, i);
            }
        }
        getcnt();
        LL ans = getans();
        printf("%lld\n", ans);
    }
}

F - Fixing Banners

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define MAX_N 10
#define MAX_A 30

using namespace std;

int T;
int cnt[MAX_N][MAX_A];
string s[MAX_N];

void solve(const string &s, int x) {
    for (int i = 0; i < s.size(); i++) {
        cnt[x][s[i] - 'a']++;
    }
}

void work() {
    for (int i = 1; i <= 6; i++) {
        cin >> s[i];
    }
    memset(cnt, 0, sizeof(cnt));
    for (int i = 1; i <= 6; i++) {
        solve(s[i], i);
    }
    int p[] = {1, 2, 3, 4, 5, 6};
    char c[] = "harbin";
    do {
        bool flag = true;
        for (int i = 0; i < 6; i++) {
            if (!cnt[p[i]][c[i] - 'a']) {
                flag = false;
                break;
            }
        }
        if (flag) {
            cout << "Yes" << endl;
            return;
        }
    } while (next_permutation(p, p + 6));
    cout << "No" << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin >> T;
    while (T--) {
        work();
    }
}

I - Interesting Permutation

#include <iostream>
#include <stdio.h>
#include <string.h>
#define MAX_N 100005
#define MOD 1000000007
#define int long long

using namespace std;

int T, n;
int h[MAX_N];

bool ok() {
    if (h[1] != 0 || h[n] != n - 1) {
        return false;
    }
    for (int i = 1; i < n; i++) {
        if (h[i] > h[i + 1]) {
            return false;
        }
    }
    return true;
}

signed main() {
    scanf("%lld", &T);
    while (T--) {
        scanf("%lld", &n);
        for (int i = 1; i <= n; i++) {
            scanf("%lld", h + i);
        }
        if (!ok()) {
            printf("0\n");
            continue;
        }
        int ans = 1, cnt = 0;
        for (int i = 1; i < n; i++) {
            if (h[i] == h[i + 1]) {
                if (!cnt) {
                    ans = 0;
                    break;
                }
                ans = ans * cnt % MOD;
                cnt--;
            } else {
                ans = (ans << 1LL) % MOD;
                cnt += h[i + 1] - h[i] - 1;
            }
        }
        printf("%lld\n", ans);
    }
}

J - Justifying the Conjecture

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

using namespace std;

int T, n;

int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        if (n <= 5) {
            printf("-1\n");
        } else {
            if (n & 1) {
                printf("%d %d\n", 3, n - 3);
            } else {
                printf("%d %d\n", 2, n - 2);
            }
        }
    }
}

K - Keeping Rabbits

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

using namespace std;

int T, n, K;
int w[MAX_N];

signed main() {
    scanf("%lld", &T);
    while (T--) {
        scanf("%lld%lld", &n, &K);
        for (int i = 1; i <= n; i++) {
            scanf("%lld", w + i);
        }
        int sum = 0;
        for (int i = 1; i <= n; i++) {
            sum += w[i];
        }
        for (int i = 1; i <= n; i++) {
            double res = (double)(sum + K) * w[i] / sum;
            printf("%.8f ", res);
        }
        printf("\n");
    }
}

L - LRU Algorithm

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <list>
#define MAX_N 5005
#define MOD1 19260817
#define MOD2 19491001
#define BASE 233
#define lit list<int>::iterator
#define pii pair<int, int>
#define int long long

using namespace std;

int T, n, m, q;
int a[MAX_N];
lit its[MAX_N];
pii h[MAX_N][MAX_N];
list<int> ls;

void add(int x) {
    if (its[x] != ls.end()) {
        ls.erase(its[x]);
    }
    ls.push_front(x);
    its[x] = ls.begin();
}

void query() {
    scanf("%lld", &m);
    int x, len = 0, hash1 = 0, hash2 = 0;
    for (int i = 1; i <= m; i++) {
        scanf("%lld", &x);
        if (x) {
            hash1 = (hash1 * BASE + x) % MOD1;
            hash2 = (hash2 * BASE + x) % MOD2;
            len++;
        }
    }
    for (int i = 1; i <= n; i++) {
        if (h[i][len] == pii(hash1, hash2)) {
            printf("Yes\n");
            return;
        }
    }
    printf("No\n");
}

void work() {
    scanf("%lld%lld", &n, &q);
    ls.clear();
    for (int i = 1; i <= n; i++) {
        its[i] = ls.end();
    }
    for (int i = 1; i <= n; i++) {
        scanf("%lld", a + i);
    }
    for (int i = 1; i <= n; i++) {
        add(a[i]);
        int hash1 = 0, hash2 = 0;
        int pos = 1;
        for (lit it = ls.begin(); it != ls.end(); it++, pos++) {
            hash1 = (hash1 * BASE + (*it)) % MOD1;
            hash2 = (hash2 * BASE + (*it)) % MOD2;
            h[i][pos] = pii(hash1, hash2);
        }
    }
    while (q--) {
        query();
    }
}

signed main() {
    scanf("%lld", &T);
    while (T--) {
        work();
    }
}
点赞

发表评论

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