抱歉，您的浏览器无法访问本站
本页面需要浏览器支持（启用）JavaScript
了解详情 >

Codeforces Round #589 (Div. 2)

发布于：2019年9月30日

比赛传送门

Pro1Pro1

传送门

让你找到任意一个数x∈[l,r]x \in [l,r]，使得xx的各位数字都不同。

Sol1Sol1

注意到1≤l≤r≤1051 \le l \le r \le 10^5，每个数最多55位。

于是硬上O(nlog⁡10n)O(n \log _{10} n)大模拟即可。

Code1Code1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>
#define MAXN 2000005
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9'){
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9'){
        x=(x<<3)+(x<<1)+(ch^'0');
        ch=getchar();
    }
    return x*f;
}
inline int Check(int x){
	int cnt[10];
	memset(cnt,0,sizeof(cnt));
	while (x) {
		cnt[x%10]++;
		x/=10;
	}
	for (register int i=0;i<=9;++i){
		if (cnt[i]>1) return false;
	}
	return true;
}
int main(){
	int l=read(),r=read();
	for (register int i=l;i<=r;++i){
		if (Check(i)){
			printf("%d\n",i);
			return 0;
		}
	}
	puts("-1");
	return 0;
}

Pro2Pro2

传送门

给你两个数列r[i],c[i]r[i],c[i]，要你构造一个长hh宽ww的格子图，使得第ii个纵列从最上面数起刚好有c[i]c[i]个连续的黑色格子，第ii个横列从最左边数起刚好有r[i]r[i]个连续的黑色格子。

求满足条件的格子图的总数。

Sol2Sol2

设这个图是mapmap，注意到map[i][1→r[i]]map[i][1 \to r[i]]都必须是黑色的，map[i][r[i]+1]map[i][r[i]+1]为白色的，对于c[i]c[i]也是同理。

如果这样染色出现冲突，答案就是00。

发现剩下的格子都可以随意染色，于是答案就是2未被染色的格子个数2^{未被染色的格子个数}

Code2Code2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <bits/stdc++.h>
#define MAXN 2000005
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9'){
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9'){
        x=(x<<3)+(x<<1)+(ch^'0');
        ch=getchar();
    }
    return x*f;
}
int a[1005][1005];
int main(){
	int h=read(),w=read();
	memset(a,-1,sizeof(a));
	for (register int i=1;i<=h;++i){
		int len=read();
		for (register int j=1;j<=len;++j){
			if (a[i][j]==0){//出现冲突
				puts("0");
				return 0;
			}
			a[i][j]=1;
		}
		if (a[i][len+1]==1){
			puts("0");
			return 0;
		}
		a[i][len+1]=0;
	}
	for (register int i=1;i<=w;++i){
		int len=read();
		for (register int j=1;j<=len;++j){
			if (a[j][i]==0){
				puts("0");
				return 0;
			}
			a[j][i]=1;
		}
		if (a[len+1][i]==1){
			puts("0");
			return 0;
		}
		a[len+1][i]=0;
	}
	long long ans=1;
	for (register int i=1;i<=h;++i){
		for (register int j=1;j<=w;++j){
			if (a[i][j]==-1) ans=(ans*2ll)%((long long)1e9+7);//没被染色
		}
	}
	printf("%lld\n",ans);
}

Pro3Pro3

传送门

定义prime(x)prime(x)为xx的质因子的集合，比如说prime(140)=2,5,7prime(140)=\\{2,5,7\\}

设g(x,p)g(x,p)是能够整除xx的最大的pkp^k，比如说g(45,3)=9g(45,3)=9

设f(x,y)f(x,y)为∏p∈prime(x)g(y,p)\prod _{p \in prime(x)} g(y,p)，比如说f(30,70)=g(70,2)⋅g(70,3)⋅g(70,5)=21⋅30⋅51=10f(30, 70) = g(70, 2) \cdot g(70, 3) \cdot g(70, 5) = 2^1 \cdot 3^0 \cdot 5^1 = 10

给你x,nx,n，计算∏i=1nf(x,i)\prod _{i=1}^n f(x,i)

Sol3Sol3

数论不会先打表

先计算一下x=10,n=10x=10,n=10的情况：

f(10,1)=1f(10,1)=1 f(10,2)=2f(10,2)=2 f(10,3)=1f(10,3)=1 f(10,4)=4f(10,4)=4 f(10,5)=5f(10,5)=5

