ABC340

A

link

模拟。

B

link

模拟指针。

C

link

记忆化搜索。

时间复杂度证明可以从一个奇数分多遍以后只会有两种数这一角度入手。

D

link

由于每次只能选择一种，于是可以将选择变成连边，进行最短路。

E

link

线段树入门。取余操作本身就是一个环。

注意题目中的操作是从 \(0\sim n-1\)。

#include<bits/stdc++.h>
#define int long long
#define ok printf("--------------\n")

template<typename T>
void read(T &x){
	 int f=1;
	 char c=getchar();
	 x=0;
	 while(c<'0'||c>'9'){
		 if(c=='-') f=-1;
		 c=getchar();
	 }
	 while(c>='0'&&c<='9') x=x*10+(int)(c-'0'),c=getchar();
	 x*=f;
}

template<typename T,typename I>
void chkmin(T &a,I b){
	 a=std::min(a,b);
}

template<typename T,typename I>
void chkmax(T &a,T b){
	a=std::max(a,b);
}

const int inf=1e18+10,MOD1=998244353,MOD2=1e9+7;

const int maxn=2e5+10;

int a[maxn],b[maxn];

struct node{
	int l,r,sum,lz,ls,rs;
}s[maxn<<1];

int tot=0;

void push_up(int p){
	s[p].sum=s[s[p].ls].sum+s[s[p].rs].sum;
	return ;
}

int build(int l,int r){
	int p=++tot;
	s[p].l=l,s[p].r=r;
	if(l==r){
		s[p].sum=a[l];
		return p;
	}
	int mid=(l+r)>>1;
	s[p].ls=build(l,mid);
	s[p].rs=build(mid+1,r);
	push_up(p);
	return p; 
}

void push_down(int p){
	if(s[p].lz){
		int ls=s[p].ls,rs=s[p].rs,lz=s[p].lz;
		s[ls].sum+=s[p].lz*(s[ls].r-s[ls].l+1);
		s[rs].sum+=s[p].lz*(s[rs].r-s[rs].l+1);
		s[ls].lz+=lz;
		s[rs].lz+=lz;
		s[p].lz=0;
	}
	return ;
}

void update(int p,int L,int R,int k){
	int l=s[p].l,r=s[p].r;
	if(l>=L&&r<=R){
		s[p].sum+=(s[p].r-s[p].l+1)*k;
		s[p].lz+=k;
		return ;
	}
	push_down(p);
	int mid=(l+r)>>1;
	if(mid>=L) update(s[p].ls,L,R,k);
	if(R>mid) update(s[p].rs,L,R,k);
	push_up(p);
	return ;
}

int query(int p,int L,int R){
	int l=s[p].l,r=s[p].r;
	if(L<=l&&r<=R){
		return s[p].sum;
	}
	push_down(p);
	int mid=(l+r)>>1,ret=0;
	if(mid>=L) ret+=query(s[p].ls,L,R);
	if(R>mid) ret+=query(s[p].rs,L,R);
	push_up(p);
	return ret;
}

signed main(){
	int n,m;
	std::cin>>n>>m;
	for(int i=0;i<n;i++) std::cin>>a[i];
	build(0,maxn);
	for(int i=1;i<=m;i++){
		std::cin>>b[i];
		int y=query(1,b[i],b[i]);
		update(1,b[i],b[i],-y);
		if(b[i]+y<=n-1) {
			update(1,b[i]+1,b[i]+y,1);
			continue;
		}
		if(1) {
			if(b[i]!=n-1)update(1,b[i]+1,n-1,1);
			y-=n-1-b[i];
			int x=y/n;
			update(1,0,n-1,x);
			y-=x*n;
			if(y==0) continue;
			update(1,0,y-1,1);
		}
	}	
	for(int i=0;i<n;i++) printf("%lld ",query(1,i,i));
	return 0;
}
/*
-读入字符一定检查回车
- 能不能搜索？
-函数要有返回值！
-想好了再写！
*/

F

link

G

[link][(https://atcoder.jp/contests/abc340/tasks/abc340_g)