CF558E A Simple Task

开一颗珂朵莉树,对于每个新的查询,先把l-1,l之间和r,r+1之间split开,然后对于剩下的部份用桶排序并暴力合并即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<set> 
using namespace std;
const int N=100005;

struct Data{
	int l;int r;char id;
	bool operator<(const Data &B)const{
		return r<B.r;
	}
};
int n,q;
char ch[N];
std::set<Data> st;
inline void split(std::set<Data>::iterator it, int X){
	int l=it->l,r=it->r;char id=it->id;
	if(X<l||X>=r){
		return;
	}
	st.erase(it);st.insert((Data){l,X,id});st.insert((Data){X+1,r,id});
}
int bckt[30];
inline void clr(){
	for(int i=0;i<26;++i){
		bckt[i]=0;
	}
}
inline void uni(int l,int r,int op){
	std::set<Data>::iterator itx,ity;
	itx=st.lower_bound((Data){0,l-1,0});
	split(itx,l-1);
	ity=st.lower_bound((Data){0,r,0});
	split(ity,r);
	itx=st.lower_bound((Data){0,l,0});
	ity=st.lower_bound((Data){0,r,0});
	++ity;
	for(std::set<Data>::iterator it=itx;it!=ity;++it){
		bckt[(it->id)-'a']+=(it->r)-(it->l)+1;
	}
	st.erase(itx,ity);
	int loc,nl=l;
	for(int i=0;i<26;++i){
		loc=op?i:(26-i-1);
		if(bckt[loc]<=0){
			continue;
		}
		st.insert((Data){nl,nl+bckt[loc]-1,'a'+loc});
		nl+=bckt[loc];
	}
	clr();
}
inline void prnt(){
	for(std::set<Data>::iterator it=st.begin();it!=st.end();++it){
		for(int j=it->l;j<=it->r;++j){
			putchar(it->id);
		}
	}
	puts("");
}
inline void init(){
	scanf("%d%d",&n,&q);
	std::cin>>ch+1;
	for(int i=1;i<=n;++i){
		st.insert((Data){i,i,ch[i]});
	}
	int l,r,op;
	for(int i=1;i<=q;++i){
		scanf("%d%d%d",&l,&r,&op);
		uni(l,r,op);
//		prnt();
	}
	prnt();
}

int main(){
	init();
	return 0;
}

CF527C Glass Carving

开四个set,分别存切割的刀以及每个区间段,然后每次各自从行和列取最长的区间段,乘一起即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<set>
using namespace std;
typedef long long ll;


ll w,h;
std::set<ll> st[2];
std::multiset<ll> sm[2];
std::multiset<ll>::iterator it;

inline void init(){
	char ch[5];ll x,l,r;int id;
	std::cin>>ch+1;scanf("%lld",&x);
	id=(ch[1]=='H');
	set<ll> &nst=st[id];
	multiset<ll> &nsm=sm[id];
	nst.insert(x);
	it=nst.find(x);
	--it;l=*it;
	++it,++it;r=*it;
	it=nsm.find(r-l);
	nsm.erase(it);nsm.insert(r-x);nsm.insert(x-l);
	it=sm[0].end();--it;l=*it;
	it=sm[1].end();--it;r=*it;
	printf("%lld\n",l*r);
}

int main(){
	scanf("%lld%lld",&w,&h);
	int T;
	scanf("%d",&T);
	st[0].insert(0),st[0].insert(w);
	st[1].insert(0),st[1].insert(h);
	sm[0].insert(w),sm[1].insert(h);
	while(T--){
		init();
	}
	return 0;
}

CF102268C

贪心构造即可。
具体来说,如果把a依次标成-n…-1,那么只会有三种数:0(贡献是下标-1),n(贡献是0)以及x(贡献是下标比x小且<-x)的数。
贪心地构造,可以保证x只出现一次。暴力枚举检验即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int N=300005;
int n;ll m;
int a[N],b[N],p[N],q[N];
int bckt[N];
void init(){
	scanf("%d%lld",&n,&m);
	for(int i=0;i<=n;++i){
		bckt[i]=0;
	}
	for(int i=1;i<=n;++i){
		scanf("%d",&p[i]);
		a[p[i]]=-n+i-1;
	}
	for(int i=1;i<=n;++i){
		scanf("%d",&q[i]);
		if(m==0){
			b[q[i]]=n;
		}else if(m>=q[i]-1){
			m-=q[i]-1;
			b[q[i]]=-1;
		}else{
			for(int j=1;j<q[i];++j){
				++bckt[a[j]+n];
			}
			for(int j=1;j<=n;++j){
				bckt[j]+=bckt[j-1];
			}
			for(int j=1;j<q[i];++j){
				if(bckt[a[j]+n]==m){
					m=0;b[q[i]]=-a[j]-1;
					break;
				}
			}
		}
	}
	puts("Yes");
	for(int i=1;i<=n;++i){
		printf("%d ",a[i]);
	}
	puts("");
	for(int i=1;i<=n;++i){
		printf("%d ",b[i]);
	}
	puts("");
}
int main(){
	init();
	return 0;
}

CF1009F Dominant Indices

首先介绍一下我们亲爱的dsu on tree,也就是(一种?)树上启发式合并。
它本质上就是一种优化的暴力:对于树上的信息,我们先把树以某种方式剖分,然后对于关键链直接上传,非关键链暴力合并。
其中,长链剖分一般用来维护和深度相关的信息。
复杂度是O(n)的。证明我不太会。
在这一题中,我们考虑暴力维护每个点为根的子树中每一层的信息,并把非长儿子的信息合并到长儿子中。
为了保证线性,我们使用指针。
我们建一个指针数组f,其中f_{i,j}表示以i为根的根节点的子树中到i的距离为j的节点的个数。
同时建一个数组tmp,那么f就变成指向的是tmp里面的值。这样子就可以O(1)合并非长儿子的信息了。因为\sigma len<=n,所以空间是足够的。
那就昨晚了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

const int N=1000005;
struct ee{
	int v;
	int nxt;
}e[N<<1];
int h[N],et=0;
inline void Eadd(int U,int V){
	e[++et]=(ee){V,h[U]};
	h[U]=et;
}
inline void add(int U,int V){
	Eadd(U,V);Eadd(V,U);
}
int n;
int sn[N],len[N],ans[N],tmp[N],*f[N],*id=tmp;
inline void dfs0(int X,int FA){
	sn[X]=0;
	for(int i=h[X];i;i=e[i].nxt){
		if(e[i].v==FA){
			continue;
		}
		dfs0(e[i].v,X);
		if(len[sn[X]]<len[e[i].v]){
			sn[X]=e[i].v;
		}
	}
	len[X]=len[sn[X]]+1;
}
inline void dfs1(int X,int FA){
	f[X][0]=1;
	if(sn[X]){
		f[sn[X]]=f[X]+1;
		dfs1(sn[X],X);
		ans[X]=ans[sn[X]]+1;
	}
	for(int i=h[X];i;i=e[i].nxt){
		if(e[i].v==FA||e[i].v==sn[X]){
			continue;
		}
		f[e[i].v]=id;id+=len[e[i].v];
		dfs1(e[i].v,X);
		for(int j=1;j<=len[e[i].v];++j){
			f[X][j]+=f[e[i].v][j-1];
			if((j<ans[X]&&f[X][j]>=f[X][ans[X]])||(j>ans[X]&&f[X][j]>f[X][ans[X]])){
				ans[X]=j;
			}
		}
	}
	if(f[X][ans[X]]==1){
		ans[X]=0;
	}
}
void init(){
	scanf("%d",&n);
	int u,v;
	for(int i=1;i<n;++i){
		scanf("%d%d",&u,&v);
		add(u,v);
	}
	dfs0(1,0);
	f[1]=id;id+=len[1];
	dfs1(1,0);
	for(int i=1;i<=n;++i){
		printf("%d\n",ans[i]);
	} 
}
int main(){
	init();
	return 0;
}

CF1140


CF1140A
这是一道签到题。模拟即可。


#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

int n;
int a[10005];
void init(){
	scanf("%d",&n);
	int ans=0;
	for(int i=1;i<=n;++i){
		scanf("%d",a+i);
	}
	int p=1,mx=0;
	while(p<=n){
		++ans;
		mx=max(mx,a[p]);
		while(p<=mx){
			mx=max(mx,a[p]);
			++p;
		}
	}
	printf("%d\n",ans);
}
int main(){
	init();
	return 0;
}


CF1140B
这是一道英文阅读理解题。
一个符号可以使用任意多次,因此形如>><><><><><><><的序列也是合法的。


#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

int n;
char ch[100005];

void init(){
	scanf("%d",&n);
	cin>>ch+1;
	int j=1,ans=0;
	while(ch[j]!='>'&&ch[n-j+1]!='<'){
		++j;
		++ans;
	}
	printf("%d\n",ans);
}
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		init();
	}
	return 0;
}


CF1140C
按好听程度排个序,枚举一遍。
显然某首歌后面的所有歌都可以听。但是有k的限制。所以从后往前用优先队列计算一下前k大和即可。


#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

typedef long long ll;
inline ll Max(ll A,ll B){
	return A>B?A:B;
}
struct data{
	ll b;
	ll t;
	inline operator<(const data &B)const{
		return t<B.t;
	}
}a[300005]; 