f(10,6)=2f(10,6)=2 f(10,7)=1f(10,7)=1 f(10,8)=8f(10,8)=8 f(10,9)=1f(10,9)=1 f(10,10)=10f(10,10)=10

如何考虑，不妨对prime(x)prime(x)中的元素分别考虑，考虑质因子22对答案的贡献，他会分别对f(x,2×i)f(x,2 \times i)做出一个22的贡献，同时对f(x,22×i)f(x,2^2 \times i)做出一个22的贡献，对f(x,23×i)f(x,2^3 \times i)做出一个22的贡献。

于是总的贡献是2⌊n/2⌋×2⌊n/22⌋×2⌊n/23⌋...2^ {⌊n/2⌋} \times 2 ^ {⌊n/2^2⌋} \times 2^{⌊n/2^3⌋} ...

于是我们得到核心代码：

1
2
3
4
5
6
7
inline int Calc(int x,int n){
	while (n){
		ans=(ans*ksm(x,n/x,MOD))%MOD;
		n/=x;
	}
	return 0;
}

就是计算每一个质因子xx对于答案的贡献。

Code3Code3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <bits/stdc++.h>
#define MAXN 200005
#define int long long
#define MOD 1000000007
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9'){
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9'){
        x=(x<<3)+(x<<1)+(ch^'0');
        ch=getchar();
    }
    return x*f;
}
int ans=1;
inline int ksm(int b,int p,int k){
    int ans=1;
    while (p>0){
        if (p&1ll){
            ans=(b*ans)%k;
        }
        b=(b*b)%k;
        p>>=1ll;
    }
    return ans%MOD;
}
inline int Calc(int x,int n){
	while (n){
		ans=(ans*ksm(x,n/x,MOD))%MOD;
		n/=x;
	}
	return 0;
}
int cnt,primes[MAXN];
inline void Sieve(int x){
	int bd=sqrt(x);
	for (register int i=2;i<=bd;++i){
		if (x%i==0){
			primes[++cnt]=i;
			while (x%i==0) x/=i;
		}
	}
	if (x>1) primes[++cnt]=x;//x是质数
}
#undef int
int main(){
#define int long long
	int x,n;
	cin>>x>>n;
	Sieve(x);//找出x的所有质因子
	for (register int i=1;i<=cnt;++i){
		Calc(primes[i],n);
	}
	cout<<ans;
}

Pro4Pro4

传送门

称两个点集v1,v2v_1,v_2是好的，当且仅当v1,v2v_1,v_2之间没有连边，而且任意x∈v1,y∈v2x \in v_1,y \in v_2，x,yx,y都有边相连。

要你把1…n1 \dots n的点分成33个集合v1,v2,v3v_1,v_2,v_3，满足v1∪v2∪v3=1…nv_1 ∪ v_2 ∪ v_3 = \\{1 \dots n\\}，而且v1,v2v_1,v_2是好的，v2,v3v_2,v_3是好的，v3,v1v_3,v_1是好的。

如下图1,2,3,4,5,6\\{1\\},\\{2,3\\},\\{4,5,6\\}就是一个合法的解。

Sol4Sol4

首先，这个图如果不联通，就无解。

仔细观察上图，发现从一个点连出的边，总是到达和这个点不属于同一个集合的一个点，我们可以利用这个性质。

首先，令点11所在的集合编号为11，显然，将11连出的边遍历一遍，就可以找到不在11中的点，剩下的点在集合11。

1
2
3
for (register int i=0;i<G[1].size();++i){
	vis[G[1][i]]=true;//标记2,3组
}

在从标记到的点集中随便抽出一个点uu，钦定它在集合22中，那么它能够到达的点肯定是在集合1,31,3中，此时11集合中的点我们已经知道了，于是33集合我们也可以知道是那些。

1
2
3
4
5
6
7
8
9
10
11
12
13
bool flag=true;
for (register int i=1;i<=n;++i){
	if (!vis[i]){
		ans[i]=1;
	}
	else if (vis[i]&&flag){
		for (register int j=0;j<G[i].size();++j){//这次到达的是1,3组
			int v=G[i][j];
			if (vis[v]) ans[v]=3;
		}
		flag=false;
	}
}

下面是麻烦的验证过程：

首先，计算出在集合11，22，33中的点数cnt1,cnt2,cnt3cnt1,cnt2,cnt3

