- 博客(397)
- 收藏
- 关注
RSS订阅原创 洛谷 P1443 马的遍历（bfs）
题目链接：https://www.luogu.com.cn/problem/P1443思路：一道广度优先搜索求最短路的裸题注意数字左对齐宽n格用printf输出格式为%-nd代码：#include<bits/stdc++.h>using namespace std;const int maxn = 404;int n, m, x, y;int mat[maxn][maxn];queue<pair<int, int> > que;int
2021-04-17 20:37:49
255
1
原创 洛谷 P4017 最大食物链计数（求拓扑排序数）
题目链接：https://www.luogu.com.cn/problem/P4017思路：一道裸的求图的拓扑排序数量的题代码：#include<bits/stdc++.h>using namespace std;const int maxn = 5005;const int mod = 80112002;int n, m; queue<int> que;int deg[maxn], cnt[maxn]; //入度 答案计数 vector&l
2021-04-16 18:41:18
233
原创 洛谷 P1219 [USACO1.5]八皇后 Checker Challenge（dfs）
题目链接：https://www.luogu.com.cn/problem/P1219思路：以行号为层次进行dfs；用vector维护每一行的列号，每次搜索时维护三个bool数组以保证列号互异、两条对角线互异；代码：#include<bits/stdc++.h>using namespace std;int n;vector<int> v;int ans;bool f[15]; //列号 bool a[100], b[100]; //对角线
2021-04-16 15:52:47
241
原创 洛谷 P1019 [NOIP2000 提高组] 单词接龙（dfs）
题目链接：https://www.luogu.com.cn/problem/P1019思路：1.首先我们对所有字符串做一个预处理得到inc[i][j]这个数组，这个数组的含义是：在字符串iii后接上字符串jjj可以使得字符串增加多少长度；做这个预处理的理由是，在真正接龙时，想要得到最长的“龙”，必定是一个字符串接在刚刚接上的字符串之后；2.然后进行暴力搜索即可，注意维护一个数组存储字符串用过的次数，大于等于两次的字符串不能再用；代码：#include <bits/stdc++.h
2021-04-15 20:51:35
345
1
原创 2021年一战南大AI上岸经验贴
前言首先自我介绍一下，我来自南京某双非学校。大一裸考过了四六级(584&497)，参加过一些数学竞赛&算法竞赛，获得过还不错的奖项，因此个人基础尚可。初试总分390（政治69，英一76，数一125，专业课120），排名6/20。随着今天未拟录取名单的公布+个人的电话确认，长达7个月的考研生涯也算是正式落幕了。十分感激南大CS&AI的学长学姐们在github无偿维护的wiki（https://github.com/nju-kaoyan/nju_csai_kaoyan），在备考期
2021-04-06 00:17:42
12056
18
原创 Python第三方库安装
Python社区（https://pypi.org）拥有很多第三方库，我们可以通过以下三种方法安装他们：一、pip安装方法常用的pip命令：1.安装指定的第三方库pip install <第三方库名>2.更新pip install -U <第三方库名>3.卸载pip uninstall <第三方库名>4.下载但不安装pip download <第三方库名>5.列出详细信息pip show <第三方库名>6.根据
2021-02-22 13:25:14
158
原创 洛谷 P1434 [SHOI2002]滑雪（记忆化搜索）
题目链接：https://www.luogu.com.cn/problem/P1434思路：1.设len[i][j]为从i行j列的格子为起点的滑坡的最大长度；2.若直接使用递推，需要扫R∗CR*CR∗C遍区域，复杂度为O(R2C2)O(R^2C^2)O(R2C2)，会TLE；3.另一个想法是使用一趟dfs得到len[i][j]的值，使用R∗CR*CR∗C趟即可得到所有的值，选取其中最大的即为答案；注意中间保留所有的搜索结果以便于之后减少重复搜索；代码：#include <bits
2021-02-04 20:23:53
206
原创 洛谷 P1216 [USACO1.5][IOI1994]数字三角形 Number Triangles（dp）
题目链接：https://www.luogu.com.cn/problem/P1216思路：1.若用二维数组来存储数字三角形，设xi,jx_{i,j}xi,j是从顶端走到第iii行第jjj列时的最大和、ai,ja_{i,j}ai,j是存储数字三角形的二维数组对应位置的值，则可得xi,j=max(xi−1,j,xi−1,j−1)+ai,jx_{i,j}=max(x_{i-1,j},x_{i-1,j-1})+a_{i,j}xi,j=max(xi−1,j,xi−1,j−1)+ai,j2.
2021-01-30 20:24:21
192
原创 Win10中关于“pip install pyinstaller”产生的一系列问题及其解决方法
笔者在win10的cmd命令行中使用如下命令产生了一系列的问题pip install pyinstaller经过一系列的折腾，最终成功解决，下面分享一下个人遇见的问题以及解决的方法1.ssl module in Python is not available.笔者在python3中import ssl未出现任何错误，但是在cmd中却出现ssl不可访问的问题；（很奇怪+1）解决方法：在http://slproweb.com/products/Win32OpenSSL.html中，重新下载ssl并安
2021-01-25 20:48:26
1817
3
原创 Yuhan的python笔记
开个坑记录一下自己的python学习笔记，以便温故知新Chapter I1.python的保留字2.一个程序实例其中，注意input()、print()、eval()、print("".format())的用法to be continued…
2021-01-08 15:18:29
270
4
原创 PAT甲级 1081 Rational Sum (20分)
题目链接：https://pintia.cn/problem-sets/994805342720868352/problems/994805386161274880思路：分数在加减时，将两个运算数的分母都化成最小公倍数就好了；最后一个测试点是输出0，不是很懂题目为什么不告诉你0值怎么输出；整数部分是0只要输出分数部分，分数部分是0呢？自己猜一个值输出吗？代码：#include <bits/stdc++.h>using namespace std;typedef lon
2020-09-03 14:42:53
136
原创 PAT甲级 1026 Table Tennis (30分)
题目链接：https://pintia.cn/problem-sets/994805342720868352/problems/994805472333250560思路：据说现在PAT已经不考这种大模拟了，准备PAT的同学可以酌情跳过节省时间~我的想法是用优先队列保存即将要发生的事件（一共三种事件），先发生的排在前面。用户排队的情况我是使用两个队列分别存储vip和普通用户的。接下来我们一个一个处理这些事件即可：（1）有vip过来打球。若有空桌，则先选择vip桌中序号最小桌，若无空vip桌则选
2020-08-10 14:06:47
254
原创 PAT 甲级 1104 Sum of Number Segments (20分)
题目链接：https://pintia.cn/problem-sets/994805342720868352/problems/994805363914686464思路：1.我们用序号[0…n-1]来给这n个数标号，观察可以发现包含第i个数的连续段起点只能在0 ~ i，终点只能在i ~ n-1；因此包含序号i的数的连续段一共有(i+1)*(n-i)个；2.如果用double存储、累加求和结果，会因为double的内存存储精度问题而产生失精的结果；解决方法是将数据放大一定的倍数从而改用long
2020-08-04 17:59:47
169
原创 PAT甲级 1106 Lowest Price in Supply Chain (25分)
题目链接：https://pintia.cn/problem-sets/994805342720868352/problems/994805362341822464思路：1.考察树的dfs；2.零售商只可能在叶子节点，若从root到零售商所经历的边的数量为aaa，则该零售商的价格就是p∗(1+r∗0.01)ap*(1+r*0.01)^ap∗(1+r∗0.01)a；代码：#include <bits/stdc++.h>using namespace std;const
2020-08-03 22:49:12
134
原创 PAT甲级 1105 Spiral Matrix (25分)
题目链接：https://pintia.cn/problem-sets/994805342720868352/problems/994805363117768704思路：1.将所给序列倒序排序；2.一圈一圈地将序列逆时针填入矩阵；我的思路是使用变量x,y来表示当前我们所需操作的矩阵位置，然后按如下顺序挨个填入数据；重点是对x，y坐标位置的控制；代码：#include <bits/stdc++.h>using namespace std;int N, m, n;i
2020-08-03 22:46:02
163
原创 C语言实现ELF文件解析
这学期Linux的大作业第一部分是解析64位/32位的ELF文件，这里偷了个懒只解析了ELF头、程序头表和节头表；这里先附上代码占个坑，有时间会来补详细解释；输入格式为ELF文件名；程序会同时将三个解析结果打印到控制台并写入同级目录下的result.txt文件中；#include <stdio.h>#include <stdlib.h>#include <elf.h>#include <string.h>#define putline pu
2020-06-29 15:06:31
5845
8
原创 基于算符优先分析法的语法分析器（编译原理之自底向上分析技术）
先用代码占个坑，等期末结束了再补详细解释。。。/* 2020-06-20 by 软件工程172 202171139 TDM-GCC 4.9.2 64-bit -std=C++11 */#include <bits/stdc++.h>#define pcc pair<char, char>#define fi first#define sc second#define mp(a, b) make_pair(a, b)using namespace std;
2020-06-26 01:45:02
1114
原创 如何优雅地在Word中粘贴代码
大家日常在用word写实验or大作业报告时都有需要在word中附上代码的时候~直接从编辑器中ctrl+c过来的代码往往显得不太美观，笔者有一个小技巧可以使得代码看上去更加美观一些，在这里分享出来希望可以帮助到大家~step1打开网站http://www.planetb.ca/syntax-highlight-word在Code框贴进自己需要写进word的代码，而后在Language下拉选择框选择自己代码的语言，再点击Show Highlighted按钮，可以得到如下图的页面：Microso
2020-06-24 22:41:51
18908
4
原创 Codeforces 1355D Game With Array
题目链接：https://codeforces.com/contest/1355/problem/D思路：结论：S<2NS<2NS<2N时Petya会输，否则会赢；证明：1.当S≥2NS\geq2NS≥2N时，我们选择(1,1,...,1,S−N+1)(1,1,...,1,S-N+1)(1,1,...,1,S−N+1)这个序列(一共有N−1N-1N−1个111)，且令K=NK=NK=N;我们需要证明任意子连续的子序列和不等于NNN和S−NS-NS−N；（1）如果子序列不
2020-05-24 15:04:52
338
1
原创 Codeforces 1353D Constructing the Array
题目链接：https://codeforces.com/contest/1353/problem/D思路：我们将所有待处理的子线段按照{长度，左端点序号，右端点序号}按序存储在优先队列中，然后挨个处理即可；代码：#include<bits/stdc++.h>using namespace std;struct seg { int len, l, r; bool operator < (const seg & s) const { return le
2020-05-16 13:17:50
269
原创 蓝桥杯 第十一届软件类第二次校内模拟赛——C/C++程序设计
第一题思路：简单排列组合问题；答案7!2!\frac{7!}{2!}2!7!第二题思路：dfs搜一下就行了代码：#include<bits/stdc++.h>#define crr(x) cerr << "#x:" << ' ' << x << '\n';using namespace std;int ...
2020-04-16 20:34:30
1005
原创 蓝桥杯 PREV-28 地宫取宝（dp）
题目链接：http://lx.lanqiao.cn/problem.page?gpid=T120思路：1.记dp[i][j][a][b]dp[i][j][a][b]dp[i][j][a][b]为走到坐标为(i,j)(i,j)(i,j)位置后，手上有aaa件物品且所有物品中最大值为bbb的方案数；2.假设我们现在从(a,b)(a,b)(a,b)走到(x,y)(x,y)(x,y)（这两个...
2020-03-31 13:21:23
175
原创 蓝桥杯 PREV-43 拉马车（stl的使用）
题目链接：http://lx.lanqiao.cn/problem.page?gpid=T447思路：1.我们可以发现出牌者的牌是遵循队列规则、而桌上的牌是遵循栈规则的；2.用map容器维护一下桌上是否有某张牌，剩下的模拟即可；代码：#include<bits/stdc++.h>using namespace std;queue<char> qu...
2020-03-28 21:08:00
183
原创 蓝桥杯 第十一届软件类校内模拟赛——C/C++程序设计
第一题思路：这题是求约数个数，数据不大可以暴力，复杂度O(n)O(n)O(n)；但求约数有O(n)O(\sqrt{n})O(n)的算法，见如下代码：代码：#include<bits/stdc++.h>using namespace std;int divisor(int n) { int rs = 0; for(int i = 1; i * i <= ...
2020-03-21 18:50:07
1736
3
原创 蓝桥杯 PREV-19 九宫重排（bfs）
题目链接：http://lx.lanqiao.cn/problem.page?gpid=T42思路：既然是求最少次数，那就用bfs搜索；每次寻找下一种可能的状态，用map容器记录即可；代码：#pragma GCC optimize(2)#include<bits/stdc++.h>using namespace std;bool tag[10][10];...
2020-03-20 17:20:16
185
原创 蓝桥杯 PREV-17 约数倍数选卡片（对抗搜索）
题目链接：http://lx.lanqiao.cn/problem.page?gpid=T40思路：1.这是博弈问题的一般方法，用dfs进行对抗搜索，遍历所有可能，双方在每一步都选取最优步骤；2.单纯dfs会超时，我们知道约大的数，它的约数+倍数个数就相对可能越少，因此我们优先遍历大数即可；代码：#include<bits/stdc++.h>using name...
2020-03-16 15:44:09
134
原创 蓝桥杯 PREV-14 高僧斗法（Nim游戏）
题目链接：http://lx.lanqiao.cn/problem.page?gpid=T37思路：1.假设从111开始给这nnn个小和尚从左往右编号，那么编号为1,2,3,...,n1,2,3,...,n1,2,3,...,n；2.我们按照一奇一偶的方式给他们组队，结果为(1,2),(3,4),...,(n−1,n)(1,2),(3,4),...,(n-1,n)(1,2),(3,4...
2020-03-10 18:26:51
143
原创 HDU 1850 Being a Good Boy in Spring Festival（Nim游戏）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1850思路：1.Nim游戏的N-position（即先手必胜态）为nnn堆石子的异或和不为0；2.反之必败态为nnn堆石子的异或和为0，那么就需要给对手创造必败态；3.遍历每一堆扑克牌，假设当前堆扑克牌数量为aaa，算出其它n−1n-1n−1堆扑克牌数量的异或和为bbb，我们需要做的即让...
2020-03-10 17:17:30
90
原创 蓝桥杯 PREV-13 网络寻路（dfs）
题目链接：http://lx.lanqiao.cn/problem.page?gpid=T36思路：每一个点都可以作为起点，用dfs遍历路径条数；代码：#include<bits/stdc++.h>using namespace std;int n, m, s;long long ans;vector<int> G[10005];bool v...
2020-03-09 14:12:11
142
原创 团体程序设计天梯赛 L3-021 神坛（极角排序）
题目链接：https://pintia.cn/problem-sets/994805046380707840/problems/994805046577840128思路：1.一共n个点，对于每一个点我们都可以将它作为顶点，那么此点和其它n-1个点就会组成n-1个向量；2.n-1个向量中，我们任意选取两个向量都可以满足“选取三块石头”这个条件，但是我们现在的目标是面积最小，因此我们需要...
2020-03-08 15:42:27
462
原创 洛谷 P1372 又是毕业季I（公约数）
题目链接：https://www.luogu.com.cn/problem/P1372思路：假设默契值为xxx，那么根据贪心的想法，这kkk个人的序号为：x,2x,3x,...,kxx,2x,3x,...,kxx,2x,3x,...,kx；根据题意我们知道kx≤nkx\leq nkx≤n，即x≤nkx\leq \frac{n}{k}x≤kn；代码：#include<bi...
2020-03-07 16:48:46
181
原创 洛谷 P1865 A % B Problem（埃氏筛法）
题目链接：https://www.luogu.com.cn/problem/P1865思路：用埃氏筛法将[1,m][1,m][1,m]间的素数全部筛选出来，再用前缀和数组维护一下即可；代码：#include<bits/stdc++.h>using namespace std;const int maxn = 1e6 + 5;bool prime[maxn];...
2020-03-07 16:17:51
241
原创 洛谷 P1060 开心的金明（0/1背包）
题目链接：https://www.luogu.com.cn/problem/P1060思路：背包裸题代码：#include<bits/stdc++.h>using namespace std;const int maxn = 3e4 + 5;int n, m, v[maxn], p[maxn];int dp[maxn];int main() {#if...
2020-03-05 14:44:36
146
原创 2020牛客寒假算法基础集训营2
题目链接：https://ac.nowcoder.com/acm/contest/3003A题思路：求出三种情况的最多获胜局数即可代码：#include<bits/stdc++.h>using namespace std;int main() {#ifdef MyTest freopen("Sakura.txt", "r", stdin);#else...
2020-03-03 16:43:47
156
原创 蓝桥杯 BEGIN-4 Fibonacci数列
题目链接：http://lx.lanqiao.cn/problem.page?gpid=T4思路：接近蓝桥杯比赛了…最近有一些同学过来问我为什么java代码提交蓝桥的OJ报运行错误，而且都是拿这题来问的…所以写这篇就是想提醒一下初次使用OJ的java选手吧（虽然我是用C++的QAQ）1.在提交代码时不能加入package语句；2.类名的定义必须是public class Main...
2020-03-02 14:53:41
179
原创 HDU 2037 今年暑假不AC
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2037思路：贪心思想，将节目结束时间从小到大排序，依次选取可以观看的节目；代码：#include<bits/stdc++.h>using namespace std;struct Pro { int s, e; bool operator < ( Pro ...
2020-03-01 19:15:58
102
原创 蓝桥杯 PREV-25 城市建设（最小生成树）
题目链接：PREV-25 城市建设思路：1.先考虑没有码头的情况，使用kruskal算得最小生成树，但是需要检查一下所有点之间是否连通；2.而后考虑建码头的情况，所谓建码头的城市均可以互相连通，我们可以设立一个虚点，城市到虚点的边权即是建造码头的费用，再使用kruskal算法算得最小生成树的最小权值；3.我们取两种情况的最小值（注意第一种情况要保证连通）；4.在写最小生成树的时候...
2020-02-29 17:32:17
188
原创 蓝桥杯 PREV-42 九宫幻方（dfs）
题目链接：PREV-42 九宫幻方思路：直接dfs搜索所有可能，记录能形成幻方的矩阵即可；代码：#include<bits/stdc++.h>using namespace std;int cnt, vst[10];vector<vector<int> > mat(3, vector<int>(3)), ans(3, ve...
2020-02-29 16:02:22
151
原创 蓝桥杯 PREV-35 正则问题
题目链接：PREV-35 正则问题思路：题目不解释一下压根不知道x () |这些符号是做什么的…简单解释：x就是代表一个字符，题目要求最长字符数；()就是起到计算中的优先级作用；|代表或，既然取最长我们就需要找到或运算左右最长的字符；举例：1.xxx|xx就是3；2.(xxx)xx是5；3.(xxx|x)xx也是5；知道意思之后使用递归即可求得最长字符串；代码：...
2020-02-28 20:01:40
140
原创 蓝桥杯 PREV-50 对局匹配（贪心）
题目链接：PREV-50 对局匹配思路：1.我们将分数模kkk相同的放在一组，我们知道只有同一组的人才有可能相互匹配到；2.我们遍历每一组，按公差为kkk的分数顺序将该分数的人数组成一个序列，例如所有分数为[2,2,4,5,3,4,5,1,8][2,2,4,5,3,4,5,1,8][2,2,4,5,3,4,5,1,8]，kkk为222，则模kkk为000的一组分数为[2,2,4,4,...
2020-02-27 15:42:16
198
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人