2021-03-13 PAT Advance (春季甲级)

￡神魔★判官ぃ 2022-11-08 11:59 42阅读 0赞

慢慢写， 慢慢写，花了好长时间终于最后AK了，自己果然是算法小辣鸡...

不过相对来说，考试之前做了2020年春、秋、冬季的模拟卷，再加上这次的考试，觉得难度还是要比2020秋季的简单的，纯粹看对各个算法的熟练程度，基本上将PAT甲级练习题刷过两遍的同学AK应该是没有什么问题的。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMjA0NTgy_size_16_color_FFFFFF_t_70][]

# 第一题： #

# ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMjA0NTgy_size_16_color_FFFFFF_t_70 1][] #

#  #

先求出比p小的素数表，然后暴力求出里面所有项数为n的等差数列，寻找公差最大的作为答案，最后竟然没有运超，感恩！

#include<iostream>
    #include<vector>
    #include<cmath>
    #include<algorithm>
    using namespace std;
    
    bool isPrime(int num) {
    	if (num < 2)
    		return false;
    	for (int i = 2; i <= sqrt(num); i++) {
    		if (num % i == 0)
    			return false;
    	}
    	return true;
    }
    
    int main() {
    	int n, p;
    	scanf("%d %d", &n, &p);
    	vector<int> primes;
    	bool is_prime[100010];
    	fill(is_prime, is_prime + 100010, false);
    	for (int i = 2; i <= p; i++) {
    		if (isPrime(i)) {
    			primes.push_back(i);
    			is_prime[i] = true;
    		}
    	}
    	if (n == 1) {
    		printf("%d", primes[primes.size()-1]);
    		return 0;
    	}
    	vector<int> res, temp;
    	for (int i = 0; i < primes.size(); i++) {
    		for (int j = i + 1; j < primes.size(); j++) {
    			temp.clear();
    			temp.push_back(primes[i]);
    			int d = primes[j] - primes[i], num = primes[i];
    			while (temp.size() < n && num + d < p) {
    				num += d;
    				if (is_prime[num])
    					temp.push_back(num);
    				else
    					break;
    			}
    			if (temp.size() == n) {
    				if (res.size() == 0)
    					res = temp;
    				else {
    					if (temp[1] - temp[0] >= res[1] - res[0])
    						res = temp;
    				}
    			}
    		}	
    	}
    	if (res.size() == n) {
    		for (int i = 0; i < n; i++) {
    			if (i == 0)
    				printf("%d", res[i]);
    			else
    				printf(" %d", res[i]);
    		}
    	}
    	else
    		printf("%d", primes[primes.size()-1]);
    	
    	return 0;
    }

# 第二题： #

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMjA0NTgy_size_16_color_FFFFFF_t_70 2][]

贪心就行，将所有的数据按离开时间从小到大排序，然后从头到尾遍历一遍。

#include<iostream>
    #include<algorithm>
    using namespace std;
    
    struct Person {
    	int enter, exit;
    } per[2010];
    int n, res = 0, endTime = 24*3600;
    
    bool cmp(Person a, Person b) {
    	return a.exit < b.exit;
    }
    
    int main() {
    	scanf("%d", &n);
    	for (int i = 0; i < n; i++) {
    		int enhh, enmm, enss, exhh, exmm, exss;
    		scanf("%d:%d:%d %d:%d:%d", &enhh, &enmm, &enss, &exhh, &exmm, &exss);
    		per[i].enter = enhh*3600 + enmm*60 + enss;
    		per[i].exit = exhh*3600 + exmm*60 + exss;
    	}
    	sort(per, per + n, cmp);
    	int now = 0;
    	for (int i = 0; i < n; i++) {
    		if (now <= per[i].enter) {
    			now = per[i].exit;
    			res++;
    		}
    	}
    	printf("%d", res);
    	
    	return 0;
    }

# 第三题： #

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMjA0NTgy_size_16_color_FFFFFF_t_70 3][]

大顶堆，写这道题的时候人傻了，忘了什么是堆，建堆规则也忘了，只能在草稿纸上不停的模拟，然后和样例输出进行对比，花了快一个小时...

因为要判断不停的指令，所以为了方便这道题用python做了

