Liston_YDQ的博客

原创 图片

原创 「NOIP2004」合并果子

题目描述在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。 每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过n-1次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。 因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为1，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序

原创 走路

想要走得远，就要从脚下的路开始。不然，你就只会在原地踏步，变成一个眼高手低的人。 ———by 烈焰火豹的确，不管是生活上的走路，还是寓意上的“走路”，这都是真理，不看你自己脚下的路，只会造成一个个你想也想不到的悲剧发生。想我，从游泳池出来游完泳的时候，happy地走在回家的路上，但没有注意脚下，脚上一滑，为了让自己不摔倒，自己的脚本能性的往前面一伸，然后“刺啦”的一下，脚被划了一个口子，说大也不大，只有6厘米左右（不.

原创 好与坏：

好与坏： 判断一个学生的好与坏，成绩是一方面，为人又是另一方面。 如果要说哪一个占得多，我会说“成绩为人三七分”。我见过很 多成绩不好的人（甚至只有初中文凭）出路很广。马云是一个 无比成功的人，他的路途也十分艰辛，在他看来，优秀年轻人 的标准是：一个人才首先要聪明，比他要聪明。他找人的时候 他觉得如果这个人五六年后可以当他的老板，他就喜欢。然后 是积极向上。马云说过：“我从来不看大学文凭，这个不太重要。重要的是这个人聪明，积极向上。我发现优秀的人都很积极，不抱怨。如果一

原创 关于排序

简单排序通常我们在获取了一些数据之后会对这些数据进行处理，常用的操作有排序，查找，插入，删除等等，本节给大家介绍两种基本的排序方法：冒泡排序，插入排序、选择排序、桶排序。冒泡排序：输入n个数，将这n个数从小到大输出。冒泡排序的思想：以n个人站队为例，从第1个开始，依次比较相邻的两个是否逆序(高在前，矮在后)，若逆序就交换这两人，即第1个和第2个比，若逆序就交换两人，接着第2个和第3个比，若逆序就交换两人，接着第3个和第4个比，若逆序就交换两人，……，直到n-1和n比较，经过一轮比较

原创 奖金

题目描述由于无敌的凡凡在2005年世界英俊帅气男总决选中胜出，Yali Company总经理Mr.Z心情好，决定给每位员工发奖金。公司决定以每个人本年在公司贡献为标准来计算他们得到的奖金是多少。 于是Mr.Z下令召开m方会谈。每位参加会谈的代表提出了自己的意见：“我认为员工a的奖金应该比b高！”Mr.Z决定要找出一种奖金方案，满足各位代表的意见，且同时使得总奖金数最少。每位员工奖金最少为100元。奖金只能是整数。输入第1行：两个整数n、m，表示员工总数和代表数；以下m行：每行2个整数a，b，表示

原创 家谱树

题目描述有个人的家族很大，辈分关系很混乱，请你帮整理一下这种关系。 给出每个人的孩子的信息。 输出一个序列，使得每个人的后辈都比那个人后列出。输入第1行：一个整数N（1<=N<=100），表示家族的人数。接下来N行：第I行描述第I个人的儿子。两个数之间用一个空格隔开每行最后是0表示描述完毕。输出输出一个序列，使得每个人的后辈都比那个人后列出。如果有多解输出任意一解。两个数之间用一个空格隔开样例输入504 5 1 01 05 3 03 0样例输出2

原创 关于o1，o2，o3

有人可能问了o1，o2，o3是什么，他们有什么用，其实，o1，o2，o3就是针对c++的一系列优化系统，鉴于这是一篇附属文章，我就不做过多的介绍了，下面，吧o1，o2，o3打给大家：o1:#pragma GCC optimize(1)o2:#pragma GCC optimize(2)o3:#pragma GCC optimize(3)当然，也可以开G++。原文链接（正文链接）：https://blog.csdn.net/Liston_YDQ/article/details/107822998

