慧编慧想-CSDN博客

原创线段树

@[TOC]线段树线段树点滴如何表示一个区间方法一定义一个结构类型：struct{ int Left , Right; }参见《算法教程》方法二节点编号与区间同步，参见《挑战》query( a, b ,k, L, R){ query(a, b, 2*k+1, L ,(L+r)/2); query(a, b, 2*k+2, (L+R)/2, R);}...

2019-06-17 07:25:33 154 2

转载摆渡车

我看到了的最好的解题报告https://www.luogu.org/blog/Sooke/solution-p5017

2019-05-20 15:39:32 248

原创最大乘积

https://www.luogu.org/problemnew/show/P1018#include <bits/stdc++.h>using namespace std;string str;long long f[7][41];long long g(int start, int end){ long long s=0; int t=1;...

2019-05-08 16:35:07 104

原创批量生成in数据文件

生成in 数据要取得[a,b)的随机整数，使用(rand() % (b-a))+ a;　　要取得[a,b]的随机整数，使用(rand() % (b-a+1))+ a;　　要取得(a,b]的随机整数，使用(rand() % (b-a))+ a + 1;　　通用公式:a + rand() % n；其中的a是起始值，n是整数的范围。　　要取得a到b之间的随机整数，另一种...

2019-02-27 19:55:50 633

原创典型算法算法以及应用

目录一、评估你的复杂度二、深度优先搜索必须弄清楚的递归思想：简单的深度搜索框架深度搜索的优化：迭代加深(ID DFS)深度搜索的优化： IDA**重叠子问题（记忆化搜索）三、宽度优先搜索宽度优先搜索框架：分支定界：A*四、二分查找查找有序数列中的某个值二分查找算法分析STL中的二分法查找：二分答案（不只是查找值）一、评估你的...

2019-02-27 10:07:16 6180

原创二分查找

目录顺序查找二分查找（查找有序数列中的某个值）二分答案（不只是查找值）二分查找（查找有序数列中的某个值）设算法的输入实例中有序的关键字序列为(05，13，19，21，37，56，64，75，80，88，92) 1 2 3 4 5 6 7 8 9 10 12 顺序查找：如果按顺序查找，分析一下查...

2018-12-09 09:22:05 704

转载分支界定法

分支界定法是求解整数线性规划最优解的经典方法。摘自：https://www.cnblogs.com/sage-blog/p/3917836.html定义：　　对有约束条件的最优化问题（其可行解为有限数）的所有可行解空间恰当地进行系统搜索，这就是分支与界定的内容。通常把全部解空间反复地分割为越来越小的子集，称为分枝；并对每个子集内的解集计算一个目标下界（对于最小值问题），这称为定界。...

2018-11-10 14:57:31 2234

原创反FBI树

泰州市程序设计比赛高中组第四题 #include <bits/stdc++.h>using namespace std;string s; void work(int left,int right){ if(left==right) { switch(s[right] ){ case 'B': cout << 0;break; case 'I'...

2018-07-04 21:37:39 158

1.上升段( one.cpp )【问题描述】输入n及n个正整数，输出上升段的数目，所谓上升段是指两个以上连续的严格单调上升序列。【输入】输入共二行第一行只有一个正整数：n 第二行共有n个不超过10000的正整数，数与数之间用一个空格隔开【输出】输出只有一行且只有一个整数：按输入的顺序计算该序列上升段的数目【输入样例】5534 657 435 556 587【输出样例】2【样例说明】534 657 ...

2018-04-30 20:29:48 1458

原创今天的比赛题目

第一题: 刚开始想烦了, 用了宽度搜索. #include <bits/stdc++.h>using namespace std;const int MM = 100000;bool zhishu[MM];void init(int R1 ){}int jisuan(int x, int y){ int xx[5]; int yy[5];...

2018-04-23 22:04:57 183

原创 NOIP 2015 普及组扫雷游戏

#include <iostream>#include <algorithm>#include <stdio.h>#include <vector>#include <queue>#include <utility>#include <bits/stdc++.h>using namespace s