int n,k;
ll sm[300005];
priority_queue< int,vector<int>,greater<int> > q;
void init(){
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;++i){
		scanf("%lld%lld",&a[i].b,&a[i].t);
	}
	sort(a+1,a+1+n);
	ll cnt=0;
	for(int i=n;i>=1;--i){
		cnt+=a[i].b;
		q.push(a[i].b);
		while(q.size()>k){
			cnt-=q.top();
			q.pop();
		}
		sm[i]=cnt;
	}
	ll ans=0;
	for(int i=1;i<=n;++i){
		ans=Max(ans,sm[i]*a[i].t);
	}
	printf("%lld\n",ans);
}
int main(){
	init();
	return 0;
}


CF1140D
贪心地考虑,每个顶点都选择1的话答案会最优。
如果每个都把一个顶点选择1的话,那么根据基本不等式,选择尽可能相邻的构成三角形会更优。


#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

int n;

void init(){
	scanf("%d",&n);
	long long ans=0;
	for(int i=2;i<n;++i){
		ans+=1*i*(i+1);
	}
	printf("%lld\n",ans);
}
int main(){
	init();
	return 0;
}


CF1140E
我们发现,由于限定为奇回文串,原题的题意可以转化为求隔一个不相等的方案数。
故而,容易发现,这是奇偶无关的。
我们容易地令\(f_{i,j}\)为第\(i\)个填\(j\)的方案数。容易得到:
$$f_{i,j}+=f_{i-1,k},(k\ne j)$$
然而这样的复杂度是不可接受的。
我们考虑统计一个-1区间的答案。首先,我们可以只考虑左端的非-1数对计算带来的影响——这是因为整个区间是对称的,所以右端的非-1数造成的额外影响是可以统计的。
不妨令这个-1区间前的第一个非-1数为\(q\),那么可以发现,\(f_{i,q}\ne f_{i,k},f_{i,j}=f_{i,k},(j\ne k,j\ne q,k\ne q)\)
发现这个性质之后,我们就可以优化前面的转移了。我们不妨令\(f_{i,0}\)表示第\(i\)位与\(q\)不同的方案数,\(f_{i,1}\)表示第\(i\)位与\(q\)相同的方案数。可以得到转移方程:
$$f_{i,0}=(k-2)f_{i-1,0}+(k-1)f_{i-1,1}$$
$$f_{i,1}=f_{i-1,0}$$
于是统计区间计算即可。
然而,我们还需要计算右端的第一个非-1数对答案的影响。如果它与左端的那个数相同,那么初始化\(f_{0,1}=1,f_{0,0}=0\)直接统计即可;如果它和左端的那个数不同,那么初始化\(f_{0,0}=1,f_{0,1}=0\),则可以把从左到右的贡献容斥掉。


#include<iostream>
#include<cstdio>


typedef long long ll;
const ll MOD=998244353;
ll n,k;
ll a[200005],f[200005][2];

inline ll calc(ll LEN,ll L,ll R){
	if(!LEN){
		return !L||!R||L!=R;
	}
	for(int i=0;i<=LEN;++i){
		f[i][0]=f[i][1]=0;
	}
	if(!L){
		--LEN;
		f[0][0]=k-1;
		f[0][1]=1;
	}else{
		f[0][L==R]=1;
	}
	for(int i=1;i<=LEN;++i){
		f[i][0]=(f[i-1][0]*(k-2)+f[i-1][1]*(k-1))%MOD;
		f[i][1]=f[i-1][0];
	}
	return R?f[LEN][0]:(f[LEN][0]+f[LEN][1])%MOD;
}

void init(){
	scanf("%lld%lld",&n,&k);
	for(int i=1;i<=n;++i){
		scanf("%lld",&a[i]);
	}
	ll lst=-1,ans=1;
	for(int i=1;i<=n+2;i+=2){
		if(~a[i]||i>n){
			ans*=calc(((i-lst)>>1)-1,lst>0?a[lst]:0,a[i]);
			ans%=MOD; 
			lst=i;
		}
	}
	lst=0;
	for(int i=2;i<=n+2;i+=2){
		if(~a[i]||i>n){
			ans*=calc(((i-lst)>>1)-1,lst>0?a[lst]:0,a[i]);
			ans%=MOD;
			lst=i;
		}
	}
	printf("%lld\n",ans);
}

int main(){
	init();
	return 0;
}

CF487E Tourists

众所周知,圆方树是用来处理图上点双相关问题的。
同时,点双又是一个和简单路径密切相关的东西。故而这一题我们可以考虑用圆方树来处理。
我们发现,如果两点之间有多条简单路径,那么它们一定处于同一个点双中。所以,我们可以把原图转化为圆方树,这样就可以用树链剖分套线段树来求解询问了。
但是题目要求要修改点权,这要怎么办呢?

一个直观的想法是暴力修改每个点周围相邻的方点。然而事实上如果出现了个菊花套菊花套菊花图的话显然是会严重TLE的。
我们考虑一种动态维护一个方点的点值的算法。我们尝试对每个方点开一个mulitiset,每当修改一个点的点权的时候就把旧的点权删去然后插入新的点权,并更新方点点值。
然而,如果每个修改的圆点周围都有很多的方点的话,这种做法仍然有TLE的风险。我们考虑对于每个圆点,只更新它的父亲方点。
它对它的儿子方点的贡献,则在询问的时候统计。
这样复杂度就对了。
这就使用了圆方树上树链剖分套线段树解决了这道题。

注意:
树链剖分中更新最大孩子的部分,这里是son!不是sz!调了我一个晚上!

#pragma GCC optimize("Ofast")
#include<iostream>
#include<cstdio>
#include<algorithm> 
#include<set>
#define Fv(H,A,X) for(int A=H[X];A;A=e[A].nxt)

std::multiset<int> s[200005]; 

const int INF=2147483647;

inline int Max(int A,int B){
	return A>B?A:B;
}
inline int Min(int A,int B){
	return A<B?A:B;
}
inline void Swap(int &A,int &B){
	A^=B^=A^=B;
}

struct ee{
	int v;
	int nxt;
}e[2000005];
int h0[100005],h[200005],et=0;
inline void Eadd(int *H,int U,int V){
	e[++et]=(ee){V,H[U]};
	H[U]=et;
}
inline void add(int *H,int U,int V){
	Eadd(H,U,V);
	Eadd(H,V,U);
}


int dfn[200005],lw[100005];
//注意数组大小。 
int nm,cnt=0;
int st[100005],tp=0;
inline void dfs0(int X){
	dfn[X]=lw[X]=++cnt;
	st[++tp]=X;
	Fv(h0,i,X){
		if(!dfn[e[i].v]){
			dfs0(e[i].v);
			lw[X]=Min(lw[X],lw[e[i].v]);
			if(lw[e[i].v]==dfn[X]){
				++nm;
				for(int j=0;j!=e[i].v;--tp){
					j=st[tp];
					add(h,nm,j);
				}
				add(h,X,nm);
			}
		}else{
			lw[X]=Min(lw[X],dfn[e[i].v]);
		}
	}
}
int fa[200005],sz[200005],dep[200005],son[200005],top[200005],loc[200005];
inline void dfs1(int X,int FA){
	fa[X]=FA,dep[X]=dep[FA]+1,sz[X]=1;
	Fv(h,i,X){
		if(e[i].v!=FA){
			dfs1(e[i].v,X);
			sz[X]+=sz[e[i].v];
			if(sz[son[X]]<sz[e[i].v]){
				son[X]=e[i].v;
				//这里是son!不是sz!调了我一个晚上! 
			}
		}
	}
}
inline void dfs2(int X,int FA,int TP){
	dfn[X]=++cnt,loc[cnt]=X,top[X]=TP;
	if(son[X]){
		dfs2(son[X],X,TP);
	}
	Fv(h,i,X){
		if(e[i].v!=FA&&e[i].v!=son[X]){
			dfs2(e[i].v,X,e[i].v);
		}
	}
}

int n,m,q;
int a[200005];

#define MID (L+R>>1)
#define LS (X<<1)
#define RS (X<<1|1)

int tr[600005];
inline void bld(int X,int L,int R){
	if(L==R){
		tr[X]=a[loc[L]];
//		记得逆哈希 
		return;
	}
	bld(LS,L,MID);
	bld(RS,MID+1,R);
	tr[X]=Min(tr[LS],tr[RS]);
}

inline void chg(int X,int L,int R,int P,int V){
	if(L==R){
		tr[X]=V;
		return;
	}
	P<=MID?chg(LS,L,MID,P,V):chg(RS,MID+1,R,P,V);
	tr[X]=Min(tr[LS],tr[RS]);
}

inline int qry(int X,int L,int R,int A,int B){
	if(A>R||L>B){
		return INF;
	}
	if(A<=L&&R<=B){
		return tr[X];
	}
	return Min(qry(LS,L,MID,A,B),qry(RS,MID+1,R,A,B));
}

