0717T1 patkice

题意

不是很久之前，在一个遥远的大陆上，住着三只橡皮鸭。在一个炎热的夏日，躺在沙滩上的鸭子们决定旅行到一座相邻的小岛(用一把老旧的黑色雨伞)。

鸭子们是经验丰富的海洋探险家，在旅行之前，他们会检查当前海洋的海图。在海图上，鸭子们目前居住的岛屿被字符o标记，鸭子们可以朝东(E)南(S)西(W)北(N)中的任意方向开始他们的旅途。

海洋中的洋流会像四个方向移动，在海图上，向东的洋流被标记为>，向西的洋流被标记为<，向北的洋流被标记为^，向南的洋流被标记为v。当鸭子们位于洋流中的某一个位置时，他们会移动到洋流所指向的下一个位置。这片海洋中的洋流比较特殊，它不会让鸭子们移动到海图之外的地方，同时，洋流也没有形成环路。

平静的海洋在海图中被标记为’.’。如果洋流带鸭子们到达了平静海域，或者时开始的岛屿，那么他们就无法继续他们的旅途了。他们想要到达的岛在图上被标记为’x’。

你的任务是帮鸭子们判断它们能否到达目的地。如果可以的话，他们需要选择哪一个方向。鉴于鸭子们并不喜欢海上漂泊的感觉，如果存在多个可以到达目的地的方向，你需要找到行动距离最短的方向。如果存在行动距离相同的方向，请按照方向的字典序输出字典序最小的方向。

Sol

简单题，根据题意bfs一下即可。

按照顺序加入队列，只用做一遍即可。

0719T1 原题（original)

题意

小\(\Delta\)出了一道他出过的原题。

小为了考验你 Pollard-Rho 能多快写出来，告诉你了一个正整数 \(n\)，让你对它分解质因数。

为了让你可以更好的检验你答案的正确性，他还告诉你了 \(\varphi(n)\)，也就 \(\le n\) 是的，与互质的正整数的个数。

Sol

当 \(n \le 10 ^ {14}\) 时，用一遍线性筛就能过。

我们先用线性筛把 \(\le 1e7\) 的质数先筛掉。