2018-04-19 18:09:20 1081

原创《挑战程序设计竞赛》 P108 Roadbloks 3255 改造Dijkstra算法次短路径

次短路径题目链接： http://poj.org/problem?id=3255我求出了最短路径，要改造一下#include <iostream>#include <algorithm>#include <stdio.h>#include <vector>#include <queue>#include <utilit...

2018-04-17 10:03:10 226

原创挑战程序设计竞赛 P109 Conscription(征兵) POJ 3723

http://poj.org/problem?id=3723这一题竟然用cin通不过，用scanf 通过了。POJ的编译器不支持struct这个用法: (edge) { e.u , e.v , e.cost }#include <iostream>#include <algorithm>#include <stdio.h>int N,M,R;co...

2018-04-17 09:10:08 202

转载《挑战程序设计竞赛》Bribe the prisioners 贿赂罪犯P129

https://www.cnblogs.com/cmmdc/p/7204991.html 写的好。方法2的思想是：例如要释放 a1,a2,...,aQ囚犯，我们记为A[1]-A[Q],先分成最小的区间开始找，为了方便，我们把两端也加入，这样变为A[0]-A[Q+1]什么叫最小的区间？就是在区间里面只有一个要释放的囚犯，这样的区间（长度为2）是 A[0]−A[2],A[1]−A[3]..A[Q−1]...

2018-04-16 10:06:47 199

原创 spring boot + jquery 调试点滴

spring boot + jquery EasyUI 调试点滴1 springdatajpa是很好用的一个工具，但是！首先你要会用今天下午就被一个spring-data-jpa的问题卡了略久，因为想要用mysql自增id，想要在save之后获取这个保存的实体的id进行后续的工作，一直以为springdatajpa中的save方法执行结束之后，save(entity)中的entity就会自动...

2018-03-07 23:05:40 1717

原创《挑战程序设计竞赛》P202 矩阵的幂

POJ 3734 题目链接： http://poj.org/problem?id=3734题解：矩阵的幂，优化动态规划poj2411 Mondriaan's Dream 题意：给定一个长宽小于等于11的矩形，问用1×2的小矩形填满，有多少种方法。题目链接：http://poj.org/problem?id=2411动态规划：状态压缩POJ 3420 题目链接： http://poj.org...

2018-02-21 09:45:12 238

原创《挑战程序设计竞赛》P185 分桶法平方分割

poj2104 K-th Number 题目链接：

2018-02-20 23:16:58 155

原创《挑战程序设计竞赛》P164 坐标离散化

问题描述】 w*h的格子画了n条或垂直或水平宽度为1的直线，求出这些格子被划分成了多少个4连块（上、下、左、右连通）。【输入格式】第一行包含两个整数：w和h，表示矩阵的列数和行数（行列编号都从1开始）。第二行包含一个整数n，表示有n条直线。接下来的n行，每行包含四个整数：x1,y1,x2,y2，表示一条直线的列号和行号。【输出格式】一个整数，表示区域数量。【输入样例】10 1051 ...

2018-02-20 09:12:44 368

原创《挑战程序设计竞赛》P158 弹性碰撞

poj3684 题目链接：http://poj.org/problem?id=3684一下代买只有样例通过了，没有别的数据。找不到出错的原因，怎么办呢？精度吗？？原因查明：先排序，最后总体加上 2*R*i。为什么不先加上2*R*i，然后排序呢？？21 10 10 1002 10 10 100//#include <bits/stdc++.h>#include <map&g...

2018-02-19 23:52:21 164

原创《挑战程序设计竞赛》 P150 开关问题

poj 3276 题目链接：http://poj.org/problem?id=3276通过啦！//#include <bits/stdc++.h>#include <map>#include <set>#include<iostream>#include <stdio.h>#include<cstring>#d...

2018-02-19 21:47:14 203 1

原创 c++转python，有些语法就是不一样

