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);
}