题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6889伪图论题，板子找的好就能A。大概要求出这个东西：lcm(2,3)+min(lcm(2,4),lcm(3,4))+min(lcm(2,4),lcm(3,4))+min(lcm(2,5),lcm(3,5),lcm(4,5))...我们可以通过唯一分解定理的思路来取min，从i=3开始，若是一个质数，那么lcm取min后肯定是2*i，若不是一个质数，那么肯定为这个数自己，因此，我们的目标就是求i=3开始到n+1(注意)的数的和加上i=3开始的质数的和。鉴于n=1e11，直接套板子。值得注意的是n为1...

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6892思路：最初的思路是这样：把长度作素因子分解，这样分解次数之和(可拆分次数)就可以视作为一堆石子，什么时候取完就是全为1的情况也就是最后状态，但是这样直接转化为尼姆游戏会与题目中所说的有所区别，分解一次，假设除m(从一堆中拿走任意多个素因子(素因子乘积为m)后)在题目中会形成m个堆，那么我们思考，既然被分解后会形成m个堆，这想法还对吗？我们可以这样思考，如果从中拿走任意非2质数，那么肯定会形成奇数个石子数量相同的堆，那么其实最后尼姆异或的结果仍是1个堆的值，新多出来的m-1个堆异或后为0。如果从...

题意：给出n，和a[i]代表第i天东西的行价，问收益最大是多少，在此前提下交易次数最少是多少？思路：维护一个小根堆，每次将堆顶与a[i]比较，如果a[i]<min,直接把a[i]放入，如果a[i]>min,那么可以a[i]-min就暂且作为我当前的收益，当然这不一定是最优的方案，考虑后面如果有a[j]>a[i]，那我这个物品肯定在a[j]卖是最划算的。如果我在a[i]卖了后，再pusha[i]进小根堆，如果到了a[j]再卖的话这个过程中，你会发现ans先加了一个a[i]-min,又加了一个a[j]-a[i]，那么其实对ans的贡献只有a[j]-min,就相当于min在a[j]...

先看官方题解：这个游戏叫做Turning Turtles，它的本质就是Nim游戏。那么它到底是如何转化为Nim游戏的呢？让我们一步一步来分析。 首先，我们先将局面分解一下，每一次我们只考虑一枚硬币。不妨设所有硬币全部背面朝上的局面为局面0假设现在N枚硬币，只有第1枚是正面朝上的。该局面只能转化为全部硬币背面朝上的局面。我们假定该局面为 局面1，则局面1可以转化为局面0。假设只有第2枚是正面朝上的。该局面可以转化为：只有硬币1正面朝上；全部硬币背面朝上。我们假定该局面为 局面2，局面2可以转化为局面1和局面0。同理我们可以推定，第i枚硬币正面朝上的局面为局面i，局面i可以转化为局面0..i-1。...

题意：有一颗n个节点的树，1号点为根节点，其他点上分别放有若干个石子，两个人轮流操作，每次可以将某个节点上的若干个石子移动到这个节点的父亲上面，无法操作者负，问先手是否必胜。 以0(root)为的深度为1，我们首先发现，0作为root，它上面的石子不管有多少对结果都无法造成影响，故可以视为0，再考察深度为奇数的节点，如果这上面有石子，那么不管alice从这里拿多少石子移到父亲节点上，bob都可以模仿alice的操作，这样的话，这些石子又将放到深度为奇数的节点上，直到root，因此直到所有奇数深度都到root，alice无法操作了，就必败了。因此我们可以把奇数节点都视作0，即消失了，因为对答案没...

模线性方程组题目链接：http://poj.org/problem?id=2947有m条记录，n个零件，那么就是m个方程，n个未知数，然后所花的天数和在工厂呆的天数对7同余，也就是求解一个模线性方程组。代码： #include<bits/stdc++.h> #define MAXN 310 #define N 310 #define MOD 7 using namespace std; int a[N][N];//增广矩阵 int x[N];//解集 bool freeX[N];//标记是否为自由变元 int GCD(int a,int b){ return !b?a:GCD(b,...

