链接

题意

        桌子上有M堆扑克牌;每堆牌的数量分别为Ni(i=1…M);两人轮流进行;每走一步可以任意选择一堆并取走其中的任意张牌；桌子上的扑克全部取光，则游戏结束；最后一次取牌的人为胜者。现在我们不想研究到底先手为胜还是为负，我只想问大家：——“先手的人如果想赢，第一步有几种选择呢？”
        M<100 Ni<1000000

题解

        t=xorsum{Ni}
        Ni -> Ni' 后t=0
        则t^Ni^Ni'=0
        即t^Ni=Ni' 
        显然Ni'唯一存在
        又Ni'<Ni 等价于t^Ni<Ni
        sum{[t^Ni<Ni]}就是答案 

链接

题意

        1堆石子有n个,两人轮流取.先取者第1次可以取任意多个，但不能全部取完.以后每次取的石子数不能超过上次取子数的2倍。取完者胜.先取者负输出"Second win".先取者胜输出"First win".
        2<=n<2^31

题解

        n为斐波拉契数的时候，先手败，否则先手胜。

链接

题意

        每个数w都能至少写成一种如w=pow(x,y)的形式，但多种形式中，y的最大值是唯一的，定义这个y为f(w), 求对a<=i<=b,求和f(i)。(2<=a<=b<=1e18)

题解

        根据区间减法化简，则a=1, 定义g(i)为[1,b]中能写成pow(x,i)的数的个数，处理出g，然后容斥

链接

题意

        n枚银币构成一个环，每次可以去1~k之间任意个连续的硬币(取完不合并- -);
        数据范围不重要

题解

        当1<k<n的时候，到后手时若剩余1或2，后手全拿走，大于2则可以玩对称博弈
        当1<k n<=k的时候先手全拿走
        当1=k 判奇偶 

链接

题意

        给两个串s,t长度都小于4000,再给一个k<4000，求s和t各自的最长子串，使这两个子串间最多k个不同的字符，

题解

        dp[i][j]代表串s以i结束，t以j结束，最多k个字符不同的最小起点在哪，
        显然dp[i+x][j+x]的值关于x单调
        于是我们就可以O(n^2)完成了
        然后优化空间就行了。

链接

题意

        小伙们打算组团去参加。他们一共有 n+m+2k 个人，包括 n+k 个男生，m+k 个女生，其中 k 对男女生为异性情侣，现在他们要找房间住。房间有三种类型，双人间 a 元一间，三人间 b 元一间，这两种只能同性一起住。情侣间能住一对异性情侣，一间 c 元。除了情侣间以外，其他房间都可以不住满。
        求最少花多少钱，能让小伙伴们都有地方住。

题解

        dp[i]代表i个同性要花多少钱才能住下
        dp[i] <-----   dp[i-2]+a  dp[i-3]+b
        然后枚举情侣房间即可

链接

题意

        找到某一串连续的自然数使得数的平方和等于某一给定值k。

题解

        dp[i]代表以i结尾的连续的自然数,其平方和小于等于k时，最大的起点在哪
        dp[i]关于i具有单调性
        可以尺取

链接

题意

        给定一个数组和一个值t，求一个子区间使得其和的绝对值与t的差值最小，如果存在多个，任意解都可行。
        n<1e5

题解

        子区间和的绝对值
        那就可以对前缀和排序了，因为abs(presum[i]-presum[j])=abs(presum[j]-presum[i]) 根ij大小无关
        于是可以对前缀和排序，
        化简题目为：
            求两个前缀和a,b，使得abs(a-b)于t相差最近
        我们对前缀和排序
        dp[i]取abs(abs(presum[i]-presum[dp[i]])-t)最小的那个
        显然dp[i]具有关于i具有单调性。
        于是可以优化为O(n)

链接

题意

        给个正数区间(从小到大的素数),找到某一个子区间,使得区间内的数的和等于某一给定值k。
        n很小，啥做法都无所谓了

题解

        dp[i]代表以第i个数结尾的区间,和小于等于k时，最大的起点在哪
        dp[i]关于i具有单调性

链接

题意

        给定一个长度为n的正数序列,求和大于等于S的最短的子串长度。
        n<1e5 s<1e9

题解

        先考虑一个暴力做法,枚举所有的子串,此做法复杂度,n^2
        然后我们尝试dp,
        dp[i]代表串S[0:i]中以i结尾的和大于等于S的最大起点
        容易证明:dp[i]关于i单调不减
        于是我们的做法出来了,枚举i,对于j我们通过记录决策点，来优化成O(1)
        然后我惊讶的发现此做法竟然就是尺取法。