洛谷7月月赛题解

D题没做出来，待补。 补完了

A-P5461 赦免战俘

题意

不停的把矩形左上角的数变成 $0$ ，然后继续分治求解剩下三部分，输出矩形最后的形态。

矩形大小为 $2^N\times 2^N$ ，$N\le 10$ 。

题解

直接按题意模拟即可。

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

int n;
bool s[1025][1025];

void work(int x1,int y1,int x2,int y2)
{
    if (x2==x1) return;
    int midx=(x1+x2)>>1,midy=(y1+y2)>>1;
    for (int i=x1;i<=midx;i++) for (int j=y1;j<=midy;j++) s[i][j]=1;
    work(midx+1,y1,x2,midy);
    work(x1,midy+1,midx,y2);
    work(midx+1,midy+1,x2,y2);
}

signed main()
{
    n=1<<read();
    work(1,1,n,n);
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=n;j++) printf("%d ",!s[i][j]);
        puts("");
    }
    return 0;
}

B-P5462 X龙珠

题意

给出长度为 $N$ 的序列，$N$ 为偶数，每次取相邻的两数输出，求字典序最大的输出序列。

$N\le 10^5$ 。

题解

每次贪心找当前最大的数和它的后一个，注意序列末尾的不能取。我比较懒就直接用优先队列。

然后用数组模拟链表，把当前数和它下一个删掉即可。

#include<bits/stdc++.h>
#define pr pair<int,int>
#define mp make_pair

using namespace std;

inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

priority_queue <pr> q;
int n,s[100005],l[100005],r[100005];
bool vis[100005];

inline void del(int x)
{
    vis[x]=1;
    r[l[x]]=r[x];
    l[r[x]]=l[x];
}

signed main()
{
    n=read();
    for (int i=1;i<=n;i++)
    {
        q.emplace(mp(s[i]=read(),i));
        l[i]=i-1;
        r[i]=i+1;
    }
    while (!q.empty())
    {
        int x=q.top().first,y=q.top().second; q.pop();
        if (vis[y] || r[y]==n+1) continue;
        printf("%d %d ",x,s[r[y]]);
        del(y); del(r[y]);
    }
    return 0;
}

C-P5463 小鱼比可爱（加强版）

题意

用 $\text{cnt[i][j]}$ 表示区间 $[i,j]$ 的逆序对个数，求：

$$\sum_{i=1}^n \sum_{j=i}^n \text{cnt[i][j]}$$

题解

考虑每个逆序对 $(S_i,S_j)$ 对答案的贡献。显然它会对所有 起点 $\in [1,i]$ 以及终点 $\in [j,n]$ 的区间 产生 $1$ 的贡献，总的贡献为

$$i\times (n-j+1)\tag{1}$$

然后考虑固定的 $S_j$ 的贡献，对于所有 $i<j$ 且 $S_i>S_j$ ，这个 $S_i$ 都会产生 $(1)$ 中的贡献。设 $T_k$ 表示在 $j$ 之前所有数值 $k$ 的下标和，那么每个 $j$ 的贡献为

$$\sum T_k \ , \ k>S_j$$

显然 $T_k$ 可以离散化后用树状数组维护，所以枚举每个 $j$ 就可以得到答案了。

实际上就是把求逆序对时 $+1$ 给换成了 $+$ 当前下标，查询时把答案 $\times (n-i+1)$ 。

答案会爆 long long ，我直接用 __int128 水过了。

#include<bits/stdc++.h>
#define ll long long

using namespace std;

