Codeforces Round #786 (Div. 3)

Author：我不会玩锐雯
发布时间：August 1, 2022
741views
No comments
11418字数
Categories： ACM技能点

比赛链接：https://codeforces.com/contest/1674

A. Number Transformation

题意：给定$1 \leq x,y \leq 100$，求一对正整数$a,b$满足$x \times b^a = y$。

解法：因为$x,y$的范围比较小，直接枚举所有可能的$a,b$组合。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 1e6 + 117;

int T;
int x, y;
int ans[107];
int main() {
    for(int b = 1; b <= 100; b++) {
        int num = 1;
        for(int a = 1; a <= 10; a++) {
            num *= b;
            if(num > 100) break;
            ans[num] = b * 1000 + a;
        }
    }
    scanf("%d", &T);
    while(T--) {
        scanf("%d%d", &x, &y);
        if(y % x != 0) {
            puts("0 0");
            continue;
        }
        printf("%d %d\n", ans[y / x] % 1000, ans[y / x] / 1000);
    }
    return 0;
}

B. Dictionary

题意：定义长度为2的字符串有以下映射规则：$ab=1$、$ac=2$...$az=25$、$ba=26$、$bc=27$...$zx=649$、$zy=650$。现给出字符串，要求输出对应的序号。

解法：字符串限制只有两位，提前枚举好每个字符串对应的序号即可。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 1e6 + 117;

int T;
string s;
map<string, int> ma;
int main() {
    int cnt = 0;
    for(int i = 0; i < 26; i++) {
        for(int j = 0; j < 26; j++) {
            if(i == j) continue;
            cnt++;
            s = "";
            s.append(1, 'a' + i);
            s.append(1, 'a' + j);
            ma[s] = cnt;
        }
    }
    scanf("%d", &T);
    while(T--) {
        cin >> s;
        cout << ma[s] << '\n';
    }
    return 0;
}

C. Infinite Replacement

题意：给定一个只由字符$a$构成的字符串$s$，和一个只由小写字母构成的字符串$t$，现在可以将$s$中的字符$a$替换成$t$，问最多可以得到多少种不同的字符串？

解法：

当$t$只有一个字符$a$时，无论怎么替换都只能得到原字符串$s$。
当$t$长度大于1且包含字符$a$时，可以不断的替换得到无限种的字符串$s$。
当$t$长度大于1且不包含字符$a$时，可以得到的字符串种类为$2^n$，$n$为字符串$s$的长度。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 1e6 + 117;

int T;
char s[77], t[77];
LL solve() {
    int lent = strlen(t);
    if(lent == 1 && t[0] == 'a') {
        return 1;
    }
    for(int i = 0; i < lent; i++) {
        if(t[i] == 'a') return -1;
    }

    LL ans = 1;
    int lens = strlen(s);
    for(int i = 0; i < lens; i++) {
        ans *= 2;
    }
    return ans;
}
int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%s%s", s, t);
        printf("%lld\n", solve());
    }
    return 0;
}

D. A-B-C Sort

题意：给定长度为$n(1 \leq n \leq 2 \times 10^5)$的数组a。第一步：当a不为空时，从a中取出最后一个元素并将其移动到数组b的中间。如果b当前为奇数长度，可以选择：将a中的元素放在b的中间元素的左侧或右侧。第二步：当b不为空时，从b中取出中间元素并将其移动到数组c的末尾。如果b当前具有偶数长度，您可以选择取两个中间元素中的哪一个。问能不能通过这两步操作得到的数组c是非递减的？

解法：经过两步操作，每一对$(a_n-2i-1,a_n-2i)$总会被移动到$(c_n-2i-1,c_n-2i)$或者$(c_n-2i,c_n-2i-1)$。遍历一遍数组把每一对组合排好序并检查整个数组是否有序即可。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 1e6 + 117;

int T;
int n;
int a[MAXN];
bool solve() {
    for(int i = 1 + n % 2; i < n; i += 2) {
        if(a[i] < a[i - 1]) swap(a[i], a[i - 1]);
        if(i - 2 >= 0 && a[i - 1] < a[i - 2]) {
            return false;
        }
    }
    return true;
}
int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        for(int i = 0; i < n; i++) scanf("%d", &a[i]);
        puts(solve() ? "YES" : "NO");
    }
    return 0;
}

