Cosmic_Tree-CSDN博客

原创 Codeforces Beta Round #68 - B- Train ( 贪心模拟 )

题目链接：点击进入题目题意偷渡者和控制者玩以下游戏。火车由 n 节车厢表示，车厢从头到尾用 1 到 n 的正整数编号。偷渡者和控制者最初在两辆不同的货车中。火车每分钟都可能处于两种状态移动或空闲。控制者每分钟都在移动。控制器有运动方向——火车头或火车尾。在移动期间，控制者对应于其移动方向移动到相邻的货车。如果在他的移动结束时，控制者进入第 1 辆或第 n 辆货车，那么他将移动方向更改为另一侧。换句话说，控制者在整个游戏过程中循环地从火车的头部到尾部然后再返回，在每次移动期间移动一辆车。请注意，

2022-01-14 18:12:41 517 1

原创 Codeforces Round #171 (Div. 2) - E - Beautiful Decomposition（贪心）

题目链接：点击进入题目题意给你一串值为 n 的二进制串，一个加数可以是 ( + / - ) 2 ^ k ( k >= 0 ) ，求最少的加数凑成 n （没有前导零）思路若这个串只有一个1，显然只需要一次即可；否则，我们可以用减法来求得这个数，例如：11010 = 100000 + 00010 - 01000反过来就是 11010 - 00010 + 01000 = 100000 ，也就是用最小的加数使原数(x位)变成2^x（若原数是11…就是变成2 ^ x，若原数是10…就是变成

2022-01-14 14:47:13 347

原创 Codeforces Round #764 (Div. 3) - G - MinOr Tree ( 贪心 )

题目连接：点击进入题目题意n 个点 m 条边，求最小或 ( or ) 生成树，即树的所有边或值最小。思路由于是求最后所有边或的值最小，或值即对于生成树的所有边来说，他们的每个对应位只要有一个 1 那么这位最终就是 1 ，要是想结果尽可能小，那么我们当然是希望每个对应位都是 0 才好，如果无法为 0 ，那么这一位越低越好，因此我们可以从高位往低位枚举每一位，如果这一位全 0 的边能够凑成一棵生成树，那么这一位为 1 的边就可以不要，那么最终结果的这一位就可以为 0 。要是凑不成，那么说明需要

2022-01-13 16:13:53 386

原创 Educational Codeforces Round 32 - G. Xor-MST ( 01字典树 + 分治 )

题目链接：点击进入题目题意给你 n 个点的值，n 个点加边生成一棵树，边权就是两点的异或值，要求最后所有边权和最小。输出最小边权和。思路将 n 个数插入到01字典树上，对于树上的每个节点，记录这个节点保存有原数组的那些数（就是原数组中有哪些数经过这个节点），因为这些数可能在原数组中是无序的所以不好保存，因此我们可以将原数组排序后再插入字典树，这样每个节点所保存的数就是连续的，也就是每个节点只记录这个连续区间的边界即可。遍历01字典树，对于两个孩子的节点，左右孩子代表的区间是不同的，代表未连接

2022-01-12 16:21:07 403

原创计算机算法设计与分析第七章思维导图&&知识点总结 ( 初稿 )

复习链接思维导图没有思维导图，单纯为了格式整齐好看哈哈哈(～￣▽￣)～知识点总结

2021-12-30 15:37:05 1184

原创计算机算法设计与分析第六章思维导图&&知识点总结 ( 初稿 )

思维导图分支限界法的概念分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。分支限界法的算法框架（1）队列式（FIFO）分支限界法将活结点表组织成一个队

2021-12-08 16:43:58 748 2

原创计算机算法设计与分析第五章思维导图&&知识点总结 ( 初稿 )

思维导图回溯法的概念回溯法（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。回溯法解题的算法框架回溯算法的两种形式（1）递归（2）迭代解空间的组织形式（1）子集树：当所给问题是从n个元素的集合S中找出满足某种性质的子集时，相应的解空间为子集树（2）排列树：当所给问题是确定n个元素满足某种性质的排列时，相

2021-12-08 16:43:33 1541

原创随笔 -（二叉树）

