PTA L2 题目合集

L2-001 紧急救援 (25 分)

题解链接

L2-002 链表去重 (25 分)

#include
#define PIS pair 
#define val first
#define ne second
using namespace std;
const int N = 1e6+10;

map Map;

string st_address;
int n, st[N];

vector  v;

int main()
{
	cin >> st_address >> n;
	for (int i = 0;i > ad >> val >> ne;
		Map[ad] = {val, ne};
	}
	
	string p = st_address;
	while (p != "-1") {
		st[abs(Map[p].val)] = 1;
		string t = Map[p].ne;
		while (t != "-1") {
			if (st[abs(Map[t].val)]) 
				v.push_back (t);
			else 
				break;
			t = Map[t].ne;
		}
		Map[p].ne = t;
		cout 1) == (idx_b>>1))) puts ("T");
			else if (op == 3 && (idx_a == (idx_b>>1))) puts ("T");
			else if (op == 4 && (idx_b == (idx_a>>1))) puts ("T");
			else puts ("F");  
		}
	}

	return 0;
}

L2-013 红色警报 (25 分)

并查集。

每次删除一座城市就将其标记一下，每删除一座城市，就使用全部关系（除了被标记的城市）重新构件连通块，判断连通分支数是否比删除该城市前的连通分支数大，如果前者大说明改变了连通性。当连通分支数为0时，说明没有城市了，game over。

#include
using namespace std;
const int N = 600, M = 5010;
int fa[N], st[N], a[M], b[M];

int find (int x) {
	return x == fa[x] ? fa[x] : fa[x] = find (fa[x]);
}

void join (int x, int y) {
	int rx = find (x), ry = find (y);
	if (rx != ry) fa[rx] = ry;
}

int main()
{
	int n, m, c, k, cnt_unit = 0, loss = 0;
	cin >> n >> m;
	for (int i = 0;i  a[i] >> b[i];
		join (a[i], b[i]);
	}	
	cin >> k;
	
	for (int i = 0;i > c;
		st[c] = 1;
		loss ++;
		for (int i = 0;i > m;
	for (int i = 1;i  s[i][j];
			mx = max (mx, s[i][j]);
			mn = min (mn, s[i][j]);
			sum += s[i][j];
		}
		v.push_back (1.0 * (sum - mx - mn) / (k - 2));
	}
	
	sort (v.begin(), v.end());
	
	printf ("%.3lf", v[v.size()-m]);
	for (int i = v.size()-m+1;i > n;
	for (int i = 1;i > a[i], sum += a[i];
	sort (a + 1, a + n + 1);
	for (int i = 1;i