SG解题模型： 1.把原游戏分解成多个独立的子游戏，则原游戏的SG函数值是它的所有子游戏的SG函数值的异或。 即sg(G)=sg(G1)^sg(G2)^...^sg(Gn)。2.分别考虑没一个子游戏，计算其SG值。 SG值的计算方法：（重点） 1.可选步数为1~m的连续整数，直接取模即可，SG(x) = x % (m+1);2.可选步数为任意步，SG(x) = x; 3.可选步数为一系列不连续的数，用模板计算。 分割博弈 HDU3980 http://acm.hdu.edu.cn/showproblem.php?pid=3980 题意：长度为n的环，每次操作取m个连续的...

题意:用一个长度为n的排列，生成一个长度为n-1的up-down序列。若后一个比前一个大，则为0。反之，则为1。给定一个长度为n-1的updown序列，问符合序列的合法排列数量.例：1,2,3,6,4,5 is 0,0,0,1,0. 分析：设状态 前1-i数字放置并且最后第i个位置放j的合法方案数，如果输入序列的第i位是0, 就需要往 转移, 否则需要往 转移. 利用前缀和优化一下 DP 即可做到 . #include<bits/stdc++.h> using namespace std; const int mod=1e9+7; int dp[5005][5005...

https://ac.nowcoder.com/acm/contest/35/D对于某个点x,以x为根的子树上，所有与x距离大于等于k的点与x的距离之和。 解法一：离线处理。https://ac.nowcoder.com/acm/contest/view-submission?submissionId=44771875解法二：bfs剪枝(竟然能过https://ac.nowcoder.com/acm/contest/view-submission?submissionId=44771300

题目大意： 个点的无根树， 条带权边。有 次询问，每次询问区间 的点的. 表示 点到点的最短距离。 参考出题人题解：https://blog.nowcoder.net/n/13d05ab8ac22444a81fbe475de2f563eHDU多校也出了一道这个题目求区间 .(怀疑出题人巨巨是同一个 分析；对于一个区间 的点集，求最大两点间的最短距离其实就是求点集的的直径。对于两个不同的点集 进行合并后， 点集的直径就是原先两个点集的直径两点，从该四点中点对距离产生。那么我们可以套个树链剖分LCA，线段树进行维护区间点集的直径合并操作，然后 进行回答询问。 #include<bit...

D.Decrement on the Tree 给定一颗无根树，有n个结点，n-1条边，每条边有一个权值。修改操作：选择两个点，两个点之间的最短路径上的边权减一。询问:将第i条边的权值赋值为x，询问要执行多少次修改操作可以使得所有边权变为零。 分析：修改操作可以看成将树划分成若干条路径。每个点将它所连接的边一一匹配起来。那么我们只需要计算路径的起点和终点个数就可以得到路径的条数。对于一个点，如果所连接的边中，没有一条边的边权超过连接边的所有边权一半，那么一定可以两两匹配（会根据奇偶性多出至多一条，那么这条边的起点就是该点）.如果超过了一半，那么未匹配的边就是2 * max-sum,这些边的起...

A. Groundhog and 2-Power Representation 题意：给一个正则表达式，求正则表达式的值。例子：2(0)=2^02(2+2(0))=2^(2+2^0) 分析：队友写的py. a = input() a = a.replace('(', '**(') print(eval(a))B. Groundhog and Apple Tree 题意：给定有n个节点一颗无根树，每个节点有点权,每条边有边权 .从起点1出发遍历所有点，并且保证每条边最多遍历1次，每次遍历一条边，体力减去该边权大小，遍历点时体力获得点权值，如果要保证行进时候当前体力不小于0，那么...

https://codeforces.com/problemset/problem/460/Ehttps://ac.nowcoder.com/acm/contest/5672/A

题意：同学们在操场跑步(操场看做无限长的数轴),每个同学如果开始跑步那么他跑步的方向不会改变直到时间结束。老师为了检查是否有同学偷懒没有跑步，手上有 份监测报告，每份监测报告说明了在 时刻时， 位置至少有一个人在跑步。问操场上至少有多少名学生没有偷懒在跑步。 分析：将每个时刻的(t,pos) 看作二维平面上的点，那么对应的同学看作斜率为45°,135°的两条直线。将所有点旋转45°，那么所有的直线就是垂直于坐标轴，那么该问题转换成了选取最少的直线覆盖所有点。将第 个点产生的垂直于轴的直线和垂直于 轴的直线，看成点，并且连一条边，建二分图，那么问题转换成了二分图的最小点覆盖问题，而二分图的最...

