A - Palindrome

给你一个长度不超过$500000$的字符串，问其中有多少个长度为$3n+1(n\geq1)$的子串满足$s[1...2n+1]$和$s[n+1...3n+1]$都是回文串。

前中期题。考虑用Manacher求出每个点开始最多扩展多少长度的奇数回文串，假设这个值为$r_i$。那么对每个$i$，就是要求有多少个$j$使得$i< j \leq i+r_i$且$j-r_j\leq i$。那么按$j-r_j$排序将$j$插入树状数组中，将$i$从前往后扫一遍每次询问$(i,i+r_i]$里有多少个$j$即可，时间复杂度$O(nlgn)$。

#include<bits/stdc++.h>
#define N 505050
using namespace std;
int T,n,i,j,mx,p,l,r[N*2],R[N],b[N],c[N];
char ma[N*2],s[N];long long an;
bool cmp(int x,int y){return x-R[x]<y-R[y];}
void add(int x,int z){for(;x<=n;x+=x&-x)c[x]+=z;}
int qu(int x){int v=0;for(;x;x-=x&-x)v+=c[x];return v;}
int main(){
	for(scanf("%d",&T);T--;){
		scanf("%s",s);n=strlen(s);an=mx=p=l=0;
		ma[l++]='$';ma[l++]='#';
		for(i=0;i<n;i++)ma[l++]=s[i],ma[l++]='#';
		for(i=0;i<l;i++){
			r[i]=mx>i?min(r[2*p-i],mx-i):1;
			for(;ma[i+r[i]]==ma[i-r[i]];r[i]++);
			if(i+r[i]>mx)mx=i+r[i],p=i;
		}
		for(i=1;i<=n;i++)R[i]=r[i*2]/2-1,b[i]=i,c[i]=0;
		sort(b+1,b+n+1,cmp);
		for(i=j=1;i<=n;i++){
			for(;b[j]-R[b[j]]<=i&&j<=n;j++)add(b[j],1);
			an+=qu(i+R[i])-qu(i);
		}
		printf("%lld\n",an);
	}
}

B - K-th Number

给定一个长度为$n$的数列$a_i$，对于所有长度不小于$K$的连续段，求出这段中第$K$大的数加入到数组$B$中，最后求出$B$数组中第$M$大的数。$n\leq100000,K\leq n,a_i \leq 10^9$

前中期题。二分答案，将数列转化为一个01序列，那么就是求有多少个连续段使得其中$1$的个数不小于$K$，于是再单调扫一遍就好了。时间复杂度$O(nlgn)$。

C - Confliction

给你两个$N$段的折线，折线的总长度相等且不超过$10^{18}$，每一段都是斜率为$-1,0,+1$的线，求两个折线相减后所有Y坐标中出现最多的数。

中期题。即有若干段斜率为$-2,-1,0,+1,+2$的连续线段，求出现最多的数。那么分奇偶讨论，离散化将关键点抠出打上正负1标记，最后再按顺序扫一遍，更新答案即可，时间复杂度$O(nlgn)$。