void init(){
	scanf("%d%d%d",&n,&m,&q);
	nm=n;
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
	}
	int u,v;
	for(int i=1;i<=m;++i){
		scanf("%d%d",&u,&v);
		add(h0,u,v);
	}
	dfs0(1);
	dfs1(1,0);
	cnt=0;
	dfs2(1,0,1);
	for(int i=1;i<=n;++i){
		if(fa[i]){
			s[fa[i]].insert(a[i]);
		}
	}
	for(int i=n+1;i<=nm;++i){
		a[i]=*s[i].begin();
	}
	
	bld(1,1,nm);
	char ch[3];
	int x,y;
	int ans;
	
	for(int i=1;i<=q;++i){
		scanf("%s%d%d",ch,&x,&y);
		if(ch[0]=='C'){
			chg(1,1,nm,dfn[x],y);
			if(fa[x]){
				u=fa[x];
				s[u].erase(s[u].lower_bound(a[x]));
				s[u].insert(y);
				if(a[u]!=*s[u].begin()){
					a[u]=*s[u].begin();
					chg(1,1,nm,dfn[u],a[u]);
				}
			}
			a[x]=y;
		}else{
			ans=INF;
			while(top[x]!=top[y]){
				if(dep[top[x]]<dep[top[y]]){
					Swap(x,y);
				}
				ans=Min(ans,qry(1,1,nm,dfn[top[x]],dfn[x]));
				x=fa[top[x]];
			}
			if(dfn[x]>dfn[y]){
				Swap(x,y);
			}
			ans=Min(ans,qry(1,1,nm,dfn[x],dfn[y]));
			if(x>n){
				ans=Min(ans,a[fa[x]]);
			}
			printf("%d\n",ans);
		}
	} 
}

int main(){
	init();
	return 0;
}

CF1138

这么早的CF已经很少见了。


CF1138A
是的这题调了我半个小时。
别说了,丢人。
具体来说就是我写代码的时候默认nw总是较小的那个,但事实上有时候a[i]也有可能是较小的那个。


#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

int a[1000005],b[1000005];
int n;

void init(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",&b[i]);
	}
	a[1]=1;
	int nw=0,ans=0;
	for(int i=2;i<=n;++i){
		if(b[i]!=b[i-1]){
			nw=a[i-1];
			a[i]=1;
			ans=max(ans,min(nw,a[i]));
		}else{
			a[i]=a[i-1]+1;
			ans=max(ans,min(nw,a[i]));
		}
	}
	printf("%d\n",ans*2);
}
int main(){
	init();
	return 0;
}


CF1138B
这题我是松过去的。
一开始没看数据范围还有O(n)的幻想,看了以后就开始YY平方级的做法,但是编了半天没编出来。
最后决定破釜沉舟,写一个复杂度三方不满的暴力,居然一发入魂过了。Amazing!
一开始觉得复杂度是十亿左右,现在仔细算一算应该是一亿出头,加上常数小卡过去其实确实是有可能的。


#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

int n;
char a[5005],b[5005];
int val[5005];
int mp[5005][5005];
bool vis[5005];
inline void prnt(int i,int j,int k,int l){
	int i1=0,j1=0,k1=0,l1=0;
	for(int t=1;t<=n;++t){
		if(val[t]==0&&i1<i){
			++i1;
			printf("%d ",t);
		}
		if(val[t]==1&&k1<k){
			++k1;
			printf("%d ",t);
		}
		if(val[t]==2&&j1<j){
			++j1;
			printf("%d ",t);
		}
		if(val[t]==3&&l1<l){
			++l1;
			printf("%d ",t);
		}
	}
}
void init(){
	scanf("%d",&n);
	cin>>a+1>>b+1;
	int q=0,w=0,e=0,r=0;
	for(int i=1;i<=n;++i){
		if(a[i]=='0'&&b[i]=='0'){
			++q;
			val[i]=0;
		}
		if(a[i]=='1'&&b[i]=='0'){
			++w;
			val[i]=1;
		}
		if(a[i]=='0'&&b[i]=='1'){
			++e;
			val[i]=2;
		}
		if(a[i]=='1'&&b[i]=='1'){
			++r;
			val[i]=3;
		}
	}
//	fst->w,scn->e
	for(int i=0;i<=min(n/2,q);++i){
		for(int j=0;j<=min(n/2-i,e);++j){
			for(int k=0;k<=min(n/2-i-j,w);++k){
				int l=n/2-i-j-k;
				if(l>r){
					continue;
				}
				if(i+k==e-j+q-i&&j+l==w-k+r-l){
					prnt(q-i,e-j,w-k,r-l);
					return;
				}
			}
		}
	}
	puts("-1");
	return;
}
int main(){
	init();
	return 0;
}


CF1138C
看到这题首先就可以想到离散化。
具体来说就是我们对于每一行和每一列都各自离散化,然后计算出每个格子在这一行/列的相对大小。
由于大小关系不能改变,所以这个相对大小必须取较大值,这样才能留下足够的空间。
同样的,比每个格子大的数量也要取较大值,也是为了留下足够的空间。
然后就可以了。
不过我离散化写丑了,丢人。


#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

int n,m;
int a[1005][1005],a1[1005][1005],a2[1005][1005];
int b[1005];
int mx1[1005],mx2[1005];
void init(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			scanf("%d",&a[i][j]);
		}
	}
	int nw;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			b[j]=a[i][j];
		}
		sort(b+1,b+1+m);
		mx1[i]=unique(b+1,b+m+1)-b-1;
		for(int j=1;j<=m;++j){
			a1[i][j]=lower_bound(b+1,b+mx1[i]+1,a[i][j])-b;
		}
	}
	for(int i=1;i<=m;++i){
		for(int j=1;j<=n;++j){
			b[j]=a[j][i]; 
		}
		sort(b+1,b+1+n);
		mx2[i]=unique(b+1,b+n+1)-b-1;
		for(int j=1;j<=n;++j){
			a2[j][i]=lower_bound(b+1,b+mx2[i]+1,a[j][i])-b;
		}
	}
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			printf("%d ",max(a1[i][j],a2[i][j])+max(mx1[i]-a1[i][j],mx2[j]-a2[i][j]));
		}
		puts("");
	}
}
int main(){
	init();
	return 0;
}


CF1138D
第一个想法是暴力循环,但是那样子好像会WA9。
仔细考虑一下发现需要处理出最大非本身Border,然后分两段乱搞。
当然是要上一个KMP了。
但是我乱搞还是写丑了,WA在几十个点。现在想来应该是输出剩余的东西的时候写得丑了。最后参考了小粉兔的才通过。


#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

char a[500005],b[500005];
int x,y,n,m;
int nxt[500005];
void init(){
	cin>>a+1;
	cin>>b+1;
	n=strlen(a+1);
	m=strlen(b+1);
	for(int i=1;i<=n;++i){
		if(a[i]=='1'){
			++x;
		}else{
			++y;
		}
	}
	int l1;
	int j=0;
    for(int i=2;i<=m;i++){
        while(j&&(b[i]!=b[j+1])){
            j=nxt[j];
        }
        if(b[j+1]==b[i]){
            j++;
        }
        nxt[i]=j;
    }
    l1=nxt[m];
	j=0;
    for(int i=1;i<=n;++i){
    	if(b[j+1]=='1'&&x){
    		putchar('1');
    		--x;++j;
    		if(j==m){
    			j=l1;
			}
		}else if(b[j+1]=='0'&&y){
			putchar('0');
			--y;++j;
			if(j==m){
				j=l1;
			}
		}else{
			putchar(b[j+1]=='0'?'1':'0');
		}
	}
}
int main(){
	init();
	return 0;
}

CF1131

这么早的CF已经很少见了,不过我还是大力掉分。
我好菜啊.jpg


CF1131A
观察题意,随便推个式子提交就AC了。
打卡题。


#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

int a,b,c,d,ans=0;
void init(){
	scanf("%d%d%d%d",&a,&b,&c,&d);
	ans=a+b*2+c+d*2+std::abs(a-c)+4;
	printf("%d\n",ans);
}
int main(){
	init();
	return 0;
}


CF1131B
一道比较简单的题,但是如果脑残了会非常难。
反正我脑残以后是瞎jb写了二十七个特判死活PP不了。
当然仔细理解题意会发现还是比较简单的——当且仅当上一个的终止状态是平局态的时候,答案会有额外的统计。


#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
int n,a[100005],b[100005],ans=1;

void init(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d%d",&a[i],&b[i]);
		ans+=max(0,min(a[i],b[i])-max(a[i-1],b[i-1])+1);
		if(a[i-1]==b[i-1]){
			--ans;
		}
	}
	printf("%d\n",ans);
}
int main(){
	init();
	return 0;
}


CF1131C
比B简单,普通构造题。
第一个直观的感觉是从小到大排列,但是仔细想想觉得那样不一定更优。
所以考虑到FJ省冬令营ZZQ讲的构造技巧,可以上一个奇偶排序。
于是AC此题。


#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

int n,a[100005];

void init(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
	}
	sort(a+1,a+1+n);
	for(int i=1;i<=n;i+=2){
		printf("%d ",a[i]);
	} 
	for(int i=n;i>=1;--i){
		if(!(i&1)){
			printf("%d ",a[i]);
		}
	}
}
int main(){
	init();
	return 0;
}


CF1131D
一道细节题,车站分级弱化版。
如果没有等于号,直接拓扑排序就可以通过。
但是等于号比较蛋疼。
会发现等于号得到的东西都是相同等级的,所以可以考虑用并查集维护。
两个坑点:首先要考虑记录访问过的点的次数来判是否无解,因为可能存在一个独立的环。
然后更新答案应该要按照最后一个更新,而非第一个。这是由这个解法的基本特性,也就是解集是所有约束条件的并集这一特性决定的。


#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

int n,m,in[2005];
char ch[1005][1005];

