【解题总结】2020 CCPC 网络选拔赛


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,0​x+bt,0​)f(dt,1​,ct,1​x+bt,1​)f(dt,kt​−1​,ct,kt​−1​x+bt,kt​−1​)f(dt,kt​​,ct,kt​​x+bt,kt​​)​x≤at,0​at,0​<x≤at,1​⋮at,kt​−2​<x≤at,kt​−1​at,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,i​at,i​+bt,i​)=f(dt,i+1​,ct,i+1​at,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=∑t​kt​。

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=0n​ai​xi,对于

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)=bi​fi−1′​(x)+ci​fi−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​+ci​x) 中,

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−1​en−i−1​f1(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=0n​wi​xi。展开发现

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∑​ej​k!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系列小说

【解题总结】2020 CCPC 网络选拔赛

免责声明,若由于商用引起版权纠纷,一切责任均由使用者承担。

您必须遵守我们的协议,如果您下载了该资源行为将被视为对《免责声明》全部内容的认可-> 联系客服 投诉资源
www.panoramacn.com资源全部来自互联网收集,仅供用于学习和交流,请勿用于商业用途。如有侵权、不妥之处,请联系站长并出示版权证明以便删除。 敬请谅解! 侵权删帖/违法举报/投稿等事物联系邮箱:2640602276@qq.com
未经允许不得转载:书荒源码源码网每日更新网站源码模板! » 【解题总结】2020 CCPC 网络选拔赛
关注我们小说电影免费看
关注我们,获取更多的全网素材资源,有趣有料!
120000+人已关注
分享到:
赞(0) 打赏

评论抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

您的打赏就是我分享的动力!

支付宝扫一扫打赏

微信扫一扫打赏