疫情在家期间颓废了n个月后，不知不觉就大三了，今天发现牛客可以建专栏了，就寻思把之前学到的一些算法知识之类的东西做个总结，希望记录一下学过的知识，看看自己几斤几两，也希望能留些有用的东西能帮到一些人吧。 关于更新，希望自己能严格遵守每天都更新吧，但是对自己的毅力还真没信心...加油吧，为了给自己的人生留点痕迹。

题意 游戏***有n名用户，编号从1到n，服务器共有m条服务线，每个用户最多只能登陆一条线，第i条线最多可以容纳v[i]名用户同时在线，且只能给编号在[l[i],r[i]]范围内的用户提供服务。现在希望找出一种合理的资源分配方案，使得同时在线人数最大化，请输出这个最大人数。 题解 看了一眼数据范围 < 1e4 ..贪心即可将当前用户分配给r更靠前的服务器，使用小根堆，遍历所有用户节点，若此节点恰好为某服务器的l值，则加入小根堆，若小根堆中服务器容量不够或r小于当前用户节点，弹出该服务器。 PS: vector动态resize范围会wa掉...不知道什么原因，还是太菜了QAQ code #...

题意 给出n*m的图，每个格点为1或0，1代表到此格点是一个障碍物.在可以移除t块障碍物的条件下。问所有互相可达的两点中，欧几里得距离最大的为多少。 题解 百度搜了一下原题数据范围才敢写....数据范围是<=30所以最多只有30*30=900个格点，可以求出每两点最少经过多少个障碍物后，枚举两点满足两点间障碍物<=t的最远距离。求解每两点间建筑物可以对相邻点建图使用最短路堆优化dijkstra复杂度为 code #include <bits/stdc++.h> #define reg register #define ll long long #define ull u...

A 题意 给出长度为n的数组，问是否可以经过不超过次交换相邻两值排序使该数组递增。 题解 我们知道冒泡排序的最坏情况复杂度即为，故只有在最坏情况下，即整个数组为严格递减序列时才能达到次交换，所以只需要判断数组是否严格递减即可。 code #include <bits/stdc++.h> using namespace std; int main() { int t; cin>>t; while(t--){ int n; cin>>n; int a[n+1]; for(int i = 0;i < n;++i){ cin>>a[i]; } in...

到10.10只有两周了呀...好快，咸鱼要冲一波啦 网络流...学了之后就没咋刷过题..以至于好多个月都给忘了，网络流24题...先写一半简单的好了 博弈...正式比赛博弈就没出过题就离谱，针对性搞一下，抄了份题单，有时间玩一玩博弈，刷个一半左右好了 HDU - 1079 HDU - 1525 HDU - 1564 HDU - 1846 HDU - 1847 HDU - 2516 HDU - 2897 HDU - 3032 HDU - 3389 HDU - 3537 HDU - 3544 HDU - 3863 HDU - 3951 HDU - 2188 HDU - 2149 HDU - 185...

题意 硬币购物一共有4种硬币。面值分别为c1,c2,c3,c4。某人去商店买东西，去了tot次。每次带di枚ci硬币，买si的价值的东西。请问每次有多少种付款方法。 题解 一眼看去一个多重背包dp...再一眼看去数据范围..1e5这样暴力背包就t了.可以转换想法，假设硬币的枚数没有限制，这样在每一组样例中，用不限制的总的数量减掉不满足条件的数量。而不限制硬币个数的数量就可以用多重背包求解即可  for(ll i = 0;i < 4;++i) for(ll j = 0;j < maxn;++j) if(j - c[i] >= 0) dp[j] += dp[j-c[i]]; 接下...

题意 牛牛可以在n*m的图中向右走或者向下走，每个点有一个权值，经过某点获得该点权值并对1e4+7求模，问从(1,1)走到(n,m)，在(n,m)点存在多少种权值情况。 题解 设一个dp三维布尔数组，dp[i][j][k]表示从(1,1)走到(i,j)点是否在(i,j)点可以产生k的权值。易知转移方程  即当前位置只能由上面一格或左面一格转移而来,且若想权值可以为k，则转移前的权值需要为 code #include <bits/stdc++.h> #define reg register #define ll long long #define ull unsigned long ...