int f[2005];
inline int fa(int X){
	return f[X]==X?X:f[X]=fa(f[X]);
}
inline void uni(int X,int Y){
	X=fa(X),Y=fa(Y);
	f[X]=Y;
}
bool mp[2005][2005];
queue<int> q;
bool vis[2005];
int ans[2005];
inline bool srt(){
	for(int i=1;i<=n+m;++i){
		if(!in[i]){
			q.push(i);
			ans[i]=1;
			vis[i]=1;
		}
	}
	int cnt=0; 
	int p;
	while(!q.empty()){
		p=q.front();
		q.pop();
		++cnt;
		for(int i=1;i<=n+m;++i){
			if(mp[p][i]){
				if(!in[fa(i)]){
					return 0;
				}else{
					--in[fa(i)];
					if(!in[fa(i)]){
						q.push(fa(i));
						ans[fa(i)]=min(ans[p]+1,ans[fa(i)]);
					}
				}
			}
		}
	}
	return cnt==n+m;
}
void init(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		std::cin>>ch[i]+1;
	}
	for(int i=1;i<=n+m;++i){
		f[i]=i,ans[i]=0x3f3f3f3f;
	}
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			if(ch[i][j]=='<'){
				mp[i][n+j]=1;
			}
			if(ch[i][j]=='>'){
				mp[n+j][i]=1;
			}
			if(ch[i][j]=='='){
				uni(i,n+j);
			}
		}
	}
	for(int i=1;i<=n+m;++i){
		if(fa(i)!=i){
			for(int j=1;j<=n+m;++j){
				mp[fa(i)][j]|=mp[i][j];
				mp[i][j]=0;
			}
			for(int j=1;j<=n+m;++j){
				if(mp[j][i]){
					mp[j][fa(i)]=1;
					mp[j][i]=0;
				}
			}
		}
	}
	for(int i=1;i<=n+m;++i){
		for(int j=1;j<=n+m;++j){
			if(mp[i][j]){
				++in[j];
			}
		}
	}
	if(!srt()){
		puts("No");
		return;
	}else{
		puts("Yes");
		for(int i=1;i<=n;++i){
			printf("%d ",ans[fa(i)]);
		}
		puts("");
		for(int i=n+1;i<=n+m;++i){
			printf("%d ",ans[fa(i)]);
		}
	}
	
	
}
int main(){
	init();
	return 0;
}


CF1131F
这道题和D题有一点神似。
我们维护每一个已经弄好的连续块的左端点和右端点,每次访问到这个块就直接连接到它的父亲。
这个过程用并查集完成,使得可以直接搜索到整个块的端点。每一次直接把前一个块接在后一个块的左边就好了。
把每个连接记录一下最后输出即可。


#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

struct ee{
	int v;
	int nxt;
}e[300005];
int h[150005],et=0;
inline void add(int U,int V){
	e[++et]=(ee){V,h[U]};
	h[U]=et;
}
int n,l[150005],r[150005];
int f[150005];
inline int fa(int X){
	return X==f[X]?X:f[X]=fa(f[X]);
}
inline void uni(int X,int Y){
	X=fa(X),Y=fa(Y);
	f[X]=Y;
}
void init(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		l[i]=r[i]=i,f[i]=i;
	}
	int a,b;
	for(int i=1;i<n;++i){
		scanf("%d%d",&a,&b);
		a=fa(a),b=fa(b);
		add(r[a],l[b]);
		uni(a,b);
		l[b]=l[a];
	}
	a=l[fa(1)],b=0;
	printf("%d ",a);
	for(int i=1;i<n;++i){
		for(int j=h[a];j;j=e[j].nxt){
			if(e[j].v!=b){
				printf("%d ",e[j].v);
				b=a,a=e[j].v;
				break;
			}
		}
	}
}
int main(){
	init();
	return 0;
}

CF1098B Nice table

话说考场上这题距离正解只差一步了,可惜我走错方向变成枚举左上角的block然后瞎鸡儿乱搞求min了。
事实上这一题猜到结论之后可以想到另一个更科学的做法。
具体来说,可以考虑,要么是行上两种字符交替出现而列上随意,要么是列上两种字符交替出现而行上随意。
所以我们可以枚举这些信息,然后检验一下即可。
顺便提一句,这一题的数据范围真的是恶意满满。考场上是瞎jb哈希,但是现在个人觉得还是string比较科学。

#include<iostream>
#include<cstdio>
#include<cstring>

#define MAXN 300005
char lst[6][2]={{'A','G'},{'A','C'},{'A','T'},{'C','T'},{'G','T'},{'C','G'}};
std::string ch[MAXN],out[MAXN];
int n,m,cnt[MAXN][2],val[MAXN][6][2],nw[2];

void init(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		std::cin>>ch[i];
	}
	for(int i=1;i<=n;++i){
		for(int j=0;j<6;++j){
			nw[1]=nw[0]=0;
			for(int k=1;k<=m;++k){
				nw[0]+=(int)(lst[(j+(i&1)*3)%6][k&1]!=ch[i][k-1]);
				nw[1]+=(int)(lst[(j+(i&1)*3)%6][!(k&1)]!=ch[i][k-1]);
			}
			val[i][j][0]=(int)(nw[0]>=nw[1]);
			cnt[j][0]+=std::min(nw[0],nw[1]);
		}
	}
	for(int i=1;i<=m;++i){
		for(int j=0;j<6;++j){
			nw[1]=nw[0]=0;
			for(int k=1;k<=n;++k){
				nw[0]+=(int)(lst[(j+(i&1)*3)%6][k&1]!=ch[k][i-1]);
				nw[1]+=(int)(lst[(j+(i&1)*3)%6][!(k&1)]!=ch[k][i-1]);
			}
			val[i][j][1]=(int)(nw[0]>=nw[1]);
			cnt[j][1]+=std::min(nw[0],nw[1]);
		}
	}
	int ans=0x3f3f3f3f;
	int pi,pj;
	for(int i=0;i<2;++i){
		for(int j=0;j<6;++j){
			ans=(cnt[j][i]<ans)?pi=i,pj=j,cnt[j][i]:ans;
		}
	}
	if(!pi){
		for(int i=1;i<=n;++i){
			for(int j=1;j<=m;++j){
				putchar(lst[(pj+(i&1)*3)%6][(j&1)!=(val[i][pj][0])]); 
			}
			puts("");
		}
	}else{
		for(int i=1;i<=m;++i){
			for(int j=1;j<=n;++j){
				out[j]+=lst[(pj+(i&1)*3)%6][(j&1)!=(val[i][pj][1])];
			}
		}
		for(int i=1;i<=n;++i){
			std::cout<<out[i]<<std::endl;
		}
	}
}

int main(){
	init();
	return 0;
}

CF1107

丢人场。
C题想了一个单调队列优化DP,然后瞎jb写,最后还是别人提醒了才发现自己傻了。


CF1107A
显然分成两段:第一个数和剩下全部的数是最容易想到的,也一定是合法的。
对于只有两个字符的要特殊处理。


#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

int n;
char ch[305];
 
void init(){
	memset(ch,0,sizeof(ch));
	scanf("%d",&n);
	cin>>ch+1;
	if(n==2&&ch[1]>=ch[2]){
		puts("NO");
		return;
	}
	puts("YES");puts("2");
	printf("%c ",ch[1]);
	for(int i=2;i<=n;++i){
		putchar(ch[i]);
	}
	puts("");
}
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		init();
	}
	return 0;
}



CF1107B
找规律题。没什么好说的。当然要证明也是可以的,感觉用归纳法是可以,时间不够就没有证明了。


#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

int n;
long long k,x,ans;

void init(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%I64d%I64d",&k,&x);
		ans=(k-1)*9+x;
		printf("%I64d\n",ans);
	}
}
int main(){
	init();
	return 0;
}


CF1107C
傻逼贪心,我不知道我怎么想成单调队列优化DP的。
具体来说就是用pq尽可能删小的。正确性(可能一点都不)显然。


#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

priority_queue<int,vector<int>,greater<int> > q;
char ch[200005];
int a[200005];
void init(){
	int n,K;
	scanf("%d%d",&n,&K);
	long long ans=0;
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
		ans+=a[i]; 
	}
	cin>>ch+1;
	int tot=1;
	for(int i=1;i<=n;++i){
		if(ch[i]==ch[i-1]){
			q.push(a[i]);
			++tot;
			while(tot>K&&!q.empty()){
				ans-=q.top();
				q.pop();
				--tot;
			}
		}else{
			tot=1;
			while(!q.empty()){
				q.pop();
			}
			q.push(a[i]);
		}
	}
	printf("%I64d\n",ans);
}
int main(){
	init();
	return 0;
}

CF1111

我一直以为这一天是除夕来着,不过也不算错就是了。
一场超级变态的比赛。具体来说就是:

We are sincerely apologize for the weak pretest of problem B.

——出题人

实际造成的效果就很感人了_(:з」∠)_,三分之一的选手被Hack,结束之后剩下的三分之二中的三分之二又FST了。

祝大家红红火火。

总之,我在只有两题的情况下涨分了…


CF1111A
热身题,暴力上个比较就行了。
(其实我没看数据范围,但复杂度大概是对的。)


#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

const char yuan[]={'a','e','i','o','u'};
bool bo1[200005],bo2[200005];
char ch1[200005],ch2[200005];
int n1,n2;
void init(){
	std::cin>>ch1+1;
	std::cin>>ch2+1;
	n1=strlen(ch1+1),n2=strlen(ch2+1);
	if(n1!=n2){
		puts("No");
		return;
	}
	for(int i=1;i<=n1;++i){
		for(int j=0;j<5;++j){
			if(ch1[i]==yuan[j]){
				bo1[i]=1;
			}
			if(ch2[i]==yuan[j]){
				bo2[i]=1;
			}
		}
	}
	for(int i=1;i<=n1;++i){
		if(bo1[i]!=bo2[i]){
			puts("No");
			return;
		}
	}
	puts("Yes");
	return;
}
int main(){
	init();
	return 0;
}