摘录自 https://www.liaoxuefeng.com/wiki/0014316089557264a6b348958f449949df42a6d3a2e542c000python基础1 Python允许用'''...'''的格式表示多行内容2空值是Python里一个特殊的值，用None表示。None不能理解为0，因为0是有意义的，而None是一个特殊的空值。3 理解变量，以下代码你一定会...

2018-02-07 21:24:26 364

原创 python cookbook 读书笔记（每一小节一句话）

第一章数据结构和算法1.1 将序列分解，只要是对象是可迭代的（元组，列表，字符串，文件，迭代器，生成器。。。），都可以分解成单独的变量。data=["acm", 50, 91.1, (2018, 2 ,8)]name, shares, price, date = date1.2 从很长的可迭代对象中单独分解出需要的元素（需要的长度，与总长度不匹配）recorder = （"张"

2018-02-07 19:17:06 140

原创《挑战程序竞赛》 P149 尺取法

Poj3320 题目链接:http://poj.org/problem?id=3320 顺利通过。顺便提一下：POJ不支持 #include <bits/stdc++.h> 这一题如果用流输入cin 会超时。改用scanf()完美通过131 2 2 3 4 1 2 3 4 2 3 2 1//#include <bits/stdc++.h>#include <m...

2018-02-01 23:18:27 173

原创树网的核

luogu上少了一句话，造成我那道题目百思不得其解。这道题目主要要理解几个概念。设T=(V, E, W) 是一个无圈且连通的无向图（也称为无根树），每条边带有正整数的权，我们称T为树网（treenetwork），其中V, E分别表示结点与边的集合，W表示各边长度的集合，并设T有n个结点。路径：树网中任何两结点a,b都存在唯一的一条简单路径，用d(a,b)表示以a,b为端点的路径的长度

2018-01-23 20:44:41 225

原创 NOIP 2010 提高组神经网络

拓扑排序递推。/*ÊäÈë4 41 2 1000003 4 1000001 3 22 4 1Êä³ö0*/#include #include using namespace std;const int MM=101; int n,p; //n 个点 p个边struct Edge{ //存储边 int to; int w

2018-01-19 23:35:23 191

原创 NOIP 2010 提高组关押罪犯

思路：并查集 + 优先队列优先队列貌似也用不上，排序就可以了。样例输入2 11 2 28135样例输出0没有通过：再次提醒我，注意边界。注意极端情况刚开始，往二分图上想了即将一个无向图分成两个独立的点集，使两个点集中所有的边的边权的最大值的最小值是多少（然而我不会二分图染色……）扫盲：什么叫做二分图，二分图的最大匹配http://www.r

2018-01-18 22:20:28 317

原创 python，你我日常办公用到的功能

python操作Excel如果实在想扩展功能，我选择 xlwings：简单强大，可替代VBA1 安装 python 3.6.2 进入 cmd ，pip install xlwings3 安装是出了问题：由于安装的时候默认安装在 c:\program files\...中，这个路径路径中有空格，安装 xlwings是没有成功l解决步骤：重新安装python，安装在没有空格的路径中...

2018-01-18 21:08:43 13671 1

原创关于状态压缩

很多状态无法压缩成不超过64位的整数。怎么办呢？为什么忘了bitset？是个好东西。bitset，每个bool值占用一个bit，所以4字节大小能存储32bit。不仅缩小了占用空间，并且有专门优化过的类型方法，提高效率，乃是提高空间和时间复杂度的利器。参见Reference： http://www.cplusplus.com/reference/bitset/bitset/

2018-01-17 17:29:22 165

原创关于排序等规则

关于优先队列：请注意reference中的这段描述Priority queuePriority queues are a type of container adaptors, specifically designed such that its first element is always the greatest of the elements it contains, according

2018-01-17 17:18:58 157

转载关于二分法的网上一个大佬的理解

CDQ 是什么意思，我还没明白http://blog.csdn.net/hbhcy98/article/details/50642773

2018-01-16 08:16:59 135

转载 NOIP 2015 提高组 Day2 跳石头

