NOIP真题
#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
输出： _________
#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 分）