- 博客(58)
- 收藏
- 关注
RSS订阅
原创 算法竞赛模板整理
算法竞赛模板整理基础算法快速排序快速排序#include<bits/stdc++.h>using namespace std;const int maxn = 1e6+5;void quick_sort(int a[],int l,int r){ if(l>=r) return; int x = a[l+r>>1], i...
2020-03-12 19:57:55
1073
原创 HDU 6796 X Number
HDU 6796 X Numberinput31 10 11 11 11 100 0output121数位DP+组合数学题意：找到[l,r]符合条件[=d]的数字。[=d]定义为:当前数字中d出现的次数严格最大。e.g.111223为[*=1]，112233为啥也不是思路：典型的数位dp虽然想到了，，，但没想到组合数学数位dp:dp[][][]三个维度分别表示当前还剩pos位，题意中的d，和一个长度为10的数组表示pos之前出现的每个数字的次数，这题不仅需要考虑limit还需
2020-07-31 00:31:01
461
原创 牛客竞赛-NC13230
区间DP思路：区间DP思路:如果我们用f[i][j][k][l]表示前一个串（a串）的第 i 个字符到第 j 个字符后一个串（b串）的第 k 个字符到第 l 个字符能否组成一个回文串的话，有四种可能，四种当中任意一种为真f[i][j][k][l]就是真。往 a[i+1] 到 a[j−1] 和 b[k] 到 b[l] 构成的串的两端加上 a[i] 和 a[j] 两个字符：f[i][j][k][l] |= (f[i+1][j-1][k][l] & (a[i] == a[j]));往 a[
2020-07-09 22:56:32
322
原创 牛客竞赛-NC50439
牛客竞赛-NC50439 每日一题3.25思路：如果没有每个士兵的人数限制，显而易见的我们会直接按照武力值大小排序，但是每个士兵对人数的加以了限制，如果我们还是按武力值大小加人的话，每次加人和删掉人都会导致队伍能容纳的人数的变化，而且还是跳跃的变化（完全有可能忽大忽小），更关键的是我们并不知道人数限制不满足了我们该删去谁——是删掉限制了我们人数的那个人扩充容量呢还是按现在的限制把多的人都删掉呢？但是想到这里，你应该能发现（也有可能你一开始就发现了），如果我们已知团队人数最多为k，那么我们的选择是可以
2020-07-09 19:14:27
617
原创 Gym 101606L-计算几何+dp
Lizard Lounge （计算几何+dp）感受到了stl+c++17的强大题目大意：起始点sx，sy还有n个其余的点x，y问以sx，sy为起点的射线中的点的最长上升子序列的个数正常代码写过去了，但感觉不太美观，就整理了下思路，之后就玩了一些好玩的东西思路：【斜率,与sx，sy的相对关系相同】同时满足时，在一条射线上，之后dis近的在前面，跑最长上升子序列即可map的key 维护的是 斜率为二元组pii，与相对关系opval为set集合，存放pii按照第一关键字dis排序看起来很舒服#i
2020-05-25 01:39:00
182
原创 int与long long效率问题
实验题ps：之前听过说long long的时间问题但是一直没有注意到过。直到遇见了他。。。。这是一个瞎搞题点这里思路：瞎搞证明：int快本着使劲优化的原则，，，加了4个优化。。但是在int数据类型其实这需要加2个多一点的优化就能过去。。。long long下需要加4个完整的优化才可以。优化1：质数ans=(1+n)/2优化2：因子只有2个质数组合优化3：因子只有3个质数组合优化4：因子只有4个质数组合每个优化都有对应的ans遍不需要暴力来处理。。。。但是在4种优化共同起作用时，in
2020-05-23 18:07:17
2228
1
原创 P1505 [国家集训队]旅游-树链剖分
P1505 [国家集训队]旅游-树链剖分码量惊人题意 如上思路1.板子2.边权转移到点权上,修改时不同链正常修改，相同链上if(x!=y) update(dfn[x]+1,dfn[y])。3.其余就是恶心的线段树了。十分恶心pushupvoid pushup(int o){ t[o].sum=t[ls].sum+t[rs].sum; t[o].max=max(t[ls].max,t[rs].max); t[o].min=min(t[ls].min,t[rs].mi
2020-05-21 20:54:01
168
原创 [NOI2015]软件包管理器 树链剖分
[NOI2015]软件包管理器 树链剖分在水一道题意 如上思路1.版子2.线段树区间覆盖pushupvoid pushup(int o){ t[o].sum=t[o<<1].sum+t[o<<1|1].sum;}pushdownvoid pushdown(int o){ if(t[o].lazy!=-1){ t[o<<1].lazy=t[o<<1|1].lazy=t[o].lazy; t[
2020-05-21 17:10:36
138
原创 VMware校园挑战赛E 树链剖分
小V和gcd树 树链剖分好题题意 如上题外话：1.树链剖分其实就是logn条链连接成，这条链满足头节点为轻儿子，之后均是重儿子相连。。。。1.轻-重-重-重-重-重-重 2.轻-重-重-重3.轻-重 这样的连在一起2.top[x]为轻儿子 ，也是重链头3.注意第二遍 为dfs2（1，1）思路：1.放入模板2.update 更改u->son[u] 与 u->fa[u] 的权值。3.query 时 记住top[x]为轻儿子，而轻儿子与father的权值肯定未被更改需要单独计算
2020-05-21 13:04:12
145
原创 tarjin求割点 割边
tarjin求割点int dfn[maxn],low[maxn];bool pc[maxn];//pc-割点void tarjin(int u,int fa){ static int cnt=0; dfn[u]=low[u]=++cnt; int sum=0; for(auto v:edge[u]){ if(v==fa) continue; if(!dfn[v]){ tarjin(v,u);
2020-05-19 23:10:33
116
原创 牛客练习赛63---牛牛的树行棋
牛牛的树行棋 （树形sg函数）题意如上思路：很好的一道树上博弈。。。首先需要看出来是sg博弈（并且知道sg博弈）知道之后 如果能猜到sg函数的表示就差不多啦，结论是：sg[x]=到达子树中最深的叶子节点的长度。那么怎么猜呢？？？叶子节点无法在向下延伸，sg=0.那么叶子节点的father只能向下延伸一步，合理的猜想过后sg=1。之后balabala就能得出 这个结论：结论是：sg[x]=到达子树中最深的叶子节点的长度。虽然我是看题解猜出来的之后就是应有的套路,sg异或和xorsum。如果x
2020-05-14 13:42:33
216
原创 动态中位数（对顶堆）
题意：动态求当前序列中的中位数思路：为了动态维护中位数，我们可以建立两个二叉堆：一个小跟堆、一个大根堆。在依次读入这个整数序列的过程中，设当前序列长度为M，我们始终保持：1.序列中从小到大排名为1-M/2的整数储存在大根堆中2.序列中从小到大排名为M/2-M的整数储存在小根堆中。任何时候，如果某一个堆中元素个数过多，打破了这个性质，就取出该堆的堆顶插入到另一个堆。这样一来，序列的中位数就...
2020-04-20 22:17:43
1110
原创 点分治 模板题
就明白了个模板题，先放个模板。多做一些题后在来整理下。#pragma GCC optimize(3,"Ofast","inline") //G++#include<bits/stdc++.h>#define mem(a,x) memset(a,x,sizeof(a))#define debug(x) cout << #x << ": " <...
2020-04-12 05:49:52
99
原创 坐标变换
坐标变换#include<bits/stdc++.h>using namespace std;#define fcout cout<<setprecision(0)<<fixedtypedef long long ll;typedef pair<ll,ll> pii;pii calc(int n,ll m){ if(n==0...
2020-04-09 22:48:36
316
原创 牛客OI周赛15-提高组 C回到过去
牛客OI周赛15-提高组 C回到过去双dp+2进制压缩题目描述n个物品，想要权值和为mm。当哪些种类的物品不选时，一定不能使权值和为mm。思路f[i][j]表示前i个物品权值和为j是否可行。g[i][j]表示后i个物品权值和为j是否可行。枚举不选的种类。然后将f数组和g数组合并一下即可。100%数据范围 做多只用450种物品，（因为权值和最大1e5+5）所以可以用类多重背包的二进制优...
2020-04-05 23:15:38
144
原创 牛客OI周赛15-提高组 A 环球旅行（树形dp）
牛客OI周赛15-提高组 A 环球旅行树形dp+树的直径题目大意:删除一条边后剩下的子树中树的直径最大值最小.求此最小值现场赛差点搞出来 ，呜呜呜思路：可证删除的这条边肯定在原树的直径上，两遍dfs确定树的直径的起点和终点，这样问题转化为删除一条边剩下的求俩个子树中直径的，可以两遍dfs分别从st，en开始ans[u][0]表示从st开始向下遍历后 如果u为断点的直径的最大值ans...
2020-04-04 23:42:41
219
1
原创 hdu4507（恨7不成妻）数位DP
hdu4507（恨7不成妻）数位DP+求平方和传送门题目大意:如果一个整数符合下面3个条件之一，那么我们就说这个整数和7有关—— 1、整数中某一位是7； 2、整数的每一位加起来的和是7的整数倍； 3、这个整数是7的整数倍；询问区间[l,r]不符合条件数字的立方和思路如果求询问区间[l,r]不符合条件数字的个数就是普通的数位dp，但此题需要维护立方和。所以开个结构体｛cn...
2020-03-21 15:44:07
268
原创 hdu4352 (数位dp+状态压缩)
HDU 4352 XHXJ’s LIS传送门题目描述：给定一个区间中，将区间的每一个数看成一个字符串，求这个区间内每个字符串的最大上升子序列等于k的个数。思路：dp[pos][sta][k]pos:搜索到第几位sta：之前的最长上升子序列的状态。k：就是输入的那个k牛逼的地方：sta储存为0-9每个数字的状态 类似最长上升子序列更新方式。sta二进制下1的个数就是当前最长上升...
2020-03-20 17:08:48
288
原创 有边数限制的最短路
bellman-ford算法有边数限制的最短路1.什么是bellman - ford算法？Bellman - ford算法是求含负权图的单源最短路径的一种算法，效率较低，代码难度较小。其原理为连续进行松弛，在每次松弛时把每条边都更新一下，若在n-1次松弛后还能更新，则说明图中有负环，因此无法得出结果，否则就完成。(通俗的来讲就是：假设1号点到n号点是可达的，每一个点同时向指向的方向出发，...
2020-03-12 19:48:54
588
原创 全排列Hash函数
/*全排列哈希这里要介绍一种变进制数，用来表示字符串的排列状态这种数的第i位逢i进一，第i位的位权是i!用d[i]来表示一个变进制数第i位上的数字一个n位变进制数的值就为∑[i:0~n-1] (d[i]×i!)*/int permutation_hash(string s, int n) //求长度为n的字符串某种排列的哈希值{ //n不能太大，通常不超过12，否...
2020-03-11 03:29:15
536
3
原创 2020牛客寒假算法基础集训营6-汉诺塔
2020牛客寒假算法基础集训营6-汉诺塔好题Dilworth定理U的链划分使用的最少集合数，等于它的最大反链长度。（1）U的反链划分使用的最少集合数，等于它的最大链长度。（2）#pragma GCC optimize(3,"Ofast","inline") //G++#include<bits/stdc++.h>#define TEST freopen("C:\\...
2020-03-07 23:34:46
193
原创 2020牛客寒假算法基础集训营6-导航系统
2020牛客寒假算法基础集训营6-导航系统好题想法很复杂，但是很好实现。。。最小生成树+prim#pragma GCC optimize(3,"Ofast","inline") //G++#include<bits/stdc++.h>#define TEST freopen("C:\\Users\\hp\\Desktop\\ACM\\in.txt","r",stdin...
2020-03-07 23:26:41
122
原创 2020牛客寒假算法基础集训营6-立方数
2020牛客寒假算法基础集训营6-立方数好题数学题—感觉优化时间复杂度的方式值得学一下这里三分的区间r应该=min(1000000ll,x)，当初写的x。。。wa傻了。还有真的卡常，oulasai（31622）最稳妥#pragma GCC optimize(3,"Ofast","inline") //G++#include<bits/stdc++.h>#defi...
2020-03-07 23:11:34
252
原创 2020牛客寒假算法基础集训营6-图
2020牛客寒假算法基础集训营6-图好题主要坑点在于有可能不是连通图。那么对于一个连通图来说，肯定是一个环+n条链，那么最大值就是链的长度+环的大小。所以可以先拓扑排序，把所有链都标记（剩下没有标记的点肯定在环上）。拓扑排序过程中dp存的值是dp【v】=max（dp【u】+1，dp【v】）表示该点最长延伸的长度（v有可能是环上的点这样ans=dp【v】+v所在环的长度-1）之后dfs没...
2020-03-07 23:07:34
215
原创 Codeforces Round #626 Div. 2
Codeforces Round #626 Div. 2补题A思路：水题#pragma GCC optimize(3,"Ofast","inline") //G++#include<bits/stdc++.h>#define TEST freopen("C:\\Users\\hp\\Desktop\\ACM\\in.txt","r",stdin);#define me...
2020-03-07 22:51:07
332
原创 牛客挑战赛37
牛客挑战赛37写在前面随机模数（香）__lg==log2 __lg返回整形下对2的对数，想当快。log2就会超时（真香）A牛牛与序列计数数学题==找规律（for me）#pragma GCC optimize(3,"Ofast","inline") //G++#include<bits/stdc++.h>#define TEST freopen("C:\\...
2020-03-07 22:38:46
230
原创 牛客小白月赛22
牛客小白月赛22水水水----放点稍微不水的A.操作序列模拟+stl看着题意打就行，主要输入恶心，所以上榜了#pragma GCC optimize(3,"Ofast","inline") //G++#include<bits/stdc++.h>#define TEST freopen("C:\\Users\\hp\\Desktop\\ACM\\in.txt","r...
2020-03-07 22:29:42
133
原创 树的直径
树的直径【定义】我们将一棵树T = ( V，E )的直径定义为maxδ ( u，v ) ( u，v ∈ V )，也就是说，树中所有最短路径距离的最大值即为树的直径。poj1985-添加链接描述【做法】做法1：2遍DFS先从任意一点P出发，找离它最远的点Q，再从点Q出发，找离它最远的点W，W到Q的距离就是是的直径。DFS从当前节点出发到达最远的点第一次DFS返回的point肯定是直径...
2020-03-07 21:35:57
174
原创 A + B问题
新学期开始，打算复习下之前学的东西，先从最简单的A+B开始。A+B题目描述输入两个整数，求这两个整数的和是多少。样例样例输入：3 4样例输出： 7算法一青铜版本#include <iostream>#include <cstdio>using namespace std;int a,b;int main(){ cin>>...
2020-03-05 15:19:20
634
2
原创 高精度模板
高精度模板题目描述:输出n+（n-1）/（m-1）直接上代码最好写的Time=88s包含 高精+高精. 高精-高精 高精*高精 高精/低精 且重载cin,cout,比较运算符#include<iostream>#include<cstring>#include<cstdlib>#include<cstdio>#define ...
2020-02-09 18:51:42
204
3
原创 Second My Problem First 单调队列
Second My Problem First 单调队列暑假训练第一天题目：Give you three integers n, A and B.Then we define S i = A i mod B and T i = Min{ S k | i-A <= k <= i, k >= 1}Your task is to calculate the product ...
2020-01-28 22:22:42
140
原创 HDU - 4126 Genghis Khan the Conqueror
HDU - 4126 Genghis Khan the Conqueror树形dp+MST题目描述Genghis Khan(成吉思汗)(1162-1227), also known by his birth name Temujin(铁木真) and temple name Taizu(元太祖), was the founder of the Mongol Empire and the gr...
2020-01-28 22:17:27
371
原创 Qin Shi Huang's National Road System HDU - 4081
Qin Shi Huang’s National Road System （HDU - 4081）次小生成树的思想题目描述During the Warring States Period of ancient China(476 BC to 221 BC), there were seven kingdoms in China ---- they were Qi, Chu, Yan, Han...
2020-01-27 23:12:12
186
原创 HDU - 1811 Rank of Tetris （并查集+拓扑排序）
HDU - 1811 Rank of Tetris题目描述自从Lele开发了Rating系统，他的Tetris事业更是如虎添翼，不久他遍把这个游戏推向了全球。为了更好的符合那些爱好者的喜好，Lele又想了一个新点子：他将制作一个全球Tetris高手排行榜，定时更新，名堂要比福布斯富豪榜还响。关于如何排名，这个不用说都知道是根据Rating从高到低来排，如果两个人具有相同的Rating，那就按...
2020-01-24 18:02:06
148
原创 牛客小白月赛21(模拟汉诺塔)
牛客小白月赛21(模拟汉诺塔)—B Bits题目连接题目描述Nancy喜欢做游戏！汉诺塔是一个神奇的游戏，神奇在哪里呢？给出3根柱子，最开始时n个盘子按照大小被置于最左的柱子。如果盘子数为偶数，则需要将她们全部移动到最右侧的柱子上，否则将她们移动到中间的柱子上。那么，Nancy该怎样移动呢？请你输出汉诺塔游戏的过程叭！输入描述:共一行：一个整数n，表示最开始n个盘子（编号为1到n...
2020-01-20 03:38:23
354
原创 Good Bye 2019补题记录
Good Bye 2019补题记录A. Card Game题目描述Two players decided to play one interesting card game.There is a deck of n cards, with values from 1 to n. The values of cards are pairwise different (this means t...
2020-01-14 14:07:54
542
1
原创 Codeforces Round #612 (Div. 2)补题记录
Codeforces Round #612 (Div. 2)补题记录A Angry Students题目描述It’s a walking tour day in SIS.Winter, so t groups of students are visiting Torzhok. Streets of Torzhok are so narrow that students have to go ...
2020-01-12 12:34:33
873
原创 CF-1237D(Balanced Playlist)
CF-1237D(Balanced Playlist)好题题目描述Your favorite music streaming platform has formed a perfectly balanced playlist exclusively for you. The playlist consists of n tracks numbered from 1 to n. The p...
2019-10-18 14:30:05
361
原创 2019网络赛
2019徐州网络赛补题**A**待补B并查集 删除x就是把x的爹变成x+1，查找祖先即可，hash_map可搞#include<bits/stdc++.h>#include <ext/hash_map> //hashmap#include <functional>#define TEST freopen("C:\\Users\\hp\\De...
2019-09-25 23:37:13
211
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人