蓝桥杯|第十三届蓝桥杯大赛软件赛省赛（C/C++ 大学A组）蓝桥杯|c

蓝桥杯 2022年省赛真题
C/C++ 大学A组

试题 A: 裁纸刀
试题 B: 灭鼠先锋
试题 C: 求和
试题 D: 选数异或
试题 E: 爬树的甲壳虫
试题 F: 青蛙过河
试题 G: 最长不下降子序列
试题 H: 扫描游戏
试题I: 数的拆分
试题 J: 推导部分和

??One more time, One more chance - Uru ?
试题 A: 裁纸刀本题总分： 5 5 5 分
【问题描述】
??小蓝有一个裁纸刀，每次可以将一张纸沿一条直线裁成两半。
??小蓝用一张纸打印出两行三列共6 6 6 个二维码，至少使用九次裁出来，下图给出了一种裁法。

文章图片

??在上面的例子中，小蓝的打印机没办法打印到边缘，所以边缘至少要裁4 4 4 次。另外，小蓝每次只能裁一张纸，不能重叠或者拼起来裁。
??如果小蓝要用一张纸打印出20 20 20 行22 22 22 列共440 440 440 个二维码，他至少需要裁多少次？
【答案提交】
??这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

443

??设状态f i , j f_{i,j} fi,j? 为i i i 行j j j 列的纸片在最优裁剪方案下的步骤数，显然有f i , j = f j , i f_{i,j} = f_{j,i} fi,j?=fj,i?、 f i , 1 = i ? 1 f_{i,1} = i-1 fi,1?=i?1、 f i , j = min ? { f i ′ , j + f i ? i ′ , j , f i , j ′ + f i , j ? j ′ } + 1 ∣ 1 ≤ i ′ < i , 1 ≤ j ′ < j f_{i,j}=\min\{f_{i',j}+f_{i-i',j},f_{i,j'} +f_{i,j-j'}\}+1|1\leq i' < i,1\leq j' < j fi,j?=min{fi′,j?+fi?i′,j?,fi,j′?+fi,j?j′?}+1∣1≤i′ ??我们将f i , j f_{i,j} fi,j? 的表达式变形为f i , j = min ? { f i ′ , j + f i ? i ′ , j + 1 , f i , j ′ + f i , j ? j ′ + 1 } ? 1 f_{i,j}=\min\{f_{i',j}+f_{i-i',j}+1,f_{i,j'} +f_{i,j-j'}+1\}-1 fi,j?=min{fi′,j?+fi?i′,j?+1,fi,j′?+fi,j?j′?+1}?1，将f i , 1 = i ? 1 f_{i,1} = i-1 fi,1?=i?1 代入式中会发现，无论怎么拆分，最后表达式一定是若干f 1 , x + 1 f_{1,x}+1 f1,x?+1、 f y , 1 + 1 f_{y,1}+1 fy,1?+1 和? 1 -1 ?1 的累加，其和一定是i × j ? 1 i×j-1 i×j?1。
??所以切分次数与切分方案无关，都是i × j ? 1 i × j - 1 i×j?1。

#include int n = 20, m = 22; int main() { printf("%d", n * m + 3); }

试题 B: 灭鼠先锋本题总分： 5 5 5 分
【问题描述】
??灭鼠先锋是一个老少咸宜的棋盘小游戏，由两人参与，轮流操作。
??灭鼠先锋的棋盘有各种规格，本题中游戏在两行四列的棋盘上进行。游戏的规则为：两人轮流操作，每次可选择在棋盘的一个空位上放置一个棋子，或在同一行的连续两个空位上各放置一个棋子，放下棋子后使棋盘放满的一方输掉游戏。
??小蓝和小乔一起玩游戏，小蓝先手，小乔后手。小蓝可以放置棋子的方法很多，通过旋转和翻转可以对应如下四种情况：：：
? X O O O \mathrm{XOOO} XOOOX X O O \mathrm{XXOO} XXOOO X O O \mathrm{OXOO} OXOOO X X O \mathrm{OXXO} OXXO
? O O O O \mathrm{OOOO} OOOOO O O O \mathrm{OOOO} OOOOO O O O \mathrm{OOOO} OOOOO O O O \mathrm{OOOO} OOOO
??其中O \mathrm O O 表示棋盘上的一个方格为空， X \mathrm X X 表示该方格已经放置了棋子。
??请问，对于以上四种情况，如果小蓝和小乔都是按照对自己最优的策略来玩游戏，小蓝是否能获胜。如果获胜，请用V \mathrm V V 表示，否则用L \mathrm L L 表示。请将四种情况的胜负结果按顺序连接在一起提交。
【答案提交】
??这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个长度为4 4 4 的由大写字母V \mathrm V V 和L \mathrm L L 组成的字符串，如V V L L \mathrm{VVLL} VVLL，在提交答案时只填写这个字符串，填写多余的内容将无法得分。

VVVL

SG 函数 ??标题应该起博弈论的，但我代码都写完了就懒得改了。
??根据公平组合游戏定理有：：：
?? 1 ) ： 1)： 1)：没有后继状态的状态是必败状态。
?? 2 ) ： 2)： 2)：一个状态是必胜状态，当且仅当存在至少一个必败状态为它的后继状态。
?? 3 ) ： 3)： 3)：一个状态是必败状态，当且仅当它的所有后继状态均为必胜状态。
??显然棋盘被放满是一个必胜状态，以它作为递归函数出口，然后根据公平组合游戏定理递归就行。

#include int SG(int line1, int line2) { if (line1 == 0b1111 && line2 == 0b1111) return 1; if ((line1 & 0b1000) == 0) if (!SG(line1 | 0b1000, line2)) return 1; if ((line2 & 0b1000) == 0) if (!SG(line1, line2 | 0b1000)) return 1; for (int i = 0; i < 3; ++i) { if ((line1 & (1 << i)) == 0) if (!SG(line1 | (1 << i), line2)) return 1; if ((line2 & (1 << i)) == 0) if (!SG(line1, line2 | (1 << i))) return 1; if ((line1 & (0b11 << i)) == 0) if (!SG(line1 | (0b11 << i), line2)) return 1; if ((line2 & (0b11 << i)) == 0) if (!SG(line1, line2 | (0b11 << i))) return 1; } return 0; }int main() { printf("%c", SG(0b1000, 0b0000) ? 'V' : 'L'); printf("%c", SG(0b1100, 0b0000) ? 'V' : 'L'); printf("%c", SG(0b0100, 0b0000) ? 'V' : 'L'); printf("%c", SG(0b0110, 0b0000) ? 'V' : 'L'); }

