专题题解 - XXII Open Cup, Grand Prix of EDG

打 * 号表示没有写的题，暂时没来得及写。

---

A. A Hero Named Magnus

难度：$\bigstar$

题目大意：

你和某人进行 BO $n$ 的比赛，前 $x-1$ 局你都可能会输，之后你永远都赢，求 $n$ 的最小值使得你保证获胜。

$1\leq x\leq 2\times 10^9$

题目解法：

显然答案为 $n=2\times x-1$，时间复杂度为 $O(1)$。

代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll t,n;
int main () {
	scanf("%lld",&t);
	for (int ii=1;ii<=t;ii++) {
		scanf("%lld",&n);
		printf("%lld\n",2*n-1);
	}
	return 0;
}

---

B. A Plus B Problem

难度：$\bigstar$

题目大意：

有两个 $n$ 位的可能含前导零的十进制整数 $A,B$，令 $C$ 为它们的和的末 $n$ 位，现在有 $q$ 次操作，每次修改 $A$ 或 $B$ 中的某一位，你需要输出 $C$ 中对应位的新的值，以及三个数中总共有多少数位发生了变化。

$1\leq n,q\leq 10^6$

题目解法：

考虑如何维护进位：维护所有 $A,B$ 对应位的和不为 $9$ 的位，那么一位上有没有进位就取决于上一个和不为 $9$ 的位的和是否 $\ge 10$。

所以我们用 set 维护这些位，就可以 $O(\log n)$ 知道某一位当前是否有前面过来的进位，以及它的进位最多能影响后面多少位。

时间复杂度为 $O((n+q)\log n)$。

代码

#include <bits/stdc++.h>
using namespace std;
const int MAXN=1000010;
int n,q,x,y,z,a[MAXN],b[MAXN];
char c[MAXN];
set <int> s;
int read () {
	int res=0;
	char c=getchar();
	while (c<'0'||c>'9') {c=getchar();}
	while (c>='0'&&c<='9') {
		res=res*10+c-'0';
		c=getchar();
	}
	return res;
}
int main () {
	scanf("%d%d",&n,&q);
	scanf("%s",c+1);
	for (int i=1;i<=n;i++) {a[i]=c[i]-'0';}
	scanf("%s",c+1);
	for (int i=1;i<=n;i++) {b[i]=c[i]-'0';}
	s.insert(0);
	for (int i=1;i<=n;i++) {
		if (a[i]+b[i]!=9) {s.insert(i);}
	}
	s.insert(n+1);
	for (int i=1;i<=q;i++) {
		scanf("%d%d%d",&x,&y,&z);
		s.erase(y);
		set<int>::iterator it=s.lower_bound(y);
		int yl=a[y]+b[y]+(a[(*it)]+b[(*it)]>=10);
		if (x==1) {a[y]=z;}
		else {b[y]=z;}
		int sm=a[y]+b[y]+(a[(*it)]+b[(*it)]>=10);
		printf("%d ",sm%10);
		if (yl==sm) {printf("0\n");} 
		else if ((yl<10)^(sm<10)) {
			it--;
			printf("%d\n",y+2-max(1,(*it)));
		} else {printf("2\n");}
		if (a[y]+b[y]!=9) {s.insert(y);}
	}
	return 0;
}

---

*C. AC Automaton

难度：$\bigstar\bigstar\bigstar\bigstar$

---

D. Assumption is All You Need

难度：$\bigstar\bigstar$

题目大意：

给定 $1,\ldots,n$ 的排列 $A_1,\ldots,A_n$ 和 $B_1,\ldots,B_n$，一次操作可以交换 $A$ 中的一对逆序对，请判断能否通过若干次操作把 $A$ 变成 $B$，如果可以还请构造。

$1\leq n\leq 2021$

题目解法：

考虑依次将 $1,\ldots,n$ 归位。

比如先考虑 $1$，显然 $1$ 只能往前交换，所以 $1$ 交换之后不能到目标位置（它在 $B$ 中位置）的前面，那么我们考虑 $2$，如果 $2$ 在 $A$ 中的位置在 $1$ 之前，而又在 $1$ 的目标位置之后，那么就可以交换 $1,2$。同时，如果在某组解中没有交换 $1,2$ 而是交换了 $1,x (x>2)$，那么这一操作是可以用先交换 $1,2$，再交换 $2,x$ 来代替的，所以先交换 $1,2$ 肯定不会错过可行解（也可以理解成对于其他数来说 $1,2$ 都一样，那么由于 $1$ 还在目标位置左边，那么不如就把 $2$ 尽量往后放）。

同理，再考虑 $1,3$，如果 $3$ 又夹在 $1$ 的当前位置和目标位置中间，就又可以交换 $1,3$，以此类推。

如果某一步中 $x$ 当前位置已经在目标位置左边，那么无解。

时间复杂度为 $O(n^2)$。

代码

