GJ Round (2024.10) Round 8~21

前言：

点此返回 GJ Round 目录

博客园可能食用更佳

Round 8 (10.5)

A

给定 $n$ 个区间，每个区间 $[l_i,r_i]$，最大化选取区间对数，使得每对区间互不相交，即 $\forall i,j\in [1,n]\cap \mathbb{Z},i\ne j$，都有 $[l_i,r_i]\cap [l_j,r_j]=\varnothing$

先按 $l_i$ 从小到大排序，再按 $r_i$ 从小到大排序

考虑贪心，维护两个小根堆，一个是已匹配的，一个是未匹配的

能匹配的就匹配（废话），不能匹配的从已匹配的中找一个小一点 $r_j$ 来匹配就好

时间复杂度 $\mathcal{O}(n\log n)$

B

你有一个从 $1$ 到 $n$ 的排列 $a_1,a_2,\dots ,a_n$、一个空的序列 $b$，和一个空的大根堆

你需要进行 $2\times n$ 次操作，每次操作有两种选择：

• 从堆中取出最大的数字，加入序列 $b$ 的末尾（仅当大根堆不为空）
• 从序列 $a$ 中最靠前的数加入堆中并从 $a$ 中删除

最终，你显然会得到一个从 $1$ 到 $n$ 的序列 $b_1,b_2,\dots ,b_n$

求总共能有多少种不同的序列 $b$ 可以生成，答案对 $8580287$ 取模

咕咕咕

C

定义平衡序列：一个 $01$ 序列是平衡序列当且仅当不存在一个子区间，其中 $01$ 的个数差的绝对值大于 $k$

计算由 $x$ 个 $0$，$y$ 个 $1$ 构成的平衡 $01$ 序列的个数，答案对 $998244353$ 取模

咕咕咕

D

有 $n$ 的 $01$ 变量组成的序列 $x$，我们称 $01$ 序列 $x$ 是美丽的当且仅当满足以下 $m$ 条限制：

每一条限制都可以表达为：形如 $u,v$ 不能同时是 $1$，即：

• $u=x_i$ 或 $u=\neg x_i$
• $v=x_j$ 或 $v=\neg x_j$

求满足美丽序列的前提下，这 $n$ 个变量的取值

咕咕咕

Round 9 (10.6)

A

求方程有整数解 $x^2-2Bx+C=0,(B,C)$ 的对数

其中，$C\in [L,R]\cap {\mathbb{N}}^{\ast },B\in {\mathbb{N}}^{\ast }$

简单数学题

暴力肯定会挂，考虑变形~~（柿子）~~式子

利用求根公式可得：$x=B\pm \sqrt{B^2-C}$

$x\in \mathbb{Z}\iff \sqrt{B^2-C}\in \mathbb{Z}$

即 $B^2-C$ 为完全平方数

那不妨可以将 $C$ 对于值域 $V$ 内所有的方案数都算出来，设 $B^2-C=A^2$，变形后为 $B^2-A^2=C$，枚举 $A,B$ 即可，注意剪枝，再弄个前缀和即可

B

给定一个从 $1$ 到 $n$ 的排列 $a_1,a_2,\dots ,a_n$

每次可以交换相邻的两个元素 $a_x,a_y,1\le x,y\le n,|x-y|=1$ 当且仅当 $a_x\ne x$ 且 $a_y\ne y$

你的目标是能否用不超过 $m$ 步将排列 $a$ 重排至一一对应，即 $\forall i,a_i=i$

如果有解，输出 YES，并构造出一种交换操作的方案，如果无解，输出 NO

特别地，当 $m=-1$ 时只需要判断是否有解，不用输出构造方案

考虑归纳，因为 $a_i=i$ 会变成不动点，所以在交换的过程中可能需要错排，而错排是有解的

C

洛谷 P6864 [RC-03] 记忆

很好的一道数据结构（DS）题

这题最重要是考虑到如何拆分序列以便于统计与更新答案

发现答案会与某些东西在每个操作都存在一定关系，那么可以试着上矩阵来维护，每次用线段树单点修改、区间查询即可

D

你是一个物流公司的调度员，你所在的城市有 $0,1,2,\dots ,x_{max}$ 这 $max+1$ 个配送点。

假设货物当前在配送点 $x$ ，你一次操作可以花费 $c(x)$ 的代价将其运送到 $\lfloor \frac{x}{2}\rfloor ,\lfloor \frac{x}{3}\rfloor ,\dots ,\lfloor \frac{x}{w}\rfloor$ 中的任意一个配送点，其中 $w$ 是给定常数。

初始时，$c(x)=d_0(x)$，其中 $d_0(x)$ 为 $x$ 的因子个数。你需要执行 $q$ 次询问或修改操作。

• 对于一次修改操作，给定正整数 $x$，令 $c(x)\leftarrow c(x)-1$，数据保证任意时刻任意 $c(x)\ge 0$。
• 对于一次询问操作，给定正整数 $x$，求将货物从配送点运送到配送点 $0$ 的最小代价。

真看不懂给的题解，咕咕咕

Round 10 (10.9)

A

求有多少个 $x\in [1,n]\cap \mathbb{Z}$，使得