E. Breaking the Wall

题意：给定$n(2 \leq n \leq 2 \times 10^5)$堵墙，每堵墙都有对应的耐久值。每次选择一个目标位置进行操作，目标位置耐久度-2，目标相邻的位置耐久度-1。对每个位置可以进行不限次数的操作，问最少多少次操作可以使得两堵墙耐久度不高于0。

解法：

第一种情况：每次都选择要打破的墙为中心进行操作。这时应该选择耐久度最低的两面墙，设耐久度最低的墙为$x$，次低的墙为$y$，所需要的次数为$\lceil \frac{x}{2} \rceil + \lceil \frac{y}{2} \rceil$。
第二种情况：要打破的墙相隔一个单位，假设为$a_i$和$a_{i+2}$。这时可以选择对$a_{i+1}$进行操作，对目标墙耐久度各-1，也可以选择其中一个目标墙操作，对目标墙耐久度-2。这时每次的操作总能对目标墙总体耐久度-2，那么所需要的次数为$\lceil \frac{a_i + a_{i+2}}{2} \rceil$。
第三种情况：要打破的墙相邻，假设为$a_i$和$a_{i+1}$，且$a_i \ge a_{i+1}$。
- 如果$a_i \ge a_{i+1} \times 2$，那么只需要一直选择$a_i$为目标操作即可，所需要的次数为$\lceil \frac{a_i}{2} \rceil$。
- 如果$a_i \lt a_{i+1} \times 2$，先选择$a_i$为目标操作$a_i-a_{i-1}$次，这时两个目标墙耐久度都剩余$2 \times a_{i-1} - a_i$。再选择两个目标墙进行操作，每次的操作总能对目标墙总体耐久度-3，那么所需要的次数为$a_i-a_{i-1} + \lceil \frac{2 \times a_{i-1} - a_i + 2 \times a_{i-1} - a_i}{3} \rceil$。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 1e6 + 117;

int n;
int a[MAXN];
int ans = INF;
void solve1(int x, int y) {
    if(x < y) swap(x, y);
    if(x >= y * 2) ans = min(ans, (x + 1) / 2);
    else ans = min(ans, x - y + ((2 * y - x) * 2 + 2) / 3);
}
void solve2(int x, int y) {
    ans = min(ans, (x + y + 1) / 2);
}
int main() {
    scanf("%d", &n);
    int minimum = INF, cmini = INF;
    for(int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
        if(i >= 1) solve1(a[i - 1], a[i]);
        if(i >= 2) solve2(a[i - 2], a[i]);
        if(a[i] < minimum) {
            cmini = minimum;
            minimum = a[i];
        } else if(a[i] < cmini) cmini = a[i];
    }
    ans = min(ans, (minimum + 1) / 2 + (cmini + 1) / 2);
    printf("%d\n", ans);
    return 0;
}

F. Desktop Rearrangement

题意：给定一个二维矩阵，每次操作可以将任意两个方格交换位置。现在有多次询问，每次询问给出一个坐标，如果坐标上是*则替换成.，反之亦然。对于每次询问求出最少多少次操作可以把所有的$*$移到最左边(从左到右、从上到下)。

解法一：定义矩阵当前总共有$sum$个*，前$sum$个格子(从左到右、从上到下)有$cnt$个*，那么需要操作的次数为$sum-cnt$。将二维矩阵按列方向转化为一维，问题转换为单点修改区间求和，使用树状数组维护即可。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 1e6 + 117;

