时间戳

首页 > 技术文章 > Codeforces Round #775 (Div. 1, based on Moscow Open Olympiad in Informatics)

Codeforces Round #775 (Div. 1, based on Moscow Open Olympiad in Informatics)

ZCETHAN 2022-03-07 13:04 原文

A

出题人，你【】。

我们需要一个动态空间。你用一个 vector 来存这个矩阵，一开始的时候 resize 一下就好了。

然后考虑做题，曼哈顿距离想到把横竖分开来算距离。对于每个颜色开一个桶，然后对每个颜色的横纵坐标记录下来，从小到大遍历这个坐标，然后可以线性求出当前答案。

My Code 
#include<bits/stdc++.h>
#define int long long
#define inf (1<<30)
#define INF (1ll<<60)
#define pb push_back
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mkp make_pair
#define fi first
#define se second
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
using namespace std;
const int MAXN=1e5+10;
int cnt[MAXN];
vector<int> c[MAXN],x[MAXN],y[MAXN];
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int n,m;cin>>n>>m;
	rep(i,1,n){
		c[i].resize(m+5);
		rep(j,1,m) cin>>c[i][j];
	}
	int ans=0,tot=0;
	rep(i,1,n) rep(j,1,m){
		int cur;
		if(cnt[c[i][j]]) cur=cnt[c[i][j]];
		else cnt[c[i][j]]=++tot,cur=tot;
		x[cur].pb(i);y[cur].pb(j);
	}
	rep(i,1,tot){
		sort(x[i].begin(),x[i].end());
		sort(y[i].begin(),y[i].end());
		int num=0,lst=x[i][0],fns=0;
		for(int s:x[i]) ans+=(fns=num*(s-lst)+fns),lst=s,num++;
		num=0,lst=y[i][0],fns=0;
		for(int s:y[i]) ans+=(fns=num*(s-lst)+fns),lst=s,num++;
	}cout<<ans<<'\n';
	return 0;
}

B

考虑这样一件事就是：

\[\lfloor\dfrac{x}{y}\rfloor=z\Leftrightarrow x=yz+k(k<y) \]

于是考虑枚举一个不在 \(a\) 数组中的 \(z\)，看有没有 \(x,y\) 能够表示出它。这样的话，每个 \(z\)，我们只要枚举 \(\dfrac{c}{z}\) 个区间，然后用前缀和预处理来 \(O(1)\) 判断一个区间内有没有数。

My Code 
#include<bits/stdc++.h>
#define int long long
#define inf (1<<30)
#define INF (1ll<<60)
#define pb push_back
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mkp make_pair
#define fi first
#define se second
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
using namespace std;
const int MAXN=2e6+10;
int sum[MAXN];
void solve(){
	int n,c,a;cin>>n>>c;
	rep(i,1,n) cin>>a,sum[a]++;
	rep(i,1,c*2) sum[i]+=sum[i-1];
	bool ok=1;
	rep(z,1,c){
		if(sum[z]-sum[z-1]) continue;
		for(int y=1;y*z<=c;y++){
//			cerr<<sum[y]<<' '<<sum[y-1]<<' '<<sum[y*z+y-1]<<' '<<sum[y*z-1]<<' '<<y<<' '<<z<<'\n';
//			cerr<<y*z+y-1<<' '<<y*z-1<<'\n';
			if((sum[y]-sum[y-1])>0&&(sum[y*z+y-1]-sum[y*z-1])>0){
				ok=0;
			}
		}
	}
	rep(i,1,c*2) sum[i]=0;
	if(ok) cout<<"Yes\n";
	else cout<<"No\n";
}
signed main()
{
	ios::sync_with_stdio(0);
//	cin.tie(0);cout.tie(0);
	int T;for(cin>>T;T--;)
		solve();
	return 0;
}

C

CRT，先有【】，再造 pretest！

注意这题有极弱的 pretest！！！

考虑对于字典序比较的计数题的套路，考虑枚举哪一个位置 \(s_i<t_i\)，然后之前的位置都相等，后面的位置随便填。

