Codeforces Round 446 (Div. 1) 题解

Author Avatar
q234rty 7月 12, 2018

施工中QwQ

A. Pride

首先如果原序列中已经有 1 ，答案是 n 减去 1 的个数。

否则一定是先构造出一个 1 ，然后再用 n-1 步全部变成 1 。

设最短的 \gcd 为 1 的区间长度为 l ，那么答案为 n+l-2 。

时间复杂度 O(n^2 + n\log a_i) ，维护不同的 \gcd 可以做到 O(n \log a_i) 。

Code

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. const int MAXSIZE=10000020;
  5. int bufpos;
  6. char buf[MAXSIZE];
  7. #define NEG 0
  8. void init(){
  9. 	#ifdef LOCAL
  10. 		freopen("891A.txt","r",stdin);
  11. 	#endif
  12. 	buf[fread(buf,1,MAXSIZE,stdin)]='\0';
  13. 	bufpos=0;
  14. }
  15. #if NEG
  16. int readint(){
  17. 	bool isneg;
  18. 	int val=0;
  19. 	for(;!isdigit(buf[bufpos]) && buf[bufpos]!='-';bufpos++);
  20. 	bufpos+=(isneg=buf[bufpos]=='-');
  21. 	for(;isdigit(buf[bufpos]);bufpos++)
  22. 		val=val*10+buf[bufpos]-'0';
  23. 	return isneg?-val:val;
  24. }
  25. #else
  26. int readint(){
  27. 	int val=0;
  28. 	for(;!isdigit(buf[bufpos]);bufpos++);
  29. 	for(;isdigit(buf[bufpos]);bufpos++)
  30. 		val=val*10+buf[bufpos]-'0';
  31. 	return val;
  32. }
  33. #endif
  34. char readchar(){
  35. 	for(;isspace(buf[bufpos]);bufpos++);
  36. 	return buf[bufpos++];
  37. }
  38. int readstr(char* s){
  39. 	int cur=0;
  40. 	for(;isspace(buf[bufpos]);bufpos++);
  41. 	for(;!isspace(buf[bufpos]);bufpos++)
  42. 		s[cur++]=buf[bufpos];
  43. 	s[cur]='\0';
  44. 	return cur;
  45. }
  46. int a[2003];
  47. int main(){
  48. 	init();
  49. 	int n=readint(),ans=n+1;
  50. 	// puts("WTF");
  51. 	for(int i=1;i<=n;i++){
  52. 		a[i]=readint();
  53. 		int now=0;
  54. 		for(int j=i;j;j--){
  55. 			now=__gcd(now,a[j]);
  56. 			if (now==1){
  57. 				ans=min(ans,i-j+1);
  58. 				break;
  59. 			}
  60. 		}
  61. 	}
  62. 	// puts("WTF");
  63. 	if (ans>n)
  64. 		return puts("-1"),0;
  65. 	if (ans==1){
  66. 		int qwq=n;
  67. 		for(int i=1;i<=n;i++)
  68. 			qwq-=(a[i]==1);
  69. 		printf("%d\n",qwq);
  70. 		return 0;
  71. 	}
  72. 	printf("%d",ans-1+n-1);
  73. }

B. Gluttony

一直在想状压DP，看了题解才发现 n \leq 22 只是因为spj需要 O(2^n) 而已。

将每个数变成第一个比它大的数（如果不存在则变成最小的数）即可。

证明：

对于每个不包含原排列中最大数的下标集合显然成立，否则考虑取补集可以发现仍然成立。

