- 博客(29)
- 收藏
- 关注
RSS订阅原创 hdu5834 Magic boy Bi Luo with his excited tree
hdu5834 Magic boy Bi Luo with his excited tree题意：一棵树，每个点有点权，边有边权，从一点出发，遍历树，每次遍历到一条边就减去边权，第一次遍历到一个点就加上点权（后续不加）。问从所有点出发能得到最大价值。刚碰这题认为这题和洛谷的Kamp很像，都是点权一次（点权可以设置为0），边权多次。但是洛谷的kamp是给定了遍历到哪些点，而这题是所有点都可以被遍历到。这也就导致了，Kamp解题思路中的边权值*2加上最长边的“最长边”这一个信息很难在这题中被维护。
2021-08-24 15:48:59
134
原创 Codeforces Round #699 (Div. 2)(A-D题解)
C,D虽然思路很容易，但是代码实现要一点细节。其余都很简单。A. Space Navigation题目链接：点击此处因为可以随意删除，所以只要知道单独上下左右最远到哪就行。#include<iostream>#include<vector>#include<cstring>#include<algorithm>#include<cmath>#include<iomanip>#include<stdio.h&g
2021-02-18 23:07:12
138
原创 Educational Codeforces Round 103 (Rated for Div. 2)（A-D题解）
比赛没打，后续补的，本场A-D还是很简单的，没有多大思维性，感觉比较吃DP。A. K-divisible Sum题目链接：点击此处只要追求平均就行。#include<iostream>#include<vector>#include<cstring>#include<algorithm>#include<cmath>#include<iomanip>#include<stdio.h>#include&
2021-02-18 22:41:59
132
原创 数位DP入门题目
数位DP通常是用来求解给你一个[l,r][l,r][l,r]区间，求这个区间满足一定条件的数的个数。1.Bomb题目链接：点击此处题意：求[1,n][1,n][1,n]中含49的个数数位DP往往用一个数组来记录nnn中每一个位的值，这边用digit[i]digit[i]digit[i]表示从个位到最高位的第iii位为多少。比如1234，则digit[1]=4,digit[2]=3,digit[3]=2,digit[4]=1digit[1]=4,digit[2]=3,digit[3]=2,digit
2021-01-28 17:31:31
161
原创 Codeforces Round #697 (Div. 3)A-G题解
A. Odd Divisor题目链接：点击此处每个大于等于2的整数都可以划分为质数的积，然后质数只有2是偶数。所以我们对于一个数除完2，看看是否为1，为1就NO，大于1就是YES。#include<iostream>#include<vector>#include<cstring>#include<algorithm>#include<cmath>#include<iomanip>#include<stdio.
2021-01-26 17:52:02
130
原创 Educational Codeforces Round 101 (Rated for Div. 2)A-D题解
A. Regular Bracket Sequence题目链接：点击此处题目给你问号和一对左右括号，看能否成功匹配。这边给了一般情况的答案，即不限于左右括号的数目的情况的代码。主要是先将问号全变为左括号，之后从右向左将括号变为右括号。#include<iostream>#include<vector>#include<cstring>#include<algorithm>#include<cmath>#include<iom
2021-01-24 20:40:20
85
原创 Codeforces Round #694 (Div. 2)A-D题解
A. Strange Partition题目链接：点击此处思路很简单，因为一个数取余有剩下，那么对于求最小值是赚的，对于求最大值是亏的。所以求最小值就是各个值除后求和，求最大值是求和再除。#include<iostream>#include<vector>#include<cstring>#include<algorithm>#include<cmath>#include<iomanip>#include<std
2021-01-24 01:06:44
154
原创 Codeforces Round #696 (Div. 2)A-D题解
D题是后续补出来的。A. Puzzle From the Future题目链接：点击此处这题贪心，对于一个字符加1，如果和前面不同，就输出1，相同输出0，再用一个pre记录前一个值就行。#include<iostream>#include<vector>#include<cstring>#include<algorithm>#include<cmath>#include<iomanip>#include<std
2021-01-22 14:41:42
116
原创 Codeforces Round #695 (Div. 2)A-D题解
Codeforces Round #695 (Div. 2)A-D这一场比赛的题的难度别cf其他的div2的要难多了。可能是自己好久没打，菜了。所以写一下这篇题解，记录一下自己的思考过程。A. Wizard of Orz题目链接：点击此处这一题难点在在长度为找哪个作为起始点，很明显，n==1n==1n==1的时候，选第一个在第9秒，n==2n==2n==2,选第二个在第8秒，n==3n==3n==3时选第二个在第8秒，后续也一样，之后自己推一下就可以出来。#include<iostream
2021-01-20 21:39:08
187
原创 CodeForcesD题记录
D. Glass Half Spilled题目链接：https://codeforces.com/contest/1459/problem/D本题的意思就是给你nnn个杯子的容量a[i]a[i]a[i]和存有的水的量b[i]b[i]b[i]，每个被子里的水都可以转到其他杯子去，但是每次都要损失b[i]2\frac{b[i]}{2}2b[i]，问我们从nnn个杯子中取得kkk个杯子，这些杯子中最多有多少水。假设nnn个杯子的容量有SaS_aSa,水有SbS_bSb，kkk个杯子有容量SakS_{a
2021-01-01 19:32:12
470
原创 动态规划——背包九讲
以前写过一篇相应的文章，那时候很多都不理解，很多思路都是乱的，今天自己看了一下那篇，准备再补一下背包九讲的内容，算是自己复习一下了。01背包为何01背包的体积可以倒序呢？因为我们01背包如果二维正序的话，其实dp[i][j]=max(dp[i−1][j−v[i]]+w[i],dp[i][j])dp[i][j]=max(dp[i-1][j-v[i]]+w[i],dp[i][j])dp[i][j]=max(dp[i−1][j−v[i]]+w[i],dp[i][j])其中的dp[i−1][j−v[i]]dp
2020-12-18 20:56:12
189
原创 新生模拟赛-拯救贺老头
这是一个简单的思维题题意给你一个 l 和 n ，表示从l开始的长度为n的连续整数，删去偶数位置的数后，用剩下的数组成一个新串，再继续操作。不妨给你 l = 5，n =5得到的一串整数是 5 6 7 8 9我们第一次删除并重新排列后 剩下 5 7 9然后再次操作为 5 9再次操作为 5只剩下一个数的时候就没有偶数位置的数了所以输出5当n = 0时，表示长度为0，就没有整数，所以输出-1下面是代码实现：#include <iostream>using namespace s.
2020-10-11 10:57:03
121
1
原创 hdu5920 Ugly Problem
#include<iostream>#include<cmath>#include<string.h>#include<algorithm>#include<iomanip>#include<cstring>#include<map>#include<vector>#include<queue>#include <cctype>#include<function.
2020-10-10 22:44:33
60
原创 二分图最大权值完美匹配 hdu2255
hdu2255#include<iostream>#include<cmath>#include<algorithm>#include<iomanip>#include<cstring>#include<map>#include<vector>#include<queue>#include <cctype>#include<functional>#include&
2020-09-21 17:25:40
95
原创 洛谷线段树题解
P3372 【模板】线段树 1#include<iostream>#include<cmath>#include<algorithm>#include<iomanip>#include<cstring>#include<map>#include<vector>#include<queue>#include<functional>#include<memory.h>
2020-09-02 21:27:51
289
原创 洛谷图论进阶
P1363 幻想迷宫#include<iostream>#include<cmath>#include<algorithm>#include<iomanip>#include<string.h>#include<map>#include<vector>#include<queue>#include<functional>#include<memory.h>#incl
2020-08-19 12:55:11
290
原创 C数学基础专题
数学专题数学是程序竞赛中常见的题目，并且很容易和其他题目一起出，作为基础，还是得尽快掌握。高精度计算洛谷P1601 A+B高精度#include <iostream>#include <cstdio>#include <cstdlib>#include <cstring>#include <vector>#include <list>#include <map>#include <set>
2020-08-12 17:55:46
793
原创 线段树基础
线段树基础简单题hdu1166 敌兵布阵标准线段树。对于query中第二行的if为何成立，给个解释。就是left和right表示我们访问的区间，l和r表示我们需要访问的区间，如果访问的区间在我们需要访问的区间内，就直接返回访问区间的值。hdu1698 Just a Hook区间修改模板题，区间修改比单点修改麻烦点，不过理清思路就行。hdu1754 I Hate It线段树找最大值。max自定义不然可能超时。hdu2795 Billboard按照高度分配，初始值为w，线段树记录最
2020-08-05 23:57:03
322
1
原创 图论的基础 小白笔录
图论图的遍历与连通性+图的存储（邻接矩阵）洛谷 图的遍历很基础的一个遍历，不过好像不能用正序找最大值，会爆内存，要用倒序，比如点1到点4，那么我们从4遍历，只要与4联通的都是4最大拓扑排序最大食物链计数dfs，这题是求从最弱动物到最强动物的路劲数，而不是深度。所以可以bfs，dfs求我这里用dfshdu1285 确定比赛名次bfs+优先队列这个方法不需要判重，只要注意输出格式就行，为何不用判重，给一组数据为 1 2，2 3，2 3，4 3，其中2到3式重边，但是不碍事，虽然这代
2020-08-01 14:56:23
772
原创 字符串进阶 小白笔录
做完一部分字符串题后，对字符串的很多操作有了一点眉头，所以现在准备写一篇字符串进阶，参考《算法竞赛从入门到进阶》的题目流程，把字符串题从头刷到尾。字符串进阶（从入门到入坑）字符串的基本操作poj3981-字符串替换gets函数（也可以是gets_s函数）读取一行，存入char数组，一个个暴力。2.getchar（）读取一个字符EOF表示ctrl+z，终止循环3.getline（）+find+replace函数getline读取一行，包括空格，是对cin无法处理空格的改进find（）找
2020-07-24 12:01:28
196
原创 AcWing 字符串专题题解
38-外观数列几个几，向下计算，由于数据小，直接dfs就行49-字母异位词分组其实就是模拟分类，分类的操作，map和set可以胜任。难点就是如何模拟，比如如何开拓vector的大小。151-翻转字符串里的单词两次反转，第一次整体反转，第二次局部反转，只有注意空格什么时候加，以及最后删除多余空格就行。165-比较版本号对每一个字符都分为是不是‘ . ’,，如果是，那么每次判断的条件更新，再对不是的，只要注意把前导零去点，其他存进数组，最后一个个比较。最长回文子串看到回文，最
2020-07-21 10:50:02
220
原创 AcWing+力扣 树结构题解
101-对称二叉树要保证对称，从2边同时向下同步寻找值104-二叉树的最大深度先看这个点是不是叶节点，如果是的话，那么比较最大值，不是的话继续深搜145-二叉树的后序遍历这题的题解还是比较详细的，主要要弄懂递归的思路是什么，以及nullptr要在什么时候插入，为何插入进行了解。先了解先序递归的套路，再想后序递归会简单很多。105-从前序与中序遍历中构建二叉树这里的bulidtree中参数传了TreeNode*&root，表示引用，我们在这个函数可以修改root，如果不引用，
2020-07-17 14:09:28
559
原创 Acwing dfs+回溯专题题解
17-电话号码的字母组合其实就是map那个感觉有点麻烦，其他还行46-全排列next_permutation函数，产生所有的下一个组合，所以要先升序排序，保证能有所有下一组合全排列IInext_permutation就是返回不重复的，所以可以继续使用...
2020-07-14 16:20:19
289
原创 AcWing哈希表专题题目题解
哈希表基础560-和为k的子数组这个一看就知道先求前缀和，但是我们求完后，我们要遍历前缀和数组，然后再遍历前面的前缀和，观察相减是否为k，为k，+1，复杂度nlogn哈希表定义前缀和数组sum我们知道连续数组和为k得到的方法是sum[i]-sum[j-1]=k,i必须再j后面，所以我们转换式子，sum[j-1]=sum[i]-k,前面的那个sum[j-1]求过了，我们循环到i的时候，sum[i]和k都是确定了,所以我们就是找前面i-1个前缀和中有几个sum[j-1]，map映射就可以，个人认为m
2020-07-11 00:06:53
267
原创 背包九讲复习（队列求多重背包暂时未解出 ）
动态规划（背包九讲复习）视频建议（b站里大佬大雪菜的背包九讲）题库acwing01背包问题经典代码：f[i][j]表示选i个物品，总体积小于j的最大价值状态转移，这个表示我们不选第i个物品表示我们选第i个物品，但要保证我选的物品的体积要小于我们背包的剩余体积01背包优化（1维数组优化）这里的等式左边dp[j]是现在要求的dp[i][j]，但是我们j从大到小循环，使得后面的dp[j]和dp[j-v[i]]都是第i-1次的值，都还没被更新过，所以max左边表示我不选第i个物品，右边表示我
2020-07-09 13:36:09
105
原创 区间DP（3）字符串类型进阶
下面是我这个初学者花了将近一天研究出来的题，对于字符串类型终于算是入门了看下这题，题目在POJ-2955上，自己找。题目意思我就不介绍了，比经典字符串多了比较和一些特殊情况经典字符串比较，比如回文字符串的话，aba最长长度为3，abab最长为3但是对于这题最长长度为对于 [ ( ] 这种情况，最长长度是2，[ ] [ ] 最长是4这边就体现了不同与经典字符串的不同下面我们就来介绍不同的时候哪些是相同的相同部分，即回文类模板，不同部分，新增判断条件对于这种问题，都似乎要形成对称
2020-07-04 21:52:32
187
原创 三角枚举基础
区间DP（2）–三角剖分题目如下You are given a regular polygon with nn vertices labeled from 11 to nn in counter-clockwise order. The triangulation of a given polygon is a set of triangles such that each vertex of each triangle is a vertex of the initial polygon, there
2020-07-04 19:36:05
228
原创 区间DP（多类石子合并问题）
区间DP（石子合并I，石子合并II，石子合并II改良，式子合并1进阶）石子合并I设有N堆石子排成一排，其编号为1，2，3，…，N。每堆石子有一定的质量，可以用一个整数来描述，现在要将这N堆石子合并成为一堆。每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻，合并时由于选择的顺序不同，合并的总代价也不相同。例如有4堆石子分别为 1 3 5 2， 我们可以先合并1、2堆，代价为4，得到4 5 2， 又合并 1，2堆，代价为9，得到9 2 ，再合并得到11
2020-07-04 12:35:43
408
原创 并查集基础中的基础（包括优化，适合初学者）
并查集基础1.并查集是一种使用的数据结构，主要处理一些不相交集合的合并问题。经典的例题有连通子图，最小生成树Kruskal算法和最近公共祖先等问题。2.听上去还是有点高端的，但是在书上有个例子，帮派，可以很好的解释并查集。例：假如1，2是朋友，1，3是朋友，那么通过并查集处理，1，2，3是朋友，然后分析完后，题目会问，有几队朋友，或者这队朋友有几人等等。3.当然，还有一些进阶题，会把并查集和一些STL容器组合，具体的在力扣上的并查集问题上有体现。现在我们讲一下并查集基础，即模板，以及它的优化方法。
2020-07-03 00:25:08
189
1
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人