题目链接：https://vjudge.net/contest/381753#problem/G 知识预备：数位DP数位DP的题目往往是这样的：给定一个闭区间[L,R],求这个区间中满足"某种条件"的数的总数量。数位DP技巧：技巧1：[X,Y] -> f(Y)-f(X-1)把统计[L,R]范围满足条件的数的个数转化为统计[1,N]内满足条件的数的个数，这样，f([L,R]) = f([1,R])-f([1,L-1]) , 那么接下来讨论问题只需要考虑上边界就行了。技巧2：树的方式来考虑代码实现用dfs从高位到低位枚举解题思路：对于这道题，dfs需要记录的状态有：1.现...

题目链接：https://vjudge.net/problem/%E8%AE%A1%E8%92%9C%E5%AE%A2-A2144题目大意：求n行三角形中等边三角形的个数，图二的三角形也算，n<=1e9解题思路：n范围这么大，一看就是个找规律题，那么先来打个表看看。打表(暴力)代码： #include<bits/stdc++.h> using namespace std; struct node{ double x, y; }a[6000]; int n, cnt; double dis(int i, int j) { return sqrt( (a[i].x-a[j].x)...

题目链接：https://vjudge.net/contest/381753#problem/A预备知识：回顾二分图：二分图：无向图G=(V,E),如果可以把结点集分成不相交的部分，即X和Y=V-X，使得每条边的其中一个端点在X中，另一个端点在Y中，则称图G是二分图。二分图最大匹配1.把二分图的两个结点集称为X和Y，有时也称为左边和右边，其中左边是X集，右边是Y集2.匹配(matching)是指两两没有公共点的边集3.最大匹配问题： 1.给出一个二分图，找一个边数最大的匹配；选尽量多的边(匹配边)，使得任意两条选中的边均没有公共点。(一个男人只能跟一个女人领证，考虑非诚勿扰)4.如果图中所有点...

题目链接：https://vjudge.net/contest/381753#problem/B解题报告：题目大意：两个矩形能把平面分为多少个区域？解题思路：列举两个矩形的关系。别漏，列全~  代码： #include<bits/stdc++.h> using namespace std; bool check(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4) { return (x1<=x3&&y1<=y3&&x4<=x2&&y4<...

题目链接：https://vjudge.net/contest/381753#problem/C解题报告：题目大意：要满足ai都小于等于k，且所有ai+an-i+1都相同。问最少从a中更改几个数？(1<= a <= k)假设ai+an-i+1 = x, 这个x有很多可能。  设minn = min(ai, an-i+1) maxn = max(ai, an-i+1)分类讨论：当x位于[2,minn],需要更改ai和an-i+1(2)当x位于[minn+1,minn+maxn-1]，需要更改其中一个(1)当x位于[minn+maxn]，不需要更改(0)当x位于[minn+maxn+1...

题目链接：https://vjudge.net/contest/381753#problem/E解题报告：一开始的错误想法：一开始q跟9的幂次比较并不能说明答案是几位数，比如999就是3位数可以达到的最大值，q如果大于它只会是4位及以上。然后跟据判断答案是几位数来通过dfs凑。啊，这...比如75，就是两位数无法通过乘积构成，然而355就能乘起来等于75.因此显然是个错误想法。dfs部分没有问题，但可以更简单。正确思路：从9到2枚举(不需要到1，因为1完全没有作用还使得答案变大)，不断把q分解，(从大到小枚举是为了使得答案的位数尽量少),然后基于统计的思想，把小的放在前面，大的放后面。 代码：...

