Burnling's Blog
0%

220920 总结

发表于 更新于

预计：$100+100+100$

实际：$100+100+10$

T1

注意到 $K\leq100$ 所以写了个类似 dp 的东西

复杂度大概是 $O(NMK)$ ？

此时大概过去了 30min

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;

const int maxN = 110;

int N,M,MOD;

unordered_set<int> S[maxN][maxN];
int A[maxN][maxN];

vector<int> V;

int main(){
	freopen("magic.in","r",stdin);
	freopen("magic.out","w",stdout);
	
	scanf("%d%d%d",&N,&M,&MOD);
	for(int i = 1;i<=N;i++){
		for(int j = 1;j<=M;j++){
			scanf("%d",&A[i][j]);
			A[i][j] %= MOD;
		}
	}
	S[0][1].insert(1);
	for(int i = 1;i<=N;i++){
		for(int j = 1;j<=M;j++){
			for(auto k : S[i-1][j]) S[i][j].insert(k*A[i][j]%MOD);
			for(auto k : S[i][j-1]) S[i][j].insert(k*A[i][j]%MOD);
		}
	}
	printf("%d\n",int(S[N][M].size()));
	
	for(auto i : S[N][M]) V.push_back(i);
	sort(V.begin(),V.end());
	for(auto i : V) printf("%d ",i);
	return 0;
}

T2

本来想写拓扑排序但一想要缩点再一看数据范围就没想去写拓扑

寻找所有的入度为 $0$ 的点，并以之为始点进行 DFS

怕有遗漏的点有扫了一遍 $N$ 个点看是不是都经过了

复杂度大概是 $O(N^2)$

此时大概又过去了 30min

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
#include<bits/stdc++.h>
using namespace std;

const int maxN = 1010;

vector<int> G[maxN];
int inD[maxN];

int N;

bool vis[maxN];
void dfs(int k){
	vis[k] = 1;
	for(auto i : G[k]) if(!vis[i]) dfs(i);
}
vector<int> V;

int main(){
	freopen("news.in","r",stdin);
	freopen("news.out","w",stdout);
	
	scanf("%d",&N);
	for(int i = 1;i<=N;i++){
		for(int j = 1;j<=N;j++){
			int t;
			scanf("%d",&t);
			if(t){
				G[i].push_back(j);
				inD[j]++;
			}
		}
	}
	int ans = 0;
	
	for(int i = 1;i<=N;i++) if(inD[i] == 0) V.push_back(i);
	for(auto i : V){
		if(!vis[i]){dfs(i);ans++;} 
	}
	for(int i = 1;i<=N;i++){
		if(!vis[i]){dfs(i);ans++;}
	}
	printf("%d",ans);
	return 0;
}

T3

一眼模拟 再一细看 哦是大模拟 乐

思路挺简单的倒是不太好写

遍历每个时间点，扫一遍所有人的借书信息 同时维护书和人的状态

写写改改改改写写

写完就马上到点了 测了下样例过了就直接交了

后来发现是 $0\leq s\lt1000$ 而不是 $0\lt s \leq 1000$ （少算了一本书的次数

（为什么我不直接加到结果里而是加到书上最后相加输出啊 我不理解

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
#include<bits/stdc++.h>
using namespace std;

const int maxN = 120;

struct Book{
	int readTimes;
	int finishTime;
	bool isReading;
}B[1010];

struct Reader{
	int arriveTime;
	int finishTime;
	int num;
	int books[8];
	int t[8];
	bool read[8];
	Reader(){
		arriveTime = finishTime = num = 0;
		memset(books,0,sizeof(books));
		memset(t,0,sizeof(t));
		memset(read,0,sizeof(read));
	}
}A[maxN];

int T,N;

int main(){
	freopen("reading.in","r",stdin);
	freopen("reading.out","w",stdout);
	scanf("%d%d",&T,&N);
	for(int i = 1;i<=N;i++){
		Reader t;
		scanf("%d",&t.arriveTime);
		t.finishTime = t.arriveTime;
		int k;
		scanf("%d",&k);
		t.num = k;
		for(int j = 1;j<=k;j++){
			scanf("%d%d",&t.books[j],&t.t[j]);
		}
		A[i] = t;
	}
	for(int t = 0;t<T;t++){
		for(int i = 1;i<=N;i++){
			bool isReading = false;
			if(A[i].finishTime > t) continue;
			for(int j = 1;j<=A[i].num;j++){
				if(A[i].read[j]) continue;
				if(B[A[i].books[j]].finishTime <= t){
					isReading = true;
					A[i].read[j] = true;
					A[i].finishTime = t + A[i].t[j];
					B[A[i].books[j]].finishTime = A[i].finishTime;
					B[A[i].books[j]].readTimes++;
					break;
				}
			}
			if(!isReading){
				int nextTime = 2e9;
				int b;
				for(int j = 1;j<=A[i].num;j++){
					if(A[i].read[j]) continue;
					if(nextTime > B[A[i].books[j]].finishTime){
						nextTime = B[A[i].books[j]].finishTime;
						b = j;
					}
				}
				if(nextTime >= T) continue;
				A[i].read[b] = true;
				
				B[A[i].books[b]].finishTime += A[i].t[b];
				A[i].finishTime = B[A[i].books[b]].finishTime;
				B[A[i].books[b]].readTimes++;
			}
		}
	}
	int ans = 0;
	for(int i = 1;i<=1000;i++) ans += B[i].readTimes;
	printf("%d",ans);
	return 0;
}