$$B_1+\lfloor \frac{A_1}{x}\rfloor =B_2+\lfloor \frac{A_2}{x}\rfloor$$

其中，$B_1,B_2,A_1,A_2\in {\mathbb{N}}^{\ast }$

简单数论分块，过

B

形式化且简化题意：定义 $Fib$ 为斐波那契数列，其中：
$$Fi{b}_i=\{\begin{array}{ll}1& \text{if}(i=1\text{or}i=2)\\ Fi{b}_{i-2}+Fi{b}_{i-1}& \text{if}(i\ge 3)\end{array}$$
求 $ax+by=c$ 非负整数对 $(x,y)$ 的个数，其中 $a\in [0,N]\cap \mathbb{Z},y\in [0,M]\cap \mathbb{Z},x=Fi{b}_{2k+1},y=Fi{b}_{2k+2},k\in \mathbb{N}$

（至于为啥是形式化题意是因为原题面又长又啰嗦）

确实有点难推出结论

扩展欧几里得算法(exgcd)即可

用归纳法证明出 $-Fi{b}_{i}Fi{b}_{i-1}+Fi{b}_{i+1}Fi{b}_{i-2}=1$ 省去 exgcd 的 $\log$，笑死，笔者觉得不如观察输出对应的 $(x,y)$ 得出结论简单

C

AT_joisc2014_e 水筒

先跑一次 bfs 建图，然后跑 Kruskal 最小生成树得到重构树，最后在树上跳倍增 LCA 求答案即可

（思路与 洛谷 P1967 [NOIP2013 提高组] 货车运输 相似，就多了个 bfs 建图个过程）

D

洛谷 P7363 [eJOI2020 Day2] Dots and Boxes

咕咕咕

Round 11 (10.10)

谴责 GJ 今天一开始只放一道题，名字叫做 $5$ 道题

A

CF1375C Element Extermination

简单结论题，$a_1<a_n$ 就符合了，过

然而事实上笔者一开始还用了栈来贪心，真是令人唏嘘

时间复杂度 $\mathcal{O}(Tn)$，瓶颈在于输入

B

将一棵 $n$ 个点的树通过切割任意条边，使得其划分成若干个大小相同的连通块，求方案数

普通树论题，但是不知道这个结论：划分成大小为 $k$ 的连通块，当且仅当树上有 $n/k$ 个点的 $size$ 是 $k$ 的倍数

C

有 $n$ 种代币，每种面值为 $a_i$。每次小明会给每个顾客依次发放任意多次任意一种代币（可以不发）。两个发代币的方案不同当且仅当给两个顾客发放代币的次数不同或发放了不同种的代币，求有多少种发放代币的方案使得发放的总面值小于等于 $K$

思路有点巧妙，暴力是 dp，发现每个物品的价值都很小，考虑大小约为 $101\times 101$ 矩阵快速幂加快递推

构造矩阵类似如下：
$$\underset{101\times 101}{\underbrace{\left[\begin{array}{ccccccc}0& 0& 0& \dots & 0& c_1& 1\\ 1& 0& 0& \dots & 0& c_2& 0\\ 0& 1& 0& \dots & 0& c_3& 0\\ 0& 0& 1& \dots & 0& c_4& 0\\ ⋮& ⋮& ⋮& \ddots & ⋮& ⋮& ⋮\\ 0& 0& 0& \dots & 1& c_n& 0\\ 0& 0& 0& \dots & 0& 0& 1\end{array}\right]}}$$

时间复杂度 $\mathcal{O}(V^2\log k)$，其中 $V^2$ 为矩阵大小

D

车站的候车室是一个二维平面，为了防疫，候车室中放置了 $n$ 个竖直挡板，第 $i$ 个挡板的端点为 $(x_i,a_i)$ 与 $(x_i,b_i)$，挡板互不相交。

每个人可以选一个位置 $(x,y)$ 候车（人的坐标可以是小数）。人们可能会随意地左右移动（改变坐标），但都不会穿过挡板。

小明从工作人员那了解到车站可能随时撤走一个挡板。人们不希望候车的过程中自己前方出现了其他人。小明想知道最多能有多少人同时在候车室，使得无论哪一个挡板被撤走，都不会有两个人能够移动到同 $x$ 一坐标上。

咕咕咕

E

设 $G(n)={\prod }_{i=1}^n(2i-1)$，给定 $n,m,x$，求：

$$\sum _{i=0}^n\sum _{j=0}^{m}G(i\oplus j\oplus x)$$

其中，$\oplus$ 是二进制按位异或，特别地，$G(0)=0$，答案对 $2^{32}$ 取模

咕咕咕

Round 12 (10.11)

A

简化题意：给定一个 $n$ 个点，$m$ 条边的有向无环图 DAG，点 $u$ 的点权为 $w_u$，选择任意一点为起点的路径上，先后选择两点 $u,v$（先到达 $u$ 再到达 $v$ 且 $u\ne v$），最大化 $(w_v-w_u)$

傻波一小明就会做亏本买卖是吧

考虑拓扑排序 + dp，另开一个数组 $m{i}_u$ 表示到达 $u$ 点前所能遇到的最小点权，那么答案即为 ${\max }_{u\subseteq G}(w_u-m{i}_u)$，时间复杂度 $\mathcal{O}(n+m)$

B

给定 $n+1$ 行格子，第 $i$ 行有 $a_i$ 个格子，保证 $\forall i,j\in [1,n)\cap \mathbb{Z}$，都有 $a_i\ge a_{i+1}$，最开始只有左上角为 $1$，其余为 $0$

每次可以选择一个格子 $(i,j)$，使得 $v_{i,j}\leftarrow v_{i,j}-1,v_{i+1,j}\leftarrow v_{i+1,j}+1,v_{i,j+1}\leftarrow v_{i,j+1}+1$，最小化花费次数使得所有格子（仅在界限内的）都变成 $0$，答案对 $10^9+7$ 取模

打表找规律题，与杨辉三角挂钩

求的就是每一行前 $a_i+1$ 个数的和，即第 $a_i$ 列的值

答案为 $ \sum_{i=1}^{n+1} {i+a_i-1 \choose i} $

C

AT_joisc2017_c 手持ち花火 (Sparklers)

所有人都向 $k$ 号跑最优，考虑时光倒流，二分，check 里贪心，后面不会，咕咕咕

D

CF526G Spiders Evil Plan

有一棵 $n$ 个点的树，带有边权。现有 $m$ 个询问如下：在树上选取 $k_i$ 条路径（树上任意两点的连接通路视为一条路径），其中至少要有一条路径覆盖到点 $a_i$，问所有被路径覆盖的边权的和最大是多少。注意重复覆盖的边只会计算一次。

nmd CF *3300

树上问题，不容易发现答案包含直径某一端点，长链剖分，后面不会，咕咕咕

Round 13 (10.14)

A

你作为一名寻宝者，来到了一个古老而神奇的城堡。城堡由多个房间组成，房间之间由墙壁隔开，从一个房间到另一个房间唯一的方法就是任意门传送。

城堡的地图可以由一个 $n$ 行 $m$ 列的网格图表示，每个格子可能是空间区域（用 $1$ 表示）或墙壁区域（用 $0$ 表示）。任意两个共享一边的空间区域被认为属于同一个房间。

你可以由一个空间区域 $(x_1,y_1)$ 前往另一个空间区域 $(x_2,y_2)$。

• 操作 $1$ - 步行：如果 $(x_1,y_1)$ 和 $(x_2,y_2)$ 属于同一个房间，那么你可以花费 $0$ 体力直接从 $(x_1,y_1)$ 走到 $(x_2,y_2)$

• 操作 $2$ - 任意门传送：如果 $(x_1,y_1)$ 和 $(x_2,y_2)$ 不属于同一个房间，那么你可以花费 $|x_1-x_2|+|y_1-y_2|$ 的体力从 $(x_1,y_1)$ 传送至 $(x_2,y_2)$

注意，如果 $(x_1,y_1)$ 和 $(x_2,y_2)$ 属于同一个房间，你只能选择步行前往，不能通过传送前往。

现在，你计划从位置 $(x_s,y_s)$ 前往位置 $(x_t,y_t)$，你可以进行任意多次步行和任意门传送。你可以重复经过同一个房间、也可以重复经过同一个空间区域。

为了更好的体验任意门的奇妙感觉，你希望使用传送的次数尽可能多。同时，你所消耗的体力值不能超过直接传送体力值：定义直接传送体力值为至多经过一次传送到达 $(x_t,y_t)$ 的最小体力值消耗。

你想知道，从 $(x_s,y_s)$ 前往任意一个空间区域，在所消耗的体力值不超过直接传送体力值的前提下，最多能够使用多少次传送？

难绷，上来就搞神秘 bfs 题，不会，咕咕咕

B

CF1310E Strange Function

模拟赛上 CF *2900 dp 也是只有 GJ 敢这么干的

（题外话：赛时 puts("1"); 有 $28$ pts 真不错「伏笔」）

考虑分类讨论

• $k=1$ 时，将 $n$ 个元素划分，上个背包就好

• $k=2$ 时，对最终序列从大到小排序，差分再上背包就好

• $k>2$ 时，因为答案已经不多了，所以直接搜索剪枝就过了（这就是为啥能总司令了~）

C

请构造一个由 $r,y,x$ 组成的大小不超过 $40\times 40$ 的矩阵，使得其中恰好有 $n$ 个连续的字符串 $ryx$，连续即同一行、同一列或 $45°$ 八个方向之一的排列

构造题

构造每一行形如 $\underline{ryxy} \dots \underline{ryxy} $、大小为 $40\times 40$ 的矩阵就好了再把最后一列也这样搞，刚好是 $2223$ 个，比法定最大 $n$ 还多 $1$ 个，即

$$\underset{40\times 40}{\underbrace{\begin{array}{ccccccccc}r& y& x& y& \dots & r& y& x& r\\ r& y& x& y& \dots & r& y& x& y\\ r& y& x& y& \dots & r& y& x& x\\ r& y& x& y& \dots & r& y& x& y\\ ⋮& ⋮& ⋮& ⋮& \ddots & ⋮& ⋮& ⋮& ⋮\\ r& y& x& y& \dots & r& y& x& r\\ r& y& x& y& \dots & r& y& x& y\\ r& y& x& y& \dots & r& y& x& x\\ r& y& x& y& \dots & r& y& x& y\end{array}}}$$

然后就交给随机化每次随机更改一个位置求贡献就好了

时间复杂度：$\mathcal{O}(T{m}^2)$，其中 $T=?,m=40$，理论上 $T\propto \frac{1}{n}$

#define pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
#define R 1
#define Y 2
#define X 3
using namespace std;
const int N=45;
const int dx[8]={-1,1,0,0,-1,1,-1,1};
const int dy[8]={0,0,-1,1,-1,1,1,-1};
int n,a[N][N],b[N][N];
int query()
{
	int res=0;
	for(int i=1;i<=40;i++)
		for(int j=1;j<=40;j++)
			for(int k=0;k<=6;k+=2)
			{
				if(a[i][j]!=Y) break;
				int A=a[i+dx[k]][j+dy[k]];
				int B=a[i+dx[k+1]][j+dy[k+1]];
				if(A==R&&B==X) res++;
				if(A==X&&B==R) res++;
			}
	return res;
}
mt19937 rd(time(NULL));
int rnd(int l,int r)
{
	return rd()%(r-l+1)+l;
}
void init()
{
	for(int i=1;i<=40;i++)
		for(int j=1;j<=37;j+=4)
			a[i][j]=R,a[i][j+1]=Y,a[i][j+2]=X,a[i][j+3]=Y;
	for(int i=1;i<=37;i+=4)
		a[i][40]=R,a[i+1][40]=Y,a[i+2][40]=X,a[i+3][40]=Y;
}
int main()
{
	scanf("%d",&n);
	init();
	memcpy(b,a,sizeof(a));
	printf("40 40\n");
	while(query()>n)
	{
		int x=rnd(1,40),y=rnd(1,40);
		a[x][y]=X;
		if(query()<n) a[x][y]=b[x][y];
	}
	for(int i=1;i<=40;i++)
	{
		for(int j=1;j<=40;j++)	
			printf("%c",a[i][j]==R?'r':a[i][j]==Y?'y':'x');
		printf("\n");
	}
	return 0;
}

D

对排列 { s n } \lbrace s_n \rbrace {sn​}，定义 $g(k,i)=\min (s_i,s_{i+1},\dots ,s_{i+k-1}),G(k)={\max }_{i=1}^{n-k+1}g(k,i)$

现给出 $G(1),G(2),\dots ,G(n)$，求有多少个满足要求的排列。

注：排列 { s n } \lbrace s_n \rbrace {sn​} 指 $1$ 到 $n$ 的 $n$ 个整数按照任意顺序排成一列后得到的序列，$s_i$ 表示排在第个位置的数字。例如当 $n=3$ 时表示长度为 $3$ 的排列，共有 $6$ 种可能，分别是：

{ 1 , 2 , 3 } , { 1 , 3 , 2 } , { 2 , 1 , 3 } , { 2 , 3 , 1 } , { 3 , 1 , 2 } , { 3 , 2 , 1 } \lbrace1,2,3\rbrace,\lbrace1,3,2\rbrace,\lbrace2,1,3\rbrace,\lbrace2,3,1\rbrace,\lbrace3,1,2\rbrace,\lbrace3,2,1\rbrace {1,2,3},{1,3,2},{2,1,3},{2,3,1},{3,1,2},{3,2,1}

咕咕咕

Round 14 (10.17)

我生活在一个绑包的世界里

谴责 GJ 不通知有模拟赛，$-1.5h$ 打模拟赛时间

A

给定一个字符串，每次可以将相邻两位 $a,b$ 相加再放回去，如果相加是两位数那么放回去还是分成两位，求操作次数最大值

入机题，模拟即可，或者直接得出答案 $ans=\lfloor \frac{(\sum S_i)-1}{9}\rfloor +|S|-1$

B

给定一个 $n\times m$ 的网格，点坐标为 $(x,y)$，距离为 $1$ 的两个点间有连边，求问是否能找到一个生成树，其中两点间的最远距离为 $t$

不仅 $200$ 个点还绑包？

构造题，可参考 AT_abc358_f Easiest Maze，但不是完全一样，还是有点差异的

上下界还是有一定难度想到，毕竟赛后才知道那个 $2\mid n,2\mid m$ 会使下界 $+1$

上界可以考虑直接螺转，下界可以考虑弄一些竖线，然后横着来一刀就差不多了

C

求逻辑表达式的值，其中运算符只有 & | ^ #，# 代表被抹去的运算符，数字只有 0 1 ?，? 代表被抹去的数字，求最终有多少种方案使得表达式的值为 $1$，答案对 $998244353$ 取模

甚至觉得比 [CSP-J 2022] 逻辑表达式 那题会简单一点，根本不用考虑优先级，全部运算似乎都会用一对 () 包着

开两个栈，一个记 $0$ 和 $1$ 的方案数，另一个记运算符，每遇到一个 ) 就计算一次贡献即可