通过电子科技大学ACM集训队的视频学习了莫比乌斯反演本篇内容为学习笔记  题目引入：给定整数N和M。求满足1<=x<=N, 1<=y<=M,且gcd(x,y)为质数的点对(x,y)的个数。数据范围：1<=N,M<=1,000,000 目录：1.莫比乌斯函数2.莫比乌斯函数的线性筛3.狄利克雷卷积介绍4.莫比乌斯反演5.整除分块6.杜教筛介绍 莫比乌斯函数：线性筛： int prime[MAXN], prime_tot; bool prime_tag[MAXN]; int mu[MAXN]; void pre_calc(int lim) { mu[1] = 1...

先看题目：https://ac.nowcoder.com/acm/problem/14399解题思路：因为数据量并不大( ),所以用试除法(O(√n))不会超时代码： #include<bits/stdc++.h> using namespace std; int factor[110]; int main() { int T; scanf("%d",&T); while(T--) { memset(factor, 0 ,sizeof(factor)); int x, tot=0; bool flag = 1; scanf("%d",...

算法思想 基本思路：对于给定的一个整数 n，显然如果 n 为素数（Miller-Rabin 算法判断），那么算法结束，返回唯一素因子 n。 否则，pollard's rho 算 ***试着找到 n 的一个因子 a（a 并不一定是素数），然后递归 Pollard_rho( a ) 和 Pollard_rho( n/a ) ，即将 n 分为了两个部分，将原问题变成了规模更小的两个子问题。 如何求因子 a？一般情况下可能会本能的想到枚举，但这样过于耗时。寻找因子是该算法中最重要的一步，该算法中采用随机化算法来查找因子 a。假设此时 n 仅有 2 个因子 p 和 q，那么如果我们用随机数来找 n 的因...

作用：有时候我们想快速的知道一个数是不是素数，而这个数又特别的大导致 O( √n) 的算法不能通过，这时候我们可以对其进行 Miller-Rabin 素数测试，可以大概率测出其是否为素数。两个定理： 费马小定理：如果p是素数，a是小于p的正整数，那么a^(p-1) mod p = 1。证明：首先我们证明这样一个结论：如果p是一个素数的话，那么对任意一个小于p的正整数a，a, 2a, 3a, …, (p-1)a除以p的余数正好是一个1到p-1的排列。例如，5是素数，3, 6, 9, 12除以5的余数分别为3, 1, 4, 2，正好就是1到4这四个数。反证法，假如结论不成立的话，那么就是说有两个小...

先看题目：https://ac.nowcoder.com/acm/problem/16710解题思路：公式lcm(a,b) = ab / gcd(a,b)记得要先a/gcd(a,b)然后再乘b以防止越界*代码：** #include<bits/stdc++.h> using namespace std; typedef unsigned long long ull; ull gcd(ull a, ull b) { return b == 0 ? a : gcd(b, a%b); } int main() { ull a, b; cin >> a >> b; ...

先看题目：https://ac.nowcoder.com/acm/problem/16563解题思路：exgcd模板题，求ax≡1(mod b)，可以写为方程的形式 ax = yb + 1, 即 ax - by = 1，这个符号可以塞到y里，令k=-y，就还是二元线性方程的形式了 —— ax + bk = 1exgcd可以解决ax+by = (a,b),那么x/(a,b), y/(a,b) 就是ax+by = 1的解。我们知道通解为x=x0+kb1,y=y0+k*a1,(b1 = b/(a,b), a1 = a/(a,b))，要求ax+by=1，x的最小正整数解，再写个while循环枚举k就搞...

先看题目：https://ac.nowcoder.com/acm/problem/15079解题思路：题目要求的是不是2，5，11，13的倍数，我们可以考虑是2，5，11，13的倍数有多少个，即求|2的倍数 U 5的倍数 U 11的倍数 U 13的倍数|，如果把它们直接加起来，发现会有一些元素重复统计了。(比如计算有n中有多少个2的倍数中会包含5，11，13的倍数)，因此需要使用容斥原理。容斥原理的内容是：对于任意个集合，都可列出这样一个等式，其中左边是所有集合的并的个数，右边是这些集合的“各种搭配”。每个“搭配”都是若干集合的交集，且每一项前面的正负号取决于集合的个数————奇数个集合为正，...

题目描述：就是给你n个数然后从中选择一些出来异或，求异或可得到的最大值解题思路：跟据题目可以假设答案ans=d1d2d3d4...(di代表ans的二进制位0/1)(这里不是乘法哦)，从高位一直枚举到低位，检验是否可行。但如果直接检验的话，复杂度是O(2^n)，显然超时。所以可以从高位枚举到低位，同时枚举检验每一位的可行性。我们可以根据这个列出方程组，这样检验可行性就成了检查截至当前的方程组是否有解。 引入：异或方程组解法(本题仅用到了判定有解，因此只要消元就行)很多异或问题都要涉及到解异或方程组，因此首先要搞懂异或方程组的解法。异或方程组的格式（设有n个未知数，m个方程）：a11x1 XOR...