给你们说个笑话，我到现在还没有AC一道题答题TAT

NOI基本是要考得了，所以再不练练就要狗带了

记录一下解题的心得和技巧

基本都是口胡哒

NOI2014消除游戏(100/100)

【题目大意】：
    给出一个N*M的矩阵，选择不超过K条长度在[lmin,lmax]的路径，设长度为L
    1.如果路径上连起来的数字是质数那么得分L^c1否则为1
    2.如果路径上连起来的数字是会文书那么得分L^c2否则为1
    如果两个都为1那么本次总得分为0否则为两次得分之和
    选择一条路径后路径上的数字会消失，然后上面的方格为下落
    求最大得分
【题目解法】：
    Task1：直接手完，一开始还玩错了，最优解只需要两步即可
    Task2：n m比较小，写了个Miller_Rabin暴力跑跑就可以拿9分辣 然后就不会了，看了看标解感觉很有道理啊TAT
    Task3：只有质数可以得分，因此需要找到500个长度为18的质数，直接Miller_Rabin+dfs爆搜即可，几乎是秒出的
    Task4：和Task3是一样的
    Task5：和Task2一样爆搜即可
    Task6：发现只有1和2并且只有回文串有分且长度为1000，暴力枚举回文中心的两个点然后dfs暴力扩展即可
    Task7：和Task6几乎一样，只不过有2 3 4三种数字，拿Task6的程序跑就可以了
    Task8：只有回文串有分，并且大部分都是5 6两种数字并且相邻的一定是不同的，一开始直接把整个图遍历了一遍发现有坏点TAT，然后暴力一下遇到坏点就枚举下一步的方向，然后尽量先走上面的再走下面的
    Task9：左右两边几乎对称，用类似Task6的方法，两边对称着扩展即可
    Task10：发现有333个3*3的循环组成，直接对称走就可以了，每一个3*3的循环用如下方法走就好
    1 -> 2   9

         |   ^
         v   |

    4 <- 3   8

    |        ^
    v        |

    5 -> 6 -> 7

WC2014非确定机

WC2013小Q运动季

WC2015未来程序(70/100)

【题目大意】：
    给出10个程序的暴力和极限数据
    你需要根据暴力写出较优的程序然后跑出极限数据
【题目解法】：
    Task1：快速乘（其实我是懒得用计算器了）
    Task2：化简一下式子变成矩阵乘法+快速幂
    Task3：1/2/3/4次方和，上网搜了一发公式A掉了，正解应该是高斯消元或者矩乘
    Task4：给出一个黑白的网格图，求：1.白色点对的个数 2.距离某个白色点最近的黑色点 第一问找出点为n个后直接就是N*(N-1)辣 第二问把所有黑色点放进队列bfs一发就好
    Task5：给出一个黑白的网格图，求白色矩形的个数。对于每个点处理出它向下延伸的最长白色长度L，对于每个行扫过去的时候对L维护一个单调递增的栈就好
    Task6：不懂啊...
    Task7：智障数独不想写TAT
    Task8：貌似是组合数搞搞？不会
    Task9：喜闻乐见的“常识”题
    Task10：暴力检索，统计一下最后的贡献就好

uoj85最小割计数

ZJOI2015黑客技术

NOI2013小Q的修炼(100/100)

【题目大意】：
    给出若干个事件，有三种类型：
    1.把某一个变量 +/- 常量或某个变量
    2.条件跳转：给出两个量（常量或变量）进行比较，如果第一个小于第二个则跳转到第x个事件否则跳转到第y个事件（x y给出）
    3.选择跳转：选择调到x或y中的某一个（x y给出）
    任务：使得一号变量最大
【题目解法】：
    据说是历年NOI最水提答
    首先注意一个事实：所有点的跳转都是无环的（因此可以直接暴力每个跳转然后跑几年应该可以A掉～）
    Task1：发现每个选择跳转都是向后面跳并且选择的次数很少，直接暴力dfs判断每次跳转哪个就好
    Task2：和Task1一样，不过有24个跳转，暴力一下，20s不到就出解了
    Task3：有若干个大块，每个大块有若干个小块，每个小块是把3-12这10个变量+一个随机整数，每个小块可选可不选，每个大块处理完之后把这10个变量的绝对值加给一号变量然后清零，也就是说大块之间的抉择和代价是独立的。因此对于每个大块，我们考虑暴力枚举10个变量最后的符号：(1)如果是正号，那么原来+的数就是正贡献原来-的数就是负贡献 (2)如果最后的符号是负号，那么原来是+的就是负贡献，原来是-的就是正贡献。然后对于每个小块贪心找到最优贡献时的跳转方式就好。
    Task4：有两个变量，仔细观察发现第二个变量初始为5000，然后每次可以选择这样的事件：第二个变量减去一个整数，第一个变量加上一个数。然后第二个变量不能减出负数。显然是个背包问题，把每个事件抽象出来做一遍背包就好。注意输出路径时，如果某个时候剩余的背包容量小于当前物品的重量是不用输出跳转方式的，因为他会直接跳过这个物品。（一开始多输出了这一步调了一个小时TAT）
    Task5：还是背包问题，不过对于某个物品，如果不能选或者选择不选那么他会跳转到下一个指定的物品。因为没有环的存在，因此可以沿用dp解决。定义f[i][j]表示后面i个物品花费j的空间能得到的最大价值，然后对于每个物品枚举选还是不选，设next[i]表示i物品不选是跳转的位置：如果i物品不选那么从f[next[i]][...]转移，如果选的话就从f[i+1][...]转移就好
    Task6：和Task5相同，不过初始容量变成10000。反正下面跑没有空间限制直接大力2000*10000的数组就好
    Task7&Task8&Task9&Task10：这几个点我是一起写的。他其实是Task3和Task5的结合版，就是Task3里面的每个大块也可以选或者不选，选的话需要付出一定代价，不选的话跳转到下一个指定的物品。分离出所有大块，对每个大块里面的小块用Task3的贪心就好。最后背包一发就好辣～