#include<bits/stdc++.h>
#define N 202020
#define LL long long
using namespace std;
int T,n,m,i,j,t0,t1,t,cnt,a1[N],a2[N],V[N];
LL S,nv,now,an,b1[N],b2[N],v[N];
struct P{LL x,z;}q0[N*2],q1[N*2];
bool cmp(P a,P b){return a.x<b.x;}
void add2(LL L,LL R){
	if(L%2==0)q0[++t0]=P{L,1},q0[++t0]=P{R,-1};
	else q1[++t1]=P{L,1},q1[++t1]=P{R,-1};
}
void ADD(LL v,int z){
	if(v%2==0)q0[++t0]=P{v,z};else q1[++t1]=P{v,z};
}
void add1(LL L,LL R){
	ADD(L,1);ADD(L+1,1);
	ADD(R,-1);ADD(R+1,-1);
}
void add0(LL L,LL len){
	if(L%2==0)q0[++t0]=P{L,len},q0[++t0]=P{L+2,-len};
	else q1[++t1]=P{L,len},q1[++t1]=P{L+2,-len};
}
void add(LL nv,int o,LL len){
//	printf("ADD %lld %d %lld\n",nv,o,len);
	if(o==2)add2(nv,nv+len*2);
	if(o==1)add1(nv,nv+len);
	if(o==0)add0(nv,len);
	if(o==-1)add1(nv-len+1,nv+1);
	if(o==-2)add2(nv-len*2+2,nv+2);
}
int main(){
	for(scanf("%d",&T);T--;){
		scanf("%d",&n);t=0;S=0;t0=t1=0;
		for(i=1;i<=n;i++)scanf("%d%lld",&a1[i],&b1[i]),v[++t]=S,S+=b1[i];
		scanf("%d",&m);
		for(S=0,i=1;i<=m;i++)scanf("%d%lld",&a2[i],&b2[i]),a2[i]=-a2[i],v[++t]=S,S+=b2[i];
		v[++t]=S+1;
		sort(v+1,v+t+1);cnt=unique(v+1,v+t+1)-v-1;
		for(S=0,i=1;i<=n;i++){
			int ll=lower_bound(v+1,v+cnt+1,S)-v,rr=lower_bound(v+1,v+cnt+1,S+b1[i])-v;
			for(j=ll;j<rr;j++)V[j]+=a1[i];
			S+=b1[i];
		}
		for(S=0,i=1;i<=m;i++){
			int ll=lower_bound(v+1,v+cnt+1,S)-v,rr=lower_bound(v+1,v+cnt+1,S+b2[i])-v;
			for(j=ll;j<rr;j++)V[j]+=a2[i];
			S+=b2[i];
		}
		nv=0;
		for(i=1;i<t;i++){
			add(nv,V[i],v[i+1]-v[i]);
			nv+=(v[i+1]-v[i])*V[i];
		}
		sort(q0+1,q0+t0+1,cmp);sort(q1+1,q1+t1+1,cmp);
		now=0;an=0;
		for(i=j=1;i<=t0;i=j){
			for(;q0[j].x==q0[i].x&&j<=t0;j++)now+=q0[j].z;
			an=max(an,now);
		}
		now=0;
	//	for(i=1;i<=t1;i++)printf("%lld %lld\n",q1[i].x,q1[i].z);
		for(i=j=1;i<=t1;i=j){
			for(;q1[j].x==q1[i].x&&j<=t1;j++)now+=q1[j].z;
			an=max(an,now);
		}
		printf("%lld\n",an);
		for(i=1;i<=t;i++)V[i]=0;
	}
}

D - X-Men

给定一颗$N$个点的树和$M$个关键点，求关键点对最远距离除以$2$向下取整。$N,M\leq1000$。

傻逼题

E - Square Network

暴力题，还没看

F - Permutation

傻逼题

G - Debug

给你若干条语句，语句如下

STATEMENT——表示一个关键点

GOTO S——转到"S:"处

S:——接应GOTO S

IF GOTO S——可能转到"S:"处，也可能转到下一行

END——一个程序的结尾

如果没有GOTO就是转到下一行

求最少要运行程序几遍才可以到达程序的每一行

STATEMENT不超过100个，关键词不超过100个，其他语句不超过500个

直接按题意先处理一遍，在前面强行加一个STATEMENT，然后求两两STATEMENT之间是否可达。

然后使用Floyd暴力缩一遍点，缩出的新图是一个DAG

在新的DAG上做最小覆盖即可，即拆点后求最大匹配数

