- 博客(77)
- 收藏
- 关注
RSS订阅原创 python安装库
pip install 库名 -i http://pypi.douban.com/simple/ --trusted-host pypi.douban.com
2021-11-30 18:32:05
557
原创 天梯地图 (30 分)
天梯地图跑两次Dijkstra,最后输出有点啰嗦,太懒了,不想改了#include <bits/stdc++.h>using namespace std;const int N = 500+10;typedef pair<int,int> PII;int n,m,k,st,ed;int u,v,len,op,ti;int g[N][N],cost[N][N],path[N];int dist[N],vis[N],dis[N];int cnt[N],sum[N
2021-10-15 21:20:37
215
原创 病毒溯源 (25 分)
病毒溯源题意: 给你一棵树，让你求出最长的那条链,如果不唯一,输出最小序列.思路: 直接dfs根节点,然后用path数组记录前驱节点.#include <bits/stdc++.h>using namespace std;const int N = 1e4+10;int n,k,v;vector<int>g[N];vector<int>ans;int in[N],path[N];void dfs(int u,int depth) { i
2021-10-15 19:36:17
571
原创 Maximal submatrix
题目链接题意：求最大子矩阵的面积，子矩阵每一列满足从上往下递增。思路：将矩阵转换成0/1矩阵，1表示这个数比上面的那个数大，0就是小，转换成0/1矩阵后用一个for循环套一个单调栈就可以解出。for循环就是更新当前状态每列矩形的高度，单调栈就是求每一部分的最大面积。#include <iostream>#include <cstdio>#include <cstdlib>#include <cmath>#include <al.
2021-07-21 15:44:32
87
转载 Java字符流缓冲区
作用：缓冲区要结合流才可以使用，而且在流的基础上对流的功能进行了增强。我们也可以说，在我们以后的实际运用之中，为了增强一下IO流的读写能力，我们就要加入缓冲区这个角色，我们可以理解是为了提高效率而这样做的。另外还有一点是，在用到缓冲区就要记得刷新。解释：我们用通俗的语言解释一下缓冲区的作用。首先，我们要假设我们很口渴，但是只有一个一滴一滴滴得很慢的水龙头，这时的我们是将嘴靠近去一滴一滴去喝还是利用一个杯子，当杯子装满一杯后，我们一饮而尽。这里，充当这个容器的东西杯子便是我们本章所要讲的缓冲区。Fi
2021-05-27 16:02:08
163
翻译 求组合数
杨辉三角#include <iostream>#include <cstdio>#include <cstdlib>#include <cmath>#include <algorithm>#include <string>#include <cstring>#include <vector>#include <map>#include <set>#include &l
2021-05-27 09:53:08
59
原创 L2-001 紧急救援 (25 分)
输入：4 5 0 320 30 40 100 1 11 3 20 3 30 2 22 3 2输出：2 600 1 3优先队列：#include <bits/stdc++.h>#define inf 0x3f3f3f3fusing namespace std;int dist[505],path[505],num[505],pathNum[505],cnt[505];int n,m,s,d,g[505][505],vis[505];struct node..
2021-04-15 17:26:59
73
原创 L2-034 口罩发放 (25 分)
好恶心的一道题,就因为我把有症状的人用set存,结果一直卡在后三个样例,把我恶心吐了,最后实在没法把set改成vector顺便标记一下看看是否访问过一次，然后就过了，我tm改了接近两个小时，结果就卡在这…#include <iostream>#include <cstdio>#include <cstdlib>#include <cmath>#include <algorithm>#include <string>#..
2021-04-10 11:26:20
728
1
原创 PTA-网红点打卡攻略
#include <iostream>#include <cstdio>#include <cstdlib>#include <cmath>#include <algorithm>#include <string>#include <cstring>#include <vector>#include <map>#include <set>#include <qu.
2021-04-10 08:48:00
591
原创 B. Flip the Bits
思路: 判断a与b是否相等，如果相等输出YES，否则，先求出串a中0（或1）的个数的前缀和，从n-1到0遍历，当反转的次数(反转次数初始为1)是奇数且a[i]!=b[i]，如果sum[i]!=i-sum[i]+1（判断从0~i 1和0的个数是否相等）flag=0，结束循环；否则反转次数加一。当反转的次数是偶数且a[i]==b[i]，在进行类似上面的判断。最后如果flag等于1就输出YES，否则输出NO。#include <iostream>#include <cstdio>..
2021-04-09 09:35:21
167
原创 L2-022 重排链表 (25 分)
#include <iostream>#include <cstdio>#include <cstdlib>#include <cmath>#include <algorithm>#include <string>#include <cstring>#include <vector>#include <map>#include <set>#include <s..
2021-04-05 20:14:19
52
原创 L3-010 是否完全二叉搜索树 (30 分)
根据节点的编号判断是否是完全二叉搜索树，如果最大的节点编号不等于n就不是，否则就是。#include <iostream>#include <cstdio>#include <cstdlib>#include <cmath>#include <algorithm>#include <string>#include <cstring>#include <vector>#include <m.
2021-04-05 15:27:45
126
原创 L1-025 正整数A+B (15 分)
#include <iostream>#include <cstdio>#include <cstdlib>#include <cmath>#include <algorithm>#include <string>#include <cstring>#include <vector>#include <map>#include <set>#include <q..
2021-04-05 15:22:24
55
原创 PTA-列车调度 (25 分)
#include <iostream>#include <cstdio>#include <cstdlib>#include <cmath>#include <algorithm>#include <string>#include <cstring>#include <vector>#include <map>#include <set>#include <qu.
2021-04-05 14:43:30
242
原创 PTA-分而治之
思路：计算一下除去Np个点之后的连通分量，如果去掉的点数+此时的连通分量==n，就输出YES，否则输出NO。#include <iostream>#include <cstdio>#include <cstdlib>#include <cmath>#include <algorithm>#include <string>#include <cstring>#include <vector>..
2021-03-31 15:37:36
312
原创 L1-046 整除光棍 (20 分)
类似于大数除法一样模拟，从1开始每次循环判断一下此时的光棍能否整除x。判断能否整除的方法就是此时的光棍除完之后余数是否为零。#include <bits/stdc++.h>using namespace std;int main() { string s="1"; int len=0; int num; cin>>num; vector<int>ans; while(true) { ans.cl..
2021-03-26 19:28:49
54
原创 pta-关于堆的判断
输入：5 446 23 26 24 1024 is the root26 and 23 are siblings46 is the parent of 2323 is a child of 10输出：FTFT小顶堆（任意一个节点，它的左子树与右子树上的节点都大于该节点）的建立：每输入一个数，把这个数与它的父节点比较，如果比这个值比父节点小的话就交换，再将父节点与父节点的父节点比较，以此类推；如果某个节点的值大于父节点的值就结束查找。#include <iostrea..
2021-03-25 20:41:54
478
原创 L - Elegant Showroom
题目链接思路：从给定的点进行bfs，搜索到位于边界上的‘D’就停止，每次取一下最小值。AC代码：#include <iostream>#include <cstdio>#include <cstdlib>#include <cmath>#include <algorithm>#include <string>#include <cstring>#include <vector>#inc
2021-03-25 16:29:07
86
原创 Book Club
题意：每个人都有自己喜欢的一本或多本书，然后在这n个人中每个人可以与其他人借书，求n个人中拿到自己喜欢的书的人的最大值。思路：读完题应该就能想到是二分图的题目，直接套二分图的模板#include <iostream>#include <cstdio>#include <cstdlib>#include <cmath>#include <algorithm>#include <string>#include &l..
2021-03-22 14:44:04
101
原创 B - Flowery Trails
题意：求出所有最短路径上每条边的距离之和思路：从0到n-1跑一遍Dijkstra，再从n-1到0跑一遍，然后在用两层for循环找出d1[u]+d2[v]等于最短路径的边（从起点到某个节点的最短距离加上从终点到该节点的最短距离等于最短路径），用sum加上这两点间的的距离，最后输出sum。这道题真是让我长见识了，以前从来没做过这种类型的，真妙！#include <iostream>#include <cstdio>#include <cstdlib>#...
2021-03-22 14:35:55
135
原创 链表去重
输入样例：00100 599999 -7 8765423854 -15 0000087654 15 -100000 -15 9999900100 21 23854输出样例：00100 21 2385423854 -15 9999999999 -7 -100000 -15 8765487654 15 -1思路：将地址作为结构体下表，在结构体中存放键值与下一个节点的地址，然后从首地址遍历直到等于-1，将需要输出的节点地址放在pre数组中，需要删去的节点的地址放在del数组中..
2021-03-14 10:59:52
146
原创 B - Super Mancunian
题目链接题意：有n个等级，某些等级是相连的，但需要费用w才可以解锁访问，解锁之后再次访问该等级不需要任何花费，从等级1开始，访问n个等级花费的最小值，另外一个条件是可以让某两个等级之间的花费变为0。思路：先用最小生成树求一下最小边权之和与最小生成树中的最大边权值maxx，再用类似最小生成树的方法求一下，在不成环的前提下，如果边权值>=maxx的边并且加上这条边能构成最小生成树，那么tot++（tot最小生成树的个数）；否则就让u的父节点归结于v的父节点。继续遍历。注意要是用long long，代
2021-02-18 10:24:25
107
原创 K - Kongey Donk
好不容易在比赛中碰到比较简单的dp，结果因为越界问题没有处理好，没有做对????。好难受，我好菜啊因为这个数据有点大，用数组肯定会越界，然后用vector做，但是我用vector写的时候出现了段错误，主要是使用的不熟练。后来查了查怎么用vector代替二维数组，改成那位大佬说的之后就a了。#include <iostream>#include <cstdio>#include <cstdlib>#include <cmath>#include &l
2021-02-09 23:59:17
116
原创 A - Alchemy 101
A - Alchemy 101题意： 输入一个数m，求出从1到m中异或和等于m且是所有情况中包含的数字最多和字典序最小的那一串数。我的想法相当暴力,就是先求出从1到m的异或和,如果等于m那就直接输出,否则就bfs从m到1与每个数进行异或运算,如果等于m就输出,否则就将其异或结果放进队列中,一直到那一串数。当然还有其他更简单的方法，先放上代码。#include <iostream>#include <cstdio>#include <cstdlib>#
2021-02-06 18:29:09
115
原创 F - Honeycomb
题目链接题意：从起点‘S’到终点‘T’经过的最少方格数，如果不能到达‘T’就输出-1。思路：从起点BFS一下，把每个六边形的中心看做一个点。蜜蜂可以向六个方向移动，分别判断一下能否到达另一个相邻的六边形并判断是否是终点。记录一下最短的路径。再总结一下做这个题遇到的一些困难：①在输入的时候花了很长时间，因为使用gets可能导致堆栈溢出覆盖之前输入的内容，这次就用了cin.getline()输入，可是之前使用的次数不多，没有深入了解过cin.getline(),使用的不是很熟练,输入的时候
2021-02-01 18:02:45
131
原创 E - Video Conference
题目链接题意：按时间顺序输入一串人名，输出的名字前缀不能与在他之前输入的名字前缀相同，如果名字与在他之前输入的完全相同，则输出全名和目前为止名字出现的次数。思路：将每个人的名字构成一个字典树，将名字插入字典树时将p->num == 1之前的所有字符存入一个数组中（包括p->num==1），这个字符数组就是就是当前这个名字的前缀且与之前输入的名字的前缀不同。#include <iostream>#include <cstdio>#include <cst
2021-02-01 11:38:23
200
原创 420. 火星人（next_permutation）
思路: 从后往前看这个给出的火星人用手指表示的数, 如果从后往前一直是递增的,那么到目前这个数不存在某种排列比当前这种排列字典序大,当出现降序时(a[i]>a[i-1])，就从i+1到n中找到第一个比a[i]大的数并交换它们俩的值，再将i之后的数反转，重复m次。next_permutation做法：#include <iostream>#include <cstring>#include <algorithm>using namespace std;.
2021-01-29 16:07:59
121
原创 AcWing 279. 自然数拆分
题目链接因为至少拆分成2个数的和，所以就从1~n-1里面选若干个数，使其加和等于n。这个题就是典型的完全背包问题，可以将1 ~ n-1看成n-1个物品，每件物品可以选任意次，背包容量是n，求出加和等于n的方案数。这里使用滚动数组 ，令 f [j] 表示加和等于j的方案数，那么 f [j] 就等于选第i个物品的方案数与不选第i个物品的方案数的和，就是 f[j] = f[j]+f[j-i](f[j]表示不选第i个物品的方案数，此时的f[j]是在上一层循环中求出的，也就是没有选第i件物品时加和等于j的方案
2021-01-28 15:19:42
97
原创 Acwing1381. 阶乘
题目链接思路:根据唯一分解定理可知，一个数可以分解成有限个质数的乘积N=P1^a1 * P2^a2 * P3^a3… Pn^an，这里P1<P2<P3…<Pn均为质数，其中指数ai是正整数。这个题要求的第一个非零整数就是从最低位开始到第一个非零整数之间的零去掉再取余10.N = 2^α * 5^β * P;k=min(α,β);N的第一个非零数就是 N/((2*5)^k) %10 = (2 ^ α-k * 5 ^ β-k * P)%10;那么这个题就是求出n!中2和5的个数
2021-01-27 16:04:41
98
转载 1353. 滑雪场设计
一开始想用贪心做，找出最高与最低的山峰求出它俩的差再将这个差除以2（考虑是奇数还是偶数的情况）最低峰加上一个值最高峰减去一个值，再排序，重复上述操作直到最高与最低相差不大于17。不知道为什么这样做不对。看的题解是用枚举做的，因为高度是大于等于一小于等于一百，就从1到83遍历，那么就找出输入的高度中不满足 >=i && <=i+17 的，求出最小值。#include <iostream>#include <cstdio>#include <c.
2021-01-27 15:45:13
63
原创 Coloring Contention
题目链接题意理解的不是很清楚，反正就是Alice想要Bob选择的路径里颜色转换次数最大，那么Alice就要使路径的颜色交替变换，但Bob想要产生的颜色转换最小，就求从1到n的最短路。（我理解的可能也不是很准确，但就是用最短路来求????）好像用普通的Dijkstra会超时，得用dijkstra+堆优化#include <iostream>#include <cstdio>#include <cstdlib>#include <cmath>#in
2021-01-25 16:09:47
88
原创 Perfect Flush
题意：找一个字典序最小的子序列。思路：使用单调栈，遍历序列，如果 栈不为空且a[i] <ans[top] (单调栈)且在 i 之后还有ans[top]这个数那么就将栈顶元素出栈,对这一步进行while循环。循环完之后,如果站里面不存在a[i],那么就将a[i]压入栈中.#include <stdio.h>#include <stdlib.h>#include <algorithm>#include <iostream>#include &l.
2021-01-25 14:22:48
74
原创 棋盘游戏
题目链接这个题与八皇后问题很相似，就是从第一行开始列举出每个棋子放在每一列的情况，每次都判断一下是否在同一行或同一列或对角线上有其他的棋子。如果有的话就回溯到上一行，在另一列放下棋子，再递归，一直到n+1行，然后输出每行棋子的位置。#include <iostream>#include <cstdio>#include <cstdlib>#include <cmath>#include <algorithm>#include <.
2021-01-23 14:59:49
192
原创 ACwing每日一题2021/1/21
二维数组对角线位置上的数都为1，从1向左右两边递增。#include <iostream>#include <cstdio>#include <cstdlib>#include <cmath>#include <algorithm>#include <string>#include <cstring>#include <vector>#include <map>#include .
2021-01-21 10:42:00
61
原创 B - Different Divisors
题意：求一个数，这个数至少有4个除数，且每个除数的差至少是d。思路：每个数的除数肯定包含1，那么就从1开始找一个素数且这个素数与1的差至少是d，然后将目前的数更新为这个素数，再从这个素数+d开始，再找一个素数，且两数之差大于等于d。假设找到的第一个素数是a，第二个是b，答案就是a*b。#include <iostream>#include <cstdio>#include <cstdlib>#include <cmath>#include <.
2021-01-21 10:38:44
453
原创 Lost Cow
题意：有n头牛，每头牛都有自己的编号，给你n-1个数，从第二头牛开始，表示第i头牛之前比第i头牛编号小的有几个，然后求出每头牛的编号。代码参考 《算法竞赛从入门到进阶》最初不太理解findpos（）和add(x,-1)什么意思，现在好像稍微懂了点（见注释），先把现在理解的记录一下。#include <iostream>#include <cstdio>#include <cstdlib>#include <cmath>#include <
2021-01-19 15:22:37
122
原创 Monument Tour
题目链接题意:从矩形的左边任一条路（东西走向）进入，然后参观所有的纪念碑与博物馆，只能向上或向下移动，参观完纪念碑与博物馆后返回到进入时的那条路上，求走出城市时的最短路程。思路:遍历x坐标轴，求出每个x坐标中的最大与最小y值，存入数组a中，然后排序，求出中位数，这个中位数就是汽车进入城市时的y坐标，然后计算从0—X汽车参观每个博物馆走的路程。代码：#include <iostream>#include <cstdio>#include <cstdlib>#i
2021-01-18 14:15:54
143
原创 Hopcroft-Karp算法的代码理解
#include <iostream>#include <cstdio>#include <cstdlib>#include <cmath>#include <algorithm>#include <string>#include <cstring>#include <vector>#include <map>#include <set>#include <que
2021-01-09 21:04:59
393
转载 Inverse Factorial
题目意思就是已知n的阶乘，求n。当输入的阶乘小于10位数的时候，我们可以用long long将字符串转化成数字，直接计算。而当输入的阶乘很大的时候，我们就可以利用位数去大概的估计n。#include <bits/stdc++.h>using namespace std;typedef long long ll;ll n, m, num, res, ans, len;string str;void input() { cin >> str; len =..
2021-01-08 10:47:05
146
原创 Big Truck（Dijkstra）
题目链接带权最短路，Dijkstra模板题一开始傻傻的用Floyd求，怎么也算不对，后来又用DFS，最后一个样例超时…最后用Dijkstra求的…后来上网查的资料才知道Dijkstra是经典的求取带权最短路算法.#include <iostream>#include <cstdio>#include <cstdlib>#include <cmath>#include <algorithm>#include <string&g
2021-01-03 13:21:28
279
1
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人