#include <bits/stdc++.h>
using namespace std;
const int MAXN=2022;
int t,n,a[MAXN],b[MAXN],p[MAXN],q[MAXN];
vector < pair<int,int> > ans;
int main () {
	scanf("%d",&t);
	for (int ii=1;ii<=t;ii++) {
		scanf("%d",&n);
		for (int i=1;i<=n;i++) {scanf("%d",&a[i]);p[a[i]]=i;}
		for (int i=1;i<=n;i++) {scanf("%d",&b[i]);q[b[i]]=i;}
		int flg=1;
		ans.clear();
		for (int i=1;i<=n;i++) {
			if (p[i]<q[i]) {
				flg=0;
				break;
			}
			for (int j=i+1;j<=n;j++) {
				if (p[i]>p[j]&&p[j]>=q[i]) {
					ans.push_back(make_pair(p[j],p[i]));
					swap(p[i],p[j]);
				}
			}
		}
		if (flg==0) {
			printf("-1\n");
		} else {
			int len=ans.size();
			printf("%d\n",len);
			for (int i=0;i<len;i++) {
				printf("%d %d\n",ans[i].first,ans[i].second);
			}
		}
	}
	return 0;
}

---

E. Buy and Delete

难度：$\bigstar$

题目大意：

给定 $n$ 个点 $m$ 条边的边带权有向图 $G$，边权为正。

记一个子图 $G’$ 的权值 $w(G’)$ 为：最少可以将 $G’$ 中的边拆成多少个 DAG（空图权值为 $0$）。

你需要选择一组边权和不超过 $C$ 的边集，使得其构成的子图权值最大，输出最大的权值。

$1\leq n\leq 2000, 1\leq m\leq 5000$

题目解法：

显然 $w(G’)\leq 2$，因为可以分成 $ij$ 的边 $(i,j)$ 这两种。

而 $w(G’)=0$ 当且仅当没有边，$w(G’)=1$ 当且仅当 $G’$ 是 DAG。

所以使得 $w(G’)\ge 1$ 的最小边权和是边权的最小值，使得 $w(G’)=2$ 的最小边权和是最小环的边权和。

用 Dijkstra 求最小环即可。

时间复杂度为 $O(nm\log n)$。

代码

#include <bits/stdc++.h>
using namespace std;
const int MAXN=2010;
int n,m,c,x,y,z,mn,zxh,dis[MAXN],vis[MAXN];
vector < pair<int,int> > v[MAXN];
void solve (int x) {
	priority_queue < pair<int,int> > q;
	memset(dis,0x3f,sizeof(dis));
	memset(vis,0,sizeof(vis));
	dis[x]=0;
	q.push(make_pair(0,x));
	while (q.size()) {
		pair<int,int> a=q.top();
		q.pop();
		if (vis[a.second]) {continue;}
		vis[a.second]=1;
		int len=v[a.second].size();
		for (int i=0;i<len;i++) {
			if (v[a.second][i].first==x) {zxh=min(zxh,dis[a.second]+v[a.second][i].second);}
			if (dis[v[a.second][i].first]>dis[a.second]+v[a.second][i].second) {
				dis[v[a.second][i].first]=dis[a.second]+v[a.second][i].second;
				q.push(make_pair(-dis[v[a.second][i].first],v[a.second][i].first));
			}
		}
	}
}
int main () {
	scanf("%d%d%d",&n,&m,&c);
	mn=zxh=c+1;
	for (int i=1;i<=m;i++) {
		scanf("%d%d%d",&x,&y,&z);
		mn=min(mn,z);
		v[x].push_back(make_pair(y,z));
	}
	for (int i=1;i<=n;i++) {solve(i);}
	if (c<mn) {printf("0\n");}
	else if (c<zxh) {printf("1\n");}
	else {printf("2\n");}
	return 0;
}

---

F. Illuminations II

难度：$\bigstar\bigstar$

题目大意：

给定一个凸 $n$ 边形和一个凸 $m$ 边形，后者完全包含在前者内部。

随机从 $n$ 边形的内边界选择一个点，求从这个点能看到的 $m$ 边形外边界的部分的长度期望。

$3\leq n,m\leq 2\times 10^5$

题目解法：

从 $n$ 边形上某个点能看到的 $m$ 边形外边界的部分显然是一段连续的边。

根据期望的线性性，转化为求出 $m$ 边形每条边能被 $n$ 边形内边界上多长的一段点看到，只需要求出两个端点即可。

设 $m$ 边形上一条边是 $AB$，我们只需要求出直线 $AB$ 与 $n$ 边形的两个交点即可，不妨考虑射线 $AB$，为了快速对每条边求出这个射线与 $n$ 边形的交点，可以用双指针转一圈，转化为只需要判定射线是否与 $n$ 边形的某条边相交，而这是容易的。

时间复杂度为 $O(n+m)$。

代码

