发布于

lp2757 [国家集训队]等差子序列

因为只要求存在性，故而观察到长度>3的等差序列只需要求前3项即可。
于是就转化为求 $$ a_j+a_k=2*a_i $$ 是否存在。
观察到数据范围 n<=10000 ，于是用两个 bitset 分别维护前缀桶和后缀桶，稍微左右移一下求交即可。

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

*/
const int N=10005;
bitset<N> pre,lst;
int n,a[N];
inline void init(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
	}
	pre.reset();lst.reset();
	for(int i=2;i<=n;++i){
		lst[n-a[i]]=1;
	}
	for(int i=2;i<n;++i){
		pre[a[i-1]]=1;lst[n-a[i]]=0;
		if(((2*a[i]>=n?lst<<(2*a[i]-n):lst>>(n-2*a[i]))&pre).any()){
			puts("Y");
			return;
		}
	}
	puts("N");
}

int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		init();
	}
	return 0;
}

发布于

lp1501 国家集训队 Tree II

如果没有操作2，就是树链剖分套线段树的裸题了。
但是操作2让这题变得麻烦了很多。
考虑LCT。我们知道LCT维护每一条链使用了平衡树。仔细观察这一题的信息，我们发现它们都是可以使用平衡树来维护的。
那么，我们就可以用LCT来维护这道题。
注意：处理信息的时候要先乘再加，否则可能会引起混乱。 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#define add(X,Y) (X=(X+Y)%MOD)
#define mlt(X,Y) (X=(1ll*X*Y%MOD))
using namespace std;

typedef long long ll;
inline void Swap(int &A,int &B){
	A^=B^=A^=B;
}
const int N=100005;
const ll MOD=51061;
int fa[N],ch[N][2],rev[N],sz[N];
ll sm[N],val[N],lzy1[N],lzy2[N];
inline void updt(int X){
	sz[X]=sz[ch[X][0]]+sz[ch[X][1]]+1;
	sm[X]=(sm[ch[X][0]]+sm[ch[X][1]]+val[X])%MOD;
}
inline void flp(int X){
	Swap(ch[X][0],ch[X][1]);
	rev[X]^=1;
}
inline void rnw1(int X,ll V){
	add(sm[X],1ll*V*sz[X]);
//	这里不应使用mlt，这是因为mlt会修改原数。 
	add(val[X],V);
	add(lzy1[X],V);
}
inline void rnw2(int X,ll V){
	mlt(sm[X],V);
	mlt(val[X],V);
	mlt(lzy2[X],V);
	mlt(lzy1[X],V);
}
inline void pshd(int X){
	if(lzy2[X]!=1){
		rnw2(ch[X][0],lzy2[X]);
		rnw2(ch[X][1],lzy2[X]);
		lzy2[X]=1;
	}
	if(lzy1[X]){
		rnw1(ch[X][0],lzy1[X]);
		rnw1(ch[X][1],lzy1[X]);
		lzy1[X]=0;
	}
	if(rev[X]){
		if(ch[X][0])flp(ch[X][0]);
		if(ch[X][1])flp(ch[X][1]);
		rev[X]=0;
	}
}
inline bool ntrt(int X){
	return ch[fa[X]][0]==X||ch[fa[X]][1]==X;
}
inline bool fndD(int X){
	return ch[fa[X]][1]==X;
}
inline void splayOne(int X){
	int Y=fa[X],Z=fa[Y],D=fndD(X),D2=fndD(Y),C=ch[X][D^1];
	if(ntrt(Y)){
		ch[Z][D2]=X;
	}
	ch[X][D^1]=Y,ch[Y][D]=C;
	if(C){
		fa[C]=Y;
	}
	fa[X]=Z,fa[Y]=X;
	updt(Y),updt(X);
}
int st[N];
inline void splay(int X){
	int Y=X,Z=0;
	st[++Z]=Y;
	while(ntrt(Y)){
		Y=fa[Y],st[++Z]=Y;
	}
	while(Z){
		pshd(st[Z--]);
	}
	while(ntrt(X)){
		Y=fa[X],Z=fa[Y];
		if(ntrt(Y)){
			splayOne(fndD(X)^fndD(Y)?X:Y);
		}
		splayOne(X);
	}
}
inline void access(int X){
	for(int Y=0;X;Y=X,X=fa[X]){
		splay(X),ch[X][1]=Y,updt(X);
	}
}
inline void chgrt(int X){
	access(X),splay(X),flp(X);
}
inline void split(int X,int Y){
	chgrt(X),access(Y),splay(Y);
}
//X在Y下方。
inline void link(int X,int Y){
	chgrt(X),fa[X]=Y;
} 
inline void cut(int X,int Y){
	split(X,Y),fa[X]=ch[Y][0]=0;
}

