P5908 猫猫和企鹅 题目描述 王国里有  个居住区，它们之间有  条道路相连，并且保证从每个居住区出发都可以到达任何一个居住区，并且每条道路的长度都为 。 除  号居住区外，每个居住区住着一个小企鹅，有一天一只猫猫从  号居住区出发，想要去拜访一些小企鹅。可是猫猫非常的懒，它只愿意去距离它不大于  的小企鹅们。 猫猫非常的懒，因此希望你告诉他，他可以拜访多少只小企鹅。 输入格式 第一行两个整数 ，意义如题所述。 第二行开始，共  行，每行两个整数 ，表示居民区  和  之间存在道路。 输出格式 一行一个整数，表示猫猫可以拜访多少只小企鹅。 输入输出样例 #1 输入 #1 5 1 1 2 1...

P1196 [NOI2002] 银河英雄传说 题目背景 公元  年，地球居民迁至金牛座  第二行星，在那里发表银河联邦创立宣言，同年改元为宇宙历元年，并开始向银河系深处拓展。 宇宙历  年，银河系的两大军事集团在巴米利恩星域爆发战争。泰山压顶集团派宇宙舰队司令莱因哈特率领十万余艘战舰出征，气吞山河集团点名将杨威利组织麾下三万艘战舰迎敌。 题目描述 杨威利擅长排兵布阵，巧妙运用各种战术屡次以少胜多，难免恣生骄气。在这次决战中，他将巴米利恩星域战场划分成  列，每列依次编号为 。之后，他把自己的战舰也依次编号为 ，让第  号战舰处于第  列，形成“一字长蛇阵”，诱敌深入。这是初始阵形。当进犯之敌到...

P1219 [USACO1.5] 八皇后 Checker Challenge 题目描述 一个如下的  的跳棋棋盘，有六个棋子被放置在棋盘上，使得每行、每列有且只有一个，每条对角线（包括两条主对角线的所有平行线）上至多有一个棋子。  上面的布局可以用序列  来描述，第  个数字表示在第  行的相应位置有一个棋子，如下： 行号  列号  这只是棋子放置的一个解。请编一个程序找出所有棋子放置的解。 并把它们以上面的序列方法输出，解按字典顺序排列。 请输出前  个解。最后一行是解的总个数。 输入格式 一行一个正整数 ，表示棋盘是  大小的。 输出格式 前三行为前三个解，每个解的两个数字之间用一个空格隔...

P1443 马的遍历 题目描述 有一个  的棋盘，在某个点  上有一个马，要求你计算出马到达棋盘上任意一个点最少要走几步。 输入格式 输入只有一行四个整数，分别为 。 输出格式 一个  的矩阵，代表马到达某个点最少要走几步（不能到达则输出 ）。 输入输出样例 #1 输入 #1 3 3 1 1  输出 #1 0 3 2 3 -1 1 2 1 4  说明/提示 数据规模与约定 对于全部的测试点，保证 ，。 2022 年 8 月之后，本题去除了对输出保留场宽的要求。为了与之兼容，本题的输出以空格或者合理的场宽分割每个整数都将判作正确。 解题思路 这是一道标准的求一点到任意一点的最短路径问题，使用BF...

P1118 [USACO06FEB] Backward Digit Sums G/S 题目描述 FJ 和他的奶牛们喜欢玩一个心算游戏。他们将数字从  到  按某种顺序写下来，然后将相邻的数字相加，得到一个数字更少的新列表。他们重复这个过程，直到只剩下一个数字。例如，游戏的一种情况（当  时）可能是这样的：  3 1 2 4 4 3 6 7 9 16  在 FJ 背后，奶牛们开始玩一个更难的游戏，她们试图从最终的总和和数字  中确定起始序列。不幸的是，这个游戏有点超出了 FJ 的心算能力。 编写一个程序来帮助 FJ 玩这个游戏，并跟上奶牛们的步伐。 输入格式 共一行两个正整数 。 输出格式 输出...

P2880 [USACO07JAN] Balanced Lineup G 题目描述 每天，农夫 John 的  头牛总是按同一序列排队。 有一天，John 决定让一些牛们玩一场飞盘比赛。他准备找一群在队列中位置连续的牛来进行比赛。但是为了避免水平悬殊，牛的身高不应该相差太大。John 准备了  个可能的牛的选择和所有牛的身高 。他想知道每一组里面最高和最低的牛的身高差。 输入格式 第一行两个数 。 接下来  行，每行一个数 。 再接下来  行，每行两个整数  和 ，表示询问第  头牛到第  头牛里的最高和最低的牛的身高差。 输出格式 输出共  行，对于每一组询问，输出每一组中最高和最低的牛的身...

P1816 忠诚 题目描述 老管家是一个聪明能干的人。他为财主工作了整整  年。财主为了让自已账目更加清楚，要求管家每天记  次账。由于管家聪明能干，因而管家总是让财主十分满意。 但是由于一些人的挑拨，财主还是对管家产生了怀疑。于是他决定用一种特别的方法来判断管家的忠诚。他把每次的账目按  编号，然后不定时地问管家这样的问题：在  到  号账中最少的一笔是多少？ 为了让管家没时间作假，他总是一次问多个问题。 输入格式 第一行输入两个数 ，表示有  笔账和  个问题。 第二行输入  个数，分别表示账目的钱数。 接下来  行分别输入  个问题，每行  个数字，分别表示开始的账目编号  和结束的账目...