#include <bits/stdc++.h>
using namespace std;
const int MAXN=200010;
const double eps=1e-8,pi=acos(-1.0),INF=1e9;
struct Vec {
	double x,y;
	Vec () {x=y=0.0;}
	Vec (double a,double b) {x=a,y=b;}
	bool operator == (Vec b) {return ((fabs(x-b.x)<eps)&&(fabs(y-b.y)<eps));}
	bool operator != (Vec b) {return ((fabs(x-b.x)>0)||(fabs(y-b.y)>0));}
	Vec operator + (Vec b) {return Vec(x+b.x,y+b.y);}
	Vec operator - (Vec b) {return Vec(x-b.x,y-b.y);}
	Vec operator - () {return Vec(-x,-y);}
	Vec operator * (double b) {return Vec(x*b,y*b);}
	Vec operator / (double b) {return Vec(x/b,y/b);}
	double operator ^ (Vec b) {return x*b.x+y*b.y;}
	double operator * (Vec b) {return x*b.y-y*b.x;}
	double len () {return sqrt(x*x+y*y);}
	double polangle () {
		double res=atan2(y,x);
		return (res>=0?res:res+2*pi);
	}
	int quad () {
		if (x>0&&y>=0) {return 1;}
		if (x<=0&&y>0) {return 2;}
		if (x<0&&y<=0) {return 3;}
		if (x>=0&&y<0) {return 4;}
		return 0;
	}
	Vec scale (Vec c,double t) {return c+(*this-c)*t;}
	Vec rot (Vec c,double a) {
		Vec tmp=*this-c;
		return c+Vec(tmp.x*cos(a)-tmp.y*sin(a),tmp.x*sin(a)+tmp.y*cos(a));
	}
	Vec perp () {return Vec(-y,x);}
	void input () {scanf("%lf%lf",&x,&y);}
	void output () {printf("(%lf,%lf)\n",x,y);}
}p[MAXN],q[MAXN];
struct Line {
	Vec p,q;
	double agl;
	Line () {p=q=Vec(0,0),agl=0.0;}
	Line (Vec a) {p=Vec(0,0),q=a,agl=a.polangle();}
	Line (Vec a,Vec b) {p=a,q=b,agl=(b-a).polangle();}
	bool operator == (Line b) {return (p==b.p)&&(q==b.q);}
	bool operator != (Line b) {return (p!=b.p)||(q!=b.q);}
	double len () {return (q-p).len();}
	Line scale (Vec c,double t) {return Line(p.scale(c,t),q.scale(c,t));}
	Line rot (double a) {return Line(p,q.rot(p,a));}
	Vec norm () {return ((q-p)/((q-p).len())).perp();}
	double linedis (Vec c) {return fabs(((p-c)*(q-c))/((p-q).len()));}
	Line line_perp (Vec c) {return Line(c,c+norm());}
	void input () {p.input();q.input();}
	void output () {printf("(%lf,%lf) - (%lf,%lf)\n",p.x,p.y,q.x,q.y);}
};
struct Circle {
	Vec c;
	double r;
	Circle () {c=Vec(0,0),r=0.0;}
	Circle (double a) {c=Vec(0,0),r=a;}
	Circle (Vec a,double b) {c=a,r=b;}
	bool operator == (Circle b) {return (c==b.c)&&(fabs(r-b.r)<eps);}
	bool operator != (Circle b) {return (c!=b.c)||(fabs(r-b.r)>eps);}
	double area () {return pi*r*r;}
	double peri () {return 2*pi*r;}
	double power (Vec p) {return ((p-c).len())*((p-c).len())-r*r;}
	Line tagent (Vec a) {return Line(c,a).line_perp(a);}
	void input () {c.input();scanf("%lf",&r);}
	void output () {printf("(%lf,%lf,%lf)\n",c.x,c.y,r);}
};
int sgn (double x) {return (x>-eps?x>eps:-1);}
double orient (Vec a,Vec b,Vec c) {return (b-a)*(c-a);}
bool cmpd (Vec a,Vec b) {return (sgn(a.x-b.x)?a.x<b.x:a.y<b.y);}
bool cmpa (Vec a,Vec b) {return (a.quad()==b.quad()?(fabs(a*b)<eps?a.x<b.x:a*b>0):a.quad()<b.quad());}
bool cmpl (Line a,Line b) {return (sgn(a.agl-b.agl)?a.agl-b.agl<0:orient(a.p,a.q,b.q)>0);}
double angle (Vec a,Vec b) {return acos(a^b/a.len()/b.len());}
double oriangle (Vec a,Vec b,Vec c) {return (orient(a,b,c)>=0?angle(b-a,c-a):pi*2.0-angle(b-a,c-a));}
bool on_line (Line a,Vec c) {return fabs((c-a.p)*(c-a.q))<eps;}
bool on_segment (Line a,Vec c) {return (on_line(a,c)&&((c-a.p)^(c-a.q))<=0);}
bool on_circle (Circle a,Vec c) {return fabs(a.power(c))<eps;}
double area3 (Vec a,Vec b,Vec c) {return ((b-a)*(c-a))/2.0;}
bool para (Line a,Line b) {
	if (fabs((a.q-a.p)*(b.q-b.p))<eps) {return 1;}
	return 0;
}
Vec itsc (Line a,Line b) {
	double tmp1=area3(b.p,a.p,a.q);
	double tmp2=area3(b.q,a.p,a.q)-tmp1;
	return b.q.scale(b.p,-tmp1/tmp2);
}
Line perpbisector (Line a) {
	Vec tmp=(a.p+a.q)/2.0;
	return a.line_perp(tmp);
}
Line anglebisector (Line a,Line b) {
	Vec x=a.q-a.p,y=b.q-b.p;
	return a.rot(oriangle(Vec(0,0),x,y)/2.0);
}
Vec projection (Line a,Vec c) {return itsc(a,a.line_perp(c));}
Vec axial_sym (Line a,Vec c) {
	Vec tmp=projection(a,c);
	return tmp*2.0-c;
}
Vec getoc (Vec a,Vec b,Vec c) {return itsc(perpbisector(Line(a,b)),perpbisector(Line(a,c)));}
Vec getgc (Vec a,Vec b,Vec c) {return Vec((a.x+b.x+c.x)/3.0,(a.y+b.y+c.y)/3.0);}
Vec getic (Vec a,Vec b,Vec c) {
	return itsc(anglebisector(Line(a,b),Line(a,c)),anglebisector(Line(b,a),Line(b,c)));
}
Vec gethc (Vec a,Vec b,Vec c) {return itsc(Line(b,c).line_perp(a),Line(a,b).line_perp(c));}
Circle outer (Vec a,Vec b,Vec c) {
	Vec d=getoc(a,b,c);
	return Circle(d,(d-a).len());
}
Circle inner (Vec a,Vec b,Vec c) {
	Vec d=getic(a,b,c);
	return Circle(d,Line(a,b).linedis(d));
}
Vec inver (Circle c,Vec a) {
	double tmp=c.r/((a-c.c).len());
	return a.scale(c.c,tmp*tmp);
}
Line inver (Circle c,Circle a) {
	Vec t=a.c*2.0-c.c;
	Vec s=a.c+((t-a.c).perp());
	return Line(inver(c,t),inver(c,s));
}
Circle inver (Circle c,Line a) {return outer(c.c,inver(c,a.p),inver(c,a.q));}
double area (Vec *a,int n) {
	double res=0;
	for (int i=0;i<n;i++) {res+=a[i]*a[(i+1)%n];}
	return fabs(res/2.0);
}
bool in_polygon (Vec *a,int n,Vec b) {
	Vec sd=Vec(b.x-2e9,b.y-1);
	int cnt=0;
	for (int i=0;i<n;i++) {
		Vec tmp=itsc(Line(b,sd),Line(a[i],a[(i+1)%n]));
		if (on_segment(Line(a[i],a[(i+1)%n]),tmp)&&on_segment(Line(b,sd),tmp)) {cnt++;}
	}
	return (cnt&1);
}
int convex (Vec *a,int n,Vec *b) {
	if (n==1) {b[0]=a[0];return 1;}
	sort(a,a+n,cmpd);
	int hd=-1;
	for (int i=0;i<n;i++) {
		while (hd>0&&orient(b[hd-1],b[hd],a[i])<=0) {hd--;}
		b[++hd]=a[i];
	}
	int tmp=hd;
	for (int i=n-2;i>=0;i--) {
		while (hd>tmp&&orient(b[hd-1],b[hd],a[i])<=0) {hd--;}
		b[++hd]=a[i];
	}
	b[hd]=Vec(0,0);
	return hd;
}
double diameter (Vec *a,int n) {
	if (n==1) {return 0.0;}
	if (n==2) {return (a[1]-a[0]).len();}
	double res=0.0;
	for (int i=0,j=1;i<n;i++) {
		while (orient(a[i],a[(i+1)%n],a[j])<orient(a[i],a[(i+1)%n],a[(j+1)%n])) {j=(j+1)%n;}
		res=max(res,max((a[j]-a[i]).len(),(a[j]-a[(i+1)%n]).len()));
	}
	return res;
}
Circle circle_cover (Vec *a,int n) {
	for (int i=1;i<n;i++) {
		int j=rand()%i;
		swap(a[i],a[j]);
	}
	Circle c;
	for (int i=0;i<n;i++) {
		if (c.power(a[i])>=0) {
			c.c=a[i],c.r=0;
			for (int j=0;j<i;j++) {
				if (c.power(a[j])>=0) {
					c.c=(a[i]+a[j])/2.0,c.r=(c.c-a[i]).len();
					for (int k=0;k<j;k++) {
						if (c.power(a[k])>=0) {c=outer(a[i],a[j],a[k]);}
					}
				}
			}
		}
	}
	return c;
}
int n,m,cur,le[MAXN],re[MAXN];
double ans,sum[MAXN*2],lt[MAXN],rt[MAXN];
Vec chk (Vec a,Vec b,Vec c,Vec d) {
	if (para(Line(a,b),Line(c,d))) {return Vec(-1e10,-1e10);}
	Vec tmp=itsc(Line(a,b),Line(c,d));
	if (((b-a)^(b-tmp))<eps&&((tmp-c)^(tmp-d))<eps) {return tmp;}
	else {return Vec(-1e10,-1e10);}
}
int main () {
	scanf("%d%d",&n,&m);
	for (int i=0;i<n;i++) {p[i].input();}
	for (int i=0;i<m;i++) {q[i].input();}
	for (int i=0;i<n;i++) {
		if (chk(q[0],q[1],p[i],p[(i+1)%n]).x>-5e9) {cur=i;break;}
	}
	for (int i=0;i<m;i++) {
		while (chk(q[i],q[(i+1)%m],p[cur],p[(cur+1)%n]).x<-5e9) {cur=(cur+1)%n;}
		Vec tmp=chk(q[i],q[(i+1)%m],p[cur],p[(cur+1)%n]);
		re[i]=cur,rt[i]=(tmp-p[cur]).len();
	}
	for (int i=0;i<n;i++) {
		if (chk(q[1],q[0],p[i],p[(i+1)%n]).x>-5e9) {cur=i;break;}
	}
	for (int i=0;i<m;i++) {
		while (chk(q[(i+1)%m],q[i],p[cur],p[(cur+1)%n]).x<-5e9) {cur=(cur+1)%n;}
		Vec tmp=chk(q[(i+1)%m],q[i],p[cur],p[(cur+1)%n]);
		le[i]=cur,lt[i]=(tmp-p[(cur+1)%n]).len();
	}
	sum[0]=(p[1]-p[0]).len();
	for (int i=1;i<2*n;i++) {sum[i]=sum[i-1]+(p[i%n]-p[(i+1)%n]).len();}
	for (int i=0;i<m;i++) {
		if (le[i]>re[i]) {re[i]+=n;}
		ans+=(sum[re[i]-1]-sum[le[i]]+rt[i]+lt[i])*(q[i]-q[(i+1)%m]).len();
	}
	ans/=sum[n-1];
	printf("%.9f\n",ans);
	return 0;
}

