机器人正在玩一个古老的基于DOS的游戏。 游戏中有N+1座建筑——从0到N编号，从左到右排列。 编号为0的建筑高度为0个单位，编号为i的建筑高度为H(i)个单位。 起初，机器人在编号为0的建筑处。 每一步，它跳到下一个（右边）建筑。 假设机器人在第k个建筑，且它现在的能量值是E，下一步它将跳到第k+1个建筑。 如果H(k+1)>E，那么机器人就失去H(k+1)−E的能量值，否则它将得到E−H(k+1)的能量值。 游戏目标是到达第N个建筑，在这个过程中能量值不能为负数个单位。 现在的问题是机器人至少以多少能量值开始游戏，才可以保证成功完成游戏？ 输入格式 第一行输入整数N。 第二行是N个空...

四平方和定理，又称为拉格朗日定理： 每个正整数都可以表示为至多4个正整数的平方和。 如果把0包括进去，就正好可以表示为4个数的平方和。 比如： 5=0^2+0^2+1^2+2^2 7=1^2+1^2+1^2+2^2 对于一个给定的正整数，可能存在多种平方和的表示法。 要求你对4个数排序： 0≤a≤b≤c≤d 并对所有的可能表示法按a,b,c,d为联合主键升序排列，最后输出第一个表示法。 输入格式 输入一个正整数N。 输出格式 输出4个非负整数，按从小到大排序，中间用空格分开。 数据范围 0<N<5∗1e6 输入样例： 5 输出样例： 0012 题解: 暴力three重循环判...

100可以表示为带分数的形式：100=3+69258/714还可以表示为：100=82+3546/197注意特征：带分数中，数字1∼9分别出现且只出现一次（不包含0）。 类似这样的带分数，100有11种表示法。 输入格式 一个正整数。 输出格式 输出输入数字用数码1∼9不重复不遗漏地组成带分数表示的全部种数。 数据范围 1≤N<1e6 输入样例1： 100 输出样例1： 11 输入样例2： 105 输出样例2： 6 题解: 枚举所有a的情况,在每种a的前提下,再枚举所有c的情况 根据a,c,n计算出b 判断是否满足[1,9]仅出现过一次,且a,b,c中不含有0 代码并...

小明正在玩一个“翻硬币”的游戏。 桌上放着排成一排的若干硬币。我们用表示正面，用o表示反面（是小写字母，不是零）。 比如，可能情形是：oooooo 如果同时翻转左边的两个硬币，则变为：oooooooo 现在小明的问题是：如果已知了初始状态和要达到的目标状态，每次只能同时翻转相邻的两个硬币,那么对特定的局面，最少要翻动多少次呢？ 我们约定：把翻动相邻的两个硬币叫做一步操作。 输入格式 两行等长的字符串，分别表示初始状态和要达到的目标状态。 输出格式 一个整数，表示最小操作步数 数据范围 输入字符串的长度均不超过100。数据保证答案一定有解。 输入样例1： oo 输出样例1: 5 输入样例...

小明开了一家糖果店。 他别出心裁：把水果糖包成4颗一包和7颗一包的两种。 糖果不能拆包卖。 小朋友来买糖的时候，他就用这两种包装来组合。 当然有些糖果数目是无法组合出来的，比如要买10颗糖。 你可以用计算机测试一下，在这种包装情况下，最大不能买到的数量是17。 大于17的任何数字都可以用4和7组合出来。 本题的要求就是在已知两个包装的数量时，求最大不能组合出的数字。 输入格式 两个正整数n,m，表示每种包装中糖的颗数。 输出格式 一个正整数，表示最大不能买到的糖数。 数据范围 2≤n,m≤1000， 保证数据一定有解。 输入样例： 47 输出样例： 17 题解: 这题其实就是一个结论,...

长100厘米的细长直杆子上有n只蚂蚁。 它们的头有的朝左，有的朝右。 每只蚂蚁都只能沿着杆子向前爬，速度是1厘米/秒。 当两只蚂蚁碰面时，它们会同时掉头往相反的方向爬行。 这些蚂蚁中，有1只蚂蚁感冒了。 并且在和其它蚂蚁碰面时，会把感冒传染给碰到的蚂蚁。 请你计算，当所有蚂蚁都爬离杆子时，有多少只蚂蚁患上了感冒。 输入格式 第一行输入一个整数n,表示蚂蚁的总数。 接着的一行是n个用空格分开的整数Xi,Xi的绝对值表示蚂蚁离开杆子左边端点的距离。 正值表示头朝右，负值表示头朝左，数据中不会出现0值，也不会出现两只蚂蚁占用同一位置。 其中，第一个数据代表的蚂蚁感冒了。 输出格式 输出1个整数，表示...