Code

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. const int MAXSIZE=10000020;
  5. int bufpos;
  6. char buf[MAXSIZE];
  7. #define NEG 0
  8. void init(){
  9. 	#ifdef LOCAL
  10. 		freopen("891B.txt","r",stdin);
  11. 	#endif
  12. 	buf[fread(buf,1,MAXSIZE,stdin)]='\0';
  13. 	bufpos=0;
  14. }
  15. #if NEG
  16. int readint(){
  17. 	bool isneg;
  18. 	int val=0;
  19. 	for(;!isdigit(buf[bufpos]) && buf[bufpos]!='-';bufpos++);
  20. 	bufpos+=(isneg=buf[bufpos]=='-');
  21. 	for(;isdigit(buf[bufpos]);bufpos++)
  22. 		val=val*10+buf[bufpos]-'0';
  23. 	return isneg?-val:val;
  24. }
  25. #else
  26. int readint(){
  27. 	int val=0;
  28. 	for(;!isdigit(buf[bufpos]);bufpos++);
  29. 	for(;isdigit(buf[bufpos]);bufpos++)
  30. 		val=val*10+buf[bufpos]-'0';
  31. 	return val;
  32. }
  33. #endif
  34. char readchar(){
  35. 	for(;isspace(buf[bufpos]);bufpos++);
  36. 	return buf[bufpos++];
  37. }
  38. int readstr(char* s){
  39. 	int cur=0;
  40. 	for(;isspace(buf[bufpos]);bufpos++);
  41. 	for(;!isspace(buf[bufpos]);bufpos++)
  42. 		s[cur++]=buf[bufpos];
  43. 	s[cur]='\0';
  44. 	return cur;
  45. }
  46. pair<int,int> a[233];
  47. int ans[233];
  48. int main(){
  49. 	init();
  50. 	int n=readint();
  51. 	for(int i=1;i<=n;i++)
  52. 		a[i].first=readint(),a[i].second=i;
  53. 	sort(a+1,a+n+1);
  54. 	for(int i=1;i<n;i++)
  55. 		ans[a[i].second]=a[i+1].first;
  56. 	ans[a[n].second]=a[1].first;
  57. 	for(int i=1;i<=n;i++)
  58. 		printf("%d ",ans[i]);
  59. }
  60. //1 2 3 4
  61. //2 3 4 1

C. Envy

算法导论上有这样一个结论：一张图的任何一个最小生成树均可以通过在Kruskal中改变相同权值的边的排列顺序得到。

于是考虑把每个询问中的边按权值分组，离线，然后在Kruskal的过程中判断一组中的边同时加入会不会产生环即可。需要带撤销的并查集，注意只需要按秩合并，路径压缩的复杂度是均摊的。

时间复杂度 O((m+\sum k) \log n) 。