做完了，时间复杂度 $\mathcal{O}(n)$

可以不用像题解那样建表达式树

D

在二维平面上有 $n$ 个点，第 $i$ 个点 $(x_i,y_i)$ 有权值 $w_i$。

可以进行若干次这样的操作：选择两个点 $u,v$，将 $u$ 的权值一部分 $\Delta w$ 加给 $v$，但是要承受 $d=\sqrt{(x_u-x_v{)}^2+(y_u-y_v{)}^2}$ 的损失，即两点间的欧几里得距离。也就是 $w_u-=\Delta w,w_v+=\max (0,\Delta w-d)$。

现在你希望所有点中最小的权值的最大，并求出该值。

两点间每操作一次，显然全局点权总和会减少，即 $\sum w\leftarrow \sum w-\sqrt{(x_u-x_v{)}^2+(y_u-y_v{)}^2}$，那么两点间显然只会操作最多一次

进一步地，操作可以形成一棵树或是森林，且同一个连通块 $|V|$ 内的最大值为 $\frac{{\sum }_{u\in V}{w}_u-mst}{|V|}$，其中 $mst$ 为连通块 $|V|$ 的最小生成树，上界易证

那么可以先状压求出每个连通块的点权，再 dp 即可

时间复杂度 $\mathcal{O}(2^n(n^2+n\log n))$，其中 $\log n$ 为并查集复杂度

