whu_begin

武汉大学2020年新生程序设计竞赛

你好,ACM!

现在是新的开始,我再次选择了你——算法竞赛。

希望你不要不识抬举!

希望这场不顺心的始动赛可以成为我大学 ACM 生涯的最低点,让我从这里开始,再重新慢慢变强!

胜败兵家事不期,卷土重来未可知!


A

坑死我的出锅题((数据出现负数

排序,最便宜的最后一次买即可。

小心一点的话不要乘 0.7 而是整体乘 10 以避免爆精度。


B

考虑一个简单的情形:询问公差为 11 的等差数列。

我们不妨考虑在 i,ji,j 的两个数字 ai,aja_i,a_j 在同一轮被相邻的选择的条件:

i<j,ai+1=aji<j,a_i+1=a_j

显然后者的条件限制更强大,因此不妨构建数列 {pi}\{p_i\} ,令 pai=ip_{a_i}=i,这样原问题就转化成了更加好处理的形式:

统计 {pi}\{p_i\} 的最长上升字串个数,即为答案

然后我们加入修改

一个自然的想法是当 knk\ge \sqrt n 时暴力处理,也就是值域分块

那么对每个 ini\le \sqrt n 维护一个答案数组 did_i

当两者交换时,我们发现只需要考虑被交换位置的前后位置即可快速 O(1)O(1) 处理出交换后的答案

事实上写起来情况比较复杂

复杂度 O(nn)O(n\sqrt n)


C

扫描一遍即可


D

就是滑动窗口,维护两个单调移动的指针 l,rl,r 始终框住最大的合法的区间即可

考场觉得二分更好写而且应该卡不掉,就写了二分


E

前面还有几个图,题意无关,不贴了

3s,强制在线 ,分块它不香吗#狗头

对每个块 i,ji,j 维护答案数组 ansi,jans_{i,j} 表示区间为从 iijj 的这些块的答案

同时维护 fi,jf_{i,j} 表示在第 11ii 个块中 jj 出现次数

然后询问的时候,散点暴力加入,通过 fi,jf_{i,j} 直接 O(1)O(1) 计算贡献即可

复杂度 O(mn)O(m\sqrt n)


F

反正就是考虑重复的问题,与其考虑处理多算的或者少算的,不如直接暴力一起算了。

我们考虑对哪些 aa 的集合可能出现重复计算,然后直接算这个集合的总答案数。

同时,我们发现对任意一个同样大小的集合,这个大小的集合贡献答案数量是一样的。

对于一个集合 {a,a2,a3,,as}\{a,a^2,a^3,\dots,a^s\} 因为 asna^s\le n ,故集合大小最大为 1919

则我们的问题变成了对任意的 s19s\le 19 找到 {a,a2,a3,,am;(a2),(a2)2,(a2)3,,(a2)n;;(as),(as)2,(as)3,,(as)m}\{a,a^2,a^3,\dots,a^m;(a^2),(a^2)^2,(a^2)^3,\dots,(a^2)^n;\dots;(a^s),(a^s)^2,(a^s)^3,\dots,(a^s)^m\}中有多少个不同的数,对这个数列同时取对数,然后暴力统计即可

复杂度 O(Tnlogn)O(Tn\log n)


G

先状压一波是比较合理的想法,然后和 FF 类似的,我们惊奇的发现,对于每个大小的集合,答案统计起来都差不多的

首先找到所有点可以升级成技能 11 的那些集合 ss

然后对每个大小为 ii 的集合,进行一个朴素的背包

dpi,jdp_{i,j} 表示任学 ii 个技能消耗技能点为 jj 的方案数

复杂度 O(T(nms+n22n))O(T(nms+n^22^n)) 左右


H

img

因为 (1,1)(1,1) (n,n)(n,n) 不会被占据,所以题目要求就是在 (1,1)(1,1)(n,n)(n,n) 对角线两侧各选一个矩阵与边界连着,然后中间再选若干矩阵把这两个矩阵连在一起,这样就把路给堵住了

把矩阵抽象成点,你发现就是个最短路

但是这个题问题在连边上

我在考场写了个只要一个矩阵的某一个角在另一个矩阵里面,就相互连边

但是这样处理没有考虑十字形矩阵交,如下图

IMG_0311(20201124-005638).PNG

考虑了就可以了

因为考场在 wa 的题比较多,所以到最后也没把目光放回这个题目上来

UPT

矩形交应该拆维判断

对任何一维只要不交,矩形就不交

这样更容易扩展到高维情况


I

字符串忘干净了啊.jpg

回头一定补.jpg

本题大概是树上后缀数组的模板题

但是想写的话后缀数据结构都能写

但是我最近确实不太想把后缀数据结构捡起来

写过hash倍增暴力估计可以跑过去


J

不想多说.jpg

考场降智严重,写个暴力 n2n^2 狂 wa

考后随手五分钟写个 O(n)O(n) 一发入魂

启示:小心暴力!


不加代码存粹是懒.jpg

下次一定.jpg

  • Copyright: Copyright is owned by the author. For commercial reprints, please contact the author for authorization. For non-commercial reprints, please indicate the source.
  • Copyrights © 2020-2022 Dew
  • Visitors: | Views:

请我喝杯咖啡吧~

支付宝
微信