注意到cnt1!=0,cnt2!=0,cnt3!=0cnt1 !=0,cnt2!=0,cnt3!=0且cnt1∗cnt2+cnt2∗cnt3+cnt1∗cnt3=mcnt1*cnt2+cnt2*cnt3+cnt1*cnt3=m。

而且和每个点相邻的所有点都在另外两个集合中，可以根据这个性质进一步验证。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int cnt1=0,cnt2=0,cnt3=0;
for (register int i=1;i<=n;++i){
	if (ans[i]==0) ans[i]=2;
	if (ans[i]==1) cnt1++;
	if (ans[i]==2) cnt2++;
	if (ans[i]==3) cnt3++;	
}
if (cnt1==0||cnt2==0||cnt3==0) return puts("-1"),0;
if (cnt1*cnt2+cnt2*cnt3+cnt3*cnt1!=m) return puts("-1"),0;

int c[4];
for (register int i=1;i<=n;++i){
	memset(c,0,sizeof(c));
	for (register int j=0;j<G[i].size();++j){
		c[ans[G[i][j]]]++;
	}
	if (c[ans[i]]!=0) return puts("-1"),0;//两个点在同一个集合
	if (ans[i]==1) if (c[2]!=cnt2||c[3]!=cnt3) return puts("-1"),0;//和不相等
	if (ans[i]==2) if (c[1]!=cnt1||c[3]!=cnt3) return puts("-1"),0;
	if (ans[i]==3) if (c[1]!=cnt1||c[2]!=cnt2) return puts("-1"),0;
}

Code4Code4

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <bits/stdc++.h>
#define MAXN 300005
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9'){
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9'){
        x=(x<<3)+(x<<1)+(ch^'0');
        ch=getchar();
    }
    return x*f;
}
int deg[MAXN],vis[MAXN];
int vised[MAXN];
vector<int>G[MAXN];
inline void dfs(int u){
	vised[u]=true;
	for (register int i=0;i<G[u].size();++i){
		if (!vised[G[u][i]]) dfs(G[u][i]);
	}
}
int ans[MAXN];
int main(){
	int n=read(),m=read();
	for (register int i=1;i<=m;++i){
		int u=read(),v=read();
		G[u].push_back(v),G[v].push_back(u);
		deg[u]++,deg[v]++;
	}
	dfs(1);
	for (register int i=1;i<=n;++i){
		if (!vised[i]) return puts("-1"),0;//判断联通
	}
	for (register int i=0;i<G[1].size();++i){
		vis[G[1][i]]=true;//标记2,3组
	}
	bool flag=true;
	for (register int i=1;i<=n;++i){
		if (!vis[i]){
			ans[i]=1;
		}
		else if (vis[i]&&flag){
			for (register int j=0;j<G[i].size();++j){//这次到达的是1,3组
				int v=G[i][j];
				if (vis[v]) ans[v]=3;
			}
			flag=false;
		}
	}
	int cnt1=0,cnt2=0,cnt3=0;
	for (register int i=1;i<=n;++i){
		if (ans[i]==0) ans[i]=2;
		if (ans[i]==1) cnt1++;
		if (ans[i]==2) cnt2++;
		if (ans[i]==3) cnt3++;
	}
	if (cnt1==0||cnt2==0||cnt3==0) return puts("-1"),0;
	if (cnt1*cnt2+cnt2*cnt3+cnt3*cnt1!=m) return puts("-1"),0;
	int c[4];
	for (register int i=1;i<=n;++i){
		memset(c,0,sizeof(c));
		for (register int j=0;j<G[i].size();++j){
			c[ans[G[i][j]]]++;
		}
		if (c[ans[i]]!=0) return puts("-1"),0;
		if (ans[i]==1) if (c[2]!=cnt2||c[3]!=cnt3) return puts("-1"),0;
		if (ans[i]==2) if (c[1]!=cnt1||c[3]!=cnt3) return puts("-1"),0;
		if (ans[i]==3) if (c[1]!=cnt1||c[2]!=cnt2) return puts("-1"),0;
	}
	for (register int i=1;i<=n;++i){
		printf("%d ",ans[i]);
	}
}
相关文章
Codeforces Round #583 (Div. 1 + Div. 2, based on Olympiad of Metropolises)P5002 专心OI - 找祖先基本概念

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：https://gaisaiyuno.github.io/archives/9b983113.html

更新于：2022年6月14日

比赛

评论