我不是匠人

未归档

KMP算法(1) LeetCode(1) Manecher算法(1) PAT数据结构与算法题目集(中文)(6) PAT甲级(66) POJ(1) STL标准模板库(6) ————ACM————(1) 二分图(2) 二分查找(3) 二叉树(5) 伪随机数(1) 分治(2) 动态规划(1) 哈夫曼树(3) 哈希散列(6) 复试上机(50) 字符串(31) 并查集(4) 广度优先搜索(3) 技巧题(2) 拓扑排序(3) 排序(12) 数字图像处理(1) 数组(3) 数论基础(15) 最小生成树(1) 最短路径(10) 最近公共祖先(1) 机器学习(9) 机器学习算法(6) 枚举(1) 树状数组(1) 模拟(12) 深度优先搜索(7) 程序员的故事(1) 笔试面试(9) 简单题(18) 线段树(1) 编程语言(4) 英语(1) 贪心算法(4) 递归(2) 链表(9) 题解(6) 高精度(4)

/ 注册

全部文章 / 未归档（共126篇）

1126 Eulerian Path （25 分）

题目很容易懂，就是判断一个无向图是否是欧拉图，或者半欧拉图，或者不是欧拉图。有两个输出，第一行输出每个顶点的度，其实是提示从度这里入手。其次有个细节需要注意的是，欧拉图需要连通，所以要判断整个图是否连通。因为我自己写图的深度太弱，所以一上去提交就出错了。这里有两种找图深度的写法。 AC代码里...

2019-02-26

0 651

1058 A+B in Hogwarts （20 分）

这道题可以说是相当简单了，我还是有个测试点没过，后来想了一下才弄懂。最开始的时候，我把abc，xyz都设定为整形，然后后面有计算的部分，而计算中没有自动转换为长整形的暗示，所以导致在计算sum的时候溢出了，最后结果当然也是错误的。所以以后得到一个教训，凡是需要用到长整型的题目，全部改为用long...

2019-02-25

0 406

1092 To Buy or Not to Buy （20 分）

这道题是散列的题，可以用hash数组解决，但是学过标准库之后就变懒了，懒得把字符转换为下标，还要判断是数字还是大小写字母，所以索性就用map直接映射了。然后本题还用到了C++11标准中的基于范围的遍历，特别好用。 #include<cstdio> #include<iostrea...

2019-02-25

0 373

任意个数异或最大值（DFS）

问题：在N<=10个数里面选任意个数，使得他们的xor值最大思路1：最简单的办法是O( <math> <semantics> <mrow> <msup> <mn> ...

2019-02-18

0 571

1063 Set Similarity （25 分）

考查set的模板题要注意的地方是查询两个集合中是否有相同元素时，可以只用一次循环，同时利用find函数来实现。如果使用map来映射会超时。注意： 1.set也有数组形式 2.set遍历时只能迭代 3.迭代取值用*it #include<cstdio> #include<set...

2019-02-16

0 565

1016 Phone Bills （25 分）

我之所以直接把代码贴上来，而没有太多解释，不是为了解析这道题目，而是为了方便我以后自己查看。这道题花了两个小时都没做出来，最后看了答案才知道，可以用map与向量的映射，这是第一次用，所以学到了。其次是不知道怎么算时间的差值和根据每个阶段的费用求结果。方法有2： 1.直接求起始日期时间与终止日期的...

2019-02-16

0 398

1029 Median （25 分）

真是是一道很搞人的题 1.数据能从1开始的，好确定中间位置 2.第一个数组离线，第二个数组在线处理 #include<cstdio> const int maxn = 2e5+10; const int INF = 0x7fffffff; int a[maxn]; int main(...

2019-02-15

0 0

1022 Digital Library （30 分）

注意： 1.书名是7位数，需要补零。 2.题目要求按照从小到大输出书名，所以用set比较好。 3.关键字的读入技巧要学到。 4.对参数使用引用会稍微快点。 //map的应用 #include<cstdio> #include<iostream> #include<m...

2019-02-15

0 549

拓扑排序（最长路径）

题目链接：计蒜客每次记录出度为零的顶点，加上出度边的最大值，作为下一个到达顶点的最大值，不断更新dp数组，然后从数组中找到一个最大值，就是整个图的最长路径。详情请观看B站大佬视频 #include<cstdio> #include<utility> #include&l...

2019-02-14

0 2196

1021 Deepest Root （25 分）

DFS 似乎找到了PAT的一些规律，如果考的是数据结构里面的东西，就很少有坑。而如果考的模拟或者简单的题，就有很多边界条件。使用了两个全局变量，记录每个起点遍历的最大深度和所有顶点的最大深度。一次性AC，还是比较开心的！版本1 只有入度为1的点才可能是最深的根节点，已经尽力优化了，但是还...

2019-02-13

0 336