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();
}
)
