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 ，虽然打对了，但是这种浪费尽量不要犯