[综合] 【索引】PAT乙级题目题解

关于一些Java代码写的题目出现运行超时的说明：点击打开链接 1001.害死人不偿命的(3n+1)猜想(15) 1002.写出这个数(20) 1003.我要通过！(20) 1004.成绩排名(20) 1005.继续(3n+1)猜想(25) 1006.换个格式输出整数(15) 1007.素数对猜想(...

[综合] C++ - PAT - 1030. 完美数列(25)

给定一个正整数数列，和正整数p，设这个数列中的最大值是M，最小值是m，如果M<=m*p，则称这个数列是完美数列。 现在给定参数p和一些正整数，请你从中选择尽可能多的数构成一个完美数列。 输入格式： 输入第一行给出两个正整数N和p，其中N（<=105）是输入的正整数的个数，p（<=1...

[综合] C++ - PAT - 1045. 快速排序(25)

著名的快速排序算法里有一个经典的划分过程：我们通常采用某种方法取一个元素作为主元，通过交换，把比主元小的元素放到它的左边，比主元大的元素放到它的右边。给定划分后的N个互不相同的正整数的排列，请问有多少个元素可能是划分前选取的主元？ 例如给定N=5,排列是1、3、2、4、5。则： 1的左边没有元素...

[综合] PAT - 1056. 组合数的和(15)

给定N个非0的个位数字，用其中任意2个数字都可以组合成1个2位的数字。要求所有可能组合出来的2位数字的和。例如给定2、5、8，则可以组合出：25、28、52、58、82、85，它们的和为330。 输入格式： 输入在一行中先给出N（1<N<10），随后是N个不同的非0个位数字。数字间以空格...

[综合] PAT - 1057. 数零壹(20)

给定一串长度不超过105的字符串，本题要求你将其中所有英文字母的序号（字母a-z对应序号1-26，不分大小写）相加，得到整数N，然后再分析一下N的二进制表示中有多少0、多少1。例如给定字符串“PAT(Basic)”，其字母序号之和为：16+1+20+2+1+19+9+3=71，而71的二进制是100...

[综合] PAT - 1058. 选择题(20)

批改多选题是比较麻烦的事情，本题就请你写个程序帮助老师批改多选题，并且指出哪道题错的人最多。 输入格式： 输入在第一行给出两个正整数N（<=1000）和M（<=100），分别是学生人数和多选题的个数。随后M行，每行顺次给出一道题的满分值（不超过5的正整数）、选项个数（不少于2且不超过5的...

[综合] C++ - PAT - 1060. 爱丁顿数(25)

英国天文学家爱丁顿很喜欢骑车。据说他为了炫耀自己的骑车功力，还定义了一个“爱丁顿数”E，即满足有E天骑车超过E英里的最大整数E。据说爱丁顿自己的E等于87。 现给定某人N天的骑车距离，请你算出对应的爱丁顿数E（<=N）。 输入格式： 输入第一行给出一个正整数N（<=105），即连续骑车的...

[综合] NYOJ - 488 - 素数环(回溯法)

描述 有一个整数n，把从1到n的数字无重复的排列成环，且使每相邻两个数（包括首尾）的和都为素数，称为素数环。 为了简便起见，我们规定每个素数环都从1开始。例如，下图就是6的一个素数环。 输入 有多组测试数据，每组输入一个n(0<n<20)，n=0表示输入结束。 输出 每组第...

[综合] NYOJ - 1058 - 部分和问题(DFS+减枝)

描述 给定整数a1、a2、.......an，判断是否可以从中选出若干数，使它们的和恰好为K。 输入 首先，n和k，n表示数的个数，k表示数的和。 接着一行n个数。 （1<=n<=20,保证不超int范围） 输出 如果和恰好可以为k，输出“YES”，并按输入顺序依次输出是由哪几...

[综合] NYOJ - 1100 - WAJUEJI which home strong！(BFS变形,优先队列)

输入 第一个数T，T组测试数据。 两个数n,m;(0<n,m<=100)表示一个h行m列的二维地图。 接下来n行每行m个字符。 ‘s’表示弟弟目前所在位置。 ‘#’表示此处为一座山。为了节省体力，不从此处通行。 从‘A’-‘Z’表示各地的经济水平，对应1-26，路过对应字符的地区需要交...

[综合] NYOJ - 325 - zb的生日(dfs减枝,)

描述 今天是阴历七月初五，acm队员zb的生日。zb正在和C小加、never在武汉集训。他想给这两位兄弟买点什么庆祝生日，经过调查，zb发现C小加和never都很喜欢吃西瓜，而且一吃就是一堆的那种，zb立刻下定决心买了一堆西瓜。当他准备把西瓜送给C小加和never的时候，遇到了一个难题，never...

[综合] NYOJ - 32 - 组合数(DFS,设计标记)

描述 找出从自然数1、2、...、n（0<n<10）中任取r(0<r<=n)个数的所有组合。 输入 输入n、r。 输出 按特定顺序输出所有组合。 特定顺序：每一个组合中的值从大到小排列，组合之间按逆字典序排列。 样例输入 53 样例输出 543 542 541 ...

[综合] NYOJ - 284 - 坦克大战(BFS求最短路,优先队列)

题目传送门~~~~ 题目的意思就是输如n和m再给定一个n*m的地图，如： 34 YBEB EERE SSTE 其中Y表示You的位置，即起点。T表示Target的位置，即终点。S和R不能通过，通过E需要1步，通过B需要2步，求Y到T的所需要的最少部署。求最少步数首先想到bfs，但是如果用普通队列...

[综合] NYOJ - 635 - Oh, my goddess(BFS,优先队列)

描述 ShiningKnightistheembodimentofjusticeandhehasaverysharpswordcanevencleavewall.Manybadguysaredeadonhissword. Oneday,twoevilsorcerercgangeeandJackch...

[综合] NYOJ - 218 - Dinner(简单问题)

描述 LittleAisonememberofACMteam.HehadjustwonthegoldinWorldFinal.Tocelebrate,hedecidedtoinvitealltohaveonemeal.Asbowl,knifeandothertablewareisnotenough...

[综合] NYOJ - 71 - 独木舟上的旅行(乘船问题)

描述 进行一次独木舟的旅行活动，独木舟可以在港口租到，并且之间没有区别。一条独木舟最多只能乘坐两个人，且乘客的总重量不能超过独木舟的最大承载量。我们要尽量减少这次活动中的花销，所以要找出可以安置所有旅客的最少的独木舟条数。现在请写一个程序，读入独木舟的最大承载量、旅客数目和每位旅客的重量。根据给出...

[综合] NYOJ - 106 - 背包问题(物品可分割问题)

描述 现在有很多物品（它们是可以分割的），我们知道它们每个物品的单位重量的价值v和重量w（1<=v,w<=10）；如果给你一个背包它能容纳的重量为m（10<=m<=20）,你所要做的就是把物品装到背包里，使背包里的物品的价值总和最大。 输入 第一行输入一个正整数n（...

[综合] NYOJ - 36 - 最长公共子序列(LCS,动态规划DP)

描述 咱们就不拐弯抹角了，如题，需要你做的就是写一个程序，得出最长公共子序列。 tip：最长公共子序列也称作最长公共子串(不要求连续)，英文缩写为LCS（LongestCommonSubsequence）。其定义是，一个序列S，如果分别是两个或多个已知序列的子序列，且是所有符合此条件序列中最长的，...

[综合] NYOJ - 14 - 会场安排问题(区间相关问题---选择不相交区间-贪心算法)

描述 学校的小礼堂每天都会有许多活动，有时间这些活动的计划时间会发生冲突，需要选择出一些活动进行举办。小刘的工作就是安排学校小礼堂的活动，每个时间最多安排一个活动。现在小刘有一些活动计划的时间表，他想尽可能的安排更多的活动，请问他该如何安排。 输入 第一行是一个整型数m(m<100...

[综合] NYOJ - 891 - 找点(区间相关问题---区间选点-贪心算法)

描述 上数学课时，老师给了LYH一些闭区间，让他取尽量少的点，使得每个闭区间内至少有一个点。但是这几天LYH太忙了，你们帮帮他吗？ 输入 多组测试数据。 每组数据先输入一个N，表示有N个闭区间（N≤100)。 接下来N行，每行输入两个数a，b(0≤a≤b≤100），表示区间的两个端点。 输...