link

T1 三值的排序

Problem

给出一个长为 nn 的、仅含 1,2,31,2,3 的序列 aia_i，求排序所需的最小交换次数（不要求相邻）。

100%→n≤1000100\% \rightarrow n\leq 1000

1s/128MB1\text{s}/128\text{MB}

Solution

提前预处理每个数值有几个，然后扫一遍所有 11 应当在的位置：

  • 如果扫到 11，不管。
  • 如果扫到 22，扫 22 应当在的位置。
    • 如果扫到了，交换，答案 +1+1。
    • 如果没扫到，扫在 33 应当在的位置，交换，答案 +1+1。
  • 如果扫到 33，类似于 22。

然后扫一遍 22 应当在的位置，操作类似于 11。

时间复杂度 O(n2)\mathcal{O}(n^2)。

Summary

出现了经典的复制下来然后后面忘了改后面的情况，100pts→90pts100\text{pts}\rightarrow 90\text{pts}。

T2 日记

Problem

求不超过 nn 的数中能表示成连续个 kk个的质数的和的最大数，无解输出 −1-1，多测。

100%→1≤T<2000,1≤n≤106,1≤k≤109100\% \rightarrow 1\leq T < 2000,1\leq n\leq 10^6,1\leq k\leq 10^9

1s/128MB1\text{s}/128\text{MB}

Solution

质数筛提前预处理质数做前缀和，然后对于每次询问二分质数中的位置，用差分查询区间和看有没有超过 nn。

时间复杂度 O(n+Tlog⁡(primesize−k))\mathcal{O}(n+T\log(\mathrm{primesize}-k))

Summary

100pts100\text{pts}

T3 切蛋糕

Problem

圆形蛋糕被切成 nn 块，每块蛋糕有权值 aia_i，A 先手拿蛋糕，然后 B, A 交替拿一块已拿蛋糕相邻的蛋糕，但 B 会拿权值最大的那一块，而 A 可以随意选择，最大化 A 拿到的蛋糕权值和，有 Subtask。

100%→1≤n≤2000,1≤ai≤109,ai are unique100\% \rightarrow 1\leq n\leq 2000,1\leq a_i\leq 10^9,a_i\text{ are unique}

2s/512MB2\text{s}/512\text{MB}

Solution

先断环成链复制一倍，显然可选蛋糕只能是已选蛋糕的两端，这样就可以做区间 DP。

设 fi,jf_{i,j} 为 A 先手获得的最大权值和，然后枚举 A 的选择来转移 B 的选择：

  • A 选择左边的蛋糕：
    • ai+1>aj→fi,j=max⁡fi+2,j+aia_{i+1} > a_j\rightarrow f_{i,j}=\max f_{i+2,j}+a_i B 之后会选择左边的蛋糕。
    • ai+1<aj→fi,j=max⁡fi+1,j−1+aia_{i+1} < a_j\rightarrow f_{i,j}=\max f_{i+1,j-1}+a_i B 之后会选择右边的蛋糕。
  • A 选择右边的蛋糕：
    • ai>aj−1→fi,j=max⁡fi+1,j−1+aja_i > a_{j-1}\rightarrow f_{i,j}=\max f_{i+1,j-1}+a_j B 之后会选择左边的蛋糕。
    • ai<aj−1→fi,j=max⁡fi,j−2+aja_i < a_{j-1}\rightarrow f_{i,j}=\max f_{i,j-2}+a_j B 之后会选择右边的蛋糕。

记搜转移即可，答案为 max⁡fi,i+n−1\max f_{i,i+n-1}。

时间复杂度 O(n2)\mathcal{O}(n^2)。

Summary

爆搜写挂了，考虑到是区间 DP 了转移想不出来了，没想到记搜，寄寄。 0pts0\text{pts}

T4 都市

Problem

给出 n(n−1)2\frac{n(n-1)}{2} 个数 bib_i，为长度为 nn 的原序列 aia_i 的两两数的和，求出所有可能的解。

解的顺序按字典序从大到小排序，解内的数按从小到大排序。

100%→1≤n≤300,1≤ai≤108100\% \rightarrow 1\leq n\leq 300,1\leq a_i\leq 10^8

1s/128MB1\text{s}/128\text{MB}

Solution

排序，显然 b1=a1+a2,b2=a1+a3b_1=a_1+a_2,b_2=a_1+a_3，然后在 bib_i 中枚举 a2+a3a_2+a_3，把这三个数删了，剩下的数中最小的肯定为 a1+a4a_1+a_4，通过 b1,b2,b3b_1,b_2,b_3 能把 aia_i 求出来，然后枚举前面的数看 a4+aia_4+a_i 在不在 bib_i 出现过，若没出现显然这个 a2+a3a_2+a_3 的方案不行，若出现就删掉，这样剩下的数中最小的又为 a1+a5a_1+a_5，以此类推。

怎么快速删数、找最小的数、看某个数是否出现过？std::multiset<int>！ STLの力は無限大です

时间复杂度 O(n2log⁡n)\mathcal{O}(n^2\log n)。

Summary

你猜题面有的地方为什么加粗（虽然我写的爆搜） 0pts0\text{pts}。

T5 街灯

Problem

给出长度为 nn 的序列 aia_i，mm 次询问区间 [l,r][l,r] 中，ai mod p=va_i\bmod p=v 的个数，其中 p,vp,v 每次询问时给出，无修。

30%→1≤n,m≤10330\% \rightarrow 1\leq n,m\leq 10^3

another 30%→p are the same\text{another } 30\%\rightarrow p\text{ are the same}

100%→1≤n,m≤105,0≤ai≤104,1≤p≤109100\% \rightarrow 1\leq n,m\leq 10^5,0\leq a_i\leq 10^4,1\leq p\leq 10^9

1s/128MB1\text{s}/128\text{MB}

Solution

3030 分暴力，6060 分莫队，也可以直接用下面 p>100p > 100 的做法。这才是设置这档分的目的吧

考虑到 aia_i 的值域比较小，提前将每个数的位置加入到这个数中的 vector 中，然后考虑根号分治：

  • p≤100p\leq 100：提前将每个数模 1∼1001\sim 100 以内的数的结果所对应的位置全加到对应模数和余数所对应的另一个 vector 中，询问的时候二分一下 vector 内部，区间差分一下结果就行了。
  • p>100p > 100：满足 ai mod p=va_i\bmod p=v 的数至多有 100100 个，考虑暴力枚举 v,p+v,2p+v…v,p+v,2p+v\dots，然后和 p≤100p\leq 100 一样的方式查询答案，不过是对一开始预处理的那个 vector 二分。

n,mn,m 同阶时时间复杂度 O(nnlog⁡n)\mathcal{O}(n\sqrt n\log n)。

Summary

莫队赢麻了。