#include<bits/stdc++.h>
#define CL(a) memset(a,0,sizeof a)
#define N 3333
#define M 111
using namespace std;
int T,n,m,i,j,k,u,id,scc,an,ff,to[N],lx[N],ne[N],ne2[N],bl[M],vv[M],lk[M];
map<string,int>mp;
string s[N],ss[N];
bool vs[N],e[M][M],ee[M][M];
void dfs(int x){
	if(!vs[ne[x]]&&ne[x])vs[ne[x]]=1,dfs(ne[x]);
	if(!vs[ne2[x]]&&ne2[x])vs[ne2[x]]=1,dfs(ne2[x]);
}
bool fd(int x,int z){
	for(int y=1;y<=scc;y++)if(ee[x][y])
		if(vv[y]!=z)if(vv[y]=z,!lk[y]||fd(lk[y],z))return lk[y]=x,1;
	return 0;
}
int main(){
	for(scanf("%d",&T);T--;){
		CL(vv);CL(ee);CL(lk);
		mp.clear();id=0;scc=0;an=0;
		for(n=0;cin>>s[++n],s[n]!="END";);
		m=1;
		ne[m]=m+1;
		lx[m]=0;
		ne2[m]=0;
		ss[m]="STATEMENT";
		for(i=1;i<=n;i++){
			if(s[i]=="IF"){
				i+=2;
				ss[++m]=s[i];
				lx[m]=1;
				ne[m]=m+1;
			}else if(s[i]=="GOTO"){
				i++;
				ss[++m]=s[i];
				lx[m]=2;
				ne[m]=0;
			}else{
				ss[++m]=s[i];
				ne[m]=m+1;
				ne2[m]=0;
				lx[m]=0;
				if(s[i]=="END")ne[m]=0;
				if(s[i][s[i].length()-1]==':'){
					lx[m]=3;ss[m]="";
					for(j=0;j<s[i].length()-1;j++)ss[m]=ss[m]+s[i][j];
				}
				mp[ss[m]]=m;
			}
		}
		for(i=1;i<=m;i++){
			if(lx[i]==1||lx[i]==2)ne2[i]=mp[ss[i]];
			if(ss[i]=="STATEMENT")to[++id]=i;
		}
		if(id>110)for(;;);
		for(i=1;i<=id;i++){
			for(j=1;j<=n;j++)vs[j]=0;vs[to[i]]=1;
			dfs(to[i]);
			for(j=1;j<=id;j++)if(vs[to[j]])e[i][j]=1;else e[i][j]=0;
		}
		for(i=1;i<=id;i++)e[i][i]=1;
		for(k=1;k<=id;k++)for(i=1;i<=id;i++)for(j=1;j<=id;j++)if(e[i][k]&&e[k][j])e[i][j]=1;
		for(i=1;i<=id;i++)bl[i]=0;
		for(i=1;i<=id;i++)if(!bl[i]){
			bl[i]=++scc;
			for(j=i;j<=id;j++)if(e[i][j]&&e[j][i])bl[j]=bl[i];
		}
		ff=0;
		for(i=1;i<=id;i++)if(!e[1][i])ff=1;
		if(ff){puts("-1");continue;}
		for(i=1;i<=id;i++)for(j=1;j<=id;j++)if(bl[i]!=bl[j]&&e[i][j])ee[bl[i]][bl[j]]=1;
	//	for(i=1;i<=scc;i++,puts(""))for(j=1;j<=scc;j++)if(ee[i][j])putchar('1');else putchar('0');
		for(i=1;i<=scc;i++){
			if(fd(i,i))an++;
		}
		printf("%d\n",scc-an);
//		for(i=1;i<=id;puts(""),i++)for(j=1;j<=id;j++)if(e[i][j])putchar('1');else putchar('0');
	}
}

H - A Simple Stone Game

有$N$堆石子，第$i$堆石子有$a_i$颗，每次能将一堆石头的一个放到其他堆，当存在一个$x$使得所有的$a_i\ mod\ x=0$时游戏结束，求最小次数。$N,a_i\leq100000$。

中前期题。令$S=\sum_{i=1}^na_i$，$x$只有是质数的时候有意义，很明显$x|S$，那么枚举质数$x$，求得$b_i=a_i\ mod\ x$，将$b_i$排序，肯定是要用前面一段填补后面一段，找到断点求的答案，所有答案中取最小的即可。时间复杂度$O(nlg^2n)$

#include<bits/stdc++.h>
#define N 101010
#define LL long long
using namespace std;
int T,n,i,t,a[N],b[N];
LL S,an,q[99],L[N],R[N];
LL cal(LL p){
	for(int i=1;i<=n;i++)b[i]=a[i]%p;
	sort(b+1,b+n+1);R[n+1]=0;
	for(int i=1;i<=n;i++)L[i]=L[i-1]+b[i];
	for(int i=n;i;i--)R[i]=R[i+1]+(p-b[i])%p;
	for(int i=1;i<=n;i++)if(L[i]>=R[i+1])return L[i];
}
int main(){
	for(scanf("%d",&T);T--;){
		scanf("%d",&n);S=0;t=0;an=1e18;
		for(i=1;i<=n;i++)scanf("%d",&a[i]),S+=a[i];
		for(i=2;1ll*i*i<=S;i++)if(S%i==0){
			q[++t]=i;
			for(;S%i==0;S/=i);
		}
		if(S>1)q[++t]=S;
		for(i=1;i<=t;i++)an=min(an,cal(q[i]));
		printf("%lld\n",an);
	}
}

I - Cow's Segment

给定不超过$300$位的实数$a$和$b$，求一个最小的整数$x$，使得$[ax,bx]$中存在一个整点。

在SB树上查找，每次二分从而一次可以找多步，用JAVA写就好了