Round 15 (10.18)

又是绑包。。。

A

给定一个长度为 $n$ 的序列 $A$，每次变化为 $A_i\leftarrow \lceil \frac{A_i}{2}\rceil +k$，其中 $k$ 为定值，多组询问，每次询问 $m$ 次变化之后 ${\sum }_{i=1}^n{A}_i$ 的值

诈骗题，经过 $\mathcal{O}(\log k)$ 次操作之后每个数变为 $2k$ 或 $2k+1$

暴力枚举前 $50$ 次总和即可，$m>50$ 的基本都可以看做 $m=50$

B

md 不会简化题意

生物学院的一组科研人员正在观察一种特殊基因的突变。这种基因用仅包含小写字母的序列来表示。

每天，基因序列中的一个非空连续子序列 $q$，都会发生突变被替换成非空序列 $q^{\prime }$。

科研人员观察了 $m$ 天，记录了 $2m$ 个数据，形成数组 $t$。其中，$t_{2i-1}$ 与 $t_{2i}$ 表示第 $i$ 天里，基因的连纹子序列 $t_{2i-1}$ 突变为了序列 $t_{2i}$。

但是，由于某种意外，数组t被打乱了。科研人员们只有被打乱后的数组 $t_1^{\prime },\dots ,t_{2m}^{\prime }$，且知道 $s_0$ 是包含一个小写字母的字符串。