int n, m, q;
int i, j, sum = 0;
int tree[MAXN];
int lowbit(int x) {
    return x & -x;
}
void update(int p, int x) {
    while(p < MAXN) {
        tree[p] += x;
        p += lowbit(p);
    }
}
int query(int p) {
    int sum = 0;
    while(p) {
        sum += tree[p];
        p -= lowbit(p);
    }
    return sum;
}
char s[1077][1077];
int main() {
    scanf("%d%d%d", &n, &m, &q);
    for(i = 0; i < n; i++) scanf("%s", s[i]);

    for(j = 0; j < m; j++) {
        for(i = 0; i < n; i++) {
            if(s[i][j] == '*') {
                sum++;
                update(j * n + i + 1, 1);
            }
        }
    }

    while(q--) {
        scanf("%d%d", &i, &j);
        i--, j--;
        if(s[i][j] == '*') {
            sum--;
            s[i][j] = '.';
            update(j * n + i + 1, -1);
        } else {
            sum++;
            s[i][j] = '*';
            update(j * n + i + 1, 1);
        }
        printf("%d\n", sum - query(sum));
    }
    return 0;
}

解法二：直接考虑每次查询对结果造成的影响。定义矩阵当前总共有$sum$个*，前$sum$个格子(从左到右、从上到下)有$cnt$个*，那么需要操作的次数为$sum-cnt$。

如果当前查询使$sum+1$，则$cnt$的值受新增加进前$sum$个的格子和查询修改的格子两者共同影响。
如果当前查询使$sum-1$，则$cnt$的值受被移出前$sum$个的格子和查询修改的格子两者共同影响。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 1e6 + 117;

int n, m, q;
int sum = 0, cnt = 0;
char s[1077][1077];
int main() {
    scanf("%d%d%d", &n, &m, &q);
    for(int i = 0; i < n; i++) {
        scanf("%s", s[i]);
        for(int j = 0; j < m; j++) {
            if(s[i][j] == '*') sum++;
        }
    }

    for(int j = 0; j < m; j++) {
        if(j * n  + 1 > sum) break;
        for(int i = 0; i < n; i++) {
            if(j * n + i + 1 > sum) break;
            if(s[i][j] == '*') cnt++;
        }
    }

    int x, y;
    while(q--) {
        scanf("%d%d", &x, &y);
        x--, y--;
        if(s[x][y] == '*') {
            sum--;
            if(s[sum % n][sum / n] == '*') cnt--;
            if(y * n + x + 1 <= sum) cnt--;
            s[x][y] = '.';
        } else {
            if(s[sum % n][sum / n] == '*') cnt++;
            sum++;
            if(y * n + x + 1 <= sum) cnt++;
            s[x][y] = '*';
        }
        printf("%d\n", sum - cnt);
    }
    return 0;
}

G. Remove Directed Edges

题意：给定一个无环、无重边的有向图，有$n(1 \leq n \leq 2 \times 10^5)$个顶点、$m(0 \leq m \leq 2 \times 10^5)$条边。先删除一些边，使得所有顶点的入度和出度都减小或者为0。再选择一个集合$s$包含一些顶点，使得集合中任意两个顶点$u$、$v$存在由$u$到$v$或者由$v$到$u$的路径。求集合$s$的最大大小？

解法：对于集合$s$，存在顶点$head$和顶点$tail$，有一条由$head$到$tail$的路径，集合$s$中的所有顶点都在这条路径上。那么对于整张有向图，删除不在$head$到$tail$路径上的所有边是可以得到集合$s$的。现在问题由寻找一个集合$s$变成寻找一条路径，且路径具有以下的特点。

路径起始顶点$head$的出度$out[head] \ge 2$。
路径中间顶点$i$的入度$in[i] \ge 2$、出度$out[i] \ge 2$。
路径结束顶点$tail$的入度$in[tail] \ge 2$。

定义$dp[i]$表示顶点$i$为中间顶点的路径往后最长有多长，则有$dp[i]=max(dp[j])+1$，其中顶点$j$是顶点$i$的儿子。记忆化搜索一下可以得到所有的$dp[i]$，然后枚举一下所有可能的起始顶点选择最长的路径就是集合$s$的顶点。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 1e6 + 117;

