洛谷七月月赛题解
赛题 #A: P5461 赦免战俘
题目大意：
现有一个 $ 2^n imes 2^n (nle10) $ 的正方形矩阵，初始时全部为1。现将正方形矩阵均分为 4 个更小的正方形矩阵，其中左上角那一个矩阵的所有元素变为0，剩下 3 个小矩阵中，每一个矩阵继续均分为 4 个更小的矩阵，直到矩阵无法再分下去为止。现在给出 $ n $ ，请你输出最终矩阵，元素之间有空格。
$ solution: $
这道题很简单，就是一道小模拟，但是大家的模拟可以说各有千秋。这道题当然可以直接递归模拟，但运行速度和码量都不快，而且需要注意边界。我们如果仔细分析样例不难发现这个矩阵就是一开始第一行最后一个为1，然后下面几行 $ f[i][j]=f[i-1][j]~xor~f[i-1][j+1] $ 。然后边转移边输出，方便快捷。
当然我们还可以用二进制 $ bitset $ 来完成这个任务。进一步优化速度。
$ code: $
#include<bits/stdc++.h>
using namespace std;
bitset<1031> f[1031];
int main(){
int n; cin>>n;
int m=1<<n; f[1][m]=1;
for(int i=1;i<m;i<<=1)
for(int j=1;j<=i;++j)
f[j+i]|=f[j]|(f[j]>>i);
for(int i=1;i<=m;++i)
for(int j=1;j<=m;++j)
printf("%d%c",bool(f[i][j]),j==m?'
':' ');
return 0;
}
赛题 #B: P5462 X龙珠
题目大意：
有个由数 $ 1～n $ 组成的排列，保证 $ n $ 为整数。现在可以从中取出两个相邻的数，知道取完为止。现要求你输出取出数列字典序最大的方案。
$ solution: $
这道题看起来很简单，直接贪心的取出较大的数即可。但需要注意可能有两个原本不相邻的数，因为他们中间的数全被取走而变得相邻。所以我们先开一个优先队列把所有满足条件的相邻数对都加进去，然后开一个链表来动态记录这个排列，每一次取出某两个相邻数对时在链表上删除对应的数，然后在加入新的相邻的数对到优先队列里去。
$ code: $
#include<iostream>
#include<cstdio>
#include<iomanip>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<bitset>
#include<vector>
#include<queue>
#include<map>
#include<set>
#define ll long long
#define db double
#define rg register int
using namespace std;
int n;
int a[100005];
bitset<100005> d;
struct su{
int x,y,z;
inline bool operator <(const su z)const{
return x<z.x;
}
};
priority_queue<su> q;
struct pi{
int l,r;
}b[100005];
inline int qr(){
register char ch; register bool sign=0; rg res=0;
while(!isdigit(ch=getchar()))if(ch=='-')sign=1;
while(isdigit(ch))res=res*10+(ch^48),ch=getchar();
if(sign)return -res; else return res;
}
inline void cut(int i){
rg x=b[i].l,y=b[b[i].r].r;
b[x].r=y; b[y].l=x;
if(y<=n)q.push(su{a[x],a[y],x});
}
int main(){
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
n=qr();
for(rg i=1;i<=n;++i){
a[i]=qr();
b[i].l=i-1;
b[i].r=i+1;
}
for(rg i=1;i<n;++i)
q.push(su{a[i],a[i+1],i});
for(rg i=1;i<=n;i+=2){
register su s;
while(!q.empty()){
s=q.top(); q.pop();
if(!d[s.x]&&!d[s.y])break;
}d[s.x]=d[s.y]=1; cut(s.z);
printf("%d %d",s.x,s.y);
if(i!=n-1)cout<<" ";
}cout<<endl;
return 0;
}
赛题 #C: P5463 小鱼比可爱（加强版）
题目大意：
给你一个长度为 $ n $ 的数列，可以预见它必定有 $ frac{n imes(n+1)}{2} $ 个不同的子数列。现在需要你求出所有这些子数列的逆序对之和。
$ solution: $
对于区间里任意一对逆序对 $ (i,j) $
- 因为区间可以向左延伸，所以 $ (i,j) $ 的贡献会被多计算 $ i $ 次
- 因为区间可以向右延伸，所以 $ (i,j) $ 的贡献会被重复计算 $ n-j+1 $ 次
注意性质1和性质2之间是乘法关系！然后我们就可以用树状数组解决这个问题了！
我们树状数组在将 $ i $ 号元素加入时，其所加权值应该是 $ i $ ，这样才能满足性质1。然后我们可以用树状数组计算出以 $ i $ 为逆序对中较小的值的所有逆序对的总贡献，然后再乘上性质2中对应的值，就可以得到所有包含 $ i $ 号元素的区间里 $ i $ 作为逆序对中较小一员的贡献。然后 $ 1～n $ 所有数的贡献即为所求。
不过这一题还需要用高精度，这个需要注意一下。
$ code: $
#include<iostream>
#include<cstdio>
#include<iomanip>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
#define ll long long
#define db double
#define rg register int
using namespace std;
int n;
ll ans;
int b[1000005];
ll s[1000005];
struct su{
int x,y;
inline bool operator <(const su &z){
return x>z.x;
}
}a[1000005];
inline int qr(){
register char ch; register bool sign=0; rg res=0;
while(!isdigit(ch=getchar()))if(ch=='-')sign=1;
while(isdigit(ch))res=res*10+(ch^48),ch=getchar();
if(sign)return -res; else return res;
}
inline void add(int x,int v){
for(;x<=n;x+=x&-x)s[x]+=v;
}
inline ll ask(int x){
ll res=0;
for(;x;x-=x&-x) res+=s[x];
return res;
}
int main(){
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
n=qr();
for(rg i=1;i<=n;++i) a[i]={qr(),i};
sort(a+1,a+n+1);
for(rg i=1,j=1;i<=n;++i){
if(a[i].x!=a[i-1].x)j=i;
b[a[i].y]=j;
}
for(rg i=1;i<=n;++i){
ans+=(ll)ask(b[i]-1)*(n-i+1);
add(b[i],i);
}printf("%lld
",ans);
return 0;
}
赛题 #D: P5464 缩小社交圈
题目大意：
社交圈子里有 $ n $ 个人，每个人都有一个 $ SAN $ 值范围 $ [l_i,r_i] $ 。当两个人的 SAN 值交集不为空时，这两个人有 PY 关系。现在希望从社交圈子里面挑选出一些人组成一个集合 $ S $ ，如果将所有集合内的人中有 PY 关系的那一对人都连上边，则 $ S $ 刚好成为一个树（森林不行哦）。请问，有多少种可以选择的方案？由于答案可能很大，请对 $ 10^{9} $ 取模。
$ solution: $
这道题博主的做法有点绕，我们首先将这些人按照区间左端点排序。然后我们发现如果选出的人要构成一棵树，那么对于任意一个点，它都不能被三个人覆盖，否则就会有环的出现。于是我们发现这颗树在区间上是线性左右延伸的，于是我们考虑线性DP。设 $ f[i][j] $ 表示（从左到右）最后一个人为 $ i $ 倒数第二个人为 $ j $ 可以构成的树，之所以这样设是因为它很好转移：
首先所有 $ f[i][i] $ 必定为一颗单点树，然后我们的 $ f $ 数组默认 $ f[i][j] $ 中 $ i $ 的右端点必须比 $ j $ 的大，这样对之后转移才有意义，也避免了重复。我们转移时枚举 $ j|j_r<i_l;~,~k|k_r<j_l $ ，即 $ i $ 和 $ j $ 有交集， $ k $ 和 $ j $ 有交集，而 $ k $ 和 $ i $ 无交集。于是：
$ { ^{f[i][j]+=f[j][k]~,~(i_r>j_r)}_{f[j][i]+=f[j][k]~,~(i_r<j_r)} $
具体枚举过程我们可以用优先队列优化，使得复杂度最终为 $ n^2 $
$ code: $
#include<iostream>
#include<cstdio>
#include<iomanip>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
#define ll long long
#define db double
#define rg register int
using namespace std;
const int mod=1e9+7;
int n;
ll ans;
ll g[2005];
ll f[2005][2005];
bool d[2005];
struct su{
int l,r;
inline bool operator <(const su &x)const{
if(l==x.l)return r>x.r; else return l<x.l;
}
}a[2005];
struct pi{
int x,y;
inline bool operator <(const pi &z)const{return x>z.x;}
};
priority_queue<pi> q;
inline int qr(){
register char ch; register bool sign=0; rg res=0;
while(!isdigit(ch=getchar()))if(ch=='-')sign=1;
while(isdigit(ch))res=res*10+(ch^48),ch=getchar();
if(sign)return -res; else return res;
}
int main(){
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
n=qr();
for(rg i=1;i<=n;++i) a[i]=su{qr(),qr()};
sort(a+1,a+n+1);
for(rg i=1;i<=n;++i){
while(!q.empty()&&q.top().x<a[i].l){
rg x=q.top().y; d[x]=0; q.pop();
for(rg j=1;j<=n;++j)
if(d[j])(g[j]+=f[j][x])%=mod;
} q.push(pi{a[i].r,i}); d[i]=1; f[i][i]=1;
for(rg j=1;j<=n;++j){
if(!d[j]||i==j)continue;
if(a[j].r>a[i].r)f[j][i]+=1+g[j];
else f[i][j]+=1+g[j];
(ans+=1+g[j])%=mod;
}
} printf("%lld
",(ans+n)%mod);
return 0;
}