- 博客(344)
- 收藏
- 关注
RSS订阅原创 BZOJ2820 - YY的GCD（莫比乌斯反演）
BZOJ2820 - YY的GCD（莫比乌斯反演）题目链接 BZOJ2820 - YY的GCD题意TTT 组查询，每次给定 N,MN, MN,M，求 1<=x<=N,1<=y<=M1<=x<=N, 1<=y<=M1<=x<=N,1<=y<=M 且 gcd...
2019-05-01 17:58:25
221
原创 欧拉函数
欧拉函数定义欧拉函数是小于x的整数中与x互质的数的个数，一般用 φ(x)φ(x)φ(x) 表示。特殊的，φ(1)=1φ(1)=1φ(1)=1计算公式设 xxx 的所有素因子分别为 p1,p2,...pnp_1,p_2,...p_np1,p2,...pn，则φ(x)=x×∏1n(1−1pi)φ(x)=x×\prod^{n}_{1}(1-\frac{1}{p_i})φ(...
2019-05-01 11:01:34
694
转载 C++ __int128的使用
#include <bits/stdc++.h>using namespace std;void scan(__int128 &x) { //输入 x = 0; int f = 1; char ch; if((ch = getchar()) == '-') f = -f; else x = x*10 + ch-'0'; while((ch = getchar(...
2019-04-21 13:40:25
4083
原创 51Nod 1484 - 猜数游戏（离散化）
【思路】把输入的每一个区间都下放到树的最后一层上，把树的最后一层看成一个序列，问题就转换成了求若干区间的交集和并集，交集比较好求，维护左右断点值即可。求并集需要将区间端点离散化后再处理，参考了大佬的代码，比较诡异，不是很懂正确性。还要注意的是，离散化完以后是一个点，对应原来的序列可能是一个区间，也可能是一个点，需要特殊判断。#include<bits/stdc++.h>usin...
2019-03-19 17:21:05
235
原创 51Nod 1405 - 树的距离之和（树DP）
【思路】假设节点标号从0开始且0为树根,设 num[u]num[u]num[u] 表示记录包含 uuu 在内 uuu 的子节点个数, dist[u]dist[u]dist[u] 记录 uuu 的所有子节点到 uuu 的距离之和, dp[u]dp[u]dp[u] 记录最终答案，先计算所有的 num[u]num[u]num[u] 和 dist[u]dist[u]dist[u]num[u]=1+∑...
2019-03-07 17:55:37
287
原创 51Nod 1350 - 斐波那契表示（找规律）
【思路】先考虑如何计算 F(n)F(n)F(n) ，如果 nnn 是斐波那契数，那么 F(n)=1F(n)=1F(n)=1 ，否则尽量把 nnn 减去最大可减的斐波那契数，并重复这一过程，也就是 F(n)={n=1,n是fib数F(n−m)+1,n 不是fib数 F(n)=\begin{cases} n=1, &amp; \text {$n$是fib数} \\ F(n-m)+...
2019-03-05 17:47:56
262
原创 最小表示法（模板）
const int maxn=100005;char s[maxn];int Get_min() {int n=strlen(s);int i=0,j=1,k=0,t;//表示从i开始k长度和从j开始k长度的字符串相同while(i&lt;n &amp;&amp; j&lt;n &amp;&amp; k&lt;n) {t=s[(i+k)%n]-s[(j+k)%n];
2019-03-01 21:25:04
164
原创 51Nod 1873 - 初中的算术（JAVA）
【思路】Java大数可以直接搞，有专门控制输出格式为非科学计数法以及去除后导0的函数import java.util.*;import java.math.*;public class Main{ public static void main(String[] args) { Scanner input=new Scanner(System.in); BigDecimal ...
2019-02-24 23:56:20
142
原创 51Nod 1076 - 2条不相交的路径（边双连通分量-模板）
#include <bits/stdc++.h>using namespace std;const int maxn=100005;vector<int> g[maxn];bool is_cut[maxn];int n,m,ans=0;//节点编号从1开始int vis[maxn];//vis[u]记录u的边双连通分量的编号,从1开始int low[maxn...
2019-02-17 21:18:46
284
原创 圆相关计算（模板）
struct Circle{ Point c; double r; Circle(Point cc,double rr):c(cc),r(rr){} Point point(double a){//通过圆心角a求圆上坐标 return Point(c.x+cos(a)*r,c.y+sin(a)*r); }};//直线和圆交点，解一元二次方程，注意sol没有清空 int ge...
2019-02-15 21:46:04
199
原创 二维几何基础（模板）
#include&amp;lt;bits/stdc++.h&amp;gt;using namespace std;const double eps=1e-10;struct Point{ double x,y; Point(double xx=0,double yy=0):x(xx),y(yy){}};typedef Point Vector;Vector operator+(Vector A...
2019-02-13 18:26:33
162
原创 51Nod 1135 - 原根（数论）
【题目描述】【思路】一个素数 ppp 的原根有 p−1p-1p−1 个，求解方法是对 p−1p-1p−1 进行唯一分解，设 p−1=p1a1p2a2...pnanp-1=p_1^{a_1}p_2^{a_2}...p_n^{a_n}p−1=p1a1p2a2...pnan，则对于一个数 ggg，ggg 是模 ppp 原根的充要条件是 gp−1pi≠1 (mod p...
2019-01-20 22:01:58
210
原创 51Nod 1183 - 编辑距离（DP）
【题目描述】【思路】设 dp[i][j]dp[i][j]dp[i][j] 表示把字符串a的前i个字符变成字符串b的前j个字符的编辑距离，有转移方程dp[i+1][j+1]={dp[i][j]+(a[i]==b[j] ? 0: 1)dp[i][j+1]+1dp[i+1][j]+1dp[i+1][j+1]=\begin{cases} dp[i][j]+(a[i]...
2019-01-13 20:36:16
108
原创 POJ 2348 - Euclid's Game（博弈）
题目链接 https://cn.vjudge.net/problem/POJ-2348【题意】一个以辗转相除法为基础的游戏给定两个整数 a,ba,ba,b ，Stan和Ollie轮流从较大的数字中减去较小数字的整数倍，至少是1倍，且相减结果不能小于0。Stan先手，在自己的回合将一个数字变为0的一方获胜。双方都采用最优策略时，谁会获胜？a,ba,ba,b 都是int范围内的正整数【思路】...
2019-01-12 15:50:17
162
原创 POJ 2484 - A Funny Game（博弈）
题目链接 https://cn.vjudge.net/problem/POJ-2484【题意】n枚硬币围成一圈，Alice和Bob轮流取，每次取一枚或连续的两枚。硬币取走之后留下空位，相隔空位的硬币是不连续的。Alice先取，取走最后一枚硬币的一方获胜。输入n，当双方都采取最优策略时，谁会获胜？【思路】当n<=2时，Alice可以一次拿完获胜。当n>2时，Alice只能现将硬币...
2018-11-28 23:48:21
150
原创 51Nod 1066 - Bash游戏
【题目描述】【思路】看 nnn 是不是 k+1k+1k+1 的倍数即可#include<bits/stdc++.h>using namespace std;int main(){ int T; scanf("%d",&T); while(T--){ int n,k; scanf("%d%d",&n,&k); if(n%(k+1)=...
2018-11-28 23:14:36
118
原创 HDU 6223 -Infinite Fraction Path（BFS+剪枝）
【题目链接】http://acm.hdu.edu.cn/showproblem.php?pid=6223【题意】给一个长度为 nnn 的只包含 [0,9][0,9][0,9] 数字的串，位置从 000 开始，下标 iii 的下一个位置是 (i2+1)&nbsp;mod&nbsp;n(i^2+1) \ mod \ n(i2+1)&nbsp;mod&nbsp;n，问其中字符个数为 nnn 的路径...
2018-11-13 20:49:16
119
原创 51Nod 1461 - 稳定桌（枚举+线段树）
【题目描述】【思路】线段树还是写的少，不知道还有这样子的用法看了别人的题解，这道题是要枚举所有的长度，然后计算把当前长度作为最长桌腿时消耗的最小代价，取最小值就是答案. 当枚举某个长度 iii 时，要把比 iii 长的桌腿都删掉，这个可以用代价的前缀和处理. 然后看一看现在长度为 iii 的桌腿有没有超过剩下桌腿的一半，超过了直接更新答案，如果没超过那么还要删掉一定数量的长度比 iii 小...
2018-11-11 22:31:34
273
原创 51Nod 1322 - 关于树的函数（树DP）
【题目描述】【思路】看了大佬的题解才想明白的，f_zyj大佬的题解两棵树，对第一棵树暴力枚举所有边，拆掉这条边后的两个子树对应两个集合 A1,B1A1,B1A1,B1，用 dfsdfsdfs 枚举，然后在枚举出某一个 A1,A2A1,A2A1,A2 时，所有在 A1A1A1 中的节点 uuu，used[u]=trueused[u]=trueused[u]=true，现在对第二棵树枚举，df...
2018-11-08 19:52:31
199
原创 51Nod 1296 - 有限制的排列（DP）
【题目描述】【思路】做这道题首先要知道一种全排列的生成方式：如果要生成 [1,n][1,n][1,n] 的全排列，考虑递推关系，如果现在所有 [1,n−1][1,n-1][1,n−1] 的排列都是已知的，那么假设 [1,n][1,n][1,n] 中的一个排列末尾元素为 xxx ，那么只要把 [1,n−1][1,n-1][1,n−1] 中所有 &amp;gt;=x&amp;gt;=x&gt;=...
2018-11-08 11:40:18
293
原创 51Nod 1293 - 球与切换器（DP）
【题目描述】【思路】经过该切换器的球的总量是k，发现如果是该位置的值是1，那么会有(k+1)/2的球像右去，剩下的球向下去。如果该位置的值是-1，那么会有(k+1)/2的球像下去，剩下的球向右去。最后求右下角的位置球向下的数量。设 dp[i][j][0]dp[i][j][0]dp[i][j][0] 表示经过位置 (i,j)(i,j)(i,j) 并向下走的球数量，dp[i][j][1]dp[...
2018-11-08 00:25:15
122
原创 51Nod 1277 - 字符串中的最大值（KMP）
【题目描述】【思路】假设现在有一个位置 pospospos ，其前缀已经出现一次即 [0,pos−1][0,pos-1][0,pos−1] 这个前缀已经出现了一次，现在考虑一下 next[pos]next[pos]next[pos] 的意义，其实就是包含在 [0,pos−1][0,pos-1][0,pos−1] 这个前缀里面的前缀（前缀针对整个字符串而言，并非 [0,pos−1][0,po...
2018-11-07 21:45:06
204
原创 51Nod 1275 - 连续子段的差异（单调队列）
【题目描述】【思路】固定左端点 iii，向右寻找一个最远的右端点 jjj ，使得区间 a[i,j]a[i,j]a[i,j] 中的最大值减去最小值的差 &lt;=k&lt;=k<=k 同时 a[i,j+1]a[i,j+1]a[i,j+1] 中的最大值减去最小值的差 &gt;k&gt;k>k，这样一来 [i,i],[i,i+1]...[i,j][i,i...
2018-11-06 21:32:11
342
原创 51Nod 1274 - 最长递增路径（DP）
【题目描述】【思路】如果是有向图，那么可以把边按照从小到大排序，然后设 dp[i]dp[i]dp[i] 以 iii 为终点的最长距离。有 dp[u]=max{dp[u],dp[v]+1∣(u,v)∈E}dp[u]=max\{dp[u],dp[v]+1|(u,v)\in E\}dp[u]=max{dp[u],dp[v]+1∣(u,v)∈E}而在无向图中，对于无向边 (u,v)(u,v)(u,...
2018-11-06 20:30:57
228
原创 51Nod 1201 - 整数划分（DP）
【题目描述】【思路】dp[i][j]表示数字i被划分成j个互不相同的数字之和的方案数，那么dp[i][j] 表示数字i被划分成j个互不相同的数字之和的方案数，那么dp[i][j]表示数字i被划分成j个互不相同的数字之和的方案数，那么dp[i][j]=dp[i−j][j]+dp[i−1][j−1]dp[i][j]=dp[i-j][j]+dp[i-1][j-1]dp[i][j]=dp[i−j]...
2018-11-05 21:27:30
139
原创 51Nod 1259 - 整数划分 V2（五边形数定理）
【题目描述】【思路】大佬的博客记板子#include<bits/stdc++.h>#define f(x)(((x)*(3*(x)-1))>>1)#define g(x)(((x)*(3*(x)+1))>>1)using namespace std;const int mod=1e9+7;const int maxn=100005;in...
2018-11-05 20:09:29
372
原创 51Nod 1257 - 背包问题 V3（二分）
【题目描述】【思路】二分最大化平均值，设被选择的集合是 SSS 那么对于某个单位价值 xxx 我们去验证物品集合 SSS 中的单位价值能否达到 xxx 即验证下面的式子是否成立 ∑i∈Spiwi&gt;=x\sum_{i \in S} \frac{p_i}{w_i}&gt;=xi∈S∑wipi>=x 移项后，等价于验证 ∑i∈S(pi−xwi)&gt;...
2018-11-05 17:20:10
143
原创 51Nod 1225 - 余数之和（整除分块）
【题目描述】【思路】整除分块+等差数列设 p=⌊ki⌋,k&nbsp;mod&nbsp;i=k−pip =\lfloor \frac{k}{i} \rfloor , k \ mod \ i =k-pip=⌊ik⌋,k&nbsp;mod&nbsp;i=k−pi 如果有⌊ki+1⌋=p,k&nbsp;mod&nbsp;(i+1)=k−p(i+1)=k−pi−p=k&nbsp;mod&
2018-11-04 23:37:42
244
原创 51Nod 1217 - Minimum Modular（数论）
【题目描述】【思路】这个题我们可以考虑从小到大枚举m（从max(1,n-k)到max(a[i])+1），然后判断能否在删不超过k个数的情况下满足每个数模m都互不相同。对于模m的情况，a[i]≡a[j](mod m)当且仅当a[i]-a[j]是m的倍数，我们可以先预处理出a[i]-a[j]=w的个数cnt[w]，然后对于模m的情况，就只用考虑删m|a[i]-a[j]的i或j了，根据调和级数我...
2018-11-04 21:56:44
171
原创 51Nod - 1215 数组的宽度（单调栈）
【题目描述】【思路】单调栈处理左右第一处比自己小和大的位置，然后计算每个元素对答案的贡献，注意若干相同元素不能重复计算，所以在处理左边第一处大于自己的位置后，右边就要处理第一处大于等于自己的位置，这样才不会重复计算，比自己小的位置也同理#include<stack>#include<cstdio>#include<cstring>#include&...
2018-11-04 20:39:16
140
原创 51Nod 1204 - Parity（并查集）
【题目描述】【思路】并查集这题要转化一下，一转化就比较明显了。我们定义前缀和为 sum[i]sum[i]sum[i] 表示 111 到 iii 的和，那么 sum[b]−sum[a−1]=c[a]+c[a+1]+c[a+2]……c[b]sum[b]-sum[a-1]=c[a]+c[a+1]+c[a+2]……c[b]sum[b]−sum[a−1]=c[a]+c[a+1]+c[a+2]……c[...
2018-11-04 19:24:13
143
原创 洛谷P3384 - 树链剖分（树链剖分模板题）
题目链接 https://www.luogu.org/problemnew/show/P3384【描述】树链剖分模板题，记一下板子#include<bits/stdc++.h>#define node tree[id]#define lson tree[id<<1]#define rson tree[id<<1|1]using namespace...
2018-11-04 12:47:50
369
原创 51Nod 1199 - Money out of Thin Air（树链剖分）
【题目描述】【思路】树链剖分，两次dfs将重链转换成连续区间，然后用线段树维护区间和#include&lt;bits/stdc++.h&gt;#define node tree[id]#define lson tree[id&lt;&lt;1]#define rson tree[id&lt;&lt;1|1]using namespace std;typedef long lon
2018-11-03 10:03:20
107
原创 51Nod 1196 - 字符串的数量（DP）
【题目描述】【思路】做不出来，看了讨论区大佬的题解才写出来的。这道题是V1难度，还有V2,V3根本不会，先贴上V1的题解下面的所有字母编号都从 111 开始，范围 [1,n][1,n][1,n]首先，一个合法的字符串显然是由若干个合法的“链”组成的。链的定义就是：从一个字母开始连，后面每个字母编号必须大于等于前一个的2倍，这样尽可能的连接下去。所谓尽可能连接下去的意思是，链的最后一个字母...
2018-10-31 23:11:18
160
原创 51Nod 1028 - 大数乘法 V2（FFT）
【题目描述】【思路】FFT的基础应用，把一个大数从低位到高位看成一个多项式，大数想乘看成多项式想乘，多项式的自变量 xxx 表示数字 101010，乘完进位即可得到结果#include<bits/stdc++.h>using namespace std;const double PI=acos(-1.0);const int maxn=400005;struct Co...
2018-10-31 19:13:45
231
转载 快速傅里叶变换FFT（模板）
转载出处 https://blog.csdn.net/f_zyj/article/details/76037583摘自大佬的博客 FFT（最详细最通俗的入门手册）const double PI=acos(-1.0);// 复数结构体struct Complex { double x,y; // 实部和虚部 x + yi Complex(double _x=0.0, doub...
2018-10-31 17:12:29
432
原创 51Nod 1161 - Partial Sums（组合数找规律）
题目链接 http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1161【题目描述】给出一个数组A，经过一次处理，生成一个数组S，数组S中的每个值相当于数组A的累加，比如：A = {1 3 5 6} =&gt; S = {1 4 9 15}。如果对生成的数组S再进行一次累加操作，{1 4 9 15} =&gt; {1 5 1...
2018-10-23 10:27:54
173
原创 51Nod 1158 - 全是1的最大子矩阵（DP）
题目链接 http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1158【题目描述】给出1个M*N的矩阵M1，里面的元素只有0或1，找出M1的一个子矩阵M2，M2中的元素只有1，并且M2的面积是最大的。输出M2的面积。Input第1行:2个数m,n中间用空格分隔(2 &lt;= m,n &lt;= 500)第2 - N...
2018-10-22 20:55:56
183
原创 51Nod 1051 - 最大子矩阵和（DP）
题目链接 http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1051【题目描述】一个M*N的矩阵，找到此矩阵的一个子矩阵，并且这个子矩阵的元素的和是最大的，输出这个最大的值。例如：3×3的矩阵：-1 3 -12 -1 3-3 1 2和最大的子矩阵是：3 -1-1 31 2Input第1行：M和N，中间...
2018-10-22 20:29:32
133
原创 51Nod 1050 - 循环数组最大子段和（DP）
题目链接 http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1050【题目描述】N个整数组成的循环序列a[1],a[2],a[3],…,a[n]，求该序列如a[i]+a[i+1]+…+a[j]的连续的子段和的最大值（循环序列是指n个数围成一个圈，因此需要考虑a[n-1],a[n],a[1],a[2]这样的序列）。当所给的...
2018-10-22 19:52:33
119
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人