One more time, One more chance - Uru ♪

本题总分： 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′ printf("%d", n * m + 3); } 试题 B: 灭鼠先锋

本题总分： 5 5 5 分

【问题描述】

  灭鼠先锋是一个老少咸宜的棋盘小游戏，由两人参与，轮流操作。

  灭鼠先锋的棋盘有各种规格，本题中游戏在两行四列的棋盘上进行。游戏的规则为：两人轮流操作，每次可选择在棋盘的一个空位上放置一个棋子，或在同一行的连续两个空位上各放置一个棋子，放下棋子后使棋盘放满的一方输掉游戏。

  小蓝和小乔一起玩游戏，小蓝先手，小乔后手。小蓝可以放置棋子的方法很多，通过旋转和翻转可以对应如下四种情况 ： ： ：

  X O O O \mathrm{XOOO} XOOO X X O O \mathrm{XXOO} XXOO O X O O \mathrm{OXOO} OXOO O X X O \mathrm{OXXO} OXXO   O O O O \mathrm{OOOO} OOOO O O O O \mathrm{OOOO} OOOO O O O O \mathrm{OOOO} OOOO O 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

  标题应该起博弈论的，但我代码都写完了就懒得改了。

  根据公平组合游戏定理有 ： ： ：

   1 ) ： 1)： 1)：没有后继状态的状态是必败状态。    2 ) ： 2)： 2)：一个状态是必胜状态，当且仅当存在至少一个必败状态为它的后继状态。    3 ) ： 3)： 3)：一个状态是必败状态，当且仅当它的所有后继状态均为必胜状态。

  显然棋盘被放满是一个必胜状态，以它作为递归函数出口，然后根据公平组合游戏定理递归就行。

时间限制: 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，表示所求的和。请使用合适的数据类型进行运算。

【样例输入】

【样例输出】

【评测用例规模与约定】

  对于 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​

时间限制: 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。

【样例输入】

【样例输出】

【样例说明】   显然整个数列中只有 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≤xi∣Ai​=Ar​⊕x}}

  不太对，感觉我在乱压行。

时间限制: 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 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 scanf("%d %d", &n, &x); for (int i = 1; i while (l scanf("%d %d", &n, &k); if (n == k || n == 1) {printf("%d", n); return 0;} for (int i = 1; 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 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 mini[rt] = min(mini[rt int mid = l + r >> 1; build(rt if (l == r) mini[rt] = 2.1e18; else { int mid = l + r >> 1; if (i scanf("%d %d", &n, &L); for (int i = 1; i 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 for (int i = 2; i scanf("%lld", &a); if (isTrivial(a)) { printf("yes\n"); continue; } for (int i = 0; i a = 0; break; } } if (a == 1) printf("yes\n"); else printf("no\n"); } }

  如果 dotcpp 上的数据是蓝桥官方的，那低能出题人卡 vector，黔驴技穷的样子可真像个小丑呢。

时间限制: 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。

【样例输入】

【样例输出】

【评测用例规模与约定】

  对于 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 所维护的信息，即是这段区间和，否则无法确定这段区间和。

  整个过程可以视作不断的在做部分和的部分和，正确性是显然的，主要我不会证。