P1449 后缀表达式 题目描述 所谓后缀表达式是指这样的一个表达式：式中不再引用括号，运算符号放在两个运算对象之后，所有计算按运算符号出现的顺序，严格地由左而右新进行（不用考虑运算符的优先级）。 本题中运算符仅包含 。保证对于  运算除数不为 0。特别地，其中  运算的结果需要向 0 取整（即与 C++ / 运算的规则一致）。 如： 对应的后缀表达式为：。在该式中，@ 为表达式的结束符号。. 为操作数的结束符号。 输入格式 输入一行一个字符串 ，表示后缀表达式。 输出格式 输出一个整数，表示表达式的值。 输入输出样例 #1 输入 #1 3.5.2.-*7.+@  输出 #1 16  输入输出...

P1030 [NOIP 2001 普及组] 求先序排列 题目描述 给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不同的大写字母表示，且二叉树的节点个数 ）。 输入格式 共两行，均为大写字母组成的字符串，表示一棵二叉树的中序与后序排列。 输出格式 共一行一个字符串，表示一棵二叉树的先序。 输入输出样例 #1 输入 #1 BADC BDCA  输出 #1 ABCD  说明/提示 【题目来源】 NOIP 2001 普及组第三题 这道题要求根据中序遍历和后序遍历结果求先序遍历字符串，那最直接的想法自然就是还原这棵树，再先序遍历。 我们清楚，中序遍历的规则是“左-根-右”，后序遍历的规...

P5597 【XR-4】复读 题目背景 赛时提醒：当机器人在这棵完全二叉树的根时，执行 U 是非法的，即你需要保证不可能出现这种情况。 赛时提醒：这棵二叉树是无限向下延伸的，即所有节点均有左子节点与右子节点，除了根的所有节点均有父亲。 题目描述 小 X 捡到了一台复读机，这台复读机可以向机器人发号施令。机器人将站在一棵完全二叉树的根上，完全二叉树是无限延伸的。你将向复读机录入一串指令，这串指令单个字符可以是：  L：命令机器人向当前节点的左子走； R：命令机器人向当前节点的右子走； U：命令机器人向当前节点的父亲走（若没有，则命令非法）。  录入指令后，复读机将会把指令无限复读下去。比如命令为...

Problem DescriptionJavac++ 一天在看计算机的书籍的时候，看到了一个有趣的东西！每一串字符都可以被编码成一些数字来储存信息，但是不同的编码方式得到的储存空间是不一样的！并且当储存空间大于一定的值的时候是不安全的！所以Javac++ 就想是否有一种方式是可以得到字符编码最小的空间值！显然这是可以的，因为书上有这一块内容--哈夫曼编码(Huffman Coding)；一个字母的权值等于该字母在字符串中出现的频率。所以Javac++ 想让你帮忙，给你安全数值和一串字符串，并让你判断这个字符串是否是安全的？Input输入有多组case，首先是一个数字n表示有n组数据，然后每一组...

由于题目链接无法解析，我直接截图呈现这道题是一道英文题，而且很长，整体的题意我就不做翻译了。他要求我们判断他给定的序列是否可行。看他的规则，是每来一节车，如果符合序列的车直接先行而不符合的车则先停留在车站且停留的车离开时需按照 “后进先出” 的顺序很明显，我们应该用栈来解决这个问题。整体代码如下： #include<iostream> #include<algorithm> #include<vector> #include<stack> #include<queue> #include<deque> #include&l...

由于题目链接无法解析，我直接截图此题要求我们判断字符串是否由 ab 插入操作得到的根据要求，我们可以发现：一个符合条件的好串，其 a 的数量和 b 的数量绝对是一一对应的，且在一一对应的 ab 对里，a 在前，b 在后。那么我们可以用一个栈，遍历字符串时，遇到 a 则入栈，遇到 b 则出栈。如果出栈时，发现栈为空，那么 1. b的数量大于 a 的数量，不是好串 2. b 在前，a 在后，不是好串如果遍历完成后，发现栈非空，那么 3. a 的数量大于 b 的数量，不是好串。此外的，都是符合条件的好串。整体代码如下： #include<iostream> #include<alg...

由于题目链接无法解析，我直接截图这个题目要求根据所给数字拼接一个最大的数字那怎么样的数字最大呢？假设给定 543 和 654，有两种拼接方式：654 543 和 543 654，这里 654543 更大，显然我们可以看出来，要使得拼接后的数字越大，我们就要让单一位越大的数字占据越高位。那么思路就清晰了：我们判断两个大数的优先级可以创建两个栈，分别记录两个大数的各位数字，从高到低依次进行比较，大的在前，小的在后。这个时候遇到一个情况：假设有 654 和 654 X ，怎么分辨优先级？这个时候分情况，如果 X＞6（假设 X=8），那么 6548 654>654 6548 如果 X＜6（假设 ...