- 博客(149)
- 收藏
- 关注
RSS订阅原创 最优装载问题（回溯经典问题 子集树）
最优装载问题，在贪心算法里有一个版本。回溯算法里，最优装载问题发生了变化问题描述小j买东西有个特点，不一定买好的，也不一定要买的多，只要能恰好把身上的钱花光就好。现在给出n个物品的价格Ai以及小j身上的现金S，假设每个物品的数目只有一个，请问他能将身上所带的钱花完吗？输入第一行输入一个数字n表示物品的数目(n ≤ 36)，一个数字S表示小j所带的钱( 1≤S≤1e12)，用空格隔开。接下来一行n个数字，每两个数字之间用空格隔开，第i个数字Ai表示第i个物品的价格( 1≤Ai≤1e12)。
2021-06-02 10:19:31
496
1
原创 旅行售货员问题（回溯排序树经典例题）
题目描述：关于旅行售货员问题，有多个版本的描述。这里小编选择了一种题目描述在瓦罗兰大陆上，蕴含着强大能量的符文散落在各地。作为召唤师的你需要收集n个铭文来强化自身。现在给出你n个符文的坐标，假设起始点在(0,0),请你计算获得这n个符文并回到起始点所需要走的最短路程。(两个点之间的距离为其曼哈顿距离)相应输入第一行输入一个n,(1≤n≤10 ) 接下来n行每行两个整数X，Y（-1000≤X，Y≤1000） 可能有不同符文的位置相同。测试样例31 13 32 3测试输出12
2021-06-01 18:33:14
891
原创 逆序数求解（归并排序思想）
最近遇到求解逆序数的问题，题目如下：问题描述：A为一个有n个数字的有序集 (1<=n<=1e5)，其中所有数字各不相同。当存在正整数 i, j 使得 1 ≤ i < j ≤ n 而且 A[i] > A[j]，则 <A[i], A[j]> 这个有序对称为 A 的一个逆序对，也称作逆序数。请问序列A中的逆序对有多少个。输入第一行，序列长度n。（1<=n<=1e5）第二行，序列a[1]…a[n]。（a[i]<1e8）输出逆序对个数。样例输入
2021-04-02 23:12:26
402
原创 Qt 5.12 解决中文乱码问题
乱码用Qt 5.12 开发的时候，遇到了不支持汉字的问题。查了很多种解决办法，最终还是这种解决办法最好解决方法在主菜单中找到工具->选项，打开文本编辑器->行为，之后按照这样的方式设置文件编码之后为了保证编码确实为utf-8，在cpp文件中加上这一句#pragma execution_character_set("utf-8")就算搞定了效果#include<QCoreApplication>#include<QTextStream>#includ
2021-01-31 20:54:42
1026
2
原创 Qt 控制台运行无法弹出小黑框
Qt Console ApplicationQt 主要是GUI界面的设计，但在学习的时候控制台运行显得更加方便一些。小编在第一次新建控制台运行的时候，点击运行没有弹出小黑框，解决方法主要是因为没有执行qmake，就需要在Qt的pro文件里面加上CONFIG += c++11 console之后再在主菜单里面找到构建，点击“执行qmake”，就可以生成小黑框了...
2021-01-30 17:20:31
3510
1
原创 Qt Creator 一些实用小技巧
添加或更改快捷键之前在VS2019中关于交换上下行的快捷键一直是Alt+Up，但在Qt 中的是ctrl+shift+up，用起来很不方便。更改方法很简单，先启动Qt Creator，一次点击主菜单的菜单选项“工具->选项”，然后在“选项”的对话框的左边选择“环境”，在右边选择“键盘”，然后在“Keyboard Shortcuts”下的编辑框中输入“moveline”，此时就会自动搜索到MoveLineDown,MoveLineUp.如图所示之后单击MoveLineDown，然后点击下方的Rec
2021-01-30 16:56:55
143
原创 Kruskal算法 （两道基础题练习）
Constructing RoadsTime Limit: 2000MS Memory Limit: 65536KDescriptionThere are N villages, which are numbered from 1 to N, and you should build some roads such that every two villages can connect to each other. We say two village A and B are connected,
2020-11-27 22:09:48
705
原创 牛客：队列Q（思维）
题目链接来源：牛客网题目描述ZZT 创造了一个队列 Q。这个队列包含了 N 个元素，队列中的第 i 个元素用 Qi 表示。Q1 表示队头元素，QN 表示队尾元素。队列中的元素是 N 的一个全排列。ZZT 需要在这个队列上执行 P 次操作，操作分两种：FIRST X: 将元素 X 移到队头。LAST X: 将元素 X 移到队尾。在 P 次操作之后，ZZT 想知道队列中的元素的排列方式，由于他最近很忙，因此需要请你帮他解决这个问题。输入描述:第一行输入一个正整数 N，表示队列的大小。第二行输
2020-11-26 11:49:20
503
原创 poj: 1258 Agri-Net（Prim算法基础）
Agri-NetDescriptionFarmer John has been elected mayor of his town! One of his campaign promises was to bring internet connectivity to all farms in the area. He needs your help, of course.Farmer John ordered a high speed connection for his farm and is go
2020-11-26 11:36:01
151
原创 poj:1270 Following Orders
Following OrdersTime Limit: 1000MSMemory Limit: 10000KDescriptionOrder is an important concept in mathematics and in computer science. For example, Zorn’s Lemma states: ``a partially ordered set in which every chain has an upper bound contains a maxima
2020-11-11 00:06:04
130
原创 定义一个简单的Computer类（类的组合）
今天做了三道C++的练习题，前两道比较简单，松松AC。关于最后一道，由于有一些C++的基础知识还没有掌握的太清楚，修改的比较多。于是就想写一下关于这道题的知识总结及其拓展延伸。题目定义一个简单的Computer类，有数据成员芯片（cpu）、内存（ram）、光驱（cdrom）等等，有两个公有成员函数run、stop。Cpu为CPU类的对象，ram为RAM类的一个对象，cdrom为CDROM类的对象，定义并实现这个类。分析其实是一道比较基础的组合类的问题，但是组合类的知识没有掌握的很周全，还有就是关于枚
2020-11-10 21:17:22
11943
原创 Eclipse Java项目建立
Java中类是在package中建立的，所以要想建立一个java类文件，需要先创建一个package。这里编译器以Eclipse为例创建Java项目点击Eclipse左上角的File，之后点击里面的New，之后选中project。之后会出现以下界面。选择Java Project，之后写好项目的名字，（以Main为例）建立项目创建package之后找到创建好的Main项目的src目录，右键选中New，之后选中package,写好包的名字即可创建类在MaIn的子目录下面找到创建好的包Mai
2020-11-06 23:45:31
205
原创 JDK与Eclipse下载及路径设置
很多初学Java的童鞋都需要下载Java虚拟机，一般比较流行的都是下载Oracle公司的JDK，官网下载JDK1.8官网链接一般是在这里下载JDK，点击链接选择JDK1.8版本进行下载。（由于Java跨系统的特性，下载时要根据需要选择相应的系统进行下载）例如：如果是windows 系统一般是选择这个划线的进行下载，注意要选择windows x86执行文件（.exe）添加路径：JDK下载完成之后需要添加JDK路径，这里需要打开JDK下载的位置，一般默认下载的位置是C盘，这里打开JDK的bin文件
2020-11-06 23:17:12
453
1
原创 Binary Search Heap Construction （笛卡尔树）
Binary Search Heap Construction题目链接Time Limit: 2000MSMemory Limit: 30000KDescriptionRead the statement of problem G for the definitions concerning trees. In the following we define the basic terminology of heaps. A heap is a tree whose internal nodes
2020-11-03 23:40:20
217
原创 二叉堆实现优先队列（大根堆、小根堆）
大根堆大根堆是根节点比其儿子结点值要大的二叉堆，故优先队列的队首数值是最大的。具体实现见代码：#include<iostream>#include<cstdio>using namespace std;const int maxn = 1000;class Priority_queue //大根堆，优先队列{public: int heap[maxn], tot; Priority_queue(); ~Priority_queue(); void
2020-10-20 16:50:16
356
原创 基础训练（四）BST二叉排序树
BST（poj:2309）题目传送门Time Limit: 1000MSMemory Limit: 65536KDescriptionConsider an infinite full binary search tree (see the figure below), the numbers in the nodes are 1, 2, 3, … In a subtree whose root node is X, we can get the minimum number in this su
2020-10-18 21:32:27
223
原创 小型计算器（后缀表达式计算）
对于普通的四则混合运算，可以将表达式通过转换成逆波兰式来进行计算。具体是通过栈来进行实现的，代码如下：代码：#include<iostream>#include<cstdio>#include<stack>#include<sstream>#include<string>using namespace std;string in, post;stack<char>st;stack<int>p;voi
2020-10-17 16:36:52
384
原创 迷宫问题再研究
迷宫问题属于简单的搜索问题，用dfs或者bfs即可比较轻松的解决。这里附上两种写法，用栈实现的dfs和用队列实现的bfs。队列实现bfs代码：#include<iostream>#include<stack>#include<queue>#include<algorithm>#include<cstdio>using namespace std;#define INF 0x3f3f3ftypedef pair<int, i
2020-10-17 16:30:17
113
原创 POJ 3437 Tree Grafting（有序树转二叉树）
Tree Grafting题目链接Time Limit: 5000MSDescriptionTrees have many applications in computer science. Perhaps the most commonly used trees are rooted binary trees, but there are other types of rooted trees that may be useful as well. One example is ordered t
2020-10-13 00:06:45
212
原创 树状数组小记
有的时候，从现实生活中抽象出来的模型中结点被赋予了一个权值，而求解目标是动态统计子树的权值和，如果通过直接遍历求解，耗费的时间复杂度是O（n），但问题是，若结点的权值在不断的发生变化，那么相关的权值和也在不断的发生着变化，如此这般通过不断遍历实现的方法时间复杂度就会很高，由此衍生出了树状数组的计算方法，可以实现不断对数组结点的权值进行查询和维护。查询和维护的时间复杂度为O（log n）；树状数组：主要有三个函数组成：函数1：主要用于对数组结点的划分int lowbit(int x) { retu
2020-10-01 11:27:24
107
原创 基础训练（三）二叉树基础概念应用
Expressions（poj: 3367）Arithmetic expressions are usually written with the operators in between the two operands (which is called infix notation). For example, (x+y)*(z-w) is an arithmetic expression in infix notation. However, it is easier to write a prog
2020-09-30 23:26:56
278
原创 Tree UVA 548 （遍历序列建立二叉树+dfs遍历）
题目链接You are to determine the value of the leaf node in a given binary tree that is the terminal node of a path of least value from the root of the binary tree to any leaf. The value of a path is the sum of values of nodes along that path.InputThe input
2020-09-30 22:43:43
147
原创 一般二叉树遍历序列转换
根据一棵二叉树的中序，后序遍历的结果，可以唯一的确定一棵二叉树，这里附上代码实现从中序，后序遍历的序列转换成广度优先搜索遍历的序列（这里默认二叉树结点数目小于10000）代码：#include<iostream>#include<cstdio>#include<string>#include<cstring>#include<algorithm>#include<vector>#include<queue>
2020-09-29 16:29:59
127
原创 基础训练（二）：字符串相关习题汇总
Manacher算法：Palindrome（poj:3974）Time Limit: 15000MS Memory Limit: 65536KTotal Submissions: 20122 Accepted: 7679DescriptionAndy the smart computer science student was attending an algorithms class when the professor asked the students a simple questio
2020-08-11 10:37:19
218
原创 基础训练（一）：并查集练习汇总
关于并查集的基础知识，这里不再赘述，这里写的很详细并查集基础这里只想汇总一下最近的练习食物链（poj:1182）Description动物王国中有三类动物A,B,C，这三类动物的食物链构成了有趣的环形。A吃B， B吃C，C吃A。现有N个动物，以1－N编号。每个动物都是A,B,C中的一种，但是我们并不知道它到底是哪一种。有人用两种说法对这N个动物所构成的食物链关系进行描述：第一种说法是"1 X Y"，表示X和Y是同类。第二种说法是"2 X Y"，表示X吃Y。此人对N个动物，用上述两种说法，一句
2020-08-11 10:16:30
219
原创 POJ 1040:Transportation
TransportationTime Limit: 1000MSMemory Limit: 10000KDescriptionRuratania is just entering capitalism and is establishing new enterprising activities in many fields in- cluding transport. The transportation company TransRuratania is starting a new expre
2020-07-23 14:42:42
154
原创 POJ 1363 Rails （值得一记的栈好题）
RailsTime Limit: 1000MS Memory Limit: 10000KDescriptionThere is a famous railway station in PopPush City. Country there is incredibly hilly. The station was built in last century. Unfortunately, funds were extremely limited that time. It was possibl
2020-07-16 17:04:07
582
原创 约瑟夫问题（问题总结）
约瑟夫问题描述n 个人标号0,1，2，…n-1 。逆时针站一圈，从 0 号开始，每一次从当前的人逆时针数 个，然后让这个人出局。问最后剩下的人是谁。线性解法模板根据问题的描述，很容易想到递推公式Josephus（n,k）=Josephus（n-1,k）。（其中n是规模，k是循环次数）。如此有一下代码：int josephus(int n, int k) { int res = 0; for (int i = 1; i <= n; ++i) res = (res + k) % i;
2020-07-15 18:28:12
410
原创 ZOJ 1256 What Day Is It?（有点坑）
What Day Is It?Time Limit: 2000 msMemory Limit: 65536 KB The calendar now in useevolved from the Romans. Julius Caesar codified a calendar system thatcame to be known as the Julian calendar. In this system, all monthshave 31 days, except for April, Ju
2020-07-14 17:33:56
171
原创 POJ 2246 Matrix Chain Multiplication
Matrix Chain MultiplicationTime Limit: 1000MSMemory Limit: 65536KDescriptionSuppose you have to evaluate an expression like ABCDE whereA,B,C,D and E are matrices. Since matrix multiplication isassociative, the order in which multiplications are p
2020-07-14 09:36:53
178
原创 Sticks（递归回溯好题）
SticksTime Limit: 1000MS Memory Limit: 10000KDescriptionGeorge took sticks of the same length and cut them randomly until all parts became at most 50 units long. Now he wants to return sticks to the original state, but he forgot how many sticks he had
2020-07-12 18:42:50
206
原创 并查集典例
P1955 [NOI2015]程序自动分析题目大意：给出一些两个数字相等的条件，再给出一些两个数字不等的条件，要求判断能让这些数字取一个值使得这些条件同时满足。思路离散化+并查集AC代码：#include<iostream>#include<algorithm>using namespace std;const int maxn = 100010;int lsh[2 * maxn];int fa[2 * maxn];struct node{ int x
2020-07-06 12:21:15
118
原创 AC自动机典例集
P3808 【模板】AC自动机（简单版）题目链接题目大意：大概是给你n组字符串，然后给你一个文本串，从中查找n组字符串在文本串中一共出现了几次。思路：AC自动机模板题，直接套AC自动机公式写即可。这里需要知道的是fail指针的建立和查找，详情请见代码的build函数和find函数。时间复杂度为文本串的长度（find函数），总子串的长度和结点总数*字符集长度（一般为26）（build函数）。#include<iostream>#include<queue>using
2020-07-04 14:48:45
212
原创 Codeforce：C. Mike and gcd problem
C. Mike and gcd problemtime limit per test 2 secondsmemory limit per test 256 megabytesMike has a sequence A = [a 1, a 2, …, a n] of length n. He considersthe sequence B = [b 1, b 2, …, b n] beautiful if the gcd of all itselements is bigger than 1,
2020-07-01 17:51:18
166
原创 C. New Year Book Reading
C. New Year Book Readingtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputNew Year is coming, and Jaehyun decided to read many books during 2015, unlike this year. He has n books numbered by integers
2020-06-28 10:52:40
149
原创 P1832 A+B Problem（再升级）
题目描述：·题目名称是吸引你点进来的·实际上该题还是很水的题目描述·1+1=? 显然是2·a+b=? 1001回看不谢·哥德巴赫猜想 似乎已呈泛滥趋势·以上纯属个人吐槽·给定一个正整数n，求将其分解成若干个素数之和的方案总数。输入格式一行：一个正整数n输出格式一行：一个整数表示方案总数输入输出样例输入 #1复制7输出 #1复制3说明/提示【样例解释】7=7 7=2+57=2+2+3【福利数据】【输入】 20【输出】 26【数据范围及约定】对于30%的数据
2020-06-28 10:47:41
145
原创 优先队列易忘点
重载函数相关点：（只针对大顶堆的优先队列）#include<iostream>#include<queue>using namespace std;struct node{ int x; bool operator < (const node b)const { return x > b.x; }};priority_queue<node> p;int main(){ ios::sync_with_stdio(fals
2020-06-25 22:18:02
85
原创 C. Two Arrays
题目链接C. Two Arraystime limit per test1 second memory limit per test256 megabytes You are given two integers n and m. Calculate the number of pairs ofarrays (a,b) such that:the length of both arrays is equal to m; each element of each array isan inte
2020-06-25 21:10:20
185
原创 Min Value
链接：https://ac.nowcoder.com/acm/contest/5929/B来源：牛客网题目描述有一天，老师告诉多多：绝对值是指一个数在数轴上所对应点到原点的距离。 接下来老师给多多一个由 N 个数组成的序列a1，a2，a3，······，an-1，an，他想让多多从中任选两个数 ai 和 aj，使得 ai + aj 的绝对值最小，并且计算出 ij 的值，其中 i ≠ j。 由于老师给出的序列太长，多多无法完成这个任务，请你帮助他。 输入描述: 输入第一行包含一个正整数 N (2
2020-06-25 19:05:10
167
原创 Codeforces Round #615 (Div. 3)D. MEX maximizing（取模找最小值）
D. MEX maximizingtime limit per test3 secondsmemory limit per test256 megabytesRecall that MEX of an array is a minimum non-negative integer thatdoes not belong to the array. Examples:for the array [0,0,1,0,2] MEX equals to 3 because numbers 0,1 and
2020-06-23 16:33:44
168
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人