import java.io.*;
import java.math.*;
import java.lang.*;
import java.util.*;

public class Main {

	static public void main (String []args) {
		Scanner in = new Scanner (System.in);
		int T = in.nextInt ();
		for (int t = 0; t < T; ++t) {
			BigDecimal a, b;
			a = in.nextBigDecimal ();
			b = in.nextBigDecimal ();
			if (a.compareTo (BigDecimal.ZERO) == 0) {
				System.out.println (1);
				continue;
			}
			BigDecimal pl = BigDecimal.ZERO, ql = BigDecimal.ONE, pr = BigDecimal.ONE, qr = BigDecimal.ZERO;
			while (true) {
				BigDecimal pm = pl.add (pr), qm = ql.add (qr);
				if (a.multiply (qm).compareTo (pm) <= 0) {
					if (b.multiply (qm).compareTo (pm) < 0) {
						BigDecimal k = pr.subtract (b.multiply (qr)).divide (b.multiply (ql).subtract (pl), 0, RoundingMode.DOWN);
						if (k.compareTo (BigDecimal.ONE) > 0) k.subtract (BigDecimal.ONE);
						pr = pr.add (k.multiply (pl)); qr = qr.add (k.multiply (ql));
					} else {
						System.out.println (qm);
						break;
					}
				} else {
					BigDecimal k = a.multiply (ql).subtract (pl).divide (pr.subtract (a.multiply (qr)), 0, RoundingMode.DOWN);
					if (k.compareTo (BigDecimal.ONE) > 0) k.subtract (BigDecimal.ONE);
					pl = pl.add (k.multiply (pr)); ql = ql.add (k.multiply (qr));
				}
			}
		}
	}

}

J - Interview

有包括A和B在内的$N$个人面试，每个人有一个$1~N$的随机编号，随机一个$K\in [0,N]$，编号$[1,K]$的人第一天面试，编号$[K+1,N]$的人第二天面试。每个人知道自己哪一天面试，但不知道自己的编号。现在A知道自己第二天面试，并知道B是第几天面试，问A在第二天面试的人中期望第几个面试。$N\leq10^9,T\leq100000$。

如果不知道B的面试情况，A期望在第二天的第$\frac{N+3}{4}$个面试。如果B第一天面试，相当于少一个人，那么A会在第二天的第$\frac{N+2}{4}$天面试。如果B在第二天面试，可以算出那么A会在第二天$\frac{3N+6}{8}$天面试

K - Server

有$N$个机器和$T$天，第$i$个机器在第$[S_i,T_i]$天工作，有两个关键值$A_i,B_i$。现在要选出一个机器集合$S$，使得每一天至少有一个机器工作，且$\frac{\sum_{i\in S}A_i}{\sum_{i\in S}B_i}$最小。$N,T\leq100000$。

二分答案$x$，令$c_i=a_i-xb_i$，那么就是要选出一个满足条件的集合$S$，且$\sum_{i\in S}c_i<0$。那么按$T_i$升序处理，令$f_i$表示到第$i$天的最小值，枚举每一个区间就可以进行转移，用树状数组或线段树优化一下就好了。时间复杂度$O(Nlg^2N)$。

L - Color a Tree

给一颗$N$个点的树涂黑色或白色，有$A+B$个限制，$A$限制要满足$x$子树内至少有$y$个黑点， $B$限制要求$x$子树外至少有$y$个黑点。问至少要有多少个点被染黑，或者输出$-1$。$N,A,B\leq100000$

中期题。很明显答案有可二分性，那么二分答案$M$判断合法性，那么每个点所在的子树要求的黑点数范围为$[L_i,R_i]$，每个点还要由它所有儿子的$L$和$R$求得最后真正的范围，那就是$LL[x]=max(\sum_{x\to y}LL[y],L[x]),RR[x]=min(\sum_{x\to y}RR[y]+1,R[x])$，一旦有一个节点$LL[x]>RR[x]$就不合法，注意如果$[LL[1],RR[1]]$不包含$x$也是不合法的。时间复杂度$O(NlgN)$

