【题目记录】山东省大学生程序设计竞赛(重现赛)总结

旧城等待， 2023-01-20 11:46 107阅读 0赞

这个竞赛最后只过了一个签到题…

# 先补一下题目 #

## H题 DP ##

先补H题是因为H提示最后做的一道题,交了几次都没过，一直不知道错误在哪里，先看题目。[https://ac.nowcoder.com/acm/contest/16092/H][https_ac.nowcoder.com_acm_contest_16092_H]

题意大概是,一个游戏,主角做任务,第一行给出任务数量n,主角血量H,主角耐力值S,然后n行给出每个任务消耗的血量,耐力值和赏金,如果血量变为零主角会立即死亡,如果耐力值的消耗量超出了当前的耐力值,多余的耐力值从血量里面扣。  
思路：  
读完题目发现是一个背包问题，跟动态规划有关，题目的关键是列出状态转移方程，用F(i,h,h+s)表示接到第i个任务时,在血量和耐力值为h和s时能拿到的最多的赏金。F(i,h,h+s)=max(F(i-1,h,h+s),F(i-1,h-H\[i\],h+s-H\[i\]-S\[i\])),因为耐力值掉完后毁掉血量,所以第二个限制因素设置成健康值和耐力值的和比单纯设为耐力值更方便计算一些。

比赛的时候一直没交过，最后回来发现是赏金的范围在 1 0 9 10^9 109之内,数据类型应该用longlong的,改成longlong后再交果然通过了…

代码:

#include<iostream>
    using namespace std;
    
    int main()
    { 
    	int n, h, s;
    	cin >> n >> h >> s;
    	int* H = new int[n];
    	int* S = new int[n];
    	long* W = new long[n];
    	for (int i = 0; i < n; i++)
    	{ 
    		cin >> H[i];
    		cin >> S[i];
    		cin >> W[i];
    	}
    	long long** res = new long long* [h + 1];//就是这里的数据类型搞错了
    	for (int i = 0; i <= h; i++)
    	{ 
    		res[i] = new long long[h + s + 1];
    	}
    	for (int i = 0; i <= h; i++)
    	{ 
    		for (int j = 0; j <= h + s; j++)
    		{ 
    			res[i][j] = 0;
    		}
    	}
    	for (int i = 0; i < n; i++)
    	{ 
    		for (int j = h; j >= 0; j--)
    		{ 
    			for (int k = h + s; k >= 0; k--)
    			{ 
    				if (j <= H[i] || k <= H[i] + S[i])	//注意血量不能等于任务消耗的血量
    				{ }
    				else
    				{ 
    					if (res[j - H[i]][k - H[i] - S[i]] + W[i] > res[j][k])
    					{ 
    						res[j][k] = res[j - H[i]][k - H[i] - S[i]] + W[i];
    					}
    				}
    			}
    		}
    	}
    	cout << res[h][h + s] << endl;
    
    	return 0;
    }

## D题 思维 ##

[https://ac.nowcoder.com/acm/contest/16092/D][https_ac.nowcoder.com_acm_contest_16092_D]据说是个简单题。  
题目大意：二维空间里放了 个盒子，有水平往左和竖直往下两种重力，求重力作用之后形成的轮廓周长  
思路：  
水平和竖直的算法是一样的。以竖直为例，周长就等于所有水平的边长之和和所有竖直的边长之和。所有水平的边长就是所有方块的列数乘2，所有竖直的边长之和就是每两列之间方块数的差值的绝对值之和。每次更新的时候，只需要更新列数和受到影响的左右两边的竖直边的个数。  
代码如下：

#include <iostream>
    #include <cmath>
    #define N (int)2e5+2
    using namespace std;
    
    int h[N] = {  0 }, v[N] = {  0 };	//某列或某行的方块数
    int hs[N] = {  0 }, vs[N] = {  0 };	//相邻两列或两行的差的绝对值
    
    long sum(int[]);
    
    int main()
    { 
    	
    	int n,hn=0,vn=0;
    	long resh, resv;
    	int hss=0,vss=0;
    	cin >> n;
    	int m;
    	while (n--)
    	{ 
    		cin >> m;
    		if (h[m] == 0)
    		{ 
    			hn++;
    		}
    		h[m]++;
    		hss -= (hs[m] + hs[m - 1]);
    		hs[m] = abs(h[m + 1] - h[m]);
    		hs[m - 1] = abs(h[m] - h[m - 1]);
    		hss += (hs[m] + hs[m - 1]);
    		resh = 2 * hn + hss;
    		cin >> m;
    		if (v[m] == 0)
    		{ 
    			vn++;
    		}
    		v[m]++;
    		vss -= (vs[m] + vs[m - 1]);
    		vs[m] = abs(v[m + 1] - v[m]);
    		vs[m - 1] = abs(v[m] - v[m - 1]);
    		vss += (vs[m] + vs[m - 1]);
    		resv = 2 * vn + vss;
    		cout << resh << " " << resv << endl;
    	}
    
    	return 0;
    }
    long sum(int a[])
    { 
    	long s = 0;
    	for (int i = 0; i < N; i++)
    	{ 
    		s += a[i];
    	}
    	return s;
    }

总结：  
主要是时间比较少，能力也有限，这次只能先补两道简单题了。  
到这次比赛确实比较少写代码了，导致有很多之前学会的东西很生疏，不能很快的写出来。之前听课学到的内容也没有及时复习，确实有一些基础没有掌握好。还有总是会犯一些常见的错误，比如本次就忽略了题目给出的值得范围。还有这次比赛因为D题的失误，一直找不到错在哪里，导致耽误了好长时间，本来能做出来的题目也没做完。总之，后面还需要多练习，熟悉比赛。

[https_ac.nowcoder.com_acm_contest_16092_H]: https://ac.nowcoder.com/acm/contest/16092/H
[https_ac.nowcoder.com_acm_contest_16092_D]: https://ac.nowcoder.com/acm/contest/16092/D