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′<i,1≤j′<j，
我们将
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 试题 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
SG 函数
标题应该起博弈论的，但我代码都写完了就懒得改了。
根据公平组合游戏定理有 ： ： ：
1
)
：
1)：
1)：没有后继状态的状态是必败状态。
2
)
：
2)：
2)：一个状态是必胜状态，当且仅当存在至少一个必败状态为它的后继状态。
3
)
：
3)：
3)：一个状态是必败状态，当且仅当它的所有后继状态均为必胜状态。
显然棋盘被放满是一个必胜状态，以它作为递归函数出口，然后根据公平组合游戏定理递归就行。
#include 试题 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。
【输入格式】
输入的第一行包含一个整数
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∑nai+a2⋅i=3∑nai+⋯+an−1⋅i=n∑nai
也就 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∑0ai+a2⋅i=1∑1ai+⋯+an⋅i=1∑n−1ai
#include 试题 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 不太对，感觉我在乱压行。
试题 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=yixi。
【输出格式】
输出一行包含一个整数表示答案，答案是一个有理数，请输出答案对质数
998244353
998244353
998244353 取模的结果。
其中有理数
a
b
\frac ab
ba 对质数
P
P
P 取模的结果是整数
c
c
c 满足
0
≤
c
<
P
0 ≤ c < P
0≤c<P 且
c
⋅
b
≡
a
(
m
o
d
P
)
c\cdot b\equiv a\pmod P
c⋅b≡a(modP)。
【样例输入 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<yi≤20；
对于
50
%
50\%
50% 的评测用例，
n
≤
500
，
1
≤
x
i
<
y
i
≤
200
n ≤ 500，1 ≤ x_i < y_i ≤ 200
n≤500，1≤xi<yi≤200；
对于所有评测用例，
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<yi≤109。
期望递推
设
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−PiE(Xi−1)+1=yi−xiyi(E(Xi−1)+1) 赛委组是跟
J
a
v
a
\mathrm{Java}
Java 有仇吗，根本不是一个难度。
#include 时间限制: 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。
二分最大流
可以将转成最大流模型，然后二分答案。
但应付 1 0 5 10^5 105 的数据还是显得捉襟见肘，
摆了，不写了。
试题 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}
dp
A
[
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 dotcpp 上卡了一个点，血压上来了。
试题 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。
不会，一碰几何我就摆。
试题 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。
试题 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=liri=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⟶Siri、
r
i
⟶
−
S
i
l
i
−
1
r_i\stackrel{-S_i}{\longrightarrow} l_i-1
ri⟶−Sili−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 所维护的信息，即是这段区间和，否则无法确定这段区间和。
整个过程可以视作不断的在做部分和的部分和，正确性是显然的，主要我不会证。
#include 欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）