差别

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

--- 2020-2021:teams:acm_life_from_zero:5.02-5.08 [2020/05/08 20:40]
lak [题目]
+++ 2020-2021:teams:acm_life_from_zero:5.02-5.08 [2020/05/15 22:41] (当前版本)
holmium [姜维翰]
@@ 行 10: / 行 10: @@
 ===== 题目 =====
 TJOI2019 唱、跳、rap、篮球
 分类：生成函数、FFT
-一句话题意：有四类人排队，每类人分别喜欢唱、跳、rap、篮球，分别有a,b,c,d个人，队伍长度n。如果任意k，k，k+1,k+2,k+3四个位置上的人依次喜欢唱、跳、rap、篮球，则不合法，求和法的排列方法。n，a,b,c,d<=1e3
+一句话题意：有四类人排队，每类人分别喜欢唱、跳、rap、篮球，分别有a,b,c,d个人，队伍长度n。如果任意k，k，k+1,k+2,k+3四个位置上的人依次喜欢唱、跳、rap、篮球，则不合法，求合法的排列方法数 mod 998244353。n，a,b,c,d<=1e3
 解法：注意任意两个四人组不可能有交，分别求至少包含1，2，…，个四人组不合法，求法使用指数型生成函数，最后容斥
 <code cpp>
@@ 行 135: / 行 138: @@
 }
-<\code>
+</code>
-====== 本周推荐 ======
+====== 姜维翰 ======
-===== 李元恺 =====
+===== 专题 =====
+没有专题
+===== 比赛 =====
+没有比赛
+===== 题目 =====
+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>
+using namespace std;
+typedef long long ll;
+typedef double db;
+typedef complex<double> cp;
+typedef pair<int,int> pll;
+const int maxn=(int)5e5+9;
+const int maxm=(int)1e6+9;
+const ll mod=(ll)998244353;
+const db pi=acos(-1);
+const db eps=1e-15;
+#define dbg(x) cerr<<#x<<" is "<<x<<endl;
+ll e[maxn];
+ll tmp[maxn];
+ll sur[maxn];
+ll n;
+int ck(ll v){
+	int p=0;
+	int fl=0;
+	int pos;
+	for(int i=0;i<=n;i++){
+		if(!fl&&(p==n||v<=e[0]||(v>e[p-1]&&v<=e[p]))){
+			fl=1;
+			tmp[i]=v;
+			pos=i;
+		}else{
+			tmp[i]=e[p];
+			p++;
+		}
+	}
+	sur[n+1]=0;
+	for(int i=n;i>=0;i--){
+		sur[i]=sur[i+1]+tmp[i];
+		//printf("$%d\n",sur[i]);
+	}
+	for(int i=n-1;i>=0;i--){
+		int pp=upper_bound(tmp,tmp+n+1,n-i)-tmp;
+		pp=min(pp,i);
+		//printf("# %d %lld %d\n",i,sur[i+1],pp);
+		if(sur[i+1]>(n-i)*(n-i-1)+sur[0]-sur[pp]+(n-i)*(i-pp+1)){
+			if(i<=pos)return 1;
+			else return -1;
+		}
+	}
+	return 0;
+}
+void init(){
+	scanf("%d",&n);
+	for(int i=0;i<n;i++){
+		scanf("%lld",&e[i]);
+	}
+	sort(e,e+n);
+}
+int main(){
+	init();
+	ll sum=0;
+	for(int i=0;i<n;i++){
+		sum+=e[i];
+	}
+	ll bg,ed;
+	bg=0;
+	ed=((ll)n)*(n+1)-sum;
+	ed=min(ed,n);
+	ll mid;
+	while(bg<ed){
+		mid=(bg+ed)/2;
+		int f=ck(mid);
+		//dbg(f);
+		//dbg(mid);
+		if(f==-1){
+			bg=mid+1;
+		}else if(f==1){
+			ed=mid-1;
+		}else{
+			break;
+		}
+	}
+	if(bg==ed&&ck(bg)!=0){
+		printf("-1\n");
+		return 0;
+	}
+	//dbg(mid);
+	ll m1=mid;
+	while(bg<m1){
+		ll mm=(bg+m1)/2;
+		int f=ck(mm);
+		if(f){
+			bg=mm+1;
+		}else{
+			m1=mm;
+		}
+	}
+	ll m2=mid;
+	while(m2<ed){
+		ll mm=(m2+ed+1)/2;
+		int f=ck(mm);
+		if(f){
+			ed=mm-1;
+		}else{
+			m2=mm;
+		}
+	}
+	ll eo=sum&1;
+	for(ll i=bg;i<=ed;i++){
+		if(eo==(i&1)){
+			printf("%lld ",i);
+		}
+	}
+	cout<<endl;
+</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

用户工具

站点工具

差别

页面工具