竞赛讨论区 > C 题题解算法一的各个档的部分分。
头像
Zxsoul
发布于 2021-10-19 11:35
+ 关注

C 题题解算法一的各个档的部分分。

看着题目挺有意思,于是做了做,结果发现题解只给出了第二种做法的代码,所以几乎所有人的代码都是第二种做法,但这道题目的价值真的是得满分吗?

不难发现,出题人细心规划的部分档非常细,并且在最后的数据范围中成功卡掉了 ,所以以下都是部分分的档,正解未写出,只想到了的做法,若有大佬可以解答一下题解中前缀和优化是如何做,请私信我。

8 pts

对于暴力, 分好成绩,不过不是我关注的重点,重点如何DP,以及 DP 优化。

20 pts

对于 20% 的数据,有 1 ≤ n ≤ 100。

表示前 个数,子集最后一个是 前一个是 的合法方案数。转移枚举 作为更靠前的一个数。

其中 表示是否满足题目要求。

代码

int f[B][B][B];
struct node{int x,y;} a[B];
int n;
int cmp(node a,node b) 
{
    return a.y>b.y;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin>>n;
    for (int i=1;i<=n;i++) 
    {
        cin>>a[i].x;
        cin>>a[i].y;
    }
    sort(a+1,a+1+n,cmp);
    int ans=0;
    for (int i=3;i<=n;i++)
        for (int j=1;j<=i-1;j++)
        {
            for (int k=1;k<=j-1;k++) f[i][j][i]=(f[i][j][i]+(f[i-1][k][j]+1)*((a[i].x<max(a[j].x,a[k].x)&&a[i].x>min(a[j].x,a[k].x)) ? 1 : 0))%mod;
            for (int k=1;k<=j-1;k++) f[i][k][j]=(f[i-1][k][j])%mod;
        }
    for (int i=1;i<=n;i++)
        for (int j=1;j<=i-1;j++) ans=(ans+f[n][j][i])%mod;
    printf("%lld",(ans+(n*(n-1)/2)+n)%mod);
    return 0;
}

pts

我们发现可以滚动数组,把第一位滚掉就可

for (int i=3;i<=n;i++)
        for (int j=1;j<=i-1;j++)
        {
            for (int k=1;k<=j-1;k++) f[j][i]=(f[j][i]+(f[k][j]+1)*((a[i].x<max(a[j].x,a[k].x)&&a[i].x>min(a[j].x,a[k].x)) ? 1 : 0))%mod;
            for (int k=1;k<=j-1;k++) f[k][j]=f[k][j]%mod;
        }
    for (int i=1;i<=n;i++)
        for (int j=1;j<=i-1;j++)
            ans=(ans+f[j][i])%mod;
    printf("%lld",(ans+(n*(n-1)/2)+n)%mod);

pts

我想了半天,只有一个树状数组维护的方法,我们给每一个点都开一颗树状数组。以各个数的排名作为下表,所以这是一颗值域树状数组。
那么他维护的含义是:在 之前的点中,排名为 的点对 点做出的贡献,即
那么我们每次 枚举 ,那么对于第三位 考虑用树状数组去做,我们发现满足要求的 有一个性质是要与 的权值作比较,我们先比较 大小,在判定 是找小于 的,还是大于 的,这个找的过程,其实就是在第 颗树状数组中 查出 的前驱或者后记的 总价值。总时间复杂度

我们发现这空间不够用,所以我们只需要开两颗树状数组,模仿着滚动数组的样子,一次清空,因为时间复杂度已经是 往上的级别了,所以清空完全可以承受,只会增加一点点常熟,所以可以用时间换空间。

以下是树状数组为滚动的代码

/*
树状数组优化+离散化 
*/
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+7;
const int B=6009;
int f[B][B];
struct node{int x,y;} a[B];
int n;
int b[B];
int t[6009][6009];
int lowbit(int x) {return x&(-x);}
void modify(int x,int v,int t1[]) {while (x<=n) t1[x]+=v,x+=lowbit(x);}
int query(int x,int t1[]) {int res=0; while (x) res+=t1[x],x-=lowbit(x);return res;}
namespace ne
{
    int t[6009][6009];
    void modify(int x,int v,int t1[]) {while (x<=n+10) t1[x]+=v,x+=lowbit(x);}
    int query(int x,int t1[]) {int res=0; while (x) res+=t1[x],x-=lowbit(x);return res;}
}
int cmp(node a,node b) 
{
    return a.y>b.y;
}
int newnum[6009];
signed main()
{
    ios::sync_with_stdio(0);
    cin>>n;
    for (int i=1;i<=n;i++) 
    {
        cin>>a[i].x;
        cin>>a[i].y;
        b[i]=a[i].x;
    }
    sort(a+1,a+1+n,cmp);
    sort(b+1,b+1+n); 
    for (int i=1;i<=n;i++)
    {
        newnum[i]=lower_bound(b+1,b+1+n,a[i].x)-b;
    }
    int ans=0;
    ne::modify(newnum[1],1,ne::t[2]);
    for (int i=3;i<=n;i++)
    {
        int st=newnum[i]; 
        ne::modify(newnum[1],1,ne::t[i]);
        for (int j=2;j<=i-1;j++)
        {
            if (a[i].x>a[j].x)
            {
                f[j][i]=((query(n,t[j])-query(st,t[j]))%mod+mod)%mod;
                f[j][i]=(f[j][i]+ne::query(n,ne::t[j])-ne::query(st,ne::t[j])+mod)%mod;
                modify(newnum[j],f[j][i],t[i]);
                ne::modify(newnum[j],1,ne::t[i]);
            }
            else
            {
                f[j][i]=query(st-1,t[j])%mod;
                f[j][i]=(f[j][i]+ne::query(st-1,ne::t[j]))%mod;
                modify(newnum[j],f[j][i],t[i]);
                ne::modify(newnum[j],1,ne::t[i]);
            } 
        }
    }
    for (int i=1;i<=n;i++)
        for (int j=1;j<=i-1;j++)
            ans=(ans+f[j][i])%mod;
    printf("%lld",(ans+(n*(n-1)/2)+n)%mod);
    return 0;
}

全部评论

(0) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