CF1111C
发现两个结论:
如果一个要塞下面有英雄,除非英雄全部聚集在某半边,否则一定是剖开来处理更优。
如果一个要塞下面是空的,一定是不剖开处理更优。
这两个结论都可以有用题目给出的式子来轻易地证明。
所以我们现在要考虑的就是如果一个要塞下面有英雄并且英雄全部聚集在某半边的情况。
考虑分治。
但是最后有一个问题:如何快速地统计一个区间之内的英雄数量?
虽然数据范围很大,但是排个序然后大力二分统计即可。
善用upperbound。


#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
/*

*/ 
long long n,k,A,B;
long long ans=0;
long long a[100005];
//所有[L,R]之间的英雄个数。
//显然upperbound(L-1)并且upperbound(R),相减即可。 
inline long long calc(int L,int R){
	return (std::upper_bound(a+1,a+1+k,R)-std::upper_bound(a+1,a+1+k,L-1)); 
}
inline long long dfs(int L,int R){
	if(L==R){
		int X=calc(L,R);
		return X?B*X:A;
	}
	if(!calc(L,R)){
		return A;
	}
	int MID=(L+R)>>1;
	if(!calc(L,MID)||!calc(MID+1,R)){
		return std::min(B*(R-L+1)*calc(L,R),dfs(L,MID)+dfs(MID+1,R));
	}else{
		return dfs(L,MID)+dfs(MID+1,R);
	}
}
void init(){
	scanf("%I64d%I64d%I64d%I64d",&n,&k,&A,&B);
	for(int i=1;i<=k;++i){
		scanf("%I64d",a+i);
	}
	std::sort(a+1,a+1+k);
	printf("%I64d",dfs(1,1<<n));
}
int main(){
	init();
	return 0;
}

CF1099

一场爆肝场。
如果不是划水划到太晚才不会打呢(大雾)
整体来说难度较低…但是EF都没做出来,丢人。


CF1099A
一道简单题。直接处理贡献即可。


#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

int w,h;
int d1,w1,d2,w2;
void init(){
	scanf("%d%d%d%d%d%d",&w,&h,&w1,&d1,&w2,&d2);
	int ans=w;
	for(int i=h;i>=0;--i){
		ans+=i;
		if(d1==i){
			ans-=w1;
			ans=std::max(ans,0);
			continue;
		}
		if(d2==i){
			ans-=w2;
			ans=std::max(ans,0);
			continue;
		}
		
	}
	printf("%d\n",ans);
}
int main(){
	init();
	return 0;
}


CF1099B
找规律题。
解一个二次方程很容易就可以找到最优解。
实际情况当然是大力分类讨论。


#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;
int n;
void init(){
	int ans=0;
	scanf("%d",&n);
	int flr=(floor(sqrt(n)));
	ans=2*flr;
	n-=flr*flr;
	if(n&&n<=flr){
		++ans;
	}else if(n&&n>flr){
		ans+=2;
	}
	printf("%d\n",ans);
}
int main(){
	init();
	return 0;
}


CF1099C
一道有一定难度的模拟题。
很容易可以想到朴素的贪心做法。就是,能删的全都删;要加的一次加光。
要考虑很多细节。注意对无解情况的判定。


#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
char base[205];
int len,del,ad,gl;
void init(){
	cin>>base+1;
	scanf("%d",&gl);
	len=strlen(base+1);
	for(int i=1;i<=len;++i){
		if(base[i]=='?'){
			++del;
		}
		if(base[i]=='*'){
			++ad;
		}
	}
	int n=len;
	len-=del;
	len-=ad;
	if(len-del-ad>gl||(!ad&&len<gl)){
		puts("Impossible");
	}else{
		if(len==gl){
			for(int i=1;i<=n;++i){
				if(base[i]!='?'&&base[i]!='*'){
					putchar(base[i]);
				}
			}
		}else if(len>gl){
			int cnt=len-gl;
			for(int i=1;i<=n;++i){
				if(base[i]=='*'){
					base[i]='?';
				}
			}
			for(int i=1;i<=n;++i){
				if(base[i+1]=='?'&&cnt){
					++i;
					--cnt;
				}else if(base[i]=='?'){
					continue;
				}else{
					putchar(base[i]);
				}
			}
			return;
		}else if(len<gl){
			int cnt=gl-len;
			for(int i=1;i<=n;++i){
				if(base[i+1]=='*'&&cnt){
					for(int j=0;j<=cnt;++j){
						putchar(base[i]);
					}
					cnt=0;
				}else if(base[i]=='?'||base[i]=='*'){
					continue;
				}else{
					putchar(base[i]);
				}
			}
		}
	}
}
int main(){
	init();
	return 0;
}


CF1099D
一道有一定思维难度的树形DP。
很容易可以证明,贪心地取子树最小总是更优的;下方只要不比上方大那就始终是有解的。


#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
struct ee{
	int v;
	int nxt;
}e[200005];
int h[100005],et=0,fa[100005],dep[100005];
inline void add(int U,int V){
	e[++et]=(ee){V,h[U]};
	h[U]=et;
}
int n,s[100005],a[100005];
inline void dfs0(int X){
	for(int i=h[X];i;i=e[i].nxt){
		if(e[i].v==fa[X]){
			continue;
		}
		dep[e[i].v]=dep[X]+1;
		dfs0(e[i].v);
	}
}
inline void dfs(int X){
	for(int i=h[X];i;i=e[i].nxt){
		if(e[i].v==fa[X]){
			continue;
		}
		dfs(e[i].v);
	}
	for(int i=h[X];i;i=e[i].nxt){
		if(e[i].v==fa[X]){
			continue;
		}
		if(!(dep[X]&1)){
			s[X]=std::min(s[X],s[e[i].v]);
		}
	}
	if(s[X]==0x3f3f3f3f){
		s[X]=s[fa[X]];
	}
}
void init(){
	scanf("%d",&n);
	int v;
	for(int i=2;i<=n;++i){
		scanf("%d",&v);
		fa[i]=v;
		add(i,v);
		add(v,i);
	}
	dep[1]=1,fa[1]=0;
	dfs0(1);
	for(int i=1;i<=n;++i){
		scanf("%d",s+i);
	}
	for(int i=1;i<=n;++i){
		if(s[i]==-1){
			s[i]=0x3f3f3f3f;
		}
	}
	dfs(1);
//	for(int i=1;i<=n;++i){
//		printf("%d ",dep[i]);
//	}
//	puts("");
	long long ans=0;
	for(int i=1;i<=n;++i){
		a[i]=s[i]-s[fa[i]];
		ans+=a[i];
		if(a[i]<0){
			puts("-1");
			return;
		}
	}
	printf("%I64d\n",ans);
}
int main(){
	init();
	return 0;
}

CF1091 Good Bye 2018

不知不觉就到了2018的最后一天。这个博客也有两个多月了。
我的姿势水平固然有了一定长进,但和巨神的距离却是越拉越远了。
这场CF也是,手速场我却没能有足够的手速。尤其是D题那种超简单的题目却死磕了半天才磕出来,F也没做出来。
总之,祝大家新年快乐_(:з」∠)_


CF1091A
依题意即可。
千万别掉进分类讨论的坑里。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
int a,b,c;

void init(){
	scanf("%d%d%d",&a,&b,&c);
	--b,c-=2;
	printf("%d",min(min(a,b),c)*3+3);
}
int main(){
	init();
	return 0;
}

CF1091B
我们将每个宝藏都加上每一个向量箭头,并标记目的地。
答案是任意一个被标记n次的。
可以用map或者hashmap维护。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
using namespace std;
int a[1005],b[1005],c[1005],d[1005];
typedef pair<int,int> pii;
typedef map<pii,int> mppii;
mppii mp;
int n;
void init(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d%d",a+i,b+i);
	}
	for(int i=1;i<=n;++i){
		scanf("%d%d",c+i,d+i);
	}
	for(int i=1;i<=n;++i){
		for(int j=1;j<=n;++j){
			pii nw(a[i]+c[j],b[i]+d[j]);
			++mp[nw];
		}
	}
	mppii::iterator it=mp.begin();
	while(it!=mp.end()){
		if(it->second==n){
			printf("%d %d\n",it->first.first,it->first.second);
			break;
		}
		++it;
	} 
}
int main(){
	init();
	return 0;
}

CF1091C
观察题意以后我们发现,对于\(k\),当且仅当\(n\%k == 0\)的时候,\(k\)会和其他的本质不同。
依据剩余系的性质容易证明。
那么我们就得到了一个朴素的求答案公式:
$$\forall x,st:n\% x==0,ans_{x}=\sum_{i=0}^{n/gcd(n,x)-1}(1+(ix-1)\%n+1) $$
然后考虑到\(n\%x==0\),所以
$$ans_{x}=\sum_{i=0}^{n/gcd(n,x)-1}(1+(ix-1)\%n)==\sum_{i=0}^{n/gcd(n,x)-1}(1+ix)$$
套上等差数列求和公式即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
inline long long gcd(long long A,long long B){
	return B?gcd(B,A%B):A;
}
long long n;
long long ans[100005],tp=0;

