Qingzhx-CSDN博客

中序表达转换成后序表达式的方法：从左到右读取该中弱序表达式：1.若是操作数，则直接输出.2.若是运算符：(1)若该运算符为"(",则直接入栈.(2)若该运算符为")",则取出堆栈中的运算符，直到"("时.(3)其它：按优先级比较，如果严格大于堆栈中当前的运算则压入栈中，否则直接输出.(4)检查栈是否非空，如果非空，则输出所有值，直到空为止.*、/、%的优先级当然比+、－高了例如：中序表达式(23+34*45/(5+6+7))转换成后序表达式23 34 45 * 5 6 + 7 + / +

2022-02-08 11:24:53 198

原创 Surround the Trees(凸包)

判定有问题，一旦将n==2的注释部分解除注释就出错（明明计算过程一样）#include <bits/stdc++.h>#define maxn 160using namespace std;struct Point{ int x, y;};Point p[maxn], ch[maxn]; //后者记录凸包上的点bool cmp(Point x, Point y){ return x.x < y.x || (x.x == y.x && x

2021-11-03 23:52:59 138

原创 Codeforces11 D. A Simple Task

按照他们的代码稍微修改并加上自我理解的注释的版本首先，对于sta->x1->x2->x3->…->end->sta的成环形式，将sta作为终点，即dp[s][sta]表示以状态s中最小点为起点，sta为终点的路径数，如果还存在sta到起点的路径则加上环，我们再枚举j来表示下一个点(此处的j应大于起点，若是等于则是对应成环的情况),也就是枚举i所连的非该集合的点,要注意j不在当前点集,那么状态转移方程式就可以出来了：f[S|(1<<j)][j]+=f[S]

2021-10-25 16:58:14 151

原创 K King of the Waves(不回溯的特殊dfs)

首先分析可知，0应当作为序列尾，而前面放一个0能赢的，同理要保证倒数第二个是前面序列的最后赢家，要使得前面放一个他能赢的，由此可以写出一个由0开始的dfs，并在dfs中回溯，如果不成立，再从该位置找到另一个满足条件的点继续dfs但是这种方法太过费时，而题目中有个关键点，A如果能赢B，则A B和B A结果一样，不用严格组成输赢链，假设0的那行为X110000，对于第一个1向下dfs，形成了序列A(且A序列不完整，不能作为答案)，按第一种写法需要重新从第二个1dfs，但是如果直接把第二个1放在A序

2021-08-31 11:12:55 50

原创试题算法提高合并石子(dp)

试题算法提高合并石子资源限制时间限制：2.0s 内存限制：256.0MB问题描述　　在一条直线上有n堆石子，每堆有一定的数量，每次可以将两堆相邻的石子合并，合并后放在两堆的中间位置，合并的费用为两堆石子的总数。求把所有石子合并成一堆的最小花费。输入格式　　输入第一行包含一个整数n，表示石子的堆数。　　接下来一行，包含n个整数，按顺序给出每堆石子的大小。输出格式　　输出一个整数，表示合并的最小花费。样例输入51 2 3 4 5样例输出33数据规模和约定　　1<=

2021-05-25 23:31:42 306

原创试题算法提高第二点五个不高兴的小明(dp)

资源限制时间限制：1.0s 内存限制：256.0MB问题描述　　有一条长为n的走廊，小明站在走廊的一端，每次可以跳过不超过p格，每格都有一个权值wi。　　小明要从一端跳到另一端，不能回跳，正好跳t次，请问他跳过的方格的权值和最大是多少？输入格式　　输入的第一行包含两个整数n, p, t，表示走廊的长度，小明每次跳跃的最长距离和小明跳的次数。　　接下来n个整数，表示走廊每个位置的权值。输出格式　　输出一个整数。表示小明跳过的方格的权值和的最大值。样例输入8 5 33 4 -1 -1

2021-05-23 11:00:12 284

原创试题算法提高天天向上(dp)

