题目 有一串长度为 n 的小写字母组成的字符串，可以从中挑选 'k' 'i' 'n' 'g' 四个字符组成一支礼炮，或者从中挑选 'k' 'i' 'n' 'g' 'i' 'n' 'g' 七个字符组成两支礼炮。请问最多能挑选多少礼炮？ 解题思路 先遍历一遍字符串，统计出 k、i、n、g 这 4 个字符的个数。记字符 k 的个数为 ，后面 3 个字符的个数的最小值为 。 如果 ，可以每 4 个字符组成一支礼炮，。 如果 ，可以每 7 个字符组成两支礼炮，。 如果 ，既有4字符礼炮，又有7字符礼炮，。 C++代码 #include<iostream> using namespace ...

题目 给定一个整数 ，表示 3 个正实数的乘积，求这 3 个正实数的最小和。 解题思路 根据基本不等式，有：。 所以 的最小值是 。 C++代码 #include<cstdio> #include<cmath> using namespace std; int main(){ int n; scanf("%d", &n); double ans = 3 * pow(n, 1/3.0); printf("%.3lf", ans); return 0; }

题目 一家超市出售一套产品 。在截止期限 内，它为每种产品 赚取利润 ，该期限是从开始销售​​之时起以时间单位的整数表示的。每种产品仅花费一个时间单位就可以出售。销售进度表 是产品 的有序子集，根据 的顺序，每个产品 的销售在截止期限 之前或 到期时完成。销售计划的利润为 。最佳销售时间表是利润最高的时间表。 编写一个程序，该程序从输入文本文件中读取产品集，并为每组产品计算最佳销售计划的利润。 解题思路 直接使用贪心算法 将产品按照利润从大到小进行排序，优先售卖利润高的产品。遍历产品，对于每个产品 ，它可以选择在第 1 到第 个时间单位售卖。而对于每个产品，越晚卖越好，这样可...

题目 牛妹在玩一个名为矩阵消除的游戏，矩阵的大小是 行 列，第 行第 列的单元格的权值为 。牛妹可以进行 个回合的游戏，在每个回合，牛妹可以选择一行或者选择一列，然后将这一行或者这一列的所有单元格中的权值变为 0，同时牛妹的分数会加上这一行或者这一列中的所有单元格的权值的和。求牛妹的最大得分。 解题思路 如果 或 ，那么可以选择矩阵的所有数，直接返回矩阵中数的总和。 使用二进制枚举的方法，枚举所有行的情况： 的二进制中，如果第 位为 0，则表示没有选择第 行，否则表示选择了这一行。如果选中的行数 大于 ，表示这种情况不存在。计算选中的所有行的和 ，然后将这些行的数据清零，记录...

题目 有 件货物， 第 件重 吨，另有 个集装箱，每个集装箱可以装重量不超过 吨的货物。货物不能分拆，请判断这 个集装箱能否装下所有货物。 解题思路 先确定最重的货物重量 ，如果 ，因为货物不能分拆，所以这些集装箱不能装下这个货物。 再比较 和 ，如果 ，那么每个货物都可以单独放置一个集装箱，所以答案是 Yes。 如果 ，使用回溯算法。 表示第 个集装箱当前装下货物的重量。 回溯算法：试着将第 个货物放到第 个集装箱中，如果可以装下，就装进去，，然后装第 个货物。如果装完了所有货物，就返回 true。如果上述方案失败，就返回前一步，重置成之前的状态，，将第 ...

题目 有一个长度为 n 的序列 a，保证它是一个 01 序列，并执行以下两种操作： 单点修改：将位置 x 上的数翻转（0 变 1，1 变 0）； 前缀修改：将位置 1~x 上的数翻转（每个数都 0 变 1，1 变 0）。 求：使得数列上的所有数都变为 0 的最小翻转次数。 解题思路 动态规划 表示将序列中前 个数都变为 0 的最小翻转次数。 表示将序列中前 个数都变为 1 的最小翻转次数。 遍历序列，如果 ， 要想将序列前 个数变为 0，可以使用单点修改直接将 变为 0，翻转次数为 。或者使用前缀修改，翻转次数为 。所以，。 要想将序列前 个数变为 1，可以不需更改，翻转次...

题目 牛牛：我们来玩取石子游戏。一共有 颗石子，每个人每次可以取 1 或 2 颗石子，谁取走了最后一颗石子就算谁获胜。牛妹：这游戏太无聊了。牛牛：那改一改。一共有 颗石子，每个人每次可以取 颗石子，谁取走了最后一颗石子就算谁获胜。牛妹：好的，你先开始取吧。牛牛心里知道自己是否有必胜策略，但他想来考考你。因为牛牛和牛妹很爱玩这种游戏，所以本题有多组数据。（注：牛牛叫 Alan，牛妹叫 Frame。） 解题思路 如果只剩下 3 颗石子，那么谁先手，就谁输。 如果 是 3 的倍数，那么 Alan 不可能取完所有石子，因为 3 不可能整除 。这时，Frame 可以取 1 颗或 2 颗石子，让剩...

