agc027 ABCD 题解

109 阅读 0 评论 72 点赞

我是靠谱客的博主谨慎指甲油，这篇文章主要介绍agc027 ABCD 题解，现在分享给大家，希望可以做个参考。

题目链接：https://agc027.contest.atcoder.jp

A. Candy Distribution Again
睿智题不说了，贪心即可

复制代码

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
// by Balloons
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define mpr make_pair
#define debug() puts("okkkkkkkk")
#define rep(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)

using namespace std;

typedef long long LL;

const int inf = 1 << 30;

int n,k;
int a[105];

int main(){
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	sort(a+1,a+n+1);
	int ans=0,i;
	for(i=1;i<=n;i++){
		if(a[i]<=k){
			k-=a[i];
			++ans;
		}else break;
	}
	if(i==n+1&&k)--ans;
	printf("%dn",ans);

	return 0;
}

B. Garbage Collector
推一下式子发现当 $n = 4$ 时，不妨设表示位置的四元组为 $(a, b, c, d) [a \leq b \leq c \leq d]$ ，那么有
$d + (d - c) * 4 + (c - b) * 9 + (b - a) * 16 + a * 25 = 5 d + 5 c + 7 b + 9 a$
显然让 $d$ 最大时最优
同理也可以扩展到更多个数
所以可以枚举需要走 $k$ 个来回，那么最大的那 $k$ 个数的系数就是5，次大的 $k$ 个数系数为5，再次大的 $k$ 个数系数为7 $\dots$ 计算即可，最后需要加上一个额外的捡的时间 $(n + k) \times x$
会爆longlong需要判断

代码：

复制代码

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
// by Balloons
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define mpr make_pair
#define debug() puts("okkkkkkkk")
#define rep(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)

using namespace std;

typedef unsigned long long ULL;
typedef long long LL;

const int inf = 1 << 30;
const int maxn=2e5+5;

ULL n,x;
ULL a[maxn],sum[maxn];

int main(){
	scanf("%llu%llu",&n,&x);
	for(int i=1;i<=n;i++)scanf("%llu",&a[i]),sum[i]=sum[i-1]+a[i];
	ULL ans=1ll<<60;
	for(LL k=1;k<=n;k++){
		ULL res=0,base=5;
		for(LL i=n;i>=1;i-=k){
			ULL tmp;
			if(i-k<=0)tmp=sum[i]-sum[0];
			else tmp=sum[i]-sum[i-k];
//			printf("%llu n",tmp);
			if(i==n){
				res+=tmp*base;
			}else res+=tmp*base,base+=2;
			if(res+(n+k)*x>ans)break;
		}
		ans=min(ans,res+(n+k)*x);
	}
	printf("%llun",ans);

	return 0;
}

C. ABland Yard
这题我yy除了无数种解法都被自己叉掉了QwQ
去膜了题解，~~差一点就想到了5555~~
一个基础的图形是A-A’ B-B’ A-B’ A’-B，我卡在怎么快速判断是否存在了，其实不需要，直接找不符合的并删掉所有边，再找不符合的，过程类似拓扑排序，最后看是否有满足条件的点即可

复制代码

// by Balloons
#include <cstdio>
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>
#define mpr make_pair
#define debug() puts("okkkkkkkk")
#define rep(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)

using namespace std;

typedef long long LL;

const int inf = 1 << 30;

const int maxn=2e5+5;
char s[maxn];
int n,m;
vector<int>g[maxn]; 
int vis[maxn];
int cnt[maxn][3];

void dfs(int x){
	vis[x]=1;
	for(int i=0;i<g[x].size();i++){
		int u=g[x][i];
		if(vis[u])continue;
//		printf("%d %d %dn",u,s[x]-'A',cnt[u][s[x]-'A']);
		--cnt[u][s[x]-'A'];
		if(cnt[u][0]==0||cnt[u][1]==0)dfs(u);
	}
}

int main(){
	scanf("%d%d",&n,&m);
	scanf("%s",s+1);
	for(int i=1;i<=m;i++){
		int x,y;scanf("%d%d",&x,&y);
		g[x].push_back(y);g[y].push_back(x);
		cnt[x][s[y]-'A']++;cnt[y][s[x]-'A']++;
	}
	for(int i=1;i<=n;i++){
//		printf("i=%d,cnt[][]=%d %dn",i,cnt[i][0],cnt[i][1]);
		if(!vis[i]&&(cnt[i][0]==0||cnt[i][1]==0))dfs(i);
	}
	for(int i=1;i<=n;i++){
		if(!vis[i]){
//			printf("i=%dn",i);
			return puts("Yes"),0;
		}
	}
	puts("No");

return 0;
}

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
// by Balloons
#include <cstdio>
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>
#define mpr make_pair
#define debug() puts("okkkkkkkk")
#define rep(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)

using namespace std;

typedef long long LL;

const int inf = 1 << 30;

const int maxn=2e5+5;
char s[maxn];
int n,m;
vector<int>g[maxn]; 
int vis[maxn];
int cnt[maxn][3];

void dfs(int x){
	vis[x]=1;
	for(int i=0;i<g[x].size();i++){
		int u=g[x][i];
		if(vis[u])continue;
//		printf("%d %d %dn",u,s[x]-'A',cnt[u][s[x]-'A']);
		--cnt[u][s[x]-'A'];
		if(cnt[u][0]==0||cnt[u][1]==0)dfs(u);
	}
}

