- 博客(52)
- 资源 (2)
- 收藏
- 关注
RSS订阅原创 C - Rencontre Gym - 102798C题解：
题目链接：C - Rencontre Gym - 102798C参考题解：这份题解用的是直接计算边用啦多少次的方式思路：三个人独立选择，那么按照树上分别计算距离即可，然后最后将总距离除以方案数，就是每两个人的期望距离。一共使用啦三种做法，归根到底是一道树形dp的题目，是一道换根dp的模板题，然后因为需要一些简单的计算所以可以转化为非换根题来做。sum[y]=sum[x]+(n−2×size[y])×len(x,y）.注意n是全集，换根的写法就是因为这里一直没调过去。1.换根dp写法：#inc
2021-11-06 19:36:39
154
原创 算法设计与分析作业:小朋友过桥问题(蓝桥杯)
在一个夜黑风高的晚上，有 nn 个小朋友在桥的这边，现在他们需要过桥，但是由于桥很窄，每次只允许不超过两人通过，他们只有一个手电筒，所以每次过桥后，需要有人把手电筒带回来，第 ii 号小朋友过桥的时间为 a_iai，两个人过桥的总时间为二者中时间长者。问所有小朋友过桥的总时间最短是多少。输入格式第一行输入一个整数 nn，表示有 nn 个小朋友。第二行有 nn 个整数 a_iai ，a_iai 表示第 ii 个小朋友过河需要的时间。输出格式输出一个整数，表示所有小朋友过河所需要的时间。随后是
2021-10-07 13:23:13
468
原创 2021（CCPC）- 网络选拔赛Problem K. Shooting Bricks
本题为原洛谷原题，代码大部分是一位网友博客的改编版，多加一个t组循环和初始化，之前确实没见过这种的背包。有点状态机配背包的味道。（刚学完背包和状态机的我表示我没学明白，当时只用分组背包求最优解。。。）从新理思路的话终点看看代码中最后三层for循环中注释内容（原代码），和未注释内容（根据思路改变一下顺序）都对，其实因为dpn中一直存的值都要大于等于dpy，所以最后一个更新用fy更新fn似乎没神魔用。#include <bits/stdc++.h>using namespace std;
2021-08-29 10:11:28
197
原创 。。。..
阶梯博弈的讲课：树的删边游戏：无向图删边游戏： 竹子原理比较好证明。 数学归纳法比较严谨，竹子原理的理解基础上在作证明。证明博客：浅谈博弈论 | 远航休息栈 (yhzq-blog.cc)【算法学习笔记】博弈论浅析之游戏类 - RioTian (cnblogs.com)这两篇博客的证明应该够啦。对于无向图的证明用奇偶对称性构造即可。二分图博弈：考虑二分图的最大匹配，若最大匹配一定包含起点，则先手胜，否则后手胜。二分图博弈是一类博弈模型，它可以被抽象为：给出一张二
2021-08-11 11:30:02
140
原创 数独的填充——AcWing 166. 数独
#include <bits/stdc++.h>#include <algorithm>#include <cstring>#include <iostream>#include <queue>#include <unordered_map>#define xx first#define yy secondusing namespace std;typedef pair<int, int> PII;typ
2021-07-29 21:07:06
145
1
原创 树状数组笔记
1.树状数组的基本使用是求求前缀和。插入中的所有数组每一个以k结尾的sum【k】中会存有1到k的前缀和，修改需要修改他的直接父节点，然后一直修改到小于等于n的大小。add公式：for(int i=x;i<=n;i+=lowbit(i))tr[i]+=c;查询例如：12 （1100）需要查询到 8和12 这两个点刚好存储啦12 之前的所有点的前缀和。ask公式：for(int i=x;i;i-=lowbit(i))res+=tr[i];return res;2.O(n)建立树状数组
2021-07-02 22:20:33
168
1
原创 牛客网暑期ACM多校训练营（第一场）AB
A: Monotonic Matrix Gym - 247727A 前置知识：LGV 引理：仅适用于 有向无环图。这道题目因为从左上到右下只能是递增，即：靠右靠下位置的值总是大于等于靠左靠上位置的值，这样我们可以从右上到坐下画两条分解线，一条是 0 与 1 的分界线，另一条是 1 与 2 的分界线（且两条分界线最多只能重合）不能相互交叉。然后求总的两条分界线的书目就可以啦。接下来看LGV定理，因为这个定理只能用于求多个起点到多个终点的不可以相交的路径情况数。所以这道题需要做一下变形。学长博客里
2021-06-29 13:20:18
186
3
原创 bfs+多队列优化。（自己出题出的后台数据水的很）
命题人：ww知识点：bfs+多队列难度：中档时间限制：1000ms内存限制：65536KiB食堂买饭#### Description题面描述：acmer今天要从实验室去食堂买包子回来，实验室的教学楼到超市之间有一条漆黑的路，路是用黑色或者白色的地板铺成的，acmer看不清黑色的地板，只能看清白色的地板，acmer需要照亮黑色的地板后才能走到该位置，白色地板则不需要。acmer用来照亮的是一个破旧的手电筒，他需要预先充电才能使用（电量初始为零），因为太过于破旧，照亮一块地板之后手电筒的
2021-06-26 20:18:47
112
3
原创 离散化模板
vector<int> v;int find(int x){ return lower_bound(v.begin(), v.end(), x) - v.begin();}方在main里面：sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end());
2021-06-04 09:49:51
104
原创 G - Water Testing————2s2=a*2-b+2；皮克定理
G - Water Testing#include <bits/stdc++.h>#include <unordered_map>#include <vector>using namespace std;typedef long long ll;const int maxn = 3e5+1000;typedef pair<ll,ll> PII;map<string,int> ma;int n;PII p[maxn];inlin
2021-06-02 12:37:56
114
原创 2021Hubei ProvincialCollegiateProgrammingContestDAF+一道acwing
比赛链接地址。先做出来的是F题这道题目的话我用的优先队列（battery）配一个sort后的location数组然后挨个遍历battery里面最小的用来先解决location里面最小的值，最后得到最优解。这道题目的话因为location全是2的倍数的大小，似乎还可以借助这个性质来做。#include <bits/stdc++.h>using namespace std;typedef long long ll;int n,m;const int maxn = 3e5+1000;
2021-05-27 18:56:54
916
5
原创 可持久化数据额结构--trie和线段树的可持久化版本。（两道模板题）
最近学啦这两种树的可持久化版本，有点感悟，记录一下。可持久化trie题目链接：最大异或和第一步：：这道题的解法需要一个前缀知识，是异或操作的可以想加减操作一样，也就是可以做一个前缀和数组，而且这道题目里面的需要的 left 到 right 区间里面选择一个p点之后，答案也就是可以转化成一个 S前缀数组里面的 S[N] ^ S[P-1] = A[p]^…A[N-1] ^A[N];最中需要求解的表达式也就转化成啦S[P-1] ^S[N] ^X;然后因为需要必须选择一个节点所以是printf("%
2021-05-21 20:02:26
101
原创 sdut操作系统XOSCATS第九单元九道题题解
第一题effective access time记住公式：（访问内存时间+访问快表时间）命中率+（访问内存时间2+访问快表时间）*未命中率=cpu访问一个数据的平均时间第二题process deadlock1.当问R1类 的最少资源数的时候用进程数n*（w-1）的到的数字加以就是不会死锁的答案2.当问没个进程R1的类资源最少为多少是用将m变成(m/n+is(m%n))n;然后就是用n（w-1）==m得到w的解计算死锁时，假设有m个共享资源，n个进程，每个进程所需的最大资源数为w，那么m&
2021-05-18 18:46:07
796
原创 L3-016 二叉搜索树的结构 (30 分)
L3-016 二叉搜索树的结构 (30 分)题目见上面连接；被恶心到的第二次，上次是因为这道题目的字符串输入用的是getline然后判端某一位置的字母然后提取数字的方式，自己给写复杂啦，不要用getline来解这道题目；我认为这道题目应该是用字符串（一个一个吃）比较好判端也不用转haul数字；这次被恶心到的是忘记判端level那个一条语句最后找不到x或者y为键值的节点的情况，这种情况应该直接输出”No“。然后附上两种代码。第一种是全部都实现啦一遍；第二种是只借用啦一个find函数实现遍历树的。
2021-04-22 17:33:57
169
原创 7-14 二叉搜索树的最近公共祖先 (30 分)
这道题目我认为只有这一种做法是nlogn的复杂度，，，，来记录一下，别的方法（一个一个插入的那种）对于深度很深的情况都是会把时间拖到n方的时间复杂度。这种做法建树过程中只有排序的时间最长；建树是n的时间复杂度（每一个节点遍历一次）。#include <algorithm>#include <bitset>#include <cmath>#include <cstdio>#include <cstdlib>#include <cst
2021-04-21 20:14:41
270
原创 蓝桥杯--七段码
#include <algorithm>#include <bitset>#include <cmath>#include <cstdio>#include <cstdlib>#include <cstring>#include <deque>#include <functional>#include <iostream>#include <map>#include &
2021-04-17 20:28:05
111
原创 L3-002 特殊堆栈 (30 分)
L3-002 特殊堆栈 (30 分)此题用multiset过不了用vector可以过就离谱。感觉这道题目用树状数组来做是最好且不可能超时的算法。毕竟是一个log级别数据结构还可以用来求逆序对。这道题目用vector来做的话直接就是开一个栈，开一个vector然后更新（o（n））最后删除（o（n）），求中值的话非常快，直接找数组中间值就好。接下来说一下树状数组的做法，今晚通过这道题和一个树状数组求逆序队的博客算是懂啦树状数组是真的香。开一个树状数组的然后树状数组的前多少项的和存的就是小于等于下标
2021-04-10 21:11:01
71
原创 L2-034 口罩发放 (25 分)
L2-034 口罩发放 (25 分)题目异常恶心，很多坑。1.分发口罩顺序：顺序按照发放顺序确定。身体状况为 1输出顺序 ：顺序按照申请记录中出现的顺序确定，同一个人只需要输出一次。2 .身份证和姓名需要特别关注输入数据是否合法。（本人就是姓名每次都是输入一个字符，改啦一晚上也还是一分，换成string来存姓名直接25）代码1：（用啦stable——sort排序还挺香的）#include <bitsdc++.h>#include <limits.h>#incl
2021-04-10 16:16:22
823
1
原创 L2-028 秀恩爱分得快 (25 分)
L2-028 秀恩爱分得快 (25 分)谢谢阿康的帮助此题历经坎坷终于补上啦阿康的博客：题意：给出m张图片，每张图片里面有k个人，然后他们在同一张图片里面会增加1/k的亲密度，最后问x，y两人是不是互相亲密度最高的最佳情侣，是的话直接输出两人，不是的话，先输出x的亲密度最高的组合，在输出y亲密度最高的组合。里面男女会有“-”的差异，-0的存在会影响代码的正确性，所以需要用字符串输入，判端男女。然后题目保证男女的绝对值不会重复。思路：题目大致是个模拟，一定要记住不要直接把照片转成二位矩阵，因为三层循环
2021-04-08 21:27:26
156
原创 模板
模板整理：模板基本是从别人的博客或者视频讲解里面挖过来的，如有侵权及时警告，本人将尽快删除侵权内容。数学：FFF快速傅里叶变换这位大佬基本把闫总讲的都写啦一遍甚至还会多出一些呢容。后期将会及时增加模板博客。...
2021-03-22 20:22:27
67
原创 K - PhD math Gym - 100814K
K - PhD math Gym - 100814KK - PhD math Gym - 100814K题干见上面链接，题意大致为给出a，b，n；让我们构造出a/b的前n位数字组成的数字序列组成一个n位数。给出p让我们找出所有子数字序列中能整除p的个数。思路：这道题目构造出number序列来之后，可以对于p进行每一位的除模运算，然后找到这些位的同余个数对于同余位就是以他们为起止的子序列可以被p整除，然后这样的话找到每一个余数的个数用num*(num-1)/2,可以直接得到这一种余数为起止的个数。代码
2021-03-17 20:07:25
121
原创 J - The King‘s Walk Kattis - kingswalk
借鉴博客题目链接：J - The King’s Walk Kattis#include <iostream>#include <bits/stdc++.h>using namespace std;#define lowbit(x) x&(-x);typedef pair<int,int> PII;typedef long long ll;const int mod = 5318008;const int INF = 0x3f3f3f3f;con
2021-03-13 09:53:37
77
原创 SDUTACM春季集训选拔赛（19级）PTA补题
比赛链接第一题输出“Hello World!”。直接进入第二题：7-2 前世档案 (20 分)题意：问你在根据字符串最后在图上会走到结论几？思路：把yn中的n看作二进制中的1，y看作二进制中的0然后求出字符串对应的二进制数加1（因为结论从1开始）即为结果：#include <iostream>#include <bits/stdc++.h>using namespace std;char s[120];int main(){ int n,m; s
2021-03-12 20:15:45
240
原创 结构体的重载与自写cmp比较函数
题目链接acwing上的一个题目。闫总总结出来的模板。记重载。#include <cstring>#include <iostream>#include <algorithm>#define x first#define y secondusing namespace std;typedef pair<int, int> PII;//const int N = 310;//int n;//struct Person//{//
2021-01-22 16:48:28
456
原创 最长上升子序列下降子序列模板。
#include <iostream>#include <algorithm>using namespace std;const int N = 1010;int n;int a[N];int f[N], g[N];int main(){ scanf("%d", &n); for(int i=1; i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=n;i++)//求最长下
2021-01-19 11:03:54
54
原创 P3374 【模板】树状数组 1
题目链接P3374 【模板】树状数组 1提交69.12k通过38.17k时间限制1.00s内存限制125.00MB提交答案加入题单题目提供者HansBug难度普及/提高-历史分数100提交记录 查看题解标签高性能进入讨论版相关讨论推荐题目展开题目描述如题，已知一个数列，你需要进行下面两种操作：将某一个数加上 xx求出某区间每一个数的和输入格式第一行包含两个正整数 n,mn,m，分别表示该数列数字的个数和操作的总个数。第二行包含 nn 个用空格分
2021-01-18 20:48:53
51
原创 Gym - 102860A_B题解。。Jumping Machine ——Triangles and a Circle
标题A - Jumping Machine Gym - 102860A题目链接Jumping MachineInput file: standard inputOutput file: standard outputTime limit: 1 secondMemory limit: 512 megabytesYoung inventor has created a new jumping machine. In order to test it, he brought it to the te
2020-12-16 15:02:46
314
原创 G - Gnoll Hypothesis Kattis - gnollhypothesis
题目链接题目讲解先看另一位博主的讲解吧，我是看的他的博客比这写出来的这道题：博客链接求第一个位置时，选中有1的方案及相应的概率：1-36% 2-25% 3-39%1-24% 2-25% 4-51%1-1% 2-25% 5-74%1-24% 3-64% 4-12%1-1% 3-64% 5-35%1-1% 4-76% 5-23%1号位置的概率期望为(36+24+1+24+1+1)/C(5,3) = 8.7对于每一个位置i，f[i][j]表示第i个位置被选中，且其上面恰好有j个相邻的位置没有
2020-12-14 11:06:55
296
原创 F - Firetrucks Are Red
题目链接题目链接Lily is fascinated by numbers. She believes the whole world revolves around them, and that everything is connected by numbers. Her friends, Alice, Bob, Charlie and Diane, are not convinced. But she gives them an example:Alice lives in house numb
2020-12-13 20:40:53
228
原创 D - A Simple Math Problem HDU - 5974数论—欧几里得
@数论之欧几里得gcd(an,bn)=ngcd(a,b);这道题可以用到的是：条件：a=x+y;b=xy;结论：gcd（x,y）==gcd(a,b);题目：D - A Simple Math Problem HDU - 5974Given two positive integers a and b,find suitable X and Y to meet the conditions:
2020-12-09 15:53:46
98
原创 Problem F Philosopher’s Walk分治递归坐标转换
题目地址Fpdf题目#include <iostream>#include <bits/stdc++.h>#include <algorithm>#include <vector>using namespace std;typedef long long ll;pair <ll,ll>solve(ll n,ll m){ if(n==0)return make_pair(1,1); ll len=1<<(
2020-12-07 17:26:38
234
原创 Fractal Streets POJ - 3889 分治+递归坐标转换
城市的规划在城市建设中是个大问题。不幸的是，很多城市在开始建设的时候并没有很好的规划，城市规模扩大之后规划不合理的问题就开始显现。而这座名为 Fractal 的城市设想了这样的一个规划方案，如下图所示：当城区规模扩大之后，Fractal 的解决方案是把和原来城区结构一样的区域按照图中的方式建设在城市周围，提升城市的等级。对于任意等级的城市，我们把正方形街区从左上角开始按照道路标号。虽然这个方案很烂，Fractal 规划部门的人员还是想知道，如果城市发展到了等级 N，编号为 A 和 B 的两个街区
2020-12-07 17:22:03
138
原创 知道二叉树知道中序和另一种遍历建树2020-11-17
后序中序建树模版#include <iostream>#include <algorithm>#include <stdio.h>#include <stdlib.h>#include <bits/stdc++.h>using namespace std;struct node{ char data; struct node *l; struct node *r;};struct node *q, *p;
2020-11-17 11:50:36
79
原创 逆序数分治归并
首先是看啦一下这个人的开头归并还是有点用的（虽然被喷的很惨）。博客链接首先说明一下什么是逆序数，下面是百度的定义：在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。如2431中，21，43，41，31是逆序，逆序数是4。①如何求逆序数方法如下：考察每一位，判断从这一位往后有多少小于该位的，结果累加，得到最后结果。例如，2,4,3,1 先判断2，之后有1是小于2的，结果+1，再判断4，之后3,1
2020-10-21 21:09:55
83
原创 归并排序merge sort（挑战程设7.1 120页）
算法复杂度O(nlongn)稳定排序（也就是不会两个数字相等却交换啦位置）快速排序就会交换位置所以sort不是稳定排序要想稳定的sort stl函数也有就是： stable sort捏个会多占用空间，其实这个就是以归并排序为基础的东西。代码：以后自己看不懂啦会来加注释的，，，，（懒狗）顺手先放个分割排序函数partition，自己写快排可以调用这个函数。#include <iostream>#include <bits/stdc++.h>using namesp
2020-10-21 20:52:52
80
原创 最短路bellman-ford模板
啊哈算法168页#include #include #include <bits/stdc++.h>using namespace std;int dis[10],i,k,n,m,u[10],v[10],w[10];int inf=99999999;int main(){scanf("%d%d",&n,&m);for(i=1;i<=m;i++)//读入边scanf("%d%d%d",&u[i],&v[i],&w[i]);for
2020-09-18 21:02:09
55
原创 G - Great dinner Gym - 102700G 排队时两人有次序的问题
https://vjudge.net/contest/392956#problem/GG - Great dinner Gym - 102700GUNAL is about to restart classes and the leaders of the algorithms group want to receive all its members with a great dinner in the university campus central dining room.The group
2020-09-16 21:07:56
226
原创 7-2 旅游规划 (25分)------Dijkstra
山东理工大学2020年全国天梯赛赛前个人专题强化赛—C（最短路）7-2 旅游规划 (25分)有了一张自驾旅游路线图，你会知道城市间的高速公路长度、以及该公路要收取的过路费。现在需要你写一个程序，帮助前来咨询的游客找一条出发地和目的地之间的最短路径。如果有若干条路径都是最短的，那么需要输出最便宜的一条路径。输入格式:输入说明：输入数据的第1行给出4个正整数N、M、S、D，其中N（2≤N≤500）是城市的个数，顺便假设城市的编号为0~(N−1)；M是高速公路的条数；S是出发地的城市编号；D是目的地的城市
2020-09-16 20:32:30
218
岱宗旅.zippppp
2023-05-09
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人