题目大意 有一棵包含n个顶点（n-1条边）的带边权的树，每次都可以选择两个不同的顶点，将这条链上每个边权值减去1。要使所有边权值为零，最小操作数是多少？还需要支持边权的修改：将第p个边的权重更改为w，每次修改后都要输出答案。 解题思路 没有图示，我很抱歉！我会尽量清楚地叙述一下这个做法的原理。（刚才我题解也看的很懵）。 转换题意 看到在带边权的树上操作，我们一个惯用的套路就是：边权转点权。这里，我们可以把减边权的操作，转化为访问点的操作。当一条边权值减1时，它的两个端点都被访问到1次。所以我们可以把问题转化为：最少访问多少次，就能所有边权变为0。 每个点的考虑 现在，我们的首要任务，就是找到每...

题目大意 有n个球队，每个球队都和其它所有球队比一场，所以一共有场比赛，每天一场比赛。每个球队会在第一场比赛开始时到，最后一场比赛后走。安排一个日程表，使所有球队停留的天数之和最小。 解题思路 最开始拿到题，由于样例的关系，还以为就是暴力输出全排列即可（发出了WA的声音）。 输入：4输出：1 21 31 42 32 43 4 但是稍加思索，就会想到这样绝对不是最优安排。假设我们有10个队，可以看到，我们的确照顾到了1号队，但是他们是比完9场就走了，而2,3,4,...,10号队都要挨个到来，要在场下白费好久。（而且1号队也是要看比赛的呀） 所以，我们要尽量地折中每个队伍的停留时间。于是一拍...

题目大意 没玩过炉石的小白翻译：现在有四种随从，这里的每种随从，如果对面没有免疫都是秒杀： 带圣盾、亡语； 带圣盾； 带亡语； 普通随从。 每种buff的效果： 圣盾效果：免疫任何攻击，免疫一次后消失； 亡语效果：随从死亡时召唤一个藤蔓； 藤蔓：只有1攻击1血量的小怪。 每回合都要发动一次攻击，游戏结束时还有随从存活就算获胜（平局不算获胜）。幸运的是，你掌握着你的对手(?)，只要有一点可能获胜就可以赢。现在你有a[i]个i种随从，他的对手有b[i​]个i种随从，你能否获胜？ 解题思路 不要被原题的长长长长长描述劝退，因为我们操控着对手，可以让对面应付我们的最优策略，所以这道题很显然是贪...

题目大意 给定n个区间[L_i, R_i]，每个区间有 1/2 的概率被选择，表示第i个被选择的线段，求的期望，答案对998244353取模。 解题思路 不同于官方题解通过树形dp的思路，我们的方法是通过累加每种情况对期望的贡献来求解。线段的交取决于最大的左端点以及最小的右端点，同时维护两个东西比较困难。 当然，我们先添加上最左最优的端点，处理所有线段都不选择的情况；再按照线段左端点从大到小排序，那么排序后的线段的交，就取决于最小的右端点，以及第一个被选择的线段的左端点，再在离散化后构建好一棵线段树，再映射到原值。先明确，我们要的 接下来要进行的操作是： 简单易得，遍历区间[i,i+1]，...

题目大意 有一个n个点的树，走过每一条边时会减少一定的hp，每条边只能最多经过2次（即每个子树只能进出一次）。吃了第i个点的苹果会回复a[i]的hp。可以在原地休息，每个单位时间回复1hp。hp不能为负。从根节点1开始出发，初始hp为0，要求经过所有点后返回1号点，求最少休息时间。 解题思路 这道题显然是用贪心的树形dp来求解。我们可以把边和边的权值都存起来，然后dfs搜索。为了保证能回溯，把找到过的节点存入vector。接下来考虑一下我们的贪心策略，那么一拍脑袋：我们应该优先走加hp更多，时间t+hp更大的节点。 用官方题解来充实我糟糕的表达.exe 显而易见，我们最方便的操作就是在根节点...

题目大意 一堆桌子被排列成n×m（范围为[1,500]）的矩形，a[i][j]=1表示位置(i,j)处有桌子，0表示没有。我们要寻找满足这些条件的子矩形： 该子矩形的四条边上没有空位； 子矩形中的空位与桌子的数量之差不超过1（不包括侧面的桌子）； 子矩形的长度和宽度必须大于1。 有多少个子矩形可以满足要求？ 解题思路 500×500的矩阵，我们最多可以跑的算法。那么对付这样的枚举子矩阵题，我们的惯用套路就是用前缀和来维护了。我们在原矩阵中把0则当做-1，求出要求的0和1的差，记录前缀和。注意：前缀和不能算上边界的1。 一种种查找的方法就是枚举上下行边界，再在每列查找。每个子矩阵要求四条...

题目大意 给出，求出 解题思路 看到这样的数据范围和数的大小，显然是不可能用类似两重循环的暴力方法搞过的。所以，我们要开始尝试用分解的方式来解决。看到求gcd，就应该尝试对给出的数分解质因数，然后对每个质因数分别讨论其幂次。那么，这个问题就转化为了个子问题。 这样，每个子问题都形如给出，要求出 那么可以枚举这个最小值，是在取到还是在取到，再求出每种情况的方案数。这里要注意的是：处理好的情况，注意如果要对幂次取模，按照欧拉/费马小定理，模数应该取 。 综上，这种算法运算的次数就是可行的，大约次。 AC代码 #include<bits/stdc++.h> using namesp...