---

G. Occupy the Cities

难度：$\bigstar$

题目大意：

给定一个长度为 $n$ 的 $\texttt{0,1}$ 串，每一步中任何一个 $\texttt{1}$ 都可以将相邻的某一个 $\texttt{0}$ 也变成 $\texttt{1}$，求最少要多少步才能使得串变成全 $\texttt{1}$。

$1\leq n\leq 10^6$

题目解法：

二分答案，从左往右贪心判定。

时间复杂度为 $O(n\log n)$。

代码

#include <bits/stdc++.h>
using namespace std;
const int MAXN=1000010;
int t,n,cnt,a[MAXN];
char c[MAXN];
bool chk (int x) {
	int mx=0;
	for (int i=1;i<=cnt;i++) {
		if (a[i]-x>mx+1) {return 0;}
		if (a[i]-x==mx+1) {mx=a[i]+x-1;}
		else {mx=a[i]+x;}
	}
	return (mx>=n);
}
int main () {
	scanf("%d",&t);
	for (int ii=1;ii<=t;ii++) {
		scanf("%d%s",&n,c+1);
		cnt=0;
		for (int i=1;i<=n;i++) {
			if (c[i]=='1') {a[++cnt]=i;}
		}
		if (cnt==n) {
			printf("0\n");
			continue;
		}
		int l=1,r=n-1;
		while (l<r) {
			int mid=(l+r)>>1;
			if (chk(mid)) {r=mid;}
			else {l=mid+1;}
		}
		printf("%d\n",l);
	}
	return 0;
}