n, m = map(int, input().split())
    nums = list(map(int, input().split()))
    heap = [1000000]
    
    def up(i):
        global heap
        index = i
        left = index*2
        while left <= len(heap)-1:
            if left + 1 <= len(heap)-1:
                right = left + 1
                if heap[left] < heap[right]:
                    left = right
            if heap[index] < heap[left]:
                heap[left], heap[index] = heap[index], heap[left]
                index = left
                left = index*2
            else:
                return
    
    def insert(num):
        global heap
        heap.append(num)
        for i in range(len(heap)//2, 0, -1):
            up(i)
    
    for i in range(n):
        insert(nums[i])
    res = ''
    for i in range(m):
        s = input()
        if 'is the root' in s:
            root = int(s.split(' ')[0])
            if root not in heap:
                res += '0'
                continue
            if heap.index(root) == 1:
                res += '1'
            else:
                res += '0'
        elif 'is the parent of' in s:
            parent = int(s.split(' ')[0])
            child = int(s.split(' ')[-1])
            if parent not in heap or child not in heap:
                res += '0'
                continue
            p_index = heap.index(parent)
            c_index = heap.index(child)
            if p_index*2 == c_index or p_index*2+1 == c_index:
                res += '1'
            else:
                res += '0'
        elif 'is the left child of' in s:
            child = int(s.split(' ')[0])
            parent = int(s.split(' ')[-1])
            if parent not in heap or child not in heap:
                res += '0'
                continue
            p_index = heap.index(parent)
            c_index = heap.index(child)
            if p_index * 2 == c_index:
                res += '1'
            else:
                res += '0'
        elif 'is the right child of' in s:
            child = int(s.split(' ')[0])
            parent = int(s.split(' ')[-1])
            if parent not in heap or child not in heap:
                res += '0'
                continue
            p_index = heap.index(parent)
            c_index = heap.index(child)
            if p_index * 2 + 1 == c_index:
                res += '1'
            else:
                res += '0'
        else:
            node1 = int(s.split(' ')[0])
            node2 = int(s.split(' ')[2])
            if node1 not in heap or node2 not in heap:
                res += '0'
                continue
            index1 = heap.index(node1)
            index2 = heap.index(node2)
            if index1//2 == index2//2:
                res += '1'
            else:
                res += '0'
    print(res)

# 第四题： #

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMjA0NTgy_size_16_color_FFFFFF_t_70 4][]

我觉得这次第四题反而是最简单的，标准的最短路径写法。

#include<iostream>
    #include<vector>
    #include<algorithm>
    using namespace std;
    
    const int maxn = 210;
    const int inf = 0x7fffffff;
    int n, m, g[maxn][maxn], dis[maxn];
    bool is_v[maxn], visit[maxn];
    
    void Dijkstra(int s) {
    	fill(dis, dis + maxn, inf);
    	fill(is_v, is_v + maxn, true);
    	dis[s] = 0;
    	for (int i = 0; i <= n; i++) {
    		int u = -1, temp = inf;
    		for (int j = 0; j <= n; j++) {
    			if (is_v[j] && dis[j] < temp) {
    				temp = dis[j];
    				u = j;
    			}
    		}
    		if (u == -1)
    			break;
    		is_v[u] = false;
    		for (int v = 0; v <= n; v++) {
    			if (is_v[v] && g[u][v] != 0 && dis[u] + g[u][v] < dis[v])
    				dis[v] = dis[u] + g[u][v];
    		}
    	}
    }
    
    int main() {
    	fill(g[0], g[0] + maxn*maxn, 0);
    	scanf("%d %d", &n, &m);
    	for (int i = 0; i < m; i++) {
    		int v1, v2, d;
    		scanf("%d %d %d", &v1, &v2, &d);
    		g[v1][v2] = d;
    		g[v2][v1] = d;
    	}
    	fill(visit, visit + maxn, true);
    	vector<int> vis, unvis;
    	int total = 0, vis_num = 0;
    	Dijkstra(0);
    	for (int i = 0; i <= n; i++) {
    		if (dis[i] == inf) {
    			unvis.push_back(i);
    			visit[i] = false;
    			vis_num++;
    		}
    	}
    	
    	int s = 0;
    	vis.push_back(s);
    	visit[s] = false;
    	vis_num++;
    	while (vis_num <= n) {
    		if (s != 0)
    			Dijkstra(s);
    		int temp = inf;
    		for (int i = 0; i <= n; i++) {
    			if (visit[i] && dis[i] < temp) {
    				temp = dis[i];
    				s = i;
    			}
    		}
    		total += dis[s];
    		vis.push_back(s);
    		visit[s] = false;
    		vis_num++;
    	}
    	if (unvis.size() == 0) {
    		for (int i = 0; i <= n; i++) {
    			if (i == n)
    				printf("%d\n", vis[i]);
    			else
    				printf("%d ", vis[i]);
    		}
    		printf("%d\n", total);
    	}
    	else {
    		for (int i = 0; i < vis.size(); i++) {
    			if (i == vis.size()-1)
    				printf("%d\n", vis[i]);
    			else
    				printf("%d ", vis[i]);
    		}
    		for (int i = 0; i < unvis.size(); i++) {
    			if (i == unvis.size()-1)
    				printf("%d\n", unvis[i]);
    			else
    				printf("%d ", unvis[i]);
    		}
    	}
    	
    	return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMjA0NTgy_size_16_color_FFFFFF_t_70]: /images/20221023/47ea84cd2257448982b3f9ae2cc69b68.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMjA0NTgy_size_16_color_FFFFFF_t_70 1]: /images/20221023/5f4872f47e424c1bb102b7830e2c6ca6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMjA0NTgy_size_16_color_FFFFFF_t_70 2]: /images/20221023/820b0b2ceeeb4991bbb06abf62637db8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMjA0NTgy_size_16_color_FFFFFF_t_70 3]: /images/20221023/3461150a16ee4a7eaedb66ac7c84b045.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMjA0NTgy_size_16_color_FFFFFF_t_70 4]: /images/20221023/3e7765e764a746428e852f34109bd1f9.png