试题 C: 求和时间限制:1.0 s 1.0\mathrm s 1.0s?内存限制:256.0 M B 256.0\mathrm{MB} 256.0MB?本题总分： 10 10 10 分
【问题描述】
??给定n n n 个整数a 1 , a 2 , ? ? , a n a_1, a_2, \cdots , a_n a1?,a2?,?,an?，求它们两两相乘再相加的和，即 S = a 1 ? a 2 + a 1 ? a 3 + ? + a 1 ? a n + a 2 ? a 3 + ? + a n ? 2 ? a n ? 1 + a n ? 2 ? a n + a n ? 1 ? a n 。 S = a_1\cdot a_2 + a_1\cdot a_3 + \cdots + a_1\cdot a_n + a_2\cdot a_3 +\cdots + a_{n?2}\cdot a_{n?1} + a_{n?2}\cdot a_n + a_{n?1}\cdot a_n。 S=a1??a2?+a1??a3?+?+a1??an?+a2??a3?+?+an?2??an?1?+an?2??an?+an?1??an?。
【输入格式】
??输入的第一行包含一个整数n n n 。
??第二行包含n n n 个整数a 1 , a 2 , ? ? , a n a_1, a_2,\cdots,a_n a1?,a2?,?,an?。
【输出格式】
??输出一个整数S S S，表示所求的和。请使用合适的数据类型进行运算。
【样例输入】

4 1 3 6 9

【样例输出】

117

【评测用例规模与约定】
??对于30 % 30\% 30% 的数据， 1 ≤ n ≤ 1000 ， 1 ≤ a i ≤ 100 1 ≤ n ≤ 1000，1 ≤ a_i ≤ 100 1≤n≤1000，1≤ai?≤100。
??对于所有评测用例， 1 ≤ n ≤ 200000 ， 1 ≤ a i ≤ 1000 1 ≤ n ≤ 200000，1 ≤ a_i ≤ 1000 1≤n≤200000，1≤ai?≤1000。
公式递推 ??将S S S 中包含a 1 a_1 a1? 的项整理出来，有：
?? S = a 1 ? ( a 2 + a 3 + ? + a n ) + a 2 ? a 3 + ? + a n ? 2 ? a n ? 1 + a n ? 2 ? a n + a n ? 1 ? a n S=a_1\cdot(a_2+a_3+\cdots+a_n)+ a_2\cdot a_3 +\cdots + a_{n?2}\cdot a_{n?1} + a_{n?2}\cdot a_n + a_{n?1}\cdot a_n S=a1??(a2?+a3?+?+an?)+a2??a3?+?+an?2??an?1?+an?2??an?+an?1??an?
??同样的将余项中包含a 2 a_2 a2?、 a 3 a_3 a3?、 ? \cdots ?、 a n a_n an? 的项整理出来：
?? S = a 1 ? ( a 2 + a 3 + ? + a n ) + a 2 ? ( a 3 + a 4 + ? + a n ) + ? + a n ? 1 ? a n = a 1 ? ∑ i = 2 n a i + a 2 ? ∑ i = 3 n a i + ? + a n ? 1 ? ∑ i = n n a i \begin{aligned}S&=a_1\cdot(a_2+a_3+\cdots+a_n)+ a_2\cdot(a_3+a_4+\cdots+a_n)+\cdots+a_{n-1}\cdot a_n\\&=a_1\cdot\sum_{i=2}^na_i+a_2\cdot \sum_{i=3}^na_i+\cdots+a_{n-1}\cdot\sum_{i=n}^{n}a_i\end{aligned} S?=a1??(a2?+a3?+?+an?)+a2??(a3?+a4?+?+an?)+?+an?1??an?=a1??i=2∑n?ai?+a2??i=3∑n?ai?+?+an?1??i=n∑n?ai??
??也就S S S 等于每个元素乘以右边所有元素的和的和，考虑到实现计算的代码量，我们将S S S 的项重排，重新整理出：
?? S = a 1 ? ∑ i = 1 0 a i + a 2 ? ∑ i = 1 1 a i + ? + a n ? ∑ i = 1 n ? 1 a i S=a_1\cdot\displaystyle\sum_{i=1}^{0}a_i+a_2\cdot \sum_{i=1}^{1}a_i+\cdots+a_{n}\cdot\sum_{i=1}^{n-1}a_i S=a1??i=1∑0?ai?+a2??i=1∑1?ai?+?+an??i=1∑n?1?ai?

#include long long n, a, sum, ans; int main() { scanf("%d", &n); while (n--) scanf("%d", &a), ans += a * sum, sum += a; printf("%lld", ans); }

试题 D: 选数异或时间限制:1.0 s 1.0\mathrm s 1.0s?内存限制:256.0 M B 256.0\mathrm{MB} 256.0MB?本题总分： 10 10 10 分
【问题描述】
??给定一个长度为n n n 的数列A 1 , A 2 , ? ? , A n A_1, A_2, \cdots , A_n A1?,A2?,?,An? 和一个非负整数x x x，给定m m m 次查询, 每次询问能否从某个区间[ l , r ] [l,r] [l,r] 中选择两个数使得他们的异或等于x x x。
【输入格式】
??输入的第一行包含三个整数n , m , x n, m, x n,m,x。
??第二行包含n n n 个整数A 1 , A 2 , ? ? , A n A_1, A_2,\cdots, A_n A1?,A2?,?,An?。
??接下来m m m 行，每行包含两个整数l i , r i l_i,r_i li?,ri? 表示询问区间[ l i , r i ] [l_i,r_i] [li?,ri?]。
【输出格式】
??对于每个询问, 如果该区间内存在两个数的异或为x x x 则输出y e s \mathrm{yes} yes, 否则输出n o \mathrm{no} no。
【样例输入】

4 4 1 1 2 3 4 1 4 1 2 2 3 3 3

【样例输出】

yes no yes no

