- 博客(26)
- 问答 (5)
- 收藏
- 关注
RSS订阅原创 浅谈带权并查集
本文主要从0基础开始讲解带权并查集，要求读者阅读本文前对并查集有一定的了解。 还是先以一道木板题为例吧！模板(hdu 3038)大致题意： 给出区间[a, b]，区间之和为v。输入m组数据，每输入一组，判断此组条件是否与前面冲突，最后输出与前面冲突的数据的个数。比如说先给出[1,10]的和为100,[1,3]的和为10，[7,10]的和为20，接着又说[4,6]的和为50，显然此时发...
2020-02-22 17:25:57
289
1
原创 Dynamic Programming: From novice to advanced
An important part of given problems can be solved with the help of dynamic programming (DP for short). Being able to tackle problems of this type would greatly increase your skill. I will try to help ...
2020-01-16 23:35:37
434
原创 01背包问题的朴素做法及其空间复杂度的优化做法
问题【题目描述】一个旅行者有一个最多能装 M 公斤的背包，现在有 n 件物品，它们的重量分别是W1，W2，…,Wn,它们的价值分别为C1,C2,…,Cn，求旅行者能获得最大总价值。【输入】第1行：两个整数，M(背包容量，M≤200)和N(物品数量，N≤30)；第2…N+1行：每行二个整数Wi，Ci，表示每个物品的重量和价值。【输出】仅一行，一个数，表示最大总价值。【输入样例】10...
2019-11-17 17:45:02
578
原创 谷歌浏览器(chrome)切换标签页的快捷键
Series 1(Ctrl+number)Ctrl+1：切换到第一个标签；Ctrl+2：是切换到第二个标签，依次类推……但值得注意的是：Ctrl+9不是第九个标签页，而是最后一个标签页Series 2(Ctrl+Tab/Ctrl+Shift+Tab)Ctrl+Tab：从左往右循环切换标签页Ctrl+Shift+Tab：从右往左循环切换标签页...
2019-11-14 21:54:25
6208
3
原创 基于动态规划对友好城市问题O(nlogn)做法的深入研究
Problem（附链接）题目描述有一条横贯东西的大河，河有笔直的南北两岸，岸上各有位置各不相同的N个城市。北岸的每个城市有且仅有一个友好城市在南岸，而且不同城市的友好城市不相同。每对友好城市都向政府申请在河上开辟一条直线航道连接两个城市，但是由于河上雾太大，政府决定避免任意两条航道交叉，以避免事故。编程帮助政府做出一些批准和拒绝申请的决定，使得在保证任意两条航道不相交的情况下，被批准的申请尽量...
2019-11-13 08:57:49
372
原创 浅谈常用的三个二分查找函数
今天我们来认识一下下面三个有关于二分查找的函数lower_bound(起始地址，结束地址，要查找的数值)upper_bound(起始地址，结束地址，要查找的数值)binary_search(起始地址，结束地址，要查找的数值)注意事项前两个函数既可用于升序数列，也可用于降序数列。第三个函数仅可用于升序数列。这三个函数参数中的区间都是左闭右开。1.lower_bound( )该...
2019-11-12 21:33:30
277
原创 赋初始值的2种常见函数(memset和fill)
在程序设计中经常需要对变量赋初始值，在这里我就介绍2中常见的用于赋初始值的函数。No.1 memset()函数函数原型：void *memset(void *s, int v, size_t n);它的原理是逐字节的赋值。基于上述原理，它对int类型变量赋值时，以下值不会错memset(arr,0,arr+n);memset(arr,1,arr+n);memset(arr,0x7f,...
2019-11-10 12:00:27
517
原创 矩阵快速幂模板
又是这个东西，真的挺简单的，还是来看看吧！这里以经典的不能再经典的斐波那契数列(Fibonacci sequence)作为模板吧。模板题题目描述Fibonacci数列是这样的：F[1]=1F[2]=1F[3]=2F[4]=3…F[N]=F[N-1]+F[N-2]现在给你两个整数N和M，请你求出Fibonacci数列的第N项F[N]，然后输出F[N]模M的值即可。输入格式输...
2019-11-08 21:14:43
258
原创 拓扑排序精讲
背景引入先看看一道题吧 （题目链接）与之相似的，在日常生活中，一项大的工程可以看作是由若干个子工程组成的集合，这些子工程必须在其他一些子工程完成之后才能开始，问这个总工程完成花费的最少时间。求解这类问题就需要用到我们今天要讲的拓扑排序。算法讲解其实思想很简单：准备工作：读入数据时，如果做B的前提是先做完A，那么就从A向B连一条有向边；读入完数据后，选择一个入度为0的点（因为入度为...
2019-11-06 20:13:29
176
原创 基于贪心思想对电池的寿命问题的深入研究
题目题目描述小S新买了一个掌上游戏机，这个游戏机由两节5号电池供电。为了保证能够长时间玩游戏，他买了很多5号电池，这些电池的生产商不同，质量也有差异，因而使用寿命也有所不同，有的能使用5个小时，有的可能就只能使用3个小时。显然如果他只有两个电池一个能用5小时一个能用3小时，那么他只能玩3个小时的游戏，有一个电池剩下的电量无法使用，但是如果他有更多的电池，就可以更加充分地利用它们，比如他有三个电...
2019-11-02 16:17:56
241
原创 C++头文件大全
先给个万能头文件#include<bits/stdc++.h>这是近几年才有的，但有些评测网站不认识，所以提交时可以用以下的头文件代替#include<iostream>#include<cstdio>#include<cstring>#include<string>#include<cmath>#inclu...
2019-11-02 14:29:05
1636
原创 在线评测网站集锦（涵盖国内国外各大题库和评测网站）
国内NOI 官方网站NOI 官方题库北京大学NOI在线评测大视野在线评测（省选以上难度）Universal Online Judge《算法进阶指南》练习网站-Contest HunterLibreOJFZOJCodechefLYOI Online Judge北京大学在线评测北京大学百练浙江大学在线评测电子科技大学在线评测杭州电子科技大学在线评测杭州电子科技大学在线...
2019-11-02 11:59:24
1903
原创 输入优化和输出优化模板
这两个优化的写法有好几种，我在这儿就展示外形比较美观的一种写法。（只适用于整型的输入与输出）Code（输入优化）template<typename T>void Read(T &cn){ char c;int sig=1; while(!isdigit(c=getchar())) if(c=='-') sig=-1;cn=c-48; while(isdigit(c=...
2019-11-01 21:19:40
218
原创 高精度除法（高精除以高精）模板
嗯，这个还有点儿难度（虽然不常用），其实也不难，稍微讲讲吧！在用竖式计算除法的时候，用减法模拟每次的相除，从高位到低位，每次减到不能再减为止，然后向后移一位。嗯，就这样。Code#include<bits/stdc++.h>using namespace std;int c[300];char ch1[300],ch2[300],ans[300];bool cmp(i...
2019-11-01 17:20:35
3686
1
原创 高精度除法（高精除以单精）模板
高精除以单精还是比较简单（还不用倒序存储呢），直接模拟竖式就好了。Code#include<bits/stdc++.h>using namespace std;int a[300],b,c[300],Left;string s;int main(){ cin>>s; cin>>b; int lena=s.size(); for(int i...
2019-11-01 16:52:47
726
原创 高精度乘法模板
这个相较于加法和减法要稍微复杂点（但也挺弱智的），还是那句话，回到小学，算一下竖式，模拟一下乘的过程。Code#include<bits/stdc++.h>using namespace std;int a[300],b[300],c[1000000];string s1,s2;int main(){ cin>>s1; cin>>s2; i...
2019-11-01 16:47:23
318
1
原创 高精度减法模板
这个也没什么好说的，还是回到小学，算一下竖式，模拟一下减的过程，就好了。Code#include<bits/stdc++.h>using namespace std;int a[300],b[300],c[300];string s1;string s2;int main(){ cin>>s1; int len1=s1.size(); cin>...
2019-11-01 16:40:45
184
原创 高精度加法模板
这个纯粹就是回到小学，算一下竖式，模拟计算过程，推推就好。Code#include<bits/stdc++.h>using namespace std;int a[300],b[300],c[300];string s;int main(){ cin>>s; int len1=s.size(); for(int i=1;i<=len1;i++)...
2019-11-01 16:37:14
305
原创 浅谈devc++编译运行时出现ld returned 1 exit status的原因
可以把ld returned 1 exit status前面的详细出错说出来程序是没有问题的,可能的问题最有可能是以下3个是你的程序已经在运行,关闭原来的程序就可以正常了你电脑上有杀毒(安全)软件阻止了你程序的生成,退出杀毒(安全)软件再试下。检查声明函数名与定义的是否一致，最好复制过来。多注意下细节就应该没有什么问题了。...
2019-10-31 21:28:11
4401
1
原创 基于贪心算法、动态规划对求解最大子矩阵问题的深入研究
背景及必备知识总所周知，矩阵实质就是一个二维数组。所以想要求最大子矩阵，不如先来看看如何求一位数组的最大子序列和吧！现假设有一个一维数组 arr[n]，要你找出连续的一段数组元素，使其和最大例如，一个一维数组：4 -5 6 3 7 -1 8 ，通过肉眼观察， 6 3 7 -1 8 为这个数组的连续最大和。那么有什么算法能够解决这个问题呢？我们可能看一眼就能想到的方法就是用三层循环来枚举吧...
2019-10-29 17:07:12
411
原创 基于贪心算法对整数区间问题(CEOI1997)的深入研究
题目题目描述请编程完成以下任务：1.从文件中读取闭区间的个数及它们的描述；2.找到一个含元素个数最少的集合,使得对于每一个区间,都至少有一个整数属于该集合，输出该集合的元素个数。输入首行包括区间的数目n,1≤n≤10000,接下来的n行,每行包括两个整数a,b,被一空格隔开,0≤a≤b≤10000,它们是某一个区间的开始值和结束值。输出第一行集合元素的个数,对于每一个区间都至少有一...
2019-10-28 11:20:45
282
原创 基于贪心算法与二分查找（时间复杂度为o(nlogn)）对导弹拦截问题（NOIP1999提高组）的深入研究
题目（输入输出样例请点链接）题目描述某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。输入导弹依次飞来的高度（雷达给出的高度数据是≤50000的正整数），计算这套系统最多能拦截...
2019-10-27 18:49:05
967
原创 关于main()函数中的argc和argv[]的意义
大家看看这段代码int main(int argc, char** argv){ }当我们看到上面的程序的时候 我们会发现 argc 和 *argv[] (第一眼观察就可以知道的是 argc是整型，argv是一个可以接收二维数组的二级指针)是不是想知道main函数中的参数是从哪里来的？相信大家都有一个模糊的记忆：main函数是程序的入口函数，所以程序运行时main函数调用别的函...
2019-10-27 16:50:32
369
原创 基于贪心思想对删数问题(NOI1994)的深入研究
题目题目描述键盘输入一个高精度的正整数N（不超过250位） ，去掉其中任意k个数字后剩下的数字按原左右次序将组成一个新的正整数。编程对给定的N和k，寻找一种方案使得剩下的数字组成的新数最小。输入格式n(高精度的正整数)k(需要删除的数字个数)输出格式最后剩下的最小数。输入输出样例输入 #1 &nbs...
2019-10-26 17:19:25
236
原创 基于贪心思想对均分纸牌(NOIP2002提高组第一题）问题的深度分析
挺有趣的一道题，看看就知道该用贪心。直切正题：直接从左往右扫描一遍（当然也可以从右往左），对于每一堆牌,为了使其变成平均数量，需对三种情况进行分析：1.多于平均数的：让其变成平均数，将其多余部分给右边相邻的一堆。2.等于平均数的：不变。3.少于平均数的：让其变成平均数，少的部分从右边拿...
2019-10-26 15:11:22
204
空空如也
c++语言该怎么用fopen读入数据?
2019-11-14
怎样把visual studio新建的源码存在指定的位置？
2019-11-12
visual studio2019用freopen读不了数据，这到底是怎么回事啊？
2019-11-10
TA创建的收藏夹 TA关注的收藏夹
TA关注的人