CSP第一轮模测五

您的姓名：

在n*m的棋盘上放置k个国王，要求k个国王互相不攻击，有多少种不同的放置方法。假设国王放置在第(x,y)格，国王的
攻击的区域是：(x-1,y-1), (x-1,y),(x-1,y+1),(x,y-1),(x,y+1),(x+1,y-1),(x+1,y),(x+1,y+1)。
读入三个数n,m,k，输出答案。
题目利用回溯法求解。棋盘行标号为0~n-1，列标号为0~m-1。
#include <bits/stdc++.h>
using namespace std;
int n, m, k, ans;
int hash[5][5];
void work(int x, int y, int tot) {
int i, j;
if (tot == k) {ans++; return;}
do {
while (hash[x][y]) {
y++;
if (y == m) {x++; y =___（1）___;}
if (x == n) return;
}
for (i = x - 1; i <= x + 1; i++)
if (i >= 0 && i < n)
for (j = y - 1; j <= y + 1; j++)
if (j >= 0 && j < m)
___（2）___;
___（3）___;
for (i = x - 1; i <= x + 1; i++)
if (i >= 0 && i < n)
for (j = y - 1; j <= y + 1; j++)
if (j >= 0 && j < m)
___（4）___;
y++;
if (y == m) {x++; y = 0;}
if (x == n) return;
} while (1);
}
int main( ) {
scanf("%d%d%d", &n, &m, &k);
ans = 0;
memset(hash, 0, sizeof(hash));
___（5）___;
printf("%d\n", ans);
return 0;
}
（1）处应填写

（2）处应填写

（3）处应填写

（4）处应填写：

（5）处应填写

给出一个数列（元素个数不多于100），数列元素均为负整数、正整数、0。
请找出数列中的一个连续子数列，使得这个子数列中包含的所有元素之和最大，在和最大的前提下还要求该子数列包含
的元素个数最多，并输出这个最大和以及该连续子数列中元素的个数。
例如：
输入：5 4 -5 3 2 4时，输出：9 3
输入：7 1 2 3 -5 0 7 8时，输出：16 7
#include <bits/stdc++.h>
using namespace std;
int a[101];
int n, i, ans, len, tmp, beg;
int main(void) {
cin >> n;
for (i = 1; i <= n; i++) cin >> a[i];
tmp = 0; ans = 0; len = 0;
beg = ___（1）___;
for (i = 1; i <= n; i++) {
if (tmp + a[i] > ans) {ans = tmp + a[i]; len = i - beg;}
else if (___（2）___&& i - beg > len) len = i - beg;
if (tmp + a[i] < ___（3）___) {beg = ___（4）___; tmp = 0;}
else ___（5）___;
}
cout << ans << " " << len << endl;
return 0;
}
（1）处应填写：

（2）处应填写

（3）处应填写

（4）处应填写

(5)处应填写

给输入一个n1*m1的矩阵a，和n2*m2的矩阵b，问a中是否存在子矩阵和b相等。
若存在，输出所有子矩阵左上角的坐标；若不存在输出“There is no answer”。
#include <bits/stdc++.h>
using namespace std;
const int SIZE = 50;
int n1, m1, n2, m2, a[SIZE][SIZE], b[SIZE][SIZE];
int main( ) {
int i, j, k1, k2;
bool good, haveAns;
cin >> n1 >> m1;
for (i = 1; i <= n1; i++)
for (j = 1; j <= m1; j++)
___（1）___;
cin >> n2 >> m2;
for (i = 1; i <= n2; i++)
for (j = 1; j <= m2; j++)
cin>>b[i][j];
haveAns = false;
for (i = 1; i <= n1 - n2 + 1; i++)
for (j = 1; j <= ___（2）___; j++) {
___（3）___;
for (k1 = 1; k1 <= n2; k1++)
for (k2 = 1; k2 <= ___（4）___; k2++)
if (a[i + k1 - 1][j + k2 - 1] != b[k1][k2])
good = false;
if (good) {cout << i << ' ' << j << endl; ___（5）___;}
}
if (!haveAns) cout << "There is no answer" << endl;
return 0;
}
（1）处应填写

（2）处应填写

（3）处应填写

（4）处应填写

(5)处应填写