然后考虑用一个树状数组维护一下枚举到 \(i\) 位置除去前面已经填了和 \(t_i\) 相等的数，每种数还剩下多少。然后对于枚举到位置 \(i\)，还剩下 \(n-i+1\) 个数。

然后我们强制 \(i\) 填小于 \(t_i\) 的，那么后面剩下的 \(n-i\) 的位置可以随便填。即，如果我们设当前每种数的数量是 \(cnt_i\)，所有数的数量和是 \(tot\)，比 \(t_i\) 小的数的数量和是 \(tmp\)，那么当前位置的答案就加上：

\[\begin{aligned}\sum_{c<t_i}\dfrac{tot!}{\prod cnt_i!}\times cnt_c &=\dfrac{tot!}{\prod cnt_i!}\times tmp\end{aligned} \]

然后你用一个变量维护一下 \(\prod cnt_i!\) 就行了。

注意最后要特判一下 \(s\) 可以是 \(t\) 的前缀，枚举的时候打个标记判断是不是前缀就行了。

My Code 
#include<bits/stdc++.h>
#define int long long
#define inf (1<<30)
#define INF (1ll<<60)
#define pb push_back
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mkp make_pair
#define fi first
#define se second
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
using namespace std;
const int MAXN=2e5+10;
const int MOD=998244353;
int ksm(int a,int p){
	int ret=1;while(p){
		if(p&1) ret=ret*a%MOD;
		a=a*a%MOD; p>>=1;
	}return ret;
}
int inv(int x){return ksm(x,MOD-2);}
struct Tree{int l,r,cnt;}tr[MAXN<<2];
int fac[MAXN];
#define ls i<<1
#define rs i<<1|1
void build(int i,int l,int r){
	tr[i].l=l;tr[i].r=r;tr[i].cnt=0;
	if(l==r) return;int mid=l+r>>1;
	build(ls,l,mid);build(rs,mid+1,r);
}
void pushup(int i){
	tr[i].cnt=tr[ls].cnt+tr[rs].cnt;
}
void upd(int i,int x,int v){
	if(tr[i].l==tr[i].r){tr[i].cnt+=v;return;}
	int mid=tr[i].l+tr[i].r>>1;
	if(x<=mid) upd(ls,x,v);else upd(rs,x,v);
	pushup(i);
}
int qcnt(int i,int l,int r){
	if(l>r) return 0;
	if(tr[i].l==l&&tr[i].r==r) return tr[i].cnt;
	int mid=tr[i].l+tr[i].r>>1;
	if(r<=mid) return qcnt(ls,l,r);
	else if(l>mid) return qcnt(rs,l,r);
	else return qcnt(ls,l,mid)+qcnt(rs,mid+1,r);
}
int s[MAXN],t[MAXN];
int cs[MAXN];
signed main()
{
	ios::sync_with_stdio(0);
//	cin.tie(0);cout.tie(0);
	fac[0]=1;rep(i,1,MAXN-10) fac[i]=fac[i-1]*i%MOD;
	int n,m;cin>>n>>m;build(1,1,MAXN-10);
	rep(i,1,n) cin>>s[i],cs[s[i]]++,upd(1,s[i],1);
	rep(i,1,m) cin>>t[i];
	int all=1;
	rep(i,1,MAXN-10) all=all*fac[cs[i]]%MOD;
	int ans=0,ok=1;
	rep(i,1,min(n,m)){
		int tmp=qcnt(1,1,t[i]-1);
//		cerr<<tmp<<'\n';
		if(tmp){
			int rem=n-i;
			ans+=fac[rem]*inv(all)%MOD*tmp%MOD;
			ans%=MOD;
		}
		if(!cs[t[i]]){ok=0;break;}
		else all=all*inv(cs[t[i]])%MOD,cs[t[i]]--,upd(1,t[i],-1);
//		rep(j,1,3) cerr<<qcnt(1,j,j)<<' ';cerr<<'\n';
	}
	if(n>=m) ok=0;
	cout<<(ans+ok)%MOD<<'\n';
	return 0;
}/*
3 6
10 7 8
8 7 6 10 5 4
*/

推荐阅读