T1 空
题意
给定一个排列 \(p\) 和一个数 \(b\)，求这个排列有多少长度为奇数的子段的中位数是 \(b\)。
赛时
观察性质。
题解
考虑把排列中大于 \(b\) 的数变成 \(1\)，小于 \(p\) 的数变成 \(-1\)。
所以做个前缀和，把 \(b\) 右边的所有数存到 map 里，扫左边匹配就做完了。
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3f3f3f
using namespace std;int n,b;
int a[200010];map<int,int> d;int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>n>>b;for(int i=1;i<=n;i++) cin>>a[i];int pos=0;for(int i=1;i<=n;i++){if(a[i]<b) a[i]=-1;else if(a[i]>b) a[i]=1;else a[i]=0,pos=i;}for(int i=1;i<=n;i++) a[i]+=a[i-1];long long ans=0;for(int i=pos;i<=n;i++) d[a[i]]++;for(int i=1;i<=pos;i++) ans+=d[a[i-1]];cout<<ans<<"\n";# ifndef ONLINE_JUDGEcerr<<"\nUsed time: "<<clock()*1.0/CLOCKS_PER_SEC<<"s.\n";# endifreturn 0;
}
T2 紫
题意
给定一个序列 \(a\)。
定义 \(f(x,y)\) 为 \(x\) 和 \(y\) 在二进制表示下有多少个不同的位置。
对于每个 \(a_i\) 求出 \(\max_{j=1}^{n}f(a_i,a_j)\)。
赛时
被卡了好久。
题解
显然所求是异或后最大的 \(\operatorname{popcount}\)。
反过来考虑，求的就是取反后和序列中其他数的最小差异位数。
所以对序列中所有数为起点跑个 bfs 就做完了。
存在字典树做法，但我懒了。
如果想看乱搞做法可以去找 mhh。
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3f3f3f
using namespace std;int n,m;int a[1048577];bool vis[1048577];
int d[1048577];
queue<int> q;
void solve(){for(int i=1;i<=n;i++) q.push(a[i]),d[a[i]]=0,vis[a[i]]=1;while(!q.empty()){int x=q.front();q.pop();for(int i=0;i<m;i++){int y=x^(1<<i);if(vis[y]) continue;vis[y]=1;d[y]=d[x]+1;q.push(y);}}
}int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>n>>m;for(int i=1;i<=n;i++) cin>>a[i];solve();for(int i=1;i<=n;i++) cout<<m-d[a[i]^((1<<m)-1)]<<" ";# ifndef ONLINE_JUDGEcerr<<"\nUsed time: "<<clock()*1.0/CLOCKS_PER_SEC<<"s.\n";# endifreturn 0;
}
T3 花
题意
给定长为 \(n\) 的序列 \(a,b\)，求：
\[\sum_{i=1}^{n}\sum_{j=1}^{i-1}C_{a_i+a_j+b_i+b_j}^{a_i+a_j}
\]
的值。
对 \(998244853\) 取模。
赛时
20 pts 暴力。
题解
考虑组合意义。
对于一对 \((i,j)\)，可以看作是 \((0,0)\) 走到 \((a_i+a_j,b_i+b_j)\)，只能朝上、右走的路径方案数。
把这个东西平移成从 \((-a_i,-b_i)\) 走到 \((a_j,b_j)\)。
注意到 \(V\) 很小。所以我们把每个 \((-a_i,-b_i)\) 的位置加 \(1\)，然后跑一个经典 dp，答案就是所有 \((a_i,b_i)\) 处的数之和。
但是会算重。首先减去 \(i\) 贡献到 \(i\) 的方案数 \(C_{2a_i+2b_i}^{2a_i}\)。
最后的最后再除个 \(2\)。因为一个点对会算两次。
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3f3f3f
using namespace std;const long long mod=998244853;
long long qpow(long long x,long long a){long long res=1;while(a){if(a&1) res=res*x%mod;x=x*x%mod;a>>=1;}return res;
}
long long fac[200010];
long long C(long long n,long long m){return fac[n]*qpow(fac[n-m]*fac[m]%mod,mod-2)%mod;}int n;
int a[200010],b[200010];
int dp[5010][5010];int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>n;for(int i=1;i<=n;i++) cin>>a[i]>>b[i];for(int i=1;i<=n;i++) dp[2500-a[i]][2500-b[i]]++;fac[0]=1;for(int i=1;i<=200000;i++) fac[i]=fac[i-1]*i%mod;for(int i=1;i<5000;i++) for(int j=1;j<5000;j++) (dp[i][j]+=dp[i-1][j]+dp[i][j-1])%=mod;long long ans=0;for(int i=1;i<=n;i++) ans=(ans+dp[2500+a[i]][2500+b[i]]-C(2*(a[i]+b[i]),2*a[i])+mod)%mod;cout<<ans*qpow(2,mod-2)%mod<<"\n";# ifndef ONLINE_JUDGEcerr<<"\nUsed time: "<<clock()*1.0/CLOCKS_PER_SEC<<"s.\n";# endifreturn 0;
}
总结
T3 T4 打不动一点。