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

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXSIZE=10000020;
int bufpos;
char buf[MAXSIZE];
#define NEG 0
void init(){
	#ifdef LOCAL
		freopen("891A.txt","r",stdin);
	#endif
	buf[fread(buf,1,MAXSIZE,stdin)]='\0';
	bufpos=0;
}
#if NEG
int readint(){
	bool isneg;
	int val=0;
	for(;!isdigit(buf[bufpos]) && buf[bufpos]!='-';bufpos++);
	bufpos+=(isneg=buf[bufpos]=='-');
	for(;isdigit(buf[bufpos]);bufpos++)
		val=val*10+buf[bufpos]-'0';
	return isneg?-val:val;
}
#else
int readint(){
	int val=0;
	for(;!isdigit(buf[bufpos]);bufpos++);
	for(;isdigit(buf[bufpos]);bufpos++)
		val=val*10+buf[bufpos]-'0';
	return val;
}
#endif
char readchar(){
	for(;isspace(buf[bufpos]);bufpos++);
	return buf[bufpos++];
}
int readstr(char* s){
	int cur=0;
	for(;isspace(buf[bufpos]);bufpos++);
	for(;!isspace(buf[bufpos]);bufpos++)
		s[cur++]=buf[bufpos];
	s[cur]='\0';
	return cur;
}
int a[2003];
int main(){
	init();
	int n=readint(),ans=n+1;
	// puts("WTF");
	for(int i=1;i<=n;i++){
		a[i]=readint();
		int now=0;
		for(int j=i;j;j--){
			now=__gcd(now,a[j]);
			if (now==1){
				ans=min(ans,i-j+1);
				break;
			}
		}
	}
	// puts("WTF");
	if (ans>n)
		return puts("-1"),0;
	if (ans==1){
		int qwq=n;
		for(int i=1;i<=n;i++)
			qwq-=(a[i]==1);
		printf("%d\n",qwq);
		return 0;
	}
	printf("%d",ans-1+n-1);
}

B. Gluttony

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

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

证明：

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

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXSIZE=10000020;
int bufpos;
char buf[MAXSIZE];
#define NEG 0
void init(){
	#ifdef LOCAL
		freopen("891B.txt","r",stdin);
	#endif
	buf[fread(buf,1,MAXSIZE,stdin)]='\0';
	bufpos=0;
}
#if NEG
int readint(){
	bool isneg;
	int val=0;
	for(;!isdigit(buf[bufpos]) && buf[bufpos]!='-';bufpos++);
	bufpos+=(isneg=buf[bufpos]=='-');
	for(;isdigit(buf[bufpos]);bufpos++)
		val=val*10+buf[bufpos]-'0';
	return isneg?-val:val;
}
#else
int readint(){
	int val=0;
	for(;!isdigit(buf[bufpos]);bufpos++);
	for(;isdigit(buf[bufpos]);bufpos++)
		val=val*10+buf[bufpos]-'0';
	return val;
}
#endif
char readchar(){
	for(;isspace(buf[bufpos]);bufpos++);
	return buf[bufpos++];
}
int readstr(char* s){
	int cur=0;
	for(;isspace(buf[bufpos]);bufpos++);
	for(;!isspace(buf[bufpos]);bufpos++)
		s[cur++]=buf[bufpos];
	s[cur]='\0';
	return cur;
}
pair<int,int> a[233];
int ans[233];
int main(){
	init();
	int n=readint();
	for(int i=1;i<=n;i++)
		a[i].first=readint(),a[i].second=i;
	sort(a+1,a+n+1);
	for(int i=1;i<n;i++)
		ans[a[i].second]=a[i+1].first;
	ans[a[n].second]=a[1].first;
	for(int i=1;i<=n;i++)
		printf("%d ",ans[i]);
}
//1 2 3 4
//2 3 4 1