题目链接：http://poj.org/problem?id=1222就是亮灯问题56的灯，列30个方程，异或方程组一套板子，完事*代码：** #include <iostream> #include <stdio.h> #include <string.h> #include <stack> #include <queue> #include <map> #include <set> #include <vector> #include <math.h> #include <bi...

题目连接：https://vjudge.net/contest/392610#problem/B解题思路：对于每个质因子，显然只有偶数和奇数的两种情况需要考虑，考虑构建异或方程组。高斯消元法一个板子下来，求出自由未知元的个数，然后就是对自由元赋值，0或者1，总共有2^k种，别忘了去掉全是0的情况，因此答案是2^k -1 代码： #include<bits/stdc++.h> using namespace std; #define MOD 1000000007 #define MAXN 2010 #define N 2010 #define INF 0x3f3f3f3f typed...

题目链接：https://vjudge.net/contest/391866#problem/A题目描述：开始的想法是都减去最小的值，这样一个连通块就被分为了若干连通块，如此重复。但这样不好实现。可以反过来去想。既然删点困难可以考虑其逆过程，加点。把所有点从大到小排序，然后放入集合中，然后遍历所有这个点相连的边(x,y),如果y在集合中，而且x，y还没有并查集合并，就合并它们，ans+=b[y]-b[x]最后再把所有根的值都加到ans代码：  const int maxn = 1e5+7; vector<int> to[maxn]; bool vis[maxn]; int fa[m...

题目大意：给出n，问从0到n有多少数对(A,B)，满足A<B,但是A的数位之和大于B的数位之和？解题思路：数位dp。之前使用数位dp，都是求解一个范围[L,R]内满足某个条件的数有多少。这次是求满足条件的对数。学到的第一个是用空间换时间，就是把lima，limb之类的都写进dp里，形成一个5维dpdp[pos][sum][lima][limb][limit]分别代表：1.当前搜索到的位置2.前面已经搜索出来的各位之差3.第一个数最高位此时是否有限制4.第二个数最高位此时是否有限制5.第二个数在前面是否已经大于了第一个数普通的数位dp是在dfs的时候构造一个满足条件的数，而这里的数位dp在...

题目链接：https://ac.nowcoder.com/acm/contest/5675/A思路：对于 i 位置若 a[i-1]* 2%p没有使用过就使用，否则就使用 a[i-1]* 3%p，若两个都已被使用，说明必定有冲突。代码： #include<bits/stdc++.h> using namespace std; const int maxn = 1e6+5; bool vis[maxn]; int a[maxn]; int main() { int t, p; scanf("%d",&t); while(t--) { scanf("...

题目链接：https://ac.nowcoder.com/acm/contest/5675/E题意：从右向左将木块推动，直到不能再推木块，求所有列的max的最小值。思路：比较直观的是二分答案M，然后从高度M，从右往左推，模拟。等价于求前缀平均值的最大。实际上从左往右先把所有能推到左边的都尽量平分到到这一部分去，即前缀和sum平分。考虑到第i列可能比第i-1列小，这时候由于取平均值不会更新答案，而当i列比第i-1列大可能更新答案。 代码： #include<bits/stdc++.h> using namespace std; typedef long long ll; const ...

题目链接：https://ac.nowcoder.com/acm/contest/5674/E思路：对于x，y的公共质因子p来说，如果在x的唯一分解中的幂次为m，在y的唯一分解中的幂次为n那么当mi >= nj的时候， 即j <= mi/n的时候，gcd的p的幂次为nj当mi < nj的时候，即j>= mi/n的时候，gcd的p的幂次为mi枚举i便可以确定mi/n对于大于mi/n的j来说，p的幂次的总和就是：mi(d-mi/n)对于小于等于m*i/n的j来说，p的幂次的总和就是：n(c+c+1+c+2+...+m*i/n)鉴于p的幂次最后会很大，可能会爆ll，可以使用欧...

Problem C — limit 1 secondFear FactoringThe Slivians are afraid of factoring; it’s just, well, difficult.Really, they don’t even care about the factors themselves, just how much they sum to.We can define F(n) as the sum of all of the factors of n; so F(6) = 12 and F(12) = 28. Your taskis, given two ...