Codeforces 353E 贪心

妖狐艹你老母 2021-12-12 02:04 352阅读 0赞

题意：给你一张有向图，第i条边连接i号点和(i + 1) % n号点，问最多可以选择多少个点，使得这些点互相不可达。

思路：容易发现，如果某个边的集合点的数目大于等于2，那么就可以选出一个点，当然也可以出现多个1条边的集合相邻的情况（假设有m个），那么可以选择m / 2条边。

代码：

  1. #include <bits/stdc++.h>
  2. #define LL long long
  3. #define INF 0x3f3f3f3f
  4. #define db double
  5. #define pii pair<int, int>
  6. using namespace std;
  7. const int mod = 1e9 + 7;
  8. const int maxn = 1000010;
  9. char s[maxn];
  10. int main() {
  11.     int ans = 0;
  12.     scanf("%s", s);
  13.     int n = strlen(s);
  14.     for (int i = 0; i < n; i++) {
  15.         if(s[i] != s[(i + 1) % n]) {
  16.             if(s[i] != s[(i + 2) % n]) ans++;//下一个集合边数大于等于2，直接选择 
  17.             else if(s[i] != s[(i + 3) % n]) {//出现了两个连续大小为1的集合，直接选择 
  18.                 i++, ans++;
  19.             }
  20.         }
  21.     }
  22.     printf("%d\n", ans);
  23. }

　　

转载于:https://www.cnblogs.com/pkgunboat/p/11107460.html

发表评论

表情：
评论列表 （有 0 条评论，352人围观）

还没有评论，来说两句吧...

相关阅读

    相关 CodeForces1154E

    [CodeForces1154E][] 题意就是有两个教练,每个教练轮流操作,每次操作会选取所有未被选取的学生中能力值最高的那一个并把这个学生向左向右各\\(k\\)个学生

    落日映苍穹つ落日映苍穹つ/ 0 赞/ 120 阅读

    相关 Codeforces 353E 贪心

    题意：给你一张有向图，第i条边连接i号点和(i + 1) % n号点，问最多可以选择多少个点，使得这些点互相不可达。 思路：容易发现，如果某个边的集合点的数目大于等于2，那么

    妖狐艹你老母妖狐艹你老母/ 0 赞/ 353 阅读