二叉搜索树的操作集BinTree Insert( BinTree BST, ElementType X ){ if(BST==NULL) { BST=(BinTree)malloc(sizeof(BinTree)); BST->Data=X; BST->Left=NULL; BST->Right=NULL; } else { if(X>BST->Data) BST->Right=Insert(BST->Right,X);

2021-11-24 17:45:20 87

原创 PAT甲级 - 1155 Heap Paths (30 分) ( 完全二叉树 + dfs )

题目链接：题目题意思路代码#include<iostream>#include<map>#include<vector>#include<cstring>using namespace std;const int maxn=1e5+10;int n,a[1010],flag;vector<int>v,path[1010];void dfs(int p){ if(p*2>n) { v.push_back

2021-11-24 17:34:48 103

原创 PAT甲级-1154 Vertex Coloring (25 分) ( set + 枚举 / dfs )

题目链接：点击进入题目题意思路代码1#include<iostream>#include<map>#include<set>#include<cstring>using namespace std;const int maxn=1e5+10;int n,m,k,a[maxn];struct node{ int x; int y;}p[maxn];set<int>s;int main( ){ cin&gt

2021-11-24 17:34:20 112

原创 P1226 【模板】快速幂||取余运算

题目链接：点击进入题目思路快速幂模板代码// Problem: P1226 【模板】快速幂||取余运算// Contest: Luogu// URL: https://www.luogu.com.cn/problem/P1226// Memory Limit: 128 MB// Time Limit: 1000 ms// // Powered by CP Editor (https://cpeditor.org)#include<iostream>#define i

2021-11-24 17:33:39 130

原创 P3390 【模板】矩阵快速幂

题目链接：点击进入题目思路矩阵快速幂模板代码// Problem: P3390 【模板】矩阵快速幂// Contest: Luogu// URL: https://www.luogu.com.cn/problem/P3390// Memory Limit: 125 MB// Time Limit: 1000 ms// // Powered by CP Editor (https://cpeditor.org)#include<iostream>#include&lt

2021-11-24 17:32:02 98

原创 Gym - 103069B - Rectangle Flip 2（暴力 + 思维）

题目链接：点击进入题目题意n * m 的网格，每秒删除其中一个小网格，问每秒后，还剩余多少个好的矩形 ( 只要是矩形，同时矩形内没有被删除的格子 )思路蚌埠住啦，这题因为万恶的javaweb被我搁置了好久，我老早就想写了，难受≧ ﹏ ≦按照顺序删除点，对于每个删除的点，看会影响多少新矩形。思考一下(脑袋里构一下图)，一个新删除的点，能影响到的，只能是以这个点x为中轴，上下每行左右扩到最大的部分(最大就是指碰到被删除的点，或者边界)，这个上下每行也是在x轴上上下扩到最大的。我们若是确定每行能扩

2021-11-22 17:17:26 655

原创计算机算法设计与分析第四章思维导图&&知识点总结

思维导图贪心算法的概念贪心算法的基本要素（1）贪心选择性质贪心选择性质是指，所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。（2）最优子结构性质贪心算法与动态规划的差异贪心算法的一般理论贪心算法的应用范例活动安排问题最优装载问题哈夫曼编码单源最短路径最小生成树多机调度问题...

2021-11-15 21:18:30 1518

原创计算机算法设计与分析第三章思维导图&&知识点总结

思维导图动态规划算法的概念动态规划是运筹学的一个分支，是求解决决策过程最优化的过程。动态规划算法与分治法类似，其基本思想是将待求解问题分解成若干子问题，先求解子问题，再结合这些子问题的解得到原问题的解。与分治法不同的是，适合用动态规划法求解的问题经分解得到的子问题往往不是互相独立的。若用分治法来解决这类问题，则分解得到的子问题数目太多，以致最后解决原问题需要耗费指数级时间。动态规划算法的基本要素##（1）最优子结构性质问题的最优解包含了子问题的最优解##（2）重叠子问题性质子问题空间要比原问

2021-10-30 18:38:40 1098 8

原创 HDU-7134-Public Transport System ( 最短路 + 拆点 )

题目连接：点击进入题目题意待补思路还是看官方题解吧，懒~~~代码//#pragma GCC optimize(3)//O3//#pragma GCC optimize(2)//O2#include<iostream>#include<string>#include<map>#include<set>//#include<unordered_map>#include<queue>#include&lt

2021-10-13 21:33:04 254 3

原创计算机算法设计与分析第二章思维导图&&知识点总结

递归的概念直接或间接地调用自身的算法成为递归算法。用函数自身给出定义的函数成为递归函数递归实例阶乘函数P11Fibonacci数列P12Ackerman函数P12排列问题P13整数划分问题P13汉诺塔问题P14分治法的基本思想将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地解决这些子问题，然后将各子问题合并得到原问题的解。分治范例二分搜索技术基本思想：将n个元素分成个数大致相同的两半，取a[n/2]与x作比较。如果x=a[n/2]，则找到x

2021-10-07 19:28:34 2110 4

原创 Gym - 103055J - Grammy and Jewelry ( dijkstra + 完全背包 )

题目链接：点击进入题目题意存在一个有 n 个顶点和 m 条边的连通无向图。顶点的索引范围为 1 到 n 。在顶点 i（ 2 <= i <=n ）中有无限的珠宝，每个都有价值的 ai 。从第 1 点开始。通过每一个边消耗1 个单位的时间。她可以在顶点 i 捡起一件珠宝，然后放回顶点 1 。捡起和放下一件珠宝可以立即完成。此外，她在任何时候最多可以携带 1 件珠宝。当她在顶点 1 放下一件价值为 x 的珠宝时，她得到了它的价值。现在，对于 1 和 T （包括 T ）之间的每一个 k ，

2021-09-21 21:54:36 489

原创 PAT甲级 - 1153 Decode Registration Card of PAT (25 分) ( 排序 + unordered_map )

题目链接：点击进入题目题意思路代码//#pragma GCC optimize(3)//O3//#pragma GCC optimize(2)//O2#include<iostream>#include<string>#include<map>#include<set>#include<unordered_map>#include<queue>#include<cstdio>#include&lt

2021-09-21 21:54:22 128

原创 PAT甲级 - 1152 Google Recruitment (20 分) ( 素数判断 + substr函数 )

题目链接：点击进入题目题意思路代码//#pragma GCC optimize(3)//O3//#pragma GCC optimize(2)//O2#include<iostream>#include<string>#include<map>#include<set>//#include<unordered_map>#include<queue>#include<cstdio>#include&

2021-09-21 21:54:07 157

原创 PAT甲级-1148 Werewolf - Simple Version (20 分)(枚举)

题目链接：点击进入题目题意思路代码//#pragma GCC optimize(3)//O3//#pragma GCC optimize(2)//O2#include<iostream>#include<string>#include<map>#include<set>//#include<unordered_map>#include<queue>#include<cstdio>#include&

2021-09-21 21:53:52 199

原创 P3128 [USACO15DEC]Max Flow P ( 树上差分 )

题目链接：点击进入题目思路学习链接树上差分应用：多次对树上的一段路径点权 ( 或者边权 ) 加减 x ，最后询问某个点 ( 或边 ) 权。前置知识：LCA，差分点权加：u , v 路径上所有点权加 x ，pos = lca ( u , v ) ,fa = pre [ pos ] [ 0 ] 为 pos 父亲节点diff [ u ] += x ,diff [ v ] += x ,diff [ pos ] -= x ,diff [ fa ] -= x ;边权加：u , v 路径上所有边

2021-09-21 21:53:18 218

原创 P3379 -【模板】最近公共祖先（LCA）

题目链接：点击进入题目思路倍增求lca（最近公共祖先）代码#include<iostream>#include<string>#include<map>#include<set>//#include<unordered_map>#include<queue>#include<cstdio>#include<vector>#include<cstring>#inclu

2021-09-21 21:52:57 207

原创 P3378 【模板】堆 ( 手写 / stl )

题目链接：点击进入题目思路 ( 手写堆 )手写最小堆。插入 x ：将 x 插入到最后一个节点处，将 x 不断与它的父节点比较，x 比父节点小就 swap 上浮一下，继续比较，否则就 break 结束。删除：删掉第一个点，将最后一个节点 x 放在第一个节点上，节点数-- ，然后将 x 不断与它的两个孩子中小的那个比较，x 比小的孩子大就 swap 下沉一下，继续比较，否则 break 结束输出最小值：第一个节点 ( 堆顶 ) 的值就是最小值。代码 ( 手写堆 )// Problem: P3

2021-09-21 21:52:40 256

原创 P4779 【模板】单源最短路径（标准版）（ dijkstra ）

题目链接：点击进入题目思路dijkstra代码// Problem: P4779 【模板】单源最短路径（标准版）// Contest: Luogu// URL: https://www.luogu.com.cn/problem/P4779// Memory Limit: 125 MB// Time Limit: 1000 ms// // Powered by CP Editor (https://cpeditor.org)//#pragma GCC optimize(3)//O

2021-09-21 21:52:17 141

原创 P3371 【模板】单源最短路径（弱化版）( spfa )

题目链接：点击进入题目思路spfa代码// Problem: P3371 【模板】单源最短路径（弱化版）// Contest: Luogu// URL: https://www.luogu.com.cn/problem/P3371// Memory Limit: 125 MB// Time Limit: 1000 ms// // Powered by CP Editor (https://cpeditor.org)//#pragma GCC optimize(3)//O3//

2021-09-21 21:51:59 135

原创计算机算法设计与分析第一章思维导图

复习链接计算机算法设计与分析第一章思维导图计算机算法设计与分析第二章思维导图&&知识点总结计算机算法设计与分析第三章思维导图&&知识点总结计算机算法设计与分析第四章思维导图&&知识点总结计算机算法设计与分析第五章思维导图&&知识点总结 ( 初稿 )计算机算法设计与分析第六章思维导图&&知识点总结 ( 初稿 )思维导图...

2021-09-21 21:16:56 1118 3

原创 2021牛客暑期多校训练营6 - F - Hamburger Steak（构造）

题目链接：点击进入题目题意n 个汉堡，m 个锅，每个汉堡都有做熟所需时间 tit_iti，一个汉堡可以在一个锅上做，也可以分两次在两个锅上做，一个锅每刻只能做一个汉堡，一个汉堡每刻只能在一个锅上。求一个汉堡放置方案，使所有汉堡做好所需时间最少（这个所需时间，应该是所有汉堡都做完的那一刻时间）思路代码...

2021-08-31 19:37:02 129 2

原创 Gym - 102001H Lexical Sign Sequence（树状数组 + 构造）

题目链接：点击进入题目题意思路代码#include<bits/stdc++.h>#define pii pair<int,int>#define lowbit(x) x & -xusing namespace std;const int maxn=1e6+10;int n,k,p[maxn],flag,c[maxn],vk[maxn];bool vis[maxn];set<int>st;struct node{ int a; in

2021-08-31 19:36:11 159

原创 Gym - 102483G Game Design（思维 + 模拟）

题目链接：点击进入题目题意思路代码#include<bits/stdc++.h>#define pii pair<int,int>using namespace std;const int maxn=1e6+10; const int base=1001;int pos[maxn];string s;vector<pii>v;void print(int x,int y){ cout<<(-x)<<" "<&

2021-08-31 19:35:38 431

原创 POJ - 3461 Oulipo（ kmp ）

题目链接：点击进入题目题意求模式串在文本串中出现多少次思路单模式串匹配 - > kmp代码// Problem: Oulipo// Contest: Virtual Judge - POJ// URL: https://vjudge.net/problem/POJ-3461// Memory Limit: 65 MB// Time Limit: 1000 ms// // Powered by CP Editor (https://cpeditor.org)//#pra

2021-08-31 19:35:10 127

原创 CodeForces - 1562D2 Two Hundred Twenty One (hard version)（前缀和 + 构造 + 二分）

题目链接：点击进入题目题意长度为 n 的字符串，’+’ 表示 1 ，‘-’ 表示 -1 。q 次询问区间，每次问最少移除多少个字母以及被移除的位置。可以使区间内电荷为 0 。电荷的计算相当于对区间 [ l , r ] 排序，然后求 a[1]−a[2]+a[3]−a[4]+...+(−1)r−l∗a[r−l+1]=0a [ 1 ] - a [ 2 ] + a [ 3 ] - a [ 4 ] + ...+ ( -1 )^{r-l}* a [ r - l + 1 ] = 0a[1]−a[2]+

2021-08-31 19:34:47 132

原创 Codeforces Round #741 (Div. 2) D1. Two Hundred Twenty One (easy version) ( 前缀和 + 构造 )

题目链接：点击进入题目题意长度为 n 的字符串，’+’ 表示 1 ，‘-’ 表示 -1 。q 次询问区间，每次问最少移除多少个字母可以使区间内电荷为 0 。电荷的计算相当于对区间 [ l , r ] 排序，然后求 a[1]−a[2]+a[3]−a[4]+...+(−1)r−l∗a[r−l+1]=0a [ 1 ] - a [ 2 ] + a [ 3 ] - a [ 4 ] + ...+ ( -1 )^{r-l}* a [ r - l + 1 ] = 0a[1]−a[2]+a[3]−a[4]+.

2021-08-31 19:34:30 150

原创 Codeforces Round #741 (Div. 2) C - Rings ( 构造 )

题目链接：点击进入题目题意长度为 n 的 01 字符串，找两个不同的子串，t1 = s [ l1 , r1 ] ，t2 = s [ l2 , r2 ] ,满足 t1 二进制转换的数字 = t2 二进制转换的数字 * k ( k >= 0 整数 )，同时两个子串的长度都大于等于 n / 2思路由 k 可以等于 0 ，我们大概可以知道，若存在一个长度 = n / 2 的全 0 连续子串，那么让 t1 等于这个子串，t2 取 s ，就满足条件。若 s 全1，那么存在一个长度 = n / 2

2021-08-31 19:34:14 156 2

原创 CodeForces - 1561E Bottom-Tier Reversals ( 构造 )

题目链接：点击进入题目题意长度为 n 的排列 ( n 为奇数 ) ，每次操作可以选择将长度为 p 的前缀翻转 ( p 为奇数 ) ，问能不能在 5n / 2 次操作内，将序列变为递增的。若能，按顺序输出每次操作的前缀长度，若不能，输出 -1 。思路简单思考一下，翻转操作，不会改变一个数位置的奇偶性。由于序列最后一定是一个1-n的递增序列，那么最终奇数一定在奇数位置，偶数一定在偶数位置。因此，可以通过判断初始序列每个数及其位置的奇偶性是否相同，但凡有一个奇偶性不同，就说明不行，也就是-1。若是

2021-08-31 18:14:39 134

原创 CodeForces - 1561D2 Up the Strip ( dp + 前缀和 )

题目链接：点击进入题目题意思路与此题类似，但是 n 变为了4e6，O(nn)O(n\sqrt{n})O(nn) 不可过代码

2021-08-31 18:14:28 187

原创 CodeForces - 1561D1 Up the Strip (simplified version) ( dp + 整除分块 + 前缀和 )

题目链接：点击进入题目题意n 个台阶，问从 n 到 1 有多少种方案。若是位于 x ，则有两种操作：1、通过减法到达 [ 1 , x - 1 ]2、通过除法到达 ⌊xz⌋⌊ \frac{x}{z} ⌋⌊zx⌋ ( 下取整 , z 取值 [ 2 , x ] )思路dp [ i ] : 表示从 n 到 i 的方案数。倒序遍历 i ：对于减法，记录一个前缀和 sum ，这个前缀和代表着，i 之前的位置 x 通过减法一步到达 i 的总方案数，sum=∑x=i+1ndp[x]sum=\sum_

2021-08-31 18:14:14 202

原创 CodeForces - 852G Bathroom terminal （字典树 + dfs ）

题目链接：点击进入题目题意给 n 个匹配串，m 此询问，每次询问给出一个模式串，问模式串能匹配几个匹配串。? 万能匹配符，也可以当作空白。思路将 n 个匹配串插入到字典树中，对于每次询问去字典树上搜索查找，对于？的部分，分别将其当作 ’ a ’ - ’ e ’ 以及空白来处理。代码// Problem: Bathroom terminal// Contest: Virtual Judge - CodeForces// URL: https://vjudge.net/proble

2021-08-26 00:27:29 156

原创 CodeForces - 432D Prefixes and Suffixes ( kmp + dp )

题目链接：点击进入题目题意对所有，长度为 i 的，且存在一个长度为 i 的后缀与它相等的，这样一个前缀，输出长度以及出现次数。思路next 数组的应用，对于每个位置 i ，通过 next [ i ] ，可以知道长度为 next [ i ] 前缀在中间出现一次，因此可以倒序 dp 计算每个前缀出现的次数，然后通过 l = next [ l ] ( l 初始值 len )，遍历所有存在相等后缀的前缀。dp [ next [ i ] ] += dp [ i ] ( dp 初始值 1 , 因为前缀

2021-08-26 00:27:19 219

原创 CodeForces - 948DPerfect Security （ 01字典树）

题目链接：点击进入题目题意O [ i ] xor Π（ p [ i ] ）= a [ i ] ， Π（ p [ i ] ）代表对 p 序列的重新排序后 p [ i ] 的下标，给你 p , a 序列，让你求字典序最小的 O 序列思路O [ i ] xor Π（ p [ i ] ）= a [ i ] =》O [ i ] = a [ i ] xor Π（ p [ i ] ）让 O [ i ] 尽可能小，就是让 a [ i ] 异或一个 p 值越小越好，那么就顺序遍历每一位，对于

2021-08-26 00:27:08 115

空空如也

空空如也