【样例说明】
??显然整个数列中只有2 , 3 2, 3 2,3 的异或为1 1 1。
【评测用例规模与约定】
??对于20 % 20\% 20% 的评测用例， 1 ≤ n , m ≤ 100 1 ≤ n, m ≤ 100 1≤n,m≤100；
??对于40 % 40\% 40% 的评测用例， 1 ≤ n , m ≤ 1000 1 ≤ n, m ≤ 1000 1≤n,m≤1000；
??对于所有评测用例， 1 ≤ n , m ≤ 100000 ， 0 ≤ x < 2 20 ， 1 ≤ l i ≤ r i ≤ n ， 0 ≤ A i < 2 20 1 ≤ n, m ≤ 100000 ，0 ≤ x < 2^{20} ，1 ≤ l_i ≤ r_i ≤ n ，0 ≤ A_i < 2^{20} 1≤n,m≤100000，0≤x<220，1≤li?≤ri?≤n，0≤Ai?<220。
动态规划 ??处理出f r f_r fr?，其意义为[ f r , r ] [f_r,r] [fr?,r] 中存在一对k k k、 g g g ， f r ≤ k ≤ g ≤ r f_r \leq k \leq g \leq r fr?≤k≤g≤r 使得A k ⊕ A g = x A_k \oplus A_g =x Ak?⊕Ag?=x 且f r f_r fr? 最大，若不存在则令f r = 0 f_r = 0 fr?=0。
??对于每一次询问[ l i , r i ] [l_i,r_i] [li?,ri?]，我们只需判断l i li li 和f r i f_{r_i} fri?? 的大小关系就能确定[ l i , r i ] [l_i,r_i] [li?,ri?] 之间是否存在两个数，它们的异或等于x x x。
??现在考虑转移，对于每一个r r r，我们判断下标大于r r r 的元素中是否存在A r ⊕ x A_r \oplus x Ar?⊕x，其中最靠r r r 的是f r f_r fr? 的一个候选值，同时我们还要考虑[ f r ? 1 , r ? 1 ] [f_{r-1},r-1] [fr?1?,r?1] 中是否有更优的方案，最终有状态转移方程： f r = max ? { f r ? 1 , max ? { i ∣ A i = A r ⊕ x } } f_r=\max\{f_{r-1},\max\{i|A_i=A_r\oplus x\}\} fr?=max{fr?1?,max{i∣Ai?=Ar?⊕x}}

#include int n, m, x, l, r, map[1 << 20], f[100010]; int max(int a, int b) { return a > b ? a : b; }int main() { scanf("%d %d %d", &n, &m, &x); for (int r = 1; r <= n; ++r) scanf("%d", &l), f[r] = max(f[r - 1], map[l ^ x]), map[l] = r; while (m--) scanf("%d %d", &l, &r), printf("%s\n", f[r] >= l ? "yes" : "no"); }

??不太对，感觉我在乱压行。
试题 E: 爬树的甲壳虫时间限制:1.0 s 1.0\mathrm s 1.0s?内存限制:256.0 M B 256.0\mathrm{MB} 256.0MB?本题总分： 15 15 15 分
【问题描述】
??有一只甲壳虫想要爬上一颗高度为n n n 的树，它一开始位于树根，高度为0 0 0，当它尝试从高度i ? 1 i ? 1 i?1 爬到高度为i i i 的位置时有P i P_i Pi? 的概率会掉回树根，求它从树根爬到树顶时，经过的时间的期望值是多少。
【输入格式】
??输入第一行包含一个整数n n n 表示树的高度。
??接下来n n n 行每行包含两个整数x i , y i x_i, y_i xi?,yi?，用一个空格分隔，表示P i = x i y i P_i =\frac{x_i}{y_i} Pi?=yi?xi??。
【输出格式】
??输出一行包含一个整数表示答案，答案是一个有理数，请输出答案对质数998244353 998244353 998244353 取模的结果。其中有理数a b \frac ab ba? 对质数P P P 取模的结果是整数c c c 满足0 ≤ c < P 0 ≤ c < P 0≤c 【样例输入 1】

1 1 2

【样例输出 1】

2

【样例输入 2】

3 1 2 3 5 7 11

【样例输出 2】

623902744

【评测用例规模与约定】
??对于20 % 20\% 20% 的评测用例， n ≤ 2 ， 1 ≤ x i < y i ≤ 20 n ≤ 2，1 ≤ x_i < y_i ≤ 20 n≤2，1≤xi? ??对于50 % 50\% 50% 的评测用例， n ≤ 500 ， 1 ≤ x i < y i ≤ 200 n ≤ 500，1 ≤ x_i < y_i ≤ 200 n≤500，1≤xi? ??对于所有评测用例， 1 ≤ n ≤ 100000 ， 1 ≤ x i < y i ≤ 1 0 9 1 ≤ n ≤ 100000，1 ≤ x_i < y_i ≤ 10^9 1≤n≤100000，1≤xi? 期望递推 ??设X i X_i Xi? 为事件甲壳虫从树根到达i i i，由期望函数E E E 是线性函数，可得 E ( X i ) = ( 1 ? P i ) ( E ( X i ? 1 ) + 1 ) + P i ( E ( X i ) + E ( X i ? 1 ) + 1 ) = E ( X i ? 1 ) + 1 1 ? P i = y i ( E ( X i ? 1 ) + 1 ) y i ? x i \begin{aligned}E(X_i)&=(1-P_i)(E(X_{i-1})+1)+P_i(E(X_i)+E(X_{i-1})+1)\\&=\frac{E(X_{i-1})+1}{1-P_i}\\&=\frac{y_i(E(X_{i-1})+1)}{y_i-x_i}\end{aligned} E(Xi?)?=(1?Pi?)(E(Xi?1?)+1)+Pi?(E(Xi?)+E(Xi?1?)+1)=1?Pi?E(Xi?1?)+1?=yi??xi?yi?(E(Xi?1?)+1)????赛委组是跟J a v a \mathrm{Java} Java 有仇吗，根本不是一个难度。

#include int n, E[100001], p = 998244353; long long x, y; int qpow(int a, int b) { long long res = 1; while (b) { if (b & 1) res = res * a % p; a = (long long)a * a % p; b >>= 1; } return res; }int main() { scanf("%d", &n); for (int i = 1; i <= n; ++i) { scanf("%d %d", &x, &y); E[i] = y * qpow(y - x, p - 2) % p * (E[i - 1] + 1) % p; } printf("%d", E[n]); }