给你打乱后的数组 $t:t_1^{\prime }～t_{2m}^{\prime }$ 与最终基因序列 $s_1$，请求出初始基因序列 $s_0$。

题目保证初始基因序列 $s_0$ 有解。

诈骗题，并且成功在赛时把我骗了

因为题目说保证有解且唯一，所以除了 $s_0$ 会出现奇数次，其他会出现偶数次

所以直接输出出现奇数次的字符，开个桶计数即可

时间复杂度 $O(\sum |S|)$

C

给定一个正整数序列 $a_1,a_2,\dots ,a_n$，其中给定 $m$ 对关系：$\mathrm{lcm}(a_{x_i},a_{y_i})=b_i$，即 $a_{x_i}$ 和 $a_{y_i}$ 的最小公倍数为 $b_i$，求原序列的所有可能性，答案对 $10^9+7$ 取模

咕咕咕

D

给定一个整数序列 $a_1,a_2,\dots ,a_n$，保证 $\forall i\in [1,n]\cap \mathbb{Z}$，都有 $a_i\in [0,n]$，你希望求出所有字串的 $\mathrm{mex}$ 函数出现的次数，即对于 $\forall i\in [0,n]\cap \mathbb{Z}$，求出 mex ⁡ { a l , a l + 1 , … , a r } = i \operatorname{mex}\lbrace a_l,a_{l+1},\dots,a_r \rbrace = i mex{al​,al+1​,…,ar​}=i 的 $l,r$ 的对数

咕咕咕

Round 16 (10.19)

Summary

GJ 设成了 IOI 赛制 😃

真的没意思，没到两个小时就 AC 前三题了

前面 $3$ 题比较简单，甚至 $T3$ 我都做过原了。。。

$T4$ 没看，puts("0"); 总司令 $15$ 分走了，然后就去补题了

赛时 $100+100+100+15=315$，打得最爽也是最高分的一集

A

AT_abc103_c Modulo Summation

入机数学题

显然对于每一个 $b_i$ 取模，必有一个数 $x$ 使得 $\forall i\in [1,n]\cap \mathbb{Z},x\mathrm{mod}{b}_i=b_i-1$

那么答案就为 $ans=\sum (b_i-1)$

B

洛谷 P3106 [USACO14OPEN] Dueling GPSs S

考虑反向建边，从 $n$ 开始跑三次 Dijkstra做完了

C

CF920F SUM and REPLACE

线段树板题

考虑先用线性筛 $\mathcal{O}(N)$ 预处理 $d(i)$，然后每次暴力修改 $a_i\leftarrow d(a_i)$

线段树再记个区间最大值 $maxl$，显然当 $maxl\le 2$ 时就不用再往下递归了