Code

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. const int MAXSIZE=100000020;
  5. int bufpos;
  6. char buf[MAXSIZE];
  7. #define NEG 0
  8. void init(){
  9. 	#ifdef LOCAL
  10. 		freopen("891C.txt","r",stdin);
  11. 	#endif
  12. 	buf[fread(buf,1,MAXSIZE,stdin)]='\0';
  13. 	bufpos=0;
  14. }
  15. #if NEG
  16. int readint(){
  17. 	bool isneg;
  18. 	int val=0;
  19. 	for(;!isdigit(buf[bufpos]) && buf[bufpos]!='-';bufpos++);
  20. 	bufpos+=(isneg=buf[bufpos]=='-');
  21. 	for(;isdigit(buf[bufpos]);bufpos++)
  22. 		val=val*10+buf[bufpos]-'0';
  23. 	return isneg?-val:val;
  24. }
  25. #else
  26. int readint(){
  27. 	int val=0;
  28. 	for(;!isdigit(buf[bufpos]);bufpos++);
  29. 	for(;isdigit(buf[bufpos]);bufpos++)
  30. 		val=val*10+buf[bufpos]-'0';
  31. 	return val;
  32. }
  33. #endif
  34. char readchar(){
  35. 	for(;isspace(buf[bufpos]);bufpos++);
  36. 	return buf[bufpos++];
  37. }
  38. int readstr(char* s){
  39. 	int cur=0;
  40. 	for(;isspace(buf[bufpos]);bufpos++);
  41. 	for(;!isspace(buf[bufpos]);bufpos++)
  42. 		s[cur++]=buf[bufpos];
  43. 	s[cur]='\0';
  44. 	return cur;
  45. }
  46. const int maxn=500002;
  47. struct dsu{
  48. 	int fa[maxn],rk[maxn];
  49. 	pair<int,int> stk[maxn*20];
  50. 	int tp;
  51. 	void init(int n){
  52. 		for(int i=1;i<=n;i++)
  53. 			fa[i]=i,rk[i]=0;
  54. 		tp=0;
  55. 	}
  56. 	void revert(int ver){
  57. 		while(tp!=ver){
  58. 			int x=stk[tp].first,y=stk[tp].second;
  59. 			if (x>0)
  60. 				fa[x]=y;
  61. 			else rk[-x]=y;
  62. 			tp--;
  63. 		}
  64. 	}
  65. 	int getf(int x){
  66. 		while(fa[x]!=x)
  67. 			x=fa[x];
  68. 		return x;
  69. 	}
  70. 	bool mer(int x,int y){
  71. 		x=getf(x),y=getf(y);
  72. 		if (x==y)
  73. 			return false;
  74. 		if (rk[x]>rk[y])
  75. 			swap(x,y);
  76. 		stk[++tp]=make_pair(x,fa[x]);
  77. 		stk[++tp]=make_pair(-y,rk[y]);
  78. 		fa[x]=y;
  79. 		rk[y]=max(rk[y],rk[x]+1);
  80. 		return true;
  81. 	}
  82. }d;
  83. struct edge{
  84. 	int u,v,w,id;
  85. 	bool operator <(const edge& rhs)const{
  86. 		return w<rhs.w;
  87. 	}
  88. }e[maxn];
  89. int to[maxn],lst[maxn];
  90. struct query{
  91. 	int id;
  92. 	vector<int> a;
  93. };
  94. vector<query> q[maxn];
  95. bool ans[maxn];
  96. int main(){
  97. 	init();
  98. 	int n=readint(),m=readint();
  99. 	for(int i=1;i<=m;i++)
  100. 		e[i].id=i,e[i].u=readint(),e[i].v=readint(),e[i].w=readint();
  101. 	sort(e+1,e+m+1);
  102. 	for(int i=1;i<=m;i++){
  103. 		to[e[i].id]=i;
  104. 		lst[i]=e[i].w==e[i-1].w?lst[i-1]:i;
  105. 	}
  106. 	int cnt=readint();
  107. 	for(int i=1;i<=cnt;i++){
  108. 		ans[i]=1;
  109. 		int k=readint();
  110. 		while(k--){
  111. 			int p=to[readint()];
  112. 			if (q[lst[p]].empty() || q[lst[p]].back().id!=i)
  113. 				q[lst[p]].push_back((query){i});
  114. 			q[lst[p]].back().a.push_back(p);
  115. 		}
  116. 	}
  117. 	d.init(n);
  118. 	for(int i=1;i<=m;i++){
  119. 		if (q[i].size()){
  120. 			for(const auto& u:q[i]){
  121. 				int ver=d.tp;
  122. 				for(const auto& v:u.a){
  123. 					if (!d.mer(e[v].u,e[v].v)){
  124. 						ans[u.id]=0;
  125. 						break;
  126. 					}
  127. 				}
  128. 				d.revert(ver);
  129. 			}
  130. 		}
  131. 		d.mer(e[i].u,e[i].v);
  132. 	}
  133. 	for(int i=1;i<=cnt;i++)
  134. 		puts(ans[i]?"YES":"NO");
  135. }

D. Sloth

留坑

E. Lust

设第 i 个数被减了 b_i 次。

首先归纳可证 res=\prod_{i}a_i-\prod_{i}(a_i-b_i) 。

那么

\mathbb{E}_{res}=\prod_{i=1}^na_i-\frac{k!}{n^k}\sum_{b_1+b_2+\cdots+b_n=k}\prod_{i=1}^n\frac{a_i-b_i}{b_i!}

注意到

