- 博客(272)
- 收藏
- 关注
RSS订阅
转载 洛谷日报 2020年3月前索引
2020 2019 2018感觉洛谷日报全是干货！！！先记下来再说2020 年洛谷日报索引3 月#260[dove]Church 编码（和 Lambda 演算）https://www.luogu.com.cn/blog/t532/church-encoding-and-lam-cal#259[Clever_Jimmy]DLX 详细讲解https://leverimmy.blog.luogu.org/dlx-xiang-xi-jiang-jie#258[ACgod]浅析尺规作图https://
2020-07-29 21:14:34
2491
1
原创 acm学习知识
1：一维数组传参 f(int a[])或f（*a）,二维数组传参 f(int a[][ size ])或 f（int (*a)[size]）二维数组传参必须加上列数注意：同样，不管是哪种声明方式，如果在函数内部对传入的数组进行了修改，该数组本身的值也会改变，有点像引用，这是因为前面提到过传入的是地址，我们是直接对地址上的元素进行修改。...
2020-04-23 21:42:05
182
原创 acm 易错警示
1：建图注意是有向图还是无向图，无向开两倍数组2：看题注意是否为多组输入，多组输入注意初始化。3：取模例如有关n*(n-1)/2%mod不能写成((n%mod)*((n-1)%mod)%mod/2; 数字2必须放在里面4：stl中.size()为unsigned如果要计算注意强制类型转换（int）...
2020-04-21 19:16:12
184
原创 Codeforces Round #665 (Div. 2) D. Maximum Distributed Tree 题解（贪心+易错）
题目链接题目大意给你一课树，要你给每一条边分权值，每条边的权值大于0，他们的乘积等于k,而且要使得n-1条边1的数量尽可能少，定义f(u,v)为u到v的边权和求max∑i=1i=n∑j=1j=nf(i,j)\max \sum_{i=1}^{i=n}\sum_{j=1}^{j=n} f(i,j)max∑i=1i=n∑j=1j=nf(i,j)k为m个质因子的乘积题目思路这显然是一个求贡献的裸题，但是里面有易错点1：sort前不要先取模2：还有要区分m可能比n-1大（太坑了代码#incl
2020-09-07 10:21:08
335
原创 Codeforces Round #667 (Div. 3) D. Decrease the Sum of Digits 题解（思维）
题目链接题目大意就是给你一个正整数n看你加多少使得数位和少于s题目思路原来这么简单，直接模拟进位即可。代码#include<set>#include<map>#include<queue>#include<stack>#include<cmath>#include<cstdio>#include<vector>#include<string>#include<cstring>
2020-09-05 10:20:58
1698
原创 CSUST 4012 我也不知道会不会防A题解(逆元)
题目链接题目大意题目思路这个题目的思路就是如果你求出a的逆元是b，那么你要求b的逆元的话，就直接是a了。所以你只要求出前n\sqrt nn左右的数。代码#include<set>#include<map>#include<queue>#include<stack>#include<cmath>#include<cstdio>#include<vector>#include<string>
2020-09-04 15:10:19
132
原创 Codeforces Round #666 (Div. 2) C. Multiples of Length题解(构造)
题目链接题目大意给你一个长为n的数组，要你进行三次操作使得整个数组变为0.操作定义为:每次选择[l,r]的区间，然后输入一个长为r-l+1的数组b[i],使得每个a[i]+=b[i]，要求b[i]是r-l+1的倍数题目思路当n=1的时候显然可以前两次操作加0，最后一次操作-a[1]否则可以第一次操作为[1,n-1]每次元素都加上(n-1)*a[i],第二次操作为第n个元素加上(n-1)a[n]，最后一次操作为每个元素都加上-na[i].至于为什么要往这方面去想，我觉得就是操作次数过于少，就应该
2020-09-03 15:42:59
135
原创 期末程序复习之串和矩阵压缩的小测试
1：利用三元组完成矩阵加法【问题描述】以三元组表存贮的稀疏矩阵A，B ,两个矩阵的行数为m,列数为n，非零元个数分别为num1 和num2。试完成程序，完成A+B。【输入形式】第一行输入稀疏矩阵A，B的行数m和列数n（假设两个矩阵行数列数相同），第二行输入稀疏矩阵A，B的非零元个数num1和num2；以下各排分别输入对应的三元组，头num1组为A中的元素，接下来num2组为B的元素，同一个矩阵的元素按照行递增排列，第一行规定为1，同一行的元素按照列递增排列，第一列规定为1。【输出形式】为相应
2020-08-20 22:22:02
407
原创 期末程序复习之拓扑排序小测试
1：拓扑排序选课【问题描述】现在你总共有 n 门课需要选，记为 0 到 n-1。在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们，如: 0,1给定课程总量，条件条数以及它们的先决条件，判断是否可能完成所有课程的学习？提示：判断拓扑序列是否有环，拓扑序列不需要输出，可以不写result数组示例 1:输入:4 41,02,03,13,2输出: true解释: 总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和
2020-08-19 16:29:09
194
原创 期末程序复习之树的小测试
1：从下至上按层遍历二叉树【问题描述】给定一颗二叉树，要求从下至上按层遍历二叉树，每层的访问顺序是从左到右，每一层单独输出一行。【输入形式】广义表表示的二叉树，结点元素类型为整型，且都大于0，例如：1( 2( 3 ( 4, 5 ) ), 6( 7, 8( 9, 10 ) ) )【输出形式】从下至上，打印每一层的结点元素值，元素间以空格隔开。每层的访问顺序是从左到右，每一层单独输出一行。【样例输入】1(2(3(4,5)),6(7,8(9,10)))，字符串内没有空格【样例输出】4 5 9
2020-08-18 14:49:37
848
原创 CSUST 4000 你真的会数据结构吗？题解（暴力+质因子分解）
题目链接题目大意题目思路感觉这个题目不是很难啊qwq，a[i]最多只有30，对应10个素因子,那么就可以考虑暴力qwq然后题目的f(n)代表了2cnt2^cnt2cnt,cnt代表d的素因子个数(显然）每次查询只要查询30次就行了，因为儿子只有最多30个不同的值代码#include<set>#include<map>#include<queue>#include<stack>#include<cmath>#include
2020-08-16 23:50:14
149
原创 CSUST 4007 你真的会图论吗？题解（容斥+思维）
题目链接题目大意题目思路emm，感觉这个题目不是特别难，不应该想的太难了。首先观察三元环的组成只有可能是全黑，全白，两黑一白，两白一黑，既然要求同一颜色的，不太好求的话，可以直接用容斥总数减去不是同一颜色的。观察一下三元环的图像你会发现颜色不同的两条边都是一个点引申出去的，而且每一个不同颜色的三元环就有两个点引申的边不一样，这样我们可以预处理每一个点与他相连的白边和黑边的个数，然后相乘然后求和，最后除以2就是所有不同的三元环的个数，然后再用总数Cn3C_n^3Cn3减去不同颜色的就行了代
2020-08-16 08:37:30
185
原创 CSUST 4005 你真的会！题解（线段树维护区间合并）
题目链接题目大意题目思路看这个修改就知道与线段树有关，但是比赛的时候看到这个式子直接就放弃了，其实感觉是一个水题，首先假设两个区间的的∑i=1i=r−l+1Si\sum_{i=1}^{i=r-l+1}S_i∑i=1i=r−l+1Si的值分别是x,y那么他们合并之后的值就是xy+x+y(自己可以思考一下)，然后你线段树维护的值一般就是答案所要的值，那么两个区间分别所维护的值为x+1,y+1，而他们合并的区间所维护的值就是xy+x+y+1,那么很显然合并的公式就是 tree[node]=tree[n
2020-08-15 15:33:33
115
原创 整除分块讲解
引入一般一个算法的引入都是为了解决一类问题，那么这个问题是什么呢?求解∑i=1i=nn/i\sum_{i=1}^{i=n}n/i∑i=1i=nn/i式子很简单，可以直接O(n)O(n)O(n)求但是如果n为1e9甚至1e14呢，这个时候就要引入整除分块的概念其实我个人认为这个算法不能算是一种高深算法，不要掌握什么其他知识就能学,就类似于贪心算法首先我们可以先写一个暴力算法(任何算法几乎都是暴力引申的）n=20; for(int i=1;i<=n;i++){ pri
2020-08-14 19:56:48
351
原创 2020牛客暑期多校训练营（第九场）Groundhog and 2-Power Representation 题解（python eval函数）
题目链接题目大意将所给字符计算成十进制数。题目思路python中a**b代表a^b次方而且python有一个eval函数，作用是计算字符串的表达式的结果，那么思路就很显然了，先修改一下字符串，然后运用一下函数就可行了代码s=input()s=s.replace('(','**(')print(eval(s))...
2020-08-13 13:54:22
104
原创 2019 ICPC Malaysia National E. Optimal Slots 题解（01背包记录路径）
题目链接题目大意给你一个大小为 t 的背包和n个物品，每个物品的价值和质量相同，求你背包最多能装的价值，并且记录装了哪些物品，如果有多组解，你要尽可能装前面的物品，即使背包中物品的编号字典序最小题目思路如果只要求最大的价值，显然就是01背包裸题。而难点是要你记录背包中物品。其实就是回溯，具体见代码实现。一定要好好了解01背包的本质代码#include<set>#include<map>#include<queue>#include<stack>
2020-08-12 18:57:40
159
原创 Codeforces Round #267 (Div. 2) C. George and Job 题解（01背包）
题目链接题目大意给你一个长度为n的数组(n<=5000)的，要你找出k个m个字串(不相交）使得这个总和最大，求其最大值题目思路看到数据范围就明白显然是一个dp,但是自己不知道写的是啥写了一个O(n3)O(n^3)O(n3)的T了，一直是又wa又T。其实这种题目很简单，就是一种模板题，你要求什么就定义什么，这样你就可以定义dp[i][j]为[1,i]中选了j的子串的最大值，然后前缀和处理一下就行了，好久没写01背包的普通版本了，一定要注意 **dp[i][j]=dp[i-1][j]**这个语
2020-08-12 15:14:57
243
原创 Codeforces Round #361 (Div. 2) D. Friends and Subsequences 题解（st表+二分 or 单调队列）
题目链接题目大意给你两个长度为n(2e5)的数组a和数组b,要你求有多少个区间区间满足下列式子即有多少个字串，使得a字串的最大值等于b字串中的最小值st表+二分首先你可以固定左端点，然后你会发现右端点变大时，a数组的最大值是非严格单调递增，而b数组的最小值是非严格单调递减的。所以就很容易想到去二分查找.枚举左端点,查找右端点。你会发现右端点可能是一段区间，然后我就不知道咋做了，其实就是两次二分就行了qwq代码#include<set>#include<map>#i
2020-08-12 09:52:32
130
原创 HDU 6852 Increasing and Decreasing 题解（构造）
题目链接题目大意要你构造一个长为n(n<=1e5)的全排列，使得其最长上升子序列和最长下降子序列的长度分别为x和y，而且要使得这个构造的全排列，字典序最小，如果不能构造则输出NO，否则输出YES，并且输出其全排列题目思路这个构造比较神奇吧，以前都没有见到过，现在学习一下，其实他的构造方法简单来说就是分段和翻转如本来是1 2 3 4 5 6 7 8 9 10的全排列 而你如果要构造一个长度为5的单调递减序列那么你就把最后5个元素翻转变成1 2 3 4 5 10 9 8 7 6 然后假如你要构
2020-08-11 18:29:12
392
4
原创 Python 学习笔记5 （函数）
1：py内置函数首先py有一个和c语言一样的内置函数abs（）使用和c语言一样还有max和min，和c语言稍微有点区别，因为他的维数可以是多个，即你可以比较多个值的最大最小值，而且可以double和int一起比较调用函数的时候，如果传入的参数数量不对，会报TypeError的错误，并且Python会明确地告诉你：abs()有且仅有1个参数，但给出了两个：>>> abs(1, 2)Traceback (most recent call last): File "<stdi
2020-08-10 21:58:22
164
原创 2019, XI Annual Programming Contest by ESCOM-IPN K. K-th Missing Digit题解（hash or 结论）
题目链接题目大意a*b=p,a,b有1e5位,p又2e5位，其中p有一位被遮住了，要你求p的那位是多少题目思路乘法的复杂度是O(n2)O(n^2)O(n2)所以我用python计算肯定超时了。。。有两种方法第一种就是枚举位数然后hash一下，这个很好理解。第二种方法就是根据一个结论。如果a*b=c那么sumdigit(a)*sumdigit(b)%9=sumdigit©%9，其中sumdigit(x)表示x的位数和，这个有点难理解，但是自己手动模拟一下乘法的操作应该就明白了，如果乘法中没有进位显
2020-08-10 20:28:58
172
原创 Python 学习笔记4(dict+set)
1：dictdict其实就是对应c语言的map看下面的格式>>> d = {'Michael': 95, 'Bob': 75, 'Tracy': 85}>>> d['Michael']95注意d=后面是大括号也可以像c语言的map一样通过数组下标赋值>>> d['Adam'] = 67>>> d['Adam']67和c语言类似，由于一个key只能对应一个value，所以，多次对一个key放入value，后面的值
2020-08-09 22:37:29
169
原创 Python 学习笔记3（条件+循环）
1：条件判断这个和c语言有点类似，看下面代码age = 20if age >= 18: print('your age is', age) print('adult')你发现了什么，if后面有个冒号，而且如果age小于18你猜结果会是怎样，如果是c语言那么肯定会输出’adult’，而py不会输出说明py的代码运行和缩进有关（不是很严谨的表述）也就是说后面那个print本质上是连在一起就像c语言上面打了一个大括号，如果你只想age>=18输出一句怎么办，直接把第二个pr
2020-08-09 21:38:56
205
原创 Python 学习笔记2（数据类型+数组）
1:python是动态语言，与之对应的是静态语言。静态语言在定义变量时必须指定变量类型，如果赋值的时候类型不匹配，就会报错而pyhton不需要指定变量类型，甚至还可以下面这样操作a = 123 # a是整数print(a)a = 'ABC' # a变为字符串print(a)2：python的a/b有点类似于c语言的(double)a/(double)b,得到的就是浮点数，而如果要达到c语言的整数就是要有两个斜杠a//b3: ord(‘a’)就是类似于c语言的(int)‘a’,chr(66)
2020-08-09 15:32:59
202
原创 Python 学习笔记1（输入+输出）
前言：由于今天在多校遇到一个题目python一行可以秒，以及高精度实属太麻烦，是时候学习一门可以不用高精度的语言了，所以就选择了简单的python.由于视频入门实属太慢了，所以选择了廖雪峰老师的python网站学习1：了解一下命令行模式和python交互模式下的不同，我还十分震惊，python居然能在黑框就能运行程序了，后面才知道那只是交互式，python交互模式的代码是输入一行，执行一行，而命令行模式下直接运行.py文件是一次性执行该文件内的所有代码。可见，Python交互模式主要是为了调试Python
2020-08-08 21:36:04
245
原创 HDU 6832 A Very Easy Graph Problem题解（最小生成树+思维）
题目链接题目思路给你一个n个点,m条无向边的图，每个点有是黑点或者白点，要你求所有黑点和所有白点的最短路的和。题目思路跑多次最短路显然会TLE，这个时候要注意他每条边的长度是2i2^i2i也就是说你跑了全部的前i条边的长度之和都比你跑第（i+1）条边的长度短，所以如果两个点能通过前i条边到达，那肯定比通过第i+1条更优，所以我们从1 到 m按顺序建最小生成树。对于白点和黑点的最短路，我们枚举每条边会被多少种白点和黑点通过，统计两侧的黑白点个数，计算贡献即可。代码#include<set&g
2020-08-07 21:59:16
206
原创 HDU 6835 Divisibility题解（思维）
题目链接题目大意判断任意b进制数y，判断下面定理是否正确：如果y%x=0,那么f(f(⋯f(y)⋯)%x=0（无限套娃）f(y)表示所有位数之和题目思路首先这种无限多的嵌套其实没必要被吓到，这个定义就是y%x=0那么f(y)%x=0,首先观察样例样例为10进制，模数是3任意一个10进制数可以表示为x=100c0+101c1+102c2......x=10^0c_0+10^1c_1+10^2c_2......x=100c0+101c1+102c2......然后让x模3，推出x（mod3
2020-08-07 20:23:18
216
2
原创 HDU 6559 The Tower 题解(计算几何)
题目链接题目大意给出一个底部圆圆心为（0，0，0），半径为r，高为h的圆锥，问起始位置为（x0，y0，z0）（x_0，y_0，z_0）（x0，y0，z0），方向为（vx,vy,vz）（v_x,v_y,v_z）（vx,vy,vz）的点撞上圆锥的时间。题目思路想了一段时间都没什么思路，其实就是很普通的一个解方程。。。假设碰撞点的坐标为(x,y,z)那么根据相似三角形x2+y2r=h−zh\frac{\sqrt{x^2+y^2}}{r}=\frac{h-z}{h}rx2+y2=hh−z
2020-08-07 15:12:53
147
原创 Codeforces Round #661 (Div. 3) E1E2. Weights Division 题解（优先队列维护贪心 二分）
题目链接题目大意有一颗有根树，每个边有边权。树的价值是根到所有叶子节点的边权和的总和即∑w(root−>leaf)\sum w(root->leaf)∑w(root−>leaf).你可以进行一次操作使得任意一条边的边权值除以2，求最少进行多少次操作使得树的价值小于等于s题目思路一个常见的套路题吧，可惜自己没想出来，就是优先队列维护贪心即可代码#include<set>#include<map>#include<queue>#includ
2020-08-06 20:46:28
191
原创 Codeforces Round #661 (Div. 3) D. Binary String To Subsequences 题解(思维)
题目链接题目大意给你一个长度为d的01串，要你把他分成若干个子序列，使得每个子序列都满足0和1交替出现，即没有相邻的0和相邻的1，要你求最少能分成多少个子序列，以及每个元素分别分给哪一个子序列题目思路比赛的时候想了好久都没想出来qwq，看了一下大佬的代码。其实这个思路谁都懂，如果现在元素是1看前面是否有0没有匹配，没有匹配则和原先那个0匹配，否则自己新成一个序列。这个元素为0也同理。这个实现就是记下没有被匹配的元素所处的子序列，然后运用队列的思想实现代码#include<set>#
2020-08-06 10:09:21
217
原创 容斥定理入门
定义在计数时，必须注意没有重复，没有遗漏。为了使重叠部分不被重复计算，人们研究出一种新的计数方法，这种方法的基本思想是：先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目排斥出去，使得计算的结果既无遗漏又无重复，这种计数的方法称为容斥原理。 （没锤子用 ）讲解最基础开始：设P1和P2是两个性质(例如“被6整除”)。我们想统计既不具有P1 也不具有P2性质的物体的个数。可以先排除掉具有P1的物体个数，然后再排除掉具有P2的物体个数，由于同时具有两种性质的物体被排
2020-08-05 21:33:43
513
原创 错排讲解
定义一个人写了n封不同的信及相应的n个不同的信封，他把这n封信都装错了信封，问都装错信封的装法有多少种？推导显然数字小可以枚举如:dp[1]=0,dp[2]=1;对于排列数较多的情况，难以采用枚举法。这时可以用递归思想推导错排数的递回关系式。当n>=3时不妨设n排在了第k位，其中k≠n，也就是 。那么考虑第n位的情况。当k排在第n位时，除了n和k以外还有n-2个数，其错排数为dp[n-2]。当k不排在第n位时，那么将第n位重新考虑成一个新的“第k位”，这时的包括k在内的剩下n-1个数的每
2020-08-05 16:33:56
197
原创 2018 AICCSA Programming Contest H. Win Strategy 题解（01背包变形）
题目链接题目大意你在[1,L]有时间玩n个游戏，每个游戏你可以选择在a[i]开始的任意时间以后玩连续的b[i]秒，你一次只能玩一个游戏，求你最多玩多少个游戏题目思路这个我最开始以为是贪心。后面发现显然不是，实话实说感觉一点都不像dp，除了数据范围有一点像，这个和普通dp不同的就是他这个背包必须要大于a[i]+b[i]-1才能进行背包。然后直接背包一下就行了。代码#include<set>#include<map>#include<queue>#inclu
2020-08-04 22:01:07
361
原创 2018 AICCSA Programming Contest C - Function 题解（杨辉三角）
题目链接题目大意dp[l][r]=dp[l+1][r]+dp[l][r−1]+pre[r]−pre[l−1],dp[i][i]=a[i]，要你求dp[1][n]dp[l][r]=dp[l+1][r]+dp[l][r-1]+pre[r]-pre[l-1],dp[i][i]=a[i]，要你求dp[1][n]dp[l][r]=dp[l+1][r]+dp[l][r−1]+pre[r]−pre[l−1],dp[i][i]=a[i]，要你求dp[1][n]题目思路如果这个题目数据范围小的话，那么显然数区间dp，
2020-08-04 19:57:21
167
原创 CSUST 2007 我爱吃烧烤 题解（状压dp）
题目链接题目大意总共 n 家烧烤店，有 m 家特殊烧烤店，从 i 到 j 号烧烤点有 mp [ i ] [ j ] 种方案，消耗一点体力值，问消耗 q 点体力值且至少经过 k 家特殊烧烤店的方案数。题目思路看到题目好吓人。。。但是要仔细观察题目所给条件，你就会发现这么小的数据不肯定是状压嘛。然后定义状态dp记录走过的特殊店，现在所在位置，还有体力值。空间复杂度可以接受的，然后在转移的时候 ,枚举下一个要到达的地点，还要注意一个关键点，我找了好久的bug，你仔细看转移方程，你会发现要把体力在最外层循
2020-07-30 22:06:17
143
原创 CSUST 2802 打扑克牌 题解（状压dp）
题目链接题目大意题目思路看到题目的数据范围就要想到状压dp，但是我一直在想这些数字位置不同模数也不同，那么该怎么去表示呢，然后我就不知道了。。其实显然可以直接定义第二维的状态是模数不就好了嘛。然后就可以转移了啊，注意可能有数字出现了多次，我们会因此漏掉一种情况： 如果某个数字 i在排列中出现了 Cnt[i] 次，那么最后的答案 Ans 应该 Ans /= (Cnt[i])!，还有状态转移要从(1<<0)开始，而不是（1<<1）这样就能确保相加的答案为（1<<n）
2020-07-30 20:58:10
157
原创 CSUST 2010 拼三角形 题解（状压dp）
题目链接题目思路首先可以直接记忆化搜索过（2800ms左右），状压dp就是先预处理所有可行状态,然后从所有合理的dp状态中选择不冲突的状态转移搜索#include<set>#include<map>#include<queue>#include<stack>#include<cmath>#include<cstdio>#include<vector>#include<string>#inc
2020-07-30 14:19:54
141
原创 HDU Tokitsukaze and Multiple 题解（贪心）
题目链接题目思路emm其实就是要明白右端点往左贪心就好了（白书上有介绍）代码#include<set>#include<map>#include<queue>#include<stack>#include<cmath>#include<cstdio>#include<vector>#include<string>#include<cstring>#include<io
2020-07-29 14:31:31
187
原创 CSUST 1008 吃零食 题解（优先队列贪心）
题目链接题目大意题目思路这个题目显然就是运用优先队列维护贪心，按di从大到小排序，如果di一样大，则w从大到小排序，但是要注意的是，如果num<p.d的时候要特判代码#include<set>#include<map>#include<queue>#include<stack>#include<cmath>#include<cstdio>#include<vector>#include<
2020-07-29 10:22:56
212
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人