inline void calc(int X){
	long long tms=n/gcd(n,X);
	ans[++tp]=tms+((((tms*(tms-1))>>1)*X));
}

void init(){
	scanf("%I64d",&n);
	for(int i=1;i*i<=n;++i){
		if(!(n%i)){
			calc(i);
			if(i*i!=n){
				calc(n/i);
			}
		}
	}
	sort(ans+1,ans+1+tp);
	tp=unique(ans+1,ans+1+tp)-1-ans;
	for(int i=1;i<=tp;++i){
		printf("%I64d ",ans[i]);
	}
}
int main(){
	init();
	return 0;
}

CF1091D
由于长度为\(n\),显然序列的值必然是\(\frac{(n*(n+1))}{2}-SUM_i+SUM_{i+1}\), 其中\(SUM_{i}\)表示第\(i\)个排列的某个前缀和。
又排列的性质我们会发现,对于任意两个相邻的全排列,它的任意长度前缀和要么增加且前缀序列变化,要么前缀和保持不变且前缀序列保持不变。
故而,如果一个序列要满足要求,它只有两种情况——它本身就是一个排列,或者它横跨的两个排列必然有一部分前缀相同。
对于第一种情况我们可以看成它们的前缀有\(0\)个相同的。
问题转化为了,求所有排列中,两种相邻排列前缀相同的长度的和。
通过打表找规律,或者对全排列性质的精确推演,我们得到了这样一个求和式:
$$ ans=\sum_{pre=0}^{n-2}(n!-(\Pi_{i=n}^{n-pre+1}i))$$
但是暴力计算的复杂度最坏是\(n^2\)的,仍然无法通过此题。
我们考虑优化这个求和。优化的点在于\(\Pi_{i=n}^{n-pre+1}i\),我们(毫不)惊讶地发现,它等价于\(\frac{n!}{n-pre}\),所以我们可以预处理阶乘和阶乘的逆元。
这样就做完了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
const long long MOD=998244353;

long long fac[1000005],inv[1000005];
long long n;

void init(){
	scanf("%I64d",&n);
	fac[0]=fac[1]=inv[0]=inv[1]=1;
	for(int i=2;i<=n;++i){
		fac[i]=fac[i-1]*i%MOD;
		inv[i]=(MOD-MOD/i)*inv[MOD%i]%MOD;
	}
	for(int i=2;i<=n;++i){
		inv[i]=inv[i-1]*inv[i]%MOD;
	}
	long long ans=fac[n];
	for(int i=1;i<=n-2;++i){
		ans+=(fac[n]-fac[n]*inv[n-i]%MOD+MOD)%MOD;
		ans%=MOD;
	}
	printf("%I64d",ans);
}
int main(){
	init();
	return 0;
}

CF600E Lomsat gelral

一道树上启发式合并的例题。
首先考虑暴力的做法。统计每一个子节点的信息,然后传到父节点。
我们发现这样做的复杂度是\(O(n^2)\)的。显然,复杂度是错误的。
我们考虑修改统计子节点的顺序。
重链剖分有一个很有意义的性质:一个点通向根的路径上的轻边的数量最多不会超过\(log_n\)。这利用重链剖分的性质可以轻松用反证法证明。
那么,依据这个性质,我们可以统计轻边、上传重边。这也就意味着,对于每一次访问,如果它是一条轻边,那么就把它的信息统计完了清空;如果是一条重边,那么把它的信息上传。
例如,我们现在有一个节点\(X\),那么我们先计算它的所有轻节点,然后我们再计算它的重节点,最后将它除了重节点以外的地方都搜一遍,这样就获得了它的所有信息。
为什么这样做复杂度是对的呢?这就可以基于刚刚那个性质来证明了。具体地来说,一个节点会被清理信息,当且仅当它是一个节点下面的一个轻节点。也就是说,它被清空的次数就是它通向根的路径上轻边的数量。
由刚才那个性质可得,这个值是对数级的,所以复杂度是对的。
注意sm数组的tp的控制。

#include<iostream>
#include<cstdio>
struct ee{
	int v;
	int nxt;
}e[200005];
int h[100005],et=0;
inline void add(int U,int V){
	e[++et]=(ee){V,h[U]};
	h[U]=et;
}
int sn[100005],sz[100005],a[100005],cnt[100005];
bool kp[100005];
long long ans[100005];//ans表示每个节点的答案 
long long sm[100005];//sn表示出现次数为cnt次的颜色值的和 
int n;
inline void dfs1(int X,int FA){
	for(int i=h[X];i;i=e[i].nxt){
		if(e[i].v!=FA){
			dfs1(e[i].v,X);
		}
	}
	sz[X]=1;
	for(int i=h[X];i;i=e[i].nxt){
		if(e[i].v){
			sz[X]+=sz[e[i].v];
			if(sz[e[i].v]>sz[sn[X]]){
				sn[X]=e[i].v;
			}
		}
	}
}
int tp;
inline void rnw(int X,int FA,int V){
	sm[cnt[a[X]]]-=a[X];
	cnt[a[X]]+=V;
	sm[cnt[a[X]]]+=a[X];
	if(sm[tp+1]){
		++tp;
	}
	if(!sm[tp]){
		--tp;
	}
	for(int i=h[X];i;i=e[i].nxt){
		if(e[i].v!=FA&&!kp[e[i].v]){
			rnw(e[i].v,X,V);
		}
	}
}
inline void dfs2(int X,int FA,int isSn){
	for(int i=h[X];i;i=e[i].nxt){
		if(e[i].v!=FA&&e[i].v!=sn[X]){
			dfs2(e[i].v,X,0);
		}
	}
	if(sn[X]){
		dfs2(sn[X],X,1);
		kp[sn[X]]=1;
	}
	rnw(X,FA,1);
	kp[sn[X]]=0;
	ans[X]=sm[tp];
	if(!isSn){
		rnw(X,FA,-1);
	} 
}
void init(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
	}
	int u,v;
	for(int i=1;i<n;++i){
		scanf("%d%d",&u,&v);
		add(u,v),add(v,u);
	}
	dfs1(1,0);
	dfs2(1,0,1);
	for(int i=1;i<=n;++i){
		printf("%lld ",ans[i]);
	}
}

int main(){
	init();
	return 0;
}

CF1093

这场比赛打得很糟心,具体来说就是Debug能力不足。勉强涨了一点分。


CF1093 A
一道水题。依照题意模拟即可。

#include<iostream>
#include<cstdio>

int n;
void init(){
	scanf("%d",&n);
	int x,ans;
	for(int i=1;i<=n;++i){
		scanf("%d",&x);
		ans=x/7+1;
		printf("%d\n",ans);
	}
}

int main(){
	init();
	return 0;
}

CF1093 B
将字符串排序之后,如果第一项和最后一项不同,那它肯定不是回文;如果相同,那么中间也都相同,判一下即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

int n,len;
char ch[1005];
void init(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		std::memset(ch,0,sizeof(ch));
		std::cin>>ch+1;
		len=std::strlen(ch+1);
		std::sort(ch+1,ch+1+len);
		if(ch[1]==ch[len]){
			puts("-1");
			continue;
		}else{
			puts(ch+1);
		}
	}
}

int main(){
	init();
	return 0;
}

CF1093 C
考虑到数列单调不减,则A序列的前半部分也单调不减,那么我们维护一个值表示当前值,然后从\(1\)扫到\(\frac{n}{2}\)即可。该增加的时候就增加。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

int n;
long long a[200005],b[200005];
void init(){
	scanf("%d",&n);
	for(int i=1;i<=(n>>1);++i){
		scanf("%I64d",b+i);
	}
	long long nw=0;
	for(int i=1;i<=(n>>1);++i){
		if(i>1&&b[i]-nw>b[i-1]-a[i-1]){
			nw=b[i]-b[i-1]+a[i-1];
		}
		a[i]=nw,a[n-i+1]=b[i]-nw;
	}
	for(int i=1;i<=n;++i){
		printf("%I64d ",a[i]);
	}
}

int main(){
	init();
	return 0;
}

CF1093 D
考虑每一个连通块各自独立,所以分别计算出值然后乘一起即可。
又,我们发现,本质上题目要求的就是一条线段两端的点的权值的奇偶性不同。
所以我们可以对一个连通块二染色,使得任意两种颜色不相邻。很容易可以证明,要么没有方案,要么方案只有一种。
我们分别考虑用一和三来填充黑色和白色,方案数很显然是\(2^{size_0}+2^{size_1}\)。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm> 
#include<queue>
const long long MOD = 998244353;
struct ee{
	int v;
	int nxt;
}e[600005];
int h[300005],et=0;
inline long long pw(int A,int X){
	long long RT=1,BS=A;
	while(X){
		if(X&1){
			RT*=BS;
			RT%=MOD;
		}
		BS*=BS;
		BS%=MOD;
		X>>=1;
	}
	return RT;
}
inline void add(int u,int v){
	e[++et]=(ee){v,h[u]};
	h[u]=et;
}
bool clr[300005],vis[300005];
std::queue<int> q;
struct data{
	int A;
	int SZ;
}; 
inline data slv(int X){
	int RT=0;
	clr[X]=0,vis[X]=1;
	while(!q.empty()){
		q.pop();
	}
	q.push(X);
	int P,SZ=0;
	while(!q.empty()){
		P=q.front();
		q.pop();
		++SZ;
		if(!clr[P]){
			++RT;
		}
		for(int i=h[P];i;i=e[i].nxt){
			if(vis[e[i].v]){
				if(clr[e[i].v]==clr[P]){
					return (data){-1,-1};
				}
			}else{
				vis[e[i].v]=1;
				clr[e[i].v]=clr[P]^1;
				q.push(e[i].v);
			}
		}
	}
	return (data){RT,SZ};
} 
int n,m;
void init(){
	scanf("%d%d",&n,&m);
	int u,v;
	for(int i=1;i<=m;++i){
		scanf("%d%d",&u,&v);
		add(u,v);
		add(v,u);
	}
	long long ans=1;
	data A;
	for(int i=1;i<=n;++i){
		clr[i]=0;vis[i]=0;
	}	
	for(int i=1;i<=n;++i){
		if(vis[i]){
			continue;
		}else{
			A=slv(i);
			if(A.A==-1){
				puts("0");
				return;
			}
			ans*=(pw(2,A.SZ-A.A)+pw(2,A.A));
			ans%=MOD;
		}
	}
	ans%=MOD;
	printf("%I64d\n",ans);
}
inline void CLEAR(){
	for(int i=1;i<=et;++i){
		e[i].v=e[i].nxt=0;
	}
	for(int i=1;i<=n;++i){
		h[i]=0;
	}
	n=0,m=0,et=0;
}
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		init();
		CLEAR();
	}
	return 0;
}