\begin{aligned} \sum_{b_1+b_2+\cdots+b_n=k}\prod_{i=1}^n\frac{a_i-b_i}{b_i!}&=[x^k]\prod_{i=1}^n\sum_{j=0}^k\frac{a_i-j}{j!}x^j \\ &=[x^k]\prod_{i=1}^n(a_ie^x-xe^x)\\ &=[x^k]e^{nx}\prod_{i=1}^n(a_i-x) \end{aligned}

设 \prod_{i=1}^n(a_i-x)=\sum_{i=0}^nc_ix^i ，我们 O(n^2) 暴力求出 c​ 。

于是

[x^k]e^{nx}\prod_{i=1}^n(a_i-x)=\sum_{i=0}^nc_i\frac{n^{k-i}}{(k-i)!}

那么

\mathbb{E}_{res}=\prod_{i=1}^na_i-\frac{k!}{n^k}\sum_{i=0}^nc_i\frac{n^{k-i}}{(k-i)!}=\prod_{i=1}^na_i-\sum_{i=0}^n\frac{k^\underline{i}}{n^i}c_i

时间复杂度 O(n^2) 。

Code

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. const int MAXSIZE=10000020;
  5. int bufpos;
  6. char buf[MAXSIZE];
  7. #define NEG 0
  8. void init(){
  9. 	#ifdef LOCAL
  10. 		freopen("891E.txt","r",stdin);
  11. 	#endif
  12. 	buf[fread(buf,1,MAXSIZE,stdin)]='\0';
  13. 	bufpos=0;
  14. }
  15. #if NEG
  16. int readint(){
  17. 	bool isneg;
  18. 	int val=0;
  19. 	for(;!isdigit(buf[bufpos]) && buf[bufpos]!='-';bufpos++);
  20. 	bufpos+=(isneg=buf[bufpos]=='-');
  21. 	for(;isdigit(buf[bufpos]);bufpos++)
  22. 		val=val*10+buf[bufpos]-'0';
  23. 	return isneg?-val:val;
  24. }
  25. #else
  26. int readint(){
  27. 	int val=0;
  28. 	for(;!isdigit(buf[bufpos]);bufpos++);
  29. 	for(;isdigit(buf[bufpos]);bufpos++)
  30. 		val=val*10+buf[bufpos]-'0';
  31. 	return val;
  32. }
  33. #endif
  34. char readchar(){
  35. 	for(;isspace(buf[bufpos]);bufpos++);
  36. 	return buf[bufpos++];
  37. }
  38. int readstr(char* s){
  39. 	int cur=0;
  40. 	for(;isspace(buf[bufpos]);bufpos++);
  41. 	for(;!isspace(buf[bufpos]);bufpos++)
  42. 		s[cur++]=buf[bufpos];
  43. 	s[cur]='\0';
  44. 	return cur;
  45. }
  46. const int mod=1000000007;
  47. ll a[5003];
  48. ll power(ll x,ll y){
  49. 	ll ans=1;
  50. 	while(y){
  51. 		if (y&1)
  52. 			ans=ans*x%mod;
  53. 		x=x*x%mod;
  54. 		y>>=1;
  55. 	}
  56. 	return ans;
  57. }
  58. int main(){
  59. 	init();
  60. 	int n=readint();
  61. 	ll k=readint(),ans=1;
  62. 	a[0]=1;
  63. 	for(int i=1;i<=n;i++){
  64. 		ll x=readint();
  65. 		ans=ans*x%mod;
  66. 		for(int j=i-1;j>=0;j--){
  67. 			a[j+1]=(a[j+1]-a[j])%mod;
  68. 			a[j]=a[j]*x%mod;
  69. 		}
  70. 	}
  71. 	ll now=1,pw=1;
  72. 	ll inv=power(n,mod-2);
  73. 	for(int i=0;i<=n;i++){
  74. 		ans=(ans-now*pw%mod*a[i])%mod;
  75. 		now=now*(k-i)%mod;
  76. 		pw=pw*inv%mod;
  77. 	}
  78. 	printf("%lld",(ans%mod+mod)%mod);
  79. }

知识共享许可协议
本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可。
本文链接：https://www.q234rty.top/2018/07/12/cf891/

隐藏