应该是要势能分析的，但是笔者不会，考虑到一个数被修改很少次就会变成 $1$ 或 $2$，每个数最多会被修改 $\mathcal{O}(\log n)$ 次

所以时间复杂度 $O(n\log n)$

同类型题目推荐：

• CF438D The Child and Sequence
• 洛谷 P4145 上帝造题的七分钟 2 / 花神游历各国

D

有一个 $N$ 个点的无向图，你现在要从这个图中选出一条游行路线，具体就是选择一个点作为开始点，走 $5$ 条连续的边，这 $5$ 条边不能有重复的边，但可以经过相同的点。问有多少种不同的取法。

这个图的边是根据如下伪代码产生的：

给出参数：$seed,threshold$，和数组 $toggl{e}_{\mathrm{0..}L-1}$。

state seed

for x = 0 .. N-1:
	for y = x+l .. N-1:
		state =(state * 1103515245 +12345) modulo 2^31
		if state threshold:
			add edge x-y
L= length(toggle)/2
for i in 0.. L-1:
	x = toggle[2*i] 
	y = toggle[2*i+1]
	if we have the edge x-y: 
		remove edge x-y
	else:
		add edge x-y 

咕咕咕

Round 17 (10.21)

题头：本次测试要用文件读入输出！

然而，事实上是，$4$ 题都不用文件读入输出……

A

有两个长度为 $n$ 的序列 $a,b$，每次可让 $a_i\leftarrow a_i+1$，代价为 $b_i$，求最小代价使得 $a$ 序列中所有的元素互不相等

贪心，按 $a_i$ 从小到大排序，考虑使用大根堆维护修改价值，然后似乎就没了（）

时间复杂度 $\mathcal{O}(n\log n)$

B

定义最小生成树的权值为其所有边权按位或得到的值

$n$ 个点，$m$ 条边，$Q$ 次单独操作询问，互不影响，每次加入一条 $(u,v)$ 权值为 $0$ 的边求新的答案，即每次在原图加边后询问

咕咕咕

C

在一个充满学术氛围的小镇上，有一家图书馆，以其庞大的藏书量和高效的索引系统而闻名。图书馆的索引系统基于一系列索引卡片，每张卡片代表一本书，其上记录了书籍的标题和与之相关的数值。

为了优化检索过程，图书馆引入了一种新的索引机制，其中涉及到对字符串的前缀操作。在这个机制中，前缀指的是字符串从开头开始的一部分，可以是整个字符串。例如，对于字符串 $S=\text{example}$，其前缀 $S[1:3]$ 就是 $\text{exa}$。

初始有 $n$ 本书，第 $i$ 本书的标题是 $S_i$，初始其数值 $a_i=0$。

图书馆管理员现在需要处理来自读者的请求，这些请求分为三种类型（假设执行这次请求前的书籍数量是 $M$):

• 1 i K x：对于每个 $1\le j\le M$，如果 $S_j[1:K]=S_i[1:K]$，则需要为这些书籍 $j$ 索引卡片上的数值 $a_j$ 增加一个特定的量 $x$。

• 2 i K T：加入一本编号为 $M+1$，标题为 $S_{M+1}=S[1:K]+T$ 的书，其索引卡片上的数值为$0$，之后 $M$ 增加 $1$。

• 3 i：查询第 $i$ 本书的索引卡片上的数值 $a_i$。

你需要编写一个程序来响应这些查询，确保索引系统既准确又高效。

发现该题没有强制在线，考虑离线将所有字符串建在 Trie 树上，用数据结构维护操作即可，适当用倍增加速递归

其实区间修改单点查询可以使用树状数组，但是笔者懒干脆就打了线段树，也就码量和常数大了点

D

在一次聚会上，你被邀请参加一个有趣的数字游戏。游戏的规则是这样的：你手中有一串数字卡片，每张卡片上都写着一个数字。你的任务是通过一系列简单的操作，使得存在两张卡片上的数字相乘后，结果是一个完全平方数。

你可以进行的操作有两种：

1. 将某张卡片上的数字乘以一个质数。

2. 如果某张卡片上的数字能被某个质数整除，你可以将这个数字除以这个质数。

现在，你面前有一串数字卡片，上面写着 $a_1,a_2,\dots ,a_n$。你的朋友提出了 $q$ 次挑战，他们想知道在不同的数字卡片组合中，你需要进行多少次操作才能达到目标。

每个挑战都以两个参数 $l_i$ 和 $r_i$ 来定义，表示从 $a_{l_i}$ 到 $a_{r_i}$ 的一系列卡片。你需要告诉他们，对于每个挑战，最少需要进行多少次操作。

形式化题意：

给你一个长度为 $n$ 的序列 $a$，定义 $P$ 为任意质数，共 $Q$ 次询问，每次询问一个区间 $[L,R]$，你可以进行以下操作：

1. $a_i\leftarrow a_i\times P$
2. $a_i\leftarrow \frac{a_i}{P},P\mid a_i$

求最小化操作次数，使得 $\exists i,j\in [L,R]\cap \mathbb{Z},a_i{a}_j=X^2,X\in \mathbb{N}$

咕咕咕

Round 18 (10.23)

Summary

我们都是冠军！（全员保龄了owo，原因是 GJ 并未告诉我们文件名是啥 😃）