C. Envy

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

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

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

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXSIZE=100000020;
int bufpos;
char buf[MAXSIZE];
#define NEG 0
void init(){
	#ifdef LOCAL
		freopen("891C.txt","r",stdin);
	#endif
	buf[fread(buf,1,MAXSIZE,stdin)]='\0';
	bufpos=0;
}
#if NEG
int readint(){
	bool isneg;
	int val=0;
	for(;!isdigit(buf[bufpos]) && buf[bufpos]!='-';bufpos++);
	bufpos+=(isneg=buf[bufpos]=='-');
	for(;isdigit(buf[bufpos]);bufpos++)
		val=val*10+buf[bufpos]-'0';
	return isneg?-val:val;
}
#else
int readint(){
	int val=0;
	for(;!isdigit(buf[bufpos]);bufpos++);
	for(;isdigit(buf[bufpos]);bufpos++)
		val=val*10+buf[bufpos]-'0';
	return val;
}
#endif
char readchar(){
	for(;isspace(buf[bufpos]);bufpos++);
	return buf[bufpos++];
}
int readstr(char* s){
	int cur=0;
	for(;isspace(buf[bufpos]);bufpos++);
	for(;!isspace(buf[bufpos]);bufpos++)
		s[cur++]=buf[bufpos];
	s[cur]='\0';
	return cur;
}
const int maxn=500002;
struct dsu{
	int fa[maxn],rk[maxn];
	pair<int,int> stk[maxn*20];
	int tp;
	void init(int n){
		for(int i=1;i<=n;i++)
			fa[i]=i,rk[i]=0;
		tp=0;
	}
	void revert(int ver){
		while(tp!=ver){
			int x=stk[tp].first,y=stk[tp].second;
			if (x>0)
				fa[x]=y;
			else rk[-x]=y;
			tp--;
		}
	}
	int getf(int x){
		while(fa[x]!=x)
			x=fa[x];
		return x;
	}
	bool mer(int x,int y){
		x=getf(x),y=getf(y);
		if (x==y)
			return false;
		if (rk[x]>rk[y])
			swap(x,y);
		stk[++tp]=make_pair(x,fa[x]);
		stk[++tp]=make_pair(-y,rk[y]);
		fa[x]=y;
		rk[y]=max(rk[y],rk[x]+1);
		return true;
	}
}d;
struct edge{
	int u,v,w,id;
	bool operator <(const edge& rhs)const{
		return w<rhs.w;
	}
}e[maxn];
int to[maxn],lst[maxn];
struct query{
	int id;
	vector<int> a;
};
vector<query> q[maxn];
bool ans[maxn];
int main(){
	init();
	int n=readint(),m=readint();
	for(int i=1;i<=m;i++)
		e[i].id=i,e[i].u=readint(),e[i].v=readint(),e[i].w=readint();
	sort(e+1,e+m+1);
	for(int i=1;i<=m;i++){
		to[e[i].id]=i;
		lst[i]=e[i].w==e[i-1].w?lst[i-1]:i;
	}
	int cnt=readint();
	for(int i=1;i<=cnt;i++){
		ans[i]=1;
		int k=readint();
		while(k--){
			int p=to[readint()];
			if (q[lst[p]].empty() || q[lst[p]].back().id!=i)
				q[lst[p]].push_back((query){i});
			q[lst[p]].back().a.push_back(p);
		}
	}
	d.init(n);
	for(int i=1;i<=m;i++){
		if (q[i].size()){
			for(const auto& u:q[i]){
				int ver=d.tp;
				for(const auto& v:u.a){
					if (!d.mer(e[v].u,e[v].v)){
						ans[u.id]=0;
						break;
					}
				}
				d.revert(ver);
			}
		}
		d.mer(e[i].u,e[i].v);
	}
	for(int i=1;i<=cnt;i++)
		puts(ans[i]?"YES":"NO");
}

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

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXSIZE=10000020;
int bufpos;
char buf[MAXSIZE];
#define NEG 0
void init(){
	#ifdef LOCAL
		freopen("891E.txt","r",stdin);
	#endif
	buf[fread(buf,1,MAXSIZE,stdin)]='\0';
	bufpos=0;
}
#if NEG
int readint(){
	bool isneg;
	int val=0;
	for(;!isdigit(buf[bufpos]) && buf[bufpos]!='-';bufpos++);
	bufpos+=(isneg=buf[bufpos]=='-');
	for(;isdigit(buf[bufpos]);bufpos++)
		val=val*10+buf[bufpos]-'0';
	return isneg?-val:val;
}
#else
int readint(){
	int val=0;
	for(;!isdigit(buf[bufpos]);bufpos++);
	for(;isdigit(buf[bufpos]);bufpos++)
		val=val*10+buf[bufpos]-'0';
	return val;
}
#endif
char readchar(){
	for(;isspace(buf[bufpos]);bufpos++);
	return buf[bufpos++];
}
int readstr(char* s){
	int cur=0;
	for(;isspace(buf[bufpos]);bufpos++);
	for(;!isspace(buf[bufpos]);bufpos++)
		s[cur++]=buf[bufpos];
	s[cur]='\0';
	return cur;
}
const int mod=1000000007;
ll a[5003];
ll power(ll x,ll y){
	ll ans=1;
	while(y){
		if (y&1)
			ans=ans*x%mod;
		x=x*x%mod;
		y>>=1;
	}
	return ans;
}
int main(){
	init();
	int n=readint();
	ll k=readint(),ans=1;
	a[0]=1;
	for(int i=1;i<=n;i++){
		ll x=readint();
		ans=ans*x%mod;
		for(int j=i-1;j>=0;j--){
			a[j+1]=(a[j+1]-a[j])%mod;
			a[j]=a[j]*x%mod;
		}
	}
	ll now=1,pw=1;
	ll inv=power(n,mod-2);
	for(int i=0;i<=n;i++){
		ans=(ans-now*pw%mod*a[i])%mod;
		now=now*(k-i)%mod;
		pw=pw*inv%mod;
	}
	printf("%lld",(ans%mod+mod)%mod);
}

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

隐藏