---

H. Popcount Words

难度：$\bigstar\bigstar\bigstar$

题目大意：

定义 $s_i$ 表示 $\operatorname{popcount}(i)\bmod 2$，令 $w(l,r)$ 表示由 $s_l,\ldots,s_r$ 依次拼接成的字符串。

给定 $n$ 个区间 $[l_i,r_i]$，令 $S$ 是由 $w(l_1,r_1),\ldots,w(l_n,r_n)$ 依次拼接成的字符串。

还有 $q$ 个询问，每个询问给定字符串 $T$，求 $T$ 在 $S$ 中的出现次数。

$1\leq n,q\leq 10^5, 1\leq l_i,r_i\leq 10^9, 1\leq \sum |T|\leq 5\times 10^5$

题目解法：

这里的 $w(l,r)$ 是一个很经典的递归构造的字符串，令 $S(0,0)=\texttt{0}, S(0,1)=\texttt{1}$，然后 $S(i+1,0)=S(i,0)+S(i,1), S(i+1,1)=S(i,1)+S(i,0)$，那么 $w(l,r)$ 就可以拆分成 $O(\log r)$ 个 $S(i,j)$ 的拼接。

所以 $S$ 可以拆分成 $O(n\log V)$ 个 $S(i,j)$ 的拼接，其中 $V$ 是 $l_i,r_i$ 的值域。

建出所有模式串的 AC 自动机，那么我们只需要先预处理出所有 $S(i,j)$（只有 $O(\log V)$ 个）在 AC 自动机上运行的结果（从一个点会跳到哪个点），就可以算出 $S$ 在 AC 自动机上行进的整个过程，而由于 $S(i,j)$ 是递归定义的，所以我们可以用类似倍增的方法算出所有 $f(u,i,j)$ 表示从 AC 自动机上点 $u$ 出发走 $S(i,j)$ 这个串会走到哪里。

