• 等级
  • 8255 访问
  • 163 原创
  • 0 转发
  • 37637 排名
  • 17 评论
  • 2 获赞

[SDOI2015]约数个数和 (莫比乌斯反演)

https://www.lydsy.com/JudgeOnline/problem.php?id=3994题意:设d(x)为x的约数个数,给定N、M,求Σi=1nΣj=1md(ij){\Sigma_{i=1}^n\Sigma_{j=1}^md(ij)}Σi=1n​Σj=1m​d(ij)思路:首先我们先了解一个公式:d(ij)=Σx∣iΣy∣j[gcd(x,y)==1]d(ij)=\S...

2019-02-19 10:51:00

线性筛莫比乌斯函数(模板)

boolvis[Maxn];intmu[Maxn],prim[Maxn];voidMoblus(){mu[1]=1;inttot=0;for(inti=2;i<=Maxn;i++){if(!vis[i]){prim[tot++]=i;mu[...

2019-02-18 11:41:57

CCPC-Wannafly Winter Camp Day4 (div2)(dp)

题目描述wlswls有一个整数nn,他想请你算一下有多少1…n1…n的排列(permutation)满足:对于所有的i(2\lei\len)i(2≤i≤n),若ii为奇数,则a[i-1]<a[i]a[i−1]<a[i],否则a[i-1]>a[i]a[i−1]>a[i]。请输出答案mod1e9+7。输入描述一行一个整数nn。1\len...

2019-01-25 23:48:24

CF:Tree with Maximum Cost

http://codeforces.com/contest/1092/problem/F题目:有一棵树,树的每个节点都有其权值问一个树上以某个点为树的根节点,其他点到根节点的距离乘上权值最大是多少思路:可以运用树状dp解决:假设suma[x]代表x的子树的权值大小,dp[x]代表x的子树到x的距离乘上权值的大小,那么x的父节点y的suma[y]就为suma[x]+a[y],而d...

2019-01-06 19:49:05

CF:New Year and the Sphere Transmission

http://codeforces.com/contest/1091/problem/C分析:我们以n=16分析,发现:1,3,5,7,9,11,13,15的值相同:都为(1+2+3+4+5+6+7+8+9+10+11+12+13+14+15+16)2,6,10,14的值相同,都为(1+3+5+7+9+11+13+15)4,12的值相同,都为(1+5+9+13)8的值,都为(1+9)...

2019-01-01 17:49:07

hihor学习日记: hiho一下 第九十四周

http://hihocoder.com/contest/hiho94/problem/1提示:约瑟夫问题小Hi:这个问题其实还蛮有名的,它被称为约瑟夫的问题。最直观的解法是用循环链表模拟报数、淘汰的过程,复杂度是O(NM)。今天我们来学习两种更高效的算法,一种是递推,另一种也是递推。第一种递推的公式为:令f[n]表示当有n个候选人时,最后当选者的编号。f[1]=0f[n]=...

2019-01-01 15:52:35

hohor学习日记: hiho一下 第九十三周(欧拉筛)

http://hihocoder.com/contest/hiho93/problem/1存一下欧拉筛模板#include<bits/stdc++.h>usingnamespacestd;#defineLLlonglongconstintMod=1e9+7;constintmaxn=1e6+5;constdoubleeps=0...

2018-12-30 13:39:58

CF:Polygon for the Angle

http://codeforces.com/contest/1096/problem/C因为在一个正n边形中选取3个点可以把这个n边形化成i边形,(3(3(3≤\leq≤iii≤\leq≤(n−2))(n-2))(n−2)),已n=5,i=2可以推出一个公式由此可以得出n边形可以得到的几个角度,因为最小的角度是1,所以最大的边是360,这样递推一下就可以得到全部结果AC代码:...

2018-12-29 15:30:09

hihor学习日记:hiho一下 第九十二周

http://hihocoder.com/contest/hiho92/problem/1小Hi:这种质数算法是基于费马小定理的一个扩展,首先我们要知道什么是费马小定理:费马小定理:对于质数p和任意整数a,有a^p≡a(modp)(同余)。反之,若满足a^p≡a(modp),p也有很大概率为质数。将两边同时约去一个a,则有a^(p-1)≡1(modp)也即是说:假设我们要...

2018-12-28 18:13:11

hihor学习日记:hiho一下 第六十二周

http://hihocoder.com/contest/hiho62/problem/1题意分析在浏览网页的时候,缓存技术能够迅速地显示页面。这里我们对浏览器的缓存技术进行简化:我们认为浏览器的缓存大小为M,表示缓存可以存储M个页面。当用户访问URL时,浏览器会先到缓存中查询是否有该页面的记录,如果有则直接从缓存中提取数据;否则,会发送网络请求,从Internet获取该页面,并将该页面放入...

2018-12-26 19:03:18

hihor学习日记:hiho一下 第六十一周

http://hihocoder.com/contest/hiho61/problem/1题意分析给定一个字符串s,以及对该字符串s的m个操作。字符串s包含n个字符,下标为1…n。字符由’A’到’Z’构成,字符增加1表示该字符变为后续字符,比如’A’增加1是’B’,‘C’增加1是’D’。需要注意的是’Z’增加1是’A’。m个操作包含以下四种类型:将字符串第i位到第j位设定为C。比如...

2018-12-26 18:11:23

hihor学习日记:hiho一下 第六十周

http://www.hihocoder.com/contest/hiho60/problem/1题意分析给定只包含字母的两个字符串A,B,求A,B两个字符串的最长公共子序列,要求构成子序列的子串长度都必须大于等于3。比如"abcdefghijklmn"和"ababceghjklmn",其最长满足题意要求的子序列为"abcjklmn",其由公共子串

2018-12-25 20:14:05

hihor日记:hiho一下 第五十九周

http://hihocoder.com/contest/hiho59/problem/1题意分析给定一个单线程程序运行的记录,包含有每个函数启动和结束的时间。判定该份记录是否错误,主要的错误包含:记录中的时间不是严格递增的一个函数的结束时间比启动时间更早记录中一个函数有不对应的启动操作START或结束操作END,比如出现了START却没有对应的END,或出现了END却没有出现START...

2018-12-24 17:54:23

hohor学习日记:hiho一下 第五十八周

http://hihocoder.com/contest/hiho58/problem/1题意分析给定字符串S,判定S是否存在子串S’满足"aa…abb…bcc…c"的形式。其中abc为连续的三个字母,且a,b,c的数量相同。原题目中数量相等的连续n(n>3)个字母也是可行的,而实际上当n>3时一定包含有n=3的情况。比如"abcd"就包含有"abc"和"bcd"两个合法子串。...

2018-12-24 16:34:19

hihor学习日记:hiho一下 第五十七周(高斯消元)

http://hihocoder.com/contest/hiho57/problem/1高斯消元的变种,因为图很小所以而且每一个小格子都得为1,那么就把图中对某个小格子有作用的点标记起来,而他们的共同作用次数为奇数的话,小格子的状态变化,反之不变,注意这里在处理矩阵是,对于第i列的数字如果原本就为0的话,就不用处理,否则会错误AC代码:#include<bits/stdc+...

2018-12-23 17:26:19

hihor学习日记:hiho一下 第五十六周(高斯消元)

http://hihocoder.com/contest/hiho56/problem/1高斯消元就是用多元一次方程求解小Ho:<吧唧><吧唧><吧唧>小Hi:小Ho,你还吃呢。想好了么?小Ho:肿抢着呢(正想着呢)…<吞咽>…我记得这个问题上课有提到过,应该是一元一次方程组吧。我们把每一件商品的价格看作是x[1]…x[n],第i个组合中第...

2018-12-22 17:36:58

hihor学习日记:hiho一下 第五十五周 (点的双连通分量)

http://hihocoder.com/contest/hiho55/problem/1与边的双联通分量类似,这个是求的割点伪代码:voiddfs(intu){ //记录dfs遍历次序 staticintcounter=0; //记录节点u的子树数 intchildren=0; ArcNode*p=graph[u].firstArc; ...

2018-12-22 14:58:12

hihor 学习日记:hihor一下 第五十四周(缩点+dfs)

http://hihocoder.com/contest/hiho54/problem/1这次是强连通分量因为强连通分量是一个回路,所以一张图的一个强连通分量可以看成一个点,伪代码:AC代码:#include<bits/stdc++.h>usingnamespacestd;#defineLLlonglongconstintMod=1e9+7...

2018-12-21 22:07:18

hihor 学习日记:hiho一下 第五十三周(边的双连通分量)

http://hihocoder.com/contest/hiho53/problem/1求出边的双联通分量与求割点与割边类似,求边的双联通分量找的是桥,有m桥,那么就有m+1的分组。而分组有点类似割边,如果一个分组中存在割边那么这个分组就不是分组,所以这张图的割边就是分组的边界,不包括在分组中,而low[u]==cur[u]正是割边所在的点,这是利用栈和DFS,把u后面入栈的点全...

2018-12-20 15:12:58

hihor 学习日记:hiho一下 第五十二周 (割边与割点)

http://hihocoder.com/contest/hiho52/problem/1题意:这道题就是求割边与割点,割边与割点思路:大致就是用DFS树来得到low,与dfn比较来判断当前点的子树上的点是否与当前点的父点相连,如果不联,那么去掉当前点,子树与原来的树不再连通,这就是割点。而割边相同,如果当前点的子树上的点不与当前点以及当前点的父点相连,那么当前点与子树相连的边就...

2018-12-19 19:34:58

henu_jizhideqingwa

关注
奖章
  • 持之以恒