CodeForces - 353E Antichain(贪心+思维)

题目链接：点击查看

题目大意：给出n个点，用n-1条边连接，第i条边连接着点i与点(i+1)%n，也就是首尾相接组成了一个环，现在0表示点i连到点(i+1)%n的一条有向边，1表示点(i+1)%n连到点i的一条有向边，现在问最多可以从n个点中拿出几个点，使得任意两点都是不连通的

题目分析：这个题目完全可以抽象成二分图的模型，一开始建边然后跑匈牙利，可问题就是这个题目的数据范围，n给到了1e6，所以用匈牙利肯定是会超时的，我们再分析一下，这个题目虽然也是给点，给边，组成了有向图，可这个题目的有向图给的是一个环，换句话说我们可以从头遍历一遍，将其变成一个线性的问题，我们再来分析一下哪些情况可以将一个点拿出来加入到答案的集合中呢（当然是看了网上的题解才分析出来的）：我们先假设0表示的是-->这个方向的边，1表示的是<--这个方向的边

若相同方向的边相邻的个数大于等于两个，我们就可以从中取出一个满足条件的点加入答案集合中，比如：

a-->b-->c，这个时候就可以将点b取出

a<--b<--c，同上

若相同方向的边交替出现大于等于两次，我们就可以选出一个点加入到答案集合中，比如：

a-->b<--c-->d<--e，这时点c一定是满足条件的

a<--b-->c<--d-->e，同上

这样线性遍历一遍就可以直接求出答案了，虽然不太会证明为什么是贪心，但看上去有点贪心的意思吧。。

代码：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=210;int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);string s;cin>>s;int n=s.size();int ans=0;for(int i=0;i<n;i++){if(s[i]!=s[(i+1)%n])//首先满足相邻的边方向不同{if(s[i]!=s[(i+2)%n])//若后面集合中的边大于等于两条(上述情况1)ans++;else if(s[i]!=s[(i+3)%n])//若后面的集合交替出现大于等于两次(上述情况2)ans++,i++;}}printf("%d\n",ans);return 0; }

 

总结

以上是生活随笔为你收集整理的CodeForces - 353E Antichain(贪心+思维)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。