PMYCQACF-CSDN博客

原创 Splay伸展树

百度百科现在我还是一个小蒟蒻,所以有关代码解释的,以后再说,你就只要知道有这个操作就好……具体请见yybdalao的博客

2017-10-18 22:38:09 408 1

原创考试总结

这几天心态很炸,特别是考试之后,每次都不理想,有时甚至想要不要接着走信息这条路,加油吧!CSDN记录1波,从蒟蒻逆袭!

2017-10-18 14:40:33 412

原创目标

近又到了休学季,要给自己指定一个小小的目标了!! 具体见图!最

2017-10-15 11:13:52 346

原创 [洛谷]P1311 选择客栈

原题首先暴力如果写的优秀,可以拿到60分,这里介绍两种暴力:40:#include<stdio.h>#include<stdlib.h>#include<math.h>#include<string.h>#include<algorithm>using namespace std;int color[200010],cost[200010];int main(){ int i

2017-10-15 10:28:51 410

原创 [CODE【VS】]江哥的DP题d

原题江哥解题报告：因为输入只有一个数，所以首先想到的是打表找规律int dp(){ int i,j; memset(f,0,sizeof(f)); for(i=1;i<=n;i++){ f[i]=1; for(j=1;j<i;j++) if(a[i]<a[j] && f[j]+1>f[i])

2017-10-05 11:07:14 399 1

原创 [CODE【VS】]江哥的DP题b

原题江哥解题报告：我们不妨按照江哥dalao的思路来写：设f(i,j)表示A中枚举到了第i个，B中枚举到了第j个，则： - a[i]=b[j] f(i,j)=f(i-1,j-1)+1;//如果相等就可以增加一条线 - a[i]≠b[j] f(i,j)=max{f(i-1,j),f(i,j-1),f(a1,b1)};a1,b1是要干什么呢？不妨看一看这张图找到当前b[j]所对应的a中b[j

2017-10-05 10:59:32 413 1

原创 [CODE【VS】]江哥的DP题a

原题先来一波江哥的解题报告杀这种方法十分的高深莫测，所以我们换一个容易理解的：f(i,j)表示前i个选j个，且第i个必选，那么就是江哥的转移方程P.S:但是不会前缀和优化！显然，这样的方法只能获得30分，数据十分的坑，那么优化如下：f(i,j,0)表示前i个里面选j个且第i个不选f(i,j,1)表示前i个里面选j个且第j个选f(i,j,0)=max{f(i-1,j,0),f(i-1,j,1)};

2017-10-05 10:47:38 344 1

原创【洛谷】P1627 中位数

原题考场想到了正解，但是依旧选择了暴力，这究竟是天意，还是人觉啊！为了表示内心的惋惜与痛却，还写什么解题思路啊！#include<stdio.h>#include<stdlib.h>#include<string.h>#include<math.h>#include<algorithm>#include<map>#include<set>#include<vector>#incl

2017-10-01 16:16:57 391

原创【洛谷】P1629 邮递员送信

原题因为邮递员每一次只能送一封信，所以他要跑回邮局拿完信后再去送信，我们可以把邮递员送信的过程分为两个部分：邮递员拿了信后送到2~nn户人家家里中送完信后再返回邮局所以我们可以通过两次Dijkstra（一次正图，第二次反向边）累积和之后输出答案，就AC了！但是要注意一些重要的细节啊！#include<stdio.h>#include<stdlib.h>#include<string.h>

2017-10-01 16:09:52 409

原创【洛谷】P1628 合并序列

原题这道题目身为普及一下难度，也是不虚其名啊！确实是一道大水题，大家如果想练字符串，就可以去用char或string刷一刷！完全就是一道纯模拟：#include<stdio.h>#include<stdlib.h>#include<string.h>#include<math.h>#include<algorithm>#include<map>#include<set>#include

2017-10-01 15:59:58 627 1

原题题目描述n 个小伙伴（编号从 0 到 n-1）围坐一圈玩游戏。按照顺时针方向给 n 个位置编号，从0 到 n-1。最初，第 0 号小伙伴在第 0 号位置，第 1 号小伙伴在第 1 号位置，……，依此类推。游戏规则如下：每一轮第 0 号位置上的小伙伴顺时针走到第 m 号位置，第 1 号位置小伙伴走到第 m+1 号位置，……，依此类推，第n − m号位置上的小伙伴走到第 0 号位置，第n-m+1 号

2017-09-26 21:32:31 549

原创【洛谷】P1966 火柴排队

原题题目描述涵涵有两盒火柴，每盒装有 n 根火柴，每根火柴都有一个高度。现在将每盒中的火柴各自排成一列，同一列火柴的高度互不相同，两列火柴之间的距离定义为： ∑(ai-bi)^2其中 ai 表示第一列火柴中第 i 个火柴的高度，bi 表示第二列火柴中第 i 个火柴的高度。每列火柴中相邻两根火柴的位置都可以交换，请你通过交换使得两列火柴之间的距离最小。请问得到这个最小的距离，最少需要交换多少次？

2017-09-26 21:29:43 575 1

原创 [洛谷]P1080 国王游戏

原题题目描述恰逢 H 国国庆，国王邀请 n 位大臣来玩一个有奖游戏。首先，他让每个大臣在左、右手上面分别写下一个整数，国王自己也在左、右手上各写一个整数。然后，让这 n 位大臣排成一排，国王站在队伍的最前面。排好队后，所有的大臣都会获得国王奖赏的若干金币，每位大臣获得的金币数分别是：排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数，然后向下取整得到的结果。国王不希望某一个大臣获得特别多的

2017-09-23 21:17:40 665 2

原创 [洛谷]P1083 借教室

原题题目描述在大学期间，经常需要租借教室。大到院系举办活动，小到学习小组自习讨论，都需要向学校申请借教室。教室的大小功能不同，借教室人的身份不同，借教室的手续也不一样。面对海量租借教室的信息，我们自然希望编程解决这个问题。我们需要处理接下来n天的借教室信息，其中第i天学校有ri个教室可供租借。共有m份订单，每份订单用三个正整数描述，分别为dj,sj,tj，表示某租借者需要从第sj天到第tj天租借教室

2017-09-23 20:23:15 497 1

原创 [洛谷]P1082 同余方程

原题题目描述求关于 x 的同余方程 ax ≡ 1 (mod b)的最小正整数解。输入输出格式输入格式：输入只有一行，包含两个正整数 a, b，用一个空格隔开。输出格式：输出只有一行，包含一个正整数 x0，即最小正整数解。输入数据保证一定有解。输入输出样例输入样例#1：3 10输出样例#1：7说明【数据范围】对于 40%的数据，2 ≤b≤ 1,000；对于 60%的数据，2 ≤b≤ 50,

2017-09-23 17:09:52 469

原创【洛谷】P1079 Vigenère 密码

原题这是NOIP2012年提高组的Day1的第一题T1,自然不会有很难,那么究竟……有多水呢?题目描述16 世纪法国外交家 Blaise de Vigenère 设计了一种多表密码加密算法――Vigenère 密码。Vigenère 密码的加密解密算法简单易用，且破译难度比较高，曾在美国南北战争中为南军所广泛使用。在密码学中，我们称需要加密的信息为明文，用 M 表示；称加密后的信息为密文，用C 表示

2017-09-23 15:18:44 544

原创【洛谷】P1582倒水

原题题目描述一天，CC买了N个容量可以认为是无限大的瓶子，开始时每个瓶子里有1升水。接着~~CC发现瓶子实在太多了，于是他决定保留不超过K个瓶子。每次他选择两个当前含水量相同的瓶子，把一个瓶子的水全部倒进另一个里，然后把空瓶丢弃。(不能丢弃有水的瓶子)显然在某些情况下CC无法达到目标，比如N=3,K=1。此时CC会重新买一些新的瓶子(新瓶子容量无限，开始时有1升水)，以到达目标。现在CC想知道，最少

2017-09-16 15:51:08 403

原创 9.16考试【广东省选】

作为一只蒟蒻，站在了一大堆大佬之中，所以对于本次考试我没有丝毫的信心，但是我依旧打算来一发题解报告本次考试有四道题目，都是广东省选的老题目，当然有的很水，有的很难，我们按照先易后难的顺序来发表。T4象棋比赛

2017-09-16 15:42:01 290

原创【NOIOPJ】P7614 最低通行费

原题描述一个商人穿过一个 N*N 的正方形的网格，去参加一个非常重要的商务活动。他要从网格的左上角进，右下角出。每穿越中间1个小方格，都要花费1个单位时间。商人必须在(2N-1)个单位时间穿越出去。而在经过中间的每个小方格时，都需要缴纳一定的费用。这个商人期望在规定时间内用最少费用穿越出去。请问至少需要多少费用？注意：不能对角穿越各个小方格（即，只能向上下左右四个方向移动且不能离开网格）。输入第

2017-09-14 19:10:34 554 1

原创【洛谷】P1525 关押罪犯

原题题目描述S 城现有两座监狱，一共关押着N 名罪犯，编号分别为1~N。他们之间的关系自然也极不和谐。很多罪犯之间甚至积怨已久，如果客观条件具备则随时可能爆发冲突。我们用“怨气值”（一个正整数值）来表示某两名罪犯之间的仇恨程度，怨气值越大，则这两名罪犯之间的积怨越多。如果两名怨气值为c 的罪犯被关押在同一监狱，他们俩之间会发生摩擦，并造成影响力为c 的冲突事件。每年年末，警察局会将本年内监狱中的所有

2017-09-13 22:24:37 375

原创【洛谷】P1541 乌龟棋

原题题目背景小明过生日的时候，爸爸送给他一副乌龟棋当作礼物。题目描述乌龟棋的棋盘是一行N个格子，每个格子上一个分数（非负整数）。棋盘第1格是唯一的起点，第N格是终点，游戏要求玩家控制一个乌龟棋子从起点出发走到终点。乌龟棋中M张爬行卡片，分成4种不同的类型（M张卡片中不一定包含所有4种类型的卡片，见样例），每种类型的卡片上分别标有1、2、3、4四个数字之一，表示使用这种卡片后，乌龟棋子将向前爬行相应的

2017-09-13 22:17:01 299

原创【洛谷】P1540 机器翻译

原题这道题目就是一道十分简单的模拟（这还用说？）#include<stdio.h>#include<stdlib.h>#include<string.h>#include<math.h>#include<algorithm>using namespace std;int flag[1010],a[1010];int main(){ int i,j,k,n,m,ans=0,del

2017-09-10 11:59:25 814

原创最近有点爆炸

最近的心态有点爆炸啊，老是码代码码到一半就疯掉了，心里老是想着别的东西，然后还有学习上的一些事情，再加上11月份就要考NOIP了，怎么办啊！！！QAQ问题在于我到现在为止还有好多知识点没学啊！！！

2017-09-07 20:25:22 326 1

原创 [HDU]1520 Anniversary party

这道题目其实就是一个裸的树形DP，和洛谷P1352 没有上司的舞会一模一样，只是要加一个读入判断罢了[英文不好导致错了3回，每次都是Wrong Answer，就是没有加这个判断！！！]#include<bits/stdc++.h>using namespace std;int dp[6010][2],fa[6010],v[6010],n;void tree_dp(int i){ in

2017-09-01 23:12:33 303

原创树形DP入门（一）『ツリーとしては』

这次我们谈论的是树形DP，它是一种神奇的动态规划，它的模型建立在树上，所以称之为树形DP。树形DP的成立性：树是一种奇妙的结构，它一定满足最优子结构和无后效性（因为它是树啊！他的状态一定会由它的子树的来[或者说它一定会从它的父节点得来]）。树形DP实现的方法：递归！！！因为它是一棵树，所以对应的有两种方式：从根到叶子结点：对应线性结构的从前往后。从叶子结点到根：对应线性结构的从后往前所以采用递

2017-09-01 13:09:25 319

原创【洛谷】P1440 求区间最小值

传送门这道题目一眼看去，先想到的必然是暴力，但是数据范围m≤n≤2000000m≤n≤2000000太吓人，所以放弃这个想法，那么我们一步步分析样例是如何得来的：/*6 27 8 1 4 3 2077113*/因为第一个数前面没有数，输出0第二个数之前的最小数为7，输出7第三个数之前2个的最小数为7，输出7第四个数之前2个的最小数为1，输出1第五个数之前2个的最小数为1，输

2017-08-29 23:31:19 475

原创【洛谷】P1120 小木棍[数据加强版]

传送门这道题目因为加强了数据，所以博客以前的题解不能够满足这道题目的时间复杂度，当然还是使用暴力，但是得多一点剪枝。剪枝1：将木棍从大到小排序，这样搜索就可以少一些可能性。剪枝2：从最大的一根木棍开始枚举，一直到木棍长度之和/2，因为最糟糕的情况就是每一根木棍只与自己搭配，所以这种情况在最后输出，再就是两两搭配，所以答案就是总和/2，这样可以减去差不多一半的复杂度。剪枝3：如果前t−1t-1个

2017-08-29 22:50:48 616

原创后缀表达式转中缀表达式

这个专题很迷，因为这种东西很少使用，一般都是中缀转后缀（容易计算），但是有一些bt的题目总是喜欢这样倒着出题，所以适当的了解还是有必要的。题目描述给出按后缀表示法输入的一个算术表达式，表达式中只有26个大写英文字母和加减乘除四个运算符号，表达式的长度<=50，表达式以#号结束。请你编程求出它的等价中缀表达式。输入输出格式输入格式：输入文件只有一行，就是后缀表达式。输出格式：输出文件只有一行，就是

2017-08-24 09:16:38 496

原创关节点及重连通图

这个内容为什么想放在这个时候就放出来呢？因为刚刚才把TOP排序讲完，所以我们跳过关键路径『有什么关联吗？』，直接进入关节点和重联通图。一、关节点：又称割点，是维系一个图能够连通的节点（就是说没有这个节点，这个图就不连通），若从连通图中删除点V，就会使这个图割裂成多个子图，则称V点为该图的关节点。二、重连通图：没有关节点的图。【补充：其充分必要条件为任意两点都在一个圈上！】以上是这两个重点的概

2017-08-22 23:50:48 3305

原创黄金海岸『Gold Beach』之Wet'n Wild Water Park

今天我们介绍的是黄金海岸的一个water park，叫做疯狂水乐园。当然接下来的内容需要使用英语完成『无奈之作业』，就让我们开启这一段愉快的旅程吧！The Wet'n Wild Water Park is on the Foursquare.The telephone number of the park is +61 133 386.If you think the blog isn't very

2017-08-19 16:30:48 908

原创约瑟夫问题『数据加强版』

约瑟夫问题在大部分情况中是一道水题，但是如果把数据加强一点，可能会难倒一片人，所以今天来介绍如何A掉这题！『这里介绍的数据范围n,m均在30000以内』#include<stdio.h>#include<stdlib.h>#include<string.h>#include<math.h>#include<algorithm>#include<vector>#include<queue>

2017-08-18 05:46:10 586

原创『洛谷T7835』士兵站队问题

题目描述有N名士兵（1<=N<=26），编号依次为A，B，C，……进行队列训练时，指挥官要把一些士兵从高到矮依次排成一行，但现在指挥官不能直接获得每个士兵的身高信息，只能获得“P1比P2高”这样的比较结果（P1，P2∈{A，B，…Z}，记为P1>P2），如“A>B”表示A比B高。编一程序，根据所得到的比较结果求出符合条件的排队方案。注：比较结果中没有涉及到的士兵不参加排队。例如，设有3个士兵，A、B

2017-08-15 21:21:07 992

原创重点公告！！！

因为博客中有一些题目是在一个名为洛谷的Onlinejudge平台上的团队中的，所以大家如果想刷题，就得加入某些团队，这下面是两个： 1 2 有的团队是本校私有，不便公开，希望大家可以多多支持，谢谢！

2017-08-15 16:11:16 272

原创拓扑（TOP）排序

今天要讲的是图论之中一个很重要的东西，叫做拓扑排序，又称top排序（下文中使用这个简称），但是我们得先介绍一下AOV网。如果有想了解官方学术语言的，戳这里。这里，为了方便，我们使用一些简洁的定义，即用顶点表示活动，用边表示活动的先后顺序的有向图。拓扑排序，是指在AOV网中，把所有的点按照它们的逻辑关系排成一个线性的序列，是每个点的前驱都排在它前面，称之为top序列。方法如下：选择一个入度为

2017-08-15 16:08:00 2522

原创【洛谷】P1626象棋比赛

题目描述有N个人要参加国际象棋比赛，该比赛要进行K场对弈。每个人最多参加两场对弈，最少参加零场对弈。每个人都有一个与其他人不相同的等级（用一个正整数来表示）。在对弈中，等级高的人必须用黑色的棋子，等级低的人必须用白色的棋子。每个人最多只能用一次黑色的棋子和一次白色的棋子。为增加比赛的可观度，观众希望K场对弈中双方的等级差的总和最小。比如有7个选手，他们的等级分别是30，17，26，41，19，38，

2017-08-02 23:01:28 1120 1

原创并查集（题解）

这里是练习并查集的一些题目和代码： 1.POJ1611#include<iostream>#include<stdio.h>#include<stdlib.h>using namespace std;int f[100010];int gi(){ char c=getchar();int f=1,sum=0; while((c>'9' || c<'0') && c!='-

2017-07-30 16:11:30 313

原创复习计划（第一次筛选）

为了应对万恶的考试，为了帮助大家顺利度过这场难关，cjoier_gjh特地为此写了一篇博客（其实是为了zz和xhy）。话不多说，来看看复习计划表吧（计划考试为2017.7.29下午14:10,从16:00开始复习）！重点还是在落实！！！

2017-07-28 15:38:57 362 1

原创二叉平衡树（AVL树）

在了解AVL树前，需要具备以下两点只知识：普通二叉树 2. 二叉排序树这时，我们可以进入到平衡树的学习中了，但在学习之前，有一个问题，何为平衡树？很多的参考书中说到，平衡树就是每一个节点的平衡因子的值只能为0，±1。那么平衡因子又是什么？平衡因子，是左右子树节点个数的差。（这样就容易理解了吧！(⊙﹏⊙)）这里涉及到了平衡树的插入操作，那么该如何对于每一个插入的数进行操作处理呢？这里的分类讨论

2017-07-28 15:19:41 546 2

原创二叉排序树浅讲

二叉排序树是一种树形结构，这种树有如下几种性质若左子树不空，则左子树所有节点值均小于其根节点值若右子树不空，则右子树所有节点值均大于其根节点值其左右子树也分别是二叉排序树有了这些性质，我们便可以证明出二叉排序树的中序遍历必然有序：下图是一个普通的二叉排序树：那么二叉排序树就可以在OI的道路上有所应用，当然以一些小牛的本领，自然只能够使用其排序，毕竟这只是二叉排序树浅讲……所以我

2017-07-26 15:02:36 427

原创堆

堆是一棵完全二叉树，何为完全二叉树？参见。有了这个定义，我们就可以将堆分成两种，一个叫小根堆，另一个叫大根堆，顾名思义，小根堆就是堆最小，大根堆就是根最大。堆的性质：堆具有所有完全二叉树的性质堆的左右子树也是一个堆。这里我们引入一个例题：【模板】堆，这一道题目就是一道裸题，很容易想到使用堆，那么堆有什么基本操作？#include<bits/stdc++.h>using names

2017-07-18 17:07:03 314

转圈游戏代码

stick.txtas

空空如也