- 博客(29)
- 收藏
- 关注
RSS订阅原创 线段树代码模板
区间查询/区间修改（加减）的模板代码#include<bits/stdc++.h>using namespace std;const int N = 1e5+10;int a[N];struct node{ int l,r,sum,lz; int mx,mn;} T[N*4];//建树void build(int i, int l, int r){ T[i].l = l; T[i].r = r; T[i].lz = 0;
2021-12-01 21:08:07
160
原创 KMP算法
KMP算法计算字符串t第一次在字符串s中出现的位置的算法最长相等前后缀abccab 的最长相等前后缀就是ab注意：前缀是当前字符前面的一部分子串，不包含当前字符，后缀类似。例如：abc前缀集合为{a，ab}，后缀集合为{c，bc}假设现在有两个字符串s，ts: a b c a b e a b c a b ct: a b c a b c初始时，i指向s[0], j指向t[0]如果s[ I ] = t[ j ]， i++, j++ ，一直往后遍历，当遇到了一个不相等的字符时，常规的
2021-04-20 21:37:52
319
1
原创 简单深搜广搜基本模板
简单搜索DFS：剪枝，条件容易超时，超时后基本就是剪枝的问题/无限递归？，或者用广搜试试？模板（自己的理解）int n,m;//一般输入的行列数/边界int mov[4][2] = {1,0,-1,0,0,1,0,-1};int vis[N][N],mapp[N][N];//vis初始化应该在主函数int s = 0;//记录步数时间什么的void DFS(int x,int y){ if(x = endx && y == endy)//满足条件
2021-04-12 21:34:21
2661
原创 I NEED A OFFER!（动规，推算一维dp数组，经费为什么不能从前往后遍历）
Problem DescriptionSpeakless很早就想出国，现在他已经考完了所有需要的考试，准备了所有要准备的材料，于是，便需要去申请学校了。要申请国外的任何大学，你都要交纳一定的申请费用，这可是很惊人的。Speakless没有多少钱，总共只攒了n万美元。他将在m个学校中选择若干的（当然要在他的经济承受范围内）。每个学校都有不同的申请费用a（万美元），并且Speakless估计了他得到这个学校offer的可能性b。不同学校之间是否得到offer不会互相影响。“I NEED A OFFER”，他大
2021-04-01 21:16:54
132
原创 方格取数(1)（状压dp）
Problem Description给你一个nn的格子的棋盘，每个格子里面有一个非负数。从中取出若干个数，使得任意的两个数所在的格子没有公共边，就是说所取的数所在的2个格子不能相邻，并且取出的数的和最大。Input包括多个测试实例，每个测试实例包括一个整数n 和nn个非负数(n<=20)Output对于每个测试实例，输出可能取得的最大的和Sample Input375 15 2175 15 2834 70 5Sample Output188状压dp最后一行的状态取决于前
2021-03-29 20:59:38
192
转载 匈牙利算法--求最大匹配（转）
转自https://blog.csdn.net/u013384984/article/details/90718287本文讲述的是匈牙利算法，即图论中寻找最大匹配的算法，暂不考虑加权的最大匹配（用KM算法实现），文章整体结构如下：基础概念介绍算法的实现好的，开始！一. 部分基础概念的介绍我会严格介绍其定义，并同时用自己的大白话来重述。概念点1. 图G的一个匹配是由一组没有公共端点的不是圈的边构成的集合。这里，我们用一个图来表示下匹配的概念：如图所示，其中的三条边即该图的一个匹配；所以，匹
2021-03-26 21:04:30
2128
原创 Train Problem I（栈）
Problem DescriptionAs the new term comes, the Ignatius Train Station is very busy nowadays. A lot of student want to get back to school by train(because the trains in the Ignatius Train Station is the fastest all over the world v). But here comes a proble
2021-03-22 21:28:08
199
原创 简单计算器（栈、处理符号）
Problem Description读入一个只包含 +, -, *, / 的非负整数计算表达式，计算该表达式的值。Input测试输入包含若干测试用例，每个测试用例占一行，每行不超过200个字符，整数和运算符之间用一个空格分隔。没有非法表达式。当一行中只有0时输入结束，相应的结果不要输出。Output对每个测试用例输出1行，即该表达式的值，精确到小数点后2位。Sample Input1 + 24 + 2 * 5 - 7 / 110Sample Output3.0013.36创建一个
2021-03-22 21:11:03
130
原创 Nightmare（BFS）
Problem DescriptionIgnatius had a nightmare last night. He found himself in a labyrinth with a time bomb on him. The labyrinth has an exit, Ignatius should get out of the labyrinth before the bomb explodes. The initial exploding time of the bomb is set to
2021-03-19 20:57:57
189
原创 逃离迷宫（bfs）
Problem Description 给定一个m × n (m行, n列)的迷宫，迷宫中有两个位置，gloria想从迷宫的一个位置走到另外一个位置，当然迷宫中有些地方是空地，gloria可以穿越，有些地方是障碍，她必须绕行，从迷宫的一个位置，只能走到与它相邻的4个位置中,当然在行走过程中，gloria不能走到迷宫外面去。令人头痛的是，gloria是个没什么方向感的人，因此，她在行走过程中，不能转太多弯了，否则她会晕倒的。我们假定给定的两个位置都是空地，初始时，gloria所面向的方向未定，她可以选择4
2021-03-16 21:13:47
281
原创 Bone Collector（01背包问题、动态规划）
背包问题动态规划：记录背包从0-v大小情况下，放入每个骨头时的最大价值。#include<stdio.h>#include<string.h>#include<stdlib.h>#define N 1010#define Max(a,b) (a)>(b)?(a):(b)int dp[N][N];int main(){ int t,n,v; scanf("%d",&t); while(t--) {
2021-03-14 19:53:05
220
原创 Super Jumping! Jumping! Jumping! （最大递增子序和、动规）
最大递增子序和#include<stdio.h>#include<string.h>#include<stdlib.h>#define Max(a,b) (a)>(b)?(a):(b)int main(){ int n,a[1010],dp[1010]; int max = -1; while(~scanf("%d",&n) && n) { max = -1; f
2021-03-14 19:33:10
205
原创 Max Sum（最大字串和、动规）
#include<stdio.h>#include<string.h>#include<stdlib.h>#define N 100010#define Max(a,b) (a)>(b)?(a):(b)int main(){ int T,n,num[N],max,dp[N]; scanf("%d",&T); for(int t = 1; t<=T; t++) { max = -1001;
2021-03-14 19:30:21
410
原创 棋盘问题（深搜）
Problem Description在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放k个棋子的所有可行的摆放方案C。Input输入含有多组测试数据。 每组数据的第一行是两个正整数，n k，用一个空格隔开，表示了将在一个n*n的矩阵内描述棋盘，以及摆放棋子的数目。 n <= 8 , k <= n 当为-1 -1时表示输入结束。 随后的n行描述了棋盘的形状：每行有n个字符，
2021-02-01 10:36:07
1676
原创 命运（动态规划）
Problem Description穿过幽谷意味着离大魔王lemon已经无限接近了！可谁能想到，yifenfei在斩杀了一些虾兵蟹将后，却再次面临命运大迷宫的考验，这是魔王lemon设下的又一个机关。要知道，不论何人，若在迷宫中被困1小时以上，则必死无疑！可怜的yifenfei为了去救MM，义无返顾地跳进了迷宫。让我们一起帮帮执着的他吧！命运大迷宫可以看成是一个两维的方格阵列，如下图所示： yifenfei一开始在左上角，目的当然是到达右下角的大魔王所在地。迷宫的每一个格子都受到幸运女神眷恋或者痛苦魔王
2021-01-28 18:49:01
376
原创 汉诺塔IV，汉诺塔V
汉诺塔IVProblem Description还记得汉诺塔III吗？他的规则是这样的：不允许直接从最左(右)边移到最右(左)边(每次移动一定是移到中间杆或从中间移出)，也不允许大盘放到小盘的上面。xhd在想如果我们允许最大的盘子放到最上面会怎么样呢？（只允许最大的放在最上面）当然最后需要的结果是盘子从小到大排在最右边。Input输入数据的第一行是一个数据T，表示有T组数据。每组数据有一个正整数n(1 <= n <= 20)，表示有n个盘子。Output对于每组输入数据，最少需要的摆
2021-01-27 12:23:06
395
原创 Heavy Transportation（最短路 Dijkstra）
Problem DescriptionBackgroundHugo Heavy is happy. After the breakdown of the Cargolifter project he can now expand business. But he needs a clever man who tells him whether there really is a way from the place his customer has build his giant steel crane
2021-01-26 19:06:24
676
原创 Bull Math（大数相乘）
Problem DescriptionBulls are so much better at math than the cows. They can multiply huge integers together and get perfectly precise answers … or so they say. Farmer John wonders if their answers are correct. Help him check the bulls’ answers. Read in tw
2021-01-26 18:02:50
426
1
原创 最短路算法Dijkstra与Floyd
Dijkstra算法Dijkstra算法采用的是一种贪心的策略，声明一个数组dis来保存源点到各个顶点的最短距离和一个保存已经找到了最短路径的顶点的数组vis，初始时，原点 s 的路径权重被赋为 0 （dis[s] = 0）。若对于顶点 s 存在能直接到达的边（s,m），则把dis[m]设为w（s, m）,同时把所有其他（源点s不能直接到达的）顶点的路径长度设为无穷大。初始时，数组vis只标记顶点s。 然后，从dis数组选择最小值，则该值就是源点s到该值对应的顶点的最短路径，并且把该点加入到vis中，此时
2021-01-17 17:03:17
622
1
原创 Anniversary Cake （深搜）
Anniversary CakeProblem DescriptionNahid Khaleh decides to invite the kids of the “Shahr-e Ghashang” to her wedding anniversary. She wants to prepare a square-shaped chocolate cake with known size. She asks each invited person to determine the size of th
2021-01-17 11:04:43
229
原创 Red and Black （深搜）
Red and BlackProblem DescriptionThere is a rectangular room, covered with square tiles. Each tile is colored either red or black. A man is standing on a black tile. From a tile, he can move to one of four adjacent tiles. But he can’t move on red tiles, h
2021-01-17 10:41:08
275
原创 Integer Inquiry（大数相加）
Integer InquiryTotal Submission(s) : 8 Accepted Submission(s) : 3Problem DescriptionOne of the first users of BIT’s new supercomputer was Chip Diller. He extended his exploration of powers of 3 to go from 0 to 333 and he explored taking various sums o
2021-01-16 18:18:03
232
原创 Bank Interest
Bank InterestProblem DescriptionFarmer John made a profit last year! He would like to invest it well but wonders how much money he will make. He knows the interest rate R (an integer between 0 and 20) that is compounded annually at his bank. He has an in
2021-01-16 17:58:02
149
原创 To the Max 最大矩形和
To the MaxProblem DescriptionGiven a two-dimensional array of positive and negative integers, a sub-rectangle is any contiguous sub-array of size 1*1 or greater located within the whole array. The sum of a rectangle is the sum of all the elements in that
2021-01-16 17:46:36
220
原创 Goldbach‘s Conjecture 哥德巴赫猜想
Goldbach’s ConjectureProblem DescriptionIn 1742, Christian Goldbach, a German amateur mathematician, sent a letter to Leonhard Euler in which he made the following conjecture:Every even number greater than 4 can bewritten as the sum of two odd prime nu
2021-01-16 17:13:22
1432
原创 Longest Ordered Subsequence 最长有序子序列
Longest Ordered SubsequenceProblem DescriptionA numeric sequence of ai is ordered if a1 < a2 < … < aN. Let the subsequence of the given numeric sequence (a1, a2, …, aN) be any sequence (ai1, ai2, …, aiK), where 1 <= i1 < i2 < … < iK
2021-01-16 16:57:34
751
原创 Palindrome 回文
PalindromeProblem DescriptionA palindrome is a symmetrical string, that is, a string read identically from left to right as well as from right to left. You are to write a program which, given a string, determines the minimal number of characters to be in
2021-01-16 16:28:37
454
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人