Codeforces Round #323 (Div.2)

传送门 >> Codeforces Round #323 (Div. 2)
更改等级规则后的第一场~
喜闻乐见地Div.1无望了qwq
AC Three problem without fst 2333，第四题脑补出奇怪算法，但没时间打了，也算过了吧er，然后第五题就不会了qwq
还是码一码题解…

A. Asphalting Roads

  • [Description]
    平面上n∗nn*n的无色格点，依次进行n∗nn*n个操作，编号1−n∗n1-n*n.对于每个操作(x,y)，若点(x,y)没有被染色，就将第x行和第y列所有点染色，否则不执行。
    输出执行了的操作编号。
    其中n≤50n≤50
  • [Solution]
    桶。

B. Robot’s Task

  • [Description]
    n台机器排成一行，破译第i台需要ai条信息。初始有k条信息，从机器1开始向右走，每破译一台机器就可获得一个信息，机器可以直走或转向，求破译所有机器至少要转向多少次，输入保证有解。
    其中n≤1000,0≤ai＜nn≤1000,0≤a_i＜n
  • [Solution]
    模拟。
    模拟从1到n，n到1…直到全部破译的过程一定是最优的。

C. GCD Table

  • [Description]
    有一个长度为n的数组a，对应一个矩阵m，其中m[i][j]=gcd(a[i],a[j])，乱序给出n*n个元素，代表某个矩阵m里的所有数，要求回复数组a。保证有解。
    其中n≤500,ai≤109n≤500,a_i≤10^9
  • [Solution]
    离散化/贪心/堆。
    我们发现，这些元素中最大值和第二大值一定存在于数组a.
    选出他们放入a，然后就可去掉他们的gcd.
    再选最大的元素，放入a，并去掉他们与之前两个数的gcd.
    …
    由此恢复数组a，需要离散化元素值。

D. Once Again…

  • [Description]
    给出一个长度为n的数组，并循环T次产生新数组a，求a的最长不降子序列。
    其中n≤100,ai≤300,T≤107n≤100,a_i≤300,T≤10^7
  • [Solution]
    乱搞。
    当T≤200可以直接求。
    当T>200，我们发现最长不降子序列中一定会出现循环重复的某个数，当T不断增大，也只是循环次数增多，最长不降子序列的“结构”并没有改变。算出最长的循环节长度x，对于T>200的，T每增加1，最长不降子序列就+=x，然后就可以算出最后的答案了。
    似乎矩阵加速DP也可以（这显然才是正解）。

E. Superior Periodic Subarrays

  • [Description]
    给出一个长度为n的数组，并将它重复无限次，得到无限数组a。我们用(l,s)表示a的一个合法子串，表示从l位置开始，长度为s的一个串，其中l,s<n。我们称一个合法子串是superior的，当且仅当将这个串重复无限次的到新无限串b，对于任意b中的元素a[i]，都满足a[l+i]≤b[i]。
    求a的所有superior的合法子串数。

  • [Solution]
    还不会…看心情更…

Comment