转载 「NOIP2008」笨小猴

题目描述笨小猴的词汇量很小，所以每次做英语选择题的时候都很头疼。但是他找到了一种方法，经试验证明，用这种方法去选择选项的时候选对的几率非常大！ 这种方法的具体描述如下：假设maxn是单词中出现次数最多的字母的出现次数，minn是单词中出现次数最少的字母的出现次数，如果maxn-minn是一个质数，那么笨小猴就认为这是个Lucky Word，这样的单词很可能就是正确的答案。输入输入只有一行，是一个单词，其中只可能出现小写字母，并且长度小于100。输出输出共两行，第一行是一个字符串，假设输入的的单词是

原创 「NOI1997」最优乘车

题目描述H城是一个旅游胜地，每年都有成千上万的人前来观光。为方便游客，巴士公司在各个旅游景点及宾馆，饭店等地都设置了巴士站并开通了一些单程巴上线路。每条单程巴士线路从某个巴士站出发，依次途经若干个巴士站，最终到达终点巴士站。一名旅客最近到H城旅游，他很想去S公园游玩，但如果从他所在的饭店没有一路已士可以直接到达S公园，则他可能要先乘某一路巴士坐几站，再下来换乘同一站台的另一路巴士, 这样换乘几次后到达S公园。现在用整数1,2,…N 给H城的所有的巴士站编号，约定这名旅客所在饭店的巴士站编号为1…S公

原创 局域网

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

原创 联络员

题目描述Tyvj已经一岁了，网站也由最初的几个用户增加到了上万个用户，随着Tyvi网站的逐步壮大，管理员的数目也越来越多，现在你身为Tyvj管理层的联络员，希望你找到一些通信渠道，使得管理员两两都可以联络（直接或者间接都可以）。Tyvj是一个公益性的网站，没有过多利润，所以你要尽可能地使费用少才可以。目前你已经知道，Tyvi的通信渠道分为两大类，一类是必选通信渠道，无论价格多少，你都需要把所有的都选择上；还有一类是选择性的通信渠道，你可以从中挑选一些作为最终管理员联络的通信渠道。数据保证给出的通行渠道可

原创 最优布线问题

题目描述学校有 nnn 台计算机，为了方便数据传输，现要将它们用数据线连接起来。两台计算机被连接是指它们有数据线连接。由于计算机所处的位置不同，因此不同的两台计算机的连接费用往往是不同的。当然，如果将任意两台计算机都用数据线连接，费用将是相当庞大的。为了节省费用，我们采用数据的间接传输手段，即一台计算机可以间接的通过若干台计算机（作为中转）来实现与另一台计算机的连接。现在由你负责连接这些计算机，任务是使任意两台计算机都连通（不管是直接的或间接的）。输入第 111 行：整数 nnn（2≤n≤10

原创 单源最短路

题目描述给出一个有向图，请输出从某一点出发到所有点的最短路径长度。输入第一行包含三个整数N、M、S，分别表示点的个数、有向边的个数、出发点的编号。接下来M行每行包含三个整数Fi、Gi、Wi，分别表示第i条有向边的出发点、目标点和长度。输出N行，每行N个用空格分隔的整数，其中第i个整数表示从点S出发到点i的最短路径长度（若S=i则最短路径长度为0，若从点S无法到达点i，则该点最短路径不输出）样例输入4 6 11 2 22 3 22 4 11 3 53 4 31 4 4样例输出0

原创 function

题目描述对于一个递归函数w(a,b,c)（1）如果a≤0 or b≤0 or c≤0就返回值1；（2）如果a>20 or b>20 or c>20就返回w(20,20,20)；（3）如果a<b并且b<c 就返回w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c)（4）其它的情况就返回w(a-1,b,c)+w(a-1,b-1,c)+w(a-1,b,c-1)-w(a-1,b-1,c-1)如果出现w(30,-1,0)既满足条件1又满足条件2，这种时候我们就