试题算法提高天天向上资源限制时间限制：1.0s 内存限制：256.0MB问题描述　　A同学的学习成绩十分不稳定，于是老师对他说：“只要你连续4天成绩有进步，那我就奖励给你一朵小红花。”可是这对于A同学太困难了。于是，老师对他放宽了要求：“只要你有4天成绩是递增的，我就奖励你一朵小红花。”即只要对于第i、j、k、l四天，满足i<j<k<l并且对于成绩wi<wj<wk<wl，那么就可以得到一朵小红花的奖励。现让你求出，A同学可以得到多少朵小红花。输入格式　

2021-05-21 16:24:48 212

转载 B - Nikita and string（前缀和与后缀和使用）

最终形式一定是aba的串（而aba均可能为0），只需使得算出的b的前缀a和后缀a数量和，以及中间的b串长度最长转自https://www.cnblogs.com/HDMaxfun/p/9340012.html#include <bits/stdc++.h>using namespace std;typedef long long ll;const int MX = 5000 + 10;char str[MX];int f[MX], b[MX];int b_list[MX];

2021-04-27 21:16:52 135

原创优先队列实现最短路

一时间没找着最短路问题，仿照L2-4 深入虎穴 (25 分)的输入捏了一个#include <bits/stdc++.h>using namespace std;typedef long long ll;int main(){ int n; cin>>n; int a[n+1][n+1]; for(int i=1;i<=n;i++) { int m; cin>>m;

2021-04-24 10:08:14 212

转载 L2-018 多项式A除以B （25 分）(多项式除法)

这仍然是一道关于A/B的题，只不过A和B都换成了多项式。你需要计算两个多项式相除的商Q和余R，其中R的阶数必须小于B的阶数。输入格式：输入分两行，每行给出一个非零多项式，先给出A，再给出B。每行的格式如下：N e[1] c[1] … e[N] c[N]其中N是该多项式非零项的个数，e[i]是第i个非零项的指数，c[i]是第i个非零项的系数。各项按照指数递减的顺序给出，保证所有指数是各不相同的非负整数，所有系数是非零整数，所有整数在整型范围内。输出格式：分两行先后输出商和余，输出格式与输入格式相同

2021-04-22 20:54:10 321

原创 L3-1 Insertion or Heap Sort (25 分)(c++自带的堆排序使用)

According to Wikipedia:Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list. Each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, an

2021-04-22 20:25:23 102

原创 7-12 部落 (25 分)(并查集find与union)

7-12 部落 (25 分)在一个社区里，每个人都有自己的小圈子，还可能同时属于很多不同的朋友圈。我们认为朋友的朋友都算在一个部落里，于是要请你统计一下，在一个给定社区中，到底有多少个互不相交的部落？并且检查任意两个人是否属于同一个部落。输入格式：输入在第一行给出一个正整数N（≤104 ），是已知小圈子的个数。随后N行，每行按下列格式给出一个小圈子里的人：K P[1] P[2] ⋯ P[K]其中K是小圈子里的人数，P[i]（i=1,⋯,K）是小圈子里每个人的编号。这里所有人的编号从1开始

2021-04-20 21:09:30 157

转载 7-11 图着色问题 (25 分)(vector建图)

图着色问题是一个著名的NP完全问题。给定无向图G=(V,E)，问可否用K种颜色为V中的每一个顶点分配一种颜色，使得不会有两个相邻顶点具有同一种颜色？但本题并不是要你解决这个着色问题，而是对给定的一种颜色分配，请你判断这是否是图着色问题的一个解。输入格式：输入在第一行给出3个整数V（0<V≤500）、E（≥0）和K（0<K≤V），分别是无向图的顶点数、边数、以及颜色数。顶点和颜色都从1到V编号。随后E行，每行给出一条边的两个端点的编号。在图的信息给出之后，给出了一个正整数N（≤20），是待检

2021-04-20 20:46:47 157

原创简单超时問題