试题 F: 青蛙过河时间限制:1.0 s 1.0\mathrm s 1.0s?内存限制:256.0 M B 256.0\mathrm{MB} 256.0MB?本题总分： 15 15 15 分
【问题描述】
??小青蛙住在一条河边，它想到河对岸的学校去学习。小青蛙打算经过河里的石头跳到对岸。
??河里的石头排成了一条直线，小青蛙每次跳跃必须落在一块石头或者岸上。不过，每块石头有一个高度，每次小青蛙从一块石头起跳，这块石头的高度就会下降1 1 1，当石头的高度下降到0 0 0 时小青蛙不能再跳到这块石头上 ( ( (某次跳跃后使石头高度下降到0 0 0 是允许的 ) ) )。
??小青蛙一共需要去学校上x x x 天课，所以它需要往返2 x 2x 2x 次。当小青蛙具有一个跳跃能力y y y 时，它能跳不超过y y y 的距离。
??请问小青蛙的跳跃能力至少是多少才能用这些石头上完x x x 次课。
【输入格式】
??输入的第一行包含两个整数n , x n, x n,x，分别表示河的宽度和小青蛙需要去学校的天数。请注意2 x 2x 2x 才是实际过河的次数。
??第二行包含n ? 1 n ? 1 n?1 个非负整数H 1 , H 2 , ? ? , H n ? 1 H_1, H_2,\cdots, H_{n?1} H1?,H2?,?,Hn?1?，其中H i > 0 H_i > 0 Hi?>0 表示在河中与小青蛙的家相距i i i 的地方有一块高度为H i H_i Hi? 的石头， H i = 0 H_i = 0 Hi?=0 表示这个位置没有石头。
【输出格式】
??输出一行，包含一个整数，表示小青蛙需要的最低跳跃能力。
【样例输入】

5 1 1 0 1 0

【样例输出】

4

【样例解释】
??由于只有两块高度为1 1 1 的石头，所以往返只能各用一块。第1 1 1 块石头和对岸的距离为4 4 4，如果小青蛙的跳跃能力为3 3 3 则无法满足要求。所以小青蛙最少需要4 4 4 的跳跃能力。
【评测用例规模与约定】
??对于30 % 30\% 30% 的评测用例， n ≤ 100 n ≤ 100 n≤100；
??对于60 % 60\% 60% 的评测用例， n ≤ 1000 n ≤ 1000 n≤1000；
??对于所有评测用例， 1 ≤ n ≤ 1 0 5 , 1 ≤ x ≤ 1 0 9 , 1 ≤ H i ≤ 1 0 4 1 ≤ n ≤ 10^5, 1 ≤ x ≤ 10^9, 1 ≤ H^i ≤ 10^4 1≤n≤105,1≤x≤109,1≤Hi≤104。
二分 + 贪心 ??跳跃能力增加下，可以往返河的次数呈单调不下降，故考虑二分跳跃能力m i d \mathrm{mid} mid，转为跳跃能力在m i d \mathrm{mid} mid 下能否往返2 x 2x 2x 天的判断问题。
??首先一条从对岸到学校的有向路径取反后即为一条从学校到对岸的有向路径，故只需判断单向是否可达2 x 2x 2x 次，
??对于一条从0 0 0 到n n n 路径，位置在i i i 上的石头，若选择处于j j j 处位置大于i i i 石头折返，路径数一定不大于先到i i i 再到j j j，若选择从位置比i i i 小的j ′ j' j′ 处跳跃到i i i， j ′ j' j′ 越小最终的路径数越大，因为较小的j ′ j' j′ 会最先称为不可选方案。
??故考虑遍历每一个i i i，同时维护一个单调队列按序号存放石头，最开始里面存放着H 0 = i n f H_0 = \mathrm{inf} H0?=inf，对于每一个H i H_i Hi?，我们先踢出位置小于i ? m i d i - \mathrm{mid} i?mid 的石头，新建一个临时石头H k = 0 H_k = 0 Hk?=0，然后编号小到大的H j H_j Hj?，若H j ≤ H i ? H k H_j \leq H_i - H_k Hj?≤Hi??Hk?，则将H k H_k Hk? 加上一个H j H_j Hj?，将H j H_j Hj? 踢出队列，若H j > H i ? H k H_j > H_i - H_k Hj?>Hi??Hk?，则将H j H_j Hj? 减去H i ? H k H_i - H_k Hi??Hk?，重复此步直至队列为空或H i = H k H_i = H_k Hi?=Hk?，最后将H k H_k Hk? 入列，其编号为i i i，进入下一轮枚举，
??最终队列中的石头之和即是跳跃能力为m i d \mathrm{mid} mid 可走的次数。

#include const int N = 100010; int n, x, l, r, H[N], S[N], V[N]; int main() { scanf("%d %d", &n, &x); for (int i = 1; i < n; ++i) scanf("%d", &H[i]); int left = 1, right = n, Hk, mid, buf; while (left < right) { mid = left + right >> 1; l = 0, r = 0, V[0] = 0x3F3F3F3F; for (int i = 1; i < n; ++i) if (H[i]) { while (l <= r && S[l] < i - mid) ++l; Hk = 0; while (l <= r && Hk < H[i]) if (V[l] <= H[i] - Hk) Hk += V[l++]; else V[l] -= H[i] - Hk, Hk = H[i]; if (Hk) S[++r] = i, V[r] = Hk; } while (l <= r && S[l] < n - mid) ++l; for (buf = 0; l <= r; ) buf += V[l++]; if (buf >= 2 * x) right = mid; else left = mid + 1; } printf("%d", left); }

试题 G: 最长不下降子序列时间限制:1.0 s 1.0\mathrm s 1.0s?内存限制:256.0 M B 256.0\mathrm{MB} 256.0MB?本题总分： 20 20 20 分
【问题描述】
??给定一个长度为N N N 的整数序列： A 1 , A 2 , ? ? , A N ：A_1, A_2,\cdots, A_N ：A1?,A2?,?,AN?。现在你有一次机会，将其中连续的K K K 个数修改成任意一个相同值。请你计算如何修改可以使修改后的数列的最长不下降子序列最长，请输出这个最长的长度。
??最长不下降子序列是指序列中的一个子序列，子序列中的每个数不小于在它之前的数。
【输入格式】
??输入第一行包含两个整数N N N 和K K K。
??第二行包含N N N 个整数A 1 , A 2 , ? ? , A N A_1, A_2,\cdots, A_N A1?,A2?,?,AN?。
【输出格式】
??输出一行包含一个整数表示答案。
【样例输入】

