首页 > 其他分享 >CF1651E Sum of Matchings

CF1651E Sum of Matchings

时间:2024-06-06 20:22:23浏览次数:20  
标签:cnt Matchings int Sum mx2 mx1 cir CF1651E mn2

标签:图论

鱼鱼蒸题。

原图由若干个偶环组成,那么对于每个环分别计算贡献,枚举环上的一段区间,然后算出要能包含这一段的 \(l,r,L,R\) 的对应的最小区间,然后又不能包含这段区间左右的点,所以要去掉一部分,然后乘起来再乘上区间长度的一半即可

优美的代码实现。

#include <bits/stdc++.h>
#define int long long

#define F(i, a, b) for (int i = (a); i <= (b); i++)
#define dF(i, a, b) for (int i = (a); i >= (b); i--)
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int N = 6005, M = (N << 1), inf = 1e16, mod = 1e9 + 7;
int ans, n, m, cnt, vis[N], cir[N];
vector<int> G[N];
void dfs(int u) {
    vis[u] = 1; cir[++cnt] = u;
    for (auto i : G[u]) if (!vis[i]) dfs(i);
}
int mx1 = 0, mn1 = inf, mx2 = 0, mn2 = inf;
void work(int x) {
    if (x <= n) mx1 = max(mx1, x), mn1 = min(mn1, x);
    else mx2 = max(mx2, x), mn2 = min(mn2, x);
}
void ckmax(int &x, int y) { if (y > x) x = y; }
void ckmin(int &x, int y) { if (y < x) x = y; }
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n;
    m = n * 2;
    F(i, 1, m) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    F(i, 1, n) {
        if (!vis[i]) {
            mx1 = 0, mn1 = inf, mx2 = 0, mn2 = inf, cnt = 0;
            dfs(i);
            F(j, 1, cnt) cir[j + cnt] = cir[j];
            F(j, 1, cnt) work(cir[j]);
            ans += mn1 * (n - mx1 + 1) * (mn2 - n) * (n * 2 - mx2 + 1) * cnt / 2;
            F(j, 1, cnt) {
                mx1 = 0, mn1 = inf, mx2 = 0, mn2 = inf, work(cir[j]);
                F(k, j + 1, j + cnt - 2) {
                    work(cir[k]);
                    int val = (k - j + 1) / 2, x[2] = {j == 1 ? cnt * 2 : j - 1, k + 1};
                    int d1 = 1, u1 = n, d2 = n + 1, u2 = n * 2;
                    F(p, 0, 1) {
                        if (cir[x[p]] >= mn1 && cir[x[p]] <= mx1 || cir[x[p]] >= mn2 && cir[x[p]] <= mx2) {val = 0; break;}
                        if (cir[x[p]] <= n) {
                            if (cir[x[p]] < mn1) ckmax(d1, cir[x[p]] + 1);
                            if (cir[x[p]] > mx1) ckmin(u1, cir[x[p]] - 1);
                        } else {
                            if (cir[x[p]] < mn2) ckmax(d2, cir[x[p]] + 1);
                            if (cir[x[p]] > mx2) ckmin(u2, cir[x[p]] - 1);
                        }
                    }
                    ans += (mn1 - d1 + 1) * (u1 - mx1 + 1) * (mn2 - d2 + 1) * (u2 - mx2 + 1) * val;
                }
            }
        }
    }
    cout << ans;
    return 0;
}

标签:cnt,Matchings,int,Sum,mx2,mx1,cir,CF1651E,mn2
From: https://www.cnblogs.com/z-t-rui/p/18235962/CF1651E