原创 最优乘车

题目描述H城是一个旅游胜地，每年都有成千上万的人前来观光。为方便游客，巴士公司在各个旅游景点及宾馆，饭店等地都设置了巴士站并开通了一些单程巴上线路。每条单程巴士线路从某个巴士站出发，依次途经若干个巴士站，最终到达终点巴士站。一名旅客最近到H城旅游，他很想去S公园游玩，但如果从他所在的饭店没有一路已士可以直接到达S公园，则他可能要先乘某一路巴士坐几站，再下来换乘同一站台的另一路巴士, 这样换乘几次后到达S公园。现在用整数1,2,…N 给H城的所有的巴士站编号，约定这名旅客所在饭店的巴士站编号为1…S公

原创 「POJ1502」MPI Maelstrom

题目描述BIT最近得到了他们的新的超级计算机，超级计算机是一个分布式的共享内存的机器，内存范围和通信时间是不均匀的，在共享相同的内存单元的处理器通信很快，不共享相同内存单元的通信就很慢。现在想完成广播（broadcast）的操作，即让一个处理器发出一条信息，让其他处理器接收到，如果都由这一个处理一个个来发送，那么计算机的性能就会很慢。解决方案：第一个处理器发给另一个处理器，然后，开始两个处理器发送，然后再四个处理器……现在如果需要进行一次广播，我们想知道最少需要花多少时间输入输入将描述一个网络连

原创 关于优化(c++)

下面是我给的一个终极优化代码(c++)：#pragma GCC optimize(1)#pragma GCC optimize(2)#pragma GCC optimize(3)#pragma GCC optimize("Ofast")#pragma GCC optimize("inline")#pragma GCC optimize("-fgcse")#pragma GCC optimize("-fgcse-lm")#pragma GCC optimize("-fipa-sra")#p

原创 「POJ1125」Stockbroker Grapevine

题目描述股票制胜法宝之一就是谣言，你成为了一名证券公司，为了给公司谋取利益，你要找出谣言传递最快的方式。谣言传递注意是指股票经纪人间传递，但是股票经纪人之信任“可信任的信息源”，即只信任他朋友传来的信息。你需要找出一个经纪人，让谣言从他这里散播出去，能够最快的让所有经纪人都知道，并且求出最快需要多长时间？输入有多组数据，每组数据第一行n，表示一共有n个经纪人(n<=100)，接下来n行，每行表示一个经纪人，第一个数为m，表示这个经纪人有多少个朋友，接下来m对数据：a b，表明该经纪人向第a个经

原创 最小花费

题目描述在n个人中，某些人的银行卡账号之间可以互相转账。这些人之间转账的手续费各不相同。给定这些人之间转账时需要从转账金额里扣除百分之几的手续费，请问A最少需要多少钱使得转账后B收到100元？输入第一行输入两个正整数n、m，分别表示总人数和可以相互转账的人的对数。以下m行每行输入三个正整数x，y，z，表示标号为x的人和标号为y的人之间可以相互转账需要扣除z%的手续费（z<100）。最后一行输入两个正整数A，B。数据保证A与B之间可以直接或间接地转账。两个数之间用一个空格隔开。输出输出A使

原创 信使

题目描述战争时期，前线有n个哨所，每个哨所可能会与其他若干个哨所之间有通信联系。信使负责在哨所之间传递信息，当然，这是要花费一定时间的（以天为单位）。指挥部设在第一个哨所，当指挥部下达第一个命令后，指挥部就派出若干个信使向与指挥部相连的哨所送信，当一个哨所接到信后，这个哨所内的信使们也以同样的方式向其他哨所送信，直至所有n个哨所全部接到命令后，送信才算成功。因为准备充足，每个哨所内都安排了足够的信使（如果一个哨所与其他k个哨所有通信联系的话，这个哨所内至少会配备k个信使）。 现在总指挥请你编一个程序