int n,q;
void init(){
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;++i){
		sm[i]=val[i]=lzy2[i]=1;
	}
	int X,Y,P,Q;
	ll V;
	for(int i=1;i<n;++i){
		scanf("%d%d",&X,&Y);
		link(X,Y);
	}
	char op[4];
	for(int i=1;i<=q;++i){
		std::cin>>op;
		scanf("%d%d",&X,&Y);
		switch(op[0]){
			case '+':{
				scanf("%lld",&V);
				split(X,Y);
				rnw1(Y,V);
				break;
			}
			case '-':{
				scanf("%d%d",&P,&Q);
				cut(X,Y);
				link(P,Q);
				break;
			}
			case '*':{
				scanf("%lld",&V);
				split(X,Y);
				rnw2(Y,V);
				break;
			}
			case '/':{
				split(X,Y);
				printf("%lld\n",sm[Y]);
				break;
			}
		}
	}
}
int main(){
	init();
	return 0;
}
发布于

lp2634 国家集训队 聪聪可可

这一题本质上和那道「模板 点分治1」是一样的，直接一边统计一边取模即可。 

#include<iostream>
#include<cstdio>
#define Fv(i,X) for(int i=h[X];i;i=e[i].nxt) 

typedef long long ll;

inline int Max(int A,int B){
	return A>B?A:B;
}
inline ll gcd(ll A,ll B){
	return B?gcd(B,A%B):A;
}

struct ee{
	int v;
	int w;
	int nxt;
}e[40005];
int h[20005],et=0;
inline void Eadd(int U,int V,int W){
	e[++et]=(ee){V,W,h[U]};
	h[U]=et; 
}
inline void add(int U,int V,int W){
	Eadd(U,V,W);
	Eadd(V,U,W);
}

int n,rt=0,s;
int vis[20005],sz[20005],mx[20005];
inline void dfs0(int X,int FA){
	sz[X]=1,mx[X]=0;
	Fv(i,X){
		if(e[i].v==FA||vis[e[i].v]){
			continue;
		}
		dfs0(e[i].v,X);
		sz[X]+=sz[e[i].v];
		mx[X]=Max(mx[X],sz[e[i].v]);
	}
	mx[X]=Max(mx[X],s-sz[X]);
	if(mx[X]<mx[rt]){
		rt=X;
	}
}
int exist[3],dis[20005],st[20005],st2[20005],tp=0,tp2=0;
ll ans=0;
inline void dfs2(int X,int FA){
	st[++tp]=dis[X];
	Fv(i,X){
		if(e[i].v==FA||vis[e[i].v]){
			continue;
		}
		dis[e[i].v]=dis[X]+e[i].w;
		dfs2(e[i].v,X);
	}
}
inline void calc(int X){
	tp2=0;
	Fv(i,X){
		if(vis[e[i].v]){
			continue;
		}
		tp=0;
		dis[e[i].v]=e[i].w;
		dfs2(e[i].v,X);
		for(int j=1;j<=tp;++j){
			ans+=exist[(3-st[j]%3)%3];
		}
		for(int j=1;j<=tp;++j){
			st2[++tp2]=st[j];
			++exist[st[j]%3];
		}
	}
	for(int i=0;i<3;++i){
		exist[i]=0;
	}
}

inline void dfs1(int X){
	exist[0]=vis[X]=1;
	calc(X);
	Fv(i,X){
		if(vis[e[i].v]){
			continue;
		}
		rt=0;
		s=sz[X];
		dfs0(e[i].v,X);
		dfs1(rt);
	}
}

void init(){
	scanf("%d",&n);
	int u,v,w;
	for(int i=1;i<n;++i){
		scanf("%d%d%d",&u,&v,&w);
		add(u,v,w);
	} 
	rt=0,mx[0]=n;
	dfs0(1,0);
	dfs1(1);
	ans=(ans<<1)+n;
	ll g=gcd(ans,n*n);
	printf("%lld/%lld\n",ans/g,(n*n)/g);
}