起初思路：用线段树维护最短距离。每次移走哪些石头呢？这是个棘手的问题。线段树行不通啊网上说二分法：没有头绪终于懂了：起初没搞清楚，究竟二分什么，以为是将石头数目进行二分。使最短跳跃距离尽可能长”就应该想到这是道二分的题，分什么？分跳跃距离！！我们二分一下两个石头之间的最大距离，从0~L，然后找一下能移走的石头，如果能移走，答案加一。最后如果答案大于允许移走的石头数，就在左区间二分，...

2018-01-12 21:49:42 241 2

原创 NOIP 2015 提高组 Day2 运输计划

通过LCA，求出u到v的路径长度。顺表找出经过的最长边（可以先将边排序）

2018-01-12 21:42:22 231

原创 NOIP 2015 提高组 Day2 子串

感觉这一题一定是动态规划：知道题目是删除相关的字符，使得结果与目标串匹配最短编辑距离？？dp[ i ] [ j ] [ k ] 我也想到了，但转移呢？在思考.....网上思路用f[i][j][k]表示A串匹配到第i个字符，B串匹配到第j个字符，已经取了k个互不重叠的非空子串的方案数，那么f[i][j][k]=Σf[i-w-o][j-w][k-1](w=1-A[i]和B[j]

2018-01-12 21:32:28 205 1

原创 NOIP 2015 提高组 Day1 斗地主

为什么网上有这么多的DFS最少需要多少次出牌，最少，就意味着宽度搜索啊。我来试一下宽度艘多。若果能我彻底领悟A*算法。我也想用A*算法试一下。今天突然有了灵感：跟上次的愤怒的小鸟有什么区别呢？如出一辙啊。状态规划+ 状态压缩。状态怎么压缩，初步的想法是longlong s 。64位，一共54张牌，完全可以状态压缩。（int 32位 Long LongLong 64位，）五进制数，

2018-01-12 21:07:30 309

原创 NOIP 2015 提高组 Day1 神奇的幻方

纯模拟。无难度#include //#define debugusing namespace std;int N;const int MM=40;int magic[MM][MM];int main(){ memset( magic, 0 ,sizeof(magic) ); cin >> N; int k=1; int i=1;

2018-01-11 17:48:26 169

原创 NOIP 2015 提高组 Day1 信息传递

求最小的环的长度。没思路大概这已经卡死一小半人。我的起初的想复杂了。后来觉得：这道题真简单：n个点，n-1条边，如果没有环的话，这是一棵树。这些题目应该不可能考察这些非常规的高难度的算法把。求强联分量起初的想法，，然后在处理。这些题目应该不可能考察这些非常规的高难度的算法把。题外话：网上看了一个好东西：有人提出了这样的算法。显然该无向图存在连通分支。对每个连通分支单独进行考

2018-01-11 08:16:24 281

原创 NOIP 2013 提高组华容道

准备用A*算法，和 IDA*算法分别试一下。A*算法最好的A*算法详解摘自：https://www.redblobgames.com/pathfinding/a-star/introduction.html国人翻译：https://www.cnblogs.com/L-Arikes/p/4314113.html 在摘录一篇http://blog.csdn.net/hitwhylz/article

2018-01-10 10:54:17 264

原创 NOIP 2016 提高组 Day2 组合数问题

是我想起了有一年考过相似的题目：当时用的是杨辉三角。https://www.cnblogs.com/ljh2000-jump/p/6189056.html思路 : 递推 + 矩阵前缀和关于矩阵前缀和：http://blog.csdn.net/Loi_YZS/article/details/52992189C(n,m)=C(n-1,m)+C(n-1,m-1),就可以直接递推出2000以内的所

2018-01-04 21:58:20 355

原创 NOIP 2016提高组 Day2 蚯蚓

直觉用大根堆堆用STL的priority_que 实现的；过了七组数据，还有13组数据未过#include using namespace std;const int MM=100000;int n,m,q,u,v,t;//那只蚯蚓 m:时间 q：增加的长度 p=u/vint qiuyin[MM];vector qiuyin2;priority_queue que;

2018-01-04 21:47:45 196

空空如也

空空如也