看着一群群比 LHF ， HQX 还强的大佬涌进了机房，本蒟蒻表示慌得一批

T1

讲题人说最简单的签到题本蒟蒻表示。。。

\(Update\)

用 ds ， dt 两个变量记录点 i 连向 s 或 t 最要多少条边，直接贪心选边少的加入即可

这种题尽量多想点，不要乱搞一个暴力就滚蛋

#include<bits/stdc++.h>

using namespace std;

char buf[200000],*S=buf,*T=buf;

inline char GC() {

	return S==T&&(T=(S=buf)+fread(buf,1,200000,stdin),S==T)?EOF:*S++;

}

inline int Rd() {

	register int o=0;

	char c=GC();

	for(;c<'0'||c>'9';c=GC());

	for(;c>'/'&&c<':';c=GC())o=(o<<1)+(o<<3)+(c^48);

	return o;

}

const int N=100005,M=200005;

int n,m,x[N],lst[N],nxt[M<<1],to[M<<1],cnt=1;

inline void Ae(int fr,int go) {

	to[++cnt]=go,nxt[cnt]=lst[fr],lst[fr]=cnt;

}

int main() {

	freopen("cut.in","r",stdin);

	freopen("cut.out","w",stdout);

	n=Rd(),m=Rd();

	for(int i=1;i<=n;i++)x[i]=-1;

	for(int i=1,u,v;i<=m;i++) {

		u=Rd(),v=Rd();

		Ae(u,v),Ae(v,u);

	}

	for(int i=1,ds,dt;i<=n;i++) {

		ds=dt=0;

		for(int j=lst[i],v;j;j=nxt[j]) {

			if(x[to[j]]==1)++ds;

			if(x[to[j]]==0)++dt;

		}

		if(ds<dt)x[i]=1;

		else x[i]=0;

	}

	for(int i=1;i<=n;i++)printf("%d ",x[i]);

}

T2

好像是单调队列+二分

讲题人说比较签到？！

T3

先跑一遍 manacher 求出回文长度 g[]

然后考虑每个询问都二分一个 mid ，若 \(i\in [l+mid-1,r-mid+1]，\min(g_i) \ge mid\) 则 mid 可行

发现可以用一个 ST 表维护区间最小值，时间复杂度为\(O((q+n)\log n)\)

#include<bits/stdc++.h>

using namespace std;

inline int Rd() {

	register int o=0;

	char c=getchar();

	for(;c<'0'||c>'9';c=getchar()) ;

	for(;c>'/'&&c<':';c=getchar()) o=(o<<1)+(o<<3)+(c^48);

	return o;

}

void Out(register int o) {

	if(o>9)Out(o/10);

	putchar(o%10|48);

}

const int N=500005;

int n,len,T,g[N<<1],mr,id,lg[N<<1],f[N<<1][30],p[30]={1},mid,LL,RR,l,r;

char tmp[N],s[N<<1];

inline void Manacher() {

	s[0]='$',s[1]='#',n=1;

	for(register int i=1;i<=len;i++)s[++n]=tmp[i],s[++n]='#';

	for(register int i=1;i<=n;i++) {

		g[i]=i<mr?min(mr-i,g[(id<<1)-i]):1;

		while(s[i-g[i]]==s[i+g[i]])++g[i];

		if(i+g[i]>mr)mr=i+g[i],id=i;

	}

	for(register int i=1;i<=n;i++)f[i][0]=g[i]-1;

	for(register int i=2;i<=n;i++)lg[i]=lg[i>>1]+1;

}

inline int RMQ(register int l,register int r) {

	register int k=lg[r-l+1];

	return max(f[l][k],f[r-p[k]+1][k]);

}

int main() {

	freopen("palindrome.in","r",stdin);

	freopen("palindrome.out","w",stdout);

	for(register int i=1;i<31;i++)p[i]=p[i-1]<<1;

	scanf("%s",tmp+1),T=Rd();

	len=strlen(tmp+1);

	Manacher();

	for(register int j=1;j<=lg[n]+1;j++)

		for(register int i=1;i+p[j-1]-1<=n;i++)

			f[i][j]=max(f[i][j-1],f[i+p[j-1]][j-1]);

	for(;T--;) {

		LL=Rd(),RR=Rd();

		l=1,r=RR-LL+1;

		LL=LL<<1,RR=RR<<1;

		while(l<r) {

			mid=l+r+1>>1;

			if(RMQ(LL+mid-1,RR-mid+1)>=mid)

				l=mid;

			else r=mid-1;

		}

		Out(l),putchar(10);

	}

}

T4 ：懵逼

听说是 CTY 出的题，难怪毒瘤，一堆生成函数什么的，膜拜 LZC 通过

End

今天不出所料的炸了，希望今天考差了不会印象明天的心态

考试时发了半天的呆，纠结了半天 manacher ，虽然打对了，但是这种浪费尽量不要犯

巴特西

GDKOI 2021 Day1 TG 。。。

T1

T2

T3

T4 ：懵逼

End

最新文章

热门文章