2023牛客多校训练第五场铜银牌题解
A
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+10,d=700;
int n,m,a[N],bl[N],ans[N],p[N],c[N],s[N],tr[N],t;
struct node{int l,r,id;}q[N];
bool cmp(node a,node b){
if(bl[a.l]!=bl[b.l])return bl[a.l]<bl[b.l];
if(bl[a.l]&1)return a.r<b.r;
else return a.r>b.r;
}
void add(int x){for(int i=x;i<=n;i+=i&-i)tr[i]+=1;}
int sum(int x){int a=0;while(x)a+=tr[x],x-=x&-x;return a;}
void addr(int x){int v=a[x];t+=p[x]*c[v]-s[v],c[v]++,s[v]+=p[x];}
void addl(int x){int v=a[x];t+=s[v]-p[x]*c[v],c[v]++,s[v]+=p[x];}
void delr(int x){int v=a[x];c[v]--,s[v]-=p[x],t-=p[x]*c[v]-s[v];}
void dell(int x){int v=a[x];c[v]--,s[v]-=p[x],t-=s[v]-p[x]*c[v];}
signed main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
add(a[i]);
bl[i]=i/700;
p[i]=sum(a[i]-1);
}
for(int i=1;i<=m;i++){
cin>>q[i].l>>q[i].r;
q[i].id=i;
}
sort(q+1,q+1+m,cmp);
int l=1,r=0;
for(int i=1;i<=m;i++){
int ql=q[i].l;
int qr=q[i].r;
int id=q[i].id;
while(r<qr)addr(++r);
while(l>ql)addl(--l);
while(r>qr)delr(r--);
while(l<ql)dell(l++);
ans[id]=t;
}
for(int i=1;i<=m;i++)cout<<ans[i]<<'\n';
}
B
对于一个长度为n的环,最小逆序对为n-1 在序列中，删掉一些点，如果只选x个的话，剩下的len-x个也会对逆序对做出贡献，所以总贡献为n-1+n-x
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int n,k,a[N];
signed main(){
cin>>n>>k;
for(int i=1;i<=n;i++)cin>>a[i];
int ans=1e9;
for(int i=1;i<=n;i++){
priority_queue<int>q;
int sum=0,x=0;
for(int j=i;j<=n;j++){
if(a[j]>=0)sum+=a[j],x++;
else q.push(a[j]);
if(sum>=k){
while(q.size()&&sum+q.top()>=k)sum+=q.top(),q.pop(),x++;
if(x)ans=min(ans,j-i+ j-i+1-x);
}
}
}
if(ans==1e9)ans=-1;
cout<<ans;
}
C
估计是数据太弱了，过了太多人 下面这个样例要输出6,绝大多数人的答案都是7是错的题解也是错的
7
0 1 0 1 1 1 1
0 0 1 1 1 1 1
1 0 0 1 1 1 1
0 0 0 0 1 1 1
0 0 0 0 0 1 0
0 0 0 0 0 0 1
0 0 0 0 1 0 0
把一组匹配i,j+n 视为连边ij ，那么这张图存在完美匹配即为可以将其所有点划分进若干回路 中。根据竞赛图的性质，其一定存在一条哈密顿路径，所以显然最大匹配至少为n-1 。再根据竞赛图 的性质，每个强连通分量必然存在一条哈密顿回路，所以答案为 等价于图中所有强连通分量大小均大 于等于2 。
所有的强连通分量大小至少为2则输出n，否则输出n-1
我们可以这样理解，这道题把二分图最大匹配和竞赛图的性质结合在一起 对于二分图的一个个匹配连通块，它其实是一个哈密顿回路，那么我们对ij连边，tarjan缩点，只要强连通块的sz>=2说明这是一个哈密顿回路
#include<bits/stdc++.h>
using namespace std;
const int N=3030;
int n,dfn[N],sz[N],low[N],o,scc_cnt,stk[N],id[N],top;
vector<int>g[N];
void tarjan(int u){
dfn[u]=low[u]=++o;
stk[++top]=u;
for(auto j:g[u]){
if(!dfn[j])tarjan(j),low[u]=min(low[u],low[j]);
else if(!id[j])low[u]=min(low[u],dfn[j]);//min( low[j]
}
if(dfn[u]==low[u]){
++scc_cnt;
int y;
do{
y=stk[top--];
id[y]=scc_cnt;
sz[scc_cnt]++;
}while(y!=u);
}
}
signed main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
int x;
cin>>x;
if(x)g[i].push_back(j);
}
}
for(int i=1;i<=n;i++){
if(!dfn[i])tarjan(i);
}
for(int i=1;i<=scc_cnt;i++){
if(sz[i]<2){
cout<<n-1;
return 0;
}
}
cout<<n;
}
竞赛图相关技巧的学习 对于一个竞赛图，一定有哈密顿通路
对于一个强连通竞赛图,一定有哈密顿回路
竞赛图缩点后肯定是一条链 有环一定是三元环
E
//对每一个区间交换最前面的r就好了
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int n,m,p[N],f[N],ne[N],ans[N],A[N];
struct node{
int l,r,w;
}a[N];
bool cmp(node a,node b){
int la=a.r-a.l;
int lb=b.r-b.l;
return la<lb;
}
signed main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++)p[i]=i,ne[i]=i,A[i]=i;
for(int i=0;i<m;i++)cin>>a[i].l>>a[i].r>>a[i].w;
sort(a,a+m,cmp);
for(int i=0;i<m;i++){
int l=a[i].l;
int r=a[i].r;
int w=a[i].w;
if(l==r){
if(w==1){cout<<-1;return 0;}
}
int ji=0;
for(int x=l;x<=r;x++)ji+=f[x];
if(w!=ji%2){
swap(p[ne[l]],p[ne[l]+1]);
f[l]++;
}
ne[l]=r;
}
for(int i=1;i<=n;i++)ans[p[i]]=i;
for(int i=1;i<=n;i++)cout<<ans[i]<<" ";
}
I
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10,mod=998244353;
int n,a[N],s[N],pre[N],suf[N],f[2][31];
signed main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n;
//处理前缀和,j=(0~i-1)
memset(f,0,sizeof f);
for(int j=0;j<=30;j++)f[0][j]=1;
int sum=0;
for(int i=1;i<=n;i++){
cin>>a[i];
sum^=a[i];
pre[i]=pre[i-1];
for(int j=0;j<=30;j++){
int x=sum>>j&1;
pre[i]+=(1<<j)*f[x^1][j];
pre[i]%=mod;
}
for(int j=0;j<=30;j++)f[sum>>j&1][j]++;
}
//处理后缀和 j=(i+1,n)
memset(f,0,sizeof f);
for(int j=0;j<=30;j++)f[0][j]=1;
for(int i=n;i>=1;i--){
s[i]=s[i+1]^a[i];
suf[i]=suf[i+1];
for(int j=0;j<=30;j++){
int x=s[i]>>j&1;
suf[i]+=(1<<j)*(f[x^1][j]);
suf[i]%=mod;
}
for(int j=0;j<=30;j++)f[s[i]>>j&1][j]++;
}
//计算总的,j=i+1~n
memset(f,0,sizeof f);
for(int j=0;j<=30;j++)f[0][j]=suf[n+1];//其实也就是0
int ans=0;
for(int i=n;i>=1;i--){
int x;
for(int j=0;j<=30;j++){
x=s[i]>>j&1;
ans+=pre[i-1]*f[x^1][j]%mod*(1<<j)%mod;
ans%=mod;
}
for(int j=0;j<=30;j++){
x=s[i]>>j&1;
f[x][j]+=suf[i];
f[x][j]%=mod;
}
}
cout<<ans;
}
也可以直接看下面两张图
京公网安备 11010502036488号