NOIP2017 题解

终于开始在晚自习的时候填填noip的坑了。

D1T1传送门

D1T2传送门

D1T3传送门

D2T1传送门

D2T2传送门

D2T3传送门

d1t1:math :

推规律(找规律),a*b-a-b;

c++代码如下:


d1t2 : complexity;

模拟

c++代码如下:

 


d1t3:park

不难发现,最多多花费k (k <= 50)的价值到达n点的话,那么对于所有点,一定多花费也不会超过k。

那么状态就不难列出f[i][j]表示i点多花费j个单位的方案数,那么转移就是所有达到该点多花费j的点的方案数之和,这里用递归求。。。

然后如果发现一个状态被访问过,那么此时一定是从零环走过来的,直接返还-1

c++代码如下:

 

考场代码(10分):


d2t1:cheese

对于每个空洞o(n)的寻求与之相连的洞,每个洞有两个状态(与上面相连,与下面相连)

然后就直接o(n)的寻找一遍,从状态1的点进入,看能不能找到状态2,如果找到了之前找到的点直接跳过(因为上一次肯定没找到

c++代码如下:


d2t2:treasure

状压dp,考虑直接加入不好处理,就设当前的点都加入已知最深的深度,然后枚举所有状态(注意去重

c++代码如下:


d2t3:phalanx

观察发现每次变动有影响的点只有当前点,最后一行最后一列的点以及当前这一行的最后一个点。

所以可以用一个支持单点修改的线段树,建立n + 1棵,前n棵代表第n行前m – 1个答案,第n+1棵表示最后一列。

每次操作将当前点(x,y)记录输出并删除,然后加入第n+1的最后一个位置,然后把第n+1棵的x位置记录加入到第x行的最后一个位置,

注意如果x本身就在最后一列就不用管。

考虑q的范围,即最多有q个点加入,那么线段树的长度最长为 max(n,m) + q.

而n,m,q,的范围均在3e5的范围,所以需要动态开点,所以内存最多只有 3 * log n *q ,搞定

c++代码如下:

 

1 + 5 =