- 博客(301)
- 资源 (1)
- 收藏
- 关注
RSS订阅
原创 【Fahaxiki！】的训练实录
2020国庆集训：2020-10-01：3/11 2018-2019 ICPC Northwestern European Regional Programming Contest (NWERC 2018)2020-10-02：5/13 2019-2020 ACM-ICPC Latin American Regional Programming Contest2020-09实验室考核：2020-09-16：1/13 2020-9-16 ACM contest实验室集训：2020-08-11： 4
2020-10-02 20:17:38
759
1
原创 专题整理——动态规划
知识点整理基础DP（一）——硬币问题基础DP（二）——0/1背包基础DP（三）——最长公共子序列LCS基础DP（四）——最长递增子序列LIS递推与记忆化搜索区间DP树形DP题目练习题目题解类型...
2020-08-14 22:39:32
227
原创 专题整理——图论
知识点整理最短路问题Floyd算法Bellman-Ford算法SPFA算法Dijkstra算法Floyd最小环最小生成树Prim算法Kruskal算法题目练习题目题解类型HDU 1596 find the safest road题解Floyd（水）HDU1874 畅通工程续题解Floyd（水）HDU2544 最短路题解Floyd（水）HDU1548 A strange lift题解Floyd（水）HDU 1598 find
2020-07-29 09:15:19
531
原创 Dijkstra算法图解
最短路径问题从图中的某个顶点出发到达另外一个顶点的所经过的边的权重和最小的一条路径，称为最短路径。Djikstra算法算法特点：Dijkstra算法适用于计算正权图（边权为正）上的单源最短路，即从单个源点出发，到所有节点的最短路。该算法同时适用于有向图和无向图。算法思路：从已确定最短路径的节点Vi出发，找到其中权值最小的边，如果原点到Vi的权值和加Vi到Vj的权值小于已知原点到Vj的权值和，则将原点到Vi的权值和加Vi到Vj的权值作为原点到Vj的最小权和。（讲的有点不是特别清楚，看图分析）
2020-07-04 12:40:35
2705
原创 Ubuntu修改用户前缀
当你点进这篇文章的时候，就已经说明你有改前缀的需求了，所以我也不必再赘述为什么需要改了。如果你只想要一个简短的前缀，这里是最简单粗暴的办法打开终端，键入vim .bashrc进入之后键入i成为编辑状态一直移动到文件末，在最后面添加一行export PS1='Username: '(注：单引号内部修改成你想要的名字即可)按esc键然后键入:wq即可保存并退出回来发现刚改好的名字还未生...
2021-03-24 20:30:00
692
原创 Fib-tree【树分治】
题目链接题意： 判断一棵树是否为斐波那契树。判定条件：树中的节点数量为斐波那契数。切断某条边，可拆成两棵斐波那契树 || 树中只有一个节点题解： 判断一棵树是不是斐波那契树，要看它是否能拆成两棵斐波那契树，而那两棵拆分出来的也需要通过相同的手段去进行判定。直至节点数量为1，就可以判断是一棵斐波那契树。拆什么边其实是没有讲究的，因为理论上需要逐步拆成n棵节点数为1的树，所以每条边都是需要拆的。#include<bits/stdc++.h>using namespace std;
2021-03-05 15:38:29
241
原创 2021 HZNU Winter Training Day 17 (2018 German Collegiate Programming Contest (GCPC 18))
2021 HZNU Winter Training Day 17 (2018 German Collegiate Programming Contest (GCPC 18))题目ABCDEFGHIJKLMsolved????-✔✔✔✔--✔---⚪✔：比赛时通过；????：赛后通过；⚪：比赛时尝试了未通过；-：比赛时未尝试...
2021-02-21 21:55:02
320
原创 HDU 5834 Magic boy Bi Luo with his excited tree【树形DP⭐】
Magic boy Bi Luo with his excited tree题意： 在一棵既有边权又有点权的(无向)树上，要求求从每个节点出发能获得的最大权值。每经过某条边，都要花费相对应的边权。重复经过将重复花费。到达某个点，可以获得相对应的点权。只能获得一次。题解：题目中强调边权重复花费的时候就应该明白一点，为了得到最大权值，是需要走多条路才会走某些路往返走了两遍。一、什么路可能会走多遍？某条支路，走过去走回来，获得点权，扣去两次边权，仍有收益。二、什么路需要走多...
2021-02-18 14:08:35
108
原创 POJ 3162 Walking Race【树形DP + 线段树】
Walking Race题意： 题意大致是，nnn天，第iii天点iii出发，跑到距离iii点最远的点，记录距离。求最大的连续天数，使得其中的最大距离−最小距离<m最大距离-最小距离<m最大距离−最小距离<m题解： 树形DP求解每个点的最远距离，然后线段树求区间最大最小值即可。#include<iostream>#include<algorithm>#include<cstring>#include<cmath>u...
2021-02-16 12:27:14
146
原创 POJ 3140 Contestants Division【树形DP】
Contestants Division题意： 一棵有点权的树，求删除某条边之后，两棵子树的权值差最小。题解： 虽然题目没有很直白地说是一棵树 但是由题意可得确实是一棵树。随便找一点开始DFS，记录以每个节点为根的子树的权值和dp[i]。然后找到最小的sum - dp[i] - dp[i]即可。#include<iostream>#include<algorithm>#include<cstring>#include<cmath>u...
2021-02-15 17:42:33
75
原创 POJ 2378 Tree Cutting【树的重心】
Tree Cutting题意： 求树的重心。题解： 模板题，略。#include<iostream>#include<algorithm>#include<cstring>#include<vector>using namespace std;const int maxn = 1e4 + 10;int n;int sz[maxn];int dp[maxn];vector<int> out;int cnt,...
2021-02-15 16:51:23
110
原创 POJ 3107 Godfather【树的重心】
Godfather题意： 求树的重心。题解：sz[i]记录以节点i为根节点的子树的节点个数dp[i]记录以连接节点i的节点为根节点的子树的节点个数dp最小的就是重心#include<iostream>#include<algorithm>using namespace std;const int maxn = 5e4 + 10;int n;int sz[maxn];int dp[maxn];int cnt, head[maxn];st...
2021-02-15 16:22:50
92
原创 CodeForces 219D Choosing Capital for Treeland【树形DP】
D. Choosing Capital for Treeland题意： 一棵有向边的树，找到一点，使得从这个点出发到所有的节点的逆边最少。求最小逆边个数和所有最小逆边的根节点。题解：虽然题意是有向边，但还是得建无向边。但是需要附上权值，正边权值为0，逆边权值为1。【权值反过来也无所谓】清楚一个地推关系。如果两个节点是u−>vu->vu−>v的关系，并且以u为根节点有xxx条逆边，那么以v为根节点则应该有x+1x+1x+1条逆边。反之，如果两个节点是u−>vu...
2021-02-15 11:30:06
100
原创 HDU 3721 Building Roads【树的中心 + 树形DP】
Building Roads题意： 移动一条边，求最小的树的直径。题解： 枚举每一条边，求删除改变之后的两棵树A、B。答案无外乎三种情况：直径完全在树A中直径完全在树B中直径贯穿了两棵树【对于这种，求出两棵树的中心，连接两树的中心，直径自然穿过】#include<bits/stdc++.h>using namespace std;const int maxn = 3e3 + 10;const int inf = 0x3f3f3f3f;int _T, n;...
2021-02-10 20:26:22
126
原创 树形相关
文章目录对【树】的大概认识树的定义树的种类相关术语二叉树的遍历【树形相关】的回顾线段树最小生成树最近公共祖先今天的学习树上差分【差分】与【前缀和】树上差分对【树】的大概认识树的定义【百度百科上是这样说的】 树，木本植物之总名，主要由根、干、枝、叶、花、果组成。 树是一种数据结构，它是由n(n>=1)n(n>=1)n(n>=1)个有限结点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：每个结点有零个
2021-02-10 18:05:07
130
原创 树上差分模板
基于LCA的模板点的差分如果题目要求对节点uuu到节点vvv的路径上所有点的权值+1+1+1.则：w[u]++, w[v]++, w[lca{u,v}]--, w[fa[lca{u,v}]]--;边的差分如果题目要求对节点uuu到节点vvv的路径上所有边的权值+1+1+1，则：w[u]++, w[v]++, w[lca{u,v}] -= 2;...
2021-02-02 16:42:05
115
原创 线段树模板
#include<bits/stdc++.h>using namespace std;typedef long long ll;const int maxn = 1e5 + 10;#define lrt rt << 1#define rrt rt << 1 | 1int n, m;int a[maxn];struct node { int l, r; ll sum, lazy; int mid () { return l + r >>
2021-02-01 21:32:23
70
原创 LCA 模板
在线倍增#include<bits/stdc++.h>using namespace std;const int maxn = 5e5 + 10;int n, m, s;struct lca { int cnt, head[maxn]; struct edge { int to, next; } e[maxn << 1]; void add (int u, int v) { e[++cnt] = {v, head[u]}; head[u] = cnt; e[
2021-02-01 21:08:31
252
原创 Codeforces Round #697 (Div. 3)
Codeforces Round #697 (Div. 3)A. Odd Divisor题意： 判断一个数是否能被一个大于111的奇数整除#include<bits/stdc++.h>using namespace std;#define endl "\n"#define pii pair<int, int>#define fi first#define se second#define pb push_back#define _for(i,a,n) for
2021-01-27 20:27:27
110
原创 kuangbin专题七 线段树
kuangbin专题1. 敌兵布阵 HDU - 1166难度： ★【究极入门题，纯当是检验本子】题意： 中文题面，不再赘述题解： 参考线段树&树状数组算法，有板子就是直接AC。因为是回头刚整理线段树，所以搞了个不一定全面当时非常长的模板，凑合着用#include<bits/stdc++.h>using namespace std;const int inf = 0x3f3f3f3f;const int maxn = 1e5 + 10;#define lrt rt &
2021-01-27 11:19:00
173
原创 Codeforces Round #696 (Div. 2) Solved: 3 out of 6
Codeforces Round #696 (Div. 2)A. Puzzle From the Future题意： 已知一串长度为nnn并且只由010101组成的数，要求构造一串长度相同同样由010101构成的的数字，使得两数相加的和最大，并且相邻两位数不能相同。#include<bits/stdc++.h>using namespace std;#define endl "\n"#define _for(i,a,n) for (int i = (a); i < (n)
2021-01-26 20:20:43
643
1
原创 Codeforces Round #693 (Div. 3) Solved: 4 out of 7
Codeforces Round #693 (Div. 3)A. Cards for Friends题意： 已知一张纸的长宽若为偶数，则可对折，每次对着层数∗2*2∗2，求能否对着到目标层数。#include<bits/stdc++.h>using namespace std;#define endl "\n"inline int read() { int s = 0, w = 1; char ch = getchar(); while(ch < '0'
2021-01-25 10:33:16
83
原创 kuangbin 专题一 简单搜索
kuangbin专题1. 棋盘问题 POJ - 1321难度： ★题意： 一个棋盘上‘#'的位置表示可以放置棋子，要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列。问你在n∗nn*nn∗n的棋盘上拜访kkk个棋子有多少种不同的方案。题解： 爆搜。每次只在某一行上放置一个棋子，并对放置的列进行标记。dfs进入下一行，可以选择在未标记的列放一颗棋子或直接进入下下一行。一直递归到放置棋子满足kkk个时对方案总数+1+1+1.#include<iostream>#include<
2021-01-23 20:13:12
223
1
原创 Codeforces Round #695 (Div. 2) Solved: 4 out of 5
Codeforces Round #695 (Div. 2)A. Wizard of Orz题意： 有个长度为n初始状态下各元素均为0的数组，每过一秒数组中所有元素都会+1，如果是9则会变成0，即0-9不断循环。现在你能够在开始后的任意时间点选取任意一个位置，改位置上的数字立刻停止增加，与其距离为x的位置上的元素则在x秒后暂停（这x秒内还是数字会继续增加）。给定你长度n，求出由n个元素构成的最大数字（包含前导零）。题解： 为了使得到的数最大，很容易会想到987654···，wa一发之后你就会 深入想
2021-01-22 16:37:03
89
原创 Codeforces Round #694 (Div. 2) Solved: 3 out of 6
Codeforces Round #694 (Div. 2)A. Strange Partition题意： 给定含nnn个元素的数组aaa和一个整数xxx，你可以将数组中任意相邻数组合并，试让你求出所有【ai/xa_i/xai/x（向上取整）的和的】最大值与最小值。题解： 因为除数是向上取整的，因此不合并求所有除数的和即为最大值，全部合并求除数即为最小值。#include<bits/stdc++.h>using namespace std;#define endl '\n'#
2021-01-21 22:53:33
95
原创 缺省源模板
#include<bits/stdc++.h>using namespace std;#define endl "\n"#define fi first#define se second#define max(a,b) ((a) > (b) ? (a) : (b))#define min(a,b) ((a) < (b) ? (a) : (b))#define _for(i,a,n) for (int i = (a); i < (n); ++i)#define
2021-01-12 23:12:50
427
原创 2019 ICPC Asia Shanghai Regional Contest
2019 ICPC Asia Shanghai Regional Contest题目ABCDEFGHIJKLMsolved-✔-⚪????--????--✔--✔：比赛时通过；????：赛后通过；⚪：比赛时尝试了未通过；-：比赛时未尝试
2020-12-18 19:27:18
221
原创 2020 ACM-ICPC, Asia Shanghai Regional
2020 ACM-ICPC, Asia Shanghai Regional题目ABCDEFGHIJKLMsolved-✔-⚪--✔-----✔✔：比赛时通过；????：赛后通过；⚪：比赛时尝试了未通过；-：比赛时未尝试
2020-12-16 19:47:45
566
1
原创 HDU 2732 Leapin‘ Lizards【最大流（Dinic + 拆点）】
Leapin’ Lizards题意： 给定一个n∗mn * mn∗m的图【nnn已知，m需要读入一行之后自己算】，第一个n∗mn*mn∗m的矩阵表示图中中的柱子情况【0表示没有柱子，其他数字表示这个柱子可以承受跳跃的次数】，第二个n∗mn*mn∗m的矩阵表示图中蜥蜴的站位，LLL表示该柱子上有一只蜥蜴。 游戏规则为：每只蜥蜴的最大跳跃距离为ddd【曼哈顿距离】，每次只能跳到一根柱子上，或者直接跳出图外表示安全，而每次离开的那根柱子则会减少一次可承受的跳跃次数。问最少有多少只蜥蜴不能安全离...
2020-12-12 12:32:33
126
1
原创 2018 ICPC Jiaozuo F. Honeycomb【恐怖输入 + BFS⭐】
题意： 【巨恶心的输入】按图形给出一个蜂巢，要求计算从SSS点到TTT点最少需要访问多少个点。题解： 【不脑抽写个优先队列就轻松过了Orz】。输入虽然有点恐怖，但是根据规律我们可以自行给每个点进行编号【我的编号规则为：第一列从上到下编号[1,r][1,r][1,r]， 第二列从上到下编号[r+1,2r][r+1,2r][r+1,2r]】。然后就是去计算每个蜂窝的中心点【S、TS、TS、T在蜂窝中心】、三条边【一个蜂窝有六条边，但是为了较少重复计数，选择其中三边即可】的位置。如果某条边为空，则对两边的蜂窝
2020-12-11 10:51:04
124
原创 2019 JUST Programming Contest
2019 JUST Programming Contest题目ABCDEFGHIJKLsolved-✔✔✔✔✔✔✔✔✔⚪⚪✔：比赛时通过；????：赛后通过；⚪：比赛时尝试了未通过；-：比赛时未尝试
2020-12-03 19:09:58
253
原创 2016 ACM-ICPC CHINA-Final shanghai
2016-2017 ACM-ICPC CHINA-Final题目ABCDEFGHIJKLsolved✔--⚪⚪------✔✔：比赛时通过；????：赛后通过；⚪：比赛时尝试了未通过；-：比赛时未尝试REPLY开什么题什么题不会，感觉需要停下来好好学一下了。...
2020-11-29 17:08:28
486
1
原创 2020 ECNU Campus Online Invitational Contest
2020 ECNU Campus Online Invitational Contest题目ABCDEFGHIsolved✔---????????--✔✔：比赛时通过；????：赛后通过；⚪：比赛时尝试了未通过；-：比赛时未尝试
2020-11-29 14:07:15
419
原创 2020 ECNU Campus Online Invitational Contest E. Even Degree【欧拉回路＜DFS输出路径+构造＞】
E. Even Degree题意： 给定一个无向图，题目保证没有重边，也没有孤立点，并且每一个节点都有偶数条边。要求每次只能从偶点上删除一条边。求最多可以删除多少条边，并按照删除顺序输出每条删除边的编号。题解： 犹豫题目保证的所有点都是偶点，所以纸上随便找几个图画一下就知道肯定可以将一个连通图删剩下一条边。然后问题就来到了删边的顺序。回顾一下最普通的输出欧拉回路的代码：关键在于先递归，后输出。这个代码的正确性我就不加证明了，不理解的可以自己百度。void euler (int u) ...
2020-11-25 21:40:16
256
原创 2019 ACM-ICPC, Asia Nanjing Regional
2019 ICPC Asia Nanjing Regional题目ABCDEFGHIJKsolved✔-✔----✔--✔✔：比赛时通过；????：赛后通过；⚪：比赛时尝试了未通过；-：比赛时未尝试
2020-11-25 19:37:23
187
原创 POJ1287 Networking【最小生成树水题】
Networking题意： 在一个n点m边的无向图中，求最小生成树的权值和题解： 模板题，Prim算法注意一下重边就好模板参考：Prim算法、Kruskal算法Prim#include<algorithm>#include<iostream>#include<cstring>using namespace std;#define _for(i, a, b) for(int i = (a); i <= (b); ++i)const int N
2020-11-24 07:40:13
99
原创 2019 ICPC Asia Nanjing Regional C. Digital Path【DFS】
C. Digital Path题意： 在一个n∗mn * mn∗m的图中，求所有连续的差值为1的极大序列【长度至少为4】的总数。题解： 题面太长了很迟才开题，但其实是一道不算难的搜索。要求差值为1，即从序列中的最小值开始搜索，通过dfs记录所有路径的数目。TLE。 不加处理的暴搜的结果。 需要记忆化搜索，记录下某些点某些路径的dp值，减少一些重复的搜索。对于序列长度至少为4的要求，即用一个三维的数组dp[x][y][i]去表示坐标(x, y)的点后续长度为i的序列个数（dp[x][y...
2020-11-23 18:08:31
138
原创 次小生成树模板
#include<iostream>#include<algorithm>#include<cstring>using namespace std;#define _for(i, a, b) for(int i = (a); i <= (b); ++i)const int inf = 0x3f3f3f3f;const int N = 110;int n, m;int lowc[N], pre[N];int G[N][N], Max[N][N];
2020-11-22 10:17:34
72
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人