int n, m;
int in[MAXN], out[MAXN];
int head[MAXN], tot;
struct Edge {
    int v;
    int ne;
} edge[MAXN];
void addEdge(int u, int v) {
    edge[tot].v = v;
    edge[tot].ne = head[u];
    head[u] = tot++;
}
int dp[MAXN];//非头结点的长度
int dfs(int i) {
    if(dp[i] != 0) return dp[i];
    if(in[i] >= 2) {
        if(out[i] >= 2) {//中间结点
            for(int j = head[i]; j != -1; j = edge[j].ne) {
                dp[i] = max(dp[i], dfs(edge[j].v) + 1);
            }
        } else {//尾结点
            dp[i] = 1;
        }
    }
    return dp[i];
}
int main() {
    scanf("%d%d", &n, &m);
    for(int i = 0; i <= n; i++) {
        dp[i] = 0;
        head[i] = -1;
        in[i] = out[i] = 0;
    }

    while(m--) {
        int u, v;
        scanf("%d%d", &u, &v);
        addEdge(u, v);
        in[v]++;
        out[u]++;
    }

    int ans = 1;
    for(int i = 1; i <= n; i++) {
        if(out[i] >= 2) {
            for(int j = head[i]; j != -1; j = edge[j].ne) {
                ans = max(ans, dfs(edge[j].v) + 1);
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}

版权属于：小影
本文链接：http://kindkidll.com/index.php/archives/193/
所有原创文章采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可。您可以自由的转载和修改，但请务必注明文章来源并且不可用于商业目的。

Last modification：August 1st, 2022 at 08:51 pm

如果觉得我的文章对你有用，请随意赞赏

Codeforces Round #786 (Div. 3)

我不会玩锐雯 • 2022 年 08 月 01 日

比赛链接：https://codeforces.com/contest/1674

A. Number Transformation

题意：给定$1 \leq x,y \leq 100$，求一对正整数$a,b$满足$x \times b^a = y$。

解法：因为$x,y$的范围比较小，直接枚举所有可能的$a,b$组合。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 1e6 + 117;

int T;
int x, y;
int ans[107];
int main() {
    for(int b = 1; b <= 100; b++) {
        int num = 1;
        for(int a = 1; a <= 10; a++) {
            num *= b;
            if(num > 100) break;
            ans[num] = b * 1000 + a;
        }
    }
    scanf("%d", &T);
    while(T--) {
        scanf("%d%d", &x, &y);
        if(y % x != 0) {
            puts("0 0");
            continue;
        }
        printf("%d %d\n", ans[y / x] % 1000, ans[y / x] / 1000);
    }
    return 0;
}

B. Dictionary

题意：定义长度为2的字符串有以下映射规则：$ab=1$、$ac=2$...$az=25$、$ba=26$、$bc=27$...$zx=649$、$zy=650$。现给出字符串，要求输出对应的序号。

解法：字符串限制只有两位，提前枚举好每个字符串对应的序号即可。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 1e6 + 117;

int T;
string s;
map<string, int> ma;
int main() {
    int cnt = 0;
    for(int i = 0; i < 26; i++) {
        for(int j = 0; j < 26; j++) {
            if(i == j) continue;
            cnt++;
            s = "";
            s.append(1, 'a' + i);
            s.append(1, 'a' + j);
            ma[s] = cnt;
        }
    }
    scanf("%d", &T);
    while(T--) {
        cin >> s;
        cout << ma[s] << '\n';
    }
    return 0;
}

C. Infinite Replacement

解法：

当$t$只有一个字符$a$时，无论怎么替换都只能得到原字符串$s$。
当$t$长度大于1且包含字符$a$时，可以不断的替换得到无限种的字符串$s$。
当$t$长度大于1且不包含字符$a$时，可以得到的字符串种类为$2^n$，$n$为字符串$s$的长度。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 1e6 + 117;

int T;
char s[77], t[77];
LL solve() {
    int lent = strlen(t);
    if(lent == 1 && t[0] == 'a') {
        return 1;
    }
    for(int i = 0; i < lent; i++) {
        if(t[i] == 'a') return -1;
    }

    LL ans = 1;
    int lens = strlen(s);
    for(int i = 0; i < lens; i++) {
        ans *= 2;
    }
    return ans;
}
int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%s%s", s, t);
        printf("%lld\n", solve());
    }
    return 0;
}

D. A-B-C Sort

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 1e6 + 117;

int T;
int n;
int a[MAXN];
bool solve() {
    for(int i = 1 + n % 2; i < n; i += 2) {
        if(a[i] < a[i - 1]) swap(a[i], a[i - 1]);
        if(i - 2 >= 0 && a[i - 1] < a[i - 2]) {
            return false;
        }
    }
    return true;
}
int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        for(int i = 0; i < n; i++) scanf("%d", &a[i]);
        puts(solve() ? "YES" : "NO");
    }
    return 0;
}