inline ll read()
{
    char ch=getchar();
    ll f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

struct node {
    ll s,id;
} s[1000005];
ll n,ord[1000005],t[1000005];

inline ll lowbit(ll x) { return x&-x; }

inline void add(ll x,ll y) { for (;x<=n;x+=lowbit(x)) t[x]+=y; }

inline ll query(ll x)
{
    ll ans=0;
    for (;x;x-=lowbit(x)) ans+=t[x];
    return ans;
}

inline bool cmp(const node &x,const node &y) { return x.s==y.s ? x.id>y.id : x.s>y.s; }

void print(__int128 x)
{
    if (x==0) return;
    print(x/10);
    putchar(x%10+'0');
}

signed main()
{
    n=read();
    for (ll i=1;i<=n;i++) s[i].s=read(),s[i].id=i;
    sort(s+1,s+n+1,cmp);
    for (ll i=1;i<=n;i++) ord[s[i].id]=i; //离散化
    __int128 ans=0;
    for (ll i=1;i<=n;i++)
    {
        add(ord[i],i);
        ans+=query(ord[i]-1)*(n-i+1);
    }
    if (ans==0) puts("0");
    else print(ans);
    return 0;
}

D-P5464 缩小社交圈

题意

如果两个区间有相交的区域，就对它们连条边。从中选出一些区间，要求连成的图不能有环，求方案数。

区间个数 $N\le 2000$，区间大小 $\le 4000$ 。

题解

先按照右端点从小到大排序。用 $\text{f[i][j]}$ 表示当前选第 $i$ 个区间，上一次选第 $j$ 个时的方案数。用 $L_i,R_i$ 表示第 $i$ 个区间的左、右端点。

显然 $j$ 区间要和 $i$ 区间有交集才能转移，即需要满足 $R_j > L_i$ 。

考虑选取 $j$ 的上一个区间 $k$ 。当 $L_j < L_i$ ，即 $i$ 不能把 $j$ 完全包含时，那么只用满足 $R_k < L_i$ 即可。转移方程式为：

$$\text{f[i][j]} = \sum_{k=0}^{i-1} \text{f[j][k]} \ (R_k < L_i)$$

如果 $L_j > L_i$ ，即 $i$ 把 $j$ 完全包含，那么满足 $R_k < L_j$ 即可。

但是这样就不满足转移的条件，即 $R_k > L_j$ 了。所以把 $j$ 和 $k$ 交换位置，先选 $k$ ，就可以解决这个问题。转移方程为：

$$\text{f[i][j]} = \sum_{k=0}^{i-1} \text{f[i][k]} \ (R_k < L_j)$$

初值为 $\text{f[i][0]}=1$ 。

用三重循环暴力枚举显然会爆，而 $k$ 的范围每次又是单调递增的，所以可以用树状数组优化掉 $k$ 。

注意取模和开 long long 。

#include<bits/stdc++.h>
#define ll long long
#define ha 1000000007

using namespace std;

inline ll read()
{
    char ch=getchar();
    ll f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

struct node {
    ll l,r;
} s[2005];
ll n,N,ans,t[2005][4005];

inline ll lowbit(ll x) { return x&-x; }

inline void add(ll x,ll y,ll id) { for (x++;x<=N;x+=lowbit(x)) t[id][x]=(t[id][x]+y)%ha; }

inline ll query(ll x,ll id)
{
    ll ans=0;
    for (x++;x;x-=lowbit(x)) ans=(ans+t[id][x])%ha;
    return ans;
}

signed main()
{
    n=read();
    for (ll i=1;i<=n;i++) s[i].l=read(),s[i].r=read(),N=max(N,s[i].r);
    N++;
    sort(s+1,s+n+1,[](const node &x,const node &y) { return x.r==y.r ? x.l<y.l : x.r<y.r; });
    for (ll i=1;i<=n;i++) add(0,1,i); 
    ans=n;
    for (ll i=2;i<=n;i++)
    {
        for (ll j=1;j<i;j++)
        {
            if (s[j].r<s[i].l) continue;
            ll cur;
            if (s[i].l>=s[j].l) cur=query(s[i].l-1,j);
            else cur=query(s[j].l-1,i);
            add(s[j].r,cur,i);
            ans=(ans+cur)%ha;
        }
    }
    printf("%lld",ans);
    return 0;
}