有N件物品和一个容量是V的背包。每件物品只能使用一次。 第i件物品的体积是vi，价值是wi。 求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。 输入格式 第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。 接下来有N行，每行两个整数vi,wi，用空格隔开，分别表示第i件物品的体积和价值。 输出格式 输出一个整数，表示最大价值。 数据范围 0<N,V≤1000 0<vi,wi≤1000 输入样例 4512243445 输出样例： 8 题解: 每个物品都有两种情况,选或者不选,所以要从2^n中方案中找到最大值 f[i][j]...

给定一个长度为N的数列，A1,A2,…AN，如果其中一段连续的子序列Ai,Ai+1,…Aj之和是K的倍数，我们就称这个区间[i,j]是K倍区间。 你能求出数列中总共有多少个K倍区间吗？ 输入格式 第一行包含两个整数N和K。 以下N行每行包含一个整数Ai。 输出格式 输出一个整数，代表K倍区间的数目。 数据范围 1≤N,K≤100000,1≤Ai≤100000 输入样例： 5212345输出样例：6 题解: 先求前缀和 对前缀和s[i]取余,余数相同的前缀和互相相减是k的倍数(ps:如果余数相同的个数是4,那么答案应该加上3+2+1;相同的个数是3的话,应该加上2+1,还不懂的话看下图) ...

儿童节那天有K位小朋友到小明家做客。 小明拿出了珍藏的巧克力招待小朋友们。 小明一共有N块巧克力，其中第i块是Hi×Wi的方格组成的长方形。 为了公平起见，小明需要从这N块巧克力中切出K块巧克力分给小朋友们。 切出的巧克力需要满足： 形状是正方形，边长是整数 大小相同 例如一块6×5的巧克力可以切出6块2×2的巧克力或者2块3×3的巧克力。 当然小朋友们都希望得到的巧克力尽可能大，你能帮小明计算出最大的边长是多少么？ 输入格式 第一行包含两个整数N和K。 以下N行每行包含两个整数Hi和Wi。 输入保证每位小朋友至少能获得一块1×1的巧克力。 输出格式 输出切出的正方形巧克力最大可能的边长...

原题链接你玩过“拉灯”游戏吗？ 25盏灯排成一个5×5的方形。 每一个灯都有一个开关，游戏者可以改变它的状态。 每一步，游戏者可以改变某一个灯的状态。 游戏者改变一个灯的状态会产生连锁反应：和这个灯上下左右相邻的灯也要相应地改变其状态。 我们用数字1表示一盏开着的灯，用数字0表示关着的灯。 下面这种状态 1011101101101111000011011在改变了最左上角的灯的状态后将变成： 0111111101101111000011011再改变它正中间的灯后状态将变成： 0111111001110011010011011给定一些游戏的初始状态，编写程序判断游戏者是否可能在6步以内使所有的灯都...

"飞行员兄弟"这个游戏，需要玩家顺利的打开一个拥有16个把手的冰箱。 已知每个把手可以处于以下两种状态之一：打开或关闭。 只有当所有把手都打开时，冰箱才会打开。 把手可以表示为一个4×4的矩阵，您可以改变任何一个位置[i,j]上把手的状态。 但是，这也会使得第i行和第j列上的所有把手的状态也随着改变。 请你求出打开冰箱所需的切换把手的次数最小值是多少。 输入格式输入一共包含四行，每行包含四个把手的初始状态。 符号+表示把手处于闭合状态，而符号表示把手处于打开状态。 至少一个手柄的初始状态是关闭的。 输出格式第一行输出一个整数N，表示所需的最小切换把手次数。 接下来N行描述切换顺序，每行输出两个...

原题链接 暴力做法(时间复杂度O(n^2)) 每次选取下标i为峰值,进行n次，对每次取max就可以找到答案 对于i左边的序列:需要满足序列是非递减的,同时每个值尽可能大 所以满足:j的位置上的数<=(j,i]上的最小的值(等于时取得最大值),同时需要保证j位置上的数要小于heights[j](题目中的要求，美丽塔的要求);即t=min(pre,heights[j])pre表示的是下标是(j,i]的最小的值 对于i右边的序列:需要满足序列是非递增的，同时每个值尽可能大 所以满足：j的位置上的数<=[i,j)上的最小的值(等于时取得最大值),同时需要保证j位置上的数要小于heigh...