好题图论的难点在于建图~首先我们关注到如果两个草堆之间的差大于K，那么他们的位置就是固定的，就相当于给了一些限制，这就是很经典的连边然后拓扑排序。其实你是不是可以直接从小的向大的连边（我没试）然后再做排序。这一部分代码（粗略验证正确性，赶着写的，可能比较一言难尽）#include<bi

“交互的本质是二分”本题的询问次数卡得很严，必须保证每次都能让候选点集合严格缩小一半。因此三选二的时候不能任选，而要选较大的两个点击查看代码#include<bits/stdc++.h>usingnamespacestd;vector<int>a[100005];introot,p,val,s[100005],cnt[100005],va[100005],d

注意可能出现dpx+1在模意义下为0的情况，此时需要额外维护0的个数而不能求逆元记f[x]表示x子树内包含x的连通子图的个数，g[x]表示全树包含x的连通子图的个数，由于子树的限制，所有fx互斥【子树互斥模型】求出f[x]后换根DP求出g[x]。答案即为u-LCA(u,v)上f的和+g[LCA(u,v)]+v-LCA(u,v

怎样实现自定义排序函数的堆呢？从C++11开始，如果使用lambda函数自定义Compare则需要将其作为构造函数的参数代入，如：priority_queue<int,vector<int>,decltype(cmp)>q(cmp);decltype说明符可以推断表达式的类型当然本题其实不需要自定义排序函数，因为在调用排序运算符时，决

T1数位设\(dp_{i,0/1}\)表示前i位，最后一段是/不是d倍数的方案数令\(d=2^x5^ym\)可以将模d同余转化为模\(2^x\)，\(5^y\),\(m\)分别同余因为\(2^{20}=1048576>10^6\)所以，当\(j<=i-20\)时，前两项的结果均为0所以首先可以开两个前缀和，求sum[i-1]*10+s[i]-'0'对前两项的取模结果

利用线段树划分区间【l,r】点击查看代码#include<bits/stdc++.h>usingnamespacestd;intl[100005],r[100005],w[100005];vector<int>a[100005],c[100005];vector<pair<int,int>>ans;voidask(intl,intr,intu,intv,intid){if(u<=l&&

T1Reversehttps://www.gxyzoj.com/d/hzoj/p/P980假设1在点i时，这个1可以通过一次翻转到达那些点，将这些点和i连边，此时答案就是s到x的最短路但是，此时边数也会到达\(n^2\)级别考虑优化，因为边权均为1，所以可以直接bfs，可以发现每个点能转移的点的奇偶性是有限制的，而且每个点至多被更

Problem给出两个数组A,B，进行q次询问，每次分别给出这两个数组的某个区间l1,r1,l2,r2,也就是\(A_{l1\simr1}\)与\(B_{l2\simr2}\)，有两位同学小L和小Q分别从A,B的以上区间中选一个数，而两数乘积为此次操作的分数，小L希望分数大，小Q希望分数小，请问他们每次以最优策略进行游戏，分数将会

独立做出了百度之星决赛的金牌题，开心~动态转移的时候直接新开一个数组存储历史值，更清晰简洁，不给自己找麻烦在memcpy语句中，被操纵的数组在前点击查看代码#include<bits/stdc++.h>usingnamespacestd;vector<int>a[100005],c[100005];intcnt[100005];longlongf[1000

水一篇题解。也是一道并查集的好题，涉及另一个并查集的基本应用，并查集维护连通块（我跟并查集过不去了？？？）大致题意：给你一棵树，对于每次询问求一个点所在连通块中到达该点的最小路径权值大于给定值的点个数。既然都连通块了，那我们在维护连通块的时候直接不把权值大于K的边加进去，用并查

【构造思路】有序化问题，按b从大到小考虑，构造当前的合法方案中包容性最强的方案，动态判断首先，对于最大的b，让r=l就好了，需不需要让r稍大一点，来让它避免被其他区间覆盖？不可能有这种情况其次，对于所有的b-1，你需要为所有的b都找到一个覆盖它的区间，并且所有的b-1之间都不会相互覆盖以此

当然可以用树形DP做，但是转移的细节很多，关键是要将所有可能的情况纳入DP的设计中四种情况：贡献1个给父亲、不需要父亲贡献、父亲贡献1个给该子树、父亲贡献2个给该子树题解的做法：对于1个大小为n的、只有根节点完成的子树，需要的次数一定为n/2另一种可能的做法：方案自动机：我们只要

备战acm校队第二天。实惨，排序学了好几年了，还是没有熟练，意难平啊。特此打开oi-wiki，从头到尾把排序敲一遍。选择排序比较简单。就是把数组里最大数找出来放到最后，然后再把第二大的找出来放在倒数第二位，依次类推，排序就结束了。注：TMD，Dev-C++原来不能把中文注释在代码，不然拷贝出来

题目描述王老师脑袋一拍，定义了乘加运算！他定义 a∗bc=(a+b)×c 。而且他觉得用括号来规定运算的先后顺序太麻烦了，他给乘加运算定义了一个权值的系数（为乘加运算的下标），权值大的乘加运算先进行。例如下面的表达式：=====​9 ∗34​ 9 ∗12​ 1 ∗23​ 6 ∗41​ 29 ∗34

题目描述王老师的班级要开始评选三好学生啦，最后要评选两个人出来。王老师班级一共有 n 个学生，编号分别为 1,2,…,n，每个人把自己心中的两名最佳三好学生 a 和 b 告诉王老师。可能存在两个人，他们心中的两名最佳三好学生是相同的。例如样例1所示。现在王老师要选出

\[Problem\]有\(N\)个机器人，给出\(M\)组关系，表示两个机器人的能力关系，问至少需要前几组关系可以确定所有机器人的排名。\[Solution\]由于是求最少的前几组关系，而关系越少越难确定排名，关系越多越容易确定，不难发现本题满足单调性，考虑二分。那么给出关系要求总排名的题，就应该

对于路径操作，DFS序是不可做的，可以考虑欧拉序欧拉序：对一棵树进行DFS，无论是第一次访问还是回溯，每次到达一个结点时都将编号记录下来，长度为2(n-1)+1=2n-1，每条边都被访问两次在LCA问题中，可以通过欧拉序将其转化为RMQ问题于是，[l,r]内DFS序最大的节点为路径的一个端点考虑记录下每

当我们考虑树的直径时，我们不应该孤立地考察这条链，而应考虑这条链在整棵树中的地位也就是说，如果树的直径不超过2*r1,进攻方选择树的直径的中点即可覆盖整棵树的节点尝试证明你感受到的结论，而不是逃避它；相信OI是美的在经过树的直径判定后，进攻方选择任意一个节点都不可能覆盖树的

寻找性质优化DP:对于一个音高为\(a_i\)的音符，在最优解中，接在其后面的音符一定是离这个音符最近的音高在【\(a_i-k,a_i\)】或【\(a_i,a_i+k\)】内的音符这个音符是可以通过线段树预处理求出来的点击查看代码#include<bits/stdc++.h>usingnamespacestd;longlonga[10000

决定写写Ynoi。P4119[Ynoi2018]未来日记最初分块。也是第一次品尝的Ynoi大分块。1lrxy将\([l,r]\)区间内的\(x\)全部变成\(y\)。2lrk查询\([l,r]\)区间内的第\(k\)小值。查询第\(k\)小看起来是个非常复杂的操作，一般来说看到这个想到的是二分

例题1：有 N 个物品，从 1 到 N 编号。对于每个 i（1≤i≤N），物品 i 的重量是 wi​ 价值是 vi​。太郎决定从 N 个物品里选一些放进背包带回家。太郎的背包的容量是 W，因此放进背包的物品的总重量不能超过 W。求太郎带回家的物品的总价值可能达到的最大值。1.贪

原题链接题解暴力方法：遍历每个节点，遍历每个节点的子节点，遍历每个子节点的子节点，看看子子节点是否是节点的子节点，时间复杂度\(O(nm^2)\)优化考虑无向边建边的时候建成有向边，且两个点建边时，度数小的指向度数大的，如果度数相等，编号小的指向编号大的（其实这一步是为了避免重复计数

这次真的是差五分钟就能过掉这题了，好可惜呀二进制数位的包含关系构成一颗树，我们可以在这棵树上DP来统计一些信息十五分钟加上这样一个DP，未必来不及。只是，越到时间紧张的关头，越要屏蔽其他念想的干扰，告诉自己不去管时间，把注意力集中在代码的编写上如果你写完代码能一遍过，那时间

ios::sync_with_stdio(false);cin.tie(0);\(\Uparrow\)关闭同步/解除绑定，可以优化读入字符串的效率这行代码的缺失，不仅导致程序在本地运行时需要过好几秒才能读入数据，更导致程序在OJ上评测时TLE时隔半年，自己还能独自完成KMP和AC自动机的代码，还是比较开心的；调试时，把握整体，注

朴素算法不必多说，\(O(n^2)\)的暴力dp转移。优化算法时间为\(O(n\logn)\)，本质是贪心，不是dp。思路是维护一个单调栈（手写版），使这个栈单调不降。当该元素\(\ge\)栈顶元素时，把这个元素压入栈中。否则，在单调栈中找到第一个大于该元素的项，把这一项改为这个元素。（因为要