首页 > 其他分享 >CF1019C Sergey's problem

CF1019C Sergey's problem

时间:2024-05-16 23:08:59浏览次数:31  
标签:head 覆盖 int CF1019C Sergey edge maxn tot problem

CF1019C Sergey's problem

很巧妙的构造题。

思路

首先我们可以把这题分成两个部分:

  • 解决覆盖问题
  • 解决边冲突问题

\(vis_i\) 为 \(i\) 点是否被覆盖的标记,\(cis_i\) 为 \(i\) 点是否被选的标记。

part1 覆盖问题

从小到大枚举 \(i\),对于点 \(i\) 如果它没被覆盖,那么我们把点 \(i\) 标为被覆盖并且使这个点被选中,存在有向边 \(i->j\) 的 \(j\) 标为被覆盖。

part2 冲突问题

从大到小枚举 \(i\),对于点 \(i\) 如果它被选中,那么我们把这个点 \(i\) 存在有向边 \(i->j\) 的点 \(j\) 的选中标记去掉。

这样的答案就是一组合法答案。

证明:

第一个部分,满足了被选中点存在边冲突当且仅当 \(u>v\) 且存在边 \(u->v\) 不存在边 \(v->u\)。

第二个部分,证明:一个点进行了二部分的操作后一定会被留下。

设点 \(u\) 进行完二部分操作后被删除,不妨设删除 \(u\) 的点为 \(v\),那么肯定有 \(u>v\) 且存在边 \(v->u\),与第一部分保证的情况产生冲突,故得证。

\(u\) 删除产生冲突的点后,对于产生冲突的点所覆盖的点,\(u\) 一定可以覆盖到(覆盖距离是 \(2\))。

易得经过一部分后所有的点都已处于被覆盖或被选中的状态,所有经过操作二后,所有的点亦处于被选中或被覆盖的状态。

得证。

CODE

#include<bits/stdc++.h>
using namespace std;

const int maxn=1e6+5;

struct Edge
{
    int tot;
    int head[maxn];
    struct edgenode{int to,nxt;}edge[maxn*2];
    inline void add(int x,int y)
    {
        tot++;
        edge[tot].to=y;
        edge[tot].nxt=head[x];
        head[x]=tot;
    }
}G;

int n,m,tot;

bool vis[maxn],cis[maxn];

inline void solve1(int u)
{
    vis[u]=true;cis[u]=true;
    for(int i=G.head[u];i;i=G.edge[i].nxt)
    {
        int v=G.edge[i].to;
        vis[v]=true;
    }
}
inline void solve2(int u)
{
    for(int i=G.head[u];i;i=G.edge[i].nxt)
    {
        int v=G.edge[i].to;
        cis[v]=false;
    }
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        G.add(x,y);
    }
    for(int i=1;i<=n;i++) if(!vis[i]) solve1(i);
    for(int i=n;i;i--) if(cis[i]) solve2(i);
    for(int i=1;i<=n;i++) if(cis[i]) tot++;
    printf("%d\n",tot);
    for(int i=1;i<=n;i++) if(cis[i]) printf("%d ",i);
}

标签:head,覆盖,int,CF1019C,Sergey,edge,maxn,tot,problem
From: https://www.cnblogs.com/binbinbjl/p/18196941

相关文章

  • D - Another Sigma Problem
    D-AnotherSigmaProblemhttps://atcoder.jp/contests/abc353/tasks/abc353_d 思路前缀和+快速幂https://zhuanlan.zhihu.com/p/697255076 Codehttps://atcoder.jp/contests/abc353/submissions/53514365typedeflonglongll;llpow(llx,lln){if(n==......
  • 「ABC353」Yet Another Sigma Problem
    题目字典树做法(用时187ms)#include<cstdio>#include<ctype.h>constintN=3e5+10;intn;longlongans;inttrans[N][26],cnt[N];inttot;chars[N];template<classT>voidread(T&x){ charc=getchar(); while(!isdigit(c))c=getchar()......
  • ABC353C Sigma Problem 题解
    ABC353CSigmaProblem题解题目链接:AT题目中的两个求和符号\(\sum_{i=1}^{N-1}\sum_{j=i+1}^{N}\)实际上是在枚举所有的有序数对\((i,j)\)。而有序数对的个数\(N(N-1)/2=O(N^{2})\),真的去枚举所有数对肯定会T。这时应该考虑去拆贡献,求出每个\(A_i\)对答案的贡献。......
  • C - Sigma Problem
    C-SigmaProblemhttps://atcoder.jp/contests/abc353/tasks/abc353_c 思路暴力TLE观察a1a2...an序列计算目标是,两两结合并并求模sum=sigma(ai+aj)%1e8ai,aj<=1e8ai+aj可能溢出,也可能不溢出于是我们考虑,统计所有溢出的个数。 对数组进行排序,......
  • Week 9 Problems
    T1用等值演算、构造指派等方式判断公式的永真性(1)\[(\forallxP(x)\rightarrow\existxQ(x))\rightarrow\existx(P(x)\rightarrowQ(x))\](2)\[(\forallxP(x)\rightarrow\forallxQ(x))\rightarrow\forallx(P(x)\rightarrowQ(x))\]T2以下哪一步出现错误?......
  • Codeforces 954I Yet Another String Matching Problem
    考虑到这个答案怎么算。能发现相当于是对应的字符间相连边,那么一个连通块中的字符就要变成同一个字符。于是一个连通块的代价就是\(sz-1\)。所以令有\(x\)个连通块,最后的代价就是\(|\Sigma|-x\)。考虑到因为\(|\Sigma|=6\),而\(B_6=203\)(贝尔数,\(B_n\)意义为大......
  • 「主席树维护高精度」 CF464E The Classic Problem
    发现难点在于维护\(dis_u\)(起点\(s\)到\(u\)的最短路)。如果使用暴力高精度,复杂度会乘上一个\(len\)。考虑边权\(2^w\)的特殊性质,如果使用一个二进制串来维护\(dis\),那么加上边权\(2^w\)相当于将二进制下某一段\(1\)置为\(0\),然后再将一个\(0\)置为\(1\)。说白了......
  • 196. 删除重复的电子邮箱【Problem:Every derived table must have its own alias】
    SQL-Boy上线,最近在写SQL语句遇到了这样的问题。Problem:Everyderivedtablemusthaveitsownalias错误语句如下deletefromPersonwhereidnotin(selectidfrom(selectmin(id)asidfromPersongroupbyemail)......
  • P1480 A/B Problem
    P1480A/BProblem题目描述输入两个整数\(a,b\),输出它们的商。输入格式两行,第一行是被除数,第二行是除数。输出格式一行,商的整数部分。样例输入102输出5提示\(0\lea\le10^{5000}\),\(1\leb\le10^9\)。思路通过题目数据范围可以发现是高精度除以单精度的题目......
  • P1303 A*B Problem
    P1303A*BProblem题目给出两个非负整数,求它们的乘积。输入输入共两行,每行一个非负整数。输出输出一个非负整数表示乘积。样例输入12输出2提示每个非负整数不超过\(10^{2000}\)。思路根据题意,乘数的数据最大范围是\(10^{2000}\),需要使用高精度乘高精度的算......