5 1 1 4 2 8 5

【样例输出】

4

【评测用例规模与约定】
??对于20 % 20\% 20% 的评测用例， 1 ≤ K ≤ N ≤ 100 1 ≤ K ≤ N ≤ 100 1≤K≤N≤100；
??对于30 % 30\% 30% 的评测用例， 1 ≤ K ≤ N ≤ 1000 1 ≤ K ≤ N ≤ 1000 1≤K≤N≤1000；
??对于50 % 50\% 50% 的评测用例， 1 ≤ K ≤ N ≤ 10000 1 ≤ K ≤ N ≤ 10000 1≤K≤N≤10000；
??对于所有评测用例， 1 ≤ K ≤ N ≤ 1 0 5 ， 1 ≤ A i ≤ 1 0 6 1 ≤ K ≤ N ≤ 10^5，1 ≤ A_i ≤ 10^6 1≤K≤N≤105，1≤Ai?≤106。
动态规划 ??首先逆序单调栈d p \mathrm{dp} dp 出f i f_i fi?，其含义为以A i A_i Ai? 开始的最长递增子序列，最长是多少，然后顺序单调栈d p \mathrm{dp} dpA [ 1 , i ] A[1,i] A[1,i] 中的最长递增子序列，此时栈中自底向上低j j j 个元素表示长度为j j j 的递增子序列，最后一个元素最小可以为多少，遍历的每一个i i i，我们在栈中二分查找最后一个不大于A i + k A_{i+k} Ai+k? 的元素位置j j j，并尝试用f i + k + j + k f_{i+k}+j+k fi+k?+j+k 更新答案。
??一开始我想的是两遍d p \mathrm{dp} dp 后枚举每对f i , g i + k f_i,g_{i+k} fi?,gi+k?，但仔细一琢磨，有陷阱兄弟们。

#include #include int n, k, ans, top, A[100001], S[100010], f[100001]; int max(int a, int b) { return a > b ? a : b; }int main() { scanf("%d %d", &n, &k); if (n == k || n == 1) {printf("%d", n); return 0; } for (int i = 1; i <= n; ++i) scanf("%d", &A[i]); for (int i = n; i > k; --i) { int k = std::upper_bound(S, S + top, -A[i]) - S; if (k == top) ++top; S[k] = -A[i]; f[i] = k; } top = 0; for (int i = 1; i <= n - k; ++i) { ans = max(ans, f[i + k] + std::lower_bound(S, S + top, A[i + k]) - S); int k = std::upper_bound(S, S + top, A[i]) - S; if (k == top) ++top; S[k] = A[i]; } printf("%d", max(top, ans + 1) + k ); }

试题 H: 扫描游戏时间限制:1.0 s 1.0\mathrm s 1.0s?内存限制:256.0 M B 256.0\mathrm{MB} 256.0MB?本题总分： 20 20 20 分
【问题描述】
??有一根围绕原点O O O 顺时针旋转的棒O A OA OA，初始时指向正上方( Y (\mathrm Y (Y 轴正向 ) ) )。在平面中有若干物件，第i i i 个物件的坐标为( x i , y i ) (x_i, y_i) (xi?,yi?)，价值为z i z_i zi?。当棒扫到某个物件时，棒的长度会瞬间增长z i z_i zi?，且物件瞬间消失( ( (棒的顶端恰好碰到物件也视为扫到 ) ) )，如果此时增长完的棒又额外碰到了其他物件，也按上述方式消去( ( (它和上述那个点视为同时消失 ) ) )。
??如果将物件按照消失的时间排序，则每个物件有一个排名，同时消失的物件排名相同，请输出每个物件的排名，如果物件永远不会消失则输出? 1 ?1 ?1。
【输入格式】
??输入第一行包含两个整数n 、 L n、L n、L，用一个空格分隔，分别表示物件数量和棒的初始长度。
??接下来n n n 行每行包含第三个整数x i , y i , z i x_i, y_i, z_i xi?,yi?,zi?。
【输出格式】
??输出一行包含n n n 整数，相邻两个整数间用一个空格分隔，依次表示每个物件的排名。
【样例输入】

5 2 0 1 1 0 3 2 4 3 5 6 8 1 -51 -33 2

【样例输出】

1 1 3 4 -1

【评测用例规模与约定】
??对于30 % 30\% 30% 的评测用例， 1 ≤ n ≤ 500 1 ≤ n ≤ 500 1≤n≤500；
??对于60 % 60\% 60% 的评测用例， 1 ≤ n ≤ 5000 1 ≤ n ≤ 5000 1≤n≤5000；
??对于所有评测用例， 1 ≤ n ≤ 200000 ， ? 1 0 9 ≤ x i , y i ≤ 1 0 9 ， 1 ≤ L , z i ≤ 1 0 9 1 ≤ n ≤ 200000，?10^9 ≤ x_i, y_i ≤ 10^9，1 ≤ L,z_i ≤ 10^9 1≤n≤200000，?109≤xi?,yi?≤109，1≤L,zi?≤109。
大模拟 ??经典 H 题出大模拟。
??为了降低搜索的复杂度，我们需要将每一对( x i , y i ) (x_i,y_i) (xi?,yi?) 视为向量，将它们按与y y y 的正半轴的夹角进行排序，但cos ? \cos cos 函数具有周期性，这使得我们很难能避免在比较夹角时先不按象限划分，而且向量夹角的计算公式cos ? θ = x ? y ∣ x ∣ ∣ y ∣ \cos\theta = \cfrac{x\cdot y}{|x||y|} cosθ=∣x∣∣y∣x?y? 还涉及到除法和开方的精度问题，所以，我们将一、二、三、四象限重排为0 0 0、 3 3 3、 2 2 2、 1 1 1 象限，对于参与比较的两个向量，我们先排象限，若象限同则引用二维向量叉积的几何意义，向量( x 1 , y 1 ) (x_1,y_1) (x1?,y1?) 与( x 2 , y 2 ) (x_2,y_2) (x2?,y2?) 的叉乘记为( x 1 , y 1 ) × ( x 2 , y 2 ) = x 1 y 2 ? x 2 y 1 (x_1,y_1) × (x_2,y_2) = x_1y_2 - x_2y_1 (x1?,y1?)×(x2?,y2?)=x1?y2??x2?y1?，若值为0 0 0， ( x 1 , y 1 ) (x_1,y_1) (x1?,y1?) 与( x 2 , y 2 ) (x_2,y_2) (x2?,y2?) 共线，若值为正， ( x 1 , y 1 ) (x_1,y_1) (x1?,y1?) 在( x 2 , y 2 ) (x_2,y_2) (x2?,y2?) 逆时针方向，否则( x 1 , y 1 ) (x_1,y_1) (x1?,y1?) 在( x 2 , y 2 ) (x_2,y_2) (x2?,y2?) 顺时针方向，若两个向量共线则我们再排向量的长度。
??使用线段树来维护这样一个序列的最小值，则我们能在log ? n \log n logn 的复杂度下查找到O A OA OA 可能的，下一个扫到的物件。
??因为O A OA OA 下一个扫到的物件，只能是从O A OA OA 所在位置顺时针一圈中，第一个小于等于L L L 的物件，但是几何上的问题最麻烦还是精度，如若我们将物件距离和L L L 都平一次方，这一个物件的最远距离为2 × 1 0 18 2×10^{18} 2×1018，而L L L 的一次最大增长为1 0 18 10^{18} 1018，所以当L ≥ 2 × 1 0 18 L \geq 2×10^{18} L≥2×1018 时，剩下的所有未扫到的物件都可以按和O A OA OA 的夹角的次序被扫到，故而需要特判的一下这个地方，以免整形溢出使得最后计算出一个错误的被扫次序。