同时算出当前的 \(\varphi(n')\)。

对当前的情况进行分类讨论：

\(n'\) 为两个 \(\ge 1e7\) 质数之积。列出一元二次方程即可。
\(n'\) 为两个相同 \(\ge 1e7\) 质数之积，特判算出来即可。
\(n'\) 为一个质数，输出即可。

0807T1 骰子游戏

题意

给你两个正整数 \(n\) 和 \(k\)，你需要构造 \(6\) 个正立方体骰子，每个骰子的每个面上都写有一个整数，满足：

写在骰子每个面上的整数都在 \([0, 1e6]\) 范围内。
对于每个骰子，其六个面上写有的数字两两不同。
同时投出这 \(n\) 个筛子，所有骰子朝上面上写有数字的异或和都是 \(k\) 的倍数。

形式化地：构造 \(n \times 6\) 的矩阵，使得每行任意选一个数字的异或和为 \(k\) 的倍数。

Sol

构造题，考场上 15min 秒了。

freopen 写错喜提保龄。

随便手玩一下发现按位异或不太好保证倍数性质。

容易发现 \(k\) 的范围很小，只有 \(60\)。

由于 \(60\) 二进制只有 \(6\) 位，所以我们可以想到暴力将这 \(6\) 位当成一位来看。

那么答案显然为:

\(k\)
\(k \times (1 << 6)\)
\(k \times (1 << 6) + k\)
\(k \times (1 << 12)\)
\(k \times (1 << 12) + k\)
\(k \times (1 << 12) + k * (1 << 6)\)

0807T2 裁剪彩带

题意

你有一条长度为 \(n\) 的彩带，彩带的每个长度为 \(1\) 的区间都有一个颜色，从左到右的 \(i\) 长度位置的颜色为 \(c_i\)。

现在你要将彩带剪开，剪开后的一部分彩带的美丽值为这一部分所有颜色的 \(mex\)，一种剪彩带的方式的美丽度为剪开后每一部分的美丽值之和。

现在，你需要计算出美丽度最大的裁剪方案的美丽度是多少，并给出一种裁剪方案。

一个集合 \(S\) 的 \(mex\) 定义为最小的没有在 \(S\) 中出现的非负整数。

形式化地：给定一个长度为 \(n\) 的序列，分成任意段，使总和 \(mex\) 最大，并输出方案。

Sol

水dp，考场上45 \(min\) 秒了。

没算空间喜提保龄。

可以想到一个朴素的dp方程 \(f_{ij}\)：前 \(i\) 个数，最后一段长度为 \(j\) 的 \(mex\) 总和。

观察数据，发现 \(0 \le a_i \le 20\)。

那么说明 \(mex\) 不会超过 \(20\)。

可以想到 \(f_{ij}\) ：前 \(i\) 个数字，最后一段的 \(mex\) 为 \(j\) 的 \(mex\) 总和。

那么简单写 \(200\) 行的预处理，记录每个数字往前 \(j\) 个 \(mex\) 的下标即可。

时间复杂度为 \(O(n)\)，有一个 \(21\) 倍常数。

0807T3 挑战NPC

题意

定义有向图上的两个回路不交，当且仅当这两个回路不经过公共点或公共边。

给你 \(n\) 个点，\(m\) 条边的有向图，求出若干两两不交的简单回路的并，使得经过每个点恰好一次。或报告无解。

如果有解，输出任意一个即可。

Sol

解题思路

由于我们需要求出不相交的环，那么就必须要求每一个点的入度和出度都为 \(1\)。
这样我们有可以想到用网络流来解决。
我们让 \(S\to \{1\sim n\}\) 来代表每一个点的入度为 \(1\)，我们再新建一组点 \(\{n+1\sim n+n\}\to T\) 来代表流出的出度。
而中间的连边 \(u\to v\) 建为 \(u\to v+n\)，所有边的容量都为 \(1\)，来跑一遍最大流 \(f\)。

如果 \(f<n\) 就代表有的点的入度为 \(1\)，不符合题意，输出 'NO'。
如果 \(f=n\) 就代表每一个点都可以通过一个对应的点来达到入度出度都为 \(1\) 的要求，只需要再用一个 DFS 来找环就行了。

0809T1 圆身

题意

有 \(n\) 个 gie gie，第 \(i\) 个 gie gie 的速度为 \(w_i\) 秒每米，听力为 \(d_i\)，即能听见距离祂不超过 \(d_i\) 米处的音乐，初始在 \(p_i\) 位置。

您，也就是圆身，要在 \(c\) 位置处开 gie gie 见面会，这个 \(c\) 由您决定且为整数。这 \(n\) 个 gie gie 都会靠近您直到能听到您。您要最小化每个人移动的时间之和。

Sol

首先可以观察到一个显然的结论：选择的位置一定在每个区间的左右端点上。

浅显地证明一下：

假如，当前最优的位置不在区间的左右端点上。
那么一定可以向左/向右移动到某个区间的端点上，答案不变。

记录从左到右的左端点的 \(w_i\) 之和。

记录从右到左的右端点的 \(w_i\) 之和。

那么直接枚举每一个位置，然后暴力将每个位置的答案算出来即可。

时间复杂度：\(O(n)\)

0809T2 周芳

题意

周芳很喜欢下国际象棋。

周芳告诉您，国际象棋中象可以沿着对角线方向前进，并且吃掉沿途经过的棋子。

现在祂给您一个 \(n \times n\) 的棋盘，您需要在上面摆放国际象棋中的象，使得它们互相攻击不到，分别求出摆放 \(1 ~ k\) 个的方案数对 \(998244353\) 取模的值。

Sol

对棋盘进行黑白染色。

黑白两色的格子没有影响。

对两个颜色的格子分别考虑。

可以发现上下顺序对答案也没有影响。

设 \(f_{ij}\) 为前 \(i\) 行，放 \(j\) 个象的方案数。

\(s_i\) 为当前行的列数。

如果列数使递增的，那么当前的方案数就为 \((s_i - j) \times f_{i - 1 j - 1}\)。

最后再用 \(k^2\) 统计答案即可。

时间复杂度显然 \(O(k ^ 2 + nk)\)，可以通过。

0809T3 弄药

题意

医师把王哲带到一个到处都是草药的山洞里，对他说：

“您有一个长度为 \(n\)，值从 \(0\) 到 \(n - 1\) 的排列 \(a\)。您需要求有多少个区间 \([l, r]\) 满足 \(mex(a_l, a_{l + 1}, \cdots, a_r) \le med(a_l,a_{l+1},\cdots,a_r)\)，其中 \(1\le l\le r\le n\)。

其中 \(mex(S)\) 为没有在 \(S\) 中出现的最小非负整数；\(med(S)\) 为 \(S\) 从小到大排序后 \(S_{\left\lfloor\dfrac{|S|+1}{2}\right\rfloor}\) 的值（下标从 \(1\) 开始）。

您作为一棵心地善良的草药，告诉王哲答案对 \(41719\) 取模就行了。王哲一看您这么聪明，连忙邀请您来解决这个问题。

Sol

正难则反。

假如我们可以求 \(mex(a_l, a_{l + 1}, \cdots, a_r) > med(a_l, a_{l + 1}, \cdots, a_r)\) 的个数，那么这道题就做完了。

由于该序列是一个排列，假如我们确定了 \(med(a_l,a_{l+1},\cdots, a_r)\) ，那么我们很容易就可以确定 \(l, r\)。

直接枚举 \(med\) 然后简单算出来 \(l, r\) 统计答案即可。

0811T1 计数练习

题意

作为一名普及组选手，小 \(A\) 喜欢数数。

一天，小 \(A\) 学习了排列相关的知识。定义一个长度为 \(n\) 的序列 \(p_{1...n}\) 是一个 \(n\) 阶排列，当且仅当 \(p_{1...n}\) 都是 \([1, n]\) 中的正整数且它们两两不同。

小 \(A\) 想数排列。为了让数排列更有趣，小 \(A\) 决定加入一个限制：

对于一个 \(n\) 阶排列 \(p\) ，小 \(A\) 会构造一个长度为 \(n\) 的序列 \(Q(p)\) ，其中 \(Q(p)_{p_i} = i\) 。小 \(A\) 称排列 \(p\) 是优秀的，当且仅当 \(p\) 的字典序严格小于 \(Q(p)\) 。即存在一个 \(i\) 使得 \(\forall 1 \le j < i, p_j = Q(p)_j\) 且 \(p_i < Q(p)_i\) 。

现在，小 \(A\) 想了一个数 \(n\)，他希望对于每个 \([1, n]\) 间的 \(m\)，计算好的 \(m\) 阶排列数量，在开始数这样的排列数量前，小 \(A\) 给了你一个质数 \(mod\) ，希望你先求出好的 \(m\) 阶排列数量对 \(mod\) 取模的结果。

为了避免极其大的输出，设表示好的阶排列数量对取模的结果，你只需要输出，即所有的异或和。这样小在自己数错的时候就有大约的概率发现自己数错了，并重新数一遍。

Sol

由于 \(Q(Q(p)) = p\)，也就是说一个排列的逆排列就是自己。

如果从 \(p\) 和 \(Q(p)\) 的视角出发，那么字典序的关系就是相反的。

那么一个排列一定会贡献 \(1\) 除非 \(p = Q(p)\)。

容易发现，如果所有轮换大小不超过 \(2\)，那么组成的排列的逆排列就是自己。

我们记这样的 \(n\) 阶排列数量为 \(f_n\)，那么有：

\[f_n = f_{n - 1} + (n - 1) \times f_{n - 2} \]

\[v_i = \dfrac{i! - f_i}{2} \]

0811T3 机房联络

题意

机房有 \(n\) 台电脑，之间有 \(m\) 条双向连接，构成一个联通的无向图。

然而，教练发现一些不法分子正在使用这些连接进行 py，这无疑影响了模拟赛的公平性。

因此，教练决定炸毁一个同学的电脑，使得正在 py 的人之间彼此无法通讯。

py 的同学以三人为一个小组进行交流。

为了阻止他们，教练会告知你这三个人的编号，请你回答能否炸毁一个同学的电脑来使他们两两之间无法通讯。

教练不会真的炸毁这台电脑（因为不想赔钱）。因此各个询问之间互相独立。

由于 pyer 有精神分裂症，可能与自己 py，因此不保证 pyer 两两不同。这种情况下，炸毁这个同学的电脑可视作阻止他与自己 py。

如有多个答案，输出编号最小的一个，无解输出 \(-1\)。

Sol

圆方树裸题。

先建出圆方树，可以发现炸毁的电脑一定是某两个点中的 \(lca\) 的深度最大的点，其次选出的点显然不能为方点。

那么直接对圆方树做一遍树剖，然后求出 \(lca\) 进行分类讨论。

0812T1 密码锁

题意

寒假时小 c 承诺以后锁车不用有大于等于一万个拨圈的密码锁，所以暑假伊始小 c 网购了只有四个拨圈的锁。

这种密码锁被解锁当且仅当拨圈每四个对应位置之和相等。

但是小 c 担心网购产品不合格，所以想检查密码锁是否能被打开。

第一行两个正整数 \(T,n(n\le 1000)\) 表示数据组数和密码锁拨圈长度。

每组数据四行，每行 \(n\) 个非负整数，分别表示每个拨圈各位置上的值。

一行一个长度为 \(T\) 的仅含 ‘0’ 和 ‘1’ 字符串，分别表示每个密码锁是否能被解锁。‘1’ 表示可以被解锁，‘0’ 表示不能被解锁。

Sol

暴力为 \(n ^ 4\) 可以想到一个经典的套路。

将 \(4\) 个拨圈分成两半，分别用 \(n ^ 2\) 求出所有方案。

可以发现现在的难点在于如何在 \(O(n)\) 的时间内，匹配所有循环重构的字符串。

考虑哈希，每次循环重构加入一个字符再删除一个字符，可以做到 \(O(1)\)。

由于循环重构后这 \(n\) 个字符串本质是相同的，可以想到保存最小哈希值以判断是否重复。

更优秀的做法是找该字符串的最小表示法，一遍哈希搞定。

0812T2 网格行走

题意

给你一个 \(n\) 的网格，网格中的每个格子中都写有一个整数，其中第 \(i\) 行第 \(j\) 列的格子上写有数字 \(a_{i,j}\)。从 \(0\) 到 \(n\times m-1\) 的所有整数都在网格中出现了恰好一次。

令 \((i,j)\) 第 \(i\) 行第 \(j\) 列的格子，你现在需要从 \((1,1)\) 走到 \((n,m)\)，每次只能向右或向下走（即从 \((i,j)\) 走向 \((i+1,j)\) 或 \((i,j+1)\)），且不能走出网格。

定义一条行走路径的价值为所有经过的点上所写数字所构成集合的 \(mex\)。你需要求出所有行走路径中价值的最大值。
定义一个集合的 \(mex\) 为没有在集合中出现过的最小非负整数。

Sol

简单题。

容易发现元素都只会出现一次，又因为我们的路径只能向下或向右走。

一个简单的偏序问题。

直接枚举答案 \(mex\) 然后简单维护一个 \(set\)/树状数组都行。

0812T4 子图

题意

给定一个 \(n\) 个点 \(m\) 条边的简单无向图。对于一个导出子图 \(G\) 和一个正整数 \(k\)，称 \(G\) 是一个 \(k\) 度子图，当且仅当：

\(G\) 中的每个点在 \(G\) 中度数都 \(\ge k\)。
\(G\) 是连通图。
\(G\) 是极大的，即不存在一个 \(G\) 的超集也满足以上两个条件。

然后定义 \(n(G)\) 为 \(G\) 的点数，\(m(G)\) 为 \(G\) 的边数，\(b(G)\) 为割的大小，即一个端点在 \(G\) 中而另一个端点不在的边的个数。
定义图 \(G\) 的权值为 \(score(G)=M\times m(G)-N\times n(G)+B\times b(G)\)，其中 \(M,N,B\) 为给定常数。
你要求出最大的 \(k\) 度子图的权值，如有多个选取 \(k\) 最大的那个。
（请注意 \(k\) 是你自己任选的。）

Sol

\(G\) 必须是极大的，从而限定了 \(G\) 的数量级。
若 \(G_1,G_2\) 均为 \(k\) 度子图，则 \(G_1\cap G_2=\emptyset\)。
找出所有合法子图，将所有的点从小到大枚举度数删除即可。删除过程中维护子图的连通性并不好做，经典套路倒着做一遍并查集即可。

0814T2 家人

题意

为了给 \(Miorine\) 争取时间，你闯入了数据风暴。数据风暴是一个 \(2 \times n\) 的迷宫，有一些格子不能走。能走的格子用 \(.\) 表示，不能走的用 \(x\) 表示。第一行的格子编号为 \(1 ~ n\)，第二行的格子编号为 \(n + 1 ~ 2n\)。

\(Miorine\) 有 \(m\) 组询问，每组询问给出两个数 \(u, v\)，您需要回答：编号为 \(u\) 的格子和编号为 \(v\) 的格子之间的最短路。

保证 \(u\) 号格子和 \(v\) 号格子是能走的。如果 \(u, v\) 两个格子间不可达，输出 \(-1\)。

Sol

可以考虑如何合并两个区间。

发现我们只需要记录：

\(lu\)：左上端点到右上端点的最短路
\(ld\)：左上端点到右下端点的最短路
\(ru\)：左下端点到右上端点的最短路
\(rd\)：左下端点到右下端点的最短路

设当前节点的左右儿子为 \(l, r\)。

很容易就能推出 pushup。

void pushup(Node &x, Node l, Node r) {
	x.lu = min(l.ld + r.ru, l.lu + r.lu) + 1;
	x.ld = min(l.ld + r.rd, l.lu + r.ld) + 1;
	x.rd = min(l.ru + r.ld, l.rd + r.rd) + 1;
	x.ru = min(l.ru + r.lu, l.rd + r.ru) + 1;
	if (x.lu >= inf) x.lu = inf;
	if (x.ld >= inf) x.ld = inf;
	if (x.rd >= inf) x.rd = inf;
	if (x.ru >= inf) x.ru = inf;
}

0814T3 你所热爱的就是你的生活 (蒙古上单：你_什么时候__啊)

题意

世界著名的系列演出《你所热爱的就是你的生活》（简称《 \(LoveLive!\) 》）在观步子市举行。\(Haruhi\) 已经抵达了观步子市，他不是任何团的粉丝，也没有时间观念。她只是单纯的想去看几场演出。如果她有足够的钱，她会去看所有的演出。不幸的是，她的财产十分有限，她决定把所有财产都用来买门票。

给出 \(Haruhi\) 的预算和每场演出的票价，试求：如果总票价不超过预算，他有多少种方案。如果存在以其中一种方案观看某场演出而另一种方案不观看，则认为这两种方案不同。

Sol

分段 dfs 板子题。

分成两段 dfs 后，直接两个指针乱跑合并就行。

0814T4 泉

题意

泉此方在 GAMERS 等柊镜。

她看到宫河日向在货架上放了 \(n\) 种漫画，货架总共有 \(m\) 列，其中第 \(i\) 种漫画在第 \(l_i\) 列到第 \(r_i\) 列中的每一列上都各有一本。

作为「ショッピングモンスター」，泉此方决定选择一个区间，并买下这个区间中每一列上摆放的所有漫画。

对于买下的每一种漫画，泉此方会分别留下若干本（可能为零）保存用和鉴赏用，再剩下一本传教用，所以她希望至少买下一种漫画，且买下的每一种漫画都有奇数本。

但这时柊镜到了，于是泉此方并没有买下任何漫画，不过她想知道，所有可以满足她心意的区间包含的列数之和为多少。

Sol

判断某种元素是否为奇数并不好做。

可以想到改成判断偶数。

如果是判断偶数，我们对每个元素打上一个随机权值，异或和的结果为 \(0\) 的区间即为答案区间。

如果当前的答案区间长度为 \(1\)。

我们相当于直接把这些区间给删掉了。

所以我们在统计答案的时候可以把所有长度为 \(0\) 的区间先加上，然后再减去不合法的长度为 \(0\) 的区间。

随便开个 \(map\) 统计答案即可。

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

0816T2 能动

题意

对于一个非空的可重实数集 \(S\)，定义 \(S\) 的平均值为 :

\[\text{avg}\ S=\frac{\sum_{x\in S}x}{|S|} \]

其中 \(|S|\) 为 \(S\) 中元素个数。

例如 :\(\text{avg}\{1,1,4,5,1,4\}=\frac{1+1+4+5+1+4}{6}=\frac{8}{3}\)。

对于一个元素个数超过 \(2\) 的可重实数集 \(S\)，定义 \(S\) 的截尾平均值为：

\[\text{exavg}\ S=\frac{\sum_{x\in S}x-\max S-\min S}{|S|-2} \]

其中 \(|S|\) 为 \(S\) 中元素个数。

例如: \(\text{exavg}\{1,9,1,9,8,1,0\}=\frac{(1+9+1+9+8+1+0)-9-0}{7-2}-4\)。

对于一个序列 \(a\) 我们定义它的 \(k\) 号权值为：

\[\text{avg}\ \{\text{exavg}\ A[l...r]|1\le l,r\le n,r-l\ge 2\}\mod k \]

现在给你一个正整数序列，要求输出它的 \(k\) 号权值。

Sol

很显然的思路，对于每个元素算具体的贡献。

当该元素为当前区间的最小/最大值时，该元素不做贡献。

设 \(f(l, r, p)\) 为左端点在 \([l, p]\) 右端点在 \([p, r]\)，\(p\) 所做的贡献。

显然可得 \(f(l, r, p)\) 为 \(\sum\limits_{i = l} ^ p \sum\limits_{j = p} ^ r \frac{[j - i \ge 2]}{j - i - 1}\)。

设 \(h(l, r)\) 为左右端点在 \([l, r]\) 的 \(p\in{[l, r]}\) 的贡献。

\[\begin{aligned} f(l, r, p) & = h(l, r) - h(l, p) - h(p, r) \\ & = \sum\limits_{len = 3}^{r - l + 1}(\frac{r - l - len + 2}{len - 2}) \\ & = \sum\limits_{len = 3} ^ {r - l + 1}(\frac{r - l}{len - 2} - 1) \\ & = [(r - l)\sum\limits_{len = 3}^{r - l + 1}\frac{1}{len - 2}] - (r - l - 1)\end{aligned} \]

对于 \(\sum\limits_{len = 3} ^ {r - l + 1}\frac{1}{len - 2}\) 使用一个前缀和预处理即可。

0816T3 数学

题意

子弹从点 \(N\) 射出，沿 水平方向 到达点 \(O\)，反射而出，在 \(M\) 处击中死者后脑勺。

你认为，若在射线 \(ON\) 上，有两个定点 \(A,B\)。一定会有且仅有一个点 \(P\) 在射线 \(OM\) 上使得 \(\angle APB\) 达到最大值。

现在我们需要你对于每一组询问求出 \(P\) 点坐标。

Sol

我们过 \(A,B\) 做圆，使得 \(OM\) 为该圆的切线，在 \(OM\) 上任取一点 \(F\)，连接 \(BF\)，交圆于点 \(G\)，连 \(AG\)。

\(\because \angle AEB=\angle AGB\)

\(\therefore \angle AEB>\angle AFB\)

易得 \(\vartriangle OBE\sim \vartriangle OEA\)

\(\therefore \dfrac{OE}{OB}=\dfrac{OA}{OE}\)

故 \(OE^2=OA\times OB\)。

所以 \(P\) 的坐标为：

\[\left(\frac{\sqrt{x_a\times x_b}}{\sqrt{x_m^2+y_m^2}}\times x_m,\frac{\sqrt{x_a\times x_b}}{\sqrt{x_m^2+y_m^2}}\times y_m\right) \]

0818T1 序列

题意

认为一个长度为 \(l\) 的序列 \(a_1,\cdots ,a_l\) 是好的，当且仅当这个序列满足如下条件：

不存在 \(x,y,z\) 满足 \(1\le x<y<z\le l\) 且满足 \(a_x<a_z<a_y\)。
不存在 \(x,y,z\) 满足 \(1\le x<y<z\le l\) 且满足 \(a_y<a_z<a_x\)。

例如序列 \(2,1,3,4\) 是好的，但是 \(1,3,2\)（不满足条件 \(1\)）和序列 \(4,3,1,2\)（不满足条件 \(2\)）都不是好的。
现在有一个长度为 \(n\) 的排列 \(p\)。\(p\) 是一个长度为 \(n\) 的序列，且 \(1,2,\cdots ,n\) 在序列中都正好出现一次。称序列 \(b_1,b_2,\cdots ,b_l\) 是 \(p\) 的一个子序列，当且仅当可以通过在排列 \(p\) 中删去若干个元素，不改变剩下元素的顺序得到序列 \(b\)。
可以发现，对于长度为 \(n\) 的排列 \(p\)，它一共有 \(2^n-1\) 个非空的子序列。求这 \(2^n-1\) 个子序列中有多少个好的序列。答案对 \(998244353\) 取模。
共有 \(T\) 组数据。

Sol

从 \(a_x\) ，\(x\) 之后的点是单调上升或单调下降的。
从 \(a_y\) ，比 \(a_y\) 小的元素必须均大于右侧比 \(a_y\) 小的元素。左侧比 \(a_y\)大的元素必须均大于右侧比 \(a_y\)大的元素。
从 \(a_z\) ，\(a_z\) 只能是序列 \(1\sim z\) 中的最小值或最大值。

我们就先从 \(a_z\) 和 \(a_x\) 入手。

从 \(a_z\) 入手是最简单的，对于每一个 \(a_i\)，要么是前缀最小值或者是前缀最大值。这样我们就得到了 \(O(n^3)\) 的 dp。\(50 pts\)。

若从 \(a_x\) 入手，当我们确定了序列的第一个元素，后面的序列与该元素构成上升/下降子序列。

从里我们可以有一个奇妙的处理，将序列翻转再拼接到开头，这样一个合法的序列就会个一个上升子序列对应，且每一个序列对应两次，复杂度为 \(O(n\log n)\)。

0818T2 浦西

题意

浦西进行翻新了。

浦西可以看做一个 \(n\) 行 \(m\) 列的矩阵 \(A\)，初始所有元素都为 \(0\)，\(A_{i,j}\) 表示坐标 \((i,j)\) 的高楼的修建年代。

整个翻新过程将会持续 \(q\) 个时刻。

在每个时刻，政府进行三种操作中的一个：

\(1\;r_i\)，政府会翻修 \(r_i\) 行的所有大楼，即矩阵的第 \(r_i\) 行全部赋值为 \(i\)。
\(2\;c_i\)，政府会翻修 \(c_i\) 列的所有大楼，即矩阵的第 \(c_i\) 列全部赋值为 \(i\)。
\(3\;r_{i,1}\;c_{i,1}\;r_{i,2}\;c_{i,2}\;k_i\)，政府想要知道从 \({r_{i,1},c_{i,1}}\) 到 \((r_{i,2},c_{i,2})\) 的最短路，其中不能走修建时刻小于 \(k\) 的大楼，即不经过 \(a_{i,j}\) 小于 \(k\) 的 \((i,j)\)（包括起点与终点）。若有最短路，则输出最短路长度，否则输出 \(‐1\)。

Sol

对于行和列计算最短路。

这里我们需要简单分讨一下：

1.两个点直接用曼哈顿距离计算。

2.还有一种情况是需要需要绕一下路。

我们需要用两颗线段树来维护一下每一行和每一列的最小值即可。

0818T3 手语的

题意

给你一个平面。

给你三个正交矩形和一个点，问是否存在一个三角形，使得该三角形的三个顶点分别在三个正交矩形内，且该三角形的重心为给定点。

正交矩形：四条边都平行于坐标轴的矩形。

Sol

我们知道三角形的重心 \(G=\left(\dfrac{x_A+x_B+x_C}{3},\dfrac{y_A+y_B+y_C}{3}\right)\)。

所以我们只需要简单判断一下：

\[x_G\in\left[\dfrac{minx_A+minx_B+minx_C}{3},\dfrac{maxx_A+maxx_B+maxx_C}{3}\right] \]

\[y_G\in\left[\dfrac{miny_A+miny_B+miny_C}{3}+\dfrac{maxy_A+maxy_B+maxy_C}{3}\right] \]

即可。

0819T1 序列II

题意

你现在有一序列\(A\) ，里面有一个数 \(x\)。

设末尾的数是 \(y\) 。你可以在 1 到 \(\lfloor \sqrt y\rfloor\) 中选取一个数 \(z\) 加到序列的末尾。

如此进行 \(114514\) 次操作，问一共有多少种可能的情况，答案对 \(998244353\) 取模。

Sol

我们设 \(f_i\) 为当前数字为 \(i\) 的所有情况数。

显然根据题意 \(f_n = \sum\limits_{i = 1} ^ {\sqrt n} f_i\)

我们设 \(g_n\) 为 \(\sum\limits_{i = 1} ^ {n} f_i\)

我们对所以的 \(n\) 的情况进行分类讨论。

\(n \le 10 ^ 5\) 直接输出 \(f_i\) 即可。
\(n \le 10 ^ {10}\) 直接输出 \(g_{\sqrt n}\) 即可。
\(n \le 10 ^ {18}\)

\[\begin{aligned} f_n & = \sum\limits_{i = 1} ^ {\sqrt n} f_i \\ & = \sum\limits_{i = 1} ^ {\sqrt {\sqrt n}} f_i \\ \end{aligned}\]

到这里这道题就做完了，我们直接对于 \(i = 1 \sim {\sqrt {\sqrt n}}\) 的 \(g_i\) 求一遍和即可。

0819T2 数学

题意

一天，好吃遇到了一道数学题：

给定 \(n\), 求出正整数对 \((x, y)\) 的对数, 满足 \(xy + 1 | x ^ 2 + y ^ 2, 1 \le x \le y \le n\)

好吃请你帮他完成这道题。你需要回答好吃的 \(t\) 次询问。

Sol

找规律题？

可以很显然发现 \((n, n ^ 3)\) 即为一组答案。

还可以发现这样一组规律：

\(30 = 8 * (2 ^ 2) - 2\)
\(112 = 30 * (2 ^ 2) - 8\)

规律就是这样。

简单用 \(for\) 生成一下。

可以证明这堆东西不会超过 \(log\)。

0822T1 压轴题

题意

给定整数 \(p, k\)，问有多少种方案构造出一个长度为 \(p\) 的非负整数序列 \(f\)（下标从 \(0\) 开始），满足对于任意 \(0\) 到 \(p - 1\) 之间的整数 \(x\)，\(\large f_{kx \% p} = kf_{x} \% p\)。

答案对 \(1e9 + 7\) 取模。

Sol

考虑每一条限制：\(\large f_{kx} = kf_x\)。

将每一条限制连边，加入并查集中。

每一个联通块中只要确定了一个元素，其他所有元素都确定了。

设联通块的数量为 \(ans\)。

答案即为 \(n ^ {ans}\)。

0822T2 极端题

题意

对于一个数列，定义一次 kiku 操作为选择数列中任意一个元素 \(a_i\)，将这个位置替换为两个 正整数 \(x, y\) ，满足 \(x + y = a_i\)。定义一个数列的”极端值“为将这个数列变成不降数列的最小操作次数。

现在给定一个长度为 \(n\) 的数列 \(a\) ，求出这个数列的所有非空子段的”极端值“之和。

答案对 \(998244353\) 取模。

Sol

一个很显然的结论。

若 \(a_i \le a_{i + 1}\) 直接跳过。

若 \(a_i > a_{i + 1}\)，\(a_i = \dfrac{a_i}{\lfloor\frac{a_i}{a_{i + 1}}\rfloor}, ans += \lfloor\frac{a_i}{a_{i + 1}}\rfloor\)。

我们可以发现，\(\forall i\in[1, n]\)，\(a_i\) 的取值只会和 \(a_{i + 1}\) 有关。

那么，我们可以想到简单开一个 \(vector\) 来保存 \(a_i\) 在 \(\forall j\in[i + 1, n]\) 为右端点的取值。

我们可以发现 \(vector\) 里面有大量的元素是相同的，简单用一个 \(list\) 对元素向前合并。

可以证明元素的个数不会超过 \(\sqrt{n}\)

时间复杂度为 \(O(n\sqrt{n})\)

0823T1 简化题面

题意

CDQZ 的出题人小 \(M\) 喜欢改题面。但是她经常把题面改得太长，从而被 HEZ 的神仙们怒斥，因此她非常伤心，决定简化题面。

小 \(M\) 出了 \(R - L + 1\) 道题，第 \(i\) 道题目的题面复杂程度是 \(L + i - 1\) 。她决定将每道题进行如下的简化：如果这道题初始的题面复杂程度为 \(x\) ，那么简化后的题面复杂度为 \(y\) ，其中 \(y\) 是把 \(x\) 的各个数位排序并去掉前导 \(0\) 后形成的数。

例如，一道题面复杂程度为 \(2023\) 的题目简化后题面复杂度为 \(223\)，同理，一道题面复杂程度为 \(114514\) 的题目简化后的题面复杂度为 \(111445\)。

小 \(M\) 想请您求出，在给定 \(L, R\) 的情况下，一共有多少种简化后的题面复杂度。因为她的姐姐小 \(S\) 非常可爱，因此您不能拒绝小 \(M\) 的请求。

Sol

可以发现满足条件的答案只有 \(C_{27}^9\) 大约只有 \(5e6\) 左右。

一个很显然的思路，枚举答案判断该数字是否在 \(L, R\) 之间。

设 \(f_{ijk}\) 为前 \(i\) 位，是否贴着上界，是否贴着下界。

我们直接暴力记搜，每次从当前的上界枚举到下界，由于一共只有 \(18 \times 4\) 种方案，所以跑得飞快。

可以过掉本题。

0823T2 题面不长

题意

给定正整数 \(n, k, M\)，且 \(M\) 为质数。对于 \(x \in [1, n]\)，求有多少个非空的可重集满足：

可重集中的元素均为 \([1, n]\) 中的正整数。
可重集中元素的重数不超过 \(k\)。一个元素的重数指的是该元素在可重集中的出现次数。
可重集中元素的平均数为 \(x\)。

答案对 \(M\) 取模。

Sol

维护平均数的限制，很容易想到可以将每个数字减去 \(x\)，然后做一个多重背包。

加上前缀和优化后该算法的复杂度为 \(O(n ^ 3 \times k)\) 不能通过本题。

再好好思考一下，如果我们只做一遍背包。

答案不就是：\(f_{i - 1}{j} \times f_{n - i}{j} \times (k + 1)\)。

时间复杂度为 \(O(n ^ 2 \times k)\)。

0823T3 题面很短

题意

小 M 厌倦了写很长的题面。

对于字符串 \(s\)，定义 \(\large f(s)\) 为 \(s + rev(s)\)，其中 \(rev(s)\) 表示 \(s\) 的反串。例如，\(\large f(mea) = meaaem\) 。

给定字符串 \(t\)。求出最短的字符串 \(s\)，使得 \(s\) 经过若干次 \(s \rightarrow f(s)\) 后 \(s\) 能够变成 \(t\)。

Sol

水题。

每次取中间，只会取 \(log\) 次。做完了。

标签：le,题意,报告,一个,Sol,times,解题,序列
From： https://www.cnblogs.com/cxqghzj/p/17661969.html

解题报告 8月