Educational Codeforces Round 113 (Rated for Div. 2)
经典卡\(C\)秒\(D\),可惜了
怪自己特判写错了吧,对式子找了半天问题结果根本不是式子的问题
找到任意一个位置\(i\),满足\(s[i]\neq s[i+1]\),那么直接输出\([i,i+1]\)这个区间作为答案即可
// URL: https://codeforces.com/contest/1569/problem/0 // Problem: A. Balanced Substring // Contest: Codeforces - Educational Codeforces Round 113 (Rated for Div. 2) // Time Limit: 2000 ms // Memory Limit: 256 MB // Create Time: 2021-09-08 22:35:25 // Author: StelaYuri // // Powered by CP Editor (https://cpeditor.org) #include<bits/stdc++.h> #define closeSync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0) #define multiCase int T;cin>>T;for(int t=1;t<=T;t++) #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i<(b);i++) #define per(i,a,b) for(int i=(a);i>=(b);i--) #define perr(i,a,b) for(int i=(a);i>(b);i--) #define all(a) (a).begin(),(a).end() #define mst(a,b) memset(a,b,sizeof(a)) #define pb push_back #define eb emplace_back #define fi first #define se second using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> P; const int INF=0x3f3f3f3f; const ll LINF=0x3f3f3f3f3f3f3f3f; const double eps=1e-12; const double PI=acos(-1.0); const ll mod=998244353; const int dx[8]={0,1,0,-1,1,1,-1,-1},dy[8]={1,0,-1,0,1,-1,1,-1}; void debug(){cerr<<'\n';}template<typename T,typename... Args>void debug(T x,Args... args){cerr<<"[ "<<x<< " ] , ";debug(args...);} mt19937 mt19937random(std::chrono::system_clock::now().time_since_epoch().count()); ll getRandom(ll l,ll r){return uniform_int_distribution<ll>(l,r)(mt19937random);} ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);} ll qmul(ll a,ll b){ll r=0;while(b){if(b&1)r=(r+a)%mod;b>>=1;a=(a+a)%mod;}return r;} ll qpow(ll a,ll n){ll r=1;while(n){if(n&1)r=(r*a)%mod;n>>=1;a=(a*a)%mod;}return r;} ll qpow(ll a,ll n,ll p){ll r=1;while(n){if(n&1)r=(r*a)%p;n>>=1;a=(a*a)%p;}return r;} void solve() { int n; string s; cin>>n>>s; repp(i,1,n) { if(s[i]!=s[i-1]) { cout<<i<<' '<<i+1<<'\n'; return; } } cout<<"-1 -1\n"; } int main() { closeSync; multiCase { solve(); } return 0; }
特殊的,如果所有人都只是不想输(全\(1\)),则输出全部平局即可
只有当想赢至少一局的人数(种类\(2\))大于等于\(3\)人时,我们可以让这些人凑成一个有向环,\(a\rightarrow b\)表示\(a\)赢\(b\),这样环内的所有人(种类\(2\)的所有人)就全是只赢\(1\)局输\(1\)局,但也满足条件
对于环外的任意边则全部视作平局即可
// URL: https://codeforces.com/contest/1569/problem/B // Problem: B. Chess Tournament // Contest: Codeforces - Educational Codeforces Round 113 (Rated for Div. 2) // Time Limit: 2000 ms // Memory Limit: 256 MB // Create Time: 2021-09-08 22:39:09 // Author: StelaYuri // // Powered by CP Editor (https://cpeditor.org) #include<bits/stdc++.h> #define closeSync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0) #define multiCase int T;cin>>T;for(int t=1;t<=T;t++) #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i<(b);i++) #define per(i,a,b) for(int i=(a);i>=(b);i--) #define perr(i,a,b) for(int i=(a);i>(b);i--) #define all(a) (a).begin(),(a).end() #define mst(a,b) memset(a,b,sizeof(a)) #define pb push_back #define eb emplace_back #define fi first #define se second using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> P; const int INF=0x3f3f3f3f; const ll LINF=0x3f3f3f3f3f3f3f3f; const double eps=1e-12; const double PI=acos(-1.0); const ll mod=998244353; const int dx[8]={0,1,0,-1,1,1,-1,-1},dy[8]={1,0,-1,0,1,-1,1,-1}; void debug(){cerr<<'\n';}template<typename T,typename... Args>void debug(T x,Args... args){cerr<<"[ "<<x<< " ] , ";debug(args...);} mt19937 mt19937random(std::chrono::system_clock::now().time_since_epoch().count()); ll getRandom(ll l,ll r){return uniform_int_distribution<ll>(l,r)(mt19937random);} ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);} ll qmul(ll a,ll b){ll r=0;while(b){if(b&1)r=(r+a)%mod;b>>=1;a=(a+a)%mod;}return r;} ll qpow(ll a,ll n){ll r=1;while(n){if(n&1)r=(r*a)%mod;n>>=1;a=(a*a)%mod;}return r;} ll qpow(ll a,ll n,ll p){ll r=1;while(n){if(n&1)r=(r*a)%p;n>>=1;a=(a*a)%p;}return r;} char mp[55][55]; void solve() { int n; string s; cin>>n>>s; mst(mp,'.'); rep(i,1,n) mp[i][i]='X'; vector<int> vec; repp(i,0,n) if(s[i]=='2') vec.pb(i+1); if(vec.size()==1||vec.size()==2) { cout<<"NO\n"; return; } rep(i,1,n) rep(j,1,n) { if(i==j)continue; if(s[i-1]=='1'||s[j-1]=='1') mp[i][j]='='; } if(vec.size()) //环 { repp(i,1,vec.size()) // i-1 -> i { mp[vec[i-1]][vec[i]]='+'; mp[vec[i]][vec[i-1]]='-'; } mp[vec[vec.size()-1]][vec[0]]='+'; mp[vec[0]][vec[vec.size()-1]]='-'; } rep(i,1,n) rep(j,1,n) if(mp[i][j]=='.') mp[i][j]='='; cout<<"YES\n"; rep(i,1,n) { rep(j,1,n) cout<<mp[i][j]; cout<<'\n'; } } int main() { closeSync; multiCase { solve(); } return 0; }
记最大值为\(a\),次大值为\(b\),最大值的数量为\(cnt1\),次大值的数量为\(cnt2\)
如果最大值的数量\(cnt1\ge 2\),那么任意排列最终都会剩下拥有最大值的这些人在循环讲话,并且同一个人不会连续说两次,故方案数为\(A_n^n\)
否则,拥有最大值\(a\)的只有\(1\)人,最后一次讲话肯定是这个人讲,于是需要保证倒数第二次讲话不是他讲
只有在次大值\(b=a-1\)时,将任意一个拥有次大值的人放在拥有最大值的人后面,才能保证条件满足;否则方案数为\(0\)
因此先将所有拥有次大值的人进行全排列,方案数为\(A_{cnt2}^{cnt2}\)
拥有最大值的人借助隔板法,当隔板插入,发现不能插在最后一个位置,其余\(cnt2\)个位置均能插入,故方案数为\(cnt2\)
剩余的\(n-(cnt2+cnt1)\)个人同样根据隔板法全部插入即可,方案数\(A_n^{n-(cnt2+cnt1)}\)
故最终答案为\(A_{cnt2}^{cnt2}\cdot cnt2\cdot A_n^{n-(cnt2+cnt1)}\)
// URL: https://codeforces.com/contest/1569/problem/C // Problem: C. Jury Meeting // Contest: Codeforces - Educational Codeforces Round 113 (Rated for Div. 2) // Time Limit: 2000 ms // Memory Limit: 256 MB // Create Time: 2021-09-08 22:52:38 // Author: StelaYuri // // Powered by CP Editor (https://cpeditor.org) #include<bits/stdc++.h> #define closeSync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0) #define multiCase int T;cin>>T;for(int t=1;t<=T;t++) #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i<(b);i++) #define per(i,a,b) for(int i=(a);i>=(b);i--) #define perr(i,a,b) for(int i=(a);i>(b);i--) #define all(a) (a).begin(),(a).end() #define mst(a,b) memset(a,b,sizeof(a)) #define pb push_back #define eb emplace_back #define fi first #define se second using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> P; const int INF=0x3f3f3f3f; const ll LINF=0x3f3f3f3f3f3f3f3f; const double eps=1e-12; const double PI=acos(-1.0); const ll mod=998244353; const int dx[8]={0,1,0,-1,1,1,-1,-1},dy[8]={1,0,-1,0,1,-1,1,-1}; void debug(){cerr<<'\n';}template<typename T,typename... Args>void debug(T x,Args... args){cerr<<"[ "<<x<< " ] , ";debug(args...);} mt19937 mt19937random(std::chrono::system_clock::now().time_since_epoch().count()); ll getRandom(ll l,ll r){return uniform_int_distribution<ll>(l,r)(mt19937random);} ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);} ll qmul(ll a,ll b){ll r=0;while(b){if(b&1)r=(r+a)%mod;b>>=1;a=(a+a)%mod;}return r;} ll qpow(ll a,ll n){ll r=1;while(n){if(n&1)r=(r*a)%mod;n>>=1;a=(a*a)%mod;}return r;} ll qpow(ll a,ll n,ll p){ll r=1;while(n){if(n&1)r=(r*a)%p;n>>=1;a=(a*a)%p;}return r;} const int N=4e5; ll fac[N+1],inv[N+1]; void init() { fac[0]=1; for(int i=1;i<=N;i++) fac[i]=fac[i-1]*i%mod; inv[N]=qpow(fac[N],mod-2); for(int i=N-1;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod; } ll getC(ll m,ll n) { return fac[m]*inv[m-n]%mod*inv[n]%mod; } ll getA(ll m,ll n) { return fac[m]*inv[m-n]%mod; } int n,a[200050]; void solve() { cin>>n; rep(i,1,n) cin>>a[i]; sort(a+1,a+n+1); int p=n; while(p>1&&a[p]==a[p-1]) p--; int cnt1=n-p+1; //最大值的数量 if(cnt1>1) { cout<<getA(n,n)<<'\n'; return; } if(a[p-1]+1<a[p]) { cout<<0<<'\n'; return; } p--; while(p>1&&a[p]==a[p-1]) p--; int cnt2=n-cnt1-p+1; //次大值的数量 cout<<getA(cnt2,cnt2)*cnt2%mod*getA(n,n-(cnt2+1))%mod<<'\n'; } int main() { closeSync; init(); multiCase { solve(); } return 0; }
根据题意,所有点都肯定落在某条横纵线上或是横纵线交点上
因此如果某个点恰好落在给定的横纵线的某个交点上,那么这个点与其余任意点之间的最短距离一定等于其曼哈顿距离,对答案无贡献
否则,假如某个点\(P\)落在某条横线上,并夹在第\(i\)条和第\(i+1\)条纵线之间
明显可以得出,所有夹在第\(i\)条和第\(i+1\)条纵线之间并且与点\(P\)不是同一条横线上的点都可以计入答案
于是我们借助\(4\)个map容器,两个map记录第\(i\)条与第\(i+1\)条横线之间、第\(i\)条与第\(i+1\)条纵线之间分别有多少点,另外两个map记录在第\(i\)条与第\(i+1\)条横线之间并且在第\(j\)条纵线上、在第\(i\)条与第\(i+1\)条纵线之间并且在第\(j\)条横线上的点分别有多少
那么对于点\(P\)夹在哪两条线之间,通过二分即可求出
统计答案时拿对应的两个容器相减即为答案,然后更新对应的两个容器即可
// URL: https://codeforces.com/contest/1569/problem/D // Problem: D. Inconvenient Pairs // Contest: Codeforces - Educational Codeforces Round 113 (Rated for Div. 2) // Time Limit: 2000 ms // Memory Limit: 256 MB // Create Time: 2021-09-08 23:52:41 // Author: StelaYuri // // Powered by CP Editor (https://cpeditor.org) #include<bits/stdc++.h> #define closeSync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0) #define multiCase int T;cin>>T;for(int t=1;t<=T;t++) #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i<(b);i++) #define per(i,a,b) for(int i=(a);i>=(b);i--) #define perr(i,a,b) for(int i=(a);i>(b);i--) #define all(a) (a).begin(),(a).end() #define mst(a,b) memset(a,b,sizeof(a)) #define pb push_back #define eb emplace_back #define fi first #define se second using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> P; const int INF=0x3f3f3f3f; const ll LINF=0x3f3f3f3f3f3f3f3f; const double eps=1e-12; const double PI=acos(-1.0); const ll mod=998244353; const int dx[8]={0,1,0,-1,1,1,-1,-1},dy[8]={1,0,-1,0,1,-1,1,-1}; void debug(){cerr<<'\n';}template<typename T,typename... Args>void debug(T x,Args... args){cerr<<"[ "<<x<< " ] , ";debug(args...);} mt19937 mt19937random(std::chrono::system_clock::now().time_since_epoch().count()); ll getRandom(ll l,ll r){return uniform_int_distribution<ll>(l,r)(mt19937random);} ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);} ll qmul(ll a,ll b){ll r=0;while(b){if(b&1)r=(r+a)%mod;b>>=1;a=(a+a)%mod;}return r;} ll qpow(ll a,ll n){ll r=1;while(n){if(n&1)r=(r*a)%mod;n>>=1;a=(a*a)%mod;}return r;} ll qpow(ll a,ll n,ll p){ll r=1;while(n){if(n&1)r=(r*a)%p;n>>=1;a=(a*a)%p;}return r;} int x[200050],y[200050]; void solve() { int n,m,k; cin>>n>>m>>k; rep(i,1,n) cin>>x[i]; rep(i,1,m) cin>>y[i]; x[n+1]=INF; y[m+1]=INF; //二分边界 map<int,int> mpx,mpy; map<P,int> mpxy,mpyx; ll ans=0; rep(i,1,k) { int xx,yy; cin>>xx>>yy; int px=lower_bound(x+1,x+n+1,xx)-x; int py=lower_bound(y+1,y+m+1,yy)-y; if(x[px]==xx&&y[py]==yy) continue; //线的交点,无贡献 if(x[px]==xx) //落在某横线上 { ans+=mpy[py]-mpxy[P(px,py)]; // py-1 ~ py 两线之间所有点,减去两线之间且在px横线上的点的数量,即为答案 mpy[py]++; mpxy[P(px,py)]++; } else //落在某纵线上 { ans+=mpx[px]-mpyx[P(py,px)]; mpx[px]++; mpyx[P(py,px)]++; } } cout<<ans<<'\n'; } int main() { closeSync; multiCase { solve(); } return 0; }
https://blog.csdn.net/qq_36394234/article/details/120192261