int main(){
	scanf("%d%d",&n,&m);
	scanf("%s",s+1);
	for(int i=1;i<=m;i++){
		int x,y;scanf("%d%d",&x,&y);
		g[x].push_back(y);g[y].push_back(x);
		cnt[x][s[y]-'A']++;cnt[y][s[x]-'A']++;
	}
	for(int i=1;i<=n;i++){
//		printf("i=%d,cnt[][]=%d %dn",i,cnt[i][0],cnt[i][1]);
		if(!vis[i]&&(cnt[i][0]==0||cnt[i][1]==0))dfs(i);
	}
	for(int i=1;i<=n;i++){
		if(!vis[i]){
//			printf("i=%dn",i);
			return puts("Yes"),0;
		}
	}
	puts("No");

	return 0;
}

D. Modulo Matrix
论读懂题的必要性
一个直观的想法（我的想法）是直接黑白染色，黑格子随便填，白格子填所有相邻的格子的lcm+1，这样 $m = 1$ ，但是这样填的话 $a_{i,j}$ 最大是 $9223216780099161841 > 10^{15}$ ，不可行
然后又去膜了题解，注意到一个黑格子对应的两个方向的对角线的交点，一个显然的想法是将对角线都赋成质数，一共要付 $2 n = 1000$ 个数（为什么是质数因为lcm之后质数不会出现重复）， $max(a_{i,j})=lcm(pm[499],pm[500],pm[999],pm[1000])+1=795792643232738<10^{15}$ （这是理论上的），符合要求
PS：我跑出来最大值是 $165863181591344$ ，不太清楚原理，有懂的dalao可以评论下告诉我感激不尽QwQ
代码：

复制代码

// by Balloons
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define mpr make_pair
#define debug() puts("okkkkkkkk")
#define rep(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
 
using namespace std;
 
typedef long long LL;
 
const int inf = 1 << 30;
 
int n;
LL a[505][505];
 
LL gcd(LL a,LL b){
	return !b?a:gcd(b,a%b);
}
LL lcm(LL a,LL b){
	if(a==0)return b;
	if(b==0)return a;
	return a/gcd(a,b)*b;
}
 
int notpm[100005],pm[100005],pcnt=0;
void xxs(){
	notpm[1]=1;
	for(int i=2;i<=100000;i++){
		if(!notpm[i]){
			pm[++pcnt]=i;
		}
		for(int j=1;pm[j]*i<=100000&&j<=pcnt;j++){
			notpm[i*pm[j]]=1;
			if(i%pm[j]==0)break;
		}
	}
}
 
int main(){
	LL cnt=0;
	scanf("%d",&n);
	if(n==2){
		puts("4 7n23 10");
		return 0;
	}
	xxs();
	
	for(int i=1;i<=n;i++){
		for(int j=(i%2==0)+1;j<=n;j+=2){
			a[i][j]=pm[(i+j)/2];
		}
	}
	
	for(int i=1;i<=n;i++){
		for(int j=(i%2==0)+1;j<=n;j+=2){
//			printf("%d %d %dn",i,j,n+(j-i+1)/2+2);
			a[i][j]*=pm[n+(j-i+((j-i)%2==0?0:1))/2+2];
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(!a[i][j]){
				a[i][j]=lcm(lcm(lcm(a[i-1][j],a[i][j-1]),a[i][j+1]),a[i+1][j])+1;
			}
		}
	}
	LL mx=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
//			if(a[i][j]==9223216780099161841){
//				printf("%d %d %lld %lld %lld %lldn",i,j,a[i-1][j],a[i+1][j],a[i][j-1],a[i][j+1]);
//			}
//			mx=max(mx,a[i][j]);
			printf("%lld ",a[i][j]);
		}
		puts("");
	}
//	printf("%lldn",mx);
 
	return 0;
}

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
78
79
80
81
82
83
84
85
// by Balloons
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define mpr make_pair
#define debug() puts("okkkkkkkk")
#define rep(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
 
using namespace std;
 
typedef long long LL;
 
const int inf = 1 << 30;
 
int n;
LL a[505][505];
 
LL gcd(LL a,LL b){
	return !b?a:gcd(b,a%b);
}
LL lcm(LL a,LL b){
	if(a==0)return b;
	if(b==0)return a;
	return a/gcd(a,b)*b;
}
 
int notpm[100005],pm[100005],pcnt=0;
void xxs(){
	notpm[1]=1;
	for(int i=2;i<=100000;i++){
		if(!notpm[i]){
			pm[++pcnt]=i;
		}
		for(int j=1;pm[j]*i<=100000&&j<=pcnt;j++){
			notpm[i*pm[j]]=1;
			if(i%pm[j]==0)break;
		}
	}
}
 
int main(){
	LL cnt=0;
	scanf("%d",&n);
	if(n==2){
		puts("4 7n23 10");
		return 0;
	}
	xxs();
	
	for(int i=1;i<=n;i++){
		for(int j=(i%2==0)+1;j<=n;j+=2){
			a[i][j]=pm[(i+j)/2];
		}
	}
	
	for(int i=1;i<=n;i++){
		for(int j=(i%2==0)+1;j<=n;j+=2){
//			printf("%d %d %dn",i,j,n+(j-i+1)/2+2);
			a[i][j]*=pm[n+(j-i+((j-i)%2==0?0:1))/2+2];
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(!a[i][j]){
				a[i][j]=lcm(lcm(lcm(a[i-1][j],a[i][j-1]),a[i][j+1]),a[i+1][j])+1;
			}
		}
	}
	LL mx=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
//			if(a[i][j]==9223216780099161841){
//				printf("%d %d %lld %lld %lld %lldn",i,j,a[i-1][j],a[i+1][j],a[i][j-1],a[i][j+1]);
//			}
//			mx=max(mx,a[i][j]);
			printf("%lld ",a[i][j]);
		}
		puts("");
	}
//	printf("%lldn",mx);
 
	return 0;
}