UR#9包子晚宴

集训队互测2016消失的源代码

【题目描述】：
    给出一个可执行文件lost，里面包含10种不同功能
    给出10个in文件每个包含10组数据，用lost只能输出第一组
    可以构造一些数据规模不超过第一组的小数据让lost运行
    根据判断对每个in输出out，每个in的每一组结果1分
【题目解法】：
    30s内把每个in的第一行求出来就有10分辣
    Task1：发现是一个26个字母的映射，把每个字母当成in输进去就可以得到映射辣
    Task2：不会啊TAT 看了题解发现是求2016x^2+4x+10 (mod 233333)的结果
    Task3：还是不会 正解是给出圆的面积求半径下取整
    Task4：构造一些小数据发现是：给出无向图，求每个连通块点数平方之和
    Task5：喜闻乐见的树终于出现辣...构造小数据发现：给出一棵树和m次询问，每次询问两个点路径边权之和，m个数异或起来输出，我个智障还写了倍增+LCA，直接暴力其实就可以了
    Task6：还是喜闻乐见的树，跟Task5基本一样，只不过把路径和改成路径最小值
    Task7：据说是sigma(sigma(gcd(i,j)) 1<=i,j<=n TAT这怎么看出来哒。容斥一发就好
    Task8：给出n个数，求本质不同的的非空连续子序列的个数？！woc，根本看不出啊TAT 后缀数组完事
    Task9：构造小数据发现：求n个点两两欧几里德距离最小值 n<=1000000 写个O(N^2)的暴力加一点优化就过了
    Task10：送分，输出10个"invalid input!"完事

APIO2013 TASKSAUTHOR(100/100)

【题目描述】：
    给出若干个程序，每次指定两个程序A B，需要你构造数据使得A不超时B超时
    有两个子问题：1.最短路 2.地图染色
    对于每个Task还有限制：构造的数据中包含的数字个数不超过T
    每个程序会有一个计数器在某些位置会让计数器+1，如果计数器>10^6即为超时
【题目解法】：
    Task1：A=floyd B=dijkstra T=107。很明显构造一个101个点的空图floyd就超时了
    Task2：A=floyd B=BellmanFord T=2222。不难发现给出的BellmanFord算法是每次遍历所有的边，如果无法更新就退出。那么我们尽量构造出这样的图：每次只让一个点能更新，这样我们就需要更新n-1次，每次遍历O(M)次，然后在询问10次就TLE辣。所以我们构造1~n的链，方向倒过来，然后构造950条1-2的重边即可
    Task3：A=BellmanFord B=floyd T=105。跟Task1一样啊
    Task4：A=dijkstra B=floyd T=157。神构造。我们直到dijkstra对负权的边的贪心是由bug的，也就是说对于每个点到t的最短路，我们使得第一条出去的边不是从这个点出去最短的边，这样就能走出许多没用的东西。具体构造方法见：http://wronganswer.blog.uoj.ac/blog/1641 反正我是没有想到TAT
    Task5：A=dijkstra B=BellmanFord T=1016。沿用Task2的方法，令n=300 m=335就没了
    Task6：A=BellmanFord B=dijkstra T=143。T卡的非常紧啊。用Task4的神构造，询问变成6次就刚刚好
    Task7：地图染色问题。看了看给的程序发现是暴力？！woc，随机一个数据就超时了
    Task8：地图染色问题。让这个SB程序不超时（写的这么渣居然还要不超时TAT）其实很好构造，随便构造一条链，然后每隔两个连一条边，这样X=3很快就能搜出来了

uoj#208 UOIP十合一(70/100)

【题目描述】：
    给出一个有向图
    求关于边的子集个数是的这个子集内无环
【题目解法】：
    首先tarjan一遍求出：强连通分量个数，每个强连通分量中包含的点数和非自环的边数
    Task1：发现除了自环以外其他边随便选都不会出环。因此统计非自环的边的数量cnt，答案为2^cnt
    Task2：发现有若干个强连通分量，然后每个里面边比较少，对每个连通分量暴力然后乘起来就好。对于非联通快内的边选和不选都可以
    Task3：发现n=m，因此每个联通块都是一个独立的大环，对于一个环答案为2^x-1，每个计算一下乘起来就好
    Task4：不会。只发现了每个点都是想[i-7,i+7]这个区间内连边，感觉可以暴力状压连通性，但是目测空间时间会炸起来
    Task5：和Task2一样
    Task6：有向完全图。考虑不存在环那么一定是DAG。直接dp，f[i]表示i个点的答案，然后枚举DAG的汇点容斥一下就好
    Task7：n=12。状压dp，利用奇偶性容斥，用dfs转移复杂度O(3^N)
    Task8：n=20。拿Task7的程序跑了几分钟，开个O2常数优化一下就好
    Task9：不会
    Task10：不会