2018-2019 ACM-ICPC, Asia Nakhon Pathom Regional Contest(Gym 102091)

来自PC Wiki
跳到导航 跳到搜索

Solutions

A(Solved by : sqc & lzy)

按高度从高到低,每次将区间中最高点给选出来,然后将左右能连边的区间看成虚点,从最高点向虚点连边,再从虚点向该区间中最高点连边;

这样就变成了一个分层的$$DAG$$,奇数层虚点(第$$1$$层为超级根),偶数层实点;

这个玩意的结构很类似树,所以我们可以用类似搞树的方法搞这个

然后直接统计每个点的深度和每个子$$DAG$$的最深深度

然后询问直接用深度搞就行,特别地需要判一下是否属于同一棵子树

Code:tr1_A

B(Unsolved)

C(Solved by : lzy)

签到题

Code:tr1_C

D(Solved by : lzy)

签到题

Code:tr1_D

E(Upsolved by : sqc)

写法不优就很容易写挂的题目。。。

考虑$$dp[i][j]$$表示$$DP$$到值为$$i$$,用了$$j$$次机会的最长长度

然后讨论转移就行了

注意枚举数字时候不要枚举值,枚举每一个数字会更好写

Code: tr1_E

F(Solved by : zhn)

类似数位dp的题目,题意是杨辉三角前N行中7的倍数的个数,即$$\sum_{n=1}^N \sum_{i=1}^n{[C^i_n \mod \, 7 = 0]}$$

用lucas定理,可发现是考虑n=1~N在七进制下小于等于n且存在某一位大于n的当前位的数的个数,通过简单容斥和数位统计技巧来做即可

不是很好写

Code: tr1_F

G(Solved by : sqc)

$$SCC$$模板题

Code: tr1_G

H(Solved by : sqc)

观察榜可以发现一些奥妙重重的东西 答案不会超过$$2^{21}$$,暴力枚举+check

Code: tr1_H

I(Upsolved by : sqc)

考虑题目所给性质,大概是连通的方块是凸的

然后考虑每加进去一个新的方块会产生多少新的矩形

设当前位置为$$(i,j)$$,记录当前列$$j$$上端为$$U[j]$$,下端为$$D[j]$$,当前行$$i$$左端为$$L[i]$$,右端为$$R[i]$$

则产生的新的矩形数目为$$[U[j],D[j]] * [L[i],R[i]]$$中的已经染色的格子数目

二维树状数组维护

Code:tr1_I

J(Solved by : lzy)

考虑利用三次方差因式分解提出一个$$1e-15$$,然后单独统计前面的部分

这样会被卡常

忽略高阶的$$1e-15$$就能过了

Code:tr1_J

K(Solved by : lzy)

动态维护第k小数字的线段树

Code:tr1_K

L(Solved by : sqc)

二分边长,二维前缀和check

卡读入,需要fastio

Code:tr1_L

Records