2019-2020 ACM-ICPC Latin American Regional Programming Contest

字数统计: 2.9k字   |   阅读时长: 14分
训练题解
solved A B C D E F G H I J K L M
6 / 13 · · · · O Ø · · O · O O O
  • O：比赛时通过
  • Ø：赛后通过
  • !：比赛时尝试了未通过
  • ·：比赛时未尝试

总结：

  • longlong：E题因为亿点细节和longlong的问题wa了十发，K题单纯因为longlong的问题白给了四发。

比赛链接

E – Eggfruit Cake

solved by Tryna1

题意：给出一块蛋糕，蛋糕的块数就是字符串的长度，字符串只含有‘P’和‘E’两种字符，给出一个整数S，每次能取不大于S块蛋糕，并且至少含有一个‘E’，问一共有多少种取法。

题解：在当前字符串中取S长度的加入字符串的末尾（因为蛋糕是一个圆），然后开始遍历到‘E’的时候，假设这个区间内没有其他‘E’，个数就是从1加到S，若有其他‘E’，则要减去重复计数的个数，不难推出重复了计数了(1+s-i+pre)*(s-i+pre)/2次，pre是前一个E的位置。

AC代码 
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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
char ch[N];
int num[N], pre,s;
int main(){
	scanf("%s", ch + 1);
	int len = strlen(ch + 1);
	scanf("%d",&s);
	for(int i = 1; i <= s; i++)ch[i + len] = ch[i];
	ll ans = 0;
	for(int i = 2; i <= s; i++){
		if(ch[i] == 'E')	pre = i;
	}	
	for(int i = s + 1; i <= len + s; i++){
		if(ch[i] == 'E'){
			ll temp = ((ll)(s + 1) * (ll)s) / 2;
            	if(pre >= i - s + 1){
                	temp -= ((ll)(1+s-i+pre)*(ll)(s-i+pre)/2);
			}  
			ans += temp;
			pre = i;
		} 
	}
	printf("%lld", ans);
	return 0;
}

F. Fabricating Sculptures

solved by lllllan.(-)

题意： 有m个方块，底层须放置n个方块，并且上方的方块放置不能出现凹槽。上图为m=6 n=3的示例，左边合法方案，右边非法。求合法的方案数量。

题解： 想来想去也只能用dp来写啊，就算是这样，状态转移方程也推了很久很久。定义状态dp[s][res]表示底层有s个方块，上方还需摆放res个方块的方法总数。
  而当res - s > s时状态转移方程为：dp[s][res] = (s - 1) * dp[1][res - 1] + (s - 2) * dp[2][res - 2] + ... + dp[s][res - s] 。
  当res - s <= s 时状态转移方程为：dp[s][res] = (s - 1) * dp[1][res - 1] + (s - 2) * dp[2][res - 2] + ... + (s - res) * dp[res][0] 。

解释：当需要放置s个方块作为底层，上方还需要放置res个方块时。我们上方的放置的选择有，即dp[s][res]：

  • 底层放置一个方块：种类 + (s - 1) * dp[1][res - 1]。（注意是上方的res个方块的底层，区别于前面所述的底层s）
  • 底层放置两个方块：种类 + (s - 2) * dp[2][res - 2]。
  • ···
  • 底层放置t = min(res, s)个方块：种类 + (s - t) * dp[t][res - t]。

如此递推直到res = 0时，种类为1。因为状态转移方程比较特殊，比较冗长，我们不可能真的去多写一个for循环来递推。所以又引用了前缀和来辅助求值。

补充： 之前写的时候只是随口提了一下借助前缀和，但是当我过几天再看这个代码的时候，越发觉得这个前缀和真的太秒了（代码是从别处学来的，所以不是自夸）
  当s = 1时：

  • dp[1][0] = 1;
  • dp[1][1] = dp[1][0] = 1; //1 + 0 = 1 (res)
  • dp[1][2] = dp[1][1] = 1; //1 + 1 = 2 (res)
  • dp[1][3] = dp[1][2] = 1; //1 + 2 = 3 (res)
  • …
    当s = 2时：
  • dp[2][0] = 1;
  • dp[2][1] = 2 * dp[1][0] = 2; //1 + 0 = 1 (res)
  • dp[2][2] = 2 * dp[1][1] + dp[2][0] = 3; //1 + 1 = 2 + 0 = 2 (res)
  • dp[2][3] = 2 * dp[1][2] + dp[2][1] = 4; //1 + 2 = 2 + 1 = 3 (res)
  • …

为了避免篇幅太长，所以只列出这么多，如果觉得不足以总结出规律的，读者可以复制代码之后自行打表观察。