还是 本次测试要用文件读入输出

看了眼下发大样例的名字，是 bag/profit/bing/array，但因为 GJ 搬题会大改所以没啥参考价值？

题目名为 魔法袋/数学作业/手牌收益/音乐变奏，经过机房的实验得出文件读入输出名分别为 maigc/homework/hand/music （不是 hand 是什么鬼）

合理怀疑考的是 OE(English Olympic)

A

小明是一个数学魔法师，他有一个神奇的魔法球，里面可以装很多魔法数，相等的数可以出现多次。一开始，魔法球中只有一个魔法数 $1$。小明要念一条包含 $n$ 个神奇数学音符的咒语，咒语上的音符有两种：

1.发生：小明念到发生音符时，球里会增加一个新的魔法数，其值为 $1$。

2.合并：小明念到合并音符时，可以任意选择球中的两个魔法数 $a$ 和 $b$，这两个数会在球中合并为一个新的魔法数 $a+b$，原来的两个数将被消耗。但是如果念到合并音符的时候球中魔法数的个数小于 $2$ 个，魔法球就会爆裂！小明的咒语长度固定为 $n$ 个音符，有些位置必须是发生音符，有些位置必须是合并音符，剩下的位置小明可以任选一种音符。

小明希望在不让魔法球爆裂的情况下，通过一系列数学操作，让球中留下的魔法数的平均值尽可能大。请你找出这个最大的平均值。

形式化并简化题意：

初始时你有一个分数 $\frac{S}{N}$，其中 $S=N=1$，你共有 $n$ 次操作，每次操作有三种操作：

• 操作一：$S\leftarrow S+1,N\leftarrow N+1$
• 操作二：$N\leftarrow N-1,N\ge 2$
• 操作三：可进行上述两种操作之一

注意你每次进行操作 $2$ 都要保证 $N\ge 2$，若无法保证，请输出 -1，最大化 $\frac{S}{N}$

显然发生音符（操作一）对答案的贡献要么不变，要么减小，那么需要尽可能最小化操作一的次数，将自由音符（操作三）尽可能转合并音符（操作二），在不爆裂的情况下尽可能合并

B

共有 $n$ 个学生 $m$ 个城市，第 $i$ 个学生要选择去 $a_i$ 和 $b_i$ 中的一个。若有奇数个人去同一个城市，那么就需要仆从随行。最小化需要的仆从数。

结论题，对于一个连通块，仆从所需要的数量等于这个连通块内的边数模二的值

显然，对于一个学生，选择其中一个点，那么点 $a_i$ 和 $b_i$ 的奇偶性变化只会有 $4$ 种情况：

$$\begin{gathered} (0,0)\to (1,1) \\ (1,1)\to (0,0) \\ (1,0)\to (0,1) \\ (0,1)\to (1,0) \end{gathered}$$

那么每次操作只会减少/增加两个 $1$，或者不变，那么自然花费最小为 $x\mathrm{mod}2$

考虑用并查集即可，时间复杂度 $\mathcal{O}(m+n\alpha (m))$，其中 $\alpha (m)$ 为反阿克曼函数

C

给定一个长度为 $n$ 的序列 $a$，求：

$$\sum _{1\le i<j<k\le n}(a_i\oplus a_j)\vee a_k$$

其中，$\oplus$ 是二进制按位异或，$\vee$ 是二进制按位或，答案对 $2^{64}$ 取模，$a_i$ 由随机数生成器产生

考虑拆位求贡献，那么显然可以统计 $0$ 的个数和 $1$ 的个数，然后随便搞搞就过了

时间复杂度 $\mathcal{O}(64n)$

D

你有一个长度为 $n$ 的序列 $a$，可以选择在序列上一段长度为 $m$ 的连续区间加上一个首项为 $c$，公差为 $d$ 的等差数列，最大化序列的第 $k$ 大

咕咕咕

Round 19 (10.24)

有点难

A

给定一个无向图，求本质不同的最小环的个数

感觉我这写的代码常数太大了不开 O3 T 飞了

显然可以用 bfs 求一下最小环的长度，然后这里我就跑了 $n$ 次 bfs 了

具体地，维护 $di{s}_y$ 为点 $x$ 到点 $y$ 的最短距离，当我们从 $u$ 结点第一次访问到 $v$ 结点时，更新其对应的 $dis$ 值，否则我们就可以找到一个长度为 $di{s}_u+di{s}_v+1$ 的环

然后就可以开始计数啦，结果这里我有用了 $n$ 次 bfs

记最小环的长度为 $L$，则：

1. 以环上任意一点为起点均会统计该环一次，答案故需要除以 $L$
2. 似乎有的写法当 $L$ 为奇数的时候会被统计成两个方向上的环，答案需要除以 $2$，（要看个人写法）

时间复杂度 $\mathcal{O}(n(n+m))$，总共跑了 $2n$ 次 $bfs$ 被题解的 $n$ 次 bfs 狠狠暴拉了

B

给定 $N,N_3,P$ 求满足 $((N^2+1)\mathrm{mod}a+b)\mathrm{mod}c=N_3$ 的三元组 $(a,b,c)$ 的方案数，其中 $1\le a,c\le P,0\le b\le P$，设方案数为 $Q$，则还需要按照字典序从小到大输出前 $\min (P,5\times 10^5)$ 个三元组

