网络优化 题目大意 有一个区间，有条网络，第条网络的服务区间为，但是它只能提供个人的服务。问：如何分配才能使得同一时间上线的人数最多？ 分析 那么就考虑对于每一个点它是否能够被覆盖到，贪心即可。那么贪心过程就可以是从左到右枚举区间上的每一个点，然后在符合条件的服务器中扣除一个人的服务。那么如何来维护符合条件的服务器呢？  先将左右的服务器按左端点从小到大排序 将所有的的服务器加入到优先队列中 把所有或者不能再提供服务的服务器弹出 如果此时优先队列不为空，那么这个人可以上线，有的贡献，将这个服务器的服务人数减一 如果此时优先队列为空，那么这个人无法上线了，没有贡献   时间复杂度大概是的 Cod...

[SDOI2017]数字表格 题目大意 求： 其中： 分析 这其实是一个多么裸的题，最多就用了一个欧拉定理。。。 那就直接来吧(规定) 其中，那一坨多么难看的指数可以拉出来特殊关照一下 那么就有 带回原式，可以得到： 这一步稍微交换一下求值顺序即可得到，然后就是中间多出来的那块求积的东西是可以预处理的，时间复杂度大概是级别的，最后的最后就是一个数论分块，因为预处理完后，这个就可以化简为： 这样以来，就十分的显然了，那么到这里，这道题就是真的完了 唯一值得注意的就是指数那一坨可能特别的大，于是乎可能需要一个欧拉定理之类的东西 但是看到，就知道只需要一个就够了，是否用欧拉定理只是对于常数优化的问题...

Minimizing maximizer 题目大意 有一条长度为的线段，然后会按照顺序给你条线段（固定起点终点）问，你按照顺序使用这条线段，最少要多少条才能把整条线段覆盖完但是题目有一个条件，大概就是这条线段至少与之前的覆盖的线段有一个交点 分析 那么这样的话，就可以设计动态转移方程表示从开始覆盖到的最小代价然后因为要求了一定与前面的线段有交点，所以方程如下： 注：表示的是枚举到的是第个线段，而并不是一个二维的然后直接这样维护，它的时间复杂度是，然后观察到这个是查询的一个区间最小值就是说这个东西大概可以用一个叫做线段树的数据结构来维护一下，这样下来，时间复杂度就变成了但是需要注意的是，更新的时...

CF1132D Stressful Training 题目大意 有台电脑，一共要撑过分钟对于每台电脑，他的初始电量为，每分钟消耗电量为问，至少需要一个功率(每分钟)为多大的充电器才能保证的电量都不为负 分析 按照贪心的思想，对于每一分钟，充电器应该用给那个还能坚持的时间最小的那个这一定是一个必要操作，正确性显然 对于初始电量可以撑过分钟的电脑，可以忽略不管 那么对于两种功率的充电器，可以简单证明，如果可以满足条件，则一定满足条件这满足二分答案的性质 所以就可以用二分答案来求得需要的答案（二分右界设为无穷大） 对于操作，可以用一个优先队列/小根堆之类的东西来维护首先表示的是这台电脑能用多久，显然...

[SCOI]最长距离 题目大意 给你一个图，里面有障碍你能移走个障碍，然后求能够联通的一个点对的最大距离是多少 分析 因为求的只是一个点对的最大距离，所以其实我们只需要一走这一条路径上的障碍即可 那么只要路径上的最小障碍数量小于等于就可以更细答案 求路径上的障碍数可以用最短路的思想，把点权看作边权即可 Code #include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 50 + 10; const int mod = 1e9 + 7; inline int __read(...

List of Intergers 题目大意 求第大的大于等于 且与 互质的数 分析 即，求最小的 使： 莫比乌斯反演 那么看见这个形式，自然而然地会想到这个东西： 所以就可以把 写成： 那么交求和顺序，先枚举 的因子 ，可以得到: 那么，这个时候，后面这一块，已经是十分好求的了，可以直接枚举 范围内 的因子(顺便得到 )的因子，按照这个直接加就可以了 容斥 还是考虑，换一种写法呢就是 那么就是说，不合法的就是 那么按照套路，还是应该用总共的减去不合法的， 那么就要枚举的每个因子对答案的贡献 同样的，还是可以得到容斥系数就是 那么还是能够得到同一个式子： 当然，这并不是巧合，有兴趣的同学可以自...

完全平方数 题目大意 就是请你求第无平方因字数 分析 有感觉的同学会发现，这个似乎和有关 此话怎讲？ 先考虑的定义 那么显然可以得到，无平方因子数的个数可以有如下表示 即所有无平方因字数的贡献都为，而其他数没有贡献 那么从这里开始就可以有两种做法了 容斥 就是说，要从简单的入手 用去减掉带有平方因子数的个数 那么就可以来枚举一下每个完全平方数对答案的贡献 那么，现在有这些素数 的贡献就有 但是例如这个数它其实是被计算了两次的 多枚举几个数以后，会发现由偶数个素数构成的数会被重复计算，那么重复的部分是需要减去的  如图，红绿蓝三个交集再三个大圆中被重复计算了，中间那个像勒洛三角形的部分再减去原交...