相关文章

  • C. Given Length and Sum of Digits...
    原题链接一句话题意分别找出长度为n,每位数字和恰好为m的最小数和最大数,如果找不到输出”-1-1“思维怎么确保构造的数最小/大?怎么确保数字和恰好为m?实施遍历每一位,贪心地选取最大/最小的数,直到接下来的数字不足以贪心细节1.没有前导零2.数字和恰好为m3.注意边界特判co......
  • LeetCode 1748. Sum of Unique Elements
    原题链接在这里:https://leetcode.com/problems/sum-of-unique-elements/description/题目:Youaregivenanintegerarray nums.Theuniqueelementsofanarrayaretheelementsthatappear exactlyonce inthearray.Return the sum ofalltheuniqueelementso......
  • [ABC238E] Range Sums
    原题链接题解把这里的数字看成间隔,不要看成点假设已知能和\(l\)组成区间的端点集合\(A\)和以\(r\)组成区间的端点集合\(B\),这时候加入一个以\(l,r\)为左右端点的区间,那么在加入区间\(l,r\)之后,这两个集合可以合并code#include<bits/stdc++.h>usingnamespacestd......
  • 文献阅读——Single Clause Assumption without Activation Literals to Speed-up IC
    SingleClauseAssumptionwithoutActivationLiteralstoSpeed-upIC3 @inproceedings{DBLP:conf/fmcad/FroleyksB21,author={NilsFroleyksandArminBiere},title={SingleClauseAssumptionwithoutActivationLitera......
  • Linux低功耗Suspend/Resume梳理(基于STM32MP1)
    基于STM32MP1简单梳理Linuxsuspend/resume涉及到的内容:触发Suspend流程,以及唤醒手段和后续resume流程。Linuxkernel中Suspend/Resume流程。TFA中冷启动、热启动、SMC处理、PSCI实现等等。其他低功耗相关:poweroff、reboot、fiq处理。PowerDomainTree介绍;PSCI移植指导等。......
  • SUMER UI3.0组件库,基于Uni-app前端框架!一端开发,多端运行!本组件库可快速二次开发各种类
    sumer-ui介绍基于uView微信小程序UI组件库,兼容vue3。本插件是SUMER组件库,只提供组件库源码下载(不包含模板源码),本组件库可快速二次开发各种类别各行业模板,包括:商城、视频、直播、聊天、支付、新闻、社区、地图、导航、出行、社区、博客、新闻、游戏、影视、订票、广告等,......
  • CF1973F Maximum GCD Sum Queries 题解
    题目链接点击打开链接题目解法首先想到枚举两个数列的$\gcd$,求最小代价两个数列的\(\gcd\)应该分别是\(a_1,b_1\)的因数或\(b_1,a_1\)的因数这样就把枚举范围缩小到了\(d(a_1)\timesd(b_1)\),这求最小代价需要\(O(n)\),不够快假设枚举的\(\gcd\)分别为\(x,y\)......
  • 基于Springboot的rabbitTemplate的Publisher和Consumer初始化
    Publisher初始化的bean(声明new 的queue或者exchange)不会连接broker(Rabbit),在开始rabbitTemplate.convertAndSend时才会连接。消息发布到没有声明的exchange会报错,声明exchange和queue,Rabbit会创建,如果没有的话。如果exchange没有绑定queue,消息(默认false)会被抛弃。如果exc......
  • [LeetCode] 1863. Sum of All Subset XOR Totals
    TheXORtotalofanarrayisdefinedasthebitwiseXORofallitselements,or0ifthearrayisempty.Forexample,theXORtotalofthearray[2,5,6]is2XOR5XOR6=1.Givenanarraynums,returnthesumofallXORtotalsforeverysubsetofnums.......
  • [ARC178C] Sum of Abs 2 题解
    题意:给定\(n\)和\(L\)以及\(n\)个数\(a_i\)。对于每个\(1\lei\len\),求出一个长度为\(L\)的\(b\)序列满足:\(\sum_{i=1}^{L-1}\sum_{j=i+1}^{L}|b_j-b_i|=a_i\),并最小化\(b\)中的最大值。显然\(b\)中元素的顺序不影响原式的结果,所以我们可以假定\(b\)是不......