当前位置：首页 > news >正文

Codeforces Round 745 (Div. 2)(C:前缀和+滑动窗口，E：位运算加分块)

news 来源：原创 2024/5/15 19:39:59

Dashboard - Codeforces Round 745 (Div. 2) - Codeforces

A：

答案就是2n!/2,

对于当前满足有k个合法下标的排列，就是一个n-k个不合法的下标的排列，

所以每一个合法排列都相反的存在一个

对称性

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10,mod=1e9+7;
#define int long long
int n,m;
int f[N];
void solve()
{cin>>n;int res=1;for(int i=1;i<=2*n;i++){if(i==2) continue;res=res*i%mod;}cout<<res%mod<<"\n";
}signed main()
{cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int t=1;cin>>t;while(t--) solve();
}

B：

可以先手完一下，

对于一个n

如果m<n-1，那么这个图直接就不连通了，直接false

如果m==(n-1)*n/2，那么这个图就是完全无向连通图，直径最长是1

在这个中间，直径最长是2，直接在1点用n-1条边连其他点

然后特判啥的就行

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10,mod=1e9+7;
#define int long long
int n,m,k;
int f[N];
void solve()
{cin>>n>>m>>k;if(k<=1||m>n*(n-1)/2||m<n-1){cout<<"NO\n";return ;}if(n==1&&m==0){cout<<"YES\n";return ;} if(k==2||k==3&&m!=n*(n-1)/2){cout<<"NO\n";return ;}cout<<"YES\n";
}signed main()
{cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int t=1;cin>>t;while(t--) solve();
}

C：

这个题好像蓝桥杯之前写过，枚举三条线，然后滑动窗口来着

这个题基本一模一样

然后想上下两条线

先想一个问题

因为枚举的是D，那么D那条线答案是不用管的（因为我们枚举的第三条就是这个嘛），

然后想U,如果某个U到D和U+x到D，相同答案，那么选谁呢，其实都一样，如果D往下移，那么他们要加的公共部分都是一样的就是g[D][L],g[D][R],和D那条线，这个都是要加的，

如果要求某个[1,D-4]的线到D最小就行

快速统计矩阵的0，1用二维前缀和即可

#include<bits/stdc++.h>
using namespace std;
const int N = 410+10,mod=1e9+7;
#define int long long
int n,m,k;
char g[N][N];
int b[N][N];;
int s[N][N];
int row[N][N];
int col[N][N];
int val(int x1,int y1,int x2,int y2){//cin>>x1>>y1>>x2>>y2;return s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1];
}
int getrow(int i,int x,int y){return row[i][y]-row[i][x-1];
}
int getcol(int i,int x,int y){return col[i][y]-col[i][x-1];
}void solve()
{cin>>n>>m;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>g[i][j];s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+(g[i][j]-'0');row[i][j]=row[i][j-1]+(g[i][j]-'0');col[j][i]=col[j][i-1]+(g[i][j]-'0');b[i][j]=g[i][j]-'0';}}int res=n*m;for(int L=1;L<=m;L++){for(int R=L+3;R<=m;R++){int tmp=n*m;for(int D=5;D<=n;D++){if(b[D-1][L]==0) tmp++;if(b[D-1][R]==0) tmp++;tmp+=val(D-1,L+1,D-1,R-1);
int now=(R-L-1)-val(D-4,L+1,D-4,R-1)+3-val(D-3,L,D-1,L)+3-val(D-3,R,D-1,R)+val(D-3,L+1,D-1,R-1);tmp=min(tmp,now);res=min(res,tmp+R-L-1-val(D,L+1,D,R-1));}}}cout<<res<<"\n";
}signed main()
{cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int t=1;cin>>t;while(t--) solve();
}

E：

如果一个车车进来了

那么

工作区间有：[st,st+x-1],[st+x+y,st+x+y+x]....

休息区间有:[st+x,st+x+y-1],[st+x+y+x,st+x+y+x+y-1]....

所以在%（x+y）这个区间在休息区间那么就加一

差分，如果x+y>500，那么只需要400次就可以遍历完所以需要修改的点，

如果x+y<500,那么维护一个区间大小（x+y）去增加这个i%（x+y）点，

即维护一个 x+y【0,500】里面每个余数相同的点

分块即可

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10,mod=1e9+7;
int n,m,k;
int x[N],y[N];
int a[N];
int s[N];
int thre,ans;
int cnt[510][510];
void update(int st,int k,int v){int aa=x[k]+y[k];int *c=cnt[aa];int l=(st+x[k])%aa;int r=(st-1)%aa;if(l<=r){for(int i=l;i<=r;i++) c[i]+=v;}else{for(int i=0;i<=r;i++) c[i]+=v;for(int i=l;i<aa;i++) c[i]+=v;}
}
int query(int x){int res=0;for(int i=2;i<=thre;i++){res+=cnt[i][x%i];}return res;
}
void solve()
{cin>>n>>m;thre=sqrt(m);for(int i=1;i<=n;i++) cin>>x[i]>>y[i];for(int i=1;i<=m;i++){int op,k;cin>>op>>k;if(op==1){int aa=x[k]+y[k];if(aa>thre){for(int j=i+x[k];j<=m;j+=aa){a[j]++;if(j+y[k]<=m) a[j+y[k]]--;}}else update(i,k,1);s[k]=i;}else{int aa=x[k]+y[k];if(aa>thre){for(int j=s[k]+x[k];j<=m;j+=aa){a[j]--;if(j<=i-1) ans--;if(j+y[k]<=i-1) ans++;if(j+y[k]<=m) a[j+y[k]]++;}}else update(s[k],k,-1);}ans+=a[i];cout<<ans+query(i)<<"\n";}
}signed main()
{cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int t=1;//cin>>t;while(t--) solve();
}