Logic
向着梦想进发
Logic's Blog

【题解】csp2021-J

蒟蒻只会J组的题了

T1 candy

取模运算实际上把自然数分成了很多类
本题实际上是求x属于[l, r]使得x % n最大
容易知道最理想的情况下x % n最大值为n - 1
所以我们只要判断能否取到n-1即可

  • 如果答案能取到n - 1,即存在x属于[l, r]使得x mod n = n - 1
    不妨设x = n · y - 1, y属于N*
    那么就有l <= n · y - 1 <= r
    解得(l + 1) / n <= y <= (l + 1) / n
    也就是说只要说明y存在那么x就一定存在
    即[(l + 1) / n, (r + 1) / n]中存在整数即可
  • 如果不能那么显然r点一定是最优解

AC代码

T2 sort

该题其实就是动态修改a数组,询问a[x]是数组中第?大的数(此处的大小要考虑数的下标),或者说是查询有多少数小于a[x]
所以正解就是树状数组加离散化
不过要注意几个细节

  • 因为修改的值也要离散化,所以要把所有数读入后再离线操作
  • 因为该题中所有数都不相等,所以离散化时所有数都都要不一样

AC代码

T3 network

不用解释,暴暴暴暴暴暴暴暴暴暴暴暴暴就行了
不过有几个好用的stl可以介绍一下
atoi(): char数组转int

to_string() : intstring

AC代码

T4 fruit

这题我调了4个小时

  • 可以用连通块维护本题中的块
    如果i-1,i在一个块中,那么把i-1,i连一条边
    考虑到一个数后面会接一个数,所以不用写邻接表或是链式前向星,只要开一个ne数组就可以了
  • 然后将每个连通块的第一个元素放入一个vector中
    这就是第一个篮子里的答案
    然后把vector中每个数变成对应联通块中的下一个元素,去掉不合法的(即没有出边的)点
  • 然后就是最头疼的地方了,如何合并两个块
    我的思路是使用并查集,其中的find(x)查找的是连通块的最后一个元素
    因为并查集可以非常容易的合并,并且拥有非常出色的时间复杂度,所以想到可以用并查集
    到这里,合并应该就容易想到了
    即: 将两个块在并查集中合并,并在前一个块的末尾元素加一条边到后一个块还没被使用的第一个元素
  • 最后用一个滚动数组实现一下转移就好了

AC代码

赞赏
本文作者: Logic
本文链接: https://i.needwe.top/csp2021-j2-solution/
本文采用 CC BY-NC-SA 4.0 Unported 协议进行许可

发表回复

textsms
account_circle
email

Logic's Blog

【题解】csp2021-J
蒟蒻只会J组的题了 T1 candy 取模运算实际上把自然数分成了很多类 本题实际上是求x属于[l, r]使得x % n最大 容易知道最理想的情况下x % n最大值为n - 1 所以我们只要判断能否取到n-1即可 …
扫描二维码继续阅读
2021-10-30