原创 最短路径问题

题目描述平面上有ｎ个点（ｎ＜＝１００），每个点的坐标均在－１００００～１００００之间，其中的一些点之间有连线。若有连线，则表示可从一个点到达另一个点，即两点间有同路，同路的距离为两点间的直线距离。现在的任务是找出从一点到另一点之间的最短路径。输入共ｎ＋ｍ＋３行。第一行：整数ｎ第２行到第ｎ＋１行（共ｎ行），每行两个整数ｘ和ｙ，描述一个点的坐标。第ｎ＋２行为一个整数ｍ，m<=1000，表示图中连线的个数。此后的ｍ行，每行描述一条连线，由两个整数ｉ和ｊ组成，表示第ｉ个点和第ｊ个点之间有连线。

原创 骑马修栅栏

题目描述农民John每年有很多栅栏要整理。他总是骑着马穿过每一个栅栏并修复它破损的地方。 John是一个与其他农民一样懒得人、他讨厌骑马，因此从来不两次经过一个一个栅栏。你必须编一个程序，读入栅栏网络的描述，并计算出一条修栅栏的路径，使每个栅栏都恰好经过一次。John能从任何一个顶点（即两个栅栏的交点）开始骑马，在任意一个顶点结束。 每一个栅栏连接两个顶点，顶点用1到500标号（虽然有农场并没有500个顶点）。一个顶点可连接任意多（>=1）个栅栏。所有栅栏都是连通的（也就是你可以从任意一个栅

原创 一笔画问题

题目描述如果一个图存在一笔画，则一笔画的路径叫做欧拉路，如果最后又回到起点，那这个路径叫做欧拉回路。 我们定义奇点是指跟这个点相连的边数目有奇数个的点。对于能够一笔画的图，我们有以下两个定理。 定理1：存在欧拉路的条件：图是连通的，有且只有2个奇点。 定理2：存在欧拉回路的条件：图是连通的，有0个奇点。 两个定理的正确性是显而易见的，既然每条边都要经过一次，那么对于欧拉路，除了起点和终点外，每个点如果进入了一次，显然一定要出去一次，显然是偶点。对于欧拉回路，每个点进入和出去次数一定都

原创 「POJ1328」radar installation

题目描述假设陆地的海岸线是一条无限延长的直线，海岛是一个个的点，现需要在海岸线上安装雷达，使整个雷达系统能够覆盖到所有的海岛。雷达所能覆盖的区域是以雷达为圆心半径为d的圆，我们用指标坐标系来描述，海岸线就是x轴，现在给出每个海岛的坐标与雷达的半径d，请编写一个程序计算出最少需要多少个雷达才能够将所有海岛全部覆盖？输入数据第一行为n (1<=n<=1000)，d，n为海岛个数，d为雷达半径，接下来n行，每行两个数描述海岛坐标。输出输出最少需要的雷达个数，如果不能满足，则输出-1，具体格式

原创 「USACO2007JAN」Protecting the Flowers

