3 SingleK

尚未进行身份认证

暂无相关简介

等级
TA的排名 1w+

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

欧拉函数

欧拉函数定义欧拉函数是小于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

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

51Nod 1484 - 猜数游戏(离散化)

【思路】把输入的每一个区间都下放到树的最后一层上,把树的最后一层看成一个序列,问题就转换成了求若干区间的交集和并集,交集比较好求,维护左右断点值即可。求并集需要将区间端点离散化后再处理,参考了大佬的代码,比较诡异,不是很懂正确性。还要注意的是,离散化完以后是一个点,对应原来的序列可能是一个区间,也可能是一个点,需要特殊判断。#include<bits/stdc++.h>usin...

2019-03-19 17:21:05

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

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, & \text {$n$是fib数} \\ F(n-m)+...

2019-03-05 17:47:56

最小表示法(模板)

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<n && j<n && k<n) {t=s[(i+k)%n]-s[(j+k)%n];

2019-03-01 21:25:04

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

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

圆相关计算(模板)

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

二维几何基础(模板)

#include<bits/stdc++.h>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

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=p1a1​​p2a2​​...pnan​​,则对于一个数 ggg,ggg 是模 ppp 原根的充要条件是 gp−1pi≠1 (mod p...

2019-01-20 22:01:58

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

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

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

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

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) mod n(i^2+1) \ mod \ n(i2+1) mod n,问其中字符个数为 nnn 的路径...

2018-11-13 20:49:16

51Nod 1461 - 稳定桌(枚举+线段树)

【题目描述】【思路】线段树还是写的少,不知道还有这样子的用法看了别人的题解,这道题是要枚举所有的长度,然后计算把当前长度作为最长桌腿时消耗的最小代价,取最小值就是答案. 当枚举某个长度 iii 时,要把比 iii 长的桌腿都删掉,这个可以用代价的前缀和处理. 然后看一看现在长度为 iii 的桌腿有没有超过剩下桌腿的一半,超过了直接更新答案,如果没超过那么还要删掉一定数量的长度比 iii 小...

2018-11-11 22:31:34

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

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] 中所有 >=x>=x>=...

2018-11-08 11:40:18

查看更多

勋章 我的勋章
  • 勤写标兵Lv1
    勤写标兵Lv1
    授予每个自然周发布1篇到3篇原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。