2025 FJCPC 复建 VP

按开题顺序写 (BCDEFGHIJKLA(D?))，(M) 送的不写

B

首先发现铜铁本质等价（铜铁的转换不影响 (val) ），所以考虑枚举最后金和银的数量 (gold, silver)，那么约束条件为：

[val=n-4g-sge p ]

[8g+4sle n ]

那么考虑剩余铁牌全合成同和全不合成情况，每合成一个铜牌那么总牌数减一，即 (g, s) 对 (iin[g+s+left lfloor frac{(n-8g-4s+1)}{2} right rfloor, g+s+(n-8g-4s)]) 的 (ans_{i}) 有 1 的贡献。

拆开下取整得 ([left lfloor frac{(n+1)}{2} right rfloor-3g-s, n-7g-3s])

我们枚举 (g) 时，需要加的区间 ([l, r]) 随着 (s) 的变化，左右端点分别为公差为 1/3 的等差数列。

将区间 +1 操作变为差分，那么对于某个 (g) 上述区间的贡献可以相当于一个等差数列下标组 +1，另一个等差数列下标组 -1，二阶差分数组可以解决。

关键代码：

	for(int i=0, x, s0; i<=n; ++i){ 		s0=min(n-4*i-p, (n-8*i)/4);if(s0<0) break; 		x=(n+1)/2-3*i;del[0][x-s0]++, del[0][x+1]--; 		x=n-7*i+1;del[1][x-3*s0]--, del[1][x+3]++; 	} 	for(int i=0; i<=n; ++i){ 		if(i) del[0][i]+=del[0][i-1]; 		if(i>2) del[1][i]+=del[1][i-3]; 		ans[i]=del[0][i]+del[1][i]; 	} 

C

贪心策略不好处理，考虑二分答案。，那么序列可视为 0/1 序列。

只有两个数是比较容易做贪心的，压缩 000 和 001 即可。

关键代码：