#include #include const int N = 2e5 + 9, inf = 1.42e9 + 5; typedef long long ll; ll mini[N << 2]; struct item { int x, y, z, idx; } items[N]; inline int quadrant(item &it) { if (it.x >= 0) { if (it.y >= 0) return 0; return 1; } if (it.y >= 0) return 3; return 2; }inline ll cross(item &it1, item &it2) { return (ll)it1.x * it2.y - (ll)it2.x * it1.y; }inline ll min(ll a, ll b) { return a < b ? a : b; }inline bool cmp(item &it1, item &it2) { if (quadrant(it1) != quadrant(it2)) return quadrant(it1) < quadrant(it2); if (cross(it1, it2) == 0) return (ll)it1.x * it1.x + (ll)it1.y * it1.y < (ll)it2.x * it2.x + (ll)it2.y * it2.y; return cross(it1, it2) < 0; }void push_up(int rt) { mini[rt] = min(mini[rt << 1], mini[rt << 1 | 1]); }void build(int rt, int l, int r) { if (l == r) mini[rt] = (ll)items[l].x * items[l].x + (ll)items[l].y * items[l].y; else { int mid = l + r >> 1; build(rt << 1, l, mid); build(rt << 1 | 1, mid + 1, r); push_up(rt); } }int query(int rt, int l, int r, int L, int R, ll k) { if (L > R) return 0; if (l == r) return mini[rt] <= k ? l : 0; int mid = l + r >> 1, res = 0; if (L <= mid && mini[rt << 1] <= k) res = query(rt << 1, l, mid, L, R, k); if (!res && R > mid && mini[rt << 1 | 1] <= k) return query(rt << 1 | 1, mid + 1, r, L, R, k); return res; }void update(int rt, int l, int r, int i) { if (l == r) mini[rt] = 2.1e18; else { int mid = l + r >> 1; if (i <= mid) update(rt << 1, l, mid, i); else update(rt << 1 | 1, mid + 1, r, i); push_up(rt); } }int n, L, cur, last, ans[N]{1}; int main() { scanf("%d %d", &n, &L); for (int i = 1; i <= n; ++i) scanf("%d %d %d", &items[i].x, &items[i].y, &items[i].z), items[i].idx = i; std::sort(items + 1, items + n + 1, cmp); build(1, 1, n); while(1) { int next = query(1, 1, n, last + 1, n, (ll)L * L); if (next == 0) next = query(1, 1, n, 1, last - 1, (ll)L * L); if (next) { if (quadrant(items[last]) == quadrant(items[next]) && cross(items[last], items[next]) == 0) ans[items[next].idx] = ans[items[last].idx], ++cur; else ans[items[next].idx] = ++cur; update(1, 1, n, next); L += items[next].z; last = next; } else break; if (L >= inf) L = inf; } for (int i = 1; i <= n; ++i) if (ans[i]) printf("%d ", ans[i]); else printf("-1 "); }

试题I: 数的拆分时间限制:1.0 s 1.0\mathrm s 1.0s?内存限制:256.0 M B 256.0\mathrm{MB} 256.0MB?本题总分： 25 25 25 分
【问题描述】
??给定T T T 个正整数a i a_i ai?，分别问每个a i a_i ai? 能否表示为x 1 y 1 ? x 2 y 2 x_1^{y_1}\cdot x_2^{y_2} x1y1???x2y2?? 的形式，其中x 1 , x 2 x_1, x_2 x1?,x2? 为正整数， y 1 , y 2 y_1, y_2 y1?,y2? 为大于等于2 2 2 的正整数。
【输入格式】
??输入第一行包含一个整数T T T 表示询问次数。
??接下来T T T 行，每行包含一个正整数a i a_i ai?。
【输出格式】
??对于每次询问, 如果a i a_i ai? 能够表示为题目描述的形式则输出y e s \mathrm{yes} yes，否则输出n o \mathrm{no} no。
【样例输入】

7 2 6 12 4 8 24 72

【样例输出】

no no no yes yes no yes

