noip2017练习总结

Day1

T1

已经知道结论就没什么好做的了，ans=a*b-a-b，考场上遇到的话就考虑打表找规律吧。。

T2

又是知道结论然后去做的，只要想到用栈来模拟就不难了。。。
顺便说一下getline这个函数，调用时这样getline(cin,s)，会一直读到换！行！符！然后停止；
我因为第一行用的cin，然后第一个getline读的就是第一行的换行符，因为这个调了蛮久的

code

T3

还是不太懂的样子，先口胡一波
先考虑搜索怎么做，就是跑出路径然后check，
考虑给他加记忆化，记f[x][k]表示到了到了x，距离超过K还剩k的方案数，
我们可以建反图跑出所有点到n的距离，那么从x到y，会多出edge[x][y]-(dis[x]-dis[y])的代价，
所以f[x][k]转移到f[y][edge[x][y]-(dis[x]-dis[y])]
边界是f[n][k]=1
考虑0环，只要在一个点回溯前又遇到了他，而且k没有变，就说明又0环
并且这个0环一定是1到n的路径上的，应为如果到不了n，dis[x]会是inf;

一直都搞不懂dp怎么做

code

Day2

T1

因为n小于等于1000，所以暴力枚举两个点，再并查集判断是否相连就可以了

code

T2

看到数据范围小于12，考虑状压，设f[i][s]表示树高为i，已选集合为s，f[i][s]+(s和t集合中，扩展出每个点的最小的边的和)*(i+1)-->f[i+1][s^t]
如果选取s中树高不为i的点去扩展，那么一定有一种情况f[ii][s0],满足ii<i,s0属于s时，他会把树高为ii的扩展到s^t,所以不会算漏

复杂度分析,外重循环枚举i是n，枚举子集3^{n,枚举两点间的边是n}2,总复杂度是3^n*n3,算出来是918330048，9e8,
我也不知道为什么我只跑了200ms

code

--- T3

感觉自己要多写一点动态开点线段树
每一步操作，显示第m列的x行移动一个到m-1列x行，然后是第m列的x+1~n行都向前移动，最后出队的那个移动到m列最后一个
我们可以考虑建n+1棵线段树，分别维护1~n行和m列，动态开点去做就好了，具体看代码吧

code