\[Codeforces Round \#323 (Div. 2)\]

传送门 >> http://codeforces.com/contest/583
更改等级规则后的第一场~
喜闻乐见地Div.1无望了qwq
AC Three problem without fst 2333,第四题脑补出奇怪算法,但没时间打了,也算过了吧er,然后第五题就不会了qwq
还是码一码题解…

A. Asphalting Roads

[Description]

平面上n*n的无色格点,依次进行n*n个操作,编号1~n*n.对于每个操作(x,y),若点(x,y)没有被染色,就将第x行和第y列所有点染色,否则不执行。
输出执行了的操作编号。
其中$n≤50$

[Solution]

桶。

B. Robot’s Task

[Description]

n台机器排成一行,破译第i台需要ai条信息。初始有k条信息,从机器1开始向右走,每破译一台机器就可获得一个信息,机器可以直走或转向,求破译所有机器至少要转向多少次,输入保证有解。
其中$n≤1000,0≤ai<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≤10^9$

[Solution]

离散化/贪心/堆。
我们发现,这些元素中最大值和第二大值一定存在于数组a.
选出他们放入a,然后就可去掉他们的gcd.
再选最大的元素,放入a,并去掉他们与之前两个数的gcd.

由此恢复数组a,需要离散化元素值。

D. Once Again…

[Description]

给出一个长度为n的数组,并循环T次产生新数组a,求a的最长不降子序列。
其中$n≤100,ai≤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]

还不会…看心情更…