全部知识点
第1561题
#include<algorithm>
#include<iostream>
#include<limits>
using namespace std;
const int MAXN = 105;
const int MAXK = 105;
int h[MAXN][MAXK];
int f(int n, int m)
{
if (m == 1) return n;
if (n == 0) return 0;
int ret = numeric_limits::max();
for (int i = 1; i <= n; i++)
ret = min(ret, max(f(n - i, m), f(i - 1, m - 1)) + 1);
return ret;
}
int g(int n, int m)
{
for (int i = 1; i <= n; i++)
h[i][1] = i;
for (int j = 1; j <= m; j++)
h[0][j] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 2; j <= m; j++) {
h[i][j] = numeric_limits::max();
for (int k = 1; k <= i; k++)
h[i][j] = min(h[i][j],max(h[i - k][j], h[k - 1][j - 1]) + 1);
}
}
return h[n][m];
}
int main()
{
int n, m;
cin >> n >> m;
cout << f(n, m) << endl << g(n, m) << endl;
return 0;
}假设输入的 n、m 均是不超过 100 的正整数，输出的两行整数总是相同的。
第1562题
#include<algorithm>
#include<iostream>
#include<limits>
using namespace std;
const int MAXN = 105;
const int MAXK = 105;
int h[MAXN][MAXK];
int f(int n, int m)
{
if (m == 1) return n;
if (n == 0) return 0;
int ret = numeric_limits::max();
for (int i = 1; i <= n; i++)
ret = min(ret, max(f(n - i, m), f(i - 1, m - 1)) + 1);
return ret;
}
int g(int n, int m)
{
for (int i = 1; i <= n; i++)
h[i][1] = i;
for (int j = 1; j <= m; j++)
h[0][j] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 2; j <= m; j++) {
h[i][j] = numeric_limits::max();
for (int k = 1; k <= i; k++)
h[i][j] = min(h[i][j],max(h[i - k][j], h[k - 1][j - 1]) + 1);
}
}
return h[n][m];
}
int main()
{
int n, m;
cin >> n >> m;
cout << f(n, m) << endl << g(n, m) << endl;
return 0;
}假设输入的 n、m 均是不超过 100 的正整数，当 m 为 1 时，输出的第一行总为 n。
第1563题
#include<algorithm>
#include<iostream>
#include<limits>
using namespace std;
const int MAXN = 105;
const int MAXK = 105;
int h[MAXN][MAXK];
int f(int n, int m)
{
if (m == 1) return n;
if (n == 0) return 0;
int ret = numeric_limits::max();
for (int i = 1; i <= n; i++)
ret = min(ret, max(f(n - i, m), f(i - 1, m - 1)) + 1);
return ret;
}
int g(int n, int m)
{
for (int i = 1; i <= n; i++)
h[i][1] = i;
for (int j = 1; j <= m; j++)
h[0][j] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 2; j <= m; j++) {
h[i][j] = numeric_limits::max();
for (int k = 1; k <= i; k++)
h[i][j] = min(h[i][j],max(h[i - k][j], h[k - 1][j - 1]) + 1);
}
}
return h[n][m];
}
int main()
{
int n, m;
cin >> n >> m;
cout << f(n, m) << endl << g(n, m) << endl;
return 0;
}假设输入的 n、m 均是不超过 100 的正整数，算法 g(n,m)最为准确的时间复杂度分析结果为（ ）。
第1564题
#include<algorithm>
#include<iostream>
#include<limits>
using namespace std;
const int MAXN = 105;
const int MAXK = 105;
int h[MAXN][MAXK];
int f(int n, int m)
{
if (m == 1) return n;
if (n == 0) return 0;
int ret = numeric_limits::max();
for (int i = 1; i <= n; i++)
ret = min(ret, max(f(n - i, m), f(i - 1, m - 1)) + 1);
return ret;
}
int g(int n, int m)
{
for (int i = 1; i <= n; i++)
h[i][1] = i;
for (int j = 1; j <= m; j++)
h[0][j] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 2; j <= m; j++) {
h[i][j] = numeric_limits::max();
for (int k = 1; k <= i; k++)
h[i][j] = min(h[i][j],max(h[i - k][j], h[k - 1][j - 1]) + 1);
}
}
return h[n][m];
}
int main()
{
int n, m;
cin >> n >> m;
cout << f(n, m) << endl << g(n, m) << endl;
return 0;
}假设输入的 n、m 均是不超过 100 的正整数，当输入为“20 2”时，输出的第一行为（ ）。
第1565题
#include<algorithm>
#include<iostream>
#include<limits>
using namespace std;
const int MAXN = 105;
const int MAXK = 105;
int h[MAXN][MAXK];
int f(int n, int m)
{
if (m == 1) return n;
if (n == 0) return 0;
int ret = numeric_limits::max();
for (int i = 1; i <= n; i++)
ret = min(ret, max(f(n - i, m), f(i - 1, m - 1)) + 1);
return ret;
}
int g(int n, int m)
{
for (int i = 1; i <= n; i++)
h[i][1] = i;
for (int j = 1; j <= m; j++)
h[0][j] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 2; j <= m; j++) {
h[i][j] = numeric_limits::max();
for (int k = 1; k <= i; k++)
h[i][j] = min(h[i][j],max(h[i - k][j], h[k - 1][j - 1]) + 1);
}
}
return h[n][m];
}
int main()
{
int n, m;
cin >> n >> m;
cout << f(n, m) << endl << g(n, m) << endl;
return 0;
}假设输入的 n、m 均是不超过 100 的正整数，当输入为“100 100”时，输出的第一行为（ ）。
第1566题
#include<iostream>
using namespace std;
int n, k;
int solve1()
{
int l = 0, r = n;
while (l <= r) {
int mid = (l + r) / 2;
if (mid * mid <= n) l = mid + 1;
else r = mid - 1;
}
return l - 1;
}
double solve2(double x)
{
if (x == 0) return x;
for (int i = 0; i < k; i++)
x = (x + n / x) / 2;
return x;
}
int main()
{
cin >> n >> k;
double ans = solve2(solve1());
cout << ans << ' ' << (ans * ans == n) << endl;
return 0;
}假设 int 为 32 位有符号整数类型，输入的 n 是不超过 47000 的自然数、k 是不超过 int 表示范围的自然数，该算法最准确的时间复杂度分析结果为?(log? + ?)。
第1567题
#include<iostream>
using namespace std;
int n, k;
int solve1()
{
int l = 0, r = n;
while (l <= r) {
int mid = (l + r) / 2;
if (mid * mid <= n) l = mid + 1;
else r = mid - 1;
}
return l - 1;
}
double solve2(double x)
{
if (x == 0) return x;
for (int i = 0; i < k; i++)
x = (x + n / x) / 2;
return x;
}
int main()
{
cin >> n >> k;
double ans = solve2(solve1());
cout << ans << ' ' << (ans * ans == n) << endl;
return 0;
}假设 int 为 32 位有符号整数类型，输入的 n 是不超过 47000 的自然数、k 是不超过 int 表示范围的自然数，当输入为“9801 1”时，输出的第一个数为“99”。
第1568题
#include<iostream>
using namespace std;
int n, k;
int solve1()
{
int l = 0, r = n;
while (l <= r) {
int mid = (l + r) / 2;
if (mid * mid <= n) l = mid + 1;
else r = mid - 1;
}
return l - 1;
}
double solve2(double x)
{
if (x == 0) return x;
for (int i = 0; i < k; i++)
x = (x + n / x) / 2;
return x;
}
int main()
{
cin >> n >> k;
double ans = solve2(solve1());
cout << ans << ' ' << (ans * ans == n) << endl;
return 0;
}假设 int 为 32 位有符号整数类型，输入的 n 是不超过 47000 的自然数、k 是不超过 int 表示范围的自然数，对于任意输入的 n，随着所输入 k 的增大，输出的第二个数会变成“1”。
第1569题
#include<iostream>
using namespace std;
int n, k;
int solve1()
{
int l = 0, r = n;
while (l <= r) {
int mid = (l + r) / 2;
if (mid * mid <= n) l = mid + 1;
else r = mid - 1;
}
return l - 1;
}
double solve2(double x)
{
if (x == 0) return x;
for (int i = 0; i < k; i++)
x = (x + n / x) / 2;
return x;
}
int main()
{
cin >> n >> k;
double ans = solve2(solve1());
cout << ans << ' ' << (ans * ans == n) << endl;
return 0;
}假设 int 为 32 位有符号整数类型，输入的 n 是不超过 47000 的自然数、k 是不超过 int 表示范围的自然数，该程序有存在缺陷。当输入的 n 过大时，第 12 行的乘法有可能溢出，因此应当将 mid 强制转换为 64 位整数再计算。
第1570题
#include<iostream>
using namespace std;
int n, k;
int solve1()
{
int l = 0, r = n;
while (l <= r) {
int mid = (l + r) / 2;
if (mid * mid <= n) l = mid + 1;
else r = mid - 1;
}
return l - 1;
}
double solve2(double x)
{
if (x == 0) return x;
for (int i = 0; i < k; i++)
x = (x + n / x) / 2;
return x;
}
int main()
{
cin >> n >> k;
double ans = solve2(solve1());
cout << ans << ' ' << (ans * ans == n) << endl;
return 0;
}假设 int 为 32 位有符号整数类型，输入的 n 是不超过 47000 的自然数、k 是不超过 int 表示范围的自然数，当输入为“2 1”时，输出的第一个数最接近（ ）。
第1571题
#include<iostream>
using namespace std;
int n, k;
int solve1()
{
int l = 0, r = n;
while (l <= r) {
int mid = (l + r) / 2;
if (mid * mid <= n) l = mid + 1;
else r = mid - 1;
}
return l - 1;
}
double solve2(double x)
{
if (x == 0) return x;
for (int i = 0; i < k; i++)
x = (x + n / x) / 2;
return x;
}
int main()
{
cin >> n >> k;
double ans = solve2(solve1());
cout << ans << ' ' << (ans * ans == n) << endl;
return 0;
}假设 int 为 32 位有符号整数类型，输入的 n 是不超过 47000 的自然数、k 是不超过 int 表示范围的自然数，当输入为“3 10”时，输出的第一个数最接近（ ）。
第1572题
#include<iostream>
using namespace std;
int n, k;
int solve1()
{
int l = 0, r = n;
while (l <= r) {
int mid = (l + r) / 2;
if (mid * mid <= n) l = mid + 1;
else r = mid - 1;
}
return l - 1;
}
double solve2(double x)
{
if (x == 0) return x;
for (int i = 0; i < k; i++)
x = (x + n / x) / 2;
return x;
}
int main()
{
cin >> n >> k;
double ans = solve2(solve1());
cout << ans << ' ' << (ans * ans == n) << endl;
return 0;
}假设 int 为 32 位有符号整数类型，输入的 n 是不超过 47000 的自然数、k 是不超过 int 表示范围的自然数，当输入为“256 11”时，输出的第一个数（ ）。
第1573题
（枚举因数）从小到大打印正整数 n 的所有正因数，试补全枚举程序。
#include<bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vectorfac;
fac.reserve((int)ceil(sqrt(n)));
int i;
for (i = 1; i * i < n; ++i) {
if (①) {
fac.push_back(i);
}
}
for (int k = 0; k < fac.size(); ++k) {
cout << ② << " ";
}
if (③) {
cout << ④ << " ";
}
for (int k = fac.size() - 1; k >= 0; --k) {
cout << ⑤ << " ";
}
}①处应填（ ）。
第1574题
（枚举因数）从小到大打印正整数 n 的所有正因数，试补全枚举程序。
#include<bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vectorfac;
fac.reserve((int)ceil(sqrt(n)));
int i;
for (i = 1; i * i < n; ++i) {
if (①) {
fac.push_back(i);
}
}
for (int k = 0; k < fac.size(); ++k) {
cout << ② << " ";
}
if (③) {
cout << ④ << " ";
}
for (int k = fac.size() - 1; k >= 0; --k) {
cout << ⑤ << " ";
}
}②处应填（ ）。
第1575题
（枚举因数）从小到大打印正整数 n 的所有正因数，试补全枚举程序。
#include<bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vectorfac;
fac.reserve((int)ceil(sqrt(n)));
int i;
for (i = 1; i * i < n; ++i) {
if (①) {
fac.push_back(i);
}
}
for (int k = 0; k < fac.size(); ++k) {
cout << ② << " ";
}
if (③) {
cout << ④ << " ";
}
for (int k = fac.size() - 1; k >= 0; --k) {
cout << ⑤ << " ";
}
}③处应填（ ）。
第1576题
（枚举因数）从小到大打印正整数 n 的所有正因数，试补全枚举程序。
#include<bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vectorfac;
fac.reserve((int)ceil(sqrt(n)));
int i;
for (i = 1; i * i < n; ++i) {
if (①) {
fac.push_back(i);
}
}
for (int k = 0; k < fac.size(); ++k) {
cout << ② << " ";
}
if (③) {
cout << ④ << " ";
}
for (int k = fac.size() - 1; k >= 0; --k) {
cout << ⑤ << " ";
}
}④处应填（ ）。
第1577题
（枚举因数）从小到大打印正整数 n 的所有正因数，试补全枚举程序。
#include<bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vectorfac;
fac.reserve((int)ceil(sqrt(n)));
int i;
for (i = 1; i * i < n; ++i) {
if (①) {
fac.push_back(i);
}
}
for (int k = 0; k < fac.size(); ++k) {
cout << ② << " ";
}
if (③) {
cout << ④ << " ";
}
for (int k = fac.size() - 1; k >= 0; --k) {
cout << ⑤ << " ";
}
}⑤处应填（ ）。
第1578题
（洪水填充）现有用字符标记像素颜色的 8x8 图像。颜色填充的操作描述如下：给定起始像素的位置和待填充的颜色，将起始像素和所有可达的像素（可达的定义：经过一次或多次的向上、下、左、右四个方向移动所能到达且终点和路径上所有像素的颜色都与起始像素颜色相同），替换为给定的颜色。
#include<bits/stdc++.h>
using namespace std;
const int ROWS = 8;
const int COLS = 8;
struct Point {
int r, c;
Point(int r, int c) : r(r), c(c) {}
};
bool is_valid(char image[ROWS][COLS], Point pt,int prev_color, int new_color) {
int r = pt.r;
int c = pt.c;
return (0 <= r && r < ROWS && 0 <= c && c < COLS && ① && image[r][c] != new_color);
}
void flood_fill(char image[ROWS][COLS], Point cur, int new_color) {
queuequeue;
queue.push(cur);
int prev_color = image[cur.r][cur.c];
②;
while (!queue.empty()) {
Point pt = queue.front();
queue.pop();
Point points[4] = {③, Point(pt.r - 1, pt.c),Point(pt.r, pt.c + 1), Point(pt.r, pt.c - 1)};
for (auto p : points) {
if (is_valid(image, p, prev_color, new_color)) {
④;
⑤;
}
}
}
}
int main() {
char image[ROWS][COLS] = {{'g', 'g', 'g', 'g', 'g', 'g', 'g', 'g'},
{'g', 'g', 'g', 'g', 'g', 'g', 'r', 'r'},
{'g', 'r', 'r', 'g', 'g', 'r', 'g', 'g'},
{'g', 'b', 'b', 'b', 'b', 'r', 'g', 'r'},
{'g', 'g', 'g', 'b', 'b', 'r', 'g', 'r'},
{'g', 'g', 'g', 'b', 'b', 'b', 'b', 'r'},
{'g', 'g', 'g', 'g', 'g', 'b', 'g', 'g'},
{'g', 'g', 'g', 'g', 'g', 'b', 'b', 'g'}};
Point cur(4, 4);
char new_color = 'y';
flood_fill(image, cur, new_color);
for (int r = 0; r < ROWS; r++) {
for (int c = 0; c < COLS; c++) {
cout << image[r][c] << " ";
}
cout << endl;
}
// 输出：
// g g g g g g g g
// g g g g g g r r
// g r r g g r g g
// g y y y y r g r
// g g g y y r g r
// g g g y y y y r
// g g g g g y g g
// g g g g g y y g
return 0;
}①处应填（ ）。
第1579题
（洪水填充）现有用字符标记像素颜色的 8x8 图像。颜色填充的操作描述如下：给定起始像素的位置和待填充的颜色，将起始像素和所有可达的像素（可达的定义：经过一次或多次的向上、下、左、右四个方向移动所能到达且终点和路径上所有像素的颜色都与起始像素颜色相同），替换为给定的颜色。
#include<bits/stdc++.h>
using namespace std;
const int ROWS = 8;
const int COLS = 8;
struct Point {
int r, c;
Point(int r, int c) : r(r), c(c) {}
};
bool is_valid(char image[ROWS][COLS], Point pt,int prev_color, int new_color) {
int r = pt.r;
int c = pt.c;
return (0 <= r && r < ROWS && 0 <= c && c < COLS && ① && image[r][c] != new_color);
}
void flood_fill(char image[ROWS][COLS], Point cur, int new_color) {
queuequeue;
queue.push(cur);
int prev_color = image[cur.r][cur.c];
②;
while (!queue.empty()) {
Point pt = queue.front();
queue.pop();
Point points[4] = {③, Point(pt.r - 1, pt.c),Point(pt.r, pt.c + 1), Point(pt.r, pt.c - 1)};
for (auto p : points) {
if (is_valid(image, p, prev_color, new_color)) {
④;
⑤;
}
}
}
}
int main() {
char image[ROWS][COLS] = {{'g', 'g', 'g', 'g', 'g', 'g', 'g', 'g'},
{'g', 'g', 'g', 'g', 'g', 'g', 'r', 'r'},
{'g', 'r', 'r', 'g', 'g', 'r', 'g', 'g'},
{'g', 'b', 'b', 'b', 'b', 'r', 'g', 'r'},
{'g', 'g', 'g', 'b', 'b', 'r', 'g', 'r'},
{'g', 'g', 'g', 'b', 'b', 'b', 'b', 'r'},
{'g', 'g', 'g', 'g', 'g', 'b', 'g', 'g'},
{'g', 'g', 'g', 'g', 'g', 'b', 'b', 'g'}};
Point cur(4, 4);
char new_color = 'y';
flood_fill(image, cur, new_color);
for (int r = 0; r < ROWS; r++) {
for (int c = 0; c < COLS; c++) {
cout << image[r][c] << " ";
}
cout << endl;
}
// 输出：
// g g g g g g g g
// g g g g g g r r
// g r r g g r g g
// g y y y y r g r
// g g g y y r g r
// g g g y y y y r
// g g g g g y g g
// g g g g g y y g
return 0;
}②处应填（ ）。
第1580题
（洪水填充）现有用字符标记像素颜色的 8x8 图像。颜色填充的操作描述如下：给定起始像素的位置和待填充的颜色，将起始像素和所有可达的像素（可达的定义：经过一次或多次的向上、下、左、右四个方向移动所能到达且终点和路径上所有像素的颜色都与起始像素颜色相同），替换为给定的颜色。
#include<bits/stdc++.h>
using namespace std;
const int ROWS = 8;
const int COLS = 8;
struct Point {
int r, c;
Point(int r, int c) : r(r), c(c) {}
};
bool is_valid(char image[ROWS][COLS], Point pt,int prev_color, int new_color) {
int r = pt.r;
int c = pt.c;
return (0 <= r && r < ROWS && 0 <= c && c < COLS && ① && image[r][c] != new_color);
}
void flood_fill(char image[ROWS][COLS], Point cur, int new_color) {
queuequeue;
queue.push(cur);
int prev_color = image[cur.r][cur.c];
②;
while (!queue.empty()) {
Point pt = queue.front();
queue.pop();
Point points[4] = {③, Point(pt.r - 1, pt.c),Point(pt.r, pt.c + 1), Point(pt.r, pt.c - 1)};
for (auto p : points) {
if (is_valid(image, p, prev_color, new_color)) {
④;
⑤;
}
}
}
}
int main() {
char image[ROWS][COLS] = {{'g', 'g', 'g', 'g', 'g', 'g', 'g', 'g'},
{'g', 'g', 'g', 'g', 'g', 'g', 'r', 'r'},
{'g', 'r', 'r', 'g', 'g', 'r', 'g', 'g'},
{'g', 'b', 'b', 'b', 'b', 'r', 'g', 'r'},
{'g', 'g', 'g', 'b', 'b', 'r', 'g', 'r'},
{'g', 'g', 'g', 'b', 'b', 'b', 'b', 'r'},
{'g', 'g', 'g', 'g', 'g', 'b', 'g', 'g'},
{'g', 'g', 'g', 'g', 'g', 'b', 'b', 'g'}};
Point cur(4, 4);
char new_color = 'y';
flood_fill(image, cur, new_color);
for (int r = 0; r < ROWS; r++) {
for (int c = 0; c < COLS; c++) {
cout << image[r][c] << " ";
}
cout << endl;
}
// 输出：
// g g g g g g g g
// g g g g g g r r
// g r r g g r g g
// g y y y y r g r
// g g g y y r g r
// g g g y y y y r
// g g g g g y g g
// g g g g g y y g
return 0;
}③处应填（ ）。