CF799C Fountains

CF799C Fountains
可以上数据结构维护,当然也可以大力分类讨论。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,A,B,Ct=0,Dt=0;
struct data{
    int b;
    int p;
    bool operator <(const data &_B)const{
        return p<_B.p;
    }
}C[100005],D[100005];
inline int slv1(){
    if((!Ct)||(!Dt)){
        return 0;
    }
    if(C[1].p>A||D[1].p>B){
        return 0;
    }
    int rtC=0,rtD=0,pC=1,pD=1;
    while(pC<=Ct&&C[pC].p<=A){
        rtC=max(rtC,C[pC].b);
        ++pC;
    }
    while(pD<=Dt&&D[pD].p<=B){
        rtD=max(rtD,D[pD].b);
        ++pD;
    }
    return rtC+rtD;
}
//AC[i]表示,剩余为i时的最大收益,rAC[i]表示,剩余大于等于i时的最大收益。 sAC与srAC分别表示它们的位置。 
int AC[100005],rAC[100005],sAC[100005],srAC[100005],sbAC[100005];
inline int slv2(){
    if(Ct<2){
        return 0;
    }
    if(C[1].p+C[2].p>A){
        return 0;
    }
    int rtC=0;
    for(int i=1;i<=Ct&&C[i].p<=A;++i){
        if(AC[A-C[i].p]<C[i].b){
            AC[A-C[i].p]=C[i].b,sAC[A-C[i].p]=i;
        }
    }
    for(int i=A;i>=1;--i){
        if(rAC[i+1]>AC[i]){
            rAC[i]=rAC[i+1];
            srAC[i]=srAC[i+1]; 
        }else{
            rAC[i]=AC[i];
            srAC[i]=sAC[i]; 
        }
    }
    for(int i=1;i<=Ct;++i){
        if(i!=srAC[C[i].p]&&rAC[C[i].p]){
            rtC=max(rtC,C[i].b+rAC[C[i].p]);
        }else{
        	//rtC=max(rtC,C[i].b+C[i-1].b);
		}
    }
    return rtC;
}

int BD[100005],rBD[100005],sBD[100005],srBD[100005];
inline int slv3(){
    if(Dt<2){
        return 0;
    }
    if(D[1].p+D[2].p>B){
        return 0;
    }
    int rtD=0;
    for(int i=1;i<=Dt&&D[i].p<=B;++i){
        if(BD[B-D[i].p]<D[i].b){
            BD[B-D[i].p]=D[i].b,sBD[B-D[i].p]=i;
        }
    }
    for(int i=B;i>=1;--i){
        if(rBD[i+1]>BD[i]){
            rBD[i]=rBD[i+1];
            srBD[i]=srBD[i+1]; 
        }else{
            rBD[i]=BD[i];
            srBD[i]=sBD[i]; 
        }
    }
    for(int i=1;i<=Dt;++i){
        if(i!=srBD[D[i].p]&&rBD[D[i].p]){
            rtD=max(rtD,D[i].b+rBD[D[i].p]);
        }
    }
    return rtD;
}
void init(){
    scanf("%d%d%d",&n,&A,&B);
    char ch[5];
    int x,y;
    for(int i=1;i<=n;++i){
        scanf("%d%d",&x,&y);
        cin>>ch;
        if(ch[0]=='C'){
            C[++Ct]=(data){x,y};
        }else{
            D[++Dt]=(data){x,y};
        }
    }
    sort(C+1,C+1+Ct);
    sort(D+1,D+1+Dt);
    int ans=0;
    ans=max(ans,slv1());
    ans=max(ans,slv2());
    ans=max(ans,slv3());
    printf("%d\n",ans);
}
int main(){
    init();
    return 0;
}

 

CF510C

因为维护的是偏序关系,很容易可以发现是拓扑排序裸题。
一个字母写错了调了半天。
可以用堆维护字典序。


#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<vector>
using namespace std;
#define Min(_A,_B) ((_A)<(_B)?(_A):(_B))

int in[30],n,len[1005],at=0,ss[30];
bool mp[30][30];
char ch[105][105];
char ans[30];
inline void CMP(const int &A,const int &B){
    int le=Min(len[A],len[B]);
    for(int i=1;i<=le;++i){
        if(ch[A][i]!=ch[B][i]){
            if(!mp[ch[A][i]-'a'][ch[B][i]-'a']){
                mp[ch[A][i]-'a'][ch[B][i]-'a']=1;
                ++in[ch[B][i]-'a'];
            }
            return;
        }
    }
    if(len[A]>len[B]){
        puts("Impossible");
        exit(0);
    }
}
priority_queue< int,vector<int>,greater<int> > q;
inline void srt(){
    for(int i=0;i<26;++i){
        if(!in[i]){
            q.push(i);
        }
    }
    int p;
    while(!q.empty()){
        p=q.top();
        q.pop();
        ans[++at]=p+'a';
        for(int i=0;i<26;++i){
            if(mp[p][i]){
                --in[i];
                if(!in[i]){
                    q.push(i);
                }
            }
        }
    }
    if(at<26){
        puts("Impossible");
        exit(0);
    }
    ans[++at]='\0';
}
void init(){
    scanf("%d",&n);
    memset(mp,0,sizeof(mp));
    memset(in,0,sizeof(in));
    for(int i=1;i<=n;++i){
        cin>>ch[i]+1;
        len[i]=strlen(ch[i]+1);
    }
    for(int i=1;i<n;++i){
        CMP(i,i+1);
    }
    srt(); 
    cout<<ans+1;
}
int main(){
    init();
    return 0;
}

 

CF148D Bag of mice

看到\(w,b \le 1000\),我们可以大胆猜想复杂度是\(w*b\)的(大雾)
那么我们设\(f[i][j]\)表示,包里还剩下\(i\)只白老鼠,\(j\)只黑老鼠的时候,轮到公主抽,赢的期望。
仔细看了看题意(之前题意看错了,瞎想半天,淦。),我们可以发现,公主输会发生在两种情况下:
一:包里没有白老鼠了;二:公主抽到了黑老鼠而龙抽到了白老鼠。
同时,对于一个局面,公主胜利的概率有两部分;
一:公主抽到了白球。二:公主的状态转移到的状态抽到了白球。
我们分类讨论。
首先,依据公主抽到白球的概率是\(\frac{i}{i+j}\),我们可以知道:
$$f_{i,j}+=\frac{i}{i+j}$$
然后,用填表法,我们发现,公主抽到了黑老鼠且龙抽到黑老鼠的概率是:
$$\frac{j}{i+j}*\frac{j-1}{i+j-1}$$
在这种情况下,跑出一只白老鼠的概率是:
$$\frac{j}{i+j}*\frac{j-1}{i+j-1}*\frac{i}{i+j-2}$$
跑出一只黑老鼠的概率是:
$$\frac{j}{i+j}*\frac{j-1}{i+j-1}*\frac{j-2}{i+j-2}$$
所以得到转移方程:
$$f_{i,j}=\frac{j}{i+j}*\frac{j-1}{i+j-1}+f_{i-1,j-2}*\frac{j}{i+j}*\frac{j-1}{i+j-1}*\frac{i}{i+j-2}+$$
$$f_{i,j-3}*\frac{j}{i+j}*\frac{j-1}{i+j-1}*\frac{j-2}{i+j-2}$$
于是填表法可得解。

#include<iostream>
#include<cstdio>
using namespace std;
int w,b;
double f[1005][1005];
void init(){
    scanf("%d%d",&w,&b);
    for(int i=1;i<=w;++i){
        for(int j=1;j<=b;++j){
            f[i][j]=0;
        }
    }
    for(int i=1;i<=w;++i){
        f[i][0]=1;
    }
    for(int i=1;i<=b;++i){
        f[0][i]=0;
    }
    for(int i=1;i<=w;++i){
        for(int j=1;j<=b;++j){
            f[i][j]+=(double)i/(i+j);
            if(j>=2){
                f[i][j]+=f[i-1][j-2]*(double)j/(i+j)*(j-1)/(i+j-1)*i/(i+j-2);
            }
            if(j>=3){
                f[i][j]+=f[i][j-3]*(double)j/(i+j)*(j-1)/(i+j-1)*(j-2)/(i+j-2);
            }
        }
    }
    printf("%.9lf",f[w][b]);
}
int main(){
    init();
    return 0;
}

 

