题目链接：C、Ehab and Prefix MEXs
题意;
有长度为n的数组a(下标从1开始),要求构造一个相同长度的数组b,使得b1,b2,....bi集合中没有出现过的最小的数是ai.
mex函数表示不在集合中的那个最小的自然数
例如：
mex(1,2,3)=0
mex(0,1,2)=3
mex(0,1,3)=2
对于题意你要保证
mex(b1)=a1
mex(b1,b2)=a2
mex(b1,b2,b3)=a3
题解：
首先这个题目肯定是有解的，无解的情况题目都给排除了。
给b数组初始值为n+1，对于ai的值，我们必须保证0——(ai-1) （这代表区间【0，(ai-1)】）这些值都在b1——bi（这代表b1,b2...bi）出现过了。那么我们取b1——bi 中最小的不是n+1的值为x（如果全是n+1，那么x=0），我们从bi向b1逆向枚举，每遇到一个n+1，那就给它赋值x，然后让x++。这样一直操作就没了
至于为什么要逆向操作，这是个贪心，因为小的值ai只会在前面出现（题目要求了ai<=a(i+1)），如果你把小的值放在前面会影响前面答案的正确性
代码：
1 #include<stdio.h> 2 #include<algorithm> 3 #include<iostream> 4 #include<string> 5 #include<queue> 6 #include<string.h> 7 #include<map> 8 #include <iostream> 9 #include <math.h> 10 using namespace std; 11 typedef long long ll; 12 const int maxn=1e5+10; 13 int v[maxn],w[maxn]; 14 int main() 15 { 16 17 int n; 18 scanf("%d",&n); 19 for(int i=1; i<=n; ++i) 20 { 21 scanf("%d",&v[i]); 22 w[i]=n+1; 23 } 24 int k=0; 25 for(int i=1; i<=n; ++i) 26 { 27 for(int j=i; j>=1; --j) 28 { 29 if(k>=v[i]) break; 30 if(w[j]==n+1) 31 { 32 w[j]=k++; 33 } 34 } 35 } 36 for(int i=1; i<=n; ++i) 37 { 38 if(i==n) 39 printf("%d\n",w[n]); 40 else printf("%d ",w[i]); 41 } 42 43 return 0; 44 }
题目链接：D、Ehab‘s Last Corollary 参考链接：https://www.cnblogs.com/Last--Whisper/p/13143897.html#
题意：
给出一张 nn 个点的无向连通图和一个常数 kk。你需要解决以下任何一个问题中的一个:
一条边的长度算作1
独立集: 独立集是一个点的集合，满足其中任意两点之间在原图上没有边直接相连。
题解：
这道题也是肯定是有解的，如果它没有环，那么k/2个点的独立集肯定能找到
如果有环，环的长度小于k直接输出，如果大于k，因为它是最小的环，那么任意一个点只会与环中两个点相连才一起构成一个环。那么这个环绝对能找出来k/2个点独立集
我们可以先假设这个图没有环，那只需要随便找一个点开始染色。然后给与这个点相连的其他点染成另外一种颜色。这样不停的染色直到这个图的每一个点都被染色就可以了
如果后面我们确定了就是没有环，那就输出相同颜色的点就可以了
对于确定是否含有环，我们可以事先定义一个vector容器p用它来装已经dfs遍历过的点，并且如果一个点在这个p容器中那就把这个点在数组is_circle中标记一下。如果一个图里面包含环的话，如下图
我们从1点开始进行dfs，我们可以看到1，2，3，5构成了一个环。我们进行模拟dfs，从1我们会dfs到2，然后从2我们dfs到5，从5我们dfs到3，从3我们dfs到1我们发现1这个点已经被标记过了。那就证明存在环
如果我们发现了环我们不管这个环是不是最小环（例如，如果多一条边2——3，那么1，2，3，5里面就包含一个小环1，2，3），直接让我们遇到那个标记过的点1到我们dfs到现在遇到的所有点都装入一个容器（也就是把1，2，5，3装入另一个容器）
我们这里说一下height数组，这个数组表示的是某一个点是第几深度遍历到的，对于序列1，2，5，3。height[1]=0,height[2]=1,height[5]=2，height[3]=3;
然后枚举每一条边，如果某条边的两个节点x和y的深度不一样且这两个点都在环中，那就证明这个环不是最小环(假设2——3这条边存在)，那么x和y就是2和3，那就从这个1，2，3，5的开头和结尾删除节点，直到遇见x或者y就截至
代码：
1 #include<stdio.h> 2 #include<algorithm> 3 #include<iostream> 4 #include<string> 5 #include<queue> 6 #include<deque> 7 #include<string.h> 8 #include<map> 9 #include <iostream> 10 #include <math.h> 11 using namespace std; 12 typedef long long ll; 13 const int maxn=2e5+10; 14 struct shudui 15 { 16 int x,y; 17 } edge[maxn]; 18 int n,m,k,height[maxn],is_circle[maxn]; 19 vector<int> w[maxn],p,colour[2]; 20 deque<int> circle; 21 void dfs(int x,int fa) 22 { 23 height[x]=p.size(); 24 p.push_back(x); 25 colour[p.size()%2].push_back(x); 26 for(int i=0; i<w[x].size(); ++i) 27 { 28 int to=w[x][i]; 29 if(to==fa) continue; 30 if(height[to]==-1) 31 { 32 dfs(to,x); 33 } 34 else 35 { 36 if(circle.empty()) 37 { 38 for(int i=height[to]; i<=height[x]; ++i) 39 { 40 circle.push_back(p[i]); 41 is_circle[p[i]]=1; 42 } 43 } 44 } 45 } 46 p.pop_back(); 47 } 48 int main() 49 { 50 memset(height,-1,sizeof(height)); 51 scanf("%d%d%d",&n,&m,&k); 52 for(int i=0; i<m; ++i) 53 { 54 int x,y; 55 scanf("%d%d",&x,&y); 56 edge[i].x=x; 57 edge[i].y=y; 58 w[x].push_back(y); 59 w[y].push_back(x); 60 } 61 dfs(1,0); 62 if(circle.empty()) 63 { 64 printf("1\n"); 65 if(colour[0].size()<colour[1].size()) swap(colour[0],colour[1]); 66 for(int i=0; i<(k+1)/2; ++i) 67 { 68 if(i==0) printf("%d",colour[0][i]); 69 else printf(" %d",colour[0][i]); 70 } 71 printf("\n"); 72 return 0; 73 } 74 75 for(int i=0; i<m; ++i) 76 { 77 int x=edge[i].x; 78 int y=edge[i].y; 79 if(is_circle[x] && is_circle[y] && abs(height[x]-height[y])>1) 80 { 81 while (circle.front() != x && circle.front() != y) 82 { 83 is_circle[circle.front()] = false; 84 circle.pop_front(); 85 } 86 while (circle.back() != x && circle.back() != y) 87 { 88 is_circle[circle.back()] = false; 89 circle.pop_back(); 90 } 91 } 92 } 93 94 if(circle.size()<=k) 95 { 96 printf("2\n%d\n",circle.size()); 97 for(int i=0;i<circle.size();++i) 98 { 99 if(i==0) printf("%d",circle[i]); 100 else printf(" %d",circle[i]); 101 } 102 printf("\n"); 103 } 104 else 105 { 106 printf("1\n"); 107 int sum=0; 108 for(int i=0;i<circle.size();i+=2) 109 { 110 if(i==0) printf("%d",circle[i]); 111 else printf(" %d",circle[i]); 112 sum++; 113 if(sum>=(k+1)/2) break; 114 } 115 printf("\n"); 116 } 117 return 0; 118 }
Codeforces Round #649 (Div. 2) C、Ehab and Prefix MEXs D、Ehab's Last Corollary 找环和点染色
原文：https://www.cnblogs.com/kongbursi-2292702937/p/13323796.html
