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个制...

B. Boundary 题意：给定n个点的点坐标，求所有过(0,0)的圆中，圆上能覆盖最多给定点的圆。输出覆盖点的最大个数。 分析： n=1,那么答案就是1. n>1,因为三个点能确定一个圆，n^2枚举两个点与原点连成三角形，求三角形的外心，然后存储坐标。这样我们可以枚举c出所有覆盖点>=2的圆。(求三角形外心直接百度板子 由于这道题卡常数，不能用map计数，我们可以sort一遍，然后遍历计算圆心的出现次数。求得最大值 . 假如一个圆覆盖了 个点，那么对于 个点两两组合，重复计数圆心次数有 次。所以最后计算答案还要再转换一下。 #include<bits/st...

类似题目：https://ac.nowcoder.com/acm/problem/50493 石子位置成一个环(就是多存一遍石子，跑2*n大致题意： 个石子，每个石子有一定的价值，每次可以合并相邻个石子，合并的代价是两个石子的价值和，合并完后两个石子的价值累加一成石子的价值，问将 个石子合并成一个石子的最小代价是多少。分析: 考虑子问题,对于区间 的石子合并成一个石子，更小的子问题就是区间已经分成了两个石子然后合并成一个石子，那么代价其实就是区间所有石子价值和(用前缀和 维护)。假如我们已经得到了 , 的最优合并解，那么对于 的最优解应该是: . 表示当前子问题合并的代价。 那么如何抉择循...

题目大意：给定 种花 个花瓶，每种花插在花瓶上都有一个美观值 ,对于第 种花，满足第 种花插在的花瓶位置一定是在第 种花插在花瓶位置之前.每个花瓶只能插一种花。问将 朵花插入花瓶最大的美观值之和是多少.并且输出插入花瓶的位置方案。(如果有方案美观值相同，按字典序最小输出) 分析：动态规划. 表示第 种花插入第 个花瓶、前 种花插入前 个花瓶的最大美观值。 转移方程： . 可以用前缀和维护。 最优解方案可以用 表示当前 前 种花插入前 个花瓶中可以获得最大的美观值，第 种花插入的花瓶位置。因为是字典序最小所以转移时 就是最大美观值，获得方案，需要倒序遍历找到最优位置，然后倒置输出。 #i...

类似题目：https://ac.nowcoder.com/acm/problem/14701 取数游戏题意： 的矩阵，每次从每行中取一个数，每行取数的得分 = 被取走的元素值 * ，其中 表示第 次取数（从1开始编号）。并且每次取走的各个元素只能是该元素所在行的行首或行尾。一共取 次，问每行取数的最大得分和是多少。 分析：每行取数互不影响，所以我们依次计算每行的最大取数方案累加起来即可。 和 的范围不大，我们可以定义 表示该行左边取数取到 位置，右边取数取到 位置的最大得分。进行dfs记忆化搜索答案。 注意数据范围爆long long,用__int128才能过. #include&l...

题意：给定花费上限 ,你有 件物品，有m 件装饰品，每件物品和每件装饰品都有两个值攻击力 和花费 。一个物品最多被一个装饰品所装饰，每个装饰品不能独立存在，问在不超过花费上限的前提下，攻击力最大能到达多少.购买限制：物品最多只能买五个.并且同一种商品不能重复购买. 分析：每种商品只能选购一次，那么就是01背包问题，状态的值就是当前ATK的最大值. 根据数据范围开状态，我们可以让花费作为状态的第一维，题目限制买的物品数量不超过5个，购买物品的数量作为状态的第二维，并且装饰品与物品数量相关，购买装饰品的数量作为第三维。 因为购买装饰品与购买物品唯一相关联的是数量，那么我们可以分两次背包，第一次背...