E. Breaking the Wall

解法：

第一种情况：每次都选择要打破的墙为中心进行操作。这时应该选择耐久度最低的两面墙，设耐久度最低的墙为$x$，次低的墙为$y$，所需要的次数为$\lceil \frac{x}{2} \rceil + \lceil \frac{y}{2} \rceil$。
第二种情况：要打破的墙相隔一个单位，假设为$a_i$和$a_{i+2}$。这时可以选择对$a_{i+1}$进行操作，对目标墙耐久度各-1，也可以选择其中一个目标墙操作，对目标墙耐久度-2。这时每次的操作总能对目标墙总体耐久度-2，那么所需要的次数为$\lceil \frac{a_i + a_{i+2}}{2} \rceil$。
第三种情况：要打破的墙相邻，假设为$a_i$和$a_{i+1}$，且$a_i \ge a_{i+1}$。
- 如果$a_i \ge a_{i+1} \times 2$，那么只需要一直选择$a_i$为目标操作即可，所需要的次数为$\lceil \frac{a_i}{2} \rceil$。
- 如果$a_i \lt a_{i+1} \times 2$，先选择$a_i$为目标操作$a_i-a_{i-1}$次，这时两个目标墙耐久度都剩余$2 \times a_{i-1} - a_i$。再选择两个目标墙进行操作，每次的操作总能对目标墙总体耐久度-3，那么所需要的次数为$a_i-a_{i-1} + \lceil \frac{2 \times a_{i-1} - a_i + 2 \times a_{i-1} - a_i}{3} \rceil$。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 1e6 + 117;

int n;
int a[MAXN];
int ans = INF;
void solve1(int x, int y) {
    if(x < y) swap(x, y);
    if(x >= y * 2) ans = min(ans, (x + 1) / 2);
    else ans = min(ans, x - y + ((2 * y - x) * 2 + 2) / 3);
}
void solve2(int x, int y) {
    ans = min(ans, (x + y + 1) / 2);
}
int main() {
    scanf("%d", &n);
    int minimum = INF, cmini = INF;
    for(int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
        if(i >= 1) solve1(a[i - 1], a[i]);
        if(i >= 2) solve2(a[i - 2], a[i]);
        if(a[i] < minimum) {
            cmini = minimum;
            minimum = a[i];
        } else if(a[i] < cmini) cmini = a[i];
    }
    ans = min(ans, (minimum + 1) / 2 + (cmini + 1) / 2);
    printf("%d\n", ans);
    return 0;
}

F. Desktop Rearrangement

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 1e6 + 117;

int n, m, q;
int i, j, sum = 0;
int tree[MAXN];
int lowbit(int x) {
    return x & -x;
}
void update(int p, int x) {
    while(p < MAXN) {
        tree[p] += x;
        p += lowbit(p);
    }
}
int query(int p) {
    int sum = 0;
    while(p) {
        sum += tree[p];
        p -= lowbit(p);
    }
    return sum;
}
char s[1077][1077];
int main() {
    scanf("%d%d%d", &n, &m, &q);
    for(i = 0; i < n; i++) scanf("%s", s[i]);

    for(j = 0; j < m; j++) {
        for(i = 0; i < n; i++) {
            if(s[i][j] == '*') {
                sum++;
                update(j * n + i + 1, 1);
            }
        }
    }

    while(q--) {
        scanf("%d%d", &i, &j);
        i--, j--;
        if(s[i][j] == '*') {
            sum--;
            s[i][j] = '.';
            update(j * n + i + 1, -1);
        } else {
            sum++;
            s[i][j] = '*';
            update(j * n + i + 1, 1);
        }
        printf("%d\n", sum - query(sum));
    }
    return 0;
}

