CSP 2022 3月

1. 未初始警告

签到题,直接打一个标记数据,如果此时右边的变量已经被初始化或者是常量,那么此时左值可以被成功初始化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<iostream>
using namespace std;

#define N 200100
int vis[N];
int main() {
    vis[0] = 1;
    int n, k;
    int ans = 0;
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= k; i++) {
        int x, y;
        scanf("%d%d",&x,&y);
        if (!vis[y]) ans++;
        vis[x] = 1;
    }
    printf("%d\n",ans);
}

2. 出行规划

这个题目稍微比第一题复杂一点, 要求的是我们在这个时刻做了核酸能满足多少个场所的要求, 此时我们可以使用前缀和数组进行求解.

假设一个场所计划时间为t,核酸要求的时间为k,那么此时在 t - k + 1 处标记上1, 在t + 1处标记上-1,进行前缀求和,即可得到最终的结果.

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
#include<iostream>
using namespace std;

#define N 200100
int sum[N];
int main() {
    int n, m, k, big;
    scanf("%d%d%d",&n, &m, &k);
    for (int i = 1;i <= n; i++) {
        int x, y;
        scanf("%d%d",&x,&y);
        sum[max(0, x- y + 1)] ++;
        sum[x+1] --;
        if (i == n) big = x;
    }
    for (int i = 0; i <= big; i++) {
        sum[i] += sum[i-1];
    }
    for (int i = 0; i < m; i++) {
        int x;
        scanf("%d",&x);
        if (x + k > big) printf("%d\n",0);
        else printf("%d\n",sum[x+k]);
    }
}

3. 计算资源调度器

大模拟,判断好节点和任务的约束就好,写法很复杂很容易出错…

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
#include<bits/stdc++.h>
using namespace std;
 
int n,m;
//计算结点的 1.所属可用区 2.计算了哪些任务 3.计算任务个数 4.结点编号 
struct node{
	int num,cnt = 0,numm;//1 3 4
	vector<int> job;//2
	friend bool operator < (const node &a, const node &b){
		return (a.cnt == b.cnt) ? a.numm < b.numm : a.cnt < b.cnt; 
	}
}N[1005];
vector<int> kyq[1005];//每个可用区执行了的应用 
 
void Print(vector<node> vec, int a){
	sort(vec.begin(),vec.end());
	int tmp = vec[0].numm;//选择的结点编号 
	cout << tmp << " ";
	N[tmp].cnt++;
	N[tmp].job.push_back(a);
	kyq[N[tmp].num].push_back(a);
}
 
void deal(int a,int p1,int p2,int p3,int p3r){
	vector<node> canuse;//可用的结点
	vector<node> backup;//不考虑p3的备用 
	int cnt1 = 0, cnt2 = 0;
	for(int i=1;i<=n;i++){
		if(!(p1 ? N[i].num == p1 : 1)) continue;//指定可用区 
		if(p2){//指定任务亲和 
			bool flag = 0;
			for(int t : kyq[N[i].num])
				if(t == p2){flag = 1; break;}
			if(!flag) continue;
		}
		backup.push_back(N[i]); 
		cnt1++; 
		if(p3){//指定任务不亲和 
			bool flag = 1;
			for(int t : N[i].job)
				if(t == p3){flag = 0; break;}
			if(!flag) continue;
		}
		canuse.push_back(N[i]);
		cnt2++;
	}
	if(!p3 && !cnt1){//没有可用的结点 
		cout << 0 << " ";
		return;
	}
	if(!p3 && cnt1){Print(backup,a); return;}
	if(p3){
		if(!cnt2){
			if(cnt1 && !p3r) Print(backup,a);
			else cout << 0 << " ";
			return;
		}
		else{
			Print(canuse,a); 
		}
	}
}
 
int main(){
	scanf("%d%d",&n,&m);
	int t;
	for(int i=1;i<=n;i++){
		scanf("%d",&N[i].num);
		N[i].numm = i;
	}
	int g;scanf("%d",&g);
	int f,a,p1,p2,p3,p3r;//个数 应用编号 指定区 指定应用 避免指定应用 尽量 
	while(g--){
		scanf("%d%d%d%d%d%d",&f,&a,&p1,&p2,&p3,&p3r);
		while(f--) deal(a,p1,p2,p3,p3r);
		cout << endl;
	}
	return 0;
}

4. 通信系统管理