Palace_-CSDN博客

原创【拓扑排序】HNOI2015菜肴制作

思路：总结题意，在满足某某一定在某某之前的约束条件下，使编号小的尽量靠前。很容易想到用小根堆求拓扑序（然而这是错的），很容易举出反例。正确的思路是求字典序最小的拓扑序，这就需要反向建图，用大根堆求反着的拓扑序。（不要忘记初始化……）代码：（码风较差，可读性较低）#include<iostream>#include<cstdio>#include&l...

2018-08-07 15:23:10 305 2

原创【并查集练习】NOI2015程序自动分析

这题据dzm大佬的话是并查集板子题，然而卡了我很久，果然还是我太弱了吗…… 思路：按秩合并和路径压缩在这道题都能用，对那些用两种优化如同写板子的OIer们算是很友好了。这道题总体思路是把条件相等的合并，条件不等的则判断是否已经在一个集合中，如果是则不成立。具体的来说，离线来做是个不错的选择。先将数据都读入，使e为1的在前，e为0的在后，先全部合并在判断，这样做对最后结果是没有影响的...

2018-08-07 15:14:23 269

原创各类简单的线段树模板（来自codevs）

本蒟蒻最近在学线段树，在学校大佬的推荐下在codevs上发现了三个比较具有代表性的线段树的模板，下面是题面线段树练习线段树练习2线段树练习3（当然在这里我只负责提供这三类简单的模板，不负责教授线段树的相关知识，各位大佬，见谅！）线段树练习代码（单点修改区间查询）#include<iostream>#include<algorithm>#include<cstdio...

2018-06-17 08:52:28 1007 3

原创洛谷P2652 同花顺

题面思路：洛谷的题目标签貌似不能相信了，明明是模拟他却非打上搜索的标签。看到题目一读题，马上就想到应该排序，隐隐约约感觉应该先按照花色从小到大排序再在每一种花色里按牌的大小排序。题目想让我们抽出最少的牌构成同花顺，那我们从另一个方面思考，是不是可以找最长上升子序列，那么n-序列长度就是抽出的牌了。当然，我们在排序的时候需要去重。代码：#include<iostream>#includ...

2018-06-10 10:39:08 250

原创洛谷P2832 行路难

题面思路：最短路问题。加上疲劳度看似很难，但只要用一个记录疲劳度的数组就好啦，另外还需要记录路径。代码：#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#include<cmath>#include<queue>#defi...

2018-06-10 08:45:37 296

题面思路：这两个不好好学习的坏学生要互相传纸条，同学们可以帮他们但不想帮第二次。如果正向反向各dp一次每一次都做标记以防止路线重复，只能得到正向反向其中某一次的最大值，无法保证两次之和最大。再仔细一想，这个题意好像有点熟悉（方格取数……？）正确的想法喷涌而出！！！这时，我们只需要把正向反向都看做两个人都从起点到终点，共两条路就好，也没有做标记的必要（当两人都到同一点时，这点的好心值只加一次就好啦！...

2018-06-03 07:59:26 281

原创洛谷P2648赚钱

题面思路：在下刚学的ｓｐｆａ当然要找一道ｓｐｆａ的题练一练了……题目里说明，只要不坐飞机就不用花钱，坐飞机就得花钱，我们完全可以把这两种类型的路存在一张有向图里。不用做飞机的路长为0，坐飞机的就是飞机票钱。有一些特别的地方：1.ｄｉｓ的初始值要非常小，因为要用ｄｉｓ数组更新赚的最多的钱，还要判断正环以防ｏｒｚ。代码：#include<iostream>#include<cstr...

2018-05-27 16:03:06 251

转载 noip2017提高组宝藏

转载【https://blog.csdn.net/qq_35914587/article/details/78964855】@HT008_123题面虽然大佬没有很详细的讲解，但是代码还是很好懂的！！代码：#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>...

2018-05-27 09:16:35 517 1

原创 noip2017提高组奶酪

点击打开链接题目描述现有一块大奶酪，它的高度为 hh ，它的长度和宽度我们可以认为是无限大的，奶酪中间有许多半径相同的球形空洞。我们可以在这块奶酪中建立空间坐标系，在坐标系中，奶酪的下表面为 z = 0z=0 ，奶酪的上表面为 z = hz=h 。现在，奶酪的下表面有一只小老鼠 Jerry，它知道奶酪中所有空洞的球心所在的坐标。如果两个空洞相切或是相交，则 Jerry 可以从其中一个空洞...

2018-05-23 18:26:51 1267

原创 SHOI2002滑雪

点击打开链接直截了当：（今天做洛谷月赛有点累，不多解释了。。。）#include<iostream>#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>#define fill( a ) memset( a, -1, sizeof( a ) ...

2018-05-19 21:16:27 490 1

原创 noip2010提高组乌龟棋

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

2018-05-09 20:34:08 460

原创 noip2006提高组金明的预算方案

题目链接题目描述金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”。今天一早，金明就开始做预算了，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是一些主件与附件的例子：主件附件电脑打印机，扫描仪书柜图书书桌台灯，文具工作椅无如果要买归...