如果当前查询使$sum+1$，则$cnt$的值受新增加进前$sum$个的格子和查询修改的格子两者共同影响。
如果当前查询使$sum-1$，则$cnt$的值受被移出前$sum$个的格子和查询修改的格子两者共同影响。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 1e6 + 117;

int n, m, q;
int sum = 0, cnt = 0;
char s[1077][1077];
int main() {
    scanf("%d%d%d", &n, &m, &q);
    for(int i = 0; i < n; i++) {
        scanf("%s", s[i]);
        for(int j = 0; j < m; j++) {
            if(s[i][j] == '*') sum++;
        }
    }

    for(int j = 0; j < m; j++) {
        if(j * n  + 1 > sum) break;
        for(int i = 0; i < n; i++) {
            if(j * n + i + 1 > sum) break;
            if(s[i][j] == '*') cnt++;
        }
    }

    int x, y;
    while(q--) {
        scanf("%d%d", &x, &y);
        x--, y--;
        if(s[x][y] == '*') {
            sum--;
            if(s[sum % n][sum / n] == '*') cnt--;
            if(y * n + x + 1 <= sum) cnt--;
            s[x][y] = '.';
        } else {
            if(s[sum % n][sum / n] == '*') cnt++;
            sum++;
            if(y * n + x + 1 <= sum) cnt++;
            s[x][y] = '*';
        }
        printf("%d\n", sum - cnt);
    }
    return 0;
}

G. Remove Directed Edges

路径起始顶点$head$的出度$out[head] \ge 2$。
路径中间顶点$i$的入度$in[i] \ge 2$、出度$out[i] \ge 2$。
路径结束顶点$tail$的入度$in[tail] \ge 2$。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 1e6 + 117;

int n, m;
int in[MAXN], out[MAXN];
int head[MAXN], tot;
struct Edge {
    int v;
    int ne;
} edge[MAXN];
void addEdge(int u, int v) {
    edge[tot].v = v;
    edge[tot].ne = head[u];
    head[u] = tot++;
}
int dp[MAXN];//非头结点的长度
int dfs(int i) {
    if(dp[i] != 0) return dp[i];
    if(in[i] >= 2) {
        if(out[i] >= 2) {//中间结点
            for(int j = head[i]; j != -1; j = edge[j].ne) {
                dp[i] = max(dp[i], dfs(edge[j].v) + 1);
            }
        } else {//尾结点
            dp[i] = 1;
        }
    }
    return dp[i];
}
int main() {
    scanf("%d%d", &n, &m);
    for(int i = 0; i <= n; i++) {
        dp[i] = 0;
        head[i] = -1;
        in[i] = out[i] = 0;
    }

    while(m--) {
        int u, v;
        scanf("%d%d", &u, &v);
        addEdge(u, v);
        in[v]++;
        out[u]++;
    }

    int ans = 1;
    for(int i = 1; i <= n; i++) {
        if(out[i] >= 2) {
            for(int j = head[i]; j != -1; j = edge[j].ne) {
                ans = max(ans, dfs(edge[j].v) + 1);
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}

版权属于：小影
本文链接：http://kindkidll.com/index.php/archives/193/
所有原创文章采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可。您可以自由的转载和修改，但请务必注明文章来源并且不可用于商业目的。

Codeforces Round #786 (Div. 3)

A. Number Transformation

B. Dictionary

C. Infinite Replacement

D. A-B-C Sort

E. Breaking the Wall

F. Desktop Rearrangement

G. Remove Directed Edges

Leave a Comment Cancel reply

【每日一题】4月7日树

链式前向星

handsome主题修改记录

红黑树入门

【每日一题】4月2日月月查华华的手机

Codeforces Round #812 (Div. 2)

Codeforces Round #765 (Div. 2)

Codeforces Round #853 (Div. 2)

2021牛客寒假算法基础集训营3

2020年4月蓝桥杯官方B组省赛模拟赛

Codeforces Round #786 (Div. 3)

A. Number Transformation

B. Dictionary

C. Infinite Replacement

D. A-B-C Sort

E. Breaking the Wall

F. Desktop Rearrangement

G. Remove Directed Edges