两天都没改多少题，合在一起写吧?
CSP模拟55
A.签
原题链接：https://atcoder.jp/contests/arc102/tasks/arc102_d
神奇的结论题。赛时想了个类似于冒泡排序的东西，初始逆序对个数是 \(n^2\) 级别的，每次消掉 3 个逆序对，最坏一次操作遍历整个数组，所以复杂度上界是 \(O(n^3)\)。但是 \(n\le 2000\) 还跑的挺快的（？）能得 50 分。
正解：
- 初始一个数下标和值奇偶性不同直接判断无解。因为每次操作每个数所在下标奇偶性不改变。
- 有解的充要条件是初始下标为奇数和偶数的数分别构成的两个序列的逆序对个数之和是原序列逆序对个数的 \(\frac{1}{3}\)。首先因为一次操作减少 3 个逆序对，所以若有解，原序列的逆序对个数一定是 3 的倍数。再考虑一次操作会使下标为奇数或者偶数构成的序列逆序对个数减少 1。即每次整个序列逆序对减少 3 一定伴随着下标为奇数或偶数之一的数构成的序列逆序对数量减 1，因此得证。
然后就求个逆序对个数就好了，时间复杂度 \(O(n\log n)\)。
点击查看代码
#include<bits/stdc++.h>
using ll=long long;
int n,a[300005],pos[300005];
struct FenwickTree{
int c[300005];
inline void clear(){memset(c,0,sizeof c);}
inline void modify(int x,int v){for(;x<=n;x+=x&-x)c[x]+=v;}
inline int query(int x){int sum=0;for(;x;x-=x&-x)sum+=c[x];return sum;}
}t,t1,t2;
inline void solve(){
t.clear();t1.clear();t2.clear();
std::cin>>n;for(int i=1;i<=n;++i)std::cin>>a[i];
for(int i=1;i<=n;++i)if((a[i]&1)^(i&1))return std::cout<<"No\n",void();
ll ans=0;
for(int i=n;i;--i)t.modify(a[i],1),ans+=t.query(a[i]-1);
if(ans%3)return std::cout<<"No\n",void();
ll ans1=0,ans2=0;
for(int i=n;i>=1;i-=2)t1.modify(a[i],1),ans1+=t1.query(a[i]-1);
for(int i=n-1;i>=1;i-=2)t2.modify(a[i],1),ans2+=t2.query(a[i]-1);
(ans1+ans2)*3==ans?std::cout<<"Yes\n":std::cout<<"No\n";
}
int main(){
std::cin.tie(nullptr)->sync_with_stdio(false);
freopen("nk.in","r",stdin);freopen("nk.out","w",stdout);
int T;std::cin>>T;while(T--)solve();
return 0;
}
B.数据结构基础练习题
P3863 序列 + P5356 [Ynoi2017] 由乃打扑克
朴素暴力时空复杂度 \(O(n^2)\) 的，空间过不了。
赛时打的主席树标记永久化，空间复杂度 \(O(n\log n)\)，但时间复杂度 \(O(n^2\log n)\)，也过不了?
考虑将操作离线下来做扫描线。扫描线扫下标，然后简单分块维护时间轴就好了。时间复杂度 \(O(m\sqrt{m\log m } \log m)\)。
点击查看代码
#include<bits/stdc++.h>
int n,m,cnt,a[70005],bel[70005],L[300],R[300],tag[300],ans[70005],bnum,bsiz;
std::vector<int> blo[300];
struct offline{
int opt,tim,idx,x,y,z;
bool operator<(const offline &rhs)const{return idx==rhs.idx?tim<rhs.tim:idx<rhs.idx;}
}q[140005];
inline void build(){
bsiz=sqrt(m);bnum=m/bsiz;
for(int i=1;i<=bnum;++i)L[i]=R[i-1]+1,R[i]=i*bsiz;R[bnum]=m;
for(int i=1;i<=bnum;++i)for(int j=L[i];j<=R[i];++j)bel[j]=i,blo[i].push_back(0);
}
inline void rebuild(int x){
blo[x].clear();
for(int i=L[x];i<=R[x];++i)blo[x].push_back(a[i]);
std::sort(blo[x].begin(),blo[x].end());
}
inline void modify(int x,int v){
for(int i=x;i<=R[bel[x]];++i)a[i]+=v;rebuild(bel[x]);
for(int i=bel[x]+1;i<=bnum;++i)tag[i]+=v;
}
inline int query(int l,int r,int x){
int ans(0);
if(bel[l]==bel[r]){
for(int i=l;i<=r;++i)(a[i]+tag[bel[l]]<=x)&&(ans++);
return ans;
}
for(int i=l;i<=R[bel[l]];++i)(a[i]+tag[bel[l]]<=x)&&(ans++);
for(int i=L[bel[r]];i<=r;++i)(a[i]+tag[bel[r]]<=x)&&(ans++);
for(int i=bel[l]+1;i<bel[r];++i)ans+=std::upper_bound(blo[i].begin(),blo[i].end(),x-tag[i])-blo[i].begin();
return ans;
}
inline int solve(int l,int r,int x){
int left=-70000000,right=70000000,mid,ans;
while(left<=right){
mid=left+right>>1;
if(query(l,r,mid)>=x)ans=mid,right=mid-1;
else left=mid+1;
}
return ans;
}
int main(){
freopen("ds.in","r",stdin);freopen("ds.out","w",stdout);
std::cin.tie(nullptr)->sync_with_stdio(false);
std::cin>>n>>m;m++;build();
std::fill(ans,ans+m+1,70000001);
for(int i=2,opt,l,r,x,y;i<=m;++i){
std::cin>>opt;
if(!opt)std::cin>>l>>r>>x,q[++cnt]={1,i,l,x,0,0},q[++cnt]={1,i,r+1,-x,0,0};
else std::cin>>x>>l>>r>>y,q[++cnt]={2,i,x,l+1,r+1,y};
}
std::sort(q+1,q+1+cnt);
for(int i=1;i<=cnt;++i){
const auto &now=q[i];
if(now.opt==1)modify(now.tim,now.x);
else ans[now.tim]=solve(now.x,now.y,now.z);
}
for(int i=2;i<=m;++i)if(ans[i]!=70000001)std::cout<<ans[i]<<'\n';
return 0;
}
CSP模拟55
A.醉
简单题。在树上距离一个点最远的点一定在树的直径上。然后倍增跳一跳就做完了。时间复杂度 \(O(n\log n)\)。但似乎有 \(O(n)\) 做法，不管了，反正也不卡常。赛时最慢点跑了 460ms。
点击查看代码
#include<bits/stdc++.h>
using ll=long long;
std::vector<int> g[200005];
int n,m,dep[200005],mxdep,head=1,tail=1,dep2[200005];
int st[200005][21];
void dfs1(int x,int f){
st[x][0]=f;for(int i=1;i<=20;++i)st[x][i]=st[st[x][i-1]][i-1];
dep[x]=dep[f]+1;
if(mxdep<dep[x])mxdep=dep[x],head=x;
for(int &y:g[x]){
if(y==f)continue;
dfs1(y,x);
}
}
void dfs2(int x,int f){
dep2[x]=dep2[f]+1;
if(mxdep<dep2[x])mxdep=dep2[x],tail=x;
for(int &y:g[x]){
if(y==f)continue;
dfs2(y,x);
}
}
inline int lca(int x,int y){
if(dep[x]<dep[y])std::swap(x,y);
for(int i=20;~i;--i)if(dep[st[x][i]]>=dep[y])x=st[x][i];
if(x==y)return x;
for(int i=20;~i;--i)if(st[x][i]^st[y][i])x=st[x][i],y=st[y][i];
return st[x][0];
}
int main(){
freopen("intoxicated.in","r",stdin);freopen("intoxicated.out","w",stdout);
std::cin.tie(nullptr)->sync_with_stdio(false);
std::cin>>n;for(int i=1,u,v;i<n;++i)std::cin>>u>>v,g[u].push_back(v),g[v].push_back(u);
dfs1(1,0);dfs2(head,0);
std::cin>>m;
for(int u,d;m;--m){
std::cin>>u>>d;
int hl=lca(u,head),tl=lca(u,tail),mx=0;
if(dep[u]+dep[head]-2*dep[hl]>dep[u]+dep[tail]-2*dep[tl]){
mx=dep[u]+dep[head]-2*dep[hl];
if(mx<d)std::cout<<-1<<'\n';
else{
int x;
if(d<=dep[u]-dep[hl]){
x=u;
for(int i=20;~i;--i)if(dep[st[x][i]]>=dep[hl]+(dep[u]-dep[hl]-d))x=st[x][i];
std::cout<<x<<'\n';
}
else{
x=head;
for(int i=20;~i;--i)if(dep[st[x][i]]>=dep[hl]+(d-(dep[u]-dep[hl])))x=st[x][i];
std::cout<<x<<'\n';
}
assert(dep[u]+dep[x]-2*dep[lca(u,x)]==d);
}
}
else{
mx=dep[u]+dep[tail]-2*dep[tl];
if(mx<d)std::cout<<-1<<'\n';
else{
int x;
if(d<=dep[u]-dep[tl]){
x=u;
for(int i=20;~i;--i)if(dep[st[x][i]]>=dep[tl]+(dep[u]-dep[tl]-d))x=st[x][i];
std::cout<<x<<'\n';
}
else{
x=tail;
for(int i=20;~i;--i){
if(dep[st[x][i]]>=dep[tl]+(d-(dep[u]-dep[tl])))x=st[x][i];
}
std::cout<<x<<'\n';
}
assert(dep[u]+dep[x]-2*dep[lca(u,x)]==d);
}
}
}
return 0;
}
B.与
看到与运算就应该立刻要按位考虑。
设 \(f_{i,j}\) 表示编号小于 \(i\) 且第 \(j\) 位为 1 的最大编号，这个可以从 \(f_{i-1,j}\) 求出来。
设 \(g_{i,j}\) 表示能够到达 \(i\) 且第 \(j\) 位为 1 的最大编号。
枚举一个转移点 \(k\)。
如果 \(i\) 能从第 \(k\) 位为 1 的数转移过来，就有 \(g_{i,j}\gets g_{f_{i,k}\,,j}\)。
如果 \(f_{i,k}\) 的第 \(j\) 位上本来就是 1。就可以直接 \(g_{i,j}\gets f_{i,k}\)。
判断答案的时候，若 \(a_x\) 的第 \(i\) 位为 1。而且 \(g_{y,i}\ge x\)，那么就是可以到达的。
总体时间复杂度 \(O(n\log^2 n)\)。
点击查看代码
#include<bits/stdc++.h>
using ll=long long;
int n,q,a[300005],f[300005][20],g[300005][20];
inline bool check(int x,int y){
if(!a[x]||!a[y])return false;
for(int i=0;i<20;++i)
if((a[x]&(1<<i))&&(g[y][i]>=x))return true;
return false;
}
int main(){
freopen("and.in","r",stdin);freopen("and.out","w",stdout);
std::cin.tie(nullptr)->sync_with_stdio(false);
std::cin>>n>>q;
for(int i=1;i<=n;++i)std::cin>>a[i];
for(int i=1;i<=n;++i){
for(int j=0;j<20;++j){
if(a[i-1]&(1<<j))f[i][j]=i-1;
else f[i][j]=f[i-1][j];
}
}
for(int i=1;i<=n;++i){
for(int j=0;j<20;++j){
for(int k=0;k<20;++k){
if(a[i]&(1<<k)){
g[i][j]=std::max(g[i][j],g[f[i][k]][j]);
if(a[f[i][k]]&(1<<j))g[i][j]=std::max(g[i][j],f[i][k]);
}
}
}
}
for(int x,y;q;--q){
std::cin>>x>>y;
if(check(x,y))std::cout<<"Shi"<<'\n';
else std::cout<<"Fou"<<'\n';
}
return 0;
}