然后我们要统计答案，先算出 AC 自动机上每个点经过了几次：由于我们已经可以知道从某个点 $u$ 出发走某个 $S(i,j)$ 走了几次（记为 $g(u,i,j)$），所以我们可以将这个过程再次根据递归结构“分解”，也就是从 $g(u,i,j)$ 递推到 $g(u,0,0)$ 和 $g(u,0,1)$，也就知道每个点走了几次了。

然后再 Fail 树上 DP 一下得到每个串的匹配次数。

时间复杂度为 $O((n+\sum |T|)\log V)$。

代码

#include <bits/stdc++.h>
#define ll long long
#pragma GCC optimize(2, 3, "Ofast")
#pragma GCC target("avx", "avx2")
using namespace std;
const int MAXN=500010;
int n,q,l,r,tot=1,ch[MAXN][2],dy[MAXN],fl[MAXN],f[MAXN][31][2];
ll g[MAXN][31][2],dp[MAXN];
char c[MAXN];
vector < pair<int,int> > v;
vector <int> sn[MAXN];
int lb (int x) {return (x&(-x));}
int ppc (int x) {return (x==0?0:(ppc(x-lb(x))^1));}
int glg (int x) {return (x==1?0:(glg(x>>1)+1));}
void chai (int l,int r) {
	r++;
	while (l+lb(l)<=r) {
		v.push_back(make_pair(glg(lb(l)),ppc(l)));
		l+=lb(l);
		//cout << l << "  " << r << "    " << v.back().first << "  " << v.back().second << endl;
	}
	stack < pair<int,int> > tmp;
	while (r-lb(r)>=l) {
		tmp.push(make_pair(glg(lb(r)),ppc(r)^1));
		r-=lb(r);
		//cout << l << "  " << r << "    " << v.back().first << "  " << v.back().second << endl;
	}
	while (tmp.size()) {v.push_back(tmp.top());tmp.pop();}
	return;
}
void ins (char* c,int id) {
	int len=strlen(c+1),p=1;
	for (int i=1;i<=len;i++) {
		if (!ch[p][c[i]-'0']) {ch[p][c[i]-'0']=++tot;}
		p=ch[p][c[i]-'0'];
	}
	dy[id]=p;
	return;
}
void gtfail () {
	ch[0][0]=ch[0][1]=1;
	queue <int> q;
	q.push(1);
	while (q.size()) {
		int a=q.front();
		q.pop();
		for (int i=0;i<=1;i++) {
			if (!ch[a][i]) {ch[a][i]=ch[fl[a]][i];}
			else {fl[ch[a][i]]=ch[fl[a]][i];q.push(ch[a][i]);}
		}
		if (a>1) {sn[fl[a]].push_back(a);}
	}
	return;
}
void dfs (int x) {
	int len=sn[x].size();
	for (int i=0;i<len;i++) {
		dfs(sn[x][i]);
		dp[x]+=dp[sn[x][i]];
	}
	return;
}
int read () {
	int res=0;
	char c=getchar();
	while (c<'0'||c>'9') {c=getchar();}
	while (c>='0'&&c<='9') {
		res=res*10+c-'0';
		c=getchar();
	}
	return res;
} 
void write (ll x) {
	if (x<=9) {putchar(x+'0');return;}
	write(x/10);
	putchar(x%10+'0');
}
int main () {
	n=read();
	q=read();
	for (int i=1;i<=n;i++) {
		l=read();
		r=read();
		chai(l,r);
	}
	for (int i=1;i<=q;i++) {
		cin >> c+1;
		ins(c,i);
	}
	gtfail();
	for (int i=1;i<=tot;i++) {
		f[i][0][0]=ch[i][0],f[i][0][1]=ch[i][1];
	}
	for (int i=1;i<=29;i++) {
		for (int j=1;j<=tot;j++) {
			f[j][i][0]=f[f[j][i-1][0]][i-1][1];
			f[j][i][1]=f[f[j][i-1][1]][i-1][0];
		}
	}
	int len=v.size(),cur=1;
	for (int i=0;i<len;i++) {
		g[cur][v[i].first][v[i].second]++;
		cur=f[cur][v[i].first][v[i].second];
	}
	for (int i=29;i>=1;i--) {
		for (int j=1;j<=tot;j++) {
			if (g[j][i][0]) {
				g[j][i-1][0]+=g[j][i][0],g[f[j][i-1][0]][i-1][1]+=g[j][i][0];
			}
			if (g[j][i][1]) {
				g[j][i-1][1]+=g[j][i][1],g[f[j][i-1][1]][i-1][0]+=g[j][i][1];
			}
		}
	}
	for (int i=1;i<=tot;i++) {dp[ch[i][0]]+=g[i][0][0],dp[ch[i][1]]+=g[i][0][1];}
	dfs(1);
	for (int i=1;i<=q;i++) {write(dp[dy[i]]);putchar('\n');}
	return 0;
}

