1 繁凡さん

学生身份

我要认证

大二蒟蒻ACMer一只

等级
TA的排名 1w+

第 45 届国际大学生程序设计竞赛(ICPC)亚洲网上区域赛模拟赛 部分题解

这次比赛好多原题呀…A、Easy Equation前缀和差分。首先一看数据范围是1e6就不可能O(n2)O(n^2)O(n2)做,只能O(n)O(n)O(n)。之前做过一道简化版的题,是求x+y=zx+y=zx+y=z的方案数,用的是前缀和。这里是三个,所以把那个方法拓展一下即可。#include<cstdio>#include<cstring>#include<algorithm>#include<iostream>#include&lt

2020-10-31 17:58:22

Java知识大全

待更…目录1. 数据类型2. 输入输出3. 数组4. 选择语句1. 数据类型boolean flag;byte a;short b;int c;long d;float e;double f;char g;2. 输入输出import java.util.*;import java.math.BigDecimal;import java.text.DecimalFormat;import java.text.NumberFormat;public class Main{

2020-10-30 11:06:05

luogu P2613 【模板】有理数取余(费马小定理,乘法逆元)

整理的算法模板合集: ACM模板目录题目传送门题目传送门相当于是一个高精的费马小定理求乘法逆元。虽然数据达到了101000110^{10001}1010001,但是我们可以使用快读然后一直模mod即可。然后就是直接求一下乘法逆元即可。#include<cstdio>#include<cmath>#include<algorithm>#include<iostream>#include<cstring>#include<

2020-10-30 08:45:46

luogu P1341 无序字母对(欧拉回路应用、模板)

整理的算法模板合集: ACM模板目录输出n+1个字母,使得n个字母对都在这个字符串中出现,因为是n+1个字母,所以我们可以看出来其实就是一个欧拉路径,因为字母对可以替换顺序,所以我们将每个字母对都连一个无向边,建图,求欧拉回路,这样求出来的就是n+1个字母的字符串,因为是欧拉路径,所以会经过每条边,也就是每一个字母对都会在里面出现。我们要先判断图是否连通(可以直接用并查集判断,或者看欧拉路径是否包含了n+1个点),如果不连通那么我们求出来的欧拉回路也不会包含所有的字母对。然后再判断是否有欧拉路径,

2020-10-29 19:48:01

luogu P2865 [USACO06NOV]Roadblocks G(次短路模板)

…题没读清楚,双向边害的我找了半天bug然后就是一个次短路模板题了。#include<cstdio>#include<cmath>#include<algorithm>#include<iostream>#include<cstring>#include<vector>#include<queue>using namespace std;typedef long long ll;const int N.

2020-10-29 17:29:39

0x33.数学 - 同余

目录一、模运算的一些性质二、费马小定理三、欧拉定理AcWing 202. 最幸运的数字四、拓展欧几里得算法翡蜀定理拓展欧几里得算法五、乘法逆元求乘法逆元的三种方法1.费马小定理2.扩展欧几里得3.线性递推AcWing 97. 约数之和六、线性同余方程中国剩余定理七、高次同余方程Baby step, Giant Step算法(大步小步算法)声明: 本系列博客是《算法竞赛进阶指南》+《算法竞赛入门经典》+《挑战程序设计竞赛》的学习笔记,主要是因为我三本都买了 按照《算法竞赛进阶指南》的目录顺序学习,包含书

2020-10-28 22:10:36

2020ICPC·小米 网络选拔赛第一场 全部题解

题目情况A 题:数论 + 动态规划B 题:计算几何 + 最短路C 题:模拟D 题:图论(连通块个数)E 题:略F 题:二分答案G 题:图论H 题:略I 题:搜索(BFS)/ 并查集J 题:二维前缀和 + 二维差分K 题:数学(难)A、 Intelligent Warehouse题目大意:给你一个序列,让你选出最多的数,使得选中的数之间互为倍数(aia_iai​是aja_jaj​的倍数或者aja_jaj​是aia_iai​的倍数)

2020-10-27 21:39:23

UVA1364 Knights of the Round Table(双连通分量、二分图染色)

UVA1364 Knights of the Round Table#include<cstdio>#include<cmath>#include<algorithm>#include<iostream>#include<cstring>#include<vector>using namespace std;typedef long long ll;const int N = 5007, M = 500007, IN

2020-10-25 22:36:17

2020年ACM团队新生第一次周赛题解

A、王学姐去上学啦二分法的模板题,大家先点下面的链接学习一下二分法。https://www.cnblogs.com/cs-whut/p/11212022.html这是我一年前(整整一年,2019年的10月24号hhh)在周赛打完这道题之后写的学习笔记,有点丑。https://fanfansann.blog.csdn.net/article/details/102726708#include<iostream>#include<algorithm>using namesp

2020-10-24 22:16:01

luogu P3455 [POI2007]ZAP-Queries (莫比乌斯反演 + 整除分块)

题目传送门本题中数据为5e4,我们只需要筛一次5e4就行了。双倍经验的P4450 双亲数中数据达到了1e6,我们直接筛1e6的莫比乌斯函数有点不可取,因为只有一组数据,所以我们直接筛一次min(a,b)min(a, b)min(a,b)即可。设f(n)f(n)f(n)表示规定范围内gcd(x,y)=ngcd(x,y)=ngcd(x,y)=n的数对个数F(n)F(n)F(n)表示规定范围内公约数包括 nnn 的数对个数(即 n∣gcdn|gcdn∣gcd的数对个数),也可以写成F(t)=F(t

2020-10-24 11:43:12

【学习笔记】整除分块

整除分块整除分块,就是把 nnn 除以每一个 iii 的商相同的分成一块枚举(l,r)(l,r)(l,r)区间即对于该分块区间任何一个数来说,n/r=n/ln/r = n/ln/r=n/l。移项得到r=n/n/lr = n/n/lr=n/n/l。∑i=1n⌊ni⌋\sum_{i=1}^{n}\lfloor\frac{n}{i}\rfloori=1∑n​⌊in​⌋模板代码:for(ll l = 1, r;l <= n; l = r + 1){ r = n / (n / l)

2020-10-23 22:13:32

【学习笔记】莫比乌斯反演(包含定理,两种形式的证明及入门经典模板)

一、莫比乌斯反演学习笔记,我是看这个博客入门的,讲的非常好,传送门,关键是给出了非常多的定理,好多是数论书上的权威概念。我自己证明的照片在文末,有点乱首先,莫比乌斯反演是什么?第一种形式:F(n)=∑d∣nf(d)=>f(n)=∑d∣nμ(d)F(nd)F(n)=\sum_{d|n}f(d)=>f(n)=\sum_{d|n}\mu(d)F(\frac{n}{d})F(n)=d∣n∑​f(d)=>f(n)=d∣n∑​μ(d)F(dn​)第二种形式:F(n)=∑n∣df(d)=&

2020-10-23 20:43:34

【数学知识】三种方法求 [1,n] 中所有数欧拉函数(线性筛欧拉函数优化至 O(n) )

①直接求小于或等于n,且与n互质的数个数(求[1,n]中所有数的欧拉函数时间复杂度:O(nn)O(n\sqrt{n})O(nn​))②求[1,n]之间每个数的质因数的个数(求[1,n]中所有数的欧拉函数时间复杂度:O(nlogn)O(nlogn)O(nlogn))③线性筛欧拉函数求[1,n]之间每个数的质因数的个数(求[1,n]中所有数的欧拉函数时间复杂度:O(n)O(n)O(n))第三种方法的证明三种方法求欧拉函数#include<cstdio>#include<cmath&

2020-10-23 11:02:02

luogu P3398 仓鼠找sugar(树链剖分、求树上两条路径有没有交点,爽!)

舒服,一次敲160行代码一次编译通过一次AC是真的爽!虽然这道题可以当作简单版的树链剖分板子题了hhh要求的是两条路径有没有交点,正解是LCA玄学证明,看的我有点懵,但是这道题可以用树链剖分呀,1e5的数据我们nlognnlognnlogn的树链剖分随便做。问两条路径有没有交点,实际上我们可以直接用树链剖分直接暴力跑还不会超时,真的爽!我们只需要每次暴力将两条路径权值+1,然后线段树维护一个最大值,看 tr[1].maxv 是不是等于2,如果等于2说明一定有一个点被赋值两次,所以一定是交点!(就算要.

2020-10-22 22:04:49

UVA1626 括号序列 Brackets sequence(区间DP匹配括号,输出匹配方案)

UVA1626 括号序列 Brackets sequence简单的区间DP,但是要输出方案,所以我们按照转移的方法再重新来一遍即可。输出时考虑四种情况:i>j不存在这种子串,返回0i==j子串长度为1说明是一个孤立点,所以要消耗1,返回1s=(s')或s=[s']那么返回的是f(i+1,j-1)其他情况,枚举断点#include<cstdio>#include<cmath>#include<algorithm>#include<ios

2020-10-22 21:19:20

UVA10003 切木棍 Cutting Sticks(区间DP、细节)

本题其实就是一个区间DP 的模板题,总长度为len,有n个切割点,也就是说能被切割成n+1段,所以左边界是0,有边界是n + 1,所以答案就是f[0][n + 1]。总时间复杂度为

2020-10-22 19:49:29

【动态规划、计算几何】最优三角剖分

最优三角剖分问题描述:给一个有n个顶点的凸多边形,有很多方法进行三角剖分(polygon triangulation) 。给每个三角形规定一个权函数w(i,j,k)w(i,j,k)w(i,j,k)(比如三角形的周长或者三顶点的权和或者三角形的面积等等),求让所有三角形权和最大的方案。 这个问题的关键在于状态的定义,因为如果允许随意切割,显然任意“半成品” 多边形的各个顶点可以是原多边形中随意选取的,很难简洁的定义成状态。但我们又可以发现,对于同一种切割方法,我们可以有多种切割顺序,但切割方法就已经决

2020-10-22 17:59:15

【动态规划】区间DP - 最优矩阵链乘(另附POJ1651Multiplication Puzzle)

最优矩阵链乘(动态规划)一个n∗mn*mn∗m的矩阵由 nnn 行 mmm 列共 n∗mn*mn∗m 排列而成。两个矩阵A和B可以相乘当且仅当A的列数等于B的行数。一个nm的矩阵乘mp的矩阵,运算量为nmp。矩阵乘法不满足分配律,但满足结合律。因此A∗B∗CA*B*CA∗B∗C既可以按顺序 (A∗B)∗C(A*B)*C(A∗B)∗C 也可以按 A∗(B∗C)A*(B*C)A∗(B∗C) 来进行。假设A、B、CA、B、CA、B、C 分别是 2∗3、3∗4、4∗52*3、3*4、4*52∗3、3∗4、4∗5

2020-10-22 16:26:20

学习笔记:树链剖分

树链剖分

2020-10-21 21:33:41

0x32.数学知识 - 约数

目录一、约数定义算术基本定理的推论求NNN的正约数集合 - 试除法求1~N每个数的正约数集合 - 倍数法AcWing198. 反素数二、最大公约数最大公约数与最大公倍数更相减损术luogu P1072 (NOIP2009)Hankson的趣味题三、互质与欧拉函数声明: 本系列博客是《算法竞赛进阶指南》+《算法竞赛入门经典》+《挑战程序设计竞赛》的学习笔记,主要是因为我三本都买了 按照《算法竞赛进阶指南》的目录顺序学习,包含书中的少部分重要知识点、例题解题报告及我个人的学习心得和对该算法的补充拓展,仅用

2020-10-20 22:13:04

查看更多

勋章 我的勋章
  • GitHub
    GitHub
    绑定GitHub第三方账户获取
  • 签到达人
    签到达人
    累计签到获取,不积跬步,无以至千里,继续坚持!
  • 新人勋章
    新人勋章
    用户发布第一条blink获赞超过3个即可获得
  • 阅读者勋章Lv3
    阅读者勋章Lv3
    授予在CSDN APP累计阅读博文达到30天的你,是你的坚持与努力,使你超越了昨天的自己。
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。
  • 原力探索
    原力探索
    参与《原力计划【第二季】——打卡挑战》的文章入选【每日精选】的博主将会获得此勋章。
  • 学习力
    学习力
    《原力计划【第二季】》第一期主题勋章 ,第一期活动已经结束啦,小伙伴们可以去参加第二期打卡挑战活动获取更多勋章哦。
  • 原力新人
    原力新人
    在《原力计划【第二季】》打卡挑战活动中,成功参与本活动并发布一篇原创文章的博主,即可获得此勋章。
  • 原力探索 · S
    原力探索 · S
    在《原力计划【第二季】》打卡挑战活动中,发布 12 篇原创文章参与活动的博主,即可获得此勋章。(本次活动结束后统一统计发放)
  • 1024勋章
    1024勋章
    #1024程序员节#连续参与两年活动升级勋章,当日发布原创博客即可获得