全部知识点
有 6 个城市，任何两个城市之间都有一条道路连接， 6 个城市两两之间的距离如下 表所示，则城市 1 到城市 6 的最短距离为 _____________ 。
书架上有 21 本书，编号从 1 到 21 ，从其中选 4 本，其中每两本的编号都不相邻的 选法一共有 ______ 种。
#include<stdio.h>
int main()
{
int i, a, b, c, d, f[4];
for(i = 0; i < 4; i++)
scanf("%d", &f[i]);
a = f[0] + f[1] + f[2] + f[3];
a = a / f[0];
b = f[0] + f[2] + f[3];
b = b / a;
c = (b * f[1] + a) / f[2];
d = f[(b / c ) % 4];
if(f[(a + b + c + d) % 4] > f[2])
printf("%d\n", a + b);
else
printf("%d\n", c + d);
return 0;
}输入： 9 19 29 39
输出： _______________
#include<stdio.h>
void foo(int a, int b, int c)
{
if(a > b)
foo(c, a, b);
else
printf("%d,%d,%d\n", a, b, c);
}
int main()
{
int a, b, c;
scanf("%d %d %d", &a, &b, &c);
foo(a, b, c);
return 0;
}输入： 2 1 3
输出 :__________
#include<stdio.h>
void f(int a, int b, int c)
{
printf("%d%d%d/", a, b, c);
if(a == 3 && b == 2 && c == 1)
return;
if(b < c)
f(a, c, b);
else if(a < b)
{
if(a < c)
f(c, a, b);
else
f(b, c, a);
}
}
int main()
{
int a, b, c;
scanf("%d %d %d", &a, &b, &c);
f(a, b, c);
printf("\n");
return 0;
}输入 : 1 3 2
输出： ________________________
#include <stdio.h>
#include <string.h>
int i,j,len;
char s[50];
int main()
{
scanf("%s", s);
len = strlen(s);
for (i = 0;i < len; ++i)
{
if (s[i] >= 'A' && s[i] <= 'Z') s[i] -= 'A' - 'a';
}
for (i = 0;i < len; ++i)
{
if (s[i] < 'x') s[i] += 3; else s[i] += -23;
}
printf("%s/", s);
for (j = 1;j < 4;j ++)
{
for (i = 0;i < len-j; i = i + j)
{
s[i] = s[i + j] ;
}
}
printf("%s\n", s);
return 0;
}输入： ABCDEFGuvwxyz
输出： __________________________
( 找第 k 大的数 ) 给定一个长度为 1,000,000 的无序正整数序列，以及另一个数 n(1<=n<=1000000) ，接下来以类似快速排序的方法找到序列中第 n 大的数 （关于第 n 大 的数：例如序列 {1 ，2， 3， 4，5，6} 中第 3 大的数是 4）。
#include <stdlib.h>
#include <stdio.h>
int a[1000001],n,ans = -1;
void swap(int *a,int *b)
{
int c;
c = *a; *a = *b; *b = c;
}
int FindKth(int left, int right, int n)
{
int tmp,value,i,j;
if (left == right) return left;
tmp = rand()% (right - left) + left;
swap( &a[tmp], &a[left] );
value = ①
i = left;
j = right;
while (i < j)
{
while (i < j && ② ) j --;
if (i < j) {a[i] = a[j]; i ++;} else break;
while (i < j && ③ ) i ++;
if (i < j) {a[j] = a[i]; j - -;} else break;
}
④
if (i < n) return FindKth( ⑤ );
if (i > n) return ⑥
return i;
}
int main()
{
int i;
int m = 1000000;
for (i = 1;i <= m;i ++)
scanf("%d", &a[i]);
scanf("%d", &n);
ans = FindKth(1,m,n);
printf("%d\n", a[ans]);
return 0;
}（矩阵中的数字） 有一个 n*n(1<=n<=5000) 的矩阵 a， 对于 1<=i < n,1<=j<=n, a[i,j] < a[i + 1,j] a[j,i] < a[j,i+1] 。即矩阵中左右相邻的两个元素，右边 的元素一定比左边的大。上下相邻的两个元素，下面的元素一定比上面的大。给定矩阵 a 中的一个数字 k，找出 k 所在的行列（注意：输入数据保证矩阵中的数各不相同） 。
#include <stdio.h>
int n,k,answerx,answery;
int a[5001][5001];
void FindKPosition()
{
int i = n,j = n;
while (j > 0)
{
if (a[n][j] < k) break;
j --;
}
①
while (a[i][j] != k)
{
while ( ② && i > 1) i --;
while ( ③ && j <= n) j ++;
}
④
⑤
}
int main()
{
int i,j;
scanf( "%d", &n );
for (i = 1;i <= n;i ++)
for (j = 1;j <= n;j ++)
scanf( "%d", &a[i][j]);
scanf( "%d", &k );
FindKPosition();
printf("%d %d\n", answerx, answery);
return 0;
}小陈现有2个任务A，B要完成，每个任务分别有若干步骤如下：A=a1->a2->a3，B=b1->b2->b3->b4->b5。在任何时候，小陈只能专心做某个任务的一个步骤。但是如果愿意，他可以在做完手中任务的当前步骤后，切换至另一个任务，从上次此任务第一个未做的步骤继续。每个任务的步骤顺序不能打乱，例如……a2->b2->a3->b3……是合法的，而……a2->b3->a3->b2……是不合法的。小陈从B任务的b1步骤开始做，当恰做完某个任务的某个步骤后，就停工回家吃饭了。当他回来时，只记得自己已经完成了整个任务A，其他的都忘了。试计算小陈饭前已做的可能的任务步骤序列共有______ 种。
有如下的一段程序：
1. a=1;
2. b=a;
3. d=-a;
4. e=a+d;
5. c=2*d;
6. f=b+e-d;
7. g=a*f+c;
现在要把这段程序分配到若干台（数量充足）用电缆连接的PC上做并行执行。每台PC执行其中的某几个语句，并可随时通过电缆与其他PC通讯，交换一些中间结果。假设每台PC 每单位时间可以执行一个语句，且通讯花费的时间不计。则这段程序最快可以在 _______单位时间内执行完毕。注意：任意中间结果只有在某台PC上已经得到，才可以被其他PC 引用。例如若语句4和6被分别分配到两台PC上执行，则因为语句6需要引用语句4的计算结果，语句6必须在语句4之后执行。
#include<stdio.h>
int a,b;
int work(int a,int b){
if (a%b)
return work(b,a%b);
return b;
}
int main()
{
scanf("%d%d",&a,&b);
printf("%d\n",work(a,b));
return 0;
}输入：20 12
输出：_____
#include <stdio.h>
int main()
{
int a[3],b[3];
int i,j,tmp;
for (i=0;i<3;i++)
scanf("%d",&b[i]);
for (i=0;i<3;i++)
{
a[i]=0;
for (j=0;j<=i;j++)
{
a[i]+=b[j];
b[a[i]%3]+=a[j];
}
}
tmp=1;
for (i=0;i<3;i++)
{
a[i]%=10;
b[i]%=10;
tmp*=a[i]+b[i];
}
printf("%d\n",tmp);
return 0;
}输入： 2 3 5
输出： _______
#include<stdio.h>
const int c=2009;
int main()
{
int n,p,s,i,j,t;
scanf("%d%d",&n,&p);
s=0;t=1;
for(i=1;i<=n;i++)
{
t=t*p%c;
for(j=1;j<=i;j++)
s=(s+t)%c;
}
printf("%d\n",s);
return 0;
}输入： 11 2
输出： ______
#include<stdio.h>
#include<string.h>
#define maxn 50
void getnext(char str[])
{
int l=strlen(str),i,j,k,temp;
k=l-2;
while(k>=0&&str[k]>str[k+1]) k--;
i=k+1;
while(i<l&&str[i]>str[k]) i++;
temp=str[k];
str[k]=str[i-1];
str[i-1]=temp;
for(i=l-1;i>k;i--)
for(j=k+1;j<i;j++)
if(str[j]>str[j+1])
{
temp=str[j];
str[j]=str[j+1];
str[j+1]=temp;
}
return ;
}
int main()
{
char a[maxn];
int n;
scanf("%s %d",a,&n);
while(n>0)
{
getnext(a);
n--;
}
printf("%s\n",a);
return 0;
}输入： NOIP 3
输出： ______
（最大连续子段和）给出一个数列（元素个数不多于 100），数列元素均为负整数、 正整数、 0。请找出数列中的一个连续子数列， 使得这个子数列中包含的所有元素之和最大， 在和最大的前提下还要求该子数列包含的元素个数最多， 并输出这个最大和以及该连续子数 列中元素的个数。例如数列为 4，-5，3，2， 4 时，输出 9 和 3；数列为 1 2 3 -5 0 7 8 时，输 出 16 和 7。
#include <stdio.h>
int a[101];
int n,i,ans,len,tmp,beg;
int main(){
scanf("%d",&n);
for (i=1;i<=n;i++)
scanf("%d",&a[i]);
tmp=0;
ans=0;
len=0;
beg= ① ;
for (i=1;i<=n;i++)
{
if (tmp+a[i]>ans)
{
ans=tmp+a[i];
len=i-beg;
}
else if ( ②&&i-beg>len)
len=i-beg;
if (tmp+a[i] ③ )
{
beg= ④ ;
tmp=0;
}
else
⑤ ;
}
printf("%d %d\n",ans,len);
return 0;
}(国王放置 ) 在 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 <stdio.h>
#include <string.h>
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= ① ;
}
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)
② ;
③ ;
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)
④ ;
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));
⑤ ;
printf("%d\n",ans);
return 0;
}拓扑排序是指将有向无 环图 G中的所有顶点排成一个线性序列，使得图中任意一对顶 点 u 和 v，若 ∈E(G)，则 u 在线性序列中出现在 v 之前，这样的线性序列成为拓扑序 列。如下的有向无环图，对其顶点做拓扑排序，则所有可能的拓扑序列的个数为 ______。
某个国家的钱币面值有 1, 7, 7 2, 7 3共计四种，如果要用现金付清 10015元的货物， 假设买卖双方各种钱币的数量无限且允许找零，那么交易过程中至少需要流通______张钱 币。
#include <iostream>
using namespace std;
int a,b;
int work(int a,int b)
{
if (a%b)
return work(b,a%b);
return b;
}
int main()
{
cin >> a >> b;
cout << work(a,b) << endl;
return 0;
}输入： 123 321
输出： _________
#include <iostream>
using namespace std;
int main()
{
int a[4],b[4];
int i,j,tmp;
for (i=0;i<4;i++)
cin >> b[i];
for (i=0;i<4;i++)
{
a[i]=0;
for (j=0;j<=i;j++)
{
a[i]+=b[j];
b[a[i]%4]+=a[j];
}
}
tmp=1;
for (i=0;i<4;i++)
{
a[i]%=10;
b[i]%=10;
tmp*=a[i]+b[i];
}
cout << tmp << endl;
return 0;
}输入： 2 3 5 7
输出： _________