全部知识点
#include <stdio.h>
int g(int m, int n, int x) {
int ans=0;
int i;
if(n == 1)
return 1;
for(i = x; i <= m / n; i++)
ans += g(m - i, n - 1, i);
return ans;
}
int main()
{
int t, m, n;
scanf("%d%d", &m, &n);
printf("%d
", g(m, n, 0));
return 0;
}输入：
7 3
输出：（ ）
#include <iostream>
#include <string>
using namespace std;
int main()
{
string ch;
int a[200];
int b[200];
int n, i, t, res;
cin >> ch;
n = ch.length();
for(i = 0; i < 200; i++) b[i] = 0;
for(i = 1; i <= n ; i++) {
a[i] = ch[i-1] - '0';
b[i] = b[i-1] + a[i];
}
res = b[n];
t = 0;
for(i = n; i > 0; i--) {
if(a[i] == 0) t++;
if(b[i-1] + t < res) res = b[i-1] + t;
}
cout << res << endl;
return 0;
}输入：
1001101011001101101011110001
输出：（ ）
#include <iostream>
using namespace std;
int main()
{
int n, m;
cin >> n >> m;
int x = 1;
int y = 1;
int dx = 1;
int dy = 1;
int cnt = 0;
while(cnt != 2) {
cnt = 0;
x = x + dx;
y = y + dy;
if(x == 1 || x == n) {
++cnt;
dx = -dx;
}
if(y == 1 || y == m) {
++cnt;
dy = -dy;
}
}
cout << x << " " << y << endl;
return 0 ;
}1）输入：
4 3
输出：（ ）
2）输入：
2017 1014
输出：（ ）
（快速幂）请完善下面的程序，该程序使用分治法求 xp mod m 的值。
输入：三个不超过 10000 的正整数 x, p, m。
输出：xp mod m 的值。
提示：若 p 为偶数，xp = (x2)p/2；若 p 为奇数，xp = x (x2)(p-1)/2。
#include <iostream>
using namespace std;
int x, p, m, i, result;
int main()
{
cin >> x >> p >> m;
result = ①;
while(②)
{
if(p % 2 == 1)
result = ③;
p /= 2;
x = ④;
}
cout << ⑤ << endl;
return 0 ;
}（切割绳子）有 n 条绳子，每条绳子的长度已知且均为正整数。绳子可以以任意正整数长度切割，但不可以连接。现在要从这些绳子中切割出m条长度相同的绳段，求绳段的最大长度是多少。
输入：第一行是一个不超过 100 的正整数 n，第二行是 n 个不超过 10^6的正整数，表示每条绳子的长度，第三行是一个不超过 10^8 的正整数 m。
输出 ：绳段的最大长度，若无法切割，输出 Failed。
#include <iostream>
using namespace std;
int n, m, i, lbound, ubound, mid, count;
int len[100]; //绳子长度
int main()
{
cin >> n;
count = 0;
for (i = 0; i < n; i++) {
cin >> len[i];
①;
}
cin >> m;
if (②) {
cout << "Failed" << endl;
return 0;
}
lbound = 1 ;
ubound = 1000000 ;
while (③) {
mid = ④;
count =0 ;
for (i = 0; i < n; i++ )
⑤;
if (count < m)
ubound = mid - 1 ;
else
lbound = mid ;
}
cout << lbound << endl;
return 0;
}如右图所示，共有 13 个格子。对任何一个格子进行一次操作，会使得它自己以及与它上下左右相邻的格子中的数字改变 (由 1 变 0，或由 0 变 1)。现在要使得所有的格子中的数字都变为 0，至少需要_____次操作。
如下图所示，A 到 B 是连通的。假设删除一条细的边的代价是 1，删除一条粗的边的代价是 2，要让 A、B 不连通，最小代价是_____（2 分），最小代价的不同方案数是_____（3 分）。（只要有一条删除的边不同，就是不同的方案）
#include <iostream>
using namespace std;
int g(int m, int n, int x) {
int ans = 0;
int i;
if (n == 1)
return 1;
for (i = x; i <= m / n; i++)
ans += g(m - i, n - 1, i);
return ans;
}
int main() {
int t, m, n;
cin >> m >> n;
cout << g(m, n, 0) << endl;
return 0;
}输入 :
8 4
输出 ：____
#include <iostream>
using namespace std;
int main() {
int n, i, j, x, y, nx, ny;
int a[40][40];
for (i = 0; i < 40; i++)
for (j = 0; j < 40; j++)
a[i][j] = 0;
cin >> n;
y = 0; x = n - 1;
n = 2 * n - 1;
for (i = 1; i <= n * n; i++) {
a[y][x] = i;
ny = (y - 1 + n) % n;
nx = (x + 1) % n;
if ((y == 0 && x == n - 1) || a[ny][nx] != 0)
y = y + 1;
else {y = ny; x = nx;}
}
for (j = 0; j < n; j++)
cout << a[0][j] << " ";
cout << endl;
return 0;
}输入 :
3
输出 ：____
#include <iostream>
using namespace std;
int n, s, a[100005], t[100005], i;
void mergesort( int l, int r ){
if (l == r)
return;
int mid = (l + r) / 2;
int p = l;
int i = l;
int j = mid + 1;
mergesort(l, mid);
mergesort(mid + 1, r);
while (i <= mid && j <= r){
if (a[j] < a[i]){
s += mid - i + 1;
t[p] = a[j];
p++;
j++;
}
else {
t[p] = a[i];
p++;
i++;
}
}
while (i <= mid){
t[p] = a[i];
p++;
i++;
}
while (j <= r){
t[p] = a[j];
p++;
j++;
}
for (i = l; i <= r; i++)
a[i] = t[i];
}
int main(){
cin >> n;
for ( i = 1; i <= n; i++ )
cin >> a[i];
mergesort(1, n);
cout << s << endl;
return 0;
}输入 ：
6
2 6 3 4 5 1
输出 ：____
#include <iostream>
using namespace std;
int main(){
int n, m;
cin >> n >> m;
int x = 1;
int y = 1;
int dx = 1;
int dy = 1;
int cnt = 0;
while (cnt != 2){
cnt = 0;
x = x + dx;
y = y + dy;
if (x == 1 || x == n){
++cnt;
dx = -dx;
}
if (y == 1 || y == m){
++cnt;
dy = -dy;
}
}
cout << x << " " << y << endl;
return 0;
}输入 1:
4 3
输出 1：____
输入 2:
2017 1014
输出 2：____
输入 3:
987 321
输出 3：____
（大整数除法）给定两个正整数 p 和 q，其中 p 不超过10100 ，q 不超过 100000 ，求 p 除以 q 的商和余数。
输入：第一行是 p 的位数 n，第二行是正整数 p ，第三行是正整数 q 。
输出：两行，分别是 p 除以 q 的商和余数。
#include <iostream>
using namespace std;
int p[100];
int n, i, q, rest;
char c;
int main(){
cin >> n;
for (i = 0; i < n; i++){
cin >> c;
p[i] = c - '0';
}
cin >> q;
rest = ___(1)___ ;
i = 1;
while (___(2)___ && i < n){
rest = rest * 10 + p[i];
i++;
}
if (rest < q)
cout << 0 << endl;
else {
cout << ___(3)___ ;
while (i < n){
rest = ___(4)___ ;
i++;
cout << rest / q;
}
cout << endl;
}
cout << ___(5)___ << endl;
return0;
}（最长路径）给定一个有向无环图，每条边长度为 1，求图中的最长路径长度。
输入：第一行是结点数 n（不超过 100）和边数 m，接下来 m 行，每行两个整数a，b，表示从结点 a 到结点 b 有一条有向边。结点标号从 0 到 (n−1) 。
输出：最长路径长度。
提示：先进行拓扑排序，然后按照拓扑序计算。
#include <iostream>
using namespace std;
int n, m, i, j, a, b, head, tail, ans;
int graph[100][100]; /* 用邻接矩阵存储图 */
int degree[100]; /* 记录每个结点的入度 */
int len[100]; /* 记录以各结点为终点的最长路径长度 */
int queue[100]; /* 存放拓扑排序结果 */
int main(){
cin >> n >> m;
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
graph[i][j] = 0;
for (i = 0; i < n; i++)
degree[i] = 0;
for (i = 0; i < m; i++){
cin >> a >> b;
graph[a][b] = 1;
___(1)___ ;
}
tail = 0;
for (i = 0; i < n; i++)
if (___(2)___){
queue[tail] = i;
tail++;
}
head = 0;
while (tail < n - 1){
for (i = 0; i < n; i++)
if (graph[queue[head]][i] == 1){
___(3)___ ;
if (degree[i] == 0){
queue[tail] = i;
tail++;
}
}
___(4)___ ;
}
ans = 0;
for (i = 0; i < n; i++){
a = queue[i];
len[a] = 1;
for (j = 0; j < n; j++)
if (graph[j][a] == 1 && len[j] + 1 > len[a])
len[a] = len[j] + 1;
if (___(5)___)
ans = len[a];
}
cout << ans << endl;
return(0);
}甲乙丙丁四人在考虑周末要不要外出郊游。已知①如果周末下雨，并且乙不去，则甲一定不去；②如果乙去，则丁一定去；③如果丙去，则丁一定不去；④如果丁不去，而且甲不去，则丙一定不去。如果周末丙去了，则甲____（去了/没去），乙____（去了/没去），丁 ___ （去了/没去），周末____（下雨/没下雨）。
从 1 到 2018 这 2018 个数中，共有___个包含数字 8 的数。包含数字 8 的数是指有某一位是“8”的数，例如“2018”与“188”。
#include <cstdio>
char st[100];
int main() {
scanf("%s", st);
for (int i = 0; st[i]; ++i) {
if ('A' <= st[i] && st[i] <= 'Z')
st[i] += 1;
}
printf("%s
", st);
return 0;
}输入：
QuanGuoLianSai
输出：（ ）
#include <cstdio>
int main() {
int x;
scanf("%d", &x);
int res = 0;
for (int i = 0; i < x; ++i) {
if (i * i % x == 1) {
++res;
}
}
printf("%d", res);
return 0;
}输入：
15
输出：（ ）
#include <iostream>
using namespace std;
int n, m;
int findans(int n, int m) {
if (n == 0) return m;
if (m == 0) return n % 3;
return findans(n - 1, m) - findans(n, m - 1) + findans(n - 1, m - 1);
}
int main(){
cin >> n >> m;
cout << findans(n, m) << endl;
return 0;
}输入：
5 6
输出：（ ）
#include <cstdio>
int n, d[100];
bool v[100];
int main() {
scanf("%d", &n);
for (int i = 0; i < n; ++i) {
scanf("%d", d + i);
v[i] = false;
}
int cnt = 0;
for (int i = 0; i < n; ++i) {
if (!v[i]) {
for (int j = i; !v[j]; j = d[j]) {
v[j] = true;
}
++cnt;
}
}
printf("%d
", cnt);
return 0;
}输入：
10 7 1 4 3 2 5 9 8 0 6
输出：（ ）
（最大公约数之和）下列程序想要求解整数 n 的所有约数两两之间最大公约数的和对10007 求余后的值，试补全程序。
举例来说，4 的所有约数是 1,2,4。1 和 2 的最大公约数为 1；2 和 4 的最大公约数为 2；1 和 4 的最大公约数为 1。于是答案为 1 + 2 + 1 = 4。
要求 getDivisor 函数的复杂度为 O(√n)，gcd 函数的复杂度为O(log max(a,b))。
例如:
#include <iostream>
using namespace std;
const int N = 110000, P = 10007;
int n;
int a[N], len;
int ans;
void getDivisor() {
len = 0;
for (int i = 1; ① <= n; ++i)
if (n % i == 0) {
a[++len] = i;
if ( ② != i) a[++len] = n / i;
}
}
}
int gcd(int a, int b) {
if (b == 0) {
③ ;
}
return gcd(b, ④ );
}
int main() {
cin >> n;
getDivisor();
ans = 0;
for (int i = 1; i <= len; ++i) {
for (int j = i + 1; j <= len; ++j) {
ans = ( ⑤ ) % P;
}
}
cout << ans << endl;
return 0;
}