- 博客(86)
- 收藏
- 关注
RSS订阅
原创 想对你说
我觉得大学四年生就是这么一个阶段啊 就是你大一的时候你知道你自己不知道 大一的时候啊大一的时候你知道你自己不知道 大二的时候你不知道你自己不知道 大三的时候你不知道你自己知道 大四的时候就是你知道你自己知道 大一的时候是因为你知道自己进入一个新的领域或者是你的目标就是上大学，对自己的未来，只是有一个小小的起步，不是有个特别明确的规划，所以说这个时候我们想向社会迈出一个小脚儿，或者是...
2018-03-22 22:43:17
329
原创 启程
启程现在我身处一所普通的院校，软件工程专业，已经大二。我渴望学技术，也坚信技术也许真的能改变世界。可能真的想学的太多了就导致学了很多东西。 注意我说的学，仅仅是了解，没什么深入了解。 我觉得我就是那种浅尝即止的那种人，有种什么都想学什么都没学的感觉。大一一开学就加入了我们学校的ACM团队，跟着团队进行寒假暑假集训。正式因为我是那种浅尝的人，导致一年半了在ACM竞赛上还没什么成绩。只能培训17级...
2018-03-22 22:39:42
352
原创 Dafny学习
Dafny Dafny: A Language and Program Verifier for Functional Correctness Dafny是用来更好的写出正确代码的语言 最简单的方法是在 这里 在线的进行程序验证 下边看几个例子简单的验证method Add(x:int,y:int) returns (r:int) requir...
2018-07-12 18:11:01
3256
原创 中科院软件所实习 DAY1
DAY1 早上7:36到达中国科学院软件所，与导师约定在9点来，我可是怕自己找不到路，就提前来了。 来了就先跟导师聊几句，之后导师带着我看看 计算机科学国家重点实验室 实验室的氛围很不错，大家都在忙自己的事，不愧是中科院的研究所！ 导师人很好，但是好像很忙的样子，不过虽然他很忙，还是带我去做实习生的登记，去看工位，实验室的领导真的很严格，完全按照登记表上的要求走，...
2018-07-12 18:01:28
4432
2
原创 T1
#include<iostream>#define N 10000using namespace std;int vis[N];int n,m;char path[N];void dfs(int now,int step){ if(step == 0 ) { path[0] = '['; } else { path[...
2018-06-30 11:54:41
213
原创 数论
比赛常用到的数论知识总结 //0.素数判定bool prime(int x) { for(int i=2; i*i<=maxn; i++) //降低时间复杂度 if(x%i==0) return false; return true;}//1.筛法素数打表void getprime(int n) { int ...
2018-04-06 23:47:17
579
3
原创 计算几何基础
主要运用到向量间的点乘和叉乘. const double eps = 1e-9; // 1.精度 inline int sgn(double x) { if(abs(x) < eps) return 0; else return x < 0 ? -1 : 1;}//向量 typedef struct Vector{ double x,y;...
2018-04-04 22:06:28
164
1
原创 PAT L2-011 玩转二叉树
PAT L2-011 玩转二叉树转载链接 如果可以的话，可以点链接打赏一下这位学姐，写的挺不错的。 给定一棵二叉树的中序遍历和前序遍历，请你先将树做个镜面反转，再输出反转后的层序遍历的序列。所谓镜面反转，是指将所有非叶结点的左右孩子对换。这里假设键值都是互不相等的正整数。 输入格式：输入第一行给出一个正整数N（<=30），是二叉树中结点的个数。第二行给出其中序遍历序列。第三...
2018-03-22 22:47:21
212
原创 PAT L2-006 树的遍历
PAT-L2-006-树的遍历参考博客 给定一棵二叉树的后序遍历和中序遍历，请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。输入格式：输入第一行给出一个正整数N（<=30），是二叉树中结点的个数。第二行给出其后序遍历序列。第三行给出其中序遍历序列。数字间以空格分隔。输出格式：在一行中输出该树的层序遍历的序列。数字间以1个空格分隔，行首尾不得有多余空格。输...
2018-03-22 22:46:05
243
原创 已知前序与中序输出后序
转载链接 如果可以的话，可以点链接打赏一下这位学姐，写的挺不错的。 已知前序（先序）与中序输出后序： 前序：1, 2, 3, 4, 5, 6（根左右） 中序：3, 2, 4, 1, 6, 5（左根右） 分析：因为前序（根左右）最先出现的总是根结点，所以令root为前序中当前的根结点下标（并且同时把一棵树分为左子树和右子树）。start为当前需要打印的子树在中序中的最左边的下标，end...
2018-03-22 22:45:09
640
原创 已知后序与中序输出前序
已知后序与中序输出前序转载链接 如果可以的话，可以点链接打赏一下这位学姐，写的挺不错的。 后序：3, 4, 2, 6, 5, 1（左右根） 中序：3, 2, 4, 1, 6, 5（左根右） 分析：因为后序的最后一个总是根结点，令i在中序中找到该根结点，则i把中序分为两部分，左边是左子树，右边是右子树。因为是输出先序（根左右），所以先打印出当前根结点，然后打印左子树，再打印右子树。左子树...
2018-03-22 22:44:45
430
原创 PAT L2-005 集合相似度
PAT-L2-005-集合相似度给定两个整数集合，它们的相似度定义为：Nc/Nt*100%。其中Nc是两个集合都有的不相等整数的个数，Nt是两个集合一共有的不相等整数的个数。你的任务就是计算任意一对给定集合的相似度。输入格式：输入第一行给出一个正整数N（<=50），是集合的个数。随后N行，每行对应一个集合。每个集合首先给出一个正整数M（<=104），是集合中元素的个数；然后...
2018-03-22 22:42:47
216
原创 PAT L2-003月饼
PAT-L2-003月饼月饼是中国人在中秋佳节时吃的一种传统食品，不同地区有许多不同风味的月饼。现给定所有种类月饼的库存量、总售价、以及市场的最大需求量，请你计算可以获得的最大收益是多少。注意：销售时允许取出一部分库存。样例给出的情形是这样的：假如我们有3种月饼，其库存量分别为18、15、10万吨，总售价分别为75、72、45亿元。如果市场的最大需求量只有20万吨，那么我们最大收益策略应该...
2018-03-22 22:41:58
176
原创 PAT L2-002 链表去重
PAT-L2-002-链表去重给定一个带整数键值的单链表L，本题要求你编写程序，删除那些键值的绝对值有重复的结点。即对任意键值K，只有键值或其绝对值等于K的第一个结点可以被保留。同时，所有被删除的结点必须被保存在另外一个链表中。例如：另L为21→-15→-15→-7→15，则你必须输出去重后的链表21→-15→-7、以及被删除的链表-15→15。 输入格式：输入第一行包含链表第一个结...
2018-03-22 22:40:35
238
原创 PAT L2-008 最长对称子串
PAT-L2-008-最长对称子串对给定的字符串，本题要求你输出最长对称子串的长度。例如，给定”Is PAT&TAP symmetric?”，最长对称子串为”s PAT&TAP s”，于是你应该输出11。 输入格式：输入在一行中给出长度不超过1000的非空字符串。输出格式：在一行中输出最长对称子串的长度。输入样例： Is PAT&TAP symm...
2018-03-22 22:38:51
215
原创 Dijkstra 优先队列优化
struct ac{ int v,dis; ac(){} ac(int _v,int _dis):v(_v),dis(_dis){} bool operator < (const ac& x)const{ if(dis==x.dis) return v>x.v; return dis>x.dis; }};vector<ac>Adj...
2018-02-12 21:45:35
332
原创 Kurskal算法
struct Edge{ int u,v,cost;};int pre[maxn];Edge e[maxv];void init(int g){ for(int i=0;i<=g;i++){ pre[i] = i; }}int Find(int x){ int r = x; while(r!=pre[r]) ...
2018-02-12 21:39:32
523
原创 Prim算法
typedef struct ac{ int v,cost; ac(){} ac(int _v,int _c):v(_v),cost(_c){}};vector<ac> Adj[maxn];int G[maxv][maxv];int d[maxn],n,m;bool vis[maxn];int Prim(int v0){ int sum = 0...
2018-02-12 21:37:26
276
原创 PAT 1030. Travel Plan Dijkstra多边权
A traveler's map gives the distances between cities along the highways, together with the cost of each highway. Now you are supposed to write a program to help a traveler to decide the shortest path b...
2018-02-12 21:15:35
247
原创 Dijkstra多权值
多边权一般有三种 1 路径多条边权2 增加点权3 直接询问有多少条最短路这就是Dijkstra的变形， 注意在这三种都是在最短路的基础上的，比如增加边权花费， 问在如果有多条最短路径情况下 最小花费是多少， 或者增加点权， 每个顶点都有一定物资，询问有多条最短路的情况下物资最多为多少， 还有就是直接问 最短路有多少条一般解决这类问题的时候都会有三种不同的思路。一种是在求最短的同时直接算出来题目所问...
2018-02-12 21:11:02
479
原创 PTA 7-10 列车调度
火车站的列车调度铁轨的结构如下图所示。两端分别是一条入口（Entrance）轨道和一条出口（Exit）轨道，它们之间有N条平行的轨道。每趟列车从入口可以选择任意一条轨道进入，最后从出口离开。在图中有9趟列车，在入口处按照{8，4，2，5，3，9，1，6，7}的顺序排队等待进入。如果要求它们必须按序号递减的顺序从出口离开，则至少需要多少条平行铁轨用于调度？输入格式：输
2018-02-02 16:37:34
1822
原创 Dijkstra算法
Dijkstra算法的具体实现：设置集合S存放以被访问的顶点，然后执行n次以下两个步骤(n为顶点数): 1.每次从集合V-S(即没有访问过的城市)中选择与起点s的最短距离最小的一个顶点(记为u)，访问并加入到集合S中(即访问过)。2.之后以顶点u为中介点，优化起点s与所有从u能到达的顶点v之间的最短距离。解决1和2的方法。集合S可以用一个bool类型的vis[]来实现，
2018-01-28 12:16:43
335
原创 二分搜索
怎么说呢，二分我之前就是太害怕它了，开始学的时候在知乎上到二分有64种写法，一下被吓着了，才一直搁到现在才学。主要思想大家都明白，就是代码实现起来有问题。个人认为，二分最后可以归结为三种问题(假设序列不下降，参数均为区间[l,r])：1. 是否存在x。如果A[mid]==x 即为找到，返回mid位置即可；如果A[mid]>x说明当前位置大了，可以确定x在[l,mid-1]区
2018-01-23 16:31:50
175
原创 C++面向对象多态与虚函数
首先要明白多态指的什么， 通俗点的话是 同一函数实现不同的功能，这点区别于多态。我个人理解的多态就是一些功能不同的函数可以使用统一函数名，也就是一个函数名可以调用内容不同功能不同的函数。比如，将父对象设置成为更多的他的子对象相等的功能，赋值之后，父对象就可以根据当前赋值给它的子对象的特性以不同的方式运作.具体看这个代码(纯虚函数)，#include using namespa
2018-01-02 20:38:03
402
原创 C++继承与派生访问权限
观察下边一段代码：class A{ public: void f1(); int i; protected: void f2(); int j; private: int k;};class B:public A{ public: void f3(); protected: int m; private: int n;};class C:p
2018-01-01 21:05:32
1769
原创 C++面向对象友元函数运算符的重载
以课本复数类为例：具体看代码，哪里不懂可以评论留言。#include using namespace std;class Complex{ public: Complex(){real = 0,imag = 0;} Complex(double r=0,double i=0):real(r),imag(i){} void display(); frie
2018-01-01 17:33:55
440
原创 Codeforces Round #441 Div. 2 B
B. Divisiblity of Differencestime limit per test1 secondmemory limit per test512 megabytesinputstandard inputoutputstandard outputYou are given a multiset of n integers.
2017-10-16 22:59:40
188
1
原创 Codeforces Round #441 Div. 2 A
A. Trip For Mealtime limit per test1 secondmemory limit per test512 megabytesinputstandard inputoutputstandard outputWinnie-the-Pooh likes honey very much! That is why he
2017-10-16 21:53:59
219
原创 Codeforces Round #439 (Div. 2) A题 he Artful Expedien
A. The Artful Expedienttime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputRock... Paper!After Karen have found the det
2017-10-07 14:44:47
239
原创 Codeforces Round #438 (868B) B Race Against Time
传送门 Have you ever tried to explain to the coordinator, why it is eight hours to the contest and not a single problem has been prepared yet? Misha had. And this time he has a really strong excuse: he f
2017-10-05 21:22:22
204
原创 51nod 1006 最长公共子序列Lcs
给出两个字符串A B，求A与B的最长公共子序列（子序列不要求是连续的）。 比如两个串为：abcicba abdkscabab是两个串的子序列，abc也是，abca也是，其中abca是这两个字符串最长的子序列。 Input 第1行：字符串A 第2行：字符串B (A,B的长度 <= 1000) Output 输出最长的子序列，如果有多个，随意输出1个。 Input示例 abcicba
2017-10-04 12:50:50
184
原创 C++大数加法乘法
string add(string a,string b){ string res; reverse(a.begin(), a.end()); reverse(b.begin(), b.end()); int i=0; int m,k=0; while(a[i]&&b[i]){ m = a[i]+b[i]+k-2*'0';
2017-10-04 11:30:48
539
原创 hpu1414: Kick Ass [字符串]
传送 1414: Kick Ass [字符串] 时间限制: 1 Sec 内存限制: 128 MB提交: 117 解决: 35 题目描述你玩过一个叫做”Kick Ass - Destroy the web”的游戏吗？如果你想玩的话当然，你没有玩过也没关系，这个游戏是通过js来加载一个飞船，让你可以通过控制它发射子弹来摧毁网页上的元素，从而获得分数。我们知道HTML是超文本标记语言，简单地说就是
2017-09-12 18:03:07
273
原创 hpu 1410 火星情报局 [数学] (哥德巴赫猜想)
题目链接：传送 1410: QAQ & 火星情报局 [数学] 时间限制: 1 Sec 内存限制: 128 MB提交: 336 解决: 74 题目描述QAQ~超级喜欢看火星情报局，每周六都是他一周中最期待的一天，QAQ喜欢和自己一样心愿是“世界和平”的薛之谦，喜欢“一言不合就飙车”的宇哥，喜欢“再扯的提案都能升华为鸡汤”的汪涵局长….当然也喜欢的里面各种各样奇葩有趣的提案…..最近 K 星颁布
2017-09-12 16:28:42
657
原创 简单的背包问题
题目连链接: 1279: 简单的背包问题 时间限制: 1 秒 内存限制: 32 MB 提交: 411 解决: 36 提交 状态 题目描述相信大家都学过背包问题了吧，那么现在我就考大家一个问题。有n个物品，每个物品有它的重量w，价值v，现在有一个容量为W的背包，问你在不超过背包容量的情况下，能装下的物品的最大价值是多少。T <= 100代表样例数 1 <= n <= 100 物品数
2017-09-05 19:36:01
339
原创 欧拉函数
f(x) = x(1-1/p1)(1-1/p2)….(1-1/pn) p1..pn表示x的质因数 模板代码：#include<iostream>#include<algorithm>#include<queue>#include<cstdio>#include<cstring>#define CLR(a,b) memset(a,b,sizeof b)#define inf 0x3f3
2017-08-21 12:24:19
240
原创 SPFA 模板
#include<iostream>#include<cstdio>#include<queue>#include<cstring>#include<algorithm>#define inf 0x3f3f3f3f#define CLR(a,b) memset(a,b,sizeof a)using namespace std...
2017-08-16 15:14:27
535
原创 hdu1841 Find the Shortest Common Superstring 两遍KMP
hdu1841 Find the Shortest Common Superstring 两遍KMP问题描述 :The shortest common superstring of 2 strings S1 and S2 is a string S with the minimum number of characters which contains both S1 and S2 as a seq
2017-08-15 11:42:23
565
原创 KMP算法
KMP算法 重点理解nex数组的是什么作用:nex[i]表示前i项的最大公众前后缀的长度,也就是匹配失败的时候字符串匹配过程中失配情况下可以向前多跳几个字符。 比如说一个字符串 “ABABAA”的nex数组. 重点来了！！！ “A” nex[0] = 0 没有最大公共前后缀 “AB” nex[1] = 0 也没 “ABA” 最大公共前后缀为
2017-08-14 23:22:08
430
2
原创 大整数阶乘
大整数阶乘 参考某位大神的博客,时间久了找不到链接了,侵权删。其核心思想就是把计算结果每一位上的数字保存到一个数组成员中，例如： 把124保存至数组中，保存结果应该是result[0] =4；result[1] =2；result[2] =1 把整个数组看成一个数字，这个数字和一个数相乘的时候，需要每一位都和这个乘数进行相乘运算还需要把前一位的进位加上。写法如下：int 结果 = resu
2017-08-14 23:01:18
1586
1
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人