- 博客(312)
- 资源 (1)
- 问答 (3)
- 收藏
- 关注
RSS订阅原创 【备战NOIP】专题复习1-动态规划-背包问题
在阅读本文之前，建议先阅读背包九讲。本文通过相关的题目来讨论一些常见的背包套路，其中包括，01背包的模板以及应用，完全背包的模板以及应用，多重背包的模板以及应用，分组背包的模板以及应用，简单的依赖背包的模板，以及二维费用背包模板，背包第K优解。最后给出了一些习题和解析。
2022-11-10 22:27:18
630
原创 CSP 2021 S2(提高组第二轮)江西自造数据的全省选手分数
声明：这是自测，非官方排名！为了能更快的评测出全省191名选手代码的相应分数，所以前面3题每题只造了10组数据，否则有些题如果造25组数据，碰到TLE的代码将会极大地影响到评测速度。测了一个小时，最后评测出的结果共有61位选手爆0，最高分是330分。部分排名如下所示：1.airport对于小数据采用随机数据，对于大数据，比如n=50000,m1=99999,m2=1,采取的造数据策略是造m1个如下规律的区间[1,199998],[2,199997],[3,199996].......
2021-10-24 22:09:58
990
原创 01背包总结
首先，需要明确dp[i][j]的含义：从前i件物品中取一些出来放在容量为j的背包里能获取的最大价值。状态转移方程是：dp[i][j]=max(dp[i-1][j],dp[i-1][j-c[i]]+w[i])这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下：“将前 i 件物品放入容量为 j 的背包中”这个问题，若只考虑第 i 件物品的策略（放或不放），那么就可以转化为一个只和前 i − 1 件物品相关的问题。如果不放第 i 件物品，那么问题就...
2021-07-22 20:13:28
146
原创 排序、DFS总结
排序 今天上午，我们了解了冒泡排序，选择排序，插入排序，桶排序，快速排序的排序原理以及各种排序算法的复杂度和稳定性。具体原理可查阅一本通。冒泡排序，选择排序，快速排序的可视化详见这里，各种算法的复杂度和稳定性如下图所示：1桶(计数)排序桶排序的原理可详见这里，AC代码如下所示：#include<bits/stdc++.h>using namespace std;int cnt[1000005];int main(){ int n,x; ci...
2021-07-20 20:47:46
419
3
原创 2021-07-19 枚举 递归 二分总结
目录前言一、枚举算法1 最大子段和2 解四元一次方程3 三角形二、递归1.1到n之和2.二分查找13.汉诺塔总结前言今天上午学习了枚举算法，下午学习了递归，二分搜索算法。接下来，让我们来一起回顾一下今天的学习内容。一、枚举算法所谓枚举算法，其实就是暴力穷举出所有可能性，然后根据题目的要求求出最大值，最小值，最大和和，最大乘积之类的结果。1 最大子段和题目描述：给定一整型数列找出连续非空子串使得该连续子串的和最大，其中，...
2021-07-19 23:27:32
251
原创 2024届信息学竞赛 模拟专题总结
模拟其实就是根据题目指定的规则进行编程，非常锻炼写代码的能力。今天首先讲到了日期相关的模拟，比如数天数，星期几的计算。这些题目主要是要特判一下闰年的2月份多了一天。一开始，叫同学练习了时光倒流这道题。题目描述：JM已知当前的日期是y年m月d日，由于种种原因，JM希望时光能够倒流，回到n天前。不过由于时光机的问题，JM需要知道n(n<=20000)天之前是具体什么日期，你能帮帮JM吗？由于n比较小，我们完全可以模拟一天天倒退来解决这道题。先对天数-1，如果天数等于0，说明回到上个
2021-07-18 21:00:50
265
原创 HUOJ 1028 Ignatius and the Princess III(完全背包计数问题)
为了字节跳动的面试，复习一波算法题目描述：输入一个n，输出n的所有组成方案，例如：n=4,有4 = 4;4 = 3 + 1;4 = 2 + 2;4 = 2 + 1 + 1;4 = 1 + 1 + 1 + 1;5种方案。看到网上的很多答案使用母函数之类的。其实这个问题可以用背包的思想解决。可以理解为有n个物品，第i个物品的容量和价值都为i，而且每个物品可以取任意次。求...
2019-09-19 13:38:12
638
1
原创 【字节跳动】2020校园招聘研发岗位第四次在线笔试AC代码
都是2019-9-15 16:00-18:00笔试的兄die啊。第一题，一开始自己手写二分写挂了，菜的抠脚，后来调库才过的，题目备注说要O(n^2)的复杂度，但是我是用O(N^2*log(n))过得，logN其实可以看成是一个常数23333.#include<bits/stdc++.h>#define LL long longusing namespace std;in...
2019-09-15 18:11:41
510
原创 圆周率里包含了所有的银行卡密码
刷知乎的时候看到了这样一个提问《圆周率里是否包含所有可能的银行卡密码？》这个问题看上去还挺有趣的，等价于圆周率里是否完整的包含000000-999999。从数学角度上去证明貌似挺难的，根本不知道从何下手。还好现在是互联网时代，有计算机这样强大的工具。我们如果枚举出所有的可能性，就可以直接证明了。π是无限不循环小数，但是我们如果取有限位出来，而这有限位又包含了000000-999999，那就可以证明...
2018-06-09 16:27:16
2024
1
原创 HDU 2222(AC自动机模板)
AC自动机这个算法网上有很多资料，这里就不多赘述了。当从一个字符串中查找另一个字符串，我们有快速的算法KMP。现在的问题是要从一个字符串中查找很多字符串，或者要从多个字符串里分别查找很多字符串。AC自动机就是解决这个问题的。HDU2222的题意就是要从一个字符串中查找很多字符串，很裸的模板题。不过测试数据相当的水，有很多人错误的程序都AC掉了。我们把一个字符串中查找很多字符串中的一个字符串成为文本...
2018-06-08 19:33:21
483
原创 Ubuntu 16.04 gogs环境搭建
1.前言我这里用的是ubuntu14.04，因为OJ系统用的PHP框架依赖的是PHP5，如果是Ubuntu16.04，由于系统默认安装PHP7，会导致OJ系统不能正常运行。接下来，先部署WEB环境，这里是apache2+php5+mysql。接着部署一个叫gogs的网站，它的功能与github类似，这样，我们就可以建立起一个私人仓库维护更新项目了。最后再安装一些OJ的必要依赖。2.LAMP环境搭建...
2018-05-31 21:13:42
2753
原创 程序设计竞赛常用结构C++模板
1.前言在平时刷题中，有一些结构是经常使用的，比如输入函数，输出函数，还有循环结构，以及一些常用的变量和结构。而利用C++中的宏定义#define，类型重命名typedef，宏常量const，以及重载等等这些特性，可以事先写好常用的结构，然后就可以快速地写出符合自己习惯的代码。因为程序设计比赛的时候往往时间是有限的，所以要想方设法地节约写代码的时间，这不失为一种方法。比赛跟工程还是不一样的，比赛是...
2018-05-14 17:03:05
1711
原创 对《TensorFlow机器学习项目实战》例1-对人工数据集的K均值聚类源代码的理解
1.闲扯由于自己比较喜欢学习算法方面的知识，这得益于本科阶段搞了很多年的ACM，现在是研究生阶段，自然就去学习一些机器学习和深度学习的知识。前段时间从一些渠道知道有TensorFlow这个深度学习框架的存在，就去其官网看了一眼，发现根本看不懂。所以，我按照我学习计算机这些技术的一贯思路（就是去买该技术的实战书籍），就购买了两本关于tensorflow的书籍，一本是姚鹏鹏翻译的《TensorFlow...
2018-05-10 23:43:16
394
原创 高斯消元法
根据数值分析的高斯消元算法，可写出C++的实现代码，如下所示：#includeusing namespace std;const int maxn=105;double a[maxn][maxn],m[maxn][maxn],b[maxn],x[maxn],det=1.0;int n;void input_data(){ freopen("data.txt","r",stdin)
2017-10-25 20:41:20
462
原创 猜数字小游戏
最近，佳颖同学给我玩了一个小游戏，一个猜数字的小游戏。就是，先随机产生4个0-9之间不同的数字，然后玩家去猜，对于玩家每次猜的数字，系统会提示玩家XA和YB，其中，XA代表有X个数字和位置都猜对了，YB代表有Y个数字猜对了但位置不对。玩家根据系统的提示思考下一步要猜的数字，然后系统会接着给出提示。直到玩家猜出数字为止！然后，我就写了一个这个游戏的页面。挂在自己的阿里云服务器上，所以没有域名哈。
2017-10-15 15:23:36
645
原创 HDOJ 1735 字数统计
原题链接：http://acm.hdu.edu.cn/showproblem.php?pid=1735这应该属于一道模拟题，稍微思考下，应该不难想出：先统计出所有的段落的数据，然后再合并，先考虑如果统计出所有段落，很显然，只要每行前两列是0，那么，这一行就可以认为是新的段落，然后我们需要统计出每个段落内有多少0，对于第i个段落，这个数据放在b[i]里，以及段落结束到行末有多少个0，这个
2017-08-27 14:14:33
369
1
原创 简单谈谈实现递归暴力枚举
简单谈一谈如何用递归实现暴力枚举。 下面先看到一个例子。 袋子里有2红3绿5黄球，随机从中摸出8个，打印显示所有组合。 暴力枚举，其实就是实现一颗搜索树。 那很显然这颗搜索树的层数是8层，因为只要摸8个就行了。每个节点拓展出去的儿子节点很显然是10个，因为每次都有10种选择。 那很显然。8层是递归出口。10个是每层要枚举的分支。所以可以写出如下代码。char s[]="gggrryyyyy
2017-03-21 01:08:18
4088
4
原创 计蒜客2016比赛
A. 青云的服务器密钥算法：分析规律1)求出出现过字符的最小次数。2)如果只出现过这一种字符，很显然，答案是n*(n-1)/2;3)如果出现过得字符不止一种，那么总是可以找到一种排，使得最小值为n-1例如 只出现过a,b各3次。可以先放置a，然后放置其他字符，最后放置其余的a，即abbbaa。对于一般的情况，设最小次数为m，不妨假设这个字符为a。先放置一个a，然后放置其他字
2016-06-05 13:03:20
1391
原创 L2-006. 树的遍历(利用后序中序还原二叉树)
题目链接：https://www.patest.cn/contests/gplt/L2-006思路分析：后序可以知道树根，然后在中序中找出树根，又可以确定左右子树，然后递归地对左右子树进行分解，即可还原出二叉树。最后把建好的树BFS一遍就可以写出层次遍历了。AC代码如下：#include#include#include#include#includeusing namespa
2016-05-16 12:28:44
2019
原创 L1-006. 连续因子(枚举因子)
题目链接：https://www.patest.cn/contests/gplt/L1-006思路分析：首先可以想到以O(sqrt(n))的复杂度求出所有因子。然后排序，这样问题就转化为求一个数组的最长连续子数组了。一开始想到的是用简单的DP，定义DP[i]为以i结尾的最长连续子数组的长度。则动态规划转移方程为if a[i]==a[i-1]+1 dp[i]=dp[i-1]+1;el
2016-05-16 10:58:33
7062
2
原创 L3-2. 堆栈(线段树单点更新)
题目链接：https://www.patest.cn/contests/gplt/L3-2思路分析：本题可以用一句话描述，就是求堆栈的中位数。堆栈是可以用数组模拟实现，可以用一个栈顶和栈底指针来实现数组模拟堆栈，分别用top和bottom。初始时，top=0,bottom=0，出栈的时候bottom++，进栈的时候top++。可以发现，栈中的所有元素恰好对应到数组里一段下标连续的子数组中。那么
2016-05-15 08:46:10
736
原创 华东交通大学2015年ACM“双基”程序设计竞赛
题目地址：http://acm.hdu.edu.cn/diy/contest_show.php?cid=284911001把HDU 4082 稍微改一下就过了/*数相似三角形个数用map记录角度注意：1、去除重点2、排除共线的情况3、精度问题。WA了8次了*/#include#include#include#include#includeusing na
2015-11-28 17:34:44
1105
原创 JXNU 2015-11
1001由于 G 为 a,b 的最大公约数,那么 G 肯定是 a 的约数。由于 L 为 a,b 的最小公倍数,那么 L 肯定是 a 的倍数,也就是说 a 是 L 的约数。既然 G 是 a 的约数,a 是 L 的约数,那么,G 必然是 L 的约数。如果 L 不能被 G 整除,那么必然不存在满足条件的 a,b如果 L 能被 G 整除,那么由于 G故只要判断 L 是否能被 G 整除即可。
2015-11-21 21:06:41
825
原创 JXNU-2015-10-月赛
1001 组合数取模，DP ，由组合数递推公式C(n,m)=C(n-1,m)+C(n-1,m) 可设dp[i][j]为：i个数里取j个数的方案数，递推公式为：dp[i][j]=(dp[i-1][j-1]+dp[i-1][j])%mod预处理储所有情况，然后对于每一个询问直接输出就好了算法复杂度o(n*n)1002 线段树成段更新 模板题了算法复杂度o(n*log(n))
2015-10-31 17:40:09
638
1
原创 2015 ACMICPC Asia Regional Shanghai Online
1008 即 HDU 5475 An easy problem 题意：给Q个操作和M。 操作有乘有除，输出每次操作后对M取模的结果。 思路：如果只有乘法，那问题就简单了，只要把所有数边乘边对M取模即可，那坑的是有除法呀。不能保存上一步的结果直接做除法。因为模过之后就把原来的数变小了。举个例子，比如有数据： 1 3 5 1 5 1 5 2 1 那每一步保存的是取模
2015-09-26 20:54:38
913
原创 欢迎使用CSDN-markdown编辑器
1008 即 HDU 5475 An easy problem 题意：给Q个操作和M。 操作有乘有除，输出每次操作后对M取模的结果。 思路：如果只有乘法，那问题就简单了，只要把所有数边乘边对M取模即可，那坑的是有除法呀。不能保存上一步的结果直接做除法。因为模过之后就把原来的数变小了。举个例子，比如有数据： 1 3 5 1 5 1 5 2 1 那每一步保存的是取模后的结果就错了。
2015-09-26 20:53:04
361
原创 HDU 2412
HDU 1520的升级版而已~#include#include#include#includeusing namespace std;const int maxn=205,inf=1<<30;struct node{ int s,f; node(int s=0,int f=0):s(s),f(f){}}dp[maxn][2];int w[maxn],in[ma
2015-09-23 19:23:39
529
原创 HDU 1561
跟HDU 1011差不多，也是水啊。#include#include#includeusing namespace std;const int maxn=205;int dp[maxn][maxn];int c[maxn],w[maxn];int n,m;vectorG[maxn];void dfs(int u,int fa){ int cost=1; fo
2015-09-23 14:09:15
411
原创 HDU 1520
跟HDU 1054差不多。水#include#include#includeusing namespace std;const int maxn=6005,inf=1<<30;int dp[maxn][2];int w[maxn],in[maxn];int n,m;vectorG[maxn];void dfs(int u,int fa){ dp[u][1]=w[u
2015-09-23 13:49:10
469
原创 HDU 1054 Strategic Game（简单树形DP）
题目太简单，懒得写解释了，直接存一份代码#include#include#includeusing namespace std;const int maxn=1505,inf=1<<30;int dp[maxn][2];int n,m;vectorG[maxn];void dfs(int u,int fa){ dp[u][1]=1; dp[u][0]=0;
2015-09-23 13:30:10
350
原创 HDU 1011 Starship Troopers(树形DP入门题)
初学者，应该看题解也是懵懵懂懂的吧。这题网上题解很多，多找几篇总会找到合适的。#include#include#includeusing namespace std;const int maxn=105;int dp[maxn][maxn];int c[maxn],w[maxn];int n,m;vectorG[maxn];void dfs(int u,int fa){
2015-09-23 12:06:04
577
原创 2015 ACM/ICPC Asia Regional Shenyang Online
1012 Largest Point 即 HDU 5461 Largest Point给定n个数 t1,t2,...tn给定a,b;求a*ti*ti+b*tj的最大值。拿到这个题我就知道是个傻逼题，我了大去，然而，我一开始傻逼了，想对a,b是否大于0分类讨论。妈蛋，分类讨论了快一个小时，越讨论，感觉越复杂。就放弃了这种想法，开始想新的算法。后来，想到了正确做法。令A[i]=
2015-09-19 23:41:12
680
原创 BestCoder Round #56 (div.2)
HDU 5463 Clarke and minecraft水题。先统计出每种材料的总数，然后每64个贪心地放。放完36个格子即用掉一个背包#include#include#include#include#include#include#include#include#include#include#include#include#include#inclu
2015-09-19 23:31:16
522
原创 每日趣味算法(2015年9月18日)
题目来自：HDU 3848 CC On The Tree(树上叶子结点最近点对)题意：给定一棵树，可以知道，任意两个叶子之间都有一个距离，求距离的最小值，也就是说求隔得最近的两个叶子的最短距离是多少。如果要求两个叶子节点之间距离的最大值，事实上这就是“树的直径”的定义。可以进行两次BFS即可。复杂度O(n)。对于本题，对图进行分析, 可知对于任意两个叶子节点, 它们的最短路径必有共
2015-09-18 23:40:51
462
原创 凸包+多边形重心模板
本模板通过了HDU 3685凸包模板是正确的，多边形求重心也是正确的，把两块板拼在一起莫名其妙地错了，唉最后还是调出了，发现有一个函数返回类型本来应该是double，我把它写成int型了，WA了二十多发，醉了醉了。。。#include#include#include#include#include#include#include#include#include#i
2015-09-18 22:26:38
585
原创 2015 ACMICPC Asia Regional Changchun Online
1002 Ponds 即HDU 5438 Ponds心好累，比赛时这道题思路对了，一下子加个特判，一下子加个变量，搞得好乱，比赛时没能AC。。。这题不难的。题目意思：给出一个无向图，删掉一些只连了一条边出去的或者没连边出去的顶点。删完之后再继续对删完后的图删点，这是一个递归的过程。思路：删点的过程跟拓扑排序的过程极其相似，只不过这里是无向图。所以我们可以用类似拓扑排序的做法删点
2015-09-13 16:51:22
655
原创 HDU 1729 Stone Game（SG函数变形）
网上很多题解，但是我找了许多才看懂。现在总结一下。大意是：你有一些盒子，这些盒子有一个体积si，然后你和另一个人往里面放石子，盒子里面本来有一些石子，你和另外一个人轮流放的时候放的最多不能超过里面的石子的平方（比如里面原来有3个，那么你可以放的石子数量是1-9）当然了石子总数量不能超过其体积，最后不能放石子的输。很容易看出是“组合游戏和”，因此只需要求出每个瓶子的sg函数值，然后求Ni
2015-09-08 09:19:45
482
原创 HDU 1524 A Chess Game (SG函数模板题)
题意:在一个有向无环图上有n个顶点,每一个顶点都只有一个棋子,有两个人,每次根据这个图只能将任意一颗棋子移动一步,如果到某一步玩家不能移动时,那么这个人就输.分析:本题是最典型的有向无环图的博弈,利用dfs把所有顶点的SG值都计算出来,然后对每个棋子的SG值进行异或运算,如果为0就是先手必败,否则就是先手必胜.如果某个人移动到出度为0的顶点,那么他必败,
2015-09-08 01:37:24
537
原创 HDU 1517 A Multiplication Game （博弈论入门题）
先引入必胜点和必败点两个概念：必败点(P点) :前一个选手(Previous player)将取胜的位置称为必败点。必胜点(N点) :下一个选手(Next player)将取胜的位置称为必胜点。对于这两个概念的描述，我开始的时候也搞不懂。其实可以从字面理解，简单说来，就是当你走到某一点的时候，如果你无论怎么走也不能赢对方，此时你必败，这个点就叫做必败点。算
2015-09-08 01:22:06
445
TA创建的收藏夹 TA关注的收藏夹
TA关注的人