#include<cstdio>
#include<algorithm>
#define N 101010
using namespace std;
int T,n,i,x,y,l,r,md,an,A,B,tot,ff,fir[N],ne[N*2],la[N*2],L[N],LL[N],R[N],sz[N],OT[N];
void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
void dfs(int x,int fa){
	sz[x]=1;LL[x]=OT[x]=0;
	for(int i=fir[x];i;i=ne[i])if(la[i]!=fa)dfs(la[i],x),sz[x]+=sz[la[i]];
}
void getans(int x,int fa,int v){
	int l=0,r=1;
	for(int i=fir[x];i;i=ne[i])if(la[i]!=fa){
		getans(la[i],x,v);
		l+=L[la[i]];r+=R[la[i]];
		l=min(l,n+1);r=min(r,sz[x]);
	}
	l=max(l,LL[x]);r=min(r,v-OT[x]);
	L[x]=l;R[x]=r;
}
bool ok(int x){
	getans(1,0,x);
	for(int i=1;i<=n;i++)if(L[i]>R[i])return 0;
	if(L[1]<=x&&x<=R[1])return 1;else return 0;
}
int main(){
	for(scanf("%d",&T);T--;){
		tot=0;
		scanf("%d",&n);
		for(i=1;i<=n;i++)fir[i]=0;
	for(i=1;i<n;i++)scanf("%d%d",&x,&y),ins(x,y),ins(y,x);
		dfs(1,0);
		scanf("%d",&A);
		for(i=1;i<=A;i++){
			scanf("%d%d",&x,&y);
			LL[x]=max(LL[x],y);
		}
				scanf("%d",&B);
		for(i=1;i<=B;i++){
			scanf("%d%d",&x,&y);
			OT[x]=max(OT[x],y);
			}
		ff=0;
		for(i=1;i<=n;i++){
			if(LL[i]>sz[i])ff=1;
			if(OT[i]>n-sz[i])ff=1;
		}
		if(ff)an=-1;else{
			for(l=0,r=n,an=-1;l<=r;)if(ok(md=l+r>>1))an=md,r=md-1;else l=md+1;
		}
		printf("%d\n",an);
	}	
}

M - Geometry Problem

给定平面上$N$个点，找到一个点使得有不少于$\frac{N}{2}$个点和它距离相等，保证有解，$N\leq100000$。

前中期题。直接每次随机三个点判断即可，随到的概率至少有$\frac{1}{8}$。注意$n\leq4$时特殊判断，以及边界情况的处理。

#include<bits/stdc++.h>
#define D double
#define eps 1e-8
#define N 111111
using namespace std;
int T,n,i,x,y,z,cnt;D R;
int Rd(int x){
	int A=rand(),B=rand();
	return (A*8192+B)%n+1;
}
D sqr(D x){return x*x;}
int sgn(D x){return x<-eps?-1:x>eps;}
struct P{
	D x,y;
	P(D x=0,D y=0):x(x),y(y){}
	D norm2(){return x*x+y*y;}
}p[111111],o;
P operator+(P a,P b){return P(a.x+b.x,a.y+b.y);}
P operator-(P a,P b){return P(a.x-b.x,a.y-b.y);}
P operator*(P a,D b){return P(a.x*b,a.y*b);}
P operator/(P a,D b){return P(a.x/b,a.y/b);}
D cj(P a,P b){return a.x*b.y-a.y*b.x;}
D dis(P a,P b){return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));}
P waixin(P a,P b,P c){
	P p=b-a,q=c-a,s(p.norm2()/2,q.norm2()/2);D d=cj(p,q);
	return a+P(cj(s,P(p.y,q.y)),cj(P(p.x,q.x),s))/d;
}
int main(){
	srand(23333);
	for(scanf("%d",&T);T--;){
		scanf("%d",&n);
		for(i=1;i<=n;i++)scanf("%lf%lf",&p[i].x,&p[i].y);
		if(n<=2){printf("%.6f %.6f 0\n",p[1].x,p[1].y);continue;}
		if(n<=4){
			o=(p[1]+p[2])/2;R=dis(o,p[1]);
			printf("%.6f %.6f %.6f\n",o.x,o.y,R);
			continue;
		}
		for(;;){
			x=Rd(n);y=Rd(n);z=Rd(n);
			if(x!=y&&x!=z&&y!=z&&sgn(cj(p[y]-p[x],p[z]-p[x]))){
				o=waixin(p[x],p[y],p[z]);R=dis(o,p[x]);cnt=0;
				if(fabs(o.x)>1e9||fabs(o.y)>1e9)continue;
				for(i=1;i<=n;i++)if(!sgn(R-dis(o,p[i])))cnt++;
				if(cnt>=(n+1)/2)break;
			}
		}
		printf("%.6f %.6f %.6f\n",o.x,o.y,R);
	}
}

• 相关文章推荐
• 全局相关文章