指思路简单，但直接写必然超时的问题。思路为：先考虑方法修改（如将多步骤合并或改变计算步骤简化），之后考虑特殊情况（计算中出现循环或可跳出的情况）。A - Sequence with Digits CodeForces - 1355ALet’s define the following recurrence:an+1=an+minDigit(an)⋅maxDigit(an).Here minDigit(x) and maxDigit(x) are the minimal and maximal d

2021-04-16 15:27:35 90

原创 D - Game With Array

Petya and Vasya are competing with each other in a new interesting game as they always do.At the beginning of the game Petya has to come up with an array of N positive integers. Sum of all elements in his array should be equal to S. Then Petya has to sele

2021-04-15 20:45:11 125

原创 C - Chain Reaction CodeForces - 608C

There are n beacons located at distinct positions on a number line. The i-th beacon has position ai and power level bi. When the i-th beacon is activated, it destroys all beacons to its left (direction of decreasing coordinates) within distance bi inclusiv

2021-04-13 20:26:56 136

转载【Codeforces 608B】Hamming Distance Sum(前缀和)

Hamming Distance SumDescriptionGenos needs your help. He was asked to solve the following programming problem by Saitama:The length of some string s is denoted |s|. The Hamming distance between two strings s and t of equal length is defined as , where s

2021-04-13 16:32:24 153

原创非连续递增序列

CodeForces - 606CAn infinitely long railway has a train consisting of n cars, numbered from 1 to n (the numbers of all the cars are distinct) and positioned in arbitrary order. David Blaine wants to sort the railway cars in the order of increasing numbers

2021-04-12 21:22:54 183

转载 B - Security Guards Gym - 101954B -BFS+预处理

B - Security Guards Gym - 101954B 题意：一个人找了很多保安来给他看护着一个最大可能为5000*5000的二维图，给出每个保安所在点。然后询问给出一些出事地点问到达出事地点的最近保安的距离。保安移动规则：change each of coordinates by 1, 0 or −1.思路：就是所有保安按照8个方向走，求每个点上最近的保安到达所需时间。普通BFS最初所有保安入队即可。#include<bits/stdc++.h>using n

2021-04-11 14:35:17 112

原创 Play on Words UVA - 10129

Some of the secret doors contain a very interesting word puzzle. The team of archaeologists has to solveit to open that doors. Because there is no other way to open the doors, the puzzle is very importantfor us.There is a large number of magnetic plates

2021-03-22 22:15:23 88

原创【Hdu2089】不要62(数位DP)

数位dp#include <bits/stdc++.h>using namespace std;typedef long long ll;const int maxn = 10;int dp[maxn][maxn];void init(){ memset(dp, 0, sizeof(dp)); dp[0][0] = 1; for (int i = 1; i < 7; i++) for (int j = 0; j < maxn; j

2021-03-20 19:05:23 79

原创试题算法训练 Yaroslav and Algorithm

问题描述　　（这道题的数据和SPJ已完工，尽情来虐吧！）Yaroslav喜欢算法。我们将描述一个他最喜欢的算法。1.这个算法接受一个字符串作为输入。我们设这个输入字符串为a。　　2.这个算法由一些命令组成。i号命令的形式为"s[i]>>w[i]“或"s[i]<>w[i]”，其中s[i]和w[i]是长度不超过7的字符串（可以为空），由数字或字符"?“组成。　　3.这个算法每次寻找一个编号最小的命令i，使得s[i]是a的子串。如果没有找到这样的命令，那么整个算法终止。　　4.

2021-03-20 09:50:52 72

转载最小圆覆盖

最小圆覆盖问题在一个平面上，给出 N 个点，求包围这些点的最小圆，输出圆心及半径。分析虽然可以用模拟退火或者三分套三分，这里只讲随机增量法，随机增量法是一种确定性算法，随机意义下均摊复杂度 O(n)，而且可以达到很高的精度（可达到 10−10 量级）有事实：如果点 p 不在集合 S 的最小圆覆盖内，则 p 一定在 S∪{p} 的最小圆覆盖上。易知，当 n 个点的分布随机时，因为三点定一圆，所以一个点不在圆上的概率为 3/i（也就外接圆上的3个点不在圆上）根据这个定理，我们可以分三次确定前 i