2018-05-09 20:24:51 208

原创 noip2000提高组单词接龙

题目描述单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”（每个单词都最多在“龙”中出现两次），在两个单词相连时，其重合部分合为一部分，例如 beast和astonish，如果接成一条龙则变为beastonish，另外相邻的两部分不能存在包含关系，例如at 和 atide 间不能相连。输入输出格式输入格式：输入的第一行为...

2018-05-06 08:49:56 352

原创洛谷P1803凌乱的yyy

题目背景快noip了，yyy很紧张！题目描述现在各大oj上有n个比赛，每个比赛的开始、结束的时间点是知道的。yyy认为，参加越多的比赛，noip就能考的越好（假的）所以，他想知道他最多能参加几个比赛。由于yyy是蒟蒻，如果要参加一个比赛必须善始善终，而且不能同时参加2个及以上的比赛。输入输出格式输入格式：第一行是一个整数n ，接下来n行每行是2个正整数ai,bi(ai<bi)，表示比赛开始、...

2018-05-05 19:45:29 288

原创洛谷P1031均分纸牌

题目描述有 N 堆纸牌，编号分别为 1，2，…, N。每堆上有若干张，但纸牌总数必为 N 的倍数。可以在任一堆上取若干张纸牌，然后移动。移牌规则为：在编号为 1 堆上取的纸牌，只能移到编号为 2 的堆上；在编号为 N 的堆上取的纸牌，只能移到编号为 N-1 的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。例如 N=4，4 堆...

2018-05-05 19:20:02 335

转载关于瑞士轮（洛谷P1309）以及引申出来的种种问题

题目链接原创链接首先来看题（没看题的看题去！），题面应该不难理解，就是每次相邻分数的两个人根据实力值进行比较，然后输赢分治，不断排序罢了。“肯定要sort哇！每次更新分数，然后sort不就得了？”其实本质上来说，是可以的，但是sort会爆炸——时间会爆炸。但是无论时间怎样，那都是ccf的测试点有没有卡tle的问题而已。但如果真从程序设计本身探讨，sort无疑是一个很浪费的算法。一、关于sort的浪...

2018-04-30 08:28:04 247

原创洛谷P1540 机器翻译

题目链接题目背景小晨的电脑上安装了一个机器翻译软件，他经常用这个软件来翻译英语文章。题目描述这个翻译软件的原理很简单，它只是从头到尾，依次将每个英文单词用对应的中文含义来替换。对于每个英文单词，软件会先在内存中查找这个单词的中文含义，如果内存中有，软件就会用它进行翻译；如果内存中没有，软件就会在外存中的词典内查找，查出单词的中文含义然后翻译，并将这个单词和译义放入内存，以备后续的查找和翻译。假设内...

2018-04-29 15:32:27 302

原创 SPFA模板

代码：#include<bits/stdc++.h>#define inf 2147483647#define maxn 10005#define maxm 500005using namespace std;int n, m, s, num_edge=0;int dis[maxn], vis[maxn], head[maxm];struct Edge { in...

2018-04-22 16:28:05 190

原创迷宫寻宝

描述 Description：一个只含有一个入口和多个出口的树型迷宫，里面分布着很多的宝藏，每个路口都有一定数量的宝藏，迷宫是单向的，只能从入口开始前行，不能返回，请你从入口进入迷宫，选择一个合适的出口，使获得的宝藏数量最多。已知迷宫共有n个路口，1号路口是入口。输入格式 Input Format：第一行：路口的个数n（n<100000）。第二行：依次是每个路口（按编号1到n的顺序）的宝藏...

2018-04-22 15:54:08 682

原创洛谷P1478陶陶摘苹果（升级版）

题目链接题目描述又是一年秋季时，陶陶家的苹果树结了n个果子。陶陶又跑去摘苹果，这次她有一个a公分的椅子。当他手够不着时，他会站到椅子上再试试。这次与NOIp2005普及组第一题不同的是：陶陶之前搬凳子，力气只剩下s了。当然，每次摘苹果时都要用一定的力气。陶陶想知道在s<0之前最多能摘到多少个苹果。现在已知n个苹果到达地上的高度xi，椅子的高度a，陶陶手伸直的最大长度b，陶陶所剩的力气s，陶陶...

2018-04-22 14:00:10 290

原创 NOIP2003 提高组加分二叉树

题目链接题目描述设一个n个节点的二叉树tree的中序遍历为（1,2,3,…,n），其中数字1,2,3,…,n为节点编号。每个节点都有一个分数（均为正整数），记第i个节点的分数为di，tree及它的每个子树都有一个加分，任一棵子树subtree（也包含tree本身）的加分计算方法如下：subtree的左子树的加分× subtree的右子树的加分＋subtree的根的分数。若某个子树为空，规定其加分为...

2018-04-22 11:09:51 348 2

原创洛谷 P2637 第一次，第二次，成交！