题意：两班各选几人参加比赛，每个人都有体重和魅力值，要求在两边体重相等的情况下魅力值最大。 分析：01背包问题，不过直接写的话复杂度是O(10^9)显然不行。(比赛时有人竟然用容量和为上界水过了官方题解的优化:通过随机化算法进行优化背包容量。(random_shuffle)将所有选手随机排列然后依次算背包，背包的容量限定在范围 中即可，而这个 足够大即可题解证明:容量上界取： . #include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=2e5+10; const ...

题意：给定A,B字符串，询问A字符串的[l,r]子字符串最少多少次操作能够变成B字符串。(可以操作A串，也可以操作B串)操作： 增加一个字符，或者减少一个字符。 分析:因为只能插删，所以最优的肯定是留下最长公共子序列。 表示到 串的第 个位置，长度为 的子序列，在 串的最小位置。序列自动机预处理一下 串，然后每次询问做一遍 的dp. #include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=2e5+10; char a[maxn],b[maxn]; int nex[...

题意：给定n个人，第i个人为1 表示是读者，2表示为程序员，ACM赛制是三人一组，规定三人至少有两个为程序员，而且三个人互相不认识。一开始所有人都是互相不认识。然后依次给出n-1条朋友关系(关系满足传递)使得所有人都互相认识。求给出第i条朋友关系时，可以三人一组组队的方案数是多少。答案模1e9+7. 分析:并查集，增加一个新边，对原有方案减少了多少。我们并查集维护一个连通块里2和1的人数各有多少。增加新边相当于要减去从(2,2,1),(2,2,2)这两种的方案。那么选人左右连通块都是可能会选的：左边选1的人，右边选2 的人 方案(1,2,2)左边选2的人，右边选1 的人 方案(1,2,2)左...

HDU6798 http://acm.hdu.edu.cn/showproblem.php?pid=6798参考博客 >https://www.cnblogs.com/stelayuri/p/13393651.html 大致题意：给定等边三角形的三个点，内有一动点，给定动点的速度向量，点与三角形边碰撞以镜面反射的角度改变方向，速度不变，求经过k次碰撞的时间。 分析；二分时间进行判断，碰撞可以看出无限个三角形进行拼接的二维平面，对于一个点移动形成的射线，与直线所经过的点数。(二维平面镜面碰撞问题)预处理三种坐标系，分别是以AB,AC,BC为X坐标轴，动点的速度向量。然后根据 求交点。具...

简单dp:https://ac.nowcoder.com/acm/problem/16664 背包1.https://ac.nowcoder.com/acm/problem/178712.https://ac.nowcoder.com/acm/problem/512163.https://ac.nowcoder.com/acm/problem/248704.https://ac.nowcoder.com/acm/problem/166715.https://ac.nowcoder.com/acm/problem/16650 迷宫类1.https://ac.nowcoder.com/acm/pr...

A.Clam and Fish 题意：一个游戏有n个阶段。每个阶段是四种状态中的一种. 0： 没有鱼、没有蛤蜊 1： 没有鱼、有一个蛤蜊 2： 有一条鱼、没有蛤蜊 3: 有一条鱼、有一个蛤蜊游戏规则：一个蛤蜊可以做成鱼饵存储起来，在0状态下如果有鱼饵，那么可以钓到一条鱼。有蛤蜊并且也有鱼，可以直接用蛤蜊钓到鱼。 问在n个阶段后，能钓到最大的鱼条数是多少。 分析：有一个贪心策略，在没有鱼只有蛤蜊（1状态）的时候进行制作鱼饵，在有一条鱼和一个蛤蜊的时候（3状态）直接钓鱼，在没有鱼没有蛤蜊的时候（0状态）如果当前有鱼饵那么直接钓鱼。这个策略下有可能会剩下a个鱼饵，那么我们只需要将减少a/2个制...