CSU-ACM Home Page

2018HNCPC题解(CSU-ACM版)

Update Time: 2018-09-07 22:04:43     Recent Editor: Scanf     Create Time: 2018-09-07 22:00:59     Creator: Scanf    


A 字符画

按题意直接输出即可

B 2018

dp或者找规律(毕竟现场过的人那么多)

C 时间旅行

因为随机性,所以考虑最差情况随机到1

那么答案就是max(h,c+1)

D 卖萌表情

因为3个符号组成一个表情,所以如果表情绵延的长度是x,贡献就是x/3

要注意的是,前两种表情是横向延伸的,后两种表情是纵向延伸的

所以可以分开求,对已经使用过的位置用vis数组标记一下

E Grid

经典离散题,对于行和列进行离散建立线段树。

每次操作对应区间覆盖与区间查询,对于行覆盖操作需要维护之前列覆盖的数目,对于列覆盖需要维护行覆盖的次数。

对于第一次行与列同时出现覆盖的情况要特殊处理一下,因为此时出现了行与列的联通快同时减少的情况,这以后都只有行联通快减少或列联通快减少的情况。

对于离散后的线段长度的统计需要注意下。

时间复杂度O(qlogq)

F Fixed Point

先将询问按照模m的余数排个序

对于m次操作,可以计算出这个置换的循环节的长度,

过程中维护出每个位置所属的循环节的编号和在循环节中的位置

将位置按照所属循环节长度从小到大排序

然后对m个操作扫一遍,相同余数的询问挨在一起,

再对刚才排好序的位置扫一遍,算出对应的答案

G 排列

n≤20,所以可以考虑状压dp

首先要处理处与某个位置有关系的所有位置

然后统计每个位置对答案的贡献

从小往大放数字,这样就可以去掉绝对值

假设当前要放数字x,

枚举所有空着的位置,然后根据位置之间的关系

求出其为正的贡献数目,为负的贡献数目

最后放完所有位置即可得到答案。

代码中需要用到统计二进制中1的个数的技巧

n=n&(n-1),每次消除最右边的1

H 千万别用树套树

对于区间覆盖操作,直接用线段树维护

对于询问操作,其实只需要支持线段树单点查询被覆盖多少次即可

对于询问操作中r-l+1=1,直接单点查询即可

对于询问操作中r-l+1=2,单点查询l被覆盖多少次,再减去以l为右端点的线段数目即可

对于询问操作中r-l+1=3,单点查询l被覆盖多少次,再减去以l为右端点的线段数目,再减去以l+1为右端点的线段数目,再加上同时以l+1为左端点和右端点的线段数目即可

时间复杂度O(qlogn)

也可以用3个树状数组进行维护

对于插入操作[L,R],将R加个一,然后统计该线段对于长度分别是i=0,1,2的询问的贡献

在相应的树状数组中的L处加一,在R-i处减一

对于长度为i的询问,答案就是相应的树状数组在L处的前缀和

时间复杂度O(qlogn)

I Steiner Tree

标题是斯坦纳树,所以确实需要用到

当k<n/2时,利用斯坦纳树的dp方法求解

当k>=n/2时,枚举一下剩下的点要哪些,

然后利用Kruskal求解最小生成树

最后将两个合并就是最终要求的答案

J 买一送一

首先要看出来这是一棵树,然后就想怎么去重。

设当前节点为u,商品类型为a[u],父节点为fa

在dfs的过程中维护这几个信息:

1、 上一个以a[u]为第二分量的二元对的数目pre[a[u]];

2、 从根到fa的不同商品类型的数目num,即以当前a[u]为第二分量的二元对的数目;

3、 从根到fa的答案ans[fa]

那么当前的答案就是ans[u]=ans[fa]+num-pre[a[u]]

时间复杂度O(n)

K Use FFT

枚举a的0-n项,对于第i项答案的贡献为b中的 max(0,l-i)~min(m,r-i)的和,利用前缀和维护区间和即可。

时间复杂度O(n+m)