bool check(int v){ 	int top=0, c[2]={0, 0}; 	for(int i=1; i<=n; ++i){ 		bool x=a[i]>=v;//printf("%d", x); 		if(!top){t[++top]={1, x};continue;} 		if(t[top].nd==x){ 			++t[top].st; 			if((!t[top].nd)&&t[top].st==3) t[top].st=1; 		} 		else{  			t[++top]={1, x}; 			if(t[top].nd&&top>1&&t[top-1].st==2){ 				--top;t[top].st=1; 			} 		} 	} 	for(int i=1; i<=top; ++i) c[t[i].nd]+=t[i].st; 	return c[1]>=c[0]; } 

E

等价于 (min |sum (-1)^{i}a_{i}|)

操作相当于任选一段长度为偶数的区间使系数 ((-1)^i) 正负翻转

如果翻转 ([l, r]) 则 (ans=|sum_{n}-2sum_{r}+2sum_{l-1}|)，(sum_{i}) 是带系数的前缀和。

即找到距离 (2sum_{r}) 最近的 (sum_{n}+2sum_{l-1})，set 维护即可。

最后的答案 (ans'=frac{sum^{n}_{i=1} a_{n}-ans}{2})， 需要注意注意 (l, r) 奇偶性相反。

关键代码：

	for(int i=1; i<=n; ++i){ 		int op=i&1;ll p=-2LL*sum[i]; 		if(S[op^1].size()){ 			auto it=S[op^1].lower_bound(-p); 			if(it!=S[op^1].end()) t=min(t, (*it)+p); 		}S[op].insert(sum[n]+2LL*sum[i-1]); 		if(T[op^1].size()){ 			auto it=T[op^1].lower_bound(p); 			if(it!=T[op^1].end()) t=min(t, (*it)-p); 		}T[op].insert(-2LL*sum[i-1]-sum[n]); 	} 

F

考虑得到 (l_i, r_{i}) 为 (i) 号点左右能让它被肘飞的点（默认 (l_{i}=0, r_{i}=n+1)）

那么即数 ([L, R]) 中 (l_{i}<L, R<r_{i}) 的 (i) 的个数，

那么点 (i) 对 ([[l_{i}+1, i], [i, r_{i}-1]]) 的询问有贡献，视为矩形加，询问单点值，扫描线解决。

求 (l_{i}, r_i)： 按 (x_{i}) 关键字排逆序在线段树上依次插入 (i, y_{i})，查询 (l_{i}) 即找到 ([1, i]) 最右边 (y_x>y_{i}) 的部分并返回，(r_i) 同理，线段树二分即可。

关键代码：

int queryL(int k, int l, int r, int x){ 	if(l>x||Mx(x, tr[k])==x) return 0; 	if(l==r) return tr[k];int res=queryL(rs, mid+1, r, x); 	return res?res:queryL(ls, l, mid, x); } int queryR(int k, int l, int r, int x){ 	if(r<x||Mx(x, tr[k])==x) return n+1; 	if(l==r) return tr[k]?tr[k]:n+1;int res=queryR(ls, l, mid, x); 	return (res<=n)?res:queryR(rs, mid+1, r, x); } 

G

只会在一个单调不降段开头买入结尾卖出，等价于 (a_{i}>a_{i-1}) 的有 (a_{i}-a_{i-1}) 的贡献，前缀和即可。

H

假设最短路是 (d), 设 (d=kr+d')。

如果 (l<r) 则在最后一步必然可以使用 与 (d') 奇偶性相同的值在走到终点后反复横跳，(ans=k+1)。

那么 (l=r) 的情况也同理分奇偶考虑，偶数情况是简单的，只能考虑长度为偶数的最短路。奇数情况，两种奇偶性最短路都要考虑，并且如果消耗时间*步数与奇偶性不同还要额外 +1 。

关键代码：

	if(L<R){ 		p=min(dis[0][id(n, m)], dis[1][id(n, m)]); 		if(p!=INF) printf("%dn", (p+R-1)/R); 		else puts("-1"); 	}  	else if(L%2){//奇数 		int u=dis[0][id(n, m)], v=dis[1][id(n, m)]; 		if(u!=INF){u=(u+L-1)/L;if((u&1)==1) ++u;} 		if(v!=INF){v=(v+R-1)/R;if((v&1)==0) ++v;} 		if(min(u, v)==INF) puts("-1"); 		else printf("%dn", min(u, v)); 	} 	else{ 		p=dis[0][id(n, m)]; 		if(p!=INF) printf("%dn", (p+L-1)/L); 		else puts("-1"); 	} 

I

从特殊情况入手，全是割点无解，因为 (n) 至少需要两条出边连向同一个连通块，这连个出边的点就不嫩是割点。

一个非割点同理，构造链考虑，如果 (n-1) 是非割点则可以和 (n) 一起连到 (n-2)，否则无解。

度数的 (ge) 条件引导我们构造一连串的等于条件，容易想到 环 和 链中间 的点都满足度数为 (2)，且环上是非割点而链是割点，于是让 1 作为环和链的交点，(n) 作为链的另一头。

J

lowbit 二进制构造。

K

先待定 (b_1=0)，那么可以推算得 (b_{i}=x_{i}+c_ib_{1}, c_{i}=1/-1) ，根据深度以及 (b_{i}) 正负性简单分讨即可。

L

前缀子集 (min+max) 的众数

对于前缀 ([1, i])，一共有 (2^i-1) 种情况，其中最大值+最小值保底有 (2^{i-2}) 种，容易发现只有 (1, 2, 2,..., 2) 时才会实现反超。

A

题面一坨，可读性不如代码。。。

考虑 DAG 剖，每个结点维护一个 ds 二元组集合统计 ((mx, cnt))，转移时轻边直接暴力取出所有元素加入，重边则继承出点的 ds。ds 使用线段树，复杂度 (O(nlog ^2 n))。

参考代码

#include  #include  #include  #include  #include  #include  #include  #define vi vector #define pb push_back #define mp make_pair #define st first #define nd second using namespace std; typedef long long ll; typedef pair  Pii; const int INF=0x3f3f3f3f; const int cp=998244353; inline int mod(int x){return x+(x<0?cp:0)-(x>=cp?cp:0);} inline void plust(int &x, int y){x=mod(x+y);return ;} inline void minut(int &x, int y){x=mod(x-y);return ;} inline int read(){ 	char ch=getchar();int x=0, f=1; 	while(!isdigit(ch)){if(ch=='-') f=-1; ch=getchar();} 	while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();} 	return x*f; } inline void write(int x){     if(x<0) putchar('-'), x=-x;     if(x>9) write(x/10);     putchar(x%10+'0'); } inline int ksm(int a, int b=cp-2){ 	int ret=1; 	for(; b; b>>=1, a=1ll*a*a%cp) 		if(b&1) ret=1ll*ret*a%cp; 	return ret; } const int N=2e5+5; char s[N];int n; namespace SAM{ 	const int Nc=N<<1;//SAM 实际点数卡满 2n-1 	const int Mc=(N<<1)+N;//SAM 实际边数卡满 3n-4 	int ndc, lst, siz[Nc], c[Nc], out[Nc], in[Nc], dfn[Nc], bac[Nc]; 	ll f[Nc], g[Nc];vi dag[Nc], inv[Nc], G[Nc]; 	struct node{int fa, len, nxt[26];}sam[Nc]; 	int clear(int x){sam[x]=sam[0], siz[x]=0;return x;} 	void remake(){clear(ndc=lst=1), dfn[0]=0;} 	int insert(char c){ 		int cur=clear(++ndc), p=lst, cc=c-'a';siz[cur]=1; 		sam[cur].len=sam[lst].len+1; 		for(; p&&!sam[p].nxt[cc]; p=sam[p].fa) 			sam[p].nxt[cc]=cur; 		int q=sam[p].nxt[cc]; 		if(!q) sam[cur].fa=1; 		else if(sam[q].len==sam[p].len+1) sam[cur].fa=q; 		else{ 			int nex=clear(++ndc);sam[nex]=sam[q], sam[nex].len=sam[p].len+1; 			for(; p&&sam[p].nxt[cc]==q; p=sam[p].fa)  				sam[p].nxt[cc]=nex; 			sam[cur].fa=sam[q].fa=nex; 		} 		return lst=cur; 	} 	void dfs(int x){bac[dfn[x]=++dfn[0]]=x;for(auto v:dag[x]) if(!dfn[v]) dfs(v);} 	void dfs2(int x){for(auto v:G[x]) dfs2(v), siz[x]+=siz[v];} 	inline bool heavy(int u, int v){return (2ll*f[u]>f[v])&&(2ll*g[v]>g[u]);} 	#define ls(p) tr[p].lc 	#define rs(p) tr[p].rc 	#define C(p) tr[p].cnt 	#define S(p) tr[p].sum 	#define mid ((l+r)>>1) 	const int M=Nc*30; 	const int P=2e5; 	struct seg{int lc, rc;ll cnt, sum;}; 	int m, rt[Nc];seg tr[M]; 	vi bin; 	inline int newnd(){ 		int t=0;if(!bin.size()) t=++m; 		else{  			t=bin.back(), bin.pop_back(); 			if(ls(t)) bin.pb(ls(t)); 			if(rs(t)) bin.pb(rs(t)); 		} 		tr[t]=(seg){0, 0, 0, 0};return t; 	} 	void update(int &k, int l, int r, int u, ll c){ 		if(!c) return ; 		if(!k) k=newnd();if(l==r){C(k)+=c, S(k)+=c*mid;return ;} 		if(u<=mid) update(ls(k), l, mid, u, c);else update(rs(k), mid+1, r, u, c); 		C(k)=C(ls(k))+C(rs(k)), S(k)=S(ls(k))+S(rs(k)); 	} 	ll cover(int &k, int l, int r, int U){//查询且覆盖 		if(!k) return 0;if(l>=U) return 0; 		if(r Q;Q.push(f[1]=1);vi topo; 		while(!Q.empty()){ 			int x=Q.front();Q.pop();topo.pb(x); 			for(auto v:dag[x]){ 				f[v]+=f[x];--in[v]; 				if(!in[v]) Q.push(v); 			} 		} 		for(int i=ndc; i>=1; --i)  			if(!out[i]) Q.push(i), g[i]=1; 		while(!Q.empty()){ 			int x=Q.front();Q.pop(); 			for(auto v:inv[x]){ 				g[v]+=g[x];--out[v]; 				if(!out[v]) Q.push(v); 			} 		} 		ll ans=0;update(rt[1], 1, P, c[1], 1); 		for(auto x:topo){ 			int son=0;ll p=cover(rt[x], 1, P, c[x]);update(rt[x], 1, P, c[x], p); 			ans+=tr[rt[x]].sum*siz[x]; 			for(auto v:dag[x])  				if(!heavy(x, v)) copy(rt[v], rt[x], 1, P);else son=v; 			if(son) swap(rt[son], rt[x]), copy(rt[son], rt[x], 1, P); 		} 		printf("%lldn", ans);bin.clear(); 		for(int i=1; i<=ndc; ++i)  			dag[i].clear(), inv[i].clear(), G[i].clear(), 			f[i]=g[i]=in[i]=dfn[i]=bac[i]=out[i]=rt[i]=siz[i]=c[i]=0; 	} } void solve(){ 	scanf("%s", s+1);n=strlen(s+1);SAM :: init(); } signed main(){ 	for(int T=read(); T; --T) solve(); 	return 0; }