数学题

先把原题面的定义放出来便于记录

定义：
$$\begin{array}{rl}{N}_0& =N^2+1\\ N_1& =N_0\mathrm{mod}a\\ N_2& =N_1+b\\ N_3& =N_2\mathrm{mod}c\end{array}$$

考虑逆递推得到 $N_2$ 的值以及对应的 $c$，然后就可以得到所有 $N_1$ 的取值以及对应的 $a$

易得 $\lfloor N_2/c\rfloor \times c+N_3=N_2,{\sum }_{c=1}^P\lfloor P/c\rfloor =\mathcal{O}(P\lg P)$，那么就可以枚举 $c$ 的取值和 $\lfloor N_2/C\rfloor$ 的取值来得到 $N_2$，且只有 $\mathcal{O}(P\lg P)$ 种取值，然后可以使用二分或者前缀和求出 $b$ 的取值，故时间复杂度为 $\mathcal{O}(P\lg P)$

代码略

C

给定一个长度为 $n$ 的字符串 $S$，定义符合 $u$ 审美的字符串是恰好由两个不同的字母交替组成的字符串，给出 $Q$ 次询问，每次询问 $S$ 的子串 $S[l_i\dots r_i]$ 中，符合 $u$ 审美的最长子序列长度是多少，并输出字典序最小的子序列对应的两个组成的字符

咕咕咕

D

咕咕咕

Round 20 (10.25)

A

给定一个由 $01$ 组成的二维地图，求总共有多少个“星际螺旋结构”

一个 $k$ 层的“星际螺旋结构”$(k\ge 2)$，第 $1$ 层 $1$ 个，第 $2$ 层 $3$ 个……第 $k-1$ 行 $(2k-3)$ 个，第 $k$ 行 $1$ 个，求且居中对齐

小模拟题，不过需要稍微预处理下就好了

记 $L_{i,j}$ 表示 $a_{i,j}$ 这个天体能到达连续区间最左端的位置，$R_{i,j}$ 同理

时间复杂度 $\mathcal{O}(n^3)$

B

给定长度为 $n$ 的序列 $A$ 和长度为 $m$ 的序列 $B$，以及常数 $x$，求以下 Python 代码生成的序列 $L$ 中第 $k$ 小的数

def generate_list(A, B, x):
    n = len(A)
    m = len(B)
    L = []
    for i in range(min(n, m - x)):
        for j in range(i + x, m):
            L.append(A[i] * B[j])
return L

咕咕咕

C

对于长度为 $n$ 的排列 $A$，若 $\forall i\in [1,n]\cap \mathbb{Z},A_{A_i}=i$，则这个排列是符合审美的

求长度为 $k$ 的排列 $B$，求有多少个符合审美的长度为 $n$ 排列是 $B$ 的子序列

咕咕咕

D

有 $n$ 个敌人，第 $i$ 个敌人拥有 $h_i$ 的血量，当 $h_i\le 0$ 时，该敌人死亡，后面的敌人补前，最左边的敌人编号为 $1$

你有 $5$ 种操作：

• 消耗 $m_A$，对第一个敌人造成 $d_A$ 伤害
• 消耗 $m_B$，对第二个敌人造成 $d_B$ 伤害
• 消耗 $m_C$，对第三个敌人造成 $d_C$ 伤害
• 消耗 $m_D$，对第四个敌人造成 $d_D$ 伤害
• 消耗 $m_E$，对前四个敌人造成 $d_E$ 伤害

求消灭所有敌人的最小花费

咕咕咕

Round 21 (10.31)

致敬 GJ 的传奇 SPJ，使得 T2 交空代码文件读入输出即可过

A

给定 $n$ 个点 $(x_i,y_i)$，求两点间曼哈顿距离与欧几里得距离的比值的最大值

人话：求

$$\max \frac{|x_i-x_j|+|y_i-y_j|}{\sqrt{(x_i-x_j{)}^2+(y_i-y_j{)}^2}}$$

显然答案只有可能在 $[1,\sqrt{2}]$ 之间，取到 $\sqrt{2}$ 当且仅当斜率为 $\pm 1$ 时，再加上特殊性质可以启发我们将坐标轴顺时针 / 逆时针旋转 $45°$，然后将相邻点对求一下对答案的贡献即可，可以得证，一定满足一对点，它们按 $x$ 或 $y$ 排序时相邻的

时间复杂度 $\mathcal{O}(n\log n)$，瓶颈在于排序

B

AT_arc152_d Halftree

构造题，看原题去

C

CF1781F Bracket Insertion

CF *2700 dp，看原题去

D

给定一个长度为 $n$ 的序列 $a$，你有两种操作：

• 给定一个参数 $x\in [1,n]$，花费 $x$ 将 $a_1,a_2,\dots ,a_x$ 都减 $1$
• 给定一个参数 $x\in [1,n]$，花费 $x$ 将 $a_n,a_{n-1},\dots ,a_{n-x+1}$ 都减 $1$

求 $\forall i\in [1,n]\cap \mathbb{Z}$，都有 $a_i\le 0$ 的最小花费

咕咕咕