1010 Reports
签到，略。
1003 Express Mail Taking
简单贪心，先往右边走，然后逐步往左边走。
1007 CCPC Training Class
答案就是出现次数最多的字符出现的次数。
1011 3×3 Convolution
容易发现只有当
K
1
,
1
=
1
K_{1, 1} = 1
K1,1=1 时输出和原矩阵相同，否则一定会收敛到
O
O
O。
1006 Robotic Class
题意：定义
n
n
n 个分段函数，每个函数形如
f
(
t
,
x
)
=
{
f
(
d
t
,
0
,
c
t
,
0
x
+
b
t
,
0
)
x
≤
a
t
,
0
f
(
d
t
,
1
,
c
t
,
1
x
+
b
t
,
1
)
a
t
,
0
<
x
≤
a
t
,
1
⋮
f
(
d
t
,
k
t
−
1
,
c
t
,
k
t
−
1
x
+
b
t
,
k
t
−
1
)
a
t
,
k
t
−
2
<
x
≤
a
t
,
k
t
−
1
f
(
d
t
,
k
t
,
c
t
,
k
t
x
+
b
t
,
k
t
)
a
t
,
k
t
−
1
<
x
f(t, x) = \begin{cases} f\left(d_{t, 0}, c_{t, 0}x +b_{t, 0}\right)& x \le a_{t, 0} \\ f\left(d_{t, 1}, c_{t, 1}x +b_{t, 1}\right) & a_{t, 0}<x \le a_{t, 1} \\ & \vdots \\ f\left(d_{t, k_t – 1}, c_{t, k_t – 1}x +b_{t, k_t – 1}\right) & a_{t, k_t – 2}<x \le a_{t, k_t – 1} \\ f\left(d_{t, k_t}, c_{t, k_t}x +b_{t, k_t}\right) & a_{t, k_t – 1}<x \\ \end{cases}
f(t,x)=⎩⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎧f(dt,0,ct,0x+bt,0)f(dt,1,ct,1x+bt,1)f(dt,kt−1,ct,kt−1x+bt,kt−1)f(dt,kt,ct,ktx+bt,kt)x≤at,0at,0<x≤at,1⋮at,kt−2<x≤at,kt−1at,kt−1<x
t
t
t 之间形成一个 DAG，只有
n
n
n 没有出边，其中
f
(
n
,
x
)
=
x
f(n, x) = x
f(n,x)=x。问
∀
1
≤
i
≤
n
\forall 1 \le i \le n
∀1≤i≤n，
f
(
i
,
x
)
f(i, x)
f(i,x) 是否是连续函数。
显然可以在
O
(
n
log
n
)
O(n \log n)
O(nlogn) 时间内用二分计算出任意的
f
(
t
,
x
)
f(t, x)
f(t,x)。
假设现在要验证
f
(
t
,
x
)
f(t, x)
f(t,x) 的连续性，如果对于任意的
i
i
i，
f
(
d
t
,
i
,
x
)
f(d_{t, i}, x)
f(dt,i,x) 都是连续函数，那么只要检查在分段的边界上
f
(
t
,
x
)
f(t, x)
f(t,x) 是否连续即可，即是否有对于任意的
i
i
i，有
f
(
d
t
,
i
,
c
t
,
i
a
t
,
i
+
b
t
,
i
)
=
f
(
d
t
,
i
+
1
,
c
t
,
i
+
1
a
t
,
i
+
b
t
,
i
+
1
)
f\left(d_{t, i}, c_{t, i}a_{t, i} + b_{t, i}\right)= f\left(d_{t, i+1}, c_{t, i+1}a_{t, i} + b_{t, i+1}\right)
f(dt,i,ct,iat,i+bt,i)=f(dt,i+1,ct,i+1at,i+bt,i+1)。
时间复杂度
O
(
T
n
K
log
n
)
,
K
=
∑
t
k
t
O(TnK\log n), K = \sum_t k_t
O(TnKlogn),K=∑tkt。
1005 Lunch
题意：有
n
n
n 堆石子，每次可以选择一个数目
l
>
1
l>1
l>1 的堆，将其分割为
k
>
1
k>1
k>1 个数目为
l
k
\frac{l}{k}
kl 的堆。所有堆均为
1
1
1 时当前玩家输。问先手是否必胜。
我好像只会打表找规律…
规律就是每个数的 SG 值为其所有奇质因子次幂的和，如果该数是偶数就还要加一。
1002 Graph Theory Class
题意：给定
[
2
,
n
+
1
]
[2, n+1]
[2,n+1] 这
n
n
n 个整数，两个数
i
,
j
i, j
i,j 的边权为
lcm
(
i
,
j
)
\operatorname{lcm}(i, j)
lcm(i,j)，求最小生成树。
考虑每个数应该和谁连边。直觉是每个数和其最大的约数连边，质数连
2
2
2。那么答案就是
[
2
,
n
+
1
]
[2, n+1]
[2,n+1] 求和然后再加所有范围内质数的和，最后减掉多算的 4。于是用 min_25 筛即可。
1012 Xor
原题题意够简单了，不叙述。
说起来这还是一个原题，Comet OJ Contest 12 出过。不妨去看那一题的解法。
1013 Residual Polynomial
题意：给定一个初始多项式
f
1
(
x
)
=
∑
i
=
0
n
a
i
x
i
f_1(x)= \sum_{i=0}^{n}a_i x^i
f1(x)=∑i=0naixi，对于
2
≤
i
≤
n
2\le i\le n
2≤i≤n，有
f
i
(
x
)
=
b
i
f
i
−
1
′
(
x
)
+
c
i
f
i
−
1
(
x
)
f_i(x) = b_i f_{i-1}'(x) + c_if_{i-1}(x)
fi(x)=bifi−1′(x)+cifi−1(x)。求
f
n
(
x
)
f_n(x)
fn(x) 的系数。
设
e
i
e_i
ei 为
∏
i
=
2
n
(
b
i
+
c
i
)
\prod_{i=2}^{n} (b_i + c_i)
∏i=2n(bi+ci) 中，含有
i
i
i 个
c
c
c 的项之和（或者说，设
e
i
e_i
ei 为
∏
i
=
2
n
(
b
i
+
c
i
x
)
\prod_{i=2}^{n} (b_i + c_ix)
∏i=2n(bi+cix) 中，
x
i
x^i
xi 的系数）。那么有：
f
n
(
x
)
=
∑
i
=
0
n
−
1
e
n
−
i
−
1
f
1
(
i
)
(
x
)
f_n(x) = \sum_{i = 0}^{n-1}e_{n – i – 1}f^{(i)}_1(x)
fn(x)=i=0∑n−1en−i−1f1(i)(x)
设
f
n
(
x
)
=
∑
i
=
0
n
w
i
x
i
f_n(x) = \sum_{i=0}^{n}w_i x^i
fn(x)=∑i=0nwixi。展开发现
i
!
w
i
=
∑
j
+
k
=
i
+
n
−
1
e
j
k
!
a
k
i! w_i = \sum_{ j + k = i + n – 1} e_{j} k!a_k
i!wi=j+k=i+n−1∑ejk!ak
后面这个是一个简单的卷积。前面
e
e
e 怎么求？考虑分治，先求
[
l
,
m
i
d
]
,
[
m
i
d
+
1
,
r
]
[l, mid], [mid + 1, r]
[l,mid],[mid+1,r] 两部分的
e
e
e，然后用一个卷积合并这两个部分即可。
时间复杂度为
O
(
n
log
2
n
)
O(n\log^2 n)
O(nlog2n)。
1004 Chess Class
待补。。。
1001 Art Class
待补。。。
1008 PE Class
待补。。。
1009 Math Class
待补。。。
小结
另，jls 已经在知乎相关回答贴了题解，想看更 official 的题解可以移步那里。
原创：https://www.panoramacn.com
源码网提供WordPress源码,帝国CMS源码discuz源码,微信小程序,小说源码,杰奇源码,thinkphp源码,ecshop模板源码,微擎模板源码,dede源码,织梦源码等。
专业搭建小说网站,小说程序,杰奇系列,微信小说系列,app系列小说
免责声明,若由于商用引起版权纠纷,一切责任均由使用者承担。
您必须遵守我们的协议，如果您下载了该资源行为将被视为对《免责声明》全部内容的认可-> 联系客服 投诉资源
评论抢沙发