总结： 横向比较时，dp[s][res]所加项都有一个特点，就是两个下标之和都等于res（其实这也算不上什么规律，因为前文我们就是这么分析，但是这一点对于求前缀和很有帮助）。纵向比较时，dp[s][res]所加项均在dp[s + 1][res]中重复出现，并且系数+1。规律已给出，代码中表现为sum和pre数组，需要读者自己多加思考。

AC代码 
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
#include<bits/stdc++.h>
using namespace std;
inline int read(){
   int s = 0, w = 1;
   char ch = getchar();
   while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}
   while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
   return s * w;
}

const int N = 5e3 + 10;
const int mod = 1e9 + 7;
int sum[N];
int pre[N];
int dp[N][N];
void run(int n, int m){
	for(int s = 1; s <= n; s++){
		for(int res = 0; res <= m; res++){
			pre[res] += sum[res];
			if(pre[res] >= mod)	pre[res] -= mod;
			if(res == 0)	dp[s][res] = 1;
			else{
				dp[s][res] += pre[res];
				if(dp[s][res] >= mod)	dp[s][res] -= mod;
			}
			sum[s + res] += dp[s][res];
			if(sum[s + res] >= mod)	sum[s + res] -= mod;
		}
	}
	printf("%d\n", dp[n][m]);
}

int main(){
	int n = read(), m = read();
	run(n, m - n);
	return 0;
}

I. Improve SPAM

solved by Sstee1XD. 1:47(+1)

题意: 给你一个有向图，N个点中有1-L个为发送点，剩下的为接收点。点1发送一封邮件给他相邻的点，其他的点接着发送，可能会收到多封邮件，每封发送。问接收点一共接收到了多少封邮件，以及多少个接收点收到了邮件。

BFS

题解: BFS。因为每封邮件都会发送，可能会有重复发送的情况，所以加一个数组判断当前点是否已在队列里（类似BellmanFord）减少时间复杂度卡过去。

AC代码 
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
#include<bits/stdc++.h>
#define bug cout << "bug********************************\n"
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
 
inline int read(){
   int s = 0, w = 1;
   char ch = getchar();
   while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}
   while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
   return s * w;
}
 
const int maxn = 2e3 + 7;
const int mod = 1e9 + 7;
vector<int>G[maxn];
int vis[maxn];
int que[maxn];
ll num[maxn];
int n, m;
ll ans, tot;

void bfs() {
	queue<int> q;
	num[1] = 1;
	q.push(1);
	que[1] = 1;
	while (!q.empty()){
		int u = q.front();
		ll w = num[u];
		num[u] = 0;
		q.pop();
		que[u] = 0;
		if (u > m) {
			tot += w;
			if (tot >= mod) tot -= mod;
			if (!vis[u]) ans++;
			vis[u] = 1;
		}
		for (auto v : G[u]) {
			num[v] += w;
			if (num[v] >= mod) num[v] -= mod;
			if (!que[v]) q.push({v});
			que[v] = 1;
		}
	}
	
}
 
void solve(){
	int k;
	for (int i = 1; i <= m; ++i) {
		scanf("%d", &k);
		for (int j = 1, v; j <= k; ++j) {
			scanf("%d", &v);
			G[i].push_back(v);
		}
	}
	bfs();
	printf("%lld %lld\n", tot, ans);
}
 
int main(){
	scanf("%d %d", &n, &m);
	solve();
	return 0;
}

BFS预处理+拓扑排序

solved by lllllan

思路： 队友的BFS就能做，比赛时能写出来就行，但是赛后写了个拓扑排序版本，发现速度更优。先跑一边BFS预处理，对所有能够访问到的点进行度数加一（拓扑需要），然后只要跑一边拓扑的模板就能稳过了。因为拓扑排序只会将度数为零的加入队列，每个点只会被访问一次，减少了访问次数，加快了速度。

AC代码 
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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
inline int read(){
   int s = 0, w = 1;
   char ch = getchar();
   while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}
   while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
   return s * w;
}
 
const int  N = 2e3 + 10;
const int mod = 1e9 + 7;
int n, m, deg[N];
set<int> S;
vector<int> V[N];
 
void topu(){
	ll ans = 0;
	ll num[N] = {0, 1};
	queue<int> Q;	Q.push(1);
	while(!Q.empty()){
		int u = Q.front(); Q.pop();
		if(u > m){
			ans += num[u];
			if(ans >= mod)	ans -= mod;
			S.insert(u);
		}
		for(auto v : V[u]){
			deg[v]--;
			num[v] += num[u];
			if(num[v] >= mod)	num[v] -= mod;
			if(!deg[v])	Q.push(v);
		}
	}
	printf("%lld %d", ans, S.size());
}
 