【样例说明】
??第4 , 5 , 7 4,5,7 4,5,7 个数分别可以表示为：：：
? a 4 = 2 2 × 1 2 a_4 = 2^2 × 1^2 a4?=22×12；
? a 5 = 2 3 × 1 2 a_5 = 2^3 × 1^2 a5?=23×12；
? a 7 = 2 3 × 3 2 a_7 = 2^3 × 3^2 a7?=23×32。
【评测用例规模与约定】
??对于10 % 10\% 10% 的评测用例， 1 ≤ T ≤ 200 ， a i ≤ 1 0 9 1 ≤ T ≤ 200，a_i ≤ 10^9 1≤T≤200，ai?≤109；
??对于30 % 30\% 30% 的评测用例， 1 ≤ T ≤ 300 ， a i ≤ 1 0 18 1 ≤ T ≤ 300，a_i ≤ 10^{18} 1≤T≤300，ai?≤1018；
??对于60 % 60\% 60% 的评测用例， 1 ≤ T ≤ 10000 ， a i ≤ 1 0 18 1 ≤ T ≤ 10000，a_i ≤ 10^{18} 1≤T≤10000，ai?≤1018；
??对于所有评测用例， 1 ≤ T ≤ 100000 ， 1 ≤ a i ≤ 1 0 18 1 ≤ T ≤ 100000，1 ≤ a_i ≤ 10^{18} 1≤T≤100000，1≤ai?≤1018。
分类讨论 ??若存在x 1 , y 1 , x 2 , y 2 x_1, y_1, x_2, y_2 x1?,y1?,x2?,y2?， x 1 , y 1 , x 2 , y 2 ∈ Z + x_1,y_1,x_2,y_2 \in\mathbb Z^+ x1?,y1?,x2?,y2?∈Z+， y 1 , y 2 ≥ 2 y_1,y_2 \geq 2 y1?,y2?≥2，使得a i a_i ai? 能被表示为x 1 y 1 ? x 2 y 2 x_1^{y_1}\cdot x_2^{y_2} x1y1???x2y2??，则a i a_i ai? 一定能被一个完全平方数整除，若y 1 y_1 y1? 为偶数，我们使x 1 y 1 x_1^{y_1} x1y1?? 变形为( x 1 y 1 2 ) 2 (x_1^{\frac {y_1}2})^2 (x12y1???)2，则该结论显然成立， y 1 , y 2 y_1,y_2 y1?,y2? 中至少有一个数为偶数的情况亦是同理，若y 1 , y 2 y_1,y_2 y1?,y2? 同为奇数，则y 1 , y 2 ≥ 3 y_1,y_2 \geq 3 y1?,y2?≥3，我们使x 1 y 1 ? x 2 y 2 x_1^{y_1}\cdot x_2^{y_2} x1y1???x2y2?? 变形为( x 1 ? y 1 2 ? x 2 ? y 2 2 ? ) 2 x 1 x 2 (x_1^{\lfloor\frac{y_1}2\rfloor}x_2^{\lfloor\frac{y_2}2\rfloor})^2x_1x_2 (x1?2y1????x2?2y2????)2x1?x2?，
??故有结论，若存在一个最大完全平方数b b b 能整除a i a_i ai?，则a i a_i ai? 能被表示为x 1 y 1 ? x 2 y 2 x_1^{y_1}\cdot x_2^{y_2} x1y1???x2y2?? 的充分必要条件是b b b 除a i a_i ai? 的商是b b b 的约数。
??虽然上述性质不足以支撑我们设计出一个复杂度优秀的算法，但它启发了我们，如果a i a_i ai? 不是完全平方数、完全立方数，则若a i a_i ai? 能表示为x 1 y 1 ? x 2 y 2 x_1^{y_1}\cdot x_2^{y_2} x1y1???x2y2??，它一定存在一个不大的质因子，这将会成为这道题目的突破口。
??若a i a_i ai? 不是完全平方数、完全立方数，则y 1 + y 2 ≥ 5 y_1 +y_2 \geq 5 y1?+y2?≥5 它才能表为x 1 y 1 ? x 2 y 2 x_1^{y_1}\cdot x_2^{y_2} x1y1???x2y2??，因为2 ≤ y 1 + y 2 < 5 2 \leq y_1 +y_2 < 5 2≤y1?+y2?<5 只当a i a_i ai? 是完全平方数、完全立方数才可表示，而当y 1 + y 2 ≥ 5 y_1 +y_2 \geq 5 y1?+y2?≥5 时a i a_i ai? 的最大质因子不会超过1 0 18 5 \sqrt[5]{10^{18}} 51018 ?，而上述结论完全可以转变为当a i a_i ai? 不存在指数为1 1 1 的质因子时， a i a_i ai? 能被表示为x 1 y 1 ? x 2 y 2 x_1^{y_1}\cdot x_2^{y_2} x1y1???x2y2??。
??于是乎，预处理出2 ～ 1 0 18 5 2 \sim \sqrt[5]{10^{18}} 2～51018 ? 间的质数，对于每一个a i a_i ai?，我们先对其开二次、三次根来判断它是否为完全平方、立方数，若不是则在2 ～ 1 0 18 5 2 \sim \sqrt[5]{10^{18}} 2～51018 ? 寻找它的质因子，若某个因子只存在一个则输出n o \mathrm{no} no、若无法使用这个区间的质数分解完a i a_i ai? 则输出n o \mathrm{no} no，其他情况均输出y e s \mathrm{yes} yes。

#include #include const int N = 3981; int T, b, m, primes[N]; bool factor[N + 1]; long long a; inline bool isTrivial(long long a) { long long t = pow(a, 0.5); if (t * t == a || (t + 1) * (t + 1) == a) return 1; t = pow(a, 1.0 / 3); if (t * t * t == a || (t + 1) * (t + 1) * (t + 1) == a || (t + 2) * (t + 2) * (t + 2) == a) return 1; return 0; }int main() { for (int i = 2; i <= N; ++i) if (!factor[i]) { primes[m++] = i; for (int j = i; j <= N; j += i) factor[j] = 1; } scanf("%d", &T); while (T--) { scanf("%lld", &a); if (isTrivial(a)) { printf("yes\n"); continue; } for (int i = 0; i < m; ++i) if (a % primes[i] == 0) { for (b = 0; a % primes[i] == 0; a /= primes[i], ++b); if (b == 1) { a = 0; break; } } if (a == 1) printf("yes\n"); else printf("no\n"); } }

