Codeforces Round 831 A - E

A. Factorise N+M

题目大意: 给定一个质数$n$，找到一个质数$m$ ，使得$n + m$是一个非质数

解题思路: 对于非$2$的质数来说其他质数全部都是奇数，那么我们可以对于这些质数加上一个$3$，然后对于$2$特判加上$5$即可

signed main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int T;
	cin >> T;
	while(T--)
	{
		cin >> n;
		if(n == 2)
		{
			cout << 7 << "\n";
		}
		else cout << 3 << "\n";
	}
	return 0;
}

B. Jumbo Extra Cheese 2

题目大意: 给定$n$个矩阵，我们需要把矩阵放到$x$轴上面，一个矩阵不能放在另外一个矩阵的上面，问这个矩阵的形成的一个图形的周长是多少

解题思路: 将这个图形拿出来在颅内思考一下，发现因为很多个矩形会贴在一起，那么对于形成的这个图形的 高 实际上就是最长的矩形的高，同时对于每个矩形来说他们的宽都要计算两边，那么我们对于每一个矩形来说我们可以选定较小的那一部分作为宽，较高的那一部分作为高，然后找一个最长的高即可

pair<int,int> a[maxn];
signed main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int T;
	cin >> T;
	while(T--)
	{
		cin >> n;
		for(int i = 1,u,v;i <= n;++i)
		{
			cin >> u >> v;
			if(u < v) swap(u,v);
			a[i] = {u,v};
		}
		sort(a + 1,a + 1 + n);
		int ans = 2 * a[n].first;
		for(int i = 1;i <= n;++i)
		{
			ans += a[i].second * 2;
		}
		cout << ans << "\n";
	}
	return 0;
}

C. Bricks and Bags

题目大意: 给定$n(1 \leq n \leq 10^5)$个数字，将他们放在$a,b,c$三个背包中，玩家需要从这三个背包中各选择一个数字，并且计算$|w_1 - w_2| + |w_2 - w_3|$ $(w_1 \in a,w_2 \in b,w_3 \in c)$的值是多少，然后玩家想要让值尽可能的小，放置者想要让值尽可能的大，问如何放置才能使得这个值最大

解题思路: 首先先放在数轴上面考虑这个问题，我们假设$w_3 > w_1$，如果$w_2$在$w_1$和$w_3$之间，那么值就是$w_3 - w_1$，如果$w_2 < w_1$，那么对应的值就是$w_1 - w_2 + w_3 - w_2$，若$w_2 > w_3$，那么对应的值就是$w_2 - w_3 + w_2 - w_1$

对于夹在中间的情况，我们可以直接计算，也就是整个序列的最大值减去整个序列的最小值

如果是第一种情况$w_2 < w_1$，那么实际上我们是去取若干个小值给放在$b$中，为了让权值最大我们可以把$a_n$给单独拉出来当作$w_3$，假设目前取到的小值已经到了第$i$位，那么权值就是$a_n - a_i + a_{i + 1} - a_i$

如果是第二种情况$w_2 > w_3$，那么实际上我们就是去取若干个大值给放在$b$中，为了让权值最大我们可以把$a_1$给单独拉出来当作$w_1$，假设目前取到的大值已经到了第$i$位，那么权值实际上就是$a_i - a_1 + a_i - a_{i - 1}$

signed main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int T;
	cin >> T;
	while(T--)
	{
		cin >> n;
		for(int i = 1;i <= n;++i) cin >> a[i];
		sort(a + 1,a + 1 + n);
		int ans = 0;
		for(int i = 1;i < n - 1;++i)
		{
			chkmax(ans,a[n] - a[i] + a[i + 1] - a[i]);
		}
		for(int i = n;i > 2;--i)
		{
			chkmax(ans,a[i] - a[i - 1] + a[i] - a[1]);
		}
		cout << ans << "\n";	
	}
	return 0;
}

D. Knowledge Cards

题目大意: 给定一个$n * m(n * m \leq 10^6)$的矩阵，刚开始在矩阵$(1,1)$堆积着$k$张牌，从顶部到底部分别是$a_1,a_2,…,a_k$，接下来我们可以把牌移动到别的格子中，注意除了$(1,1)$和$(n,m)$这两个格子其他格子放置的牌数不能超过一张，然后$(1,1)$不能被重复放置牌，也不能从$(n,m)$移出去一张牌，问堆在$(n,m)$上面的牌从顶部到底部牌的排列是否可以是$1,2,3,…k$

解题思路: 直接移动牌即可，因为我们在移动牌的时候肯定需要给当前一张牌留出一点位置的，所以除了$(1,1)$和$(n,m)$我们另外留出一个位置就能随便移动了，否则就是不能构成的情况

cin >> n >> m >> k;
for(int i = 1;i <= k;++i) cin >> a[i];
int nowcnt = k;
priority_queue<int,vector<int>,less<int>> q;
int f = 1;
for(int i = 1;i <= k;++i)
{
    q.push(a[i]);
    if(q.size() >= n * m - 2)
    {
        f = 0;
        break;
    }
    while(!q.empty() && q.top() == nowcnt)
    {
        q.pop();
        nowcnt--;
    }
}
if(f) cout << "YA\n";
else cout << "TIDAK\n";

E. Hanging Hearts

题目大意: 给定一棵树，我们需要给这棵树分配一些权值，这些权值属于一个排列。然后我们从叶子开始取，取的时候会构成一个序列。我们每次取叶子的时候判断他的父节点是否大于叶子结点如果大于叶子结点那么父节点的权值也变成叶子结点的权值，问构成的序列中形成的最大非递减子序列长度是多少

解题思路: 考虑拿取叶子的性质实际上我们将小的权值放在下面更好一点，因为小的权值会把权值赋值给上面的父亲节点，那么对于一个节点来说她下面可能有很多条链，我这个节点要么作为子序列的终点要么作为子序列的中转点。如果作为终点的话那么也需要从下面的终点转移过来，如果作为中转点的话就可以将下面的节点选择他们的中转点或者是终点取最大然后把权值全部加起来

int n,m,k;
int dp[maxn][2];
vector<int> edge[maxn];
void dfs(int s,int fa)
{
	dp[s][0] = dp[s][1] = 0;
	int mx = 0;
	for(auto to:edge[s])
	{
		if(to == fa) continue;
		dfs(to,s);
		dp[s][0] += max(dp[to][0],dp[to][1]);
		chkmax(mx,dp[to][1]);
	}
	dp[s][1] = mx + 1;
}
signed main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin >> n;
	for(int i = 2,x;i <= n;++i)
	{
		cin >> x;
		edge[i].push_back(x);
		edge[x].push_back(i);
	}
	dfs(1,0);
	cout << max(dp[1][0],dp[1][1]) << "\n";
	return 0;
}