Codeforces Round #751 (Div. 1)


CF1601A Array Elimination

洛谷传送门
CF1601A


分析

可以发现每一位可以拆开,也就是每一位的一的个数一定是 \(k\) 的倍数,

直接求 \(\gcd\) 出来,它的约数就是所有 \(k\) 的取值(\(\gcd=0\)就是 \(1\sim n\)


代码

#include 
#include 
#include 
using namespace std;
const int N=200011; int n,GCD,a[N];
int iut(){
	int ans=0; char c=getchar();
	while (!isdigit(c)) c=getchar();
	while (isdigit(c)) ans=ans*10+c-48,c=getchar();
	return ans; 
}
void print(int ans){
	if (ans>9) print(ans/10);
	putchar(ans%10+48);
}
int gcd(int x,int y){return y?gcd(y,x%y):x;}
int main(){
	for (int T=iut();T;--T){
		n=iut(),GCD=0;
		for (int i=1;i<=n;++i) a[i]=iut();
		for (int i=0;i<30;++i){
			int C=0;
			for (int j=1;j<=n;++j)
			    if ((a[j]>>i)&1) ++C;
			GCD=gcd(GCD,C);
		}
		for (int i=1;i<=n;++i)
		    if (gcd(GCD,i)==i) printf("%d ",i);
		putchar(10);
	}
	return 0;
}

CF1601B Frog Traveler

洛谷传送门
CF1601B


代码(线段树优化建图跑Dijkstra)

//直接O(n)贪心更好写
#include 
#include 
#include 
#include 
using namespace std;
const int N=1000011; pairheap[N<<1];
struct node{int y,w,next;}e[N*6];
int pre[N],p[N],Cnt,et,n,as[N],cnt,dis[N],b[N],ls[N],rs[N],a[N],root;
int iut(){
	int ans=0; char c=getchar();
	while (!isdigit(c)) c=getchar();
	while (isdigit(c)) ans=ans*10+c-48,c=getchar();
	return ans; 
}
void print(int x){
	if (x==n) return; print(pre[x]);
	if (x<=n) printf("%d ",p[x]);
}
void add(int x,int y,int w){
	e[++et]=(node){y,w,as[x]},as[x]=et;
}
void Push(pairw){
	heap[++Cnt]=w;
	int x=Cnt;
	while (x>1){
		if (heap[x]>1])
		    swap(heap[x],heap[x>>1]),x>>=1;
		else return; 
	}
}
void Pop(){
	heap[1]=heap[Cnt--];
	int x=1;
	while ((x<<1)<=Cnt){
		int y=x<<1;
		if (yheap[y]) swap(heap[x],heap[y]),x=y;
		    else return;
	}
}
void Dijkstra(int S){
	heap[++Cnt]=make_pair(0,S);
	for (int i=0;i<=cnt;++i) dis[i]=0x3f3f3f3f; dis[S]=0;
	while (Cnt){
		int t=heap[1].first,x=heap[1].second;
		Pop(); if (t!=dis[x]) continue;
		for (int i=as[x];~i;i=e[i].next)
		if (dis[e[i].y]>dis[x]+(e[i].w>0)){
			dis[e[i].y]=dis[x]+(e[i].w>0),pre[e[i].y]=x,p[e[i].y]=e[i].w;
			Push(make_pair(dis[e[i].y],e[i].y));
		}
	}
}
void build(int &rt,int l,int r){
	rt=++cnt;
	if (l==r){
		add(rt,b[l],l);
		return;
	}
	int mid=(l+r)>>1;
	build(ls[rt],l,mid);
	build(rs[rt],mid+1,r);
	add(rt,ls[rt],0),add(rt,rs[rt],0);
}
void update(int rt,int l,int r,int x,int y,int z){
	if (l==x&&r==y){
		add(z,rt,0);
		return;
	}
	int mid=(l+r)>>1;
	if (y<=mid) update(ls[rt],l,mid,x,y,z);
	else if (x>mid) update(rs[rt],mid+1,r,x,y,z);
	    else update(ls[rt],l,mid,x,mid,z),update(rs[rt],mid+1,r,mid+1,y,z);
}
int main(){
	n=iut(),cnt=n,et=0,memset(as,-1,sizeof(as));
	for (int i=1;i<=n;++i) a[i]=iut();
	for (int i=1;i<=n;++i) b[i]=i+iut();
	build(root,0,n);
	for (int i=1;i<=n;++i) update(root,0,n,i-a[i],i,i);
	Dijkstra(n);
	if (dis[0]==0x3f3f3f3f) printf("-1");
	    else printf("%d\n",dis[0]+1),print(0);
	return 0;
}

