思路：为了保证为平方数，如果的某个质因数的个数为奇数个，那么的该质因数个数也应该是奇数个，依次类推，那么所有中出现过的质因数在每个中出现的次数要么都是奇数个要么都是偶数个，取代价最小的。 MyCode: #include <bits/stdc++.h> typedef long long ll; const int maxn=1e6+7,mod=1000000007; using namespace std; bool vis[maxn]; vector<int>prime; inline void init() { for(int i=2;i<maxn;++i)...

P1383 高级打字机 这题用红黑树实现的可持久化数据结构可以很轻松的AC，码量非常小，自行百度。 MyCode: #include<bits/stdc++.h> using namespace std; const int maxn=1e5+7; typedef long long ll; typedef unsigned long long ull; struct node { int lt,rt; char s; } t[maxn*10]; int tot,len[maxn],rt[maxn]; char ch,op; void modify(int &x,int l...

如果颜色最多个数大于其它颜色之和，可以匹配的对数就是其它颜色之和，即其它颜色的都和颜色最多的两两匹配反之，每个颜色都能找到匹配，因为其它颜色匹配后，剩下的只要不断拿出两个去拆已经匹配了的一对，一定能用完。 MyCode: #include<bits/stdc++.h> using namespace std; const int maxn=2e5+7,maxm=4e5+7; typedef long long ll; inline ll read(){ ll s = 0, w = 1; char ch = getchar(); while (ch < 48 || ch &gt...

给定 n 个点，m 条有向边，给定每条边的容量，求从点 s 到点 t 的最大流。 DinicDinicDinic算法复杂度上界为n2mn^2mn2m，可以优化到nmlogCnmlogCnmlogC ，CCC是最大的流量，代补。 HLPPHLPPHLPP算法复杂度上界为n2mn^2 \sqrt{m} n2m​，并且在经过优化后这种算法在数据随机的情况下速度也不亚于上述两种增广路算法。 常规： #include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #incl...

1 7 1 4 6 5 6 3 1 2 1 6 1 7思路：先以为根画出上面的图。节点度为，有两个度为的叶子节点，我们可以知道，如果将边断开，然后再将其中的一个叶子和树上度为的叶子相连（比如连），此时是最优的，因为这样不必在断开后还需要断开的一个叶子。 所以我们的策略是：如果某个点只有一条链，不操作；如果有两条链（两个叶子节点），就和上面一样操作，如果有多于两条，任意连即可（随便和其它叶子节点连接）。 MyCode: #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned...

坑：又是一种可以搞死面向案例编程的选手的恶心案例，仗着数组是自己隐藏的，自己是知道答案的，于是就假装问几下然后就输出答案。这题别看样例！光这几个问答根本确定不了排列。 思路：通过一定能找出的位置，如果那么，如果，那么 找到之后就可以通过来得到的值。 MyCode: #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; const int maxn=1e4+7; int a[maxn]; int main() { int t,n,num; s...

拆点后入点和出点两条（容量，边权）为的边求解最大流需要寻找所以一条增广路，为了费用之和最小，可以改用spfa寻找一条单位费用之和最小的增广路，每次在残余网络中跑最长路，直到找到最大流。这题不要求最大流，所以如果残余网络中得不到费用后可以直接退出。 MyCode: #include <bits/stdc++.h> using namespace std; const int maxn=5010,maxm=200010; typedef long long int ll; int head[maxn],Next[maxm],to[maxm],edge[maxm],tot=1,d[max...

方法一：记忆化二分，有这么两种二分：、第一种和线段树的所有区间重叠，的子区间都是，如果开个桶去记忆化，需要查次，但可以知道的是被遍历的区间远小于这么多，所以可以去记忆化。 方法二：将扩大到的幂次，然后预处理的幂次的下标的值（即对原数组分块）。然后每次二分答案在那个块里面（已经预处理，不需要询问测评姬），接着只要在长度不大与的块里面二分询问就可以了。找到答案后用树状数组维护的值增加的值。 MyCode: #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long lo...

思路：无向图不连通则必有两个点不连通，枚举两个点，求在剩下的个节点中最少去掉多少个点，可以使和不连通，在每次枚举的结果中取最小值就是这题的答案。拆点的两种方式：1.入点和出点分别是和，需要知道有多少个点2.入点和出点分别是和 点的出边到的入边的最小割就是需要去掉的点，枚举完后把反向边的容量加回去就可以把残余网络复原了。 MyCode: #include <cstdio> #include <queue> #include <cstring> using namespace std; const int maxn=110,maxm=6e3+10; int he...

思路：用网络流跑二分图的最大匹配，先将H公司第个人的编号变为，然后表示公司和公司的两个人有关系,待匹配。残余网络中非匹配边为从左部到右部的有向边，的边权为，匹配边为从右部到左部的有向边，边权为。非匹配边：，表示边的容量匹配边：因为要求不可行的边的数量，即不是可行边和必须边的边；先跑一遍最大匹配最大匹配时，必须边一定会被包括，所以如果，那么它就不是必须边，如果边上的点又不在一个强连通分量内，那么也不是可行边，而是不可行边。 MyCode： #include<bits/stdc++.h> using namespace std; const int maxn=2e4+7,maxm=2e...

题意：组数据，每组数据输入一个，接着输入个数，表示一个数组，然后一个，表示组询问，接着输入个整数，对每次询问输出它的异或第小值。 思路：高斯消元后的线性基是一个对角矩阵，有一个非行就表示有多少个数成功插入，同时异或谁就相当于加上谁，这和二进制的位权刚好想对应，大的向量对应高位权，小的向量对应低位权。有个非零行的线性基能表示个不同的数，而线性基是线性无关的向量组是不能异或出的，所以如果有不能成功插入的数，该数组就能表示个不同的数. MyCode: #include<bits/stdc++.h> using namespace std; typedef long long ll; ty...

思路：首先，判断极角相同可以用斜率表示。用一组最小正整数表示一个极角。我们可以将没个极角标号，而对于一个点，我们可以看作它是把两个不同的极角连边。那么问题就变成了：给定一张图，两条边可匹配当且仅当它们连接一个相同的点，求每条边唯一匹配的最大匹配数量。 最大边匹配 这里有个结论：对于一个无向图，使用遍历同时给图中节点打上深度标记后，除去走过的边，剩下的边连接的两个顶点它们的深度一定不相同。显然，如果存在某条边两端深度相同，那么在遍历到其中一段时，一定会走这条边遍历到另一端。因而，这样没有被遍历的边称为返祖边。 处理这一类问题可以建一颗dfs序树，从叶子节点开始考虑，先不考虑这个点连向父亲的边，如...

A. Tit for Tat   思路：(从最高位开始)高位不断减一、最底位不断加一，直到高位都为或者操作了次 MyCode: #include <bits/stdc++.h> using namespace std; const int maxn=1e5+7,maxm=2e5+7,mod=1e9+7; typedef long long int ll; typedef unsigned long long ull; inline void solve() { int n,k; cin>>n>>k; vector<int>a(n+1); for(...

别人链接：1^@^1 MyCode: #include <bits/stdc++.h> using namespace std; const int maxn=1e5+7,maxm=2e5+7,mod=1e9+7; typedef long long int ll; typedef unsigned long long ull; mt19937 read(time(0)); ll mul(ll a,ll b,ll p) { ll res(0); while(b) { if(b&1) res=(res+a)%p; a=(a+a)%p; b>>=1; } retur...