虐狗大赛：本来想让搞线段树和差分序列，结果数据太水暴力都能过算了反正第一题就简单点吧观察到询问很少，所以我们只需简化修改的时间复杂度用另一棵线段树维护每个单身狗受攻击的次数把减少攻击等价于增加生命即可，设次数为di,攻击为Ai,防御为Bi则答案为Ai-Bi*di，这样做单次修改复杂度O(logn)同时也由于询问很少，可以用差分序列代替线段树,单次时间复杂度O(1)殉国://分数为未加强数据前题目大意：Ax+By=C,x>=0,y>=0,求x+y最大值，x+y最小值x,y的解得个数暴力算法1：枚举x,y更新O(N^2)20分暴力算法2：枚举x，测试y是否符合情况，O(N) 40分-100分（原谅我数据太水）很明显的扩展欧几里得令gcd(A,B)=D;Ax+By=C满足有解的必要条件是C mod D = 0我们先解方程Ax+By=gcd(A,B),得到该方程一组解(p',q’)乘以C/D即为原方程的一组解(p0,q0)则任何(p,q)满足p = p0 +B/D *tq = q0–A/D *t(其中t为任意整数)都为原方程的解我们解不等式p>=0&&q>=0得到关于t的一个区间[l,r](注意不等式的向下取整和向上取整)则通解个数显然为r-l+1最小最大解一定分别在l,r处取得（因为是线性方程）时间复杂度O(logN)加强数据后，最优的枚举只能50分 扩展欧几里得+枚举+优化=65-85分 题解做法：100分燃灵之链：K子序列最大和，由NOIP初赛的双子序列最大和改编而来20分算法：O(2^n)的暴搜70分算法：设状态f[i][k]表示前i个点含有k个子序列的最大值。考虑动规:设si=a1+a2+……ai则显然if(j!=i-1)f[i][k]=max(f[i][k],f[j][k-1]+s[i]-s[j+1]);(不相邻，开创一个新序列)f[i][k]=max(f[i][k],f[j][k]);(j