int main(){
	init();
	return 0;
}
发布于

lp1494 国家集训队 小Z的袜子

令颜色为\(c_i\)为第\(i\)种颜色在给定区间内出现的次数。
则，题目所求为：
$$\frac{\sum_{i=1}^{n}c_{i}(c_{i}-1)}{(r-l)(r-l+1)}$$
展开可以得到：
$$\frac{\sum_{i=1}^{n}c_{i}^2-\sum_{i=1}^{n}c_{i}}{(r-l)(r-l+1)}$$
由性质可得：
$$\sum_{i=1}^{n}c_{i}=r-l+1$$
故而，我们需要求的仅有：
$$\sum_{i=1}^{n}c_{i}^2$$
对于这个式子的求法，我们很容易可以想到莫队。
我们考虑一个区间添加上一个数与删除一个数造成的影响。
令修改的颜色为\(x\)，则：
$$\Delta v=\sum_{i=1}^{n}c_{i}^2-c_{x}^{2}+(c_{x}±1)^2-\sum_{i=1}^{n}c_{i}^2$$
展开可得：
$$\Delta v=1±2c_{x}$$

下面考虑莫队。
莫队的原理大致是，将原数列分块，然后将询问以左端点在原数列中的块为第一关键字，右端点为第二关键词来排序。
虽然说它是一种优化后的暴力，但是，若令一次修改的复杂度是\(f_{n}\)，根据最小直线斯坦纳树的性质，可以证明这么做的复杂度是 \(O(f_{n} n \sqrt{m})\)，可以通过此题。
依据毒瘤lxl的说法，莫队最快的分块大小是\(n/\sqrt{m*2/3}\)
故而我们对原数列分块完以后，将询问排序。然后开始移动区间。
扫一遍即可。
另外就是一个小优化，排序的时候分奇偶排序，也就是说，奇数块右端点递增，偶数块右端点递减。
原理很简单，就是移过去再移回来，路上的点都扫了一遍。 

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
int BLOCK;
int belong[50005];
struct Query{
	int l;
	int r;
	int id;
	int len;
	inline bool operator <(const Query &B)const{
		return (belong[l]^belong[B.l])?(belong[l]<belong[B.l]):((belong[l]&1)?r<B.r:r>B.r);
	}
}q[50005];
long long tot=0;
int cnt[50005];
inline void add(int X){
	tot+=(cnt[X]<<1|1);
	++cnt[X];
}
inline void del(int X){
	tot+=(1-(cnt[X]<<1));
	--cnt[X];
}
inline long long Gcd(long long A,long long B){
	return B?Gcd(B,A%B):A;
}
long long ans1[50005],ans2[50005];
int n,m,a[50005];
void init(){
	scanf("%d%d",&n,&m);
	BLOCK=n/std::sqrt(m*2.0/3.0); 
	for(int i=1;i<=n;++i){
		scanf("%d",a+i);
	}
	for(int i=1;i<=m;++i){
		scanf("%d%d",&q[i].l,&q[i].r);
		q[i].id=i;
		q[i].len=q[i].r-q[i].l+1;
		ans2[i]=1;
	}
	for(int i=1;i<=n;++i){
		belong[i]=(i-1)/BLOCK+1;
	}
	std::stable_sort(q+1,q+1+m);
	int l=q[1].l,r=q[1].l-1;
	long long nwgcd;
	for(int i=1;i<=m;++i){
		while(l<q[i].l){
			del(a[l]);
			++l;
		}
		while(l>q[i].l){
			--l;
			add(a[l]);
		}
		while(r>q[i].r){
			del(a[r]);
			--r;
		}
		while(r<q[i].r){
			++r;
			add(a[r]);
		}
		if(tot!=q[i].len){
			ans1[q[i].id]=tot-q[i].len,ans2[q[i].id]=1LL*(q[i].r-q[i].l)*q[i].len;
			nwgcd=Gcd(ans1[q[i].id],ans2[q[i].id]);
			ans1[q[i].id]/=nwgcd,ans2[q[i].id]/=nwgcd;
		}
	}
	for(int i=1;i<=m;++i){
		printf("%lld/%lld\n",ans1[i],ans2[i]);
	}
}