题意 在树上存在n个点，每个点为两种状态之一，两种状态的点之间无法相互抵达，求树上最大的可联通子树，并按递增顺序输出所有节点，若有多棵子树最大，将所有子树节点均排序输出。 题解 对树进行dfs，每次求一颗子树大小，并将其所有节点标记，遍历过程记录子树个数与其所有节点，最后找到最大联通子树将所有最大子树的节点放到数组中排序输出 code #include <bits/stdc++.h> #define reg register #define ll long long #define ull unsigned long long #define pii pair<int,int...

题意 （啊好难总结复制了）去学校只有两种方式，坐公交车和步行，牛牛去学校是一条直线，这条直线上总共有n个车站，车站之间的距离都是相等的，每个车站只有一种公交车ai，每个公交车只在对应的公交站停车，第i种公交车过一站的时间需要ti，并且公交车是单向行驶，只能从左到到右，走路可以任意走，然而牛牛自己步行走一站需要的时间为T，恰好牛牛家和学校都在某一个站点，分别为s和t，问最少需要多少时间牛牛才能到学校？ 题解  建图，存在两种情况  通过步行到达，任意两点均可，但为了效率，仅对相邻两点填边（双向边）即可 通过公交车到达，对每个站点记录此站点公交车的上一站，若存在则填边（单向边）。建好图直接进行di...

题意 给出一个模板串和n个字符串，设每个字符串的权值为其字串中模板串前缀的长度，求n个字符串中最大权值和。 题解 前置知识:kmp使用kmp的next数组即可，在两串匹配过程中不断更新j指针能在模板串中到达的最远位置，即为能匹配的最长前缀。将n个字符串逐个匹配取最大值加和即可。 code #include <bits/stdc++.h> #define reg register #define ll long long #define ull unsigned long long #define pii pair<int,int> #define inf 0x3f3f3...

题意 题解 将a与b看为2进制数，根据按位与性质易知在a与b不为0的情况下，一定是大于等于的，只需要判断此数所剩的2进制位，是否均为a&b为0的2进制位。 code #include <bits/stdc++.h> #define reg register #define ll long long #define ull unsigned long long #define pii pair<int,int> #define inf 0x3f3f3f3f #define eps 1e-8 #define pi acos(-1.0) #define e exp(1...

题意 将字符串转换为对应权值，A-Z为1-26，若字母后面存在数字，则将前面字母或括号内权值乘以后面的数字注意多种特殊情况。 题解 （题解写着写着发现一组hack数据把自己昨天的代码hack了...这题数据有锅呀，hack数据 ABC5 答案应该是18）对左右括号，数字，字母进行分类讨论即可.将每对括号中的字符串当作一段，使用栈模拟递归..（或者不传参递归，传参字符串把内存传爆了）具体见注释。 code #include <bits/stdc++.h> #define reg register #define ll long long #define ull unsigned lo...

题意 在大小的棋盘中，对位置的棋子进行操作，向上1或2格，向左1或2格。最终无法移动棋子的人输。 题解 根据SG定理画出NP点的转移图 SG定理 P点(必胜点)：即处于此位置，在双方无失误情况下此方必胜N点(必败点)：即处于此位置，在双方无失误情况下此方必败转移：1.对于所有必胜点，一定存在至少一种情况在下一步进入必败点2.对于所有必败点，在所有情况下的下一步均进入必胜点。 本题的转移图如下：  在图中可看到，此图是关于左上-右下对角线对称的，所以只关注左下三角即可。发现当且仅当y与x坐标之差为3的倍数或0时，为必败点。 code #include <bits/stdc++.h> ...

题意 n面骰子，投m次，若每次均为n则牛牛赢，求牛牛输的概率。（读了半天的赢的概率，wa傻了都） 题解 直接对分母用费马小定理求逆元即可，概率为 code #include <bits/stdc++.h> #define reg register #define ll long long #define ull unsigned long long #define pii pair<int,int> #define inf 0x3f3f3f3f #define eps 1e-8 #define pi acos(-1.0) #define e exp(1.0) #defi...