全部知识点
#include <iostream>
using namespace std;
const int maxn=50;
const int y=2009;
int main()
{
int n,c[maxn][maxn],i,j,s=0;
cin >> n;
c[0][0]=1;
for(i=1;i<=n;i++)
{
c[i][0]=1;
for(j=1;j<i;j++)
c[i][j]=c[i-1][j-1]+c[i-1][j];
c[i][i]=1;
}
for(i=0;i<=n;i++)
s=(s+c[n][i])%y;
cout << s << endl;
return 0;
}输入： 17
输出:_______
#include <iostream>
using namespace std;
int main()
{
int n,m,i,j,p,k;
int a[100],b[100];
cin >> n >> m;
a[0]=n;
i=0;
p=0;
k=0;
do
{
for (j=0;j<i;j++)
if (a[i]==a[j])
{
p=1;
k=j;
break;
}
if (p)
break;
b[i]=a[i]/m;
a[i+1]=a[i]%m*10;
i++;
}while (a[i]!=0);
cout << b[0] << ".";
for (j=1; j<k; j++)
cout << b[j];
if (p)
cout << "(";
for (j=k;j<i;j++)
cout << b[j];
if (p)
cout << ")";
cout << endl;
return 0;
}输入： 5 13
输出： _________
（最大连续子段和） 给出一个数列（元素个数不多于 100），数列元素均为负整数、正 整数、0。请找出数列中的一个连续子数列，使得这个子数列中包含的所有元素之和最大，在 和最大的前提下还要求该子数列包含的元素个数最多，并输出这个最大和以及该连续子数列 中元素的个数。例如数列为 4，-5，3，2，4 时，输出 9 和 3；数列为 1 2 3 -5 0 7 8 时， 输出 16和 7。
#include <iostream>
using namespace std;
int a[101];
int n,i,ans,len,tmp,beg,end;
int main()
{
cin >> n;
for (i=1;i<=n;i++)
cin >> 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
⑤ ;
}
cout << ans << " " << len << endl;
return 0;
}( 寻找等差数列 ) 有一些长度相等的等差数列（数列中每个数都为 0~59 的整数），设 长度均为 L，将等差数列中的所有数打乱顺序放在一起。现在给你这些打乱后的数，问原先， L 最大可能为多大？先读入一个数 n（1<=n<=60），再读入 n 个数，代表打乱后的数。输出等 差数列最大可能长度 L。
#include <iostream>
using namespace std;
int hash[60];
int n, x, ans, maxnum;
int work(int now)
{
int first, second, delta, i;
int ok;
while ( ① && !hash[now])
++now;
if (now > maxnum)
return 1;
first = now;
for (second = first; second <= maxnum; second++)
if (hash[second])
{
delta = ② ;
if (first + delta * ③ > maxnum)
break;
if (delta == 0)
ok = ( ④ );
else{
ok = 1;
for (i = 0; i < ans; i++)
ok = ⑤ && (hash[first+delta*i]);
}
if (ok)
{
for (i = 0; i < ans; i++)
hash[first+delta*i]--;
if (work(first))
return 1;
for (i = 0; i < ans; i++)
hash[first+delta*i]++;
}
}
return 0;
}
int main()
{
int i;
memset(hash, 0, sizeof(hash));
cin >> n;
maxnum = 0;
for (i = 0; i < n; i++){
cin >> x;
hash[x]++;
if (x > maxnum)
maxnum = x;
}
for (ans = n; ans >= 1; ans--)
if ( n%ans==0 && ⑥ ) {
cout << ans << endl;
break;
}
return 0;
}LZW 编码是一种自适应词典编码。在编码的过程中，开始时只有一部基础构造元素的编 码词典， 如果在编码的过程中遇到一个新的词条， 则该词条及一个新的编码会被追加到词典 中，并用于后继信息的编码。 举例说明，考虑一个待编码的信息串： “xyx yy yy xyx” 。初始词典只有 3 个条目， 第一个为 x，编码为 1；第二个为 y，编码为 2 ；第三个为空格，编码为 3；于是串 “xyx” 的编码为 1-2-1 （其中 – 为编码分隔符） ，加上后面的一个空格就是 1-2-1-3 。但由于有了 一个空格， 我们就知道前面的 “xyx” 是一个单词， 而由于该单词没有在词典中， 我们就可以 自适应的把这个词条添加到词典里，编码为 4 ，然后按照新的词典对后继信息进行编码，以 此类推。于是，最后得到编码： 1-2-1-3-2-2-3-5-3-4 。 现在已知初始词典的 3 个条目如上述，则信息串 “yyxy xx yyxy xyx xx xyx” 的 编码是___________
队列快照是指在某一时刻队列中的元素组成的有序序列。例如，当元素 1 、2 、3 入队， 元素 1 出队后， 此刻的队列快照是 “2 3” 。当元素 2、3 也出队后，队列快照是 “” ，即为空。 现有 3 个正整数元素依次入队、出队。已知它们的和为 8，则共有 _________ 种可能的不 同的队列快照（不同队列的相同快照只计一次）。例如， “5 1″ 、”4 2 2″ 、”” 都是可能 的队列快照；而 “7” 不是可能的队列快照，因为剩下的 2 个正整数的和不可能是 1。
#include<iostream>
using namespace std;
void swap(int & a, int & b) {
int t;
t = a;
a = b;
b = t;
}
int main() {
int a1, a2, a3, x;
cin>>a1>>a2>>a3;
if (a1 > a2)
swap(a1, a2);
if (a2 > a3)
swap(a2, a3);
if (a1 > a2)
swap(a1, a2);
cin>>x;
if (x < a2)
if (x < a1)
cout<<x<<' '<<a1<<' '<<a2<<' '<<a3<<endl;
else
cout<<a1<<' '<<x<<' '<<a2<<' '<<a3<<endl;
else if (x < a3)
cout<<a1<<' '<<a2<<' '<<x<<' '<<a3<<endl;
else
cout<<a1<<' '<<a2<<' '<<a3<<' '<<x<<endl;
return 0;
}输入： 91 2 20 77
输出： _______
#include<iostream>
using namespace std;
int rSum(int j) {
int sum = 0;
while (j != 0) {
sum = sum * 10 + (j % 10);
j = j / 10;
}
return sum;
}
int main() {
int n, m, i;
cin>>n>>m;
for (i = n; i < m; i++)
if (i == rSum(i))
cout<<i<<' ';
return 0;
}输入： 90 120
输出： _______
#include<iostream>
#include<iostream>
using namespace std;
int main() {
string s;
char m1, m2;
int i;
getline(cin, s);
m1 = ' ';
m2 = ' ';
for (i = 0; i < s.length(); i++)
if (s[i] > m1) {
m2 = m1;
m1 = s[i];
} else if (s[i] > m2)
m2 = s[i];
cout<<int(m1)<<' '<<int(m2)<<endl;
return 0;
}输入： Expo 2010 Shanghai China
输出： _______
#include<iostream>
using namespace std;
const int NUM = 5;
int r(int n) {
int i;
if (n <= NUM)
return n;
for (i = 1; i <= NUM; i++)
if (r(n - i) < 0)
return i;
return -1;
}
int main() {
int n;
cin>>n;
cout<<r(n)<<endl;
return 0;
}（1） 输入： 7 输出： _______ （4 分）
（2） 输入： 16 输出： _______ （4 分）
（哥德巴赫猜想） 哥德巴赫猜想是指，任一大于 2 的偶数都可写成两个质数之和。迄今 为止， 这仍然是一个著名的世界难题，被誉为数学王冠上的明珠。 试编写程序，验证任一大 于 2 且不超过 n 的偶数都能写成两个质数之和。
#include<iostream>
using namespace std;
int main() {
const int SIZE = 1000;
int n, r, p[SIZE], i, j, k, ans;
bool tmp;
cin>>n;
r = 1;
p[1] = 2;
for (i = 3; i <= n; i++) {
① _______;
for (j = 1; j <= r; j++)
if (i % ② ______) {
tmp = false;
break;
}
if (tmp) {
r++;
③_________
}
}
ans = 0;
for (i = 2; i <= n / 2; i++) { // i=n/2 表示缩小范围，排除重复情况。
tmp = false;
for (j = 1; j <= r; j++)
for (k = j; k <= r; k++)
if (i + i == ④ _______ ) {
tmp = true;
break;
}
if (tmp)
ans++;
}
cout<<ans<<endl;
return 0;
}若输入 n 为 2010 ，则输出 ⑤ _______ 时表示验证成功，即大于 2 且不超过 2010 的偶数都 满足哥德巴赫猜想。（过河问题） 在一个月黑风高的夜晚，有一群人在河的右岸，想通过唯一的一根独木桥 走到河的左岸。 在这伸手不见五指的黑夜里， 过桥时必须借助灯光来照明， 很不幸的是，他 们只有一盏灯。 另外，独木桥上最多承受两个人同时经过，否则将会坍塌。 每个人单独过桥 都需要一定的时间，不同的人需要的时间可能不同。两个人一起过桥时，由于只有一盏灯，所以需要的时间是较慢的那个人单独过桥时所花的时间。现输入 n（ 2≤n≤100）和这 n 个 人单独过桥时需要的时间，请计算总共最少需要多少时间，他们才能全部到达河的左岸。 例如，有 3 个人甲、乙、丙，他们单独过桥的时间分别为 1、 2、4，则总共最少需要 的时间为 7 。具体方法是：甲、乙一起过桥到河的左岸，甲单独回到河的右岸将灯带回，然 后甲、丙再一起过桥到河的左岸，总时间为 2+1+4=7 。
#include<iostream>
using namespace std;
const int SIZE = 100;
const int INFINITY = 10000;
const bool LEFT = true;
const bool RIGHT = false;
const bool LEFT_TO_RIGHT = true;
const bool RIGHT_TO_LEFT = false;
int n, hour[SIZE]; //存放每个人的过河时间
bool pos[SIZE];
int max(int a, int b) {
if (a > b)
return a;
else
return b;
}
int go(bool stage) {
int i, j, num, tmp, ans;
if (stage == RIGHT_TO_LEFT) {
num = 0;
ans = 0;
for (i = 1; i <= n; i++)
if (pos[i] == RIGHT) {
num++; //人数加1
if (hour[i] > ans)
ans = hour[i]; //ans保留了最长的过桥时间，
}
if ( ① __________ )
return ans;
ans = INFINITY;
for (i = 1; i <= n - 1; i++)
if (pos[i] == RIGHT) //如果这个人在右侧
for (j = i + 1; j <= n; j++)
if (pos[j] == RIGHT) {
pos[i] = LEFT;
pos[j] = LEFT;
tmp = max(hour[i], hour[j]) + ② __________) ;
if (tmp < ans)
ans = tmp;
pos[i] = RIGHT;
pos[j] = RIGHT;
}
return ans;
}
if (stage == LEFT_TO_RIGHT) {
ans = INFINITY;
for (i = 1; i <= n; i++)
if ( ③_________) {
pos[i] = RIGHT;
tmp = ④ _________;
if (tmp < ans)
ans = tmp;
⑤__________ ;
}
return ans;
}
return 0;
}
int main() {
int i;
cin>>n;
for (i = 1; i <=n; i++) {
cin>>hour[i];
pos[i] = RIGHT; //pos是记录每个元素所处的位置。
}
cout<<go(RIGHT_TO_LEFT)<<endl; //初始状态RIGHT_TO_LEFT
return 0;
}LZW 编码是一种自适应词典编码。在编码的过程中，开始时只有一部基础构造元素的编 码词典， 如果在编码的过程中遇到一个新的词条， 则该词条及一个新的编码会被追加到词典 中，并用于后继信息的编码。 举例说明，考虑一个待编码的信息串：“ xyx yy yy xyx ”。初始词典只有 3 个条目， 第一个为 x,编码为 1；第二个为 y，编码为 2；第三个为空格，编码为 3；于是串“ xyx”的 编码为 1-2-1 （其中 -为编码分隔符），加上后面的一个空格就是 1-2-1-3 。但由于有了一个 空格，我们就知道前面的“ xyx”是一个单词，而由于该单词没有在词典中，我们就可以自 适应的把这个词条添加到词典里，编码为 4，然后按照新的词典对后继信息进行编码，以此 类推。于是，最后得到编码： 1-2-1-3-2-2-3-5-3-4 。 我们可以看到，信息被压缩了。压缩好的信息传递到接受方，接收方也只要根据基础 词典就可以完成对该序列的完全恢复。 解码过程是编码过程的逆操作。 现在已知初始词典的 3 个条目如上述，接收端收到的编码信息为 2-2-1-2-3-1-1-3-4-3-1-2-1-3-5-3-6 ，则解码 后的信息串是” ______________________________________________________________ ”。
无向图 G 有 7 个顶点，若不存在奇数条边构成的简单回路，则它至多有 __________ 条 边。
记 T 为一队列初始为空现有 n 个总和不超过 32 的正整数依次入队如果无论这些数具 体为何值都能找到一种出队的方式使得存在某个时刻队列 T 中的数之和恰好为 9 那么 n 的最小值是 ________________。
#include <stdio.h>
#define SIZE 10
int main()
{
int data[SIZE], i, j, cnt, n, m;// 定义 //
scanf("%d %d\n", &n, &m);// 输入 n 和 m，此处我们输入的是 5 和 2//
for(i = 1; i <= n; i++)
scanf("%d", &data[i]);// 再次输入 i 个数 data[1] =96 data[2]=-8 data[3]=0 data[4]=16 data[5]=87//
for(i = 1; i <= n; i++)
{ //n=5//
cnt = 0;
for(j = 1; j<= n; j++)//n=5 ，data[1] =96 data[2]=-8 data[3]=0 data[4]= 16
data[5]=87//
if ((data[i] < data[j]) || (data[j] == data[i] && j< i))// 如果说 data[i]<data[j] ，或者说{data[j] 等于 data[i] ，同时 j 小于 i
cnt++;//cnt 的数目加 1//
if(cnt == m)// 如果说 cnt 等于 m 等于 2，因为 cnt=2 ，即整个程序运行了两遍，也运行两遍，换句话说，只有恰好运行两遍的数字才能满足题意。假设， data[1]=96 ，与
data[2]=-8 data[3]=0 data[4]= 16 data[5]=87 //比较大小时， 显然为最大， 不能比其他的数小，不满足条件 data[i] < data[j] ，同样， data[2]=-8 ，比它大的数有 3 个也不满足题意，
data[3]=0 //比它大的数有 4 个，不合题意 data[4]= 16 ，比它大的数恰恰只有两个，满足题意，为所输出 //
printf("%d\n", data[i]);// 输出 data[i]//
}
getch(); //（此语句在 windows 2000 以上系统用 winTC 编译 C 时需要加入，用以暂停查看屏幕）
return 0;
}输入： 5 2
96 -8 0 16 87
输出： ______
#include <stdio.h>
#define SIZE 100
int main()
{
int na, nb, a[SIZE], b[SIZE], i, j, k;// 定义 //
scanf("%d\n", &na);// 输入 5,即 na=5//
for (i = 1; i <= na; i++)
scanf("%d", &a[i]);// 输入数字， a[1]=1. a[2]=3 a[3]=5 a[4]=7 a[5]=9//
scanf("%d\n", &nb);// 输入数字 4//
for (i = 1; i <= nb; i++)
scanf("%d", &b[i]);// 同理，输入数字 b[1] =2 b[2] =6 b[3] =10 b[4] =14//
i=1;
j=1;
while ((i <= na) && (j <= nb))
{// 当 i 小于等于 na 时，并且 j 小于等于 nb 时候 //
if (a[i] <= b[j])
{// 如果说 a[i]大于 b[j]//
printf("%d ", a[i]);// 输出 a[i]//
i++;//i 增加 1//
}
else {
printf("%d ", b[j]);// 否则输出 b[j]//
j++;
}
}
if (i <= na)// 如果 i 小于等于 na//
for (k = i; k<= na; k++)// 循环 //
printf("%d ", a[k]); //按照上面的循环条件输出数字 //
if (j <= nb)
for (k = j; k<= nb; k++)// 同理 //
printf ("%d ", b[k]);
getch();
return 0;
}输入： 5
1 3 5 7 9
4
2 6 10 14
输出：______
#include<iostream>
using namespace std;
const int NUM=5;
int r(int n)
{
int i;
if(n<=NUM)
return 0;
for(i=1;i<=NUM;i++)
if( r(n-i)<0)
return i;
return -1;
}
int main()
{
int n;
cin>>n;
cout<<r(n)<<endl;
return 0;
}输入： 16
输出： ______________
#include<iostream>
#include<cstring>
using namespace std;
const int SIZE=100;
int n,m,r[SIZE];
bool map[SIZE][SIZE],found;
bool successful()
{
int i;
for(i=1;i<=n;i++)
if(!map[r[i]][r[i%n+1]])
return false;
return true;
}
void swap(int *a,int *b)
{
int t;
t=*a;
*a=*b;
*b=t;
}
void perm(int left,int right)
{
int i;
if(found)
return ;
if(left>right)
{
if(successful())
{
for(i=1;i<=n;i++)
cout<<r[i]<<' ';
found=true;
}
return ;
}
for(i=left;i<=right;i++)
{
swap(r+left,r+i);
perm(left+1,right);
swap(r+left,r+i);
}
}
int main()
{
int x,y,i;
cin>>n>>m;
memset(map,false,sizeof(map));
for(i=1;i<=m;i++)
{
cin>>x>>y;
map[x][y]=true;
map[y][x]=true;
}
for(i=1;i<=n;i++)
r[i]=i;
found=false;
perm(1,n);
if(!found)
cout<<"No solution!"<<endl;
return 0;
}输入： 9 12
1 2
2 3
3 4
4 5
5 6
6 1
1 7
2 7
3 8
4 8
5 9
6 9
输出： _________
( 过河问题 ) 在一个月黑风高的夜晚 , 有一群人在河的右岸 , 想通过唯一的一根独木桥走到 河的左岸 . 在伸手不见五指的黑夜里 , 过桥时必须借照灯光来照明 , 不幸的是 , 他们只有一盏灯 . 另外, 独木桥上最多能承受两个人同时经过 , 否则将会坍塌 . 每个人单独过独木桥都需要一定 的时间 , 不同的人要的时间可能不同 . 两个人一起过独木桥时 , 由于只有一盏灯 , 所以需要的时 间是较慢的那个人单独过桥所花费的时间 . 现在输入 N(2<=N<1000)和这 N 个人单独过桥需要 的时间 , 请计算总共最少需要多少时间 , 他们才能全部到达河左岸 .
例如, 有 3 个人甲、乙、丙 , 他们单独过桥的时间分别为 1、2、4, 则总共最少需要的时 间为 7. 具体方法是 : 甲、乙一起过桥到河的左岸 , 甲单独回到河的右岸将灯带回 , 然后甲、丙 在一起过桥到河的左岸 , 总时间为 2+1+4=7.
#include<iostream>
#include<cstring>
using namespace std;
const int SIZE=100;
const int INFINITY = 10000;
const bool LEFT=true;
const bool RIGHT =false;
const bool LEFT_TO_RIGHT=true;
const bool RIGHT_TO_LEFT=false;
int n,hour[SIZE];
bool pos[SIZE];
int max(int a,int b)
{
if(a>b)
return a;
else
return b;
}
int go(bool stage)
{
int i,j,num,tmp,ans;
if(stage==RIGHT_TO_LEFT)
{
num=0;
ans=0;
for(i=1;i<=n;i++)
if(pos[i]==RIGHT)
{
num++;
if( hour[i]>ans)
ans=hour[i];
}
if( ① )
return ans;
ans=INFINITY;
for(i=1;i<=n-1;i++)
if(pos[i]==RIGHT)
for(j=i+1;j<=n;j++)
if(pos[j]==RIGHT)
{
pos[i]=LEFT;
pos[j]=LEFT;
tmp=max(hour[i],hour[j])+ ② ;
if(tmp<ans)
ans=tmp;
pos[i]=RIGHT;
pos[j]=RIGHT;
}
return ans;
}
if(stage==LEFT_TO_RIGHT)
{
ans=INFINITY;
for(i=1;i<=n;i++)
if( ③ )
{
pos[i]=RIGHT;
tmp= ④ ;
if(tmp<ans)
ans=tmp;
⑤ ;
}
return ans;
}
return 0;
}
int main()
{
int i;
cin>>n;
for(i=1;i<=n;i++)
{
cin>>hour[i];
pos[i]=RIGHT;
}
cout<<go[RIGHT_TO_LEFT)<<endl;
return 0;
}