Educational Codeforces Round 1

题目链接：https://codeforces.com/contest/598

A - Tricky Sum

挺有意思的一条送分题。

B - Queries on a String

题意：给一个长<=10000的字符串，然后<=300次询问，每次询问要求把[l,r]子串循环右移k<=1000000次。求最终的结果。

题解：感觉这题有个FHQTreap的解法。不过仔细想想看长度这么短，询问也这么少，直接把k模子串长度然后暴力就可以了。

char s[10005];
char tmp1[10005];
char tmp2[10005];

void test_case() {
    scanf("%s", s + 1);
    int n = strlen(s + 1), m;
    scanf("%d", &m);
    while(m--) {
        int l, r, k;
        scanf("%d%d%d", &l, &r, &k);
        k %= (r - l + 1);
        int t1top = 0, t2top = 0;
        for(int i = l; i <= r - k; ++i)
            tmp1[++t1top] = s[i];
        for(int i = r - k + 1; i <= r; ++i)
            tmp2[++t2top] = s[i];
        tmp1[t1top + 1] = '\0';
        tmp2[t2top + 1] = '\0';
        for(int i = l, k = 1; k <= t2top; ++i, ++k)
            s[i] = tmp2[k];
        for(int i = l + t2top, k = 1; k <= t1top; ++i, ++k)
            s[i] = tmp1[k];
    }
    puts(s + 1);
}

D - Igor In the Museum

一个挺明显的挖油井问题，要数某个白格连通块中与白格接壤的黑格的不同面的数量。假如去掉同一个黑格的不同面，只需要在cntwall前判断一下有没有被当前白色连通块vis过，然后涂上这个连通块特有的颜色。

int di[4] = {0, 0, -1, 1};
int dj[4] = {-1, 1, 0, 0};

char g[1005][1005];
int vis[1005][1005];
int cnt[1005][1005];
queue<pii> Q1, Q2;

void bfs(int si, int sj, int color) {
    vis[si][sj] = color;
    Q1.push({si, sj});
    Q2.push({si, sj});
    int cntwall = 0;
    while(!Q1.empty()) {
        int ui = Q1.front().first, uj = Q1.front().second;
        Q1.pop();
        for(int k = 0; k < 4; ++k) {
            int vi = ui + di[k];
            int vj = uj + dj[k];
            if(g[vi][vj] == '*')
                ++cntwall;
            if(g[vi][vj] == '.' && vis[vi][vj] == 0) {
                vis[vi][vj] = color;
                Q1.push({vi, vj});
                Q2.push({vi, vj});
            }
        }
    }
    while(!Q2.empty()) {
        int ui = Q2.front().first, uj = Q2.front().second;
        Q2.pop();
        cnt[ui][uj] = cntwall;
    }
}

void test_case() {
    int n, m, q;
    scanf("%d%d%d", &n, &m, &q);
    for(int i = 1; i <= n; ++i)
        scanf("%s", g[i] + 1);
    int cntcolor = 0;
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= m; ++j) {
            if(g[i][j] == '.' && vis[i][j] == 0)
                bfs(i, j, ++cntcolor);
        }
    }
    while(q--) {
        int qi, qj;
        scanf("%d%d", &qi, &qj);
        printf("%d\n", cnt[qi][qj]);
    }
}

*E - Chocolate Bar

题意：一块n*m的格子巧克力（其中n<=30且m<=30），要恰好吃k(<=min(n*m,50))块巧克力，已知每次可以沿一条直的格子边界掰断巧克力，代价是长度的平方。求最小代价。

题解：一开始以为是枚举k的因数，发现过不了第3个样例，然后猜测要多一些零头，注意这些零头未必只有1格宽。观察到掰断之后的小巧克力的代价，与掰断前的巧克力无关，是个相似结构的子问题，设计一个dp算法，然后卡一堆常数解决。

ll dp[31][31][51];

void test_case() {
    memset(dp, LINF, sizeof(dp));
    for(int a = 0; a <= 30; ++a) {
        for(int b = 0; b <= 30; ++b) {
            dp[a][b][0] = 0;
            if(a * b <= 50)
                dp[a][b][a * b] = 0;
        }
    }
    for(int a = 1; a <= 30; ++a) {
        for(int b = 1; b <= a; ++b) {
            int ck = min(a * b - 1, 50);
            for(int k = 0; k <= ck; ++k) {
                ll tmp = dp[a][b][k];
                for(int a1 = 1; a1 < a; ++a1) {
                    int cs = min(k, a1 * b);
                    for(int s = 0, t = b * b; s <= cs && tmp > t; ++s) {
                        tmp = min(tmp, dp[a1][b][s] + dp[a - a1][b][k - s] + t);
                        tmp = min(tmp, dp[a1][b][k - s] + dp[a - a1][b][s] + t);
                    }
                }
                for(int b1 = 1; b1 < b; ++b1) {
                    int cs = min(k, b1 * a);
                    for(int s = 0, t = a * a; s <= cs && tmp > t; ++s) {
                        tmp = min(tmp, dp[a][b1][s] + dp[a][b - b1][k - s] + t);
                        tmp = min(tmp, dp[a][b1][k - s] + dp[a][b - b1][s] + t);
                    }
                }
                dp[a][b][k] = min(dp[a][b][k], tmp);
                dp[b][a][k] = min(dp[b][a][k], tmp);
                //printf("dp[%d][%d][%d]=%lld\n", a, b, k, dp[a][b][k]);
            }
        }
    }
    int t;
    scanf("%d", &t);
    while(t--) {
        int n, m, k;
        scanf("%d%d%d", &n, &m, &k);
        printf("%lld\n", dp[n][m][k]);
    }
}

Educational Codeforces Round 1

原文：https://www.cnblogs.com/KisekiPurin2019/p/12459840.html