差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:acm_life_from_zero:5.02-5.08 [2020/05/08 22:27]
holmium
+++ 2020-2021:teams:acm_life_from_zero:5.02-5.08 [2020/05/15 22:41] (当前版本)
holmium [姜维翰]
@@ 行 146: / 行 146: @@
 ===== 题目 =====
 cf goodbye 2018 E
 题意：一个n点无向图，给出n-1点的度数，问第n个点的所有可能度数，无解输出-1
 n=500000
 解法：我们可以很容易知道答案的奇偶性，此外若a和b都可行a<b，则对于a<c<b，且c和ab奇偶性相同，那么c一定可行
 所以只要找出上下界就行
 原题中给出了一个定理，利用这个定理以及握手定理可以判定给定的度数是否合法
-看上去不能十分，但是这个定理在判出非法的同时你还可以知道是偏大还是偏小，所以可以先二分找一个可靠解，再对上下界二分
+看上去不能二分，但是这个定理在判出非法的同时你还可以知道是偏大还是偏小，所以可以先二分找一个可靠解，再对上下界二分
 <code cpp>
 #include<bits/stdc++.h>
@@ 行 271: / 行 278: @@
 	cout<<endl;
-<code>
+</code>
-====== 本周推荐 ======
-===== 李元恺 =====
+====== 袁熙 ======
+===== 专题 =====
+没有专题
+===== 比赛 =====
+没有比赛
+===== 题目 =====
+CF1344C Quantifier Question DFS
+理解一下题意：给E,V~2e5的图，若无环，求有多少点，满足是其所在连通块上点编号最小的点
+花的时间有点久，写之前想的不太充分，只考虑了后面的点
+实际解法：做正向和逆向的拓扑排序，确定点是否为编号最小
+<code cpp>
+#include <bits/stdc++.h>
+#define ll long long
+#define tmp(x) std::cout<<"& "<<(x)<<" &\n"
+#define rep(i,a,b) for(int i=(a);i<=(b);++i)
+#define per(i,a,b) for(int i=(a);i>=(b);--i)
+using namespace std;
+const int maxn=2e5+100;
+const int mo=998244353;
+int ck[maxn],deg[maxn],vis[maxn],vs[maxn],vss[maxn],rdeg[maxn];
+vector<int> g1[maxn],g2[maxn];
+int n,m,u,v,pt;
+inline int read(){
+    int x=0,f=1;
+    char c=getchar();
+    while(c>'9'||c<'0'){
+        if(c=='-')f=-1;
+        c=getchar();
+    }
+    while(c>='0'&&c<='9'){
+        x=x*10+c-'0';c=getchar();
+    }
+    return x*f;
+}
+queue<int> qq;
+queue<int> q;
+void topo(){
+    for(int i=1;i<=n;++i){
+        vs[i]=vss[i]=i;
+        if(!deg[i])vis[i]=1,q.push(i);
+        if(!rdeg[i])qq.push(i);
+    }
+    while(!q.empty()){
+        int x=q.front();q.pop();
+        for(int i=0;i<g1[x].size();++i){
+            vs[g1[x][i]]=min(vs[x],vs[g1[x][i]]);
+            if(--deg[g1[x][i]]==0)vis[g1[x][i]]=1,q.push(g1[x][i]);
+        }
+    }
+    while(!qq.empty()){
+        int x=qq.front();qq.pop();
+        for(int i=0;i<g2[x].size();++i){
+            vss[g2[x][i]]=min(vss[x],vss[g2[x][i]]);
+            if(--rdeg[g2[x][i]]==0)qq.push(g2[x][i]);
+        }
+    }
+    rep(i,1,n)if(!vis[i]){
+            printf("-1\n");return;
+        }
+    rep(i,1,n)if(vs[i]==i&&vss[i]==vs[i])++pt,ck[i]=1;
+    printf("%d\n",pt);
+    rep(i,1,n){
+        if(ck[i])printf("A");
+        else printf("E");
+    }
+    printf("\n");
+}
+int main() {
+    freopen("in.txt","r",stdin);
+    n=read(),m=read();
+    rep(i,1,m){
+        u=read(),v=read();
+        g1[u].push_back(v),g2[v].push_back(u);
+        ++deg[v],++rdeg[u];
+    }
+    topo();
+    return 0;
+}
+</code>
+====== 本周推荐 ======
+===== 李元恺 =====
+推荐后缀数组
+===== 袁熙 =====
+CF1344F 高斯消元
+[[http://codeforces.com/contest/1344/problem/F|题目链接]]（线性代数题？）
+===== 姜维翰 =====
+关于给定各顶点度数时如何判定能否构成图，可以参考这个链接[[https://en.wikipedia.org/wiki/Graph_realization_problem]]

CVBB ACM Team

用户工具

站点工具

差别

页面工具