poj 1141题目链接 题意：给出一个括号序列，要求添加最少的括号，使得这个序列变成合法的括号匹配，输出最后的序列。 思路：区间dp。。。有了那么一点思路。。。我们可以用dp[i][j]表示区间[i,j]的序列最少需要添加几个符号使得匹配。。转移的话。。。和之前差不多。。dp[i][j] = dp[i+1][j-1] (s[i]与s[j])匹配。。。不匹配的话也是找中间某个点。。。初始化的话。。要变成最大值。。。比较没思路的是输出括号序列这部分。。。 参考了这篇题解：参考题解 记录路径的思路是。。。记录转移的点。。。 cut[i][j]表示的是区间[i,j]的最优值是由点cut[i][j]这里划分得到的。。。 cut[i][j] …

poj2955题目链接 题意：给出若干括号，问最大匹配数是多少。 思路：没有思路。我知道这是dp。。。然后其他就什么都不知道了。。。转移方程？ 完全没思路。。知道了转移方程。。。。嗯，还是不会。。。边界怎么写？状态怎么推？循环顺序? 循环次序？我一点思路都没有。。。。。 人生中第一道区间dp(这话我都说了不知道多少次了。。。每次都学不会。。。。sad) 我的dp水平和其他部分的水平还真是不匹配。。。 看了题解。。。自己写（抄）了一遍。。还是觉得好玄学。。。 细节见代码。 /* *********************************************** Author :111qqz Created Time …

hdu 3980 题目链接 题意：一个有n个石子的环形串，初始没有被涂颜色，两个人轮流，涂连续m个没有被涂色的石子，不能操作的人为负。问先手是否有必赢策略。 思路：和hdu2999很像。。所不同的是。。。那道题是线型的珠子。。。这道题是环型的数字。。。 然而我们机智得发现。。。环形的任意涂一次。。就变成了线型的啊orz。。。 所以先随便取一次，然后剩下的n-m个按照线型串的方法搞，划分区间即可。 由于先随便取了一次，所以和线型的交换输赢的结论。。。 以及。。要特判一次都不能取的情况。。。2A /* *********************************************** Author :111qqz …

hdu2999题目链接 题意：有一串石子，给定一个集合S，每次只能拿连续x个石子，石子必须是在集合S中的数，问先手是否有必赢策略。需要注意石子的位置是不能变化的，也就是说如果一串连续的石子因为中间有石子被取走，那么这段石子就变成不连续的了，也就不能一次取走。 思路：一开始没有读懂题。需要特别强调的是。石子的位置是不能合并的。。 举个例子，如果我有5个石子，S={2},那么我取完一次剩下的情况是 {3,4,5}或者{1},{4,5}或者{1,2},{5}或者{1,2,3} 一共四种。 题意搞清楚以后就好做了。。类似于bomb game那道题。。我们仍然可以把取一次的操作拆分两个子过程，也就是两个区间。我们不关心区间具体的情况，只关心区 …

hdu 2873题目链接 题意：n*m个格子，有若干炸弹。对于在第一行或者第一列的炸弹，爆炸后会到那一行或者那一列的更前面（总的来说就是更靠近左上角）的位置。对于其他位置的炸弹，爆炸后会生成两个炸弹，分别到那一行的更前面或者那 一列的更前面。问先手是否有必赢策略。 思路： 不会做2333 参考了 参考博客1 参考博客2 大概明白了一点。整个游戏可以分为若干个炸弹的游戏的和，而实际上一个不在边界行或者列的炸弹，依然可以继续分，分成两个炸弹的和。而位于(i.j)的炸弹，分成两个炸弹的和，有(i-1)*(j-1)种方案（这个不重要2333） 处于边界行或者列的点的sg值我们是可以知道的。。因为规则单一。。和移动等价。。 然后根据边界来进一 …

hdu2509题目链接 题意：？？？ 思路：同1907 /* *********************************************** Author :111qqz Created Time :2016年07月23日 星期六 04时41分38秒 File Name :code/hdu/2509.cpp ************************************************ */ #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> …

hdu1907题目链接 题意：n堆石子，每次选一堆，最少拿一个，最多拿光那一堆，拿走最有一个的人输。 问是否有必胜策略。 思路：anti-nim问题。。。 要用到sj定理（是啥。。。?) 参考资料：参考博客 SJ定理 **对于任意一个Anti-SG游戏，如果定义所有子游戏的SG值为0时游戏结束，先手必胜的条件： ** **1、游戏的SG值为0且所有子游戏SG值均不超过1。 ** 2、游戏的SG值不为0且至少一个子游戏SG值超过1。 /* *********************************************** Author :111qqz Created Time :2016年07月22日 星期五 23 …

hdu 1730 题意：n行格子，每行m个，每行有一黑一白两个棋子，给定初始位置，先手执黑棋，后手执白棋，每次可以在同一行内向左移动，不能超过边界，且不能越过对方的棋子，同一个格子只能有一个棋子。问先手是否必赢。 思路：可以看成n个独立的游戏的 叠加。。。所以最后异或和一下就好。。 我们来求sg函数。。。一开始的是想把点对hash成一个数。。。然后发现其实没必要。。。直接二维就好了。。 由于初始化的时候要考虑最大。。。所以sg函数的值会有一个便宜。。。和设定N有关。。减去偏移就好了。。。（我的代码里这个偏移是11026） 1A蛤蛤蛤 /* *********************************************** …

hdu 1404题目链接 题意：一个数字串，每次可以选择一位减少任意大小到一个非负数，或者清除一个0以及该位右边的所有数字。问是否有必胜策略。。 思路：定义来搞。。所有能一步走到p点的都是n点，那么如果我们现在知道p点，就可以反过来推n点。。 看到一些人强行把变量名起成sg就说自己用了sg函数也是笑死我了呵呵呵呵 /* *********************************************** Author :111qqz Created Time :2016年07月22日 星期五 19时11分16秒 File Name :code/hdu/1404.cpp …

终于忍不了因为没办法科学上网而不能做什么事的感觉了。。。 买了班瓦工 20刀/年。。。搭了ss。。然后全平台（ios/androd/fedora/win）的上网问题就全解决了。。。 网速似乎很快。。。youtube 1080p好无压力，虽然我不看2333