题目 给定一个长度为 的序列 ，你需要从中挑出任意多个（可以 0 个）数，使得他们 & 起来值最大。 解题思路 给定两个整数 和 ，。所以，序列 中的最大值就是答案。 C++代码 #include<iostream> using namespace std; int main(){ int T, n; cin >> T; while(T--){ cin >> n; int ans = 0; int a; for(int i=0; i<n; ++i){...

题目 牛牛得到了一个字符串（可能含有空格），他希望在这些字符串中提取出数字。例如：a1b23c456d007890 中可以提取出 1、23、456、7890 共4个数字。 现在，他得到了一个长度高达 1000 的字符串，请你帮他提取出所有的数字。 本题有多组数据。输出提取出的所有数字，相邻两个数字用一个空格隔开。不包含数字的时候输出空行。注意，输出的数不能含有前导 0。 解题思路 遍历字符串的每个字符。如果遇到了字符是数字的话，先判断是不是 0。 如果是 0，继续向后遍历，直到出现其他数字，直接输出数字；如果没有遇到其他数字，而是非数字字符，则输出 0。 如果是其他数字，直接输出数字，直到遇...

题目 牛牛得到了一份寻宝图，根据寻宝图的指示，牛牛在一个 的网格中，牛牛的位置在 ，宝藏的位置在 。由于寻宝需要按照特定规则，所以牛牛只能往上走或者往右走。藏宝人为了让故意为难牛牛，在地图中设置了一块长方形的陷阱区域，陷阱左下坐标为 ，右上坐标为 ，牛牛要是碰到了陷阱可能会有生命危险。牛牛能顺利找到宝藏有多少种不同的寻宝路径？ 解题思路 动态规划 表示顺利到达位置 时的路径数目。牛牛可以往上走或往右走，所以 。当然前提是位置 不是位于陷阱区域。如果是的话，。最后，返回 作为答案。 C++代码 class Solution { const int mod = 1e9+7; pu...

题目 牛牛和牛妹进行石头剪刀布游戏。游戏规则如下：两个人进行石头剪刀布大战，开始时会发给每个人 张牌，然后两人进行 次剪刀石头布大战，每一次两人分别选择自己的 张牌中的一张，打出，每张牌只能用一次。牛牛每赢一局会 +1 分，每输一局会 -1 分，每平局一局不加分也不减分。开始发给牛牛的 张牌里，有 张石头牌， 张剪刀牌， 张布牌。开始发给牛妹的 张牌里，有 张石头牌， 张剪刀牌， 张布牌。 请问在知道牛妹每一轮出什么牌的情况下，牛牛最终的分数最高多少分？ 解题思路 先计算牛牛最多能赢多少轮：，得到了这么多分。并将发出的牌减去相应数目。然后计算平局的次数：。这些局不得分。最后把 ...

题目 下课了，牛牛要去食堂吃饭，他们学校的食堂有很多个门，而且整个建筑物是圆形的。只不过要去吃饭的人很多，在里面吃饭的人也很多，所以大家都在门口外面排队等待吃饭。 所以牛牛采取了这样的一个策略：刚开始时，牛牛在第一个门口，如果这个门口有人在排队，那么他选择花费 1 分钟时间走到下一个门口，如果没有人的话，牛牛就可以直接进去吃饭啦。食堂的每一个门，每 1 分钟排队的人数都会减少一个。 现在给出门的数量 ，和每个门外排队的人的数量，如果按照牛牛的策略，那么牛牛最终会在哪个门进去吃饭呢？ 解题思路 牛牛在第 1 门开始进行第 1 轮排队， 分钟后，每个门口排队的人都会减少 个人（如果有这么多人的话...

题目 牛牛和牛妹进行石头剪刀布游戏。游戏规则如下：两个人进行石头剪刀布大战，开始时会发给每个人 张牌，然后两人进行 次剪刀石头布大战，每一次两人分别选择自己的 张牌中的一张，打出，每张牌只能用一次。开始发给牛牛的 张牌里，有 张石头牌， 张剪刀牌， 张布牌。开始发给牛妹的 张牌里，有 张石头牌， 张剪刀牌， 张布牌。请问在知道牛妹每一轮出什么牌的情况下，牛牛最多能赢多少局比赛？ 解题思路 牛妹出石头牌，牛牛出布牌，牛牛赢的次数为 。牛妹出剪刀牌，牛牛出石头牌，牛牛赢的次数为 。牛妹出布牌，牛牛出剪刀牌，牛牛赢的次数为 。 C++代码 class Solution { public...

题目 Shuseki 群岛是 Yutampo 海中 30001 个小岛的群岛。这些岛沿一条线均匀分布，从西到东编号从 0 到 30000。这些岛屿拥有许多宝藏。在 Shuseki 群岛***有 颗宝石，而第 颗宝石位于 岛上。（） Kitayuta 先生刚到达 0 岛。凭借出色的跳跃能力，他将按照以下过程向东部的岛屿反复跳跃： 首先，他将从岛 0 跳到岛 。（） 之后，他将根据以下规则继续跳跃。令 为前一次跳跃的长度，即，如果他的前一次跳跃是从岛 到岛 ，则令 。他将向东进行长度为 ， 或 的跳跃。即他可以跳至岛 ， 或 （如果存在）。跳跃的长度必须为正数，即当 时，他不能执行长...