计协第九周算法赛A组所有+B组前俩题题解

A组题解

A.饮料换购

打卡题，注意下细节即可

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
#include<bits/stdc++.h>
using namespace std;
// #pragma GCC optimize(2)
// #pragma G++ optimize(2)
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
    int n;
    cin>>n;
    int ans=n;
    while(n>=3){
        ans+=n/3;
        n=n/3+n%3;
    }
    cout<<ans;
    return 0;
}

B.Display The Number

模拟题，用有限的段输出能显示的最大数字

如输入2时显示1, 3时显示7, 1和7两个数字是性价比最高的

只需要判断这个数字是奇数还是偶数, 是偶数就全输出1, 奇数输出1个7, 随后的都输出1即可

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
using namespace std;
// #pragma GCC optimize(2)
// #pragma G++ optimize(2)
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int t;
	cin>>t;
	while(t--){
		int n;
		cin>>n;
		if(n%2==1){
			cout<<"7";
			n-=3; 
		}
		for(int i=0;i<n/2;i++){
			cout<<"1";
		}
		cout<<"\n";
	}
	return 0;
}

C.外卖店优先级

原文链接

首先来介绍几个数组的作用: order 数组用来存储 pair 信息:时刻编号和外卖店编号; st[i] 是判断编号为 i 的外卖店是否在有限缓存中, score[i] 用来存储编号为 i 的外卖店的当前优先级, last[i] 表示编号为 i 的外卖店的上一次订单的时间。

首先对 order 数组按照时间进行排序,然后依次去枚举每个订单,我们只需要去考虑有订单的时间点，比如编号为 3 的店的订单是在 5 时刻,然后下一次 3 号点的订单是在 8 时刻,那么对于 3 号店铺而言,我们不需要去考虑 5 ~ 7 这些时刻的情况,因为肯定是没有订单的,我们只需要在处理 8 时刻之前,去让店铺的优先级减去这些没有订单的时刻即可

1
2
int j=i;
while(j<m&&order[j]==order[i]) j++;

因为此时的 order 数组已经有序,上述代码的结果即 i~j-1 的范围内的值都是相同的,即对于同一家外卖店在同一时刻有多个订单,即一共订单量为:cnt=j-3,这家点的编号为:id=order[i].y;,时刻为:tm=order[i].x;,即当前的时刻是tm,现在我们要计算tm时刻之前(从last[id]到tm-1)的信息

1
2
3
score[id] -= tm - last[id] - 1;
score[id] = max(0, score[id]);
if (score[id] <= 3) st[id] = false;

最后,我们要计算在每个店铺获得了最后一个订单的时刻到最终的 t 时刻,需要让优先级减去多少,并计算是否让这些店铺退出优先缓存

1
2
3
4
5
6
for (int i=1;i<=n;i++){
    if (last[i]<t){
        score[i]-=t-last[i];
        if (score[i]<=3) st[i]=false;
    }
}

 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
#include <cstdio>
#include <cstring>
#include <algorithm>

#define x first
#define y second

using namespace std;

const int N = 100010;

typedef pair<int, int> PII;

PII order[N];

int last[N];         // 上一次的订单时间
int score[N];        // 店铺的优先级
bool st[N];

int main()
{
    int n, m, t;
    scanf("%d%d%d", &n, &m, &t);
    for (int i = 0; i < m; i ++ ) scanf("%d%d", &order[i].x, &order[i].y);
    
    sort(order, order + m);
    
    for (int i = 0; i < m;)
    {
        int j = i;
        while (j < m && order[j] == order[i]) j ++;
        int cnt = j - i, id = order[i].y, tm = order[i].x;
        
        // 当前的时刻是tm,现在我们要计算tm时刻之前(从last[id]到tm-1)的信息
        score[id] -= tm - last[id] - 1;
        score[id] = max(0, score[id]);
        if (score[id] <= 3) st[id] = false;
        
        // 现在处理t时刻的信息
        score[id] += cnt * 2;
        if (score[id] > 5) st[id] = true;
        last[id] = tm;
        
        i = j;
    }
    
    for (int i = 1; i <= n; i ++ ) 
        if (last[i] < t)
        {
            score[i] -= t - last[i];
            if (score[i] <= 3) st[i] = false;
        }
    
    int res = 0;
    for (int i = 1; i <= n; i ++ )
        if (st[i]) res ++;
        
    printf("%d\n", res);
    
    return 0;
}

D.BAN BAN

二分BAN序列，将N全部丢左边，B全部丢右边即可

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
using namespace std;
// #pragma GCC optimize(2)
// #pragma G++ optimize(2)
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t;
	cin>>t;
	while(t--){
		int n,count;
		cin>>n;
		count=n/2+n%2;
		cout<<count<<"\n";
		for(int i=0;i<count;i++){
			cout<<i*3+1<<" "<<n*3-i*3<<"\n";
		}
	}
	return 0;
}