[HAOI2018]硬币购物 都这年头了，还有谁购物用硬币的吗？ 题目大意 首先，你有四种面值的硬币 然后你会出门采购次 每次出门，你都会带上一些硬币，每种硬币的个数给定 然后你买了的东西 问你有多少种付款的方案 分析 直接写裸的背包的时间复杂度直接炸天 那么正难则反是一个十分优秀的想法 就是说，可以不计代价的用总的方案减去不合法的方案 那么剩下的全是合法的了 那么，就要分别统计 这四种硬币构成的所有集合的不合法的方案 及当且仅当上述集合中的种类的硬币不满足条件是的总方案数 怎么求？ 首先，可以用到二进制枚举子集，得到上述个集合 然后考虑容斥 可以得到，子集大小为奇数的容斥系数为，而偶数的容斥...

[CQOI2017]小Q的表格 题目描述 给定一个表格，满足：     有次操作  每次操作修改的值，为了使整个表满足条件，所以要修改的点还挺多的 然后让你输出的范围内的数的和  Solution 对于性质，观察发现它可以转化一下： 对于转化到不太理解的同学，可以看看这个结论 这里就不细说了 所以可以得到一个结论： 为了方便后文描述，这里就记 那么就得到了一个线性的表了 那么再回头看看题目要求的问题 考虑: 所以原式可以化为: 那么这个时候我们发现，后面的是可以直接求解的（先预处理，就可以直接查询） 然而前面那个是会发生改变的 这个可以用树状数组或者是分块来维护 这两个理论上是可以过的，实测再...

[SCOI2009]游戏 题目大意 有一个到的序列, 每个数可能对应另一个数 不停的变换, 直到变回串, 一次变换记作一次花费 问你对于所有可能的对应关系, 有多少种不同的花费 分析 显然, 无论对应关系如何, 这些有对应关系的数一定构成环(包括自环) 对于每一个环, 若他的长度为, 那么这个环归位的花费一定为 那么原串长度可以表示为, 那么花费就为 所以问题就转化为了有多少种不同的 再考虑所有的, 可以表示为 看上去是不是有点点像背包了呢? 因为我们知道, 那后每个物品至多选一次(若可以选多次, 那么后面选的不应该有贡献, 如上式), 似乎就可以写一个背包了呢 所以我们可以先处理出内所有的素...

联合权值 题目大意: 你有一棵树,问你距离为二的节点的最大联合权值与联合权值和 分析: 找到中间的点, 然后枚举他的儿子们, 求个和, 然后再求个最大值, 好像就完了 #include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 2e5 + 10; const int mod = 10007; inline int __read() { int x(0), t(1); char o (getchar()); while (o < '0' || o > '9') {...

The XOR-longest Path 题目大意 给定一棵树, 让你求树上异或和最大的简单路径的异或和 分析 想要异或和最大, 那么我们想要的显然是贪心, 那就是尽量让他们在二进制下不相同 这样考虑的话, 我们可以想到的是字典树, 从高次项向低处贪心, 能保证最值 那么还有一个问题, 如何求一个简单路径的异或值? 我们又可以想到关于异或的优良性质: 就是说, 可以随机找一个根, 求到其他所有结点的链的路径异或和 如果我们要求的是, 那么它就可以十分简单的表示为 那么我们把所有的从根开始的路径插入到字典树中, 暴力查询跟新答案就好惹 #include <cstdio> const ...

Closest Equals 题目大意: 给你一串数,有次询问,每次求问一个区间,问在区间内最近的两个相同的数的距离是多少 分析: 第一反应就是记录一下这个值上一次出现的位置,这就可以记录一次答案了 然后可以构造出一个新的序列,因为当某两个可行的数在另外两个可行的数内时,外面的数是没有贡献的 然后就可以找到第一个的, 然后再找到最后一个 这就构成了一个新的可行区间 那么如果找到的新的那么这就是无解的, 直接输出 #include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 5...

Present 题目大意: 先给你一串序列,你至多有次操作使得一段长度为的区间加一问这串序列的最小值最大可以是多少? 分析: 最小值最大或者最大值最小,我们的第一反应可能都是二分答案  简单证明一下:  如果最小值最大为,那么只要我们少做一次操作,那么也是可行的这满足二分答案的性质,所以呢二分答案没有问题的   那么关于函数的话,如果当前我们枚举到的数他小于这个我们的值,那么我们就给这一段区间加上这个差值(如果可以加,否则返回零)那么时间复杂度大概就是,可以接受的 #include <bits/stdc++.h> using namespace std; typedef long ...