A. 配对

题意

给定含有 $n$ 个正整数的集合 $A$ 和 $B$ ,你需要建立他们之间的一一映射。将配对的两个数相加可以得到 $n$ 个和,问第 $k$ 大的和最大为多少。

思路

首先我们可以确定,组成前 $k$ 个最大的和一定用的是两个序列里面前 $k$ 大的数字。那么我们只需要知道如何配对能使第 $k$ 大的和最大。我们把问题简化一下如果 $A_1 < A_2$ ,$B_1 < B_2$ ,那么如果想要第二个和最大,肯定是需要 $A_1$ 和 $B_2$ 匹配,$A_2$ 和 $B_1$ 匹配,然后两个选一个最小的。所以这个问题我们类推一下,就是将 $A$ 和 $B$ 序列进行排序,然后取两个里面前 $k$ 个数,$A$ 中大的依次匹配 $B$ 中小的。然后在这 $k$ 个和中取一个最小值即可。

代码实现

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>

using namespace std;

const int maxn=1e5+5;
int a[maxn];
int b[maxn];
int n,k,ans=1e9+7;
int cmp(int a,int b)
{
	return a>b;
} 
int main()
{
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&b[i]);
	}
	sort(a+1,a+1+n,cmp);
	sort(b+1,b+1+n,cmp);
	for(int i=1;i<=k;i++)
	{
		ans=min(ans,a[i]+b[k-i+1]);
	}
	printf("%d",ans);
}

B. 十字阵列

题意

给定一个 $n\times m$ 的网格,每一个交点都一个敌人。你可以使用共 $h$ 次魔法,第 $i$ 次魔法能对第 $x_i$ 行和第 $y_i$ 列的所有敌人造成 $w_i$ 点伤害,交界点的伤害只计算一次。。如果施放完所有所有魔法后,如果一个点 $(i,j)$ 共受到 $z_i$ 点伤害,问 $\sum{z_i(i+j)}$ 为多少。

思路

无脑的计数题QAQ..真的是水题啊,我们只需要给每次魔法施放的 $w_i$ 乘上一个 $(i,j)$ 即可,但是因为是一行一列都会变化,那么其实我们可以优化一下,先把一行一列的 $\sum(i+j)$ 给求出来,然后施法的时候直接乘上这个常数就可以了。(这个题还有个很神奇的地方就是,我明明算的不会爆int然后开的int,然后就错了,后来一直找问题没找出来,后来全改成long long就AC了,太奇怪了。。)

代码实现

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>

using namespace std;

const int maxn=2005;
typedef long long ll;
int mod = 1e9+7;
ll row[maxn];
ll col[maxn];
ll x,y,z;
ll n,m,h;
ll ans,now;
int main()
{
	scanf("%lld%lld%lld",&n,&m,&h);
	for(int i=1;i<=n;i++) 
	{
		row[i]=(m*i)%mod+(m)*(m+1)/2;
		row[i]%=mod;
	}
	for(int j=1;j<=m;j++)
	{
		col[j]=(n*j)%mod+(n)*(n+1)/2;
		col[j]%=mod;
	}
	for(int i=1;i<=h;i++)
	{
		scanf("%lld%lld%lld",&x,&y,&z);
		now=((row[x]+col[y]-(x+y))%mod)*(z%mod);
		now%=mod;
		ans+=now;
		ans%=mod;
	}
	printf("%lld\n",ans);
}

C. 垃圾陷阱

题意

奶牛卡门想要从垃圾井底上到地面,对于一个垃圾它可以吃掉,或者是堆起来。初始卡门有10个小时的能量,吃掉一个垃圾会给他提供 $f_i$ 个小时的能量,叠起来一个垃圾会获得 $h_i$ 点高度,当垃圾总高度超过井的深度 $D$ 的时候,卡门就能上到地面。一个垃圾当 $t_i$ 小时时会到达井底。给出所有垃圾的状态,问奶牛能否到达地面。

思路

这个题面被我翻译的屎一样,QAQ,如果看不懂还是去看原题叭。。 这是一个类似于背包的题,对于一个垃圾,我们有两种选择,一个是吃掉它,一个是把他堆起来。。这个状态其实我没找好,看了题解发现可以设 $f[i][j]$ 来表示当用了前 $i$ 个垃圾时,当高度为 $j$ 的时候的最大的体力值(体力值就是还能继续活动多长时间)。我们用结构体数组 $a$ 来表示垃圾,写出如下转移方程。

  • 如果选择把这个垃圾吃掉,那么 $f[i][j]=max(f[i-1][j]+a[i].f,f[i][j])$

  • 如果选择把这个垃圾搭起来,那么$f[i][j+a[i].h]=max(f[i-1][j+a[i].h],f[i-1][j])$

我们发现边界就是 $f[0][0]=10$ ,也就是用了0个垃圾,高度为0的时候体力值为10。

注意一个地方我们如果到达了地面,就直接输出时间,然后退出程序即可,如果没有的话,我们可以选择遍历每一个垃圾下的 $0$ 高度,也就是说所有垃圾都不叠是最长的寿命,所以输出一个其中的最大值即可。

代码实现

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
using namespace std;

const int maxn=105;
struct node
{
	int t,f,h;
}a[maxn];
int cmp(node a,node b)
{
	return a.t<b.t;
}
int d,g;
int dp[maxn][maxn]; //dp[i][j] 用i个垃圾,当高度为j时所具备的最高生命值 
int main()
{
	freopen("test.in","r",stdin);
	scanf("%d%d",&d,&g);
	for(int i=1;i<=g;i++)
	{
		scanf("%d%d%d",&a[i].t,&a[i].f,&a[i].h); 
	}
	sort(a+1,a+1+g,cmp);
	memset(dp,-1,sizeof(dp));
	dp[0][0]=10;
	for(int i=1;i<=g;i++)
	{
		for(int j=0;j<=d;j++)
		{
			if(dp[i-1][j]>=a[i].t)
			{
				if(j+a[i].h>=d)
				{
					printf("%d",a[i].t);
					return 0;
				}
				dp[i][j]=max(dp[i-1][j]+a[i].f,dp[i][j]);
				dp[i][j+a[i].h]=max(dp[i-1][j+a[i].h],dp[i-1][j]);
			}
		}
	}
	int ans=0;
	for(int i=1;i<=g;i++) ans=max(ans,dp[i][0]);
	printf("%d",ans);
}