E.路径之谜

这道题考察搜索

我的思路是有一个 res[n][n] 存储已走路径, top[n] 存储每列已运行步数, left[n] 存储每行已运行步数,每次搜索向4个方向进行搜索，如果遇上边界、移动方向步数已达阈值、路径已走，中断此次搜索(也就是剪枝)

因为周日开会+写B组去了，索性帖个别人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
69
70
71
72
73
74
75
76
#include <bits/stdc++.h>
using namespace std;

int n;
int path[25][25], vis[25][25];
int north[25], west[25];
int north_tru[25], west_tru[25];
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
vector<int> vv;
bool flag = false;

bool judge() {
	for (int i = 1; i <= n; i++) {
		if (north[i] != north_tru[i] || west[i] != west_tru[i])
			return false;
	}
	return true;
}

void dfs(int x, int y) {
	if (flag) return ;   // 剪枝，找到答案后就提前结束，不要再去遍历所有情况了
	// 因为题目保证了路径唯一
	if (x == n && y == n) {
		if (judge()) {
			// 输出路径
			for (int i = 0; i < vv.size(); i++) {
				cout << vv[i] << " ";
			}
			flag = true;
		}
		return ;
	}
	for (int i = 0; i < 4; i++) {
		int tx = x + dx[i];
		int ty = y + dy[i];
		if (tx <= 0 || tx > n || ty <= 0 || ty > n) continue;
		if (!vis[tx][ty]) {
			if (west[tx] >= west_tru[tx] || north[ty] >= north_tru[ty]) continue;  // 最关键的一个剪枝，不加上的话，会超时
			vis[tx][ty] = 1;
			west[tx]++, north[ty]++;  // 向正北方和正西方各射一箭
			vv.push_back(path[tx][ty]); // 记录路径

			dfs(tx, ty);

			vis[tx][ty] = 0;
			west[tx]--, north[ty]--;
			vv.pop_back();
		}
	}
}

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> north_tru[i];
	}
	for (int i = 1; i <= n; i++) {
		cin >> west_tru[i];
	}

	int k = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			path[i][j] = k;
			k++;
		}
	}

	vis[1][1] = 1;
	west[1]++, north[1]++;
	vv.push_back(path[1][1]);
	dfs(1,1);

	return 0;
}

F.Xenia and Ringroad

水题 ~~(虽然它有1000分)~~ ,有 n 个点围成的圆,每个点编号 1~~n ,移动一个点花费为1,要求第 i 个点的任务必须在 a~~i~ 点完成,并且必须按照顺序去完成任务,计算完成所有任务需要花费的最小时间

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
using namespace std;
// #pragma GCC optimize(2)
// #pragma G++ optimize(2)
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, m;
	cin>>n>>m;
	int flag = 1;
	long long ans=0;
	for(int i=0; i<m; i++) {
		int now;
		cin>>now;
		if(now >= flag)
			ans += now - flag;
		else
			ans += n - (flag - now);
		flag = now;
	}
	cout << ans << "\n";
	return 0;
}

G.Portal

此题摘自DMOI Round 1,难死人

因为本次周赛是IOI 赛制，所以想着有人用dfs暴力一下，~~万一有神犇学了剪枝能A呢(虽然自己做后看题解才知道要用01bfs才能A(悲))~~

由于我用的dfs+剪枝不能A，只有一半多的分，这里就不班门弄斧了，官方题解已经很详细了

官方题解点我

H.灵能传输

前缀和+贪心

我做的时候Full-WA了，所以还是看看别人的题解吧(悲)

点我~~嘲笑DoubleCat~~看题解

B组

A.Yes-Yes?

打卡题

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
using namespace std;
// #pragma GCC optimize(2)
// #pragma G++ optimize(2)
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t;
	cin>>t;
	while(t--){
		string s1,s2="";
		cin>>s1;
		for(int i=0;i<20;i++){
			s2+="Yes";
		}
		if(s2.find(s1,0)==string::npos){
			cout<<"NO\n";
		}else{
			cout<<"YES\n";
		}
	}
	return 0;
}

B.Stripes

水题，看是否有一行全是R

 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
#include<bits/stdc++.h>
using namespace std;
// #pragma GCC optimize(2)
// #pragma G++ optimize(2)
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t;
	cin>>t;
	while(t--){
		char res[9][9];
		int red=0,flag=0;
		for(int i=1;i<=8;i++){
			for(int j=1;j<=8;j++){
				cin>>res[i][j];
			}
		}
		for(int i=1;i<=8;i++){
			flag=0;
			for(int j=1;j<=8;j++){
				if(res[i][j]=='R'){
					flag++;
				}
			}
			if(flag==8){
				red=1;
			}
		}
		if(red){
			cout<<"R\n";
		}else{
			cout<<"B\n";
		}
	}
	return 0;
}