??如果 dotcpp 上的数据是蓝桥官方的，那低能出题人卡 vector，黔驴技穷的样子可真像个小丑呢。
试题 J: 推导部分和时间限制:1.0 s 1.0\mathrm s 1.0s?内存限制:256.0 M B 256.0\mathrm{MB} 256.0MB?本题总分： 25 25 25 分
【问题描述】
??对于一个长度为N N N 的整数数列A 1 , A 2 , ? ? , A N A_1, A_2,\cdots,A_N A1?,A2?,?,AN?，小蓝想知道下标l l l 到r r r 的部分和∑ i = l r = A l + A l + 1 + ? + A r \sum_{i=l}^r= A_l + A_{l+1} +\cdots+ A_r ∑i=lr?=Al?+Al+1?+?+Ar? 是多少？
??然而，小蓝并不知道数列中每个数的值是多少，他只知道它的M M M 个部分和的值。其中第i i i 个部分和是下标l i l_i li? 到r i r_i ri? 的部分和∑ j = l i r i = A l i + A l i + 1 + ? + A r i \sum_{j=l_i}^{r_i}= A_{l_i} + A_{l_i+1} +\cdots+ A_{r_i} ∑j=li?ri??=Ali??+Ali?+1?+?+Ari?? 值是S i S_i Si?。
【输入格式】
??第一行包含3 3 3 个整数N 、 M N、M N、M 和Q Q Q。分别代表数组长度、已知的部分和数量和询问的部分和数量。
??接下来M M M 行，每行包含3 3 3 个整数l i , r i , S i l_i, r_i, S_i li?,ri?,Si?。
??接下来Q Q Q 行，每行包含2 2 2 个整数l l l 和r r r，代表一个小蓝想知道的部分和。
【输出格式】
??对于每个询问，输出一行包含一个整数表示答案。如果答案无法确定，输出U N K N O W N \mathrm{UNKNOWN} UNKNOWN。
【样例输入】

5 3 3 1 5 15 4 5 9 2 3 5 1 5 1 3 1 2

【样例输出】

15 6 UNKNOWN

【评测用例规模与约定】
??对于10 % 10\% 10% 的评测用例， 1 ≤ N , M , Q ≤ 10 ， ? 100 ≤ S i ≤ 100 1 ≤ N, M, Q ≤ 10，?100 ≤ S_i ≤ 100 1≤N,M,Q≤10，?100≤Si?≤100。
??对于20 % 20\% 20% 的评测用例， 1 ≤ N , M , Q ≤ 20 ， ? 1000 ≤ S i ≤ 1000 1 ≤ N, M, Q ≤ 20，?1000 ≤ S_i ≤ 1000 1≤N,M,Q≤20，?1000≤Si?≤1000。
??对于30 % 30\% 30% 的评测用例， 1 ≤ N , M , Q ≤ 50 ， ? 10000 ≤ S i ≤ 10000 1 ≤ N, M, Q ≤ 50，?10000 ≤ S_i ≤ 10000 1≤N,M,Q≤50，?10000≤Si?≤10000。
??对于40 % 40\% 40% 的评测用例， 1 ≤ N , M , Q ≤ 1000 ， ? 1 0 6 ≤ S i ≤ 1 0 6 1 ≤ N, M, Q ≤ 1000，?10^6 ≤ S_i ≤ 10^6 1≤N,M,Q≤1000，?106≤Si?≤106。
??对于60 % 60\% 60% 的评测用例， 1 ≤ N , M , Q ≤ 10000 ， ? 1 0 9 ≤ S i ≤ 1 0 9 1 ≤ N, M, Q ≤ 10000，?10^9 ≤ S_i ≤ 10^9 1≤N,M,Q≤10000，?109≤Si?≤109。
??对于所有评测用例， 1 ≤ N , M , Q ≤ 1 0 5 ， ? 1 0 12 ≤ S i ≤ 1 0 12 ， 1 ≤ l i ≤ r i ≤ N ， 1 ≤ l ≤ r ≤ N 1 ≤ N, M, Q ≤ 10^5，?10^{12} ≤ S_i ≤ 10^{12}，1 ≤ l_i ≤ r_i ≤ N，1 ≤ l ≤ r ≤ N 1≤N,M,Q≤105，?1012≤Si?≤1012，1≤li?≤ri?≤N，1≤l≤r≤N。数据保证没有矛盾。
树模型 ??对于每一组( l i , r i , S i ) (l_i,r_i,S_i) (li?,ri?,Si?)，我们是否能找到一种表示方法，将相关联的区间和用更一般的方式表示出来，显然这是可以的。
??对于每一组( l i , r i , S i ) (l_i,r_i,S_i) (li?,ri?,Si?)，我们将其视为l i ? 1 ? S i r i l_i-1\stackrel{S_i}{\longrightarrow} r_i li??1?Si??ri?、 r i ? ? S i l i ? 1 r_i\stackrel{-S_i}{\longrightarrow} l_i-1 ri???Si??li??1 上的有向边，一开始我们维护一个空图，读取完全部部分和后它可能会形成一片森林，对于每一个根节点l r t l_{rt} lrt?，我们做一遍深度优先遍历，下传边权同时对它的子树染色，最后每一个子节点r s o n r_{son} rson?，都维护着∑ i = l r t + 1 r s o n \sum_{i=l_{rt}+1}^{r_{son}} ∑i=lrt?+1rson?? 的信息，对于每一个查询l , r l,r l,r，若l ? 1 l-1 l?1和r r r 颜色相同，则r r r 节点维护的信息减去l ? 1 l-1 l?1 所维护的信息，即是这段区间和，否则无法确定这段区间和。
【蓝桥杯|第十三届蓝桥杯大赛软件赛省赛（C/C++ 大学A组）】??整个过程可以视作不断的在做部分和的部分和，正确性是显然的，主要我不会证。

#include const int N = 100001, M = 100001; long long S, next[M << 1], val[M << 1], sum[N]; int n, m, q, l, r, cur, linked[N], color[N], ver[M << 1]; void link(int u, int v, long long w) { next[++cur] = linked[u], linked[u] = cur, ver[cur] = v, val[cur] =w; next[++cur] = linked[v], linked[v] = cur, ver[cur] = u, val[cur] = -w; }void dfs(int rt, int clr) { if (color[rt]) return; color[rt] = clr; for (int i = linked[rt]; i; i = next[i]) sum[ver[i]] = val[i] + sum[rt], dfs(ver[i], clr); }int main() { scanf("%d %d %d", &n, &m, &q); while (m--) scanf("%d %d %lld", &l, &r, &S), link(l - 1, r, S); for (int i = 0; i <= n; ++i) if (!color[i]) dfs(i, ++cur); while (q--) { scanf("%d %d", &l, &r); if (color[l - 1] == color[r]) printf("%lld\n", sum[r] - sum[l - 1]); else printf("UNKNOWN\n"); } }