---

I. PTSD

难度：$\bigstar$

题目大意：

给定长度为 $n$ 的 $\texttt{0,1}$ 串 $S$，你要将 $\{1,\ldots,n\}$ 划分成若干个子集，使得所有满足 $S_i=\texttt{1}$ 且 $i$ 在其所属子集中为次大值的 $i$ 之和最大。

$1\leq n\leq 10^6$

题目解法：

从大到小贪心，维护当前还剩几个可以作为最大值的数，如果还有这样的数且当前位为 $1$，就将它们分入一个集合，否则就将当前数也加入可以作为最大值的候选。

时间复杂度为 $O(n)$。

代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=1000010;
ll t,n,ans,lft;
char c[MAXN];
int main () {
	scanf("%lld",&t);
	for (int ii=1;ii<=t;ii++) {
		scanf("%lld%s",&n,c+1);
		ans=lft=0;
		for (int i=n;i>=1;i--) {
			if (lft&&c[i]=='1') {
				lft--,ans+=i;
			} else {
				lft++;
			}
		}
		printf("%lld\n",ans);
	}
	return 0;
}

---

J. Suffix Automaton

难度：$\bigstar\bigstar$

题目大意：

给定字符串 $S$，将所有 $S$ 的本质不同非空子串按长度为第一关键字，字典序为第二关键字排序，$q$ 次询问其中第 $k$ 个子串是什么（输出最前一次出现的左右端点）。

$1\leq |S|,q\leq 10^6$

题目解法：

本题用后缀数组处理更为直观一些。

预处理后缀数组，考虑将 height 数组按值排序，离线询问，三者（询问值，height 值和子串长度）同时从小到大考虑。

假设当前考虑到了长度为 $i$ 的子串，我们维护长度小于 $i$ 的子串数量，还维护所有长度为 $i$ 的不同子串在后缀数组中的首次出现位置，于是我们就只需要快速求出其中的第 $k$ 小，用一个维护第 $k$ 小值的倍增树状数组即可，而求出最前一次出现的左右端点只需要利用一个建立在后缀数组上的查询最小值的 ST 表即可实现。

时间复杂度为 $O((|S|+q)\log |S|)$。

代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=1000010;
struct Query {
	int id,ansl,ansr;
	ll k;
}q[MAXN];
struct Event {
	int p,v;
}e[MAXN];
int n,qu,cura,curb,sa[MAXN],rk[MAXN],zz[MAXN],buc[MAXN],sec[MAXN],h[MAXN];
int lg[MAXN],fw[MAXN],st[MAXN][21];
char c[MAXN];
bool cmp1 (Query a,Query b) {return a.k<b.k;}
bool cmp2 (Query a,Query b) {return a.id<b.id;}
bool cmp3 (int a,int b) {return c[a]<c[b];}
bool cmp4 (Event a,Event b) {return a.v<b.v;}
void bucsort () {
	for (int i=1;i<=max(n,26);i++) {buc[i]=0;}
	for (int i=1;i<=n;i++) {buc[rk[i]]++;}
	for (int i=1;i<=max(n,26);i++) {buc[i]+=buc[i-1];}
	for (int i=n;i>=1;i--) {rk[sec[i]]=buc[rk[sec[i]]]--;}
	return;
}
void getsa () {
	for (int i=1;i<=n;i++) {rk[i]=c[i]-'a'+1;}
	for (int i=1;i<=n;i++) {sa[i]=i;}
	sort(sa+1,sa+n+1,cmp3);
	for (int i=0;i<=19;i++) {
		int tmp=0;
		for (int j=n;j>=n-(1<<i)+1;j--) {sec[++tmp]=j;}
		for (int j=1;j<=n;j++) {
			zz[j]=rk[j];
			if (sa[j]>(1<<i)) {sec[++tmp]=sa[j]-(1<<i);}
		}
		bucsort();
		for (int j=1;j<=n;j++) {sa[rk[j]]=j;}
		tmp=0;
		for (int j=1;j<=n;j++) {
			if (j==1||zz[sa[j]]!=zz[sa[j-1]]||zz[sa[j]+(1<<i)]!=zz[sa[j-1]+(1<<i)]) {tmp++;}
			rk[sa[j]]=tmp;
		}
	}
	return;
}
int querymn (int l,int r) {
	int k=lg[r-l+1];
	return min(st[l][k],st[r-(1<<k)+1][k]);
}
void modify (int x,int v) {
	for (int i=x;i<=n+1;i+=(i&(-i))) {fw[i]+=v;}
	return;
}
int kth (int k) {
	int tmp=0,sum=0;
	for (int i=19;i>=0;i--) {
		if (tmp+(1<<i)<=n+1&&sum+fw[tmp+(1<<i)]<k) {
			sum+=fw[tmp+(1<<i)];
			tmp+=(1<<i);
		}
	}
	return tmp+1;
}
int main () {
	scanf("%s%d",c+1,&qu);
	n=strlen(c+1);
	getsa();
	int cur=0;
	lg[0]=-1;
	for (int i=1;i<=n;i++) {
		lg[i]=lg[i>>1]+1,st[i][0]=sa[i];
		if (rk[i]==1) {h[rk[i]]=cur=0;}
		else {
			while (i+cur<=n&&sa[rk[i]-1]+cur<=n&&c[i+cur]==c[sa[rk[i]-1]+cur]) {cur++;}
			h[rk[i]]=cur;
			cur=max(0,cur-1);
		}
	}
	for (int i=1;i<=20;i++) {
		for (int j=1;j+(1<<i)-1<=n;j++) {st[j][i]=min(st[j][i-1],st[j+(1<<(i-1))][i-1]);}
	}
	for (int i=2;i<=n;i++) {e[i-1].p=i,e[i-1].v=h[i];}
	sort(e+1,e+n,cmp4);
	for (int i=1;i<=qu;i++) {scanf("%lld",&q[i].k);q[i].id=i;}
	sort(q+1,q+qu+1,cmp1);
	cura=curb=1;
	ll nw=0,al=1;
	modify(1,1);
	modify(n+1,1);
	for (int i=1;i<=n;i++) {
		//cout << i << endl;
		if (i>1) {
			al--;
			modify(rk[n-i+2],-1);
		}
		while (cura<=n-1&&e[cura].v<i) {modify(e[cura++].p,1);al++;}
		while (curb<=qu&&q[curb].k<=nw+al) {
			int tmp=q[curb].k-nw;
			int tmpa=kth(tmp),tmpb=kth(tmp+1);
			//cout << curb << "  " << q[curb].k << "  " << nw << "  " << 
			//al << "  " << i << "  " << tmp << "  " << tmpa << "  " << tmpb << endl;
			q[curb].ansl=querymn(tmpa,tmpb-1);
			q[curb].ansr=q[curb].ansl+i-1;
			curb++;
		}
		nw+=al;
		//cout << i << "  " << al << "  " << nw << endl;
	}
	while (curb<=qu) {
		q[curb].ansl=q[curb].ansr=-1;
		curb++;
	}
	sort(q+1,q+qu+1,cmp2);
	for (int i=1;i<=qu;i++) {printf("%d %d\n",q[i].ansl,q[i].ansr);}
	return 0;
}

