百变kkk第三弹题解

T1：求逆序对不解释。

T2：Prim算法求最小生成树。

T3：看到“最大值最小”就会想到二分。对于此题可以二分最大的身高差，再用贪心验证一下即可。

那么如何贪心呢？首先可以证明，把A2放在A1左边，A3放在A1右边，A4放在A2左边，A5放在A3右边等等，这种方法是不可行的。

我们可以先把A1放在第一位，然后每次在后面尽可能的放上一个大的Ai，在前面尽可能的放上一个小的Aj（但是Ai和Aj都必须满足身高差），放完的时候判断身高差是否满足要求即可。

T4：两条线路 (a<->x) 和 (b<->y) 出现如下情况之一就算相交: (a<b and y<x) or (a>b and x<y) or (a=b and x=y).

首先可以看出这题不能用贪心解决。一种比较明显的思路就是双重循环枚举两个点后DP，但是更明显的是这样做的时间复杂度根本不能承受。联想到克鲁斯卡尔算法与普利姆算法的区别，我们想到以边作为状态。首先要排序（去除后效性），然后设f1[i]表示左边以i结尾的最大收益，f2[i]表示右边以i结尾的最大收益，状态转移方程就很明显了。转移的时候注意用临时变量存储。

T5：就是求所有a[i]-i的顺序对。

鉴于T4询问的人数较多，给出标程

PASCAL

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define maxn 40005
#define maxe 100005
typedef long long LL;
typedef pair<int,int> pii;
int n,m,k;
LL a[maxn],b[maxn],f1[maxn],f2[maxn];
pii e[maxe];
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=m;i++) scanf("%d",&b[i]);
    for(int i=1;i<=k;i++) scanf("%d%d",&e[i].first,&e[i].second);
    sort(e+1,e+k+1);
    memcpy(f1,a,sizeof(a));
    memcpy(f2,b,sizeof(b));
    for(int i=k;i>=1;i--) {
        int u=e[i].first,v=e[i].second;
        LL va=a[u]+f2[v];
        LL vb=b[v]+f1[u];
        f1[u]=max(f1[u],va);
        f2[v]=max(f2[v],vb);
    }
    int ans=0;
    for (int i=1;i<=n;i++) if (ans<f1[i]) ans=f1[i];
    for (int i=1;i<=m;i++) if (ans<f2[i]) ans=f2[i];
    cout<<ans;
    return 0;
}

百变kkk第三弹题解

讨论操作

回复

相关推荐

百变kkk第三弹题解