题意：n个数ai，求有多少对ai相乘之后能变成某数的k次方的形式。   可以想到某数的k次方可以表示成多种质因子的k次方的乘积（例：6^3 = 2^3 * 3^3 ），   进一步想，如果对于每个ai我们都按照因子从小到大（不用管质不质因子了，即我们按照同一套分离方法分离所有ai）将 他表示成多个因子的乘积，   如果两个ai乘起来能表达成多个因子的k次方乘积，那么这两个ai分离出的每个因子都是相等的，且每个因子分离出的次数相加等于k。      那么我们就把每个ai分离的情况记录下来，这里怎么记录要灵活运用stl，   int main() { ll ans = 0; int n, k;rd...

题意：一共有S元，给n个人分，每个人允许分到的钱数有一个范围（ l ~ r ），可以不用完s，问最大的中位数是多少   思路：当时做到这里的时候宿舍也熄灯了，脑子还巨困。。。   比赛的时候想的是把全部人按照（ l , r ）排序，然后二分中间那个人的可分配范围，看最多能给这个人分配多少钱。   但是这么写有个问题，，，可能不用中间那个人作为中位数，如：   2 4 2 7 4 4 5 6 6 8  这种情况下，如果按照我的思路是4，但是显然可以有，2，7，4，6，8。。。类似这种取法，原因在于 l 小的人可能 r 大，那么他可以取到更大的范围，这么排列就没啥用了！   昨天晚上一直在绞尽脑汁...

题意：给一串单词依次连接（第一个和第二个，加起来再和第三个......），连接时前一个单词和后一个单词最长的前后缀重合，问最后的句子      拿来复习KMP。。实在太久没写过KMP了,   KMP通过求解最长相同前后缀进行字符串匹配，next数组为最长长度表右移一位得到。   KMP过程中求得是：模式串的前缀与母串的后缀最长相同长度   i代表当前母串匹配位置，每轮匹配 j 初始值为i-1位置母串对应的最长相同前后缀末端位置+1，   如果此时满足，母串[ i ]=模式串[ j+1 ]，则当前最长相同前后缀末端为nxt[ i-1 ]+1 (++j)   因为nxt数组其实是长度表右移，所以最...

贡献题多考虑考虑差分吧🐺   题意：给定一个n*n大小的网格，上面有两种颜色黑和白，要求使用k*k的橡皮擦擦一次，输出最多的白线(全为白的行和列)数目。   这里的行与列其实互不影响，我们分别算出来行列然后相加就可以，   但是怎么判断一个左上角在（x，y）位置的橡皮擦能得到多少全白的行/列实在想不到了。。。   一开始想预处理出来每一行白块的个数（该题和个数关系不大），但是脑子稍微转一转就能想到没什么用啊摔！(ノ｀Д)ノ   能维护的差不多就那么几样，对于每一行，应该找的是每一行最左边和最右边黑块的位置，这样才能判断出橡皮擦到底能不能覆盖全。   预处理完成之后，怎么计算答案也是个问题，知...

题意    若两个数字AND之后不为零则🔗一条边，求图中是否存在环及最小环。    求解最小环    第一次接触求最小环问题，虽然说图论板题多可是他的板子也是真的多啊。。。   求图中的最小环主要有两种方法。      传统的解决方法(dijkstra)      设置w为原图，dis为最短路图，   任意一个环的权值，我们都可以看成i、j的直接距离加上i、j间不包含边(边i->j)的最短路径（w[ i ][ j ]+dis[ j ][ i ]）。求最短路径我们第一个想到的就是Dijkstra算法。而Dijkstra所求的是一个点到所有点的最短距离。用Dijkstra所求的i、j的最短...

淦，不知不觉又一个星期没有写码了   这星期好像就是各种怠惰   捣鼓基友的电脑（广告太多看不下去了）   在自己电脑上捣鼓双系统，   在舍友电脑上捣鼓win10界面美化   穿插着补作业，，一星期就这么没了   不能逃避了，   下周就银川比赛了呀。。。   这周决定全心全力肝肝肝。

Manthan, Codefest 19 (open for everyone, rated, Div. 1 + Div. 2)-E. Let Them Slide   题意：n×w的方格中，每一行有cnti个数字，   每一行的数字都连续的放在一起，但是可以任意的平移。问每一列的最大和为多少。          单调栈+差分    能想到维护每个数字在该行能影响到哪些列，一开始想单调栈，但是不知道维护出来之后怎么累加的问题，   对于每行的第i+1列，其实和第i列有很大的关系，（由第i列加一些值减一些值得到）//差不多滑窗？？？   记录每个值影响区间的左右端点之后，左端点处就把该值加进来，...

题意：对应每个 i 给出一个数si，代表i之前比ai小的值的和，求原序列。   链接：https://codeforces.com/contest/1208/problem/D   对着样例乱猜看出来最后一个0的位置就是1，进一步想到，把1出现的位置之后都减去1，   然后从整个序列里再找最右边（优先搜索右子树实现）的0就是2，然后又是新一轮构造------   想拿树形结构维护，每次要找的是0，一开始思维局限在找0上，其实这个0也是最小值呀摔，   线段树维护的无非那几样东西，最大最小区间和，0是最小值就每次维护最小值就好了，每次进行减操作就是区间修改，   还有要消去前面计算过的0对后面的...

CodeForces 1214-E Petya and Construction Set 树上构造   题目大意：你需要构造出一个节点数为2n的一棵树. 给出n个正整数 di。   你构造出来的树需要满足：第 2i−1个点与第 2i个点在树上的距离恰为di。这里定义两个点 之间的距离为u到v路径上的边数.如果有多种方案，输出任意一种即可。      又是构造题，可以发现奇数点之间没有关系，偶数点之间也没有关系，   单独把偶数/奇数点拿出来先构造出一条链（按照距离最大的在链头，这样才可以把距离等于链长的放在链尾），   然后在链上找满足题意的分叉点，如果两点距离等于当前链长就把点加到链最后并增...

Technocup 2020 - Elimination Round 1-C  Save the Nature    好久不打比赛一打就unrated？？？   被掉分掉自闭了之后，每次好不容易鼓起勇气打一场网站就炸到unrated，，，我枯了‘   这次的C题差点点就写出来了哎呀，本来想贪心不过发现贪不动，队友喊了句二分加验证就开始胡写，   第二天交了一下WA5，原来是贪心没贪全。思维还是不够爱，永远差那么一点点（指间宇宙）   int n; ll x,y,a,b,k; ll p[MAXN]; int tag[MAXN]; //不仅要满足分配给a尽量大的 //还要满足分配给a+b尽量大的 ...

Educational Codeforces Round 72 D. Coloring Edges（拓扑判环）   题意：现在有n个点，m条有向边，现在要对这m条有向边染色，染色的要求是在一个环里面的边的颜色不能相同，   现在让你求出最少要几种颜色，才能满足条件的染色，并输出方案数   首先判断有无环，没环直接1，   有环的话，设计一种染色方案（差不多是个构造？CF里面好多方案不唯一的都要自己指定一种行之有效的方案出来）   考虑存在环的时候，必然既存在从小点指向大点的边，也存在从大点指向小点的边，对这两种边分别染色就可以保证环内颜色不同，   所以最多只需要两种颜色   #include...

题意：   一个人在原点s，每个城市有对应的评价值w，不能走上次刚走的点，   比如最开始从6-2，下一次不能立即从2-6，但可以通过绕一圈6-2-1-3-4-2-6的方式回到6，意味着每个节点每条边都有可能经过多次，每个节点只算第一次经过时候的值。   求他在整个图中经过的城市累积的评价值的最大值。    既然可以转圈圈，首先对强连通分量缩点，   缩完点之后第一次dfs预处理每个点的val值，对每个点，只要他的后代结点有环，就可以到达后代结点并回来，   那么后代结点的值直接累加到该点，对后代节点置零。   第二次dfs就是普通树上dp，因为到现在就是选择哪条链的问题。   还有模一下ta...

迷茫了大概一个星期了吧   拜托拜托   快点振作起来啊   明明知道无所事事之后会很烦恼的   就不能有自制力一点吗   明明都已经这么菜了   再不努力一点的话。。。   学不下去也尽量学一下   拜托了

不知不觉好久没写博客，怠惰惹   #include<bits/stdc++.h> using namespace std; #define stop system("pause") //0 dragon,1 ninja,2 iceman,3 lion,4 wolf const int MAXN=1111;//每个总部最多能有多少武士 const int WNUM=5;//一共有多少种武士 class Head; class Warrior//武士 { private: int kind;//类型 int cnt;//该武士编号 Head *phead;//属于哪...