void BFS(){
	queue<int> Q;	Q.push(1);
	int vis[N] = {0, 1};
	while(!Q.empty()){
		int u = Q.front(); Q.pop();
		for(auto v : V[u]){
			deg[v]++;
			if(!vis[v])	Q.push(v);
			vis[v] = 1;
		}
	}
}
 
int main(){
	n = read(), m = read();
	for(int i = 1; i <= m; i++){
		int t = read();
		for(int j = 1; j <= t; j++){
			int v = read();
			V[i].push_back(v);
		}
	}
	BFS();
	topu();
	return 0;
}

K – Know your Aliens

solved by Tryna1

题意：构造一个一元多次函数，第i个位置如果是‘H’，就让P(2i) > 0 ,如果是‘A’，则P(2i) < 0 。

题解：字符从‘A’变到‘H’，从‘H’变到‘A’就意味着该函数的图像与x轴有交点，交点可以选两个偶数之间的那个奇数，方便计算。
那么P(x)=(x - x1)(x - x2)(x - x3)(x - x4)…具体如何将括号展开可以看代码。

AC代码 
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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
#define endl "\n"
string st;
ll a[10010],b[10010],d,f=0,j;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin>>st;
    int flag = 0;
	for(int i = 1;i <st.size(); i++){
		if(st[i - 1] != st[i]){
			flag = 1;
			a[d] = -(2*(i + 1) - 1);
			d++;
		}
	}
	if(st[st.size()-1] == 'H') f = 1;
	else  f = -1;
    b[0] = a[0];
    b[1] = 1;
    for(int i = 1;i < d ;i++){
    	b[i + 1] = 1;
    	for( j = i;j >= 1;j-- ){
    		b[j] = b[j] * a[i] +b[j - 1];
		}
		b[0] = b[0] * a[i];
	}
    cout<<d<<endl;
    if(flag == 0) cout<<f<<endl;
    else{
    if(f == -1){
    	for(int i = 0 ;i<=d;i++) b[i]=-b[i];
	}
	cout<<b[d];
	for(int i = d-1 ;i>=0;i--) cout<<" "<<b[i];
		cout<<endl;
	}
	return 0;
}

L.Leverage MDT

solved by Sstee1XD. 3:13(+2)

题意：给你一个"GB"矩阵，可以以行为单位反转元素的属性，问最大能获得的’G’正方形面积有多大。

题解：横向维护一个前缀和数组，代表到此为止有多少个连续相同的字符。然后从上到下扫，维护范围内最小的前缀和与当前方块数量的最小值，每次都更新答案。

AC代码 
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
#include<bits/stdc++.h>
using namespace std;
 
const int maxn = 1e3 + 7;
 
int n, m;
char maps[maxn][maxn];
 
int dp[maxn][maxn], ans = 1;
 
void gao() {
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			dp[i][j] = 1;
		}
	}
	for (int i = 1; i <= n; ++i) {
		for (int j = 2; j <= m; ++j) {
			if (maps[i][j] == maps[i][j - 1]) dp[i][j] += dp[i][j - 1];
		}
	}
	for (int j = 2; j <= m; ++j) {
		int minn = 10000, mini = 1;
		int num = 0;
		for (int i = 1; i <= n; ++i) {
			if (dp[i][j] <= minn) {
				minn = dp[i][j];
				mini = i;
			}
			num++;
			int tmp = min(num, minn);
			ans = max(ans, tmp * tmp);
			if (num >= minn) {
				num = 0;
				minn = 10000;
				i = mini;
			}
		}
	}
}
 
void solve(){
	for (int i = 1;i <= n; ++i) {
		scanf("%s", maps[i] + 1);
	}
	gao();
	printf("%d\n", ans);
}
 
int main(){
	scanf("%d %d", &n, &m);
	solve();
	return 0;
}

M – Mountain Ranges

solved by Tryna1

AC代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1010;
int a[maxn],maxx,n,x;
 
int main(){
	cin>>n>>x;
	for(int i =1;i<=n;i++){
		cin>>a[i];
	}
	int sum = 1;
	for(int i =1;i<n;i++){
		if(a[i+1]-a[i]<=x){
			sum++;
		}
		else{
			if(sum>maxx) maxx = sum;
			sum = 1;
		}
	}
	if(sum > maxx) maxx = sum;
	cout<<maxx<<endl; 
	return 0;
}
文章目录
  1. E – Eggfruit Cake
  2. F. Fabricating Sculptures
  3. I. Improve SPAM
    1. BFS
    2. BFS预处理+拓扑排序
  4. K – Know your Aliens
  5. L.Leverage MDT
  6. M – Mountain Ranges
|