[原创]2016年湖南省第十二届省赛【ABGHJ】

2017-04-27 00:45:08 Tabris_ 阅读数：368

博客爬取于2020-06-14 22:40:51
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/70835664

做这套的时候很迷啊感觉回到了杭州的时候签到题半天没有A，明明很水的题目我竟要去想容斥那套理论GG，3小时AC签到题？？！果然是菜的可以。，

但仔细想想，可能这套题真的偏难吧，
最后补题只A了4个 H是看了题解的。。

A CSU 1803 2016

————————————————————————————————————————————
真的是水题啊上来就想到容斥那一套理论，然后GG。（也暴露了我容斥反演那一套学的并不好的事实啊

其实就是考虑每一个20162016的块，对结果的贡献是相同的，所以就变成了求有几个20162016的块然后边界的在计算一下就好了，如果预处理二维前缀和的话，就能O(1)做了

B CSU 1804 有向无环图

————————————————————————————————————————————

$\sum_{i=1}^{n}\sum_{j=1}^{n}count(i,j)\times a_i \times b_j \\ =\sum_{i=1}^{n}a_i \times \sum_{j=1}^{n}count(i,j)\times b_j$

其实就是大概这意思，
对于里层的 $\sum,a_i$ 就是一个常数了 ,提出来就好了
这个时候我们只要统计就好了

现在是1->2->3 的
那么能到达2 的是{1}, 能到达3的是{1,2}
脑补下再长一点的结果,发现如果 $a$ 能到达 $b$ 那么能到达 $a$ 的点都能到达 $b$ ,通过这个我们就可以直接计数

$cnt[to] = cnt[fa]+1;$

只要将点的个数变成点的 $b_i$ 就好了,最后的结果就是

$\sum_{i=1}^{n}cnt_i\times a_i$

因为给的是有向无环图，我们可以在拓扑过程中计数，能够保证每个节点的值不会有后效性。

C CSU 1805 Three Capitals

————————————————————————————————————————————

D CSU 1806 Toll

————————————————————————————————————————————

E CSU 1807 最长上升子序列~

————————————————————————————————————————————

F CSU 1808 地铁

————————————————————————————————————————————

G CSU 1809 Parenthesis

————————————————————————————————————————————
这题很容易想到对’(’ +1， ‘)’ -1 我们在处理前缀和的时候能够知道当前位置能不能匹配上，
那么对于一次交换的时候可以知道这个符号有没有能和他匹配的最开始想用树状数组维护，然后直接找，
然后考虑了交换符号一样时一定是yes。还有写了好多个）(的情况发现总会找到匹配的(不会证明），
然后对（）的时候用树状数组进行维护，
提交wa。。

后来发现一组数据交换粗体的时候换完之后这两个符号都有匹配的
((())(()))()
()())(()()()
但是这两个就不匹配了
()()) (()()()

然后发现当一个位置的括号不匹配了一定是‘）’，在前面没有与它相配的’)',这个位置的前缀和是-1的，
那么也好想，‘）’在原序列上贡献了-2，在交换的区间如果有<2的位置就一定存在不匹配的，
注意这个区间是左闭右开的，因为左边还有多个2的贡献，

然后就是查询区间内有没有<2的就好了, 维护这个方法就很多了,RMQ,BIT.SEGMENT_TREE…

H CSU 1810 Reverse

————————————————————————————————————————————

做这题开始的时候思路还是很清晰的,
一定是求每个位置的贡献,然后统计,

然后这个贡献怎么求,
对于这个位置的值是本身,
一个是交换的区间不包含它,那就是 $(i)*(1+i)/2 + (n-i)*(1+n-i)/2$
第二个是交换的区间以i为轴那区间就是min(i,n-i)

然后关键就是这个位置的值是被交换过来的值,我们要怎么求? 这里我就想蒙蔽了…
交换多次要多统计的a[j]~a[k]中的数,然后想了想乱糟的,就放弃了

~~中间还思路想到了一个奇怪的想法…过了第一个样例…~~

后来看了题解,
发现在上述基础上接着再按求贡献的思路找,
找每个 $a_j$ 对这个贡献的贡献就好了,

依然考虑每个 $a_j$ 有几种交换能交换到 $i$ 的位置.
对于每个 $a_j$ 交换到 $i$ 的位置的情况数$min(j,n-j+1)\ $
其实细分啊 $a_j$ 在 $i$ 左边的就是 $a[j]*j$ 右边的就是 $a[j]*(n-j+1)$

维护的时候就线预处理处理前缀和就好了,这样就能在O(n)复杂度计算每个位置的贡献了…

I CSU 1811 Tree Intersection

————————————————————————————————————————————

J CSU 1812 三角形和矩形

————————————————————————————————————————————

因为图形和坐标轴是平行的 ,扫描线走一遍就行;

当然还可以暴力的求凸包交,然后面积和减去面积交就是面积并了…

K CSU 1813 盖房子

————————————————————————————————————————————