PAT-2021年冬季考试（满分）

PAT-2021年冬季考试 - Advanced Level

贴贴这次满分的代码

7-1 Fake News (20 分)

题目链接

#include <iostream>
#include <map>
using namespace std;
int a[10010], vis[10010];
int main() {
    
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, m, x;
	cin >> n >> m;
	while(m--) {
    
		int maxn = 0;
		map<int, int> b;
		for(int i = 0; i < n; ++i){
    
			cin >> a[i];
			b[a[i]]++;
		}
		for(int i = 0; i < n; ++i) {
    
			maxn = max(maxn, n - b[a[i]]);
		}
		for(int i = 0; i < n; ++i) {
    
			if(n - b[a[i]] == maxn)
				vis[i + 1]++;
		}
	}
	int ans = 1;
	for(int i = 2; i <= n; ++i){
    
		if(vis[i] > vis[ans])
			ans = i;
	}
	cout << ans;
} 

7-2 Rank a Linked List (25 分)

题目链接

#include <iostream>
#include <map>
using namespace std;
int a[100100];
map<int, int> m;
int main() {
    
	int n, root, ret = 1, x;
	cin >> n;
	for(int i = 0; i < n; ++i) {
    
		cin >> x;
		m[x] = i;
		if(x == -1)
			root = x;
	}
	while(ret <= n){
    
		a[m[root]] = ret++;
		root = m[root];
	}
	for(int i = 0; i < n; ++i){
    
		if(i != 0) cout << " ";
		cout << ret - a[i];
	}
} 

7-3 Size of Military Unit (25 分)

题目链接

#include <iostream> 
#include <vector>
using namespace std;
vector<int> v[100100];
int ans[100100];
int dfs(int x) {
    
	for(int i = 0; i < v[x].size(); ++i)
		ans[x] += dfs(v[x][i]);
	return ans[x] = ans[x] + 1;
}
int main() {
    
	int n, m, x;
	scanf("%d", &n);
	for(int i = 2; i <= n; ++i) {
    
		scanf("%d", &x);
		v[x].push_back(i);
	}
	dfs(1);
	scanf("%d", &m);
	while(m--) {
    
		scanf("%d", &x);
		printf("%d\n", ans[x]);
	}
} 

7-4 Helping the Couriers (30 分)

题目链接

#include <iostream> 
#include <cstring>
using namespace std;
const int inf = 0x3f3f3f3f;
struct node{
    
	int time, y, p;
}a[1010];
int map[1010][1010], n, vis[1010];
void flody(){
    
	for(int k = 0; k <= n; ++k)
		for(int i = 0; i <= n; ++i)
			for(int j = 0; j <= n; ++j)
				map[i][j] = min(map[i][j], map[i][k] + map[k][j]);
}
int main() {
    
	int m, k, start, x, y, z, maxp = -999999999, mint = 999999999;
	scanf("%d%d", &n, &m);
	memset(map, inf, sizeof map);
	for(int i = 0; i <= n; ++i)
		map[i][i] = 0;
	scanf("%d:%d", &x, &y);
	start = x * 60 + y;
	for(int i = 1; i <= n; ++i){
    
		scanf("%d:%d", &x, &y);
		a[i].time = x * 60 + y;
		scanf("%d%d", &a[i].y, &a[i].p);
	}
	while(m--) {
    
		scanf("%d%d%d", &x, &y, &z);
		map[x][y] = map[y][x] = min(map[x][y], z);
	}
	flody();
	scanf("%d", &k);
	while(k--) {
    
		memset(vis, 0, sizeof vis);
		int now = start, pay = 0, f = 1;
		x = 0;
		for(int i = 0; i < n; ++i){
    
			scanf("%d", &y);
			if(f == 0) continue;
			if(vis[y] || map[x][y] == inf) f = 0;
			if(now + map[x][y] <= a[y].time) {
    
				pay += a[y].y;
			}
			else {
    
				pay += a[y].y - a[y].p;
			}
			now += map[x][y];
			vis[y] = 1;
			x = y;
		}
		if(f == 0) continue;
		now += map[x][0];
// printf("%d %02d:%02d\n", pay, now / 60, now % 60);
		if(pay > maxp) {
    
			maxp = pay;
			mint = now;
		}
		else if(pay == maxp && now < mint) {
    
			mint = now;
		}
	}
	printf("%d %02d:%02d", maxp, (mint/60) % 24, mint % 60);
}