Atcoder ARC 125

A

(;)
细节题。一开始如果一样就能不动则不动。
然后特判一下是否只有1或0的情况,如果有解的话,之后的情况必定是在某个1和0交界的地方左右游走(有些抽象)

B

(;)

[x^2-y=c^2 ]

[(x+c)(x-c)=y ]

[x+c=a,x-c=b ]

[x=frac{a+b}{2} ]

所以对于(y)的一组因数(a,b),这里(ab=y)
相当于唯一对应着一个(x)
那么只需统计所以数的因数个数和(注意这里(a,b)奇偶性要相同)
枚举到(sqrt n),统计每个数的贡献

C

(;)
今晚的题细节有点多啊(其实还是我太菜了)
容易发现,(P_1=A_1)一定是最好的,不然前面就要填一个更大的数。
然后为了最小化字典序,尝试在(P_1,P_2)之间填一个尽可能小的数(这样一定也是可以的)
但这里一定要特判一下,如果发现([1,P_2-1])间的数已被选了,就只能选(P_2),否则会导致LIS变长
最后(A_m)的时候也要特殊处理,从大到小填

D

(;)
尝试处理以每个(i)为结尾的子序列(B)数量
发现([s_i+1,s_{i+1}-1])之间不能出现(B_{i},B_{i+1}),那么统计以(i)为结尾的答案时,必须满足这个位置是(a_i)最后出现的位置
看一下如何转移,(jin[lst_i, i-1])(lst_i)(a_i)上次出现的位置
但要注意必须要选其中(a_j)最后一次出现的位置,即:若(a_j=a_k,j<k),那么只能去选(k)
所以在dp的时候,如果算完了(i),要把上次转移的(a_i)的答案给减去,(i)把上次的给覆盖了。
用树状数组维护

E

(;)
网络流小清新题。
一种比较裸的想法是直接暴力建边跑最大流。
考虑如何去优化建边。
然后1h过去了,啥也想不到。
说明这道题如果要硬套网络流,尝试去跑最大流是死路一条。
这时候要考虑最大流的实际意义(不就是求最小割嘛)
从实际意义出发,我们尝试割的最小方案。
这道题比较特殊的一点是左集合(A)和右集合(B)之间的边只和(B)有关。
所以考虑从小到大去割(S->A_i)的边,因为与A具体是什么无关,我们只关心数量
再预处理一下右边的每个点到底是割(C_i),还是(B_i|X|)(|X|)是还没有割的(A)的数量,实时统计取min

原文地址:https://www.cnblogs.com/czyty114/p/15175098.html