2021-03-14 10:38:13 306

原创 ACMB6

吃了次重定向的亏F - Folding Gym - 101142F折叠问题，只有当长大于等于目标长，宽大于等于目标宽时才成立，而折叠方式也有两种，长变长和长变宽，比较谁小即可#include <bits/stdc++.h>using namespace std;typedef long long ll;int main(){ freopen("folding.in","r",stdin); freopen("folding.out","w",stdout);

2020-11-25 12:44:28 138

原创 1031C - Cram Time

In a galaxy far, far away Lesha the student has just got to know that he has an exam in two days. As always, he hasn't attended any single class during the previous year, so he decided to spend the remaining time wisely.Lesha knows that today he can stud

2020-11-21 16:44:57 148 1

转载出栈合法性检测

题目Given a stack which can keep M numbers at most. Push N numbers in the order of 1, 2, 3, …, N and pop randomly. You are supposed to tell if a given sequence of numbers is a possible pop sequence of the stack. For example, if M is 5 and N is 7, we can obt

2020-11-17 15:37:50 132

原创 L2-011 玩转二叉树 (25分)

定一棵二叉树的中序遍历和前序遍历，请你先将树做个镜面反转，再输出反转后的层序遍历的序列。所谓镜面反转，是指将所有非叶结点的左右孩子对换。这里假设键值都是互不相等的正整数。输入格式：输入第一行给出一个正整数N（≤30），是二叉树中结点的个数。第二行给出其中序遍历序列。第三行给出其前序遍历序列。数字间以空格分隔。输出格式：在一行中输出该树反转后的层序遍历的序列。数字间以1个空格分隔，行首尾不得有多余空格。输入样例：71 2 3 4 5 6 74 1 3 2 6 5 7输出样例：4 6 1 7

2020-11-17 15:27:23 317

转载 PAT-A-1115-二叉搜索树最后两层的节点的个数的和

转自：https://blog.csdn.net/weixin_44701217/article/details/1057413353数组建树，利用v[]存储输入节点，l[],r[],分别存储下标对应的左右子树下标（均指v[]中的下标）#include<iostream>#include<algorithm>using namespace std;const int N = 1010;int n;int l[N], r[N], v[N], idx;int cn

2020-11-17 14:52:29 111

原创 7-1 关键活动 (30分)

7-1 关键活动 (30分)假定一个工程项目由一组子任务构成，子任务之间有的可以并行执行，有的必须在完成了其它一些子任务后才能执行。“任务调度”包括一组子任务、以及每个子任务可以执行所依赖的子任务集。比如完成一个专业的所有课程学习和毕业设计可以看成一个本科生要完成的一项工程，各门课程可以看成是子任务。有些课程可以同时开设，比如英语和C程序设计，它们没有必须先修哪门的约束；有些课程则不可以同时开设，因为它们有先后的依赖关系，比如C程序设计和数据结构两门课，必须先学习前者。但是需要注意的是，对一组子任务，

2020-11-02 21:48:21 1530

转载 7-2 关于堆的判断 (25分)

堆是一种数据结构，就是每个节点根据某种规则排序，从根节点往下都符合某种规律，根节点的值比所有节点的值都大，称为最大堆；根节点的值比所有节点的值都小，称为最小堆；将一系列给定数字顺序插入一个初始为空的小顶堆H[]。随后判断一系列相关命题是否为真。命题分下列几种：x is the root：x是根结点；x and y are siblings：x和y是兄弟结点；x is the parent of y：x是y的父结点；x is a child of y：x是y的一个子结点。输入格式：每组

2020-11-02 12:44:36 1214

转载 7-4 秀恩爱分得快 (25分)

