8378人阅读
搜索（13）
动态规划（10）
思维技巧（20）
[编程题] 合唱团
有 n 个学生站成一排，每个学生有一个能力值，牛牛想从这 n 个学生中按照顺序选取 k 名学生，要求相邻两个学生的位置编号的差不超过 d，使得这 k 个学生的能力值的乘积最大，你能返回最大的乘积吗？&
每个输入包含 1 个测试用例。每个测试数据的第一行包含一个整数 n (1 &= n &= 50)，表示学生的个数，接下来的一行，包含 n 个整数，按顺序表示每个学生的能力值 ai（-50 &= ai &= 50）。接下来的一行包含两个整数，k 和 d (1 &= k &= 10, 1 &= d &= 50)。
输出一行表示最大的乘积。
分析：dp。由于本题求的是乘积最大，而且数据存在负数，那么就需要存储最大值以及最小值。dp[i][j] 表示选第 i 个学生作为第 j 个备选人，mins存最小值，maxs存最大值。
代码清单：
#include &cstdio&
#include &cstring&
#include &iostream&
#include &algorithm&
const int maxn = 50 + 5;
const long long minn = -1e17;
struct DP {
}dp[maxn][15];
int a[maxn];
void input() {
for(int i = 1; i &= ++i) {
scanf(&%d&, &a[i]);
scanf(&%d%d&, &k, &d);
void solve() {
memset(dp, 0, sizeof(dp));
for(int i = 1; i &= ++i) dp[i][1].mins = dp[i][1].maxs = a[i];
long long ans =
for(int i = 1; i &= ++i) {
for(int ki = 2; ki &= ++ki) {
int j = i -
if(j &= 0) j = 1;
for(; j & ++j) {
dp[i][ki].mins = min(dp[i][ki].mins, min(dp[j][ki - 1].mins * a[i], dp[j][ki - 1].maxs * a[i]));
dp[i][ki].maxs = max(dp[i][ki].maxs, max(dp[j][ki - 1].mins * a[i], dp[j][ki - 1].maxs * a[i]));
for(int i = 1; i &= ++i) {
ans = max(ans, dp[i][k].maxs);
printf(&%lld\n&, ans);
int main() {
while(scanf(&%d&, &n) != EOF) {
[编程题] 地牢逃脱
给定一个 n 行 m 列的地牢，其中 '.' 表示可以通行的位置，'X' 表示不可通行的障碍，牛牛从 (x0&, y0&)
位置出发，遍历这个地牢，和一般的游戏所不同的是，他每一步只能按照一些指定的步长遍历地牢，要求每一步都不可以超过地牢的边界，也不能到达障碍上。地牢的出口可能在任意某个可以通行的位置上。牛牛想知道最坏情况下，他需要多少步才可以离开这个地牢。&
每个输入包含 1 个测试用例。每个测试用例的第一行包含两个整数 n 和 m（1 &= n, m &= 50），表示地牢的长和宽。接下来的 n 行，每行 m 个字符，描述地牢，地牢将至少包含两个 '.'。接下来的一行，包含两个整数 x0, y0，表示牛牛的出发位置（0 &= x0 & n, 0 &= y0 & m，左上角的坐标为 （0, 0），出发位置一定是 '.'）。之后的一行包含一个整数 k（0 & k &= 50）表示牛牛合法的步长数，接下来的 k 行，每行两个整数 dx, dy 表示每次可选择移动的行和列步长（-50 &= dx, dy &= 50）
输出一行一个数字表示最坏情况下需要多少次移动可以离开地牢，如果永远无法离开，输出 -1。以下测试用例中，牛牛可以上下左右移动，在所有可通行的位置.上，地牢出口如果被设置在右下角，牛牛想离开需要移动的次数最多，为3次。
分析：bfs。当存在 ‘.’ 的位置没有访问，输出-1。
代码清单：
#include &set&
#include &cmath&
#include &queue&
#include &vector&
#include &cstdio&
#include &cstring&
#include &iostream&
#include &algorithm&
const int maxn = 50 + 5;
struct que {
que(int _x, int _y, int _step) {
this -& x = _x;
this -& y = _y;
this -& step = _
char tmap[maxn][maxn];
int dx[maxn], dy[maxn];
void input() {
for(int i = 0; i & ++i) {
scanf(&%s&, tmap[i]);
scanf(&%d%d&, &sx, &sy);
scanf(&%d&, &k);
for(int i = 0; i & ++i) {
scanf(&%d%d&, &dx[i], &dy[i]);
bool check(int x, int y) {
return (x &= 0 && x & n && y &= 0 && y & m && tmap[x][y] == '.');
int bfs() {
queue &que&
q.push(que(sx, sy, 0));
bool vis[maxn][maxn];
memset(vis, false, sizeof(vis));
vis[sx][sy] =
int ans = 0;
while(!q.empty()) {
que p = q.front(); q.pop();
ans = max(ans, p.step);
for(int i = 0; i & ++i) {
int xx = p.x + dx[i];
int yy = p.y + dy[i];
if(!vis[xx][yy] && check(xx, yy)) {
vis[xx][yy] =
q.push(que(xx, yy, p.step + 1));
for(int i = 0; i & ++i) {
for(int j = 0; j & ++j) {
if(tmap[i][j] == '.' && vis[i][j] == false) {
return -1;
void solve() {
printf(&%d\n&, bfs());
int main() {
while(scanf(&%d%d&, &n, &m) != EOF) {
[编程题] 下厨房
牛牛想尝试一些新的料理，每个料理需要一些不同的材料，问完成所有的料理需要准备多少种不同的材料。&
每个输入包含 1 个测试用例。每个测试用例的第 i 行，表示完成第 i 件料理需要哪些材料，各个材料用空格隔开，输入只包含大写英文字母和空格，输入文件不超过 50 行，每一行不超过 50 个字符。
输出一行一个数字表示完成所有料理需要多少种不同的材料。
BUTTER FLOUR
HONEY FLOUR EGG
分析：map一下就好。
代码清单：
#include &set&
#include &map&
#include &cmath&
#include &queue&
#include &vector&
#include &cstdio&
#include &cstring&
#include &iostream&
#include &algorithm&
char str[55];
map&string,int&m;
int main() {
//freopen(&wangyi03.txt&, &r&, stdin);
m.clear();
while(scanf(&%s&, str) != EOF) {
if(m.count(str) == 0) {
m[str] = ++
printf(&%d\n&, cont);
[编程题] 分田地
牛牛和 15 个朋友来玩打土豪分田地的游戏，牛牛决定让你来分田地，地主的田地可以看成是一个矩形，每个位置有一个价值。分割田地的方法是横竖各切三刀，分成 16 份，作为领导干部，牛牛总是会选择其中总价值最小的一份田地， 作为牛牛最好的朋友，你希望牛牛取得的田地的价值和尽可能大，你知道这个值最大可以是多少吗？&
每个输入包含 1 个测试用例。每个测试用例的第一行包含两个整数 n 和 m（1 &= n, m &= 75），表示田地的大小，接下来的 n 行，每行包含 m 个 0-9 之间的数字，表示每块位置的价值。
输出一行表示牛牛所能取得的最大的价值。
分析：二分 + 枚举。二分答案判断可行性。
可行性判断：假定二分值为mid。暴力枚举竖切的位置，然后看横切能切多少刀。枚举横切时，当这部分的4个矩形的价值都大于等于mid，说明这一刀切得合理，从这个位置开始继续往下枚举横切。如果最终横切的刀数大于等于4，那么说明这个值mid是合理的，否则不合理。通过这样的不断压缩区间，最终必然能够得到答案。
其中如何巧妙计算每个小矩形的和，也是可以通过预处理然后得到的。具体可见代码。
代码清单：
#include &cstdio&
#include &cstring&
#include &iostream&
#include &algorithm&
const int maxn = 75 + 5;
char str[maxn];
int a[maxn][maxn];
int sum[maxn][maxn];
void input() {
for(int i = 1; i &= ++i) {
scanf(&%s&, str + 1);
for(int j = 1; j &= ++j) {
a[i][j] = str[j] - '0';
int getArea(int x1, int y1, int x2, int y2) {
return (sum[x2][y2] - sum[x2][y1] - sum[x1][y2] + sum[x1][y1]);
bool judge(int mid) {
for(int j1 = 1; j1 &= m - 3; ++j1) {
for(int j2 = j1 + 1; j2 &= m - 2; ++j2) {
for(int j3 = j2 + 1; j3 &= m - 1; ++j3) {
int prei = 0, cnt = 0;
for(int i = 1; i &= ++i) {
int cube1 = getArea(prei, 0, i, j1);
int cube2 = getArea(prei, j1, i, j2);
int cube3 = getArea(prei, j2, i, j3);
int cube4 = getArea(prei, j3, i, m);
if(cube1 &= mid && cube2 &= mid && cube3 &= mid && cube4 &= mid) {
if(cnt &= 4)
void solve() {
memset(sum, 0, sizeof(sum));
for(int i = 1; i &= ++i) {
for(int j = 1; j &= ++j) {
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + a[i][j];
int l = 0, r = sum[n][m],
int ans = 0;
while(l &= r) {
mid = (l + r) && 1;
if(judge(mid)) {
l = mid + 1;
r = mid - 1;
printf(&%d\n&, ans);
int main() {
while(scanf(&%d%d&, &n, &m) != EOF) {
[编程题] 分苹果
n 只奶牛坐在一排，每个奶牛拥有 ai&个苹果，现在你要在它们之间转移苹果，使得最后所有奶牛拥有的苹果数都相同，每一次，你只能从一只奶牛身上拿走恰好两个苹果到另一个奶牛上，问最少需要移动多少次可以平分苹果，如果方案不存在输出 -1。&
每个输入包含一个测试用例。每个测试用例的第一行包含一个整数 n（1 &= n &= 100），接下来的一行包含 n 个整数 ai（1 &= ai &= 100）。
输出一行表示最少需要移动多少次可以平分苹果，如果方案不存在则输出 -1。
首先判断不存在的情况。
1）当总和不能均分时；
2）当数据中同时出现了偶数以及奇数时；
3）当所有数为偶数并且总和均分为奇数 or 所有数为奇数并且总和均分为偶数时；
以上任一条件满足的时候直接输出-1即可。
否则，一遍循环找比均分值大的数，然后相减除2，累计即可。
代码清单：
#include &set&
#include &map&
#include &cmath&
#include &queue&
#include &vector&
#include &cstdio&
#include &cstring&
#include &iostream&
#include &algorithm&
const int maxn = 100 + 5;
int a[maxn];
void input() {
for(int i = 0; i & ++i) {
scanf(&%d&, &a[i]);
void solve() {
int suma = 0;
bool odd =
bool even =
for(int i = 0; i & ++i) {
suma += a[i];
if(a[i] % 2) odd =
else even =
int ave = suma /
if(suma % n) {
printf(&-1\n&);
else if(odd && even) {
printf(&-1\n&);
else if((odd && ave % 2 == 0) || (even && ave % 2 != 0)) {
printf(&-1\n&);
int ans = 0;
for(int i = 0; i & ++i) {
if(a[i] & ave) ans += (a[i] - ave) / 2;
printf(&%d\n&, ans);
int main() {
while(scanf(&%d&, &n) != EOF) {
[编程题] 星际穿越
航天飞行器是一项复杂而又精密的仪器，飞行器的损耗主要集中在发射和降落的过程，科学家根据实验数据估计，如果在发射过程中，产生了 x 程度的损耗，那么在降落的过程中就会产生 x2&程度的损耗，如果飞船的总损耗超过了它的耐久度，飞行器就会爆炸坠毁。问一艘耐久度为 h 的飞行器，假设在飞行过程中不产生损耗，那么为了保证其可以安全的到达目的地，只考虑整数解，至多发射过程中可以承受多少程度的损耗？&
每个输入包含一个测试用例。每个测试用例包含一行一个整数 h （1 &= h &= 10^18）。
输出一行一个整数表示结果。
分析：暴力。令 x = sqrt(h)，然后判断 x 是否满足题意（x + x * x &= h），若不满足，则 x -= 1 直到满足为止。
代码清单：
#include &set&
#include &map&
#include &cmath&
#include &queue&
#include &vector&
#include &cstdio&
#include &cstring&
#include &iostream&
#include &algorithm&
int main() {
while(scanf(&%lld&, &h) != EOF) {
long long x = (long long)sqrt(h);
for(; x &= 0; --x) {
if(x + x * x &= h) {
printf(&%lld\n&, x);
[编程题] 藏宝图
牛牛拿到了一个藏宝图，顺着藏宝图的指示，牛牛发现了一个藏宝盒，藏宝盒上有一个机关，机关每次会显示两个字符串 s 和 t，根据古老的传说，牛牛需要每次都回答 t 是否是 s 的子序列。注意，子序列不要求在原字符串中是连续的，例如串 abc，它的子序列就有 {空串, a, b, c, ab, ac, bc, abc} 8 种。&
每个输入包含一个测试用例。每个测试用例包含两行长度不超过 10 的不包含空格的可见 ASCII 字符串。
输出一行 “Yes” 或者 “No” 表示结果。
分析：模拟。两个指针分别指向两个字符串，然后循环判断即可。
代码清单：
#include &set&
#include &map&
#include &cmath&
#include &queue&
#include &vector&
#include &cstdio&
#include &cstring&
#include &iostream&
#include &algorithm&
const int maxs = 1000 + 5;
char str1[maxs];
char str2[maxs];
int main() {
while(scanf(&%s%s&, str1, str2) != EOF) {
int len1 = strlen(str1);
int len2 = strlen(str2);
if(len1 & len2) {
printf(&No\n&);
int i1 = 0, i2 = 0;
while(i1 & len1 && i2 & len2) {
if(str1[i1] == str2[i2]) {
if(i2 == len2) {
printf(&Yes\n&);
printf(&No\n&);
[编程题] 数列还原
牛牛的作业薄上有一个长度为 n 的排列 A，这个排列包含了从1到n的n个数，但是因为一些原因，其中有一些位置（不超过 10 个）看不清了，但是牛牛记得这个数列顺序对的数量是 k，顺序对是指满足 i & j 且 A[i] & A[j] 的对数，请帮助牛牛计算出，符合这个要求的合法排列的数目。&
每个输入包含一个测试用例。每个测试用例的第一行包含两个整数 n 和 k（1 &= n &= 100, 0 &= k &= ），接下来的 1 行，包含 n 个数字表示排列 A，其中等于0的项表示看不清的位置（不超过 10 个）。
输出一行表示合法的排列数目。
分析：暴力 + 预处理。由于未知数不超过10个，那么可以用next_permutation暴力枚举未知数的安插顺序。那么如何来求出总的顺序对呢？总顺序对可以拆分为三部分，即：
总顺序对 = 已知数间的顺序对 + 未知数间的顺序对 + 已知数和未知数间的顺序对；第一部分可以先求出来 O(100^2)，第二部分在每次暴力枚举时可以求出 O(55)，关键是第三部分，我们可以这样预处理，计算出每个未知数在每个位置上与已知数之间产生的顺序对数，这个是可以做到的，即算左边比它小的数有多少，右边算比它大的数。时间复杂度大概也就在O(10 * 100)。这样算来总的复杂度为：O(10! * 55)，是可以通过的。
代码清单：
#include &set&
#include &map&
#include &cmath&
#include &queue&
#include &vector&
#include &cstdio&
#include &cstring&
#include &iostream&
#include &algorithm&
const int maxn = 100 + 5;
int A[maxn];
int B[15];
bool vis[maxn];
void input() {
memset(vis, false, sizeof(vis));
for(int i = 0; i & ++i) {
scanf(&%d&, &A[i]);
vis[A[i]] =
int get_pair(int *a, int x) {
int cnt = 0;
for(int i = 0; i & x - 1; ++i) {
for(int j = i + 1; j & ++j) {
if(a[i] & a[j]) cnt += 1;
void solve() {
if(k & n * (n + 1) / 2) {
printf(&0\n&);
for(int i = 1; i &= ++i) {
if(!vis[i]) B[bidx++] =
int pair1 = 0;
for(int i = 0; i & ++i) {
if(A[i] == 0)
for(int j = i + 1; j & ++j) {
if(A[j] != 0 && A[i] & A[j]) {
pair1 += 1;
int left[maxn][15], right[maxn][15];
memset(left, 0, sizeof(left));
memset(right, 0, sizeof(right));
for(int i = 0; i & ++i) {
int cnt = 0, id = 0;
for(int j = 0; j & ++j) {
if(A[j] != 0) {
if(A[j] & B[i]) cnt += 1;
left[B[i]][id++] =
cnt = 0; id = bidx - 1;
for(int j = n - 1; j &= 0; --j) {
if(A[j] != 0) {
if(A[j] & B[i]) cnt += 1;
right[B[i]][id--] =
int ans = 0;
int sum = pair1 + get_pair(B, bidx);
for(int i = 0; i & ++i) {
sum = sum + left[B[i]][i] + right[B[i]][i];
if(sum == k) ans += 1;
}while(next_permutation(B, B + bidx));
printf(&%d\n&, ans);
int main() {
while(scanf(&%d%d&, &n, &k) != EOF) {
题目链接：
&&相关文章推荐
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：119527次
积分：2799
积分：2799
排名：第13361名
原创：163篇
评论：54条
(4)(7)(4)(10)(8)(21)(25)(12)(1)(23)(11)(10)(1)(3)(4)(1)(4)(16)(1)(1)
(window.slotbydup = window.slotbydup || []).push({
id: '4740887',
container: s,
size: '250,250',
display: 'inlay-fix'}