int main(){
	init();
	return 0;
}
发布于

lp4555 国家集训队 最长双回文串

一开始以为是和最长双倍回文串一样的题，不过仔细看一下发现还是简单很多。
总之是麻辣烫（Manacher）的模板题。

Manacher是一\(O(n)\)种处理回文子串的通用方法。
具体来说，对于任意回文串，以它的对称轴为对称轴的所有子串都是回文串；不以它的对称轴为对称轴的所有子串都是对称的。
因此，我们可以分别考虑用着两种情况，使得我们只需要双指针扫一遍即可。
我们记\(f[i]\)表示，以第\(i\)个点为对称轴，最长的回文串半径。
首先我们维护当前对称轴\(mid\)以及当前右端点\(mx\)，那么对于第一种情况，只需要拓展右端点即可。
下面我们考虑第二种情况。
首先，对于当前点\(i\)，总是有\(i>mid\)。
那么，如果\(i<mx\)，那么显然，在对称轴的另一边的点\(j=mid-(i-mid)\)，在\(mx\)的范围内，两者必然是拥有共同的子串的。
这样算法就设计完了。

因为是双指针移动，所以复杂度是对的。
然后呢，对于每一个位置\(i\)，我们考虑，维护\(l_{i}\)和\(r_{i}\)，分别表示，\(i\)所在的回文串中最左的左端点和最右的右端点。
那么，\(ans=Max(r_{i}-l_{i})\)
处理方法的话，维护一个双指针即可。

#include
#include
#include
using namespace std;
#define Max(_A,_B) ((_A)>(_B)?(_A):(_B))
#define Min(_A,_B) ((_A)<(_B)?(_A):(_B))

int n,f[200005],l[200005],r[200005];
char ch[100005],s[200005];
inline void manacher(){
	int mx=0,nw;
	for(int i=2;i<=n;++i){
		if(imx){
			mx=i+f[i];
			nw=i;
		}
	}
}
void init(){
	cin>>(ch+1);
	n=strlen(ch+1);
	s[1]=s[2]='#';
	for(int i=1;i<=n;++i){
		s[(i<<1)+1]=ch[i];
		s[(i<<1)+2]='#';
	}
	n=(n<<1)+2;
	s[n+1]=0;
	manacher();
	int nw=1;
	for(int i=1;i<=n;++i){
		while(nw<=i+f[i]-1){
			l[nw]=i;
			++nw;
		}
	}
	nw=n+1;
	for(int i=n;i>=1;--i){
		while(nw>=i-f[i]+1){
			r[nw]=i;
			--nw;
		}
	}
	int ans=0;
	for(int i=1;i<=n;++i){
		ans=Max(ans,r[i]-l[i]);
	}
	printf("%d\n",ans);
}
int main(){
	init();
	return 0;
}
发布于

lp1792 国家集训队 种树

首先拿到题面很容易可以想到的是状压DP，状态转移方程很容易可以推出来。
但是这么做的复杂度是\(O(n^2)\)的，只能拿到50分。
我们深入地考虑这一题的性质，我们发现，对于这个环，如果取用了上面的某一个点，那么这个点的两个邻点都不可取。
贪心地依据权值从大到小考虑，如果一个点的两个邻点加起来都不如它大的话，那么取邻点中的任意一个都不如取这个点。
如果这个点的两个邻点加一起比它大，那就考虑两种情况，一种情况是选择这个点，一种情况是选择这个点的两个邻点。
（很容易可以知道，如果两个邻点只选一个，那是一定没有选这个点优的。）
我们考虑先取了这个点，再转变为取这个点的两个邻点的情况。这种情况下，总权值就会减去这个点的权值，并且加上这个点的两个邻点的权值。
我们考虑一个有趣的性质。如果一个点的两个邻点都选取了，那么影响到的“不可被选取区域”的大小，是和三个都选是相同的。
因此，我们考虑究竟应该选取这个点还是这个点的两个邻点。我们考虑每当挖去一个点的时候，都把它的两个邻点标记为消失。
这时候对不可选取区域的影响已经确定了，因此只要确定对对权值的影响。
那么我们考虑建一个虚点，替代在贪心选取的那个点以及两个相邻的位置。这个虚点的权值相当于邻点的权值和减去原点的权值。
对于这个虚点，我们把它当做这个环上本来就存在的一个点来处理即可。
所以可以考虑用堆+双向链表来维护。