古人云：秀恩爱，分得快。互联网上每天都有大量人发布大量照片，我们通过分析这些照片，可以分析人与人之间的亲密度。如果一张照片上出现了 K 个人，这些人两两间的亲密度就被定义为 1/K。任意两个人如果同时出现在若干张照片里，他们之间的亲密度就是所有这些同框照片对应的亲密度之和。下面给定一批照片，请你分析一对给定的情侣，看看他们分别有没有亲密度更高的异性朋友？输入格式：输入在第一行给出 2 个正整数：N（不超过1000，为总人数——简单起见，我们把所有人从 0 到 N-1 编号。为了区分性别，我们用编号前的

2020-10-28 23:10:08 1802

转载 L3-1 是否完全二叉搜索树 (30分)

将一系列给定数字顺序插入一个初始为空的二叉搜索树（定义为左子树键值大，右子树键值小），你需要判断最后的树是否一棵完全二叉树，并且给出其层序遍历的结果。输入格式：输入第一行给出一个不超过20的正整数N；第二行给出N个互不相同的正整数，其间以空格分隔。输出格式：将输入的N个正整数顺序插入一个初始为空的二叉搜索树。在第一行中输出结果树的层序遍历结果，数字间以1个空格分隔，行的首尾不得有多余空格。第二行输出YES，如果该树是完全二叉树；否则输出NO。输入样例1：938 45 42 24 58 30 6

2020-10-27 23:28:51 152

原创 L1-7 A-B (20分)

本题要求你计算A−B。不过麻烦的是，A和B都是字符串 —— 即从字符串A中把字符串B所包含的字符全删掉，剩下的字符组成的就是字符串A−B。输入格式：输入在2行中先后给出字符串A和B。两字符串的长度都不超过104 ，并且保证每个字符串都是由可见的ASCII码和空白字符组成，最后以换行符结束。输出格式：在一行中打印出A−B的结果字符串。输入样例：I love GPLT! It’s a fun game!aeiou输出样例：I lv GPLT! It’s fn gm!#incl

2020-10-23 20:15:11 385

转载 L2-1 红色警戒(dfs)

#include<bits/stdc++.h>using namespace std;const int maxn=505;//思路：把原来有几个连通量求出来，赋为1后有几个求出来，增加的话警告bool vis[maxn],v[maxn][maxn];int n;void dfs(int x){ vis[x]=true; for(int i=0;i<n;i++){ if(!vis[i]&&v[x][i]==true)

2020-10-21 20:46:15 91

转载 L1-3 敲笨钟 (20分)

L1-3 敲笨钟 (20分)微博上有个自称“大笨钟V”的家伙，每天敲钟催促码农们爱惜身体早点睡觉。为了增加敲钟的趣味性，还会糟改几句古诗词。其糟改的方法为：去网上搜寻压“ong”韵的古诗词，把句尾的三个字换成“敲笨钟”。例如唐代诗人李贺有名句曰：“寻章摘句老雕虫，晓月当帘挂玉弓”，其中“虫”（chong）和“弓”（gong）都压了“ong”韵。于是这句诗就被糟改为“寻章摘句老雕虫，晓月当帘敲笨钟”。现在给你一大堆古诗词句，要求你写个程序自动将压“ong”韵的句子糟改成“敲笨钟”。输入格式：输入首先在

2020-10-21 19:15:30 431

转载 L1-6 整除光棍 (20分)

这里所谓的“光棍”，并不是指单身汪啦~ 说的是全部由1组成的数字，比如1、11、111、1111等。传说任何一个光棍都能被一个不以5结尾的奇数整除。比如，111111就可以被13整除。现在，你的程序要读入一个整数x，这个整数一定是奇数并且不以5结尾。然后，经过计算，输出两个数字：第一个数字s，表示x乘以s是一个光棍，第二个数字n是这个光棍的位数。这样的解当然不是唯一的,题目要求你输出最小的解。提示：一个显然的办法是逐渐增加光棍的位数，直到可以整除x为止。但难点在于，s可能是个非常大的数 —— 比如，程序

2020-10-19 23:15:29 258

空空如也

空空如也