CF1601C Optimal Insertion

洛谷传送门
CF1601C


分析

首先 \(b\) 中元素在 \(c\) 中一定是从小到大排列的
所以升序依次填入每个数,用线段树维护 \(a\) 每个位置能提供的逆序对,那肯定越小越好


代码

#include 
#include 
#include 
using namespace std;
const int N=1000011; long long ans;
int A[N],a[N],b[N],k,n,m,c[N],lazy[N<<2],rk[N];
struct rec{
	int p,w;
}w[N<<2];
int iut(){
	int ans=0; char c=getchar();
	while (!isdigit(c)) c=getchar();
	while (isdigit(c)) ans=ans*10+c-48,c=getchar();
	return ans; 
}
bool cmp(int x,int y){return a[x]y.w?y:x;}
void Update(int x,int y){
    for (;x<=k;x+=-x&x) c[x]+=y;
}
int Query(int x){
	int ans=0;
	for (;x;x-=-x&x) ans+=c[x];
	return ans;
}
void ptag(int k,int z){w[k].w+=z,lazy[k]+=z;}
void pdown(int k){
	if (lazy[k]){
		ptag(k<<1,lazy[k]);
		ptag(k<<1|1,lazy[k]);
		lazy[k]=0;
	}
}
void build(int k,int l,int r){
	lazy[k]=0;
	if (l==r){
		w[k]=(rec){l,0};
		return;
	}
	int mid=(l+r)>>1;
	build(k<<1,l,mid);
	build(k<<1|1,mid+1,r);
    w[k]=pup(w[k<<1],w[k<<1|1]);
}
void update(int k,int l,int r,int x,int y,int z){
	if (l==x&&r==y){
		ptag(k,z);
		return;
	}
	int mid=(l+r)>>1; pdown(k);
	if (y<=mid) update(k<<1,l,mid,x,y,z);
	else if (x>mid) update(k<<1|1,mid+1,r,x,y,z);
	    else update(k<<1,l,mid,x,mid,z),update(k<<1|1,mid+1,r,mid+1,y,z);
	w[k]=pup(w[k<<1],w[k<<1|1]); 
}
rec query(int k,int l,int r,int x,int y){
	if (l==x&&r==y) return w[k];
	int mid=(l+r)>>1; pdown(k);
	if (y<=mid) return query(k<<1,l,mid,x,y);
	else if (x>mid) return query(k<<1|1,mid+1,r,x,y);
	    else return pup(query(k<<1,l,mid,x,mid),query(k<<1|1,mid+1,r,mid+1,y));
}
int main(){
	for (int T=iut();T;--T){
		n=iut(),m=iut(),ans=0;
		for (int i=1;i<=n;++i) rk[i]=i,A[i]=a[i]=iut();
		for (int i=1;i<=m;++i) b[i]=iut();
		sort(b+1,b+1+m),sort(rk+1,rk+1+n,cmp);
		build(1,0,n+1);
		for (int i=1;i<=n;++i) update(1,0,n+1,i,n+1,1);
		for (int l=1,r,j=1,last=0;l<=m;l=r+1){
			for (r=l;r<=m&&b[r]==b[l];++r); --r;
			for (;j<=n&&a[rk[j]]

CF1601D Difficult Mountain

洛谷传送门
CF1601D


分析

先按照 \(\max\{s_i,a_i\}\) 升序排序,再按照 \(s_i\) 升序排序,这样贪心可以证明一定是最优的


代码

#include 
#include 
#include 
using namespace std;
const int N=500011;
struct rec{int x,y,mx;}a[N];
int n,A,ans;
int iut(){
	int ans=0,f=1; char c=getchar();
	while (!isdigit(c)) f=(c=='-')?-f:f,c=getchar();
	while (isdigit(c)) ans=ans*10+c-48,c=getchar();
	return ans*f; 
}
int max(int a,int b){return a>b?a:b;}
bool cmp(rec x,rec y){
    if (x.mx!=y.mx) return x.mx=A){
		A=max(A,a[i].y);
		++ans;
	}
	return !printf("%d",ans);
}

CF1601E Phys Ed Online

洛谷传送门
CF1601E


分析

可以发现答案与 \([l,l+ki]\) 的最小值有关,这个可以用ST表预处理出来。
那么答案其实与 \(l\bmod k\) 的值有关,考虑分成 \(k\) 种情况处理。
取出来一定是一段单调递减的位置,从右到左用一个单调递增的单调栈维护。
如果将 \([l,r]\) 的最小值位置 \(mn\) 取出来,那么就是 \([l,mn]\) 是单调栈的答案,\((mn,r]\)\(a[mn]\) 的答案。
直接取出相应的位置计算答案即可。


代码

#include 
#include 
#include 
#include 
using namespace std;
const int N=300011; typedef long long lll;
struct rec{int l,r,rk;}; vectorK[N]; lll ans[N],dp[N];
int n,Q,k,f[N][19],lg[N],two[19],a[N],b[N],st[N],Top;
int iut(){
	int ans=0; char c=getchar();
	while (!isdigit(c)) c=getchar();
	while (isdigit(c)) ans=ans*10+c-48,c=getchar();
	return ans; 
}
void print(lll ans){
	if (ans>9) print(ans/10);
	putchar(ans%10+48);
}
int Get(int x,int y){return a[x]>a[y]?y:x;}
int query(int l,int r){
	int z=lg[r-l+1];
	return Get(f[l][z],f[r-two[z]+1][z]); 
}
int main(){
	n=iut(),Q=iut(),k=iut(),lg[0]=-1,two[0]=1;
	for (int i=1;i<=n;++i) a[i]=iut(),lg[i]=lg[i>>1]+1,f[i][0]=i;
	for (int i=1;i<=lg[n];++i) two[i]=two[i-1]<<1;
	for (int j=1;j<=lg[n];++j)
	for (int i=1;i+two[j]-1<=n;++i)
	    f[i][j]=Get(f[i][j-1],f[i+two[j-1]][j-1]);
	for (int i=1;i<=Q;++i){
		int l=iut(),r=iut();
		if (l+k>r) ans[i]=a[l];
		    else K[l%k].push_back((rec){l,r,i});
	}
	for (int i=0;in)?n:(j+k));
		}
		for (int j=n/k;~j;--j){
			while (Top&&a[b[st[Top]]]>=a[b[j]]) --Top;
			dp[j]=dp[st[Top]]+1ll*(st[Top]-j)*a[b[j]];
			st[++Top]=j;
		}
		int len=K[i].size();
		for (int j=0;j

CF1601F Two Sorts

洛谷传送门
CF1601F


分析

可以发现字典序的第几个很难求,考虑将排列转换成第几个字典序
考虑折半搜索,如果将 \(n\) 的后六位去除,前若干位就是一个关键字,

只要小于 \(\left\lfloor\frac{n}{10^6}\right\rfloor\) 的非零数都能当作关键字

这些关键字后面可以放任意不超过六位的数字,这个预处理出来就可以了。

如果不作为关键字直接暴力就可以了,注意取模很阴间,所以要二分多少个数需要减去模数。


代码

#include 
#include 
#include 
using namespace std;
const int mod=998244353,MOD=1000000007;
typedef long long lll; vectorK[7];
lll s[7],siz[7],n,kth; int ans,ten[8],Kth;
void dfs1(int dep,int now){
	if (dep==7) return;
	int t=(Kth-now+mod)%mod;
	K[dep].push_back(t),s[dep]+=t,++Kth;
	for (int i=0;i<10;++i)
	    dfs1(dep+1,now*10+i);
}
void dfs2(int dep,lll now){
	if (now>n) return;
	if ((now+1)*ten[6]-1<=n&&now*ten[7]>n){
		for (int i=0;i<7;++i){
			int t=((kth-now*ten[i])%mod+mod)%mod;
			int pos=lower_bound(K[i].begin(),K[i].end(),mod-t)-K[i].begin();
			ans=(ans+s[i]+t*siz[i]-mod*(siz[i]-pos))%MOD;
		}
		kth+=Kth;
		return;
	}
	int t=((kth-now)%mod+mod)%mod;
	ans=(ans+t)%MOD,++kth;
	for (int i=!dep;i<10;++i)
	    dfs2(dep+1,now*10+i);
}
int main(){
    ios::sync_with_stdio(0);
    cin>>n,ten[0]=1,dfs1(0,0);
    for (int i=1;i<=7;++i) ten[i]=ten[i-1]*10;
	for (int i=0;i<7;++i) sort(K[i].begin(),K[i].end()),siz[i]=K[i].size();
	dfs2(0,0);
	cout<

相关