---

K. Tax

难度：$\bigstar\bigstar\bigstar$

题目大意：

给定一个 $n$ 个点 $m$ 条边的无向图，任意两个点间至多有一条边，每条边有颜色 $c_i$，第 $x$ 次经过颜色 $c_i$ 的边需要支付 $x\times w_i$ 的钱。

对于每个 $i\in [2,n]$，求出从 $1$ 到 $i$ 走一条最短路，至少需要支付多少钱。

$1\leq n\leq 50$

题目解法：

首先求出以 $1$ 出发的最短路 DAG，由于这是分层 DAG，且只有 $50$ 个点，所以可以算出路径数量非常少，直接暴搜即可。

实际上感觉非常不好想。

时间复杂度大约为 $O(3^{\frac{n}{3}})$。

代码

#include <bits/stdc++.h>
using namespace std;
const int MAXN=60;
int n,m,x,y,z,w[MAXN*MAXN],dis[MAXN],ans[MAXN],cnt[MAXN*MAXN],c[MAXN][MAXN];
vector <int> v[MAXN],v2[MAXN];
queue <int> q;
void dfs (int x,int cs) {
	ans[x]=min(ans[x],cs);
	int len=v2[x].size();
	for (int i=0;i<len;i++) {
		int tmp=c[x][v2[x][i]];
		dfs(v2[x][i],cs+w[tmp]*(++cnt[tmp]));
		cnt[tmp]--;
	}
	return;
}
int main () {
	scanf("%d%d",&n,&m);
	for (int i=1;i<=m;i++) {scanf("%d",&w[i]);}
	for (int i=1;i<=m;i++) {
		scanf("%d%d%d",&x,&y,&z);
		c[x][y]=c[y][x]=z;
		v[x].push_back(y),v[y].push_back(x);
	}
	memset(dis,0x3f,sizeof(dis));
	memset(ans,0x3f,sizeof(ans));
	q.push(1);
	dis[1]=0;
	while (q.size()) {
		int a=q.front();
		q.pop();
		int len=v[a].size();
		for (int i=0;i<len;i++) {
			if (dis[v[a][i]]==0x3f3f3f3f) {
				dis[v[a][i]]=dis[a]+1;
				q.push(v[a][i]);
			}
		}
	}
	for (int i=1;i<=n;i++) {
		for (int j=1;j<=n;j++) {
			if (c[i][j]&&dis[j]==dis[i]+1) {
				v2[i].push_back(j);
			}
		}
	}
	dfs(1,0);
	for (int i=2;i<=n;i++) {printf("%d\n",ans[i]);}
	return 0;
}

---

*L. Wiring Engineering

难度：$\bigstar\bigstar\bigstar$