前言： 点此 返回 GJ Round 目录
Round 8 (10.5)
A
给定 \(n\) 个区间，每个区间 \([l_i,r_i]\)，最大化选取区间对数，使得每对区间 \([l_i,r_i],[l_j,r_j]\) 满足 \([l_i,r_i] \cap [l_j,r_j] =\varnothing\)
先按 \(l_i\) 从小到大排序，再按 \(r_i\) 从小到大排序
考虑贪心，维护两个小根堆，一个是已匹配的，一个是未匹配的
能匹配的就匹配（废话），不能匹配的从已匹配的中找一个小一点 \(r_j\) 来匹配就好
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^{*},B \in \mathbb N^{*}\)
简单数学题
暴力肯定会挂，考虑变形（柿子）式子
利用求根公式可得：\(x=B \pm \sqrt{B^2-C}\)
\(x \in \mathbb Z \Leftrightarrow \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 \leq x,y \leq n,|x-y|=1\) 当且仅当 \(a_x \neq x\) 且 \(a_y \neq y\)
你的目标是能否用不超过 \(m\) 步将排列 \(a\) 重排至一一对应，即 \(\forall i,a_i=i\)
如果有解，输出
YES，并构造出一种交换操作的方案，如果无解，输出NO特别地，当 \(m=-1\) 时只需要判断是否有解，不用输出构造方案
考虑归纳，因为 \(a_i=i\) 会变成不动点，所以在交换的过程中可能需要错排，而错排是有解的
C
很好的一道数据结构（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) \gets c(x)-1\)，数据保证任意时刻任意 \(c(x) \geq 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^{*}\)
简单数论分块，过
B
形式化且简化题意：定义 \(Fib\) 为斐波那契数列，其中：
\[Fib_i= \begin{cases} 1 &\text{if}(i=1\ \text{or}\ i=2) \\ Fib_{i-2}+Fib_{i-1} &\text{if}(i \geq 3) \end{cases} \]求 \(ax+by=c\) 非负整数对 \((x,y)\) 的个数，其中 \(a \in [0,N] \cap \mathbb Z,y \in [0,M] \cap \mathbb Z,x=Fib_{2k+1},y=Fib_{2k+2},k \in \mathbb{N}\)
（至于为啥是形式化题意是因为原题面又长又啰嗦）
确实有点难推出结论
扩展欧几里得算法(exgcd)即可
用归纳法证明出 \(-Fib_iFib_{i-1}+Fib_{i+1}Fib_{i-2}=1\) 省去 exgcd 的 \(\log\)，笑死，笔者觉得不如观察输出对应的 \((x,y)\) 得出结论简单
C
先跑一次 bfs 建图，然后跑 Kruskal 最小生成树得到重构树，最后在树上跳倍增 LCA 求答案即可
（思路与 洛谷 P1967 [NOIP2013 提高组] 货车运输 相似，就多了个 bfs 建图个过程）
D
洛谷 P7363 [eJOI2020 Day2] Dots and Boxes
咕咕咕
Round 11 (10.10)
谴责 GJ 今天一开始只放一道题，名字叫做 \(5\) 道题
A
简单结论题，\(a_1<a_n\) 就符合了，过
然而事实上笔者一开始还用了栈来贪心，真是令人唏嘘
时间复杂度 \(\mathcal O(Tn)\)，瓶颈在于输入
B
将一棵 \(n\) 个点的树通过切割任意条边，使得其划分成若干个大小相同的连通块，求方案数
普通树论题，但是不知道这个结论：划分成大小为 \(k\) 的连通块，当且仅当树上有 \(n/k\) 个点的 \(size\) 是 \(k\) 的倍数
C
有 \(n\) 种代币，每种面值为 \(a_i\)。每次小明会给每个顾客依次发放任意多次任意一种代币（可以不发）。两个发代币的方案不同当且仅当给两个顾客发放代币的次数不同或发放了不同种的代币，求有多少种发放代币的方案使得发放的总面值小于等于 \(K\)
思路有点巧妙，暴力是 dp，发现每个物品的价值都很小，考虑大小约为 \(101 \times 101\) 矩阵快速幂加快递推
构造矩阵类似如下：
\[\underbrace{ \begin{bmatrix} 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 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots \\ 0 & 0 & 0 & \dots & 1 & c_n & 0 \\ 0 & 0 & 0 & \dots & 0 & 0 & 1 \\ \end{bmatrix}}_{101 \times 101} \]时间复杂度 \(\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 \neq v\)），最大化 \((w_v-w_u)\)
傻波一小明就会做亏本买卖是吧
考虑拓扑排序 + dp，另开一个数组 \(mi_u\) 表示到达 \(u\) 点前所能遇到的最小点权，那么答案即为 \(\max_{u \subseteq G}(w_u-mi_u)\)，时间复杂度 \(\mathcal O(n+m)\)
B
给定 \(n+1\) 行格子，第 \(i\) 行有 \(a_i\) 个格子，保证 \(\forall i,j \in [1,n) \cap \mathbb Z\)，都有 \(a_i \geq a_{i+1}\)，最开始只有左上角为 \(1\)，其余为 \(0\)
每次可以选择一个格子 \((i,j)\)，使得 \(v_{i,j} \gets v_{i,j}-1,v_{i+1,j} \gets v_{i+1,j} + 1,v_{i,j+1} \gets 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
有一棵 \(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
模拟赛上 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 \degree\) 八个方向之一的排列
构造题
构造每一行形如 $\underline{ryxy} \dots \underline{ryxy} $、大小为 \(40 \times 40\) 的矩阵就好了再把最后一列也这样搞，刚好是 \(2223\) 个，比法定最大 \(n\) 还多 \(1\) 个，即
\[\underbrace{\begin{matrix} \color{blue}r & \color{blue}y & \color{blue}x & \color{blue}y & \dots & r & y & x & \color{red}r \\ \color{green}r & \color{green}y & \color{green}x & \color{green}y & \dots & r & y & x & \color{red}y \\ \color{blue}r & \color{blue}y & \color{blue}x & \color{blue}y & \dots & r & y & x & \color{red}x \\ \color{green}r & \color{green}y & \color{green}x & \color{green}y & \dots & r & y & x & \color{red}y \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots & \vdots \\ r & y & x & y & \dots & r & y & x & \color{red}r \\ r & y & x & y & \dots & r & y & x & \color{red}y \\ r & y & x & y & \dots & r & y & x & \color{red}x \\ r & y & x & y & \dots & r & y & x & \color{red}y \\ \end{matrix}}_{40 \times 40} \]然后就交给随机化每次随机更改一个位置求贡献就好了
时间复杂度：\(\mathcal O(Tm^2)\)，其中 \(T=?,m=40\)，理论上 \(T ∝ \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
对排列 \(\lbrace s_n \rbrace\)，定义 \(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)\)，求有多少个满足要求的排列。
注：排列 \(\lbrace s_n \rbrace\) 指 \(1\) 到 \(n\) 的 \(n\) 个整数按照任意顺序排成一列后得到的序列，\(s_i\) 表示排在第个位置的数字。例如当 \(n=3\) 时表示长度为 \(3\) 的排列，共有 \(6\) 种可能，分别是：
\(\lbrace1,2,3\rbrace,\lbrace1,3,2\rbrace,\lbrace2,1,3\rbrace,\lbrace2,3,1\rbrace,\lbrace3,1,2\rbrace,\lbrace3,2,1\rbrace\)
咕咕咕
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 \gets \sum w - \sqrt{(x_u-x_v)^2+(y_u-y_v)^2}\)，那么两点间显然只会操作最多一次
进一步地，操作可以形成一棵树或是森林，且同一个连通块 \(\lvert V \rvert\) 内的最大值为 \(\frac{\sum_{u \in V} w_u - mst}{\lvert V \rvert }\)，其中 \(mst\) 为连通块 \(\lvert V \rvert\) 的最小生成树，上界易证
那么可以先状压求出每个连通块的点权，再 dp 即可
时间复杂度 \(\mathcal O(2^n (n^2+n \log n))\)，其中 \(\log n\) 为并查集复杂度
Round 15 (10.18)
又是绑包。。。
A
给定一个长度为 \(n\) 的序列 \(A\)，每次变化为 \(A_i \gets \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^\prime_1,\dots,t^\prime_{2m}\)，且知道 \(s_0\) 是包含一个小写字母的字符串。
给你打乱后的数组 \(t:t^\prime_1～t^\prime_{2m}\) 与最终基因序列 \(s_1\)，请求出初始基因序列 \(s_0\)。
题目保证初始基因序列 \(s_0\) 有解。
诈骗题，并且成功在赛时把我骗了
因为题目说保证有解且唯一，所以除了 \(s_0\) 会出现奇数次，其他会出现偶数次
所以直接输出出现奇数次的字符，开个桶计数即可
时间复杂度 \(O(\sum | S |)\)
C
给定一个正整数序列 \(a_1,a_2,\dots,a_n\)，其中给定 \(m\) 对关系：\(\operatorname{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]\)，你希望求出所有字串的 \(\operatorname{mex}\) 函数出现的次数，即对于 \(\forall i \in [0,n] \cap \mathbb Z\)，求出 \(\operatorname{mex}\lbrace a_l,a_{l+1},\dots,a_r \rbrace = i\) 的 \(l,r\) 的对数
咕咕咕
Round 16 (10.19)
Summary
GJ 设成了 IOI 赛制
标签：dots,2024.10,color,GJ,给定,序列,操作,Round From： https://www.cnblogs.com/lunjiahao/p/18530958/GJ_Round_2024_10