题目描述有n头奶牛跑到FJ的花园里去吃花儿了，它们分别在距离牛圈T分钟处吃花儿，每分钟会吃掉D朵卡哇伊的花儿，（此处有点拗口，不要在意细节啊！），FJ现在要将它们给弄回牛圈，但是他每次只能弄一头回去，来回用时总共为2*T分钟，在这段时间内，其它的奶牛会继续吃FJ卡哇伊的花儿，速度保持不变，当然正在被赶回牛圈的奶牛就没口福了！现在要求以一种最棒的方法来尽可能的减少花儿的损失数量，求奶牛吃掉花儿的最少朵数！(2 ≤ N ≤ 100,000) (1 ≤ Ti ≤ 2,000,000) (1 ≤ Di ≤ 1

原创 整数区间

题目描述请编写完成以下任务： 1、从文件中读取闭区间的个数及它们的描述； 2、找到一个含元素个数最少的集合，使得对于每一个区间，都至少有一个整数属于该集合，输出该集合的元素的个数。 输入首行包括区间的数目n，1<=n<=10000接下来n行，每行包括两个整数a，b，两个数之间用一空格隔开，0<=a<=b<=10000，它们是某一区间的开始值和结束值。输出第一行集合元素的个数，对于每一个区间都至少有一个整数属于该区间，且集合所包含元素数目最少。样例

原创 活动选择

题目描述假设有一个需要使用某一资源的n个活动所组成的集合S，S={1,…,n}。该资源一次只能被一个活动所占用，每一个活动有一个开始时间bi和结束时间ei(bi<=ei)。若bi>=ej或bj>=ei，则称活动i和活动j兼容。你的任务是：选择由互相兼容的活动所组成的最大集合。输入共n+1行，其中第1行为n，第2行到第n+1行表示n个活动的开始时间和结束时间(中间用空格隔开)，格式为：nn(n<=1000)b1 e1……bn en输出最大能满足的活动数量样例输入1

原创 最大乘积

题目描述输入n个整数元素组成的序列S，你需要找出一个乘积最大的连续子序列。如果这个最大的乘积不是正数，应输出0（表示无解）。1<=n<=18,-10<=si<=10。输入第一行：一个整数N第二行：N个数，空格分开输出最大乘积或者0样例输入32 4 -3样例输出8#include<cstdio>#include<cstdlib>#include<iostream>using namespace std;long lo

原创 求逆序对数目

题目描述给定一个序列 a1,a2,…,ana_1,a_2,…,a_na1​,a2​,…,an​，如果存在 ai>aja_i>a_jai​>aj​ 且 i<ji<ji<j ，那么我们称之为逆序对的，求逆序对的数目。输入第一行为 nnn,表示序列长度，接下来的 nnn 行，第 i+1i+1i+1 行表示序列中的第 iii 个数。输出所有逆序对总数。样例输入43232样例输出3提示N≤105N\le 10^5N≤105，Ai≤105A_i\le 1

原创 求最大公约数

题目描述用递归算法求两个数 mmm 和 nnn 的最大公约数。（0<n,m≤1090 < n,m \le 10^90<n,m≤109）辗转相除法：辗转相除法不需要把两个数作质因子分解，而是利用以下理论来确定两个正整数 mmm 和 nnn 的最大公约数：如果 qqq 和 rrr 分别是 mmm 除以 nnn 的商和余数，即 m=nq+rm=nq+rm=nq+r，则 gcd⁡(m,n)=gcd⁡(n,r)\gcd(m,n)=\gcd(n,r)gcd(m,n)=gcd(n,r)。gcd⁡(m

原创 「模板」递归求阶乘

题目描述输入 n(0<n<20)n(0<n<20)n(0<n<20), 求 n!n!n! 并输出.输入输入一个正整数 nnn输出输出 nnn 的阶乘样例输入3样例输出6#include<bits/stdc++.h>using namespace std;long long int jc(long long int n){ if(n==1) return n; else return jc(n-1)*n;}int m

原创 统计素数

题目描述输入一个正整数 nnn，统计 1∼n1 \sim n1∼n 之间的素数个数。输入一个整数 nnn ，1≤n≤100001\le n\le 100001≤n≤10000输出一个整数，表示素数个数样例输入10样例输出4#include<bits/stdc++.h>using namespace std;int sum; bool ch(int x){ for(int i=2;i*i<=x;i++) if(x%i==0)return 0;

原创 组合数计算

题目描述实现组合数的计算。输入n，m，计算出提示：1）m个不同元素中取出n(n≤m)个元素的所有组合的个数，(不考虑顺序)叫做从m个不同元素中取出n个元素的组合数。2）公式： 3）阶乘的计算n!=123*••••••*(n-1)*n；4）可将阶乘与计算组合数都写成函数形式。Int jc(int n); int zuhe(int n,int m)输入一行：n m输出一行，输出组合数的值样例输入1 3样例输出3#include<cstdio>int jc(int

原创 「NOIP2005 普及组」校门外的树

题目描述某校大门外长度为L的马路上有一排树，每两棵相邻的树之间的间隔都是1米。我们可以把马路看成一个数轴，马路的一端在数轴0的位置，另一端在L的位置；数轴上的每个整数点，即0，1，2，……，L，都种有一棵树。由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要把这些区域中的树（包括区域端点处的两棵树）移走。你的任务是计算将这些树都移走后，马路上还有多少棵树。输入第一行有两个整数L（1 <= L

原创 「NOIP2015 普及组」金币

题目描述国王将金币作为工资，发放给忠诚的骑士。第一天骑士收到一枚金币；之后两天（第二天和第三天），每天收到两枚金币；之后三天（第四、五、六天），每天收到三枚金币；之后四天，每天收到四枚金币，以此类推；这种工资发放模式会一直延续下去，当连续N天收到N枚金币后，骑士会在之后的N+1天，每天收到N+1枚金币。请计算前K天里，骑士一共获得了多少金币。输入输入包含一个正整数K，表示发放金币的天数。输出输出一个正整数，即骑士收到的金币数。样例输入6样例输出14提示 骑士第一天收到一枚金币；第

原创 A + B Problem

题目描述输入两个整数a,b，输出它们的和(∣a∣,∣b∣≤109|a|,|b| \le 10^9∣a∣,∣b∣≤109)注意pascal使用integer会爆掉哦！有负数哦！c/c++的main函数必须是int类型，而且最后要return 0。这不仅对FZOJ其他题目有效，而且也是noip/noi比赛的要求！好吧，同志们，我们就从这一题开始，向着大牛的路进发。任何一个伟大的思想，都有一个微不足道的开始。输入输出格式输入格式两个整数以空格分开输出格式一个数输入输出样例输入样例 #1

原创 选择不相交区间

选择不相交区间题目描述数轴上有n开区间（ai，bi），请选择尽量多的 区间，使其两两不相交。输入第一行n之后n行，每行两个数分别为ai，bi输出最多能选择的区间个数样例输入31 32 43 5样例输出2提示对于20%的数据，n≤10；对于50%的数据，n≤1000；对于70%的数据，n≤100000；对于100%的数据，n≤1000000，0≤ai＜bi≤1000000。#include<bits/stdc++.h>using namespace std

原创 一笔画问题

题目描述如果一个图存在一笔画，则一笔画的路径叫做欧拉路，如果最后又回到起点，那这个路径叫做欧拉回路。 我们定义奇点是指跟这个点相连的边数目有奇数个的点。对于能够一笔画的图，我们有以下两个定理。 定理1：存在欧拉路的条件：图是连通的，有且只有2个奇点。 定理2：存在欧拉回路的条件：图是连通的，有0个奇点。 两个定理的正确性是显而易见的，既然每条边都要经过一次，那么对于欧拉路，除了起点和终点外，每个点如果进入了一次，显然一定要出去一次，显然是偶点。对于欧拉回路，每个点进入和出去次数一定都

原创 图的存储

题目描述本题目考察大家图的存储的基本能力（建议大家将两种图的储存方式都试一下），题目将给大家n个点的信息（字符串，长度<=30),再给大家m条边的信息，最后提出k个问题，每个问题都是寻找每个点的邻接点。（注意，该题数据会有重边）输入第一行：n,m,k接下来n行，每行一个字符串，表示每个顶点的信息（字符串长度<=30)接下来m行，每行两个数字a b，(0<=a,b ＜n 且a!=b)表示存在一条第a个点指向第b个点的边；接下来k行，每行一个数字z，表示询问第z顶点所有的邻接点信息