首页 > 其他分享 >P3043 [USACO12JAN] Bovine Alliance G 题解

P3043 [USACO12JAN] Bovine Alliance G 题解

时间:2024-08-01 13:28:30浏览次数:18  
标签:__ cnt P3043 联通 int 题解 USACO12JAN cnt1 ans

P3043 [USACO12JAN] Bovine Alliance G

题目传送门

思路

首先分情况讨论每种联通块的可能,有三种不同的情况会对答案 \(ans\) 产生不同的贡献。

联通块有环

1
如图,因为每条边都有要有归属,所以环上的边只能全都顺时针或逆时针属于某个点,且不在环上的点仅有一种可能。

因此该情况对答案的贡献为 \(ans \times 2\) 。

联通块为链

2
对于一条链,边数比点数小 1 所以仅有一个点是没有边的,而若确认某个点没有边的话,边的所属仅有一种可能。因此答案的贡献为 \(ans \times t\) , \(t\) 为该联通块点的个数。

联通块内边数大于等于点数

3
问题的答案为 \(0\) ,直接结束了。

转化

问题变为判断联通块内的情况,对此,利用联通块内度数除以 \(2\) 等于边数,判断点数与边数的关系即可。

代码

#include <iostream>
#include <cstdio>
typedef long long LL;

using namespace std;

const int mod = 1e9 + 7, N = 1e5 + 5;

#define MOD(x) ((x + mod) % mod)
#define LF(i, __l, __r) for (int i = __l; i <= __r; i++)
#define RF(i, __r, __l) for (int i = __r; i >= __l; i--)

int head[N], ver[N * 2], nxt[N * 2], edge[N * 2];
int n, m, tot = 1;
bool vis[N];
LL ans = 1, cnt, cnt1;

void add(int u, int v) {
    ver[++tot] = v;
    nxt[tot] = head[u], head[u] = tot;
}

void dfs(int u) {
    vis[u] = true, cnt++;
    for (int i = head[u]; i; i = nxt[i]) {
        cnt1++;
        if (!vis[ver[i]]) dfs(ver[i]);
    }
}

int main() {
    scanf("%d%d", &n, &m);
    
    LF(i, 1, m) {
        int x, y;
        scanf("%d%d", &x, &y);
        add(x, y), add(y, x);
    }

    LF(i, 1, n) {
        if (!vis[i]) {
            cnt = cnt1 = 0;
            dfs(i);
            if (cnt == cnt1 / 2) ans = MOD(ans * 2);
            else if (cnt > cnt1 / 2) ans = MOD(ans * cnt);
            else { ans = 0; break; } 
        }
    }

    printf("%lld", ans);
    return 0;
}

三军可夺帅也,匹夫不可夺志也。

标签:__,cnt,P3043,联通,int,题解,USACO12JAN,cnt1,ans
From: https://www.cnblogs.com/FRZ29/p/18336480

相关文章

  • 题解:CF687C The Values You Can Make
    CF687CTheValuesYouCanMake题解题目翻译感觉不明不白的(至少我看了几遍没看懂),这里给个较为清晰的题面。题目描述给你\(n\)个硬币,第\(i\)个硬币有一个价值\(c_i\),你需要从中选出一些价值和为\(k\)的硬币组成一个集合,再输出这个集合中硬币可能组成的价值和。算法动......
  • 题解:CF559B Equivalent Strings
    CF559BEquivalentStrings题解题目描述吐槽一下,题目翻译有歧义。思路分析你会发现,当你需要判断字符串\(a,b\)是否等价时,如果长度为偶数,需要继续判断字符串\(a\)拆分的字串。所用知识s.substr(i,j)//在字符串s中,从位置i开始截取长度为j的字串参考代码#include<bits......
  • 题解:CF718A Efim and Strange Grade
    CF718AEfimandStrangeGrade题解算法贪心+模拟思路分析显然,要最优每一次进位就只能五入不能四舍。而且当我们五入时,要取位数最高的。比如说\(1.3535\),我们有两种进位方式,一种是进位成\(1.4\),一种是进位成\(1.354\),显然前者更优。那这道题给的次数有啥用呢?考虑一种“......
  • P10511 方差 题解
    【题目简述】定义一个长度为\(n\)的序列\(a\)的方差为:\(s^2=\frac{1}{n}\sum_{i=1}^n(a_i-\overline{a})^2\)。\(\sum\)为累加求和符号,\(\overline{a}\)为序列\(a\)的平均数。给定\(m\)个形如\([l,r,b]\)的组合,表示\(a_l,a_{l+1},\ldots,a_r\)为\(b\)。给定......
  • 洛谷P2696之慈善的约瑟夫——题解
    洛谷P2696题解[传送锚点](P2696慈善的约瑟夫-洛谷|计算机科学教育新生态(luogu.com.cn))比不过大佬,从蒟蒻做起选择比较水有意思的解法——用队列模拟(还是窝太弱了)正片开始考虑队列模拟,因为每次都是假的剔除,所以我们的目标是找到每回游戏的最终存活者。将不被剔除,......
  • 题解:Pinely Round 4 (Div. 1 + Div. 2) C
    C.AbsoluteZerotimelimitpertest:2secondsmemorylimitpertest:256megabytesinput:standardinputoutput:standardoutputYouaregivenanarray\(a\)of\(n\)integers.Inoneoperation,youwillperformthefollowingtwo-stepmove:Choose......
  • Codeforces 11D A Simple Task 题解 [ 蓝 ] [ 状压 dp ]
    思路不难想,细节比较多。思路观察到\(n\le19\),首先想到状压dp。于是自然地定义\(dp[j][i]\)为:抵达点的状态为\(i\),且此时在点\(j\)时,简单路径的条数。注意这里是简单路径的条数,而不是环的个数,因为环的个数要在dp过程中统计。这里的dp作用就在于求简单路径条数。......
  • [JOI 2020 Final] 火事 题解
    给一篇题解。(下面这张图是从luogu上粘贴的,因为不太会画图)其中纵坐标为\(t\),横坐标为\(a_i\)。发现同颜色块只有平行四边形和直角梯形(等腰直角三角形)两种情况。可以将直角梯形削去左下角,分成两部分考虑。等直可以直接暴力插入区间,总个数\(O(n)\)。平行四边形可以看作上......
  • [CF455D] Serega and Fun 题解
    不知道大家做没做过数列分块基础9题?插入删除操作可以用链表,线段树等数据结构都不好维护,考虑分块。对于修改操作,暴力重构受影响块的链表,发现除首尾块外,其他块都可以看作是区间左移一位,所以加头删尾即可。每个块开一个数组(绝对不能是\((un\_)map\),不然你会和我一样死的很诡异),表示......
  • HDU2024 R2 T9 题解
    考虑维护一下每个点的速度。把区间加拆成后缀加和后缀减,然后考虑后缀加。减就同理。考虑在一段后缀的目标速度增加之后,哪些时刻的加速度会变化。这里加速度必然只会变大\(1\),因此在这个时刻之后的速度都会增加\(1\),又由于目标速度也增加了\(1\),所以这个位置之后的加速度都不再......