题目大意 有n天，每天穿一件衣服，第天有件衣服可以穿，穿第件衣服的的权值为。求其中任意m天中，所穿衣服的权值最大值与最小值的最小差。 解题思路 我们要做的是最小化最大最小值之差，所以必要的肯定是把所有衣服按照权值从小到大排个序。我们可以把每件衣服打一个标记，记录一下是从哪一天来的。然后在里面维护一个来自不同的天的个数为m，这些衣服的权值必定是大于左端点小于右端点，直接求ans即可。 AC代码 #include<bits/stdc++.h> #define ll long long using namespace std; const int N=2e6+10; struct nod...

题目大意 给定一棵有n个节点，n-1条边的树，每条边长度为1，开始土拨鼠在1号节点，沿着最短路走向n号。 土拨鼠出发t秒钟后，Orange以2m/s的速度跑向土拨鼠，而土拨鼠以1m/s的速度向任意方向逃跑。设每秒钟土拨鼠先移动Orange再移动。土拨鼠可以选择留在原地。 求Orange最晚几秒钟能追上他。 解题思路 思路一 二分时间t，判断在t内土拨鼠是否会被追上。每次都以Orange所在的寝室为根建树，从1到n枚举所有的土拨鼠能够到达的点，然后判断在走的过程中会不会被追上。 这个思路比赛时想到过，就是走一步看一步，只是后来举出几个“反例”，以为很难实现。 思路二 我们先以Orange为...

题目大意 输入计算式，求解。其中2(x)表示2的x次方，式中每一项都对应着答案在二进制表示下的数位为1的位。 解题思路 高精度快速幂，冲冲冲！但是要注意的是具体实现时的细节（队友的高精度写的一堆Bug），还有读入时一层层递归下去。 AC代码 #include<bits/stdc++.h> using namespace std; int a[1005],ans[205],t,l,lans; long long sum; char s[20010]; void big_multi(int a[],int len) { lans=max(lans,len); for(i...

题目大意 给定一棵大小为n的树，有m次操作，分为三种： (1 x w) 位置x上的权值+w，同时所有位置的权值加上w-dis(x,y)；（dis(x,y)为从x到y的边数） (2 x) 如果x位置的权值>0，那么设为0。 (3 x) 输出x位置的权值 解题思路 这题有很多种做法，我再这里用的是魔改版的树链剖分（刚学会）。 操作1 我们在画图分析后，可以得到这样一个简单的式子，来转化操作1： （LCA：最近公共祖先，应该都了解怎么求，为的深度） 对于任意的来说，都应该是个常数，所以我们可以专门记录。接下来，我们设第次的操作节点为，修改的节点为，为；可以得到，我们每执行一次操作1，就...

题目大意 数字n的分区是所有数字之和等于n的集合。 如果分区满足以下条件，则称为神秘分区： 是整数，对于，。 对于任意， 设为的神秘分区的个数。现对于给出的每对，求出。 解题思路 感谢大佬的思路：https://blog.csdn.net/tianyizhicheng/article/details/107773762 显而易见，这道题的做法必须为预处理每个数合法的构造数。由于这个构造的首尾差最大为2，所以我们可以把每个构造的都可以分成3段。现在我们设第一段数值为，那么第二段是，第三段是，设每段长度为。所以我们得到这样的式子： 合并+替换：最后可以得到： 引用一段对于差分的解释...

题目大意 一张纸牌有4个特征，每种特征有3种不同的情况，所以一套牌中有81张不重复的牌。对于4种特征中的每种，当任意三张卡牌这项特征完全相同，或完全不同时，这三张牌组成一个set。有一些万能卡，万能卡的某些特征可以任意决定，例如[*][diamond][solid][red]可以任意决定第一项特征。 给定N张不一样的卡牌，找到任意一种合法的set。 解题思路 暴力出奇迹，直接冲！三层循环判断即可。但是题目中的牌数N≤256，而样例数T≤1000，好像不满足时间要求啊。 但是，由于某些神奇的结论，不能构成set的集合最大就是20，枚举21张肯定可以找到set。（原来出题人提供了原论文，但是我网站...

题目大意 有n道菜，第i道菜有bi盘，每盘利润为ai（利润可能为负）。遵循以下规则为每个顾客上菜：● 每位顾客至少有一道菜。● 每位顾客都得到从1开始的连续编号的菜，每道菜只吃一盘。问能容纳的最大的顾客数，已经可赚取的最大利润。 解题思路 出题人：这是一道 简 单 题。可以发现，i因为所有人都必须吃第一盘菜，所有b[1]就是最大顾客数量。我们求利润a数组的前缀和为s,从大到小取即可。 AC代码 #include<bits/stdc++.h> using namespace std; const long long N=1e5+9,mod=1e14; long long a[N],b...