题目链接题目描述因为奶牛们的节食运动（奶牛还节食？）给农夫JOHN余下了一大批干草无法处理，所以他准备要开一个拍卖会去出售他的干草。他有N(1<=N<=1000)批干草（每批大约100捆）。他的客户有M个（1<=M<=1000），都是和他相邻的农夫。第I名农夫会告诉农夫JOHN他会为农夫JOHN的每批干草付P_i的钱（1<=P_i<=1,000,000）。每个...

2018-04-22 09:53:55 981

转载根据两种遍历顺序确定树结构（求后序遍历+先序遍历）

作者：C20180630_zjf原创地址一、原题根据两种遍历顺序确定树结构(build-tree)输入第1行：二叉树的前序遍历顺序第2行：中序遍历顺序输出二叉树的后序遍历顺序样例输入ABCDEFGH CBEDAGHF样例输出CEDBHGFA二、分析这道题要运用到搜索，其代码与二分查找比较相似，要先读入，然后把字符串分成两个部分进行下一步的递归，以便用二叉树的前序遍历和中序遍历来找到二叉树的后序遍...

2018-04-22 09:02:57 1843

原创洛谷P1305 新二叉树

题目链接题目描述输入一串二叉树，用遍历前序打出。输入输出格式输入格式：第一行为二叉树的节点数n。( n \leq 26n≤26 )后面n行，每一个字母为节点，后两个字母分别为其左右儿子。空节点用*表示输出格式：前序排列的二叉树输入输出样例输入样例#1： 6abcbdicj*d**i**j**输出样例#1： abdicj思路：简单的二叉树先序遍历，关键我是个不会字符类各种知识的蒟蒻，只好...

2018-04-21 20:42:09 235

原创超基础！树的先中后序遍历

个人笔记（直接贴代码）#include <cstdio>#include <iostream>#define maxn 110using namespace std;int f[maxn],l[maxn],r[maxn];int v[maxn];int n,t;void init() { //建树 int p, k, lch, rch; //结点编号...

2018-04-21 18:43:50 192

原创 UVa 679 Dropping Balls 下落的小球

题目描述：有一棵二叉树，最大深度为D，且所有叶子的深度都相同。所有叶子从上到下从左到右编号为1,2,3……2^D-1。在结点1处放一个小球，它会往下落。每个内结点上都有一个开关，初始全部关闭，当每次有小球落到一个开关上时，状态都会改变。当小球到达一个内结点时，如果该结点上的开关关闭，则往左走，否则往右走，直到走到叶子结点，如图所示。一些小球从结点1处依次下落，最后一个小球会落到那里呢？输入叶子的深...

2018-04-18 21:43:50 182

原创 codevs 3641 上帝选人

题目链接题目描述 Description世界上的人都有智商IQ和情商EQ。我们用两个数字来表示人的智商和情商，数字大就代表其相应智商或情商高。现在你面前有N个人，这N个人的智商和情商均已知，请你选择出尽量多的人，要求选出的人中不存在任意两人i和j，i的智商大于j的智商但i的情商小于j的情商。输入描述 Input Description 第一行一个正整数N，表示人的数量。第二行至第N+1行，每行两...

2018-04-15 15:17:57 374

原创洛谷 P1074 靶形数独

题目描述小城和小华都是热爱数学的好学生，最近，他们不约而同地迷上了数独游戏，好胜的他们想用数独来一比高低。但普通的数独对他们来说都过于简单了，于是他们向 Z 博士请教，Z 博士拿出了他最近发明的“靶形数独”，作为这两个孩子比试的题目。靶形数独的方格同普通数独一样，在 9 格宽×9 格高的大九宫格中有 9 个 3 格宽×3 格高的小九宫格（用粗黑色线隔开的）。在这个大九宫格中，有一些数字是已知的，根...

2018-04-15 10:35:23 173

原创洛谷 P2330 [SCOI2005]繁忙的都市

题目链接题目描述城市C是一个非常繁忙的大都市，城市中的道路十分的拥挤，于是市长决定对其中的道路进行改造。城市C的道路是这样分布的：城市中有n个交叉路口，有些交叉路口之间有道路相连，两个交叉路口之间最多有一条道路相连接。这些道路是双向的，且把所有的交叉路口直接或间接的连接起来了。每条道路都有一个分值，分值越小表示这个道路越繁忙，越需要进行改造。但是市政府的资金有限，市长希望进行改造的道路越少越好，于...

2018-04-15 10:27:47 191

原创洛谷P2820 局域网

题目链接题目背景某个局域网内有n(n<=100)台计算机，由于搭建局域网时工作人员的疏忽，现在局域网内的连接形成了回路，我们知道如果局域网形成回路那么数据将不停的在回路内传输，造成网络卡的现象。因为连接计算机的网线本身不同，所以有一些连线不是很畅通，我们用f(i,j)表示i,j之间连接的畅通程度，f(i,j)值越小表示i,j之间连接越通畅，f(i,j)为0表示i,j之间无网线连接。题目描述需...

2018-04-15 10:22:21 465

Palace_的博客