顺便提一句，这是一道三倍经验题，它的亲人们：
lp3620 APIO/CTSC2007 数据备份，lp1484 种树
前者只要差分一下，边转点，改大小判断以后的边界，再改一下单调队列；后者只要判一下负数情况。

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;

int n,m,a[200005],l[200005],r[200005],nw,nw2;
bool ext[200005];
typedef pair<int,int> pii;
priority_queue<pii> q;
void init(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
		q.push((pii){a[i],i});
		ext[i]=0;
	}
	if(m>(n>>1)){
		puts("Error!");
		return;
	}
	for(int i=2;i<=n;++i){
		l[i]=i-1;
	}
	l[1]=n;
	for(int i=1;i<n;++i){
		r[i]=i+1;
	}
	r[n]=1;
	long long ans=0;
	for(int i=1;i<=m;++i){
		while(!q.empty()&&ext[q.top().second]){
			q.pop();
		}
		nw=q.top().second;
		ans+=q.top().first;
		ext[l[nw]]=1,ext[r[nw]]=1;
		nw2=a[l[nw]]+a[r[nw]]-q.top().first;
		a[nw]=nw2;
		l[nw]=l[l[nw]],r[nw]=r[r[nw]];
		r[l[nw]]=nw,l[r[nw]]=nw;
		q.pop();
		q.push((pii){nw2,nw});
	}
	printf("%lld",ans);
}

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

顺便贴一下后面两题的代码：

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
int n,m,a[500005],l[500005],r[500005],nw,nw2;
bool ext[500005];
//lp1484 种树 
typedef pair<int,int> pii;
priority_queue<pii> q;
void init(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
		q.push((pii){a[i],i});
		ext[i]=0;
	}
	if(m>(n>>1)){
		puts("Error!");
		return;
	}
	for(int i=1;i<=n;++i){
		l[i]=i-1;
	}
	for(int i=1;i<=n;++i){
		r[i]=i+1;
	}
	long long ans=0;
	for(int i=1;i<=m;++i){
		while(!q.empty()&&ext[q.top().second]){
			q.pop();
		}
		if(q.top().first<0){
			break;
		} 
		nw=q.top().second;
		ans+=q.top().first;
		ext[l[nw]]=1,ext[r[nw]]=1;
		nw2=a[l[nw]]+a[r[nw]]-q.top().first;
		a[nw]=nw2;
		l[nw]=l[l[nw]],r[nw]=r[r[nw]];
		r[l[nw]]=nw,l[r[nw]]=nw;
		q.pop();
		q.push((pii){nw2,nw});
	}
	printf("%lld",ans);
}

int main(){
	init();
	return 0;
}
#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>
using namespace std;
int n,m,a[100005],l[100005],r[100005],nw,nw2;
bool ext[100005];
//lp3620 APIOCTSC2007 数据备份 
typedef pair<int,int> pii;
priority_queue< pii,vector<pii>,greater<pii> > q;
void init(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
		ext[i]=0;
	}
	for(int i=n;i>=1;--i){
		a[i]-=a[i-1];
	}
	for(int i=1;i<n;++i){
		a[i]=a[i+1];
		q.push((pii){a[i],i});
	} 
	a[0]=a[n]=0x3f3f3f3f; 
	if(m>(n>>1)){
		puts("Error!");
		return;
	}
	for(int i=1;i<n;++i){
		l[i]=i-1;
	}
	for(int i=1;i<n;++i){
		r[i]=i+1;
	}
	long long ans=0;
	for(int i=1;i<=m;++i){
		while(!q.empty()&&ext[q.top().second]){
			q.pop();
		}
		nw=q.top().second;
		ans+=q.top().first;
		ext[l[nw]]=1,ext[r[nw]]=1;
		nw2=a[l[nw]]+a[r[nw]]-q.top().first;
		a[nw]=nw2;
		l[nw]=l[l[nw]],r[nw]=r[r[nw]];
		r[l[nw]]=nw,l[r[nw]]=nw;
		q.pop();
		q.push((pii){nw2,nw});
	}
	printf("%lld",ans);
}

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