CF1073

CF1073A

一道水题。
首先从题意可知,当连续两个字符不同的时候,这样的字符串就是合法的。
所以找第一组两个不同的字符即可。

CF1073B

没什么好说的,依照题意大力模拟即可。

CF1073C

有一定难度的水题,但是我考场上没 调 出 来!
其实很容易可以想到,因为当长度为\(len\)的可行,长度为\(len+1\)的也一定可行。
所以考虑二分答案。
如何检验呢?其实就是将一连串的移动移除了,然后考虑它前面的部分加上后面的部分,再加上长度为len的移动序列,要怎样才能走到终点。
因此我们可以预处理曼哈顿距离前缀和。于是可以\(O(1)\)检验。
这题就做完了。
但是,我调了一个多小时——
因为我的Abs函数写挂了!!!!!
于是就从开心上分场变成了掉分场。
缺省源能写挂也是很厉害。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
#define Max(_A,_B) ((_A)>(_B)?(_A):(_B))
#define Min(_A,_B) ((_A)<(_B)?(_A):(_B))
#define INF 0x3f3f3f3f
#define Abs(_A) ((_A)>0?(_A):(-(_A)))
/*
CF1073A
*/
int n;
char ch[1005];
inline void pt(const char &a,const char &b){
	puts("YES");
	putchar(b),putchar(a);
} 
void init(){
	scanf("%d",&n);
	cin>>ch;
	int nw=0;
	for(int i=0;i<n;++i){
		if(!i){
			nw=ch[i];
		}
		if(ch[i]!=nw){
			pt(ch[i],nw);
			return;
		}
	}
	puts("NO");
}
int main(){
	init();
	return 0;
}
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
#define Max(_A,_B) ((_A)>(_B)?(_A):(_B))
#define Min(_A,_B) ((_A)<(_B)?(_A):(_B))
#define INF 0x3f3f3f3f
#define Abs(_A) ((_A)>0?(_A):(-(_A)))
/*
CF1073B
*/
int n,a[200005],b[200005];
bool bckt[200005];
priority_queue< int,vector<int>,greater<int> > q;
void init(){
	scanf("%d",&n);
	memset(bckt,0,sizeof(bckt));
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
	}
	int cnt=0,p=1;
	for(int i=1;i<=n;++i){
		scanf("%d",&b[i]);
		cnt=0;
		if(bckt[b[i]]){
			printf("0 ");
			continue;
		}
		while(a[p]!=b[i]&&p<=n){
			bckt[a[p]]=1;
			++cnt;
			++p;
		}
		if(a[p]==b[i]){
			bckt[a[p]]=1;
			++cnt;
			++p;
		}
		printf("%d ",cnt);
	}
	
}
int main(){
	init();
	return 0;
}
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
#define Max(_A,_B) ((_A)>(_B)?(_A):(_B))
#define Min(_A,_B) ((_A)<(_B)?(_A):(_B))
#define INF 0x3f3f3f3f
#define Abs(_A) ((_A)>0?(_A):(-(_A)))
/*
CF1073C
有一定难度的水题,但是我考场上没 调 出 来!
其实很容易可以想到,因为当长度为$lated len$的可行,长度为\(len+1\)的也一定可行。
所以考虑二分答案。
如何检验呢?其实就是将一连串的移动移除了,然后考虑它前面的部分加上后面的部分,再加上长度为len的移动序列,要怎样才能走到终点。 
因此我们可以预处理曼哈顿距离前缀和。于是可以\(O(1)\)检验。
这题就做完了。
但是,我调了一个多小时——
因为我的Abs函数写挂了!!!!!
于是就从开心上分场变成了掉分场。
缺省源能写挂也是很厉害。 
*/
int n;
char ch[200005];
int X,Y,smx[200005],smy[200005];
inline bool cckk(const int &s,const int &t,const int &len){
	int dx=X-(smx[n]-smx[t])-smx[s-1],dy=Y-(smy[n]-smy[t])-smy[s-1];
	if(((dx+dy)&1)!=(len&1)){
		return 0;
	}
	if((Abs(dx)+Abs(dy)>len)){
		return 0;
	}
	return 1;
}
inline bool chck(const int &len){
	for(int i=1;i-1+len<=n;++i){
		if(cckk(i,i+len-1,len)){
			return 1;
		}
	}
	return 0;
}
void init(){
	scanf("%d",&n);
	cin>>ch+1;
	scanf("%d%d",&X,&Y);
	smx[0]=smy[0]=0;
	for(int i=1;i<=n;++i){
		if(ch[i]=='U'){
			smy[i]=smy[i-1]+1;
			smx[i]=smx[i-1];
		}else if(ch[i]=='D'){
			smy[i]=smy[i-1]-1;
			smx[i]=smx[i-1];
		}else if(ch[i]=='L'){
			smx[i]=smx[i-1]-1;
			smy[i]=smy[i-1];
		}else if(ch[i]=='R'){
			smx[i]=smx[i-1]+1;
			smy[i]=smy[i-1];
		}
	}
	int l=0,r=n+1,mid;
	while(l<r){
		mid=(l+r)>>1;
		if(chck(mid)){
			r=mid;
		}else{
			l=mid+1;
		}
	}
	if(l>n){
		puts("-1");
	}else{
		printf("%d",l);
	}
}
int main(){
	init();
	return 0;
}

 

CF1072

CF1072A
一道简单题。
可以不断地切割成子问题。
然后统计计算即可。

CF1072B
一道猜结论题。
我们猜测,对于\([0,3]\)当\(t_i\)确定的时候,\(t_i | t_{i+1}==a_i\)与\(t_i \& t_{i+1}==b_i\)可以推导出唯一确定的\(t_{i+1}\)
证明很复杂,但是正确性很显然。
那么依据这个结论,可以简单\(DFS\),从而得出结果。

CF1072C
一道复杂题。
它再一次警醒了我——
你tm不会二分。

做法很显然,因为答案显然具有单调性,所以二分\(k\),然后\(O(n)\)检验即可。
检验的时候贪心地排布即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define Max(_A,_B) (_A>_B?_A:_B)
#define Min(_A,_B) (_A<_B?_A:_B)
#define Abs(_A) ((_A)?(_A):(-(_A))
#define INF 0x3f3f3f3f
/*
CF1072A
*/
int w,h,k;
void init(){
    int ans=0;
    scanf("%d%d%d",&w,&h,&k);
    while(k){
        ans+=((w<<1)+(h<<1)-4);
        --k;
        h-=4,w-=4;
    }
    printf("%d",ans);
}
int main(){
	init();
	return 0;
}
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define Max(_A,_B) (_A>_B?_A:_B)
#define Min(_A,_B) (_A<_B?_A:_B)
#define Abs(_A) ((_A)?(_A):(-(_A))
#define INF 0x3f3f3f3f
/*
CF1072B
*/
int n,a[100005],b[100005],t[100005];
void init(){
    scanf("%d",&n);
    for(int i=1;i<n;++i){
        scanf("%d",&a[i]);
    }
    for(int i=1;i<n;++i){
        scanf("%d",&b[i]);
    }
    for(int i=0;i<=4;++i){
        if(i==4){
            puts("NO");
            return;
        }
        t[1]=i;
        for(int j=1;j<n;++j){
            for(int k=0;k<=4;++k){
                if(k==4){
                    goto loop;
                }
                if((t[j]|k)==a[j]&&(t[j]&k)==b[j]){
                    t[j+1]=k;
                    break;
                }
            }
            if(j==n-1){
                puts("YES");
                for(int i=1;i<=n;++i){
                    printf("%d ",t[i]);
                }
                return;
            }
        }
        loop:;
    }
    
}
int main(){
	init();
	return 0;
}
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define Max(_A,_B) (_A>_B?_A:_B)
#define Min(_A,_B) (_A<_B?_A:_B)
#define Abs(_A) ((_A)?(_A):(-(_A))
#define INF 0x3f3f3f3f
/*
CF1072C
*/
bool bo[100005];
int a,b,at,bt,al[50005],bl[50005];
inline bool chck(int k){
    memset(bo,0,sizeof(bo));
    int nw=k,att=0,btt=0;
    at=0,bt=0;
    while(nw){
        if(att+nw<=a){
            att+=nw;
            bo[nw]=1;
            al[at++]=nw;
        }
        --nw;
    }
    nw=k;
    while(nw){
        if((!bo[nw])&&(btt+nw<=b)){
            btt+=nw;
            bo[nw]=1;
            bl[bt++]=nw;
        }
        --nw;
    }
    for(int i=1;i<=k;++i){
        if(!bo[i]){
            return 0;
        }
    }
    return 1;
}

void init(){
    scanf("%d%d",&a,&b);
    int l=0,r=100000,mid,ans=0;
    while(l<=r){
        mid=((l+r)>>1);
        if(chck(mid)){
            ans=Max(ans,mid);
            l=mid+1;
        }else{
            r=mid-1;
        }
    }
    chck(ans);
    printf("%d\n",at);
    for(int i=0;i<at;++i){
        printf("%d ",al[i]);
    }
    puts("");
    printf("%d\n",bt);
    for(int i=0;i<bt;++i){
        printf("%d ",bl[i]);
    }
    puts("");
}
int main(){
	init();
	return 0;
}