nowting的博客

转载 51nod 1489(不懂） dfs（暴搜）也可dp

题目:搜索 CodeForces1489 蜥蜴和地下室1 秒 131,072 KB 10 分 2 级题哈利喜欢玩角色扮演的电脑游戏《蜥蜴和地下室》。此时，他正在扮演一个魔术师。在最后一关，他必须和一排的弓箭手战斗。他唯一能消灭他们的办法是一个火球咒语。如果哈利用他的火球咒语攻击第i个弓箭手（他们从左到右标记），这个弓箭手会失去a点生命值。同时，这个咒语使与第i个弓箭手左右相邻的弓箭手（如...

原创 markdown语法个人的小总结

 表示缩进两个空格 表示缩进一个空格有关大括号：效果：数学式子：https://math.meta.stackexchange.com/questions/5020/mathjax-basic-tutorial-and-quick-referenceMarkDown语法进阶（三）（文字居中、图片处理、插入视频音乐、标准字体）M...

原创 树状数组与二维树状数组

树状数组：C[i]数组的理解：图一：如何计算C数组？(数组下标用二进制表示,尾部有n个0，c数组就等于n+1个相加）二进制末尾为1，则为本身，如c[1],c[11],c[101];若末尾有0，则依次将末尾的0依次变为1，并累加起来就是c数组，如c[10100]=c[10010]+c[10011]+a[10100];(即10100的中的00依次变为1，得10和11，然后加上前的101-1=100，得10010，和10011.c[1]:c[1]=c[1]c[2]:c[10]=c[1]+a[10

原创 2019华东双基（I题数位dp，）

I题-不要666链接:https://ac.nowcoder.com/acm/contest/1168/I满足以下3个条件中的一个，我们就认为这个整数与6有关。1.这个整数在10进制下某一位是6.2.这个整数在10进制下的数位和是6的倍数.3.这个数是6的整数倍。输入描述:本题为多组输入，请处理到文件结尾，每行包含两个正整数L，R。（1<=L<=R<=1e18）。...

原创 hdu 1542 扫描线

代码：#include <iostream>#include <algorithm>using namespace std;const int maxn = 300+5;double v[maxn];// 线段struct L{ double x; double y1, y2; int state; bool operator<(L oth)...

原创 扫描线

落谷 p5490这里直接讲讲代码的思路：（胡扯下）这里从左往右扫先将矩形的竖边放到line结构体中，同时将矩形的两个纵坐标放到v数组中，v排序后，v[1]存第一小y坐标值，v[2]存第二小y坐标值，（这里没有去重，应该是在modify以及pushup中不会有影响），line存的就是每个线段（与y轴平行），按x轴从小到大排列，sgt[1].len表示当前线段所在直线覆盖的矩形的实际长度，然后乘...

原创 hdu 5321 Beautiful Set（推式子+ 反演+组合）*

先挖好坑，

原创 HDU_5528_Count a * b （推式子+积性函数）*

参考一位很牛的大佬博客：https://blog.csdn.net/firstlucker/article/details/49336427https://www.cnblogs.com/edward108/p/7636856.html         分析：f(n)=n2−∑i=0n−1∑j=0n−1n∣(i∗j)=n2−∑i=1n∑j=1nn∣(i∗j)表明j中含有（n...

原创 hdu 6053 TrickGCD(莫比乌斯函数 或 ) *

link :http://acm.hdu.edu.cn/showproblem.php?pid=6053TrickGCDTime Limit: 5000/2500 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)Total Submission(s): 4951 Accepted Submission(s):...

转载 原根的定义

下面的图片来自：百度百科原根的定义：原根，是一个数学符号。设m是正整数，a是整数，若a模m的阶等于φ(m)，则称a为模m的一个原根。1. 原根的定义设m是正整数，a是整数，若a模m的阶等于φ(m)，则称a为模m的一个原根。（其中φ(m)表示m的欧拉函数）假设一个数g对于P来说是原根，那么g^i mod P的结果两两不同，且有 1<g<P, 0<i<P,...

原创 Gym - 101955K K - Let the Flames Begin【2018沈阳onsite】(约瑟夫环问题，递推，思维）

link:https://nanti.jisuanke.com/t/A2172code：#include <bits/stdc++.h>using namespace std;#define ll long long /* 有n个人编号0..n-1,从0开始数到k-1出队，f(i)表示总数为i人的编号， f(i)与f(i-1)间的编号的关系：f(i)=(f(i-1)+k...

原创 2018 焦作 onsite E - Resistors in Parallel（数学或规律+大数）

题目链接：http://codeforces.com/gym/102028/problem/EE. Resistors in Paralleltime limit per test2.0 smemory limit per test1024 MBinputstandard inputoutputstandard outputIn this physics problem, wha...

原创 背包九讲笔记

f [ i ][ v ]表示前i个物品，放入容量为v的背包中可以获得的最大价值状态转移方程：f[i][v] = max( f[i-1][v], f[i-1][v-c[i]] + w[i])优化空间复杂度：for i = 1.. N for v = V..0 f[v] = max(f[v]...

原创 2018nanjing onsite J Prime Game(计数题）

题目链接：https://nanti.jisuanke.com/t/A2147Given a sequence of nnn integers aia_iai​.Let mul(l,r)=∏i=lrai\text{mul}(l, r) = \prod_{i = l}^{r} a_imul(l,r)=∏i=lr​ai​ and fac(l,r)\text{fac}(l, r) fac(l,r) ...

原创 hdu 5573 Binary Tree(2015年ICPC上海 B题）（二进制位运算，思维规律题）*

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5573Binary TreeTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 2172 Accepted Submission(s): ...

原创 hdu 6736 Forest Program(2019CCPC秦皇岛 F题）dfs做法

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6736Forest ProgramTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)Total Submission(s): 305 Accepted Submission(...

原创 zoj 3981 Balloon Robot - - 2017秦皇岛A题（思维题）

链接Balloon RobotTime Limit: 1000 msMemory Limit: 65536 KBThe 2017 China Collegiate Programming Contest Qinhuangdao Site is coming! There will be teams participating in the contest, and the contest w...

原创 zoj 3983 Crusaders Quest（~水~）

链接Crusaders Quest is an interesting mobile game. A mysterious witch has brought great darkness to the game world, and the only hope for your kingdom is to save the Goddesses so that they can unleash ...

原创 hdu 6558 The Moon（dp+概率+记忆化)*

题目链接：hdu 6558The MoonTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)Total Submission(s): 539 Accepted Submission(s): 249Special JudgeProblem DescriptionT...

原创 hdu 6267 Master of Random(2017中国大学生程序设计竞赛-杭州站)(每个结点在可以所有组成的树上的深度之和-----找规律是个技术活）*

题目链接：hdu 6267分析：：参考博文没做出来，搜了下规律。这规律估计我得运气到顶才能发现o(╯□╰)o规律：如果n = 4；0节点的贡献是6 = 3！1节点的贡献是12 = 3！+ 3！/12节点的贡献是15 = 3！+ 3！/1 + 3！/23节点的贡献是17 = 3！+ 3！/1 + 3！/2 + 3！/3代码：#include<iostream>#...

原创 hdu 6265 Master of Phi(杭州ccpc题目）（积性函数+欧拉函数）*

题目链接：hdu 6265分析：这题和南京网络赛的K Sum有点类似，不过这题没那题复杂先将∑d∣nφ(d)∗nd\sum_{d|n}\varphi(d)*\frac{n}{d}d∣n∑​φ(d)∗dn​中的d改成质因子的形式∑l1=1q1⋯∑lm=1qm(p1l1⋯pmlm)φ(p1q1−l1⋯pmqm−lm)\sum_{l_1=1}^{q_1}\cdots\sum_{l_m=1}^{...

原创 2019 ICPC南京网络赛 E. K sum (莫比乌斯反演+杜教筛)**

题目链接：https://nanti.jisuanke.com/t/41302Define functionfn(k)=∑l1=1n∑l2=1n…∑lk=1n(gcd⁡(l1,l2,…,lk))2\displaystyle f_n(k)=\sum_{l_1=1}^n \sum_{l_2=1}^n … \sum_{l_k=1}^n (\gcd(l_1,l_2,…,l_k))^2 fn​(k)=l...

原创 2019南昌icpc网络赛C.hello 2019 & codeforce 750E.New Year and Old Subsequence(线段树+矩阵+dp思想）*

题目链接：C.hello 2019cf 750E先讲讲cf 750E,首先安利下cf这场比赛的题解http://codeforces.com/blog/entry/49412关于这题核心就在题解链接中的讨论部分，当发现类似连在一起几把锁的图案就是该部分虽然是英文的，但讲的很好（可以像我一样用划词翻译）下面理了理这题的思路最难的还是如何想到构造这样一个矩阵（没办法，自己都是看题...

原创 2019nanchang icpc网络赛E(双端队列+模拟）

题目链接：https://nanti.jisuanke.com/t/41352John is not only a magic master but also a shuffling master.Famous though he is, he likes interacting with his fans by playing a game with his fantastic shuffl...

原创 落谷 P4213 【模板】杜教筛（Sum）

题目链接 ：https://www.luogu.org/problem/P4213题目描述给定一个正整数N(N≤231−1)N(N\le2^{31}-1)N(N≤231−1)求ans1=∑i=1nφ(i)ans_1=\sum_{i=1}^n\varphi(i) ans1​=i=1∑n​φ(i)ans2=∑i=1nμ(i)ans_2=\sum_{i=1}^n \mu(i) ans2​=i=1...

原创 落谷 P3327 [SDOI2015]约数个数和 （莫比乌斯反演+分块）*

题目链接：https://www.luogu.org/problem/P3327题目描述设d(x)为x的约数个数，给定N、M，求 ∑i=1N∑j=1Md(ij)\sumN_{i=1}\sumM_{j=1}d(ij)∑i=1N​∑j=1M​d(ij)输入格式输入文件包含多组测试数据。第一行，一个整数T，表示测试数据的组数。接下来的T行，每行两个整数N、M。输出格式T行，每行一个整数，表示你...

原创 莫比乌斯反演

相关定义，性质及证明：百度百科-莫比乌斯反演计算：参考资料百度百科-莫比乌斯反演

原创 bzoj 2301 (莫比乌斯反演）

题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=23012301: [HAOI2011]Problem bTime Limit: 50 Sec Memory Limit: 256 MBSubmit: 8632 Solved: 4233[Submit][Status][Discuss]Description对于给出的n个询问...

原创 落谷 P3455 ZAP-Queries（莫比乌斯反演入门题+分块）

####题目链接：https://www.luogu.org/problem/P3455P3455 [POI2007]ZAP-Queries提交 4.14k通过 2.32k时间限制 2.00s内存限制 125.00MB题目提供者 洛谷难度省选/NOI-历史分数 100提交记录 查看题解标签POI高性能2007相关讨论进入讨论版推荐题目展开题目描述Byteas...

原创 杜教筛

先放这，主要还是得自己会推

原创 整除分块

原创 hdu 1695 GCD (莫比乌斯反演入门题）*

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1695GCDTime Limit: 6000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 19579 Accepted Submission(s): 7510P...

原创 hdu 2588 GCD(欧拉函数）+ bzoj 2818 gcd(欧拉筛）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2588GCDTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 4323 Accepted Submission(s): 2318Pro...

原创 The Preliminary Contest for ICPC Asia Nanjing 2019(数塔--扩展欧拉定理，）

题目链接：https://www.jisuanke.com/contest/3004?view=challengesB【数塔】输入a,b,m求b层aaa⋅⋅a^{a^{a^{\cdot^{\cdot}}}}aaa⋅⋅的幂塔函数mod m的值大佬博客：https://blog.csdn.net/zzkksunboy/article/details/78867686分析：主要就是利用扩展欧...

原创 The 2018 ACM-ICPC Chinese Collegiate Programming Contest

题目链接：https://www.jisuanke.com/contest/2991?view=challengesEFGIJKLM

原创 poj 1015 Jury Compromise(动态规划，并找出路径）*

题目链接：http://poj.org/problem?id=1015题面：Jury CompromiseTime Limit: 1000MS Memory Limit: 65536KTotal Submissions: 35458 Accepted: 9586 Special JudgeDescriptionIn Frobnia, a far-away country, the...

原创 摘抄

做ACM要做到僧人的淡泊，军人的纪律，诗人的想象所谓僧人的淡泊，就是不以好比而喜，不以比差而悲，不因别人贬低而怒，不因别人捧高而狂所谓军人的纪律，就是持之以恒，生活有规律，刷题有恒心，遇到困难不退缩所谓诗人的想象，就是不要低估自己的能力，不要觉得金牌遥不可及，final也只是看你有没有决心，有决心，有恒心，配合有效的学习方法和厚脸皮精神，我只能说一切皆有可能。----- 来自https:/...

原创 动态规划

这篇讲述了概念https://www.topcoder.com/community/competitive-programming/tutorials/dynamic-programming-from-novice-to-advanced/MIT的视频（但是看不了）还是这篇写得不错

原创 HDU - 1024 Max Sum Plus Plus(最大m段字段和)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1024Max Sum Plus PlusTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 44725 Accepted Submiss...

原创 hdu 6438 Buy and Resell（贪心）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6438Buy and ResellTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 3366 Accepted Submission(...