比赛链接:https://codeforces.ml/contest/1740

A题:水题,两个素数相加一定是偶数。

B题:大意是给出一堆长方形(包含正方形),纵向放置不能堆叠,求最短周长,可以任意旋转。

思路:最长的一个边可以包含其他长方形最长的边,然后所有的长方形的最短边可以取2倍+最长边取2倍。

C题:大意是给出一堆数,放到三个袋子里,每个袋子取一个。求|a-b|+|b-c|的最大值。放置为最优方案,取出为最优方案。

刚开始读题读错了,以为要全部顺序取出,因此开了栈和队列。确实在读题上还是存在一些问题。
其实只需要取一次。那么我们在a里放置最大,然后互相取bc;还可以在a中放最小,然后互相取bc。
为什么最优值不放在b里面,因为最优值说到底只能放置一个,不然取不到。所以不管放在哪里另外的都是连续的低值,ac取不到低值,那么等同于前两个方案。还有有些难想,其实不管怎么样多枚举一遍也能过,主要是读错了题。就算读对题了还是需要思考一段时间。

code:


void solve()
{
	memset(a,0,sizeof a);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	sort(a+1,a+n+1);
	int ans = 0;
	for(int i=1;i<=n-2;i++){
		ans = max(a[n]-a[i]+a[i+1]-a[i],ans);
	}
	for(int i=3;i<=n;i++){
		ans = max(ans,a[i]-a[1]+a[i]-a[i-1]);
	}
	cout<<ans<<endl;
}


D题:大意是给出一个n*m的矩阵,一些卡片1-k的全排列堆叠在(1,1)上面。你需要将这些卡片以正序堆叠在(n,m),你可以通过任意移动他们来到达(n,m)。
如果能够完成正序堆叠yes,否则no

思路:如果存在除了(1,1)(n,m)之外的两个空格子,那么这张卡片便可以移动到目的地。另外移动到目的地之后,这张卡片将不再占用格子。
解决方法:带着堆叠顺序进行排序,然后按照上面的方法进行判断。
整体代码都写对了,但是留出来的空间是n+m-2,这里存在非常大的问题。感觉这个题整体上难度小于C题。C题真不是很好推导。

code:


void solve()
{
	int n,m,k;
	cin>>n>>m>>k;
	int x;
	vector<tdata> ve;
	for(int i=1;i<=k;i++){
		cin>>x;
		ve.push_back({x,i});
	}
	sort(ve.begin(),ve.end(),cmp);
	for(int i=0,cnt=0;i<ve.size();i++){
		if(ve[i].pos-1>(n*m-4)+cnt){
			cout<<"TIDAK"<<endl;
			return;
		}
		cnt++;
	}
	cout<<"YA"<<endl;
}


E题:给定一个树,我们的目标是构造树的点权。每次操作可以选择一个叶子节点,并且摘掉这个叶子节点并且获得叶子节点的权值。每次摘叶子的时候,如果你摘的叶子的权值比他的父节点小,那么父节点的权值就会变成这个叶子的权值,一直进行到树被摘完。最终我们会获得摘叶子的序列,其价值是该序列的最长非下降子序列。请合理的构造树上的权值,最大化操作后的价值。

读不懂题。。。首先可以确定的是我们要求的是最长不减子序列的长度。根据题目中的题意我们可以知道,越深的节点,它的点权越小。
这样我们肯定是要从最深的一个节点开始摘,然后将一个较小的值传到上面,再依次传递构造一个较优的子序列。

code:

void dfs(int u) {
    a[u][0] = a[u][1] = 0;
    int res = 0;
    for(int i = h[u]; ~i ; i = ne[i]) {
        int j = e[i];
        dfs(j);
        a[u][0] += max(a[j][0], a[j][1]); // 找到最大值,但是不+1
        res = max(res, a[j][1]); // 从最深的儿子转移过来且连续,每次+1
    }
    a[u][1] = res + 1; // 自己结尾,所以要+1
}