大二上学期代码

第4讲 文字或算式题目的解题技巧（2）

1.下列乘法算式中：赛软件 * 比赛 = 软件比拼

其中每个汉字代表1个数字（0~9）。相同的汉字代表相同的数字，不同的汉字代表不同的数字。

试编程确定使得整个算式成立的数字组合，如有多种情况，请给出所有可能的答案。

#include<stdio.h>

#include<math.h>

int main()

{

int a,b,c,d,e,f,g; 

int x,y,z,k=1;

for(a=0;a<=9;a++){

for(b=0;b<=9;b++){

for(c=0;c<=9;c++){

for(d=0;d<=9;d++){

for(e=0;e<=9;e++){

for(f=0;f<=9;f++){

for(g=0;g<=9;g++){

                            if(a!=b && a!=c&& a!=d&&a!=e && a!=f&& a!=g && 

b!=c && b!=d && b!=e && b!=f && b!=g &&

c!=d && c!=e && c!=f && c!=g

 && d!=e && d!=f && d!=g &&

  e!=f && e!=g &&

   f!=g

   && k!=a &&k!=b &&k!=c &&k!=d &&k!=e &&k!=f &&k!=g ) {

    x=a*1000+b*100+c*10+d;

    y=k*1000+e*100+f*10+b;

    z=k*10000+e*1000+c*100+b*10+g;  }

if(x+y==z){

printf("%d+%d=%d",x,y,z);

return 0; }}}}}}}}

return 0;}

2.题目2：2012年——古堡算式

福尔摩斯到某古堡探险，看到门上写着一个奇怪的算式：

    ABCDE * ? = EDCBA

    他对华生说：“ABCDE应该代表不同的数字，问号也代表某个数字！”

    华生：“我猜也是！”

于是，两人沉默了好久，还是没有算出合适的结果来。

请你利用计算机的优势，找到破解的答案。

把 ABCDE 所代表的数字写出来。

#include <stdio.h>

int main(){

int a,b,c,d,e;

int x,y,z;

for(a=1;a<10;a++){

for(b=1;b<10;b++){

for(c=0;c<10;c++){

for(d=1;d<10;d++){

for(e=0;e<10;e++){

if(a!=b  &&  a!=c  &&  a!=d  &&  a!=e  &&  b!=c  && b!=d  &&  b!=e  &&  c!=d  &&  c!=e  &&  d!=e){

   x=a*100+b*10+c;

   y=d*10+a;

   z=b*1000+c*100*d*10+e;

   if(x*y==z){

       printf("%d*%d=%d\n",x,y,z); } } } } } } }

return 0; }

3.小明是个急性子，上小学的时候经常把老师写在黑板上的题目抄错了。

有一次，老师出的题目是：36 x 495 = ?

他却给抄成了：396 x 45 = ?

但结果却很戏剧性，他的答案竟然是对的！！

因为 36 * 495 = 396 * 45 = 17820

类似这样的巧合情况可能还有很多，比如：27 * 594 = 297 * 54

假设 a b c d e 代表1~9不同的5个数字（注意是各不相同的数字，且不含0）

答案是:142

#include<stdio.h>

#include<math.h>

int main()

{

int a,b,c,d,e;

int x1,y1,x2,y2;

int i=0;

for(a=1;a<=9;a++)  {

for(b=1;b<=9;b++)  {

for(c=1;c<=9;c++)  {

for(d=1;d<=9;d++)  {

for(e=1;e<=9;e++)  {

if(a!=b&&a!=c&&a!=d&&a!=e&&

b!=c&&b!=e&&b!=d&&

c!=d&&c!=e&&

d!=e)  {

                    x1=a*10+b;

                    y1=c*100+d*10+e;

                    x2=a*100+d*10+b;

                    y2=c*10+e;

                    if(x1*y1==x2*y2)  {

                     i++;  } } } } } } }

printf("%d",i);

return 0;  }

4.题目4：2015年——三羊献瑞

观察下面的加法算式：

其中，相同的汉字代表相同的数字，不同的汉字代表不同的数字。

请你填写“三羊献瑞”所代表的4位数字（答案唯一），不要填写任何多余内容。

#include<stdio.h>

#include<math.h>

int main()  {

int a,b,c,d,e,f,g; 

int x,y,z,k=1;

for(a=0;a<=9;a++)  {

for(b=0;b<=9;b++)  {

for(c=0;c<=9;c++)  {

for(d=0;d<=9;d++)  {

for(e=0;e<=9;e++)  {

for(f=0;f<=9;f++)  {

for(g=0;g<=9;g++)  {

                            if(a!=b && a!=c&& a!=d&&a!=e && a!=f&& a!=g && 

b!=c && b!=d && b!=e && b!=f && b!=g &&

c!=d && c!=e && c!=f && c!=g

 && d!=e && d!=f && d!=g &&

  e!=f && e!=g &&

   f!=g

   && k!=a &&k!=b &&k!=c &&k!=d &&k!=e &&k!=f &&k!=g )  {

    x=a*1000+b*100+c*10+d;

    y=k*1000+e*100+f*10+b;

    z=k*10000+e*1000+c*100+b*10+g;   }

if(x+y==z)  {

printf("%d+%d=%d",x,y,z);

return 0;  } } } } } } } }

return 0;}

5.题目1：2015年——加法变乘法

我们都知道：1+2+3+ ... + 49 = 1225

现在要求你把其中两个不相邻的加号变成乘号，使得结果为2015。

比如：1+2+3+...+10*11+12+...+27*28+29+...+49 = 2015 就是符合要求的答案。

请你寻找另外一个可能的答案，并把位置靠前的那个乘号左边的数字提交（对于示例，就是提交10）。

#include <stdio.h>

int main()

{

int i,j;

for(i=1;i<=48;i++)  {

for(j=i+2;j<=48;j++)  {

if(i*(i+1)+j*(j+1)==2015-1225-i-(i+1)-j-(j+1))

   printf("%d %d %d %d\n",i,i+1,j,j+1);  } }

return 0; } 

6.题目2：625

625这个数字很特别，625的平方等于390625，刚好其末3位是625本身。除了625，还有其它的3位数有这个特征吗？

请编写程序，寻找所有这样的3位数：它的平方的末3位是这个数字本身。

输出结果中，从小到大，每个找到的数字占一行。比如那个625就输出为：625

#include <stdio.h>

#include <math.h>

int main(){

long long n,x,y;

for(n=100;n<1000;n++) {

x=n*n;

y=x%1000;

if(n==y)   {

printf("%lld\n",n);  } }

return 0; }

7.题目 3：立方和问题。

考虑方程式：a^3 + b^3 = c^3 + d^3

其中：“^”表示乘方。a、b、c、d是互不相同的小于30的正整数。这个方程有很多解。比如：

a = 1，b=12，c=9，d=10 就是一个解。因为：1的立方加12的立方等于1729，而9的立方加10的立方也等于1729。

当然，a=12，b=1，c=9，d=10 显然也是解。

如果不计abcd交换次序的情况，这算同一个解。

请编写程序实现如下任务：找到所有小于30的不同的正整数解。把a b c d按从小到大排列，用逗号分隔，每个解占用1行。比如，刚才的解输出为：1,9,10,12    不同解间的顺序可以不考虑。

#include <stdio.h>

int main()

{

int a,b,c,d;

for(a=1;a<=30;a++)  {

for(b=1;b<30;b++)  {

for(c=a+1;c<=30;c++)  {

for(d=c+1;d<=30;d++)  {

if(a!=b && a!=c && a!=d && b!=c && b!=d && c!=d)  {

if(a*a*a+b*b*b==c*c*c+d*d*d)

   printf("%d,%d,%d,%d\n",a,c,d,b);  } } } } } } 

第8讲 递归函数的构建及其应用

题目1：递归函数构建——输出begin到end

编写一个递归函数，分行输出begin到end。然后在主函数中调用该函数进行测试。

#include<stdio.h>

int giao(int a,int b)

{

    if(a==b)   {

     printf("%d\n",b);

     return 0;   }

printf("%d\n",a);

return giao(a+1,b);  }

int main()

{

int a,b;

scanf("%d %d",&a,&b);

giao(a,b);  }

题目2：编写递归函数int mysum(int n)，功能是实现求1到n之和并返回。然后在主函数中输入整数n，调用mysum函数求1到n之和并输出。

#include<stdio.h>

int giao (int n)

{

if(n==0) return 0;

if(n==1) return 1;

return giao(n-1)+n;  }

int main()  {

int n,sum=0;

scanf("%d",&n);

sum=giao(n);

printf("%d\n",sum);  } 

3.题目：编写递归函数求两个数的最大公约数

编写递归函数int gcd(int m,int n)计算m和n的最大公约数并返回。然后在主函数中输入2个整数并调用gcd函数求最大公约数并输出。

#include<stdio.h>

int giao (int m,int n)

{

if(m%n==0) return n;

return giao(n,m%n);  }

int main()  {

int m,n,x;

scanf("%d %d",&m,&n);

x=giao(m,n);

printf("%d\n",x);   }

4.题目.使用递归，求数组的前n项之和。

int mysum1( int a[ ],int n )   

//该递归函数是求数组a的前n个元素之和 

{

}

#include<stdio.h>

int giao (int a[],int n)

{

if(n==0) return 0;

if(n==1) return 1;

return giao(a,n-1)+a[n-1];  }

int main()

{

int n,sum=0,a[100];

scanf("%d",&n);

for(int i=0;i<n;i++)

scanf("%d",&a[i]);

sum=giao(a,n);

printf("%d\n",sum);

} 

5.题目.使用递归，求数组的前n项之和。

int mysum2( int a[ ],int L,int R ) 

 //该递归函数是求数组a的第L到第R个元素之和 

{

}

#include<stdio.h>

int giao (int a[],int L,int R)

{

if(L>R) return 0;

return a[L]+giao(a,L+1,R);  }

int main()

{

int n,sum=0,a[100];

scanf("%d",&n);

for(int i=0;i<n;i++)

scanf("%d",&a[i]);

sum=giao(a,0,n-1);

printf("%d\n",sum);  } 

（以下题目要求用递归函数实现）

题目 1575: 蓝桥杯算法提高VIP-递归倒置字符数组

完成一个递归程序，倒置字符数组。并打印实现过程

递归逻辑为：

当字符长度等于1时，直接返回

否则，调换首尾两个字符，在递归地倒置字符数组的剩下部分

输入   字符数组长度及该数组 

输出

在求解过程中，打印字符数组的变化情况。 

最后空一行，在程序结尾处打印倒置后该数组的各个元素。 

样例输入  5 abcde

样例输出

ebcda

edcba

Edcba

#include <stdio.h>

#include <string.h>

void mychar(char a[],int l,int r)

{

    if(l>=r) return ;

    char t;

    t=a[l];

    a[l]=a[r];

    a[r]=t;

    puts(a);

    mychar(a,l+1,r-1);  }

int main()  {

    char a[1000];

    int n;

    scanf("%d\n",&n);

    gets(a);

    mychar(a,0,n-1);

    printf("\n");

    puts(a);

    return 0;  }

题目 1400: 教学楼的楼梯

沈理工的教学楼有多少级楼梯，你造吗？

那么问题来了，假设共M级，刚开始时你在第一级，若每次只能跨上一级或二级，要走上第M级，共有多少种走法？

输入  输入数据首先包含一个整数N，表示测试实例的个数，然后是N行数据，每行包含一个整数M（1<=M<=40）,表示楼梯的级数。

输出   对于每个测试实例，请输出不同走法的数量

样例输入

2

2

3

样例输出

1

2

#include<stdio.h>

int main()

{

 int n,t,i;

 int f[40];

 scanf("%d",&n);

 f[0]=f[1]=1;

 for(i=2;i<40;i++)   {

  f[i]=f[i-1]+f[i-2];   }

 while(n--)  {

  scanf("%d",&t);

  if(t>=1&&t<=40)

   printf("%d\n",f[t-1]);   }

 return 0;  }

题目 1861: 程序员爬楼梯

程序员是善于思考的，有一天他在爬楼梯的时候想出一个问题。

  楼梯有 n 级。每次你只能爬 1 级或者 3 级，那么你有多少种方法爬到楼梯的顶部？

  开始的时候在0级楼梯，顶级在第n级。

输入  一行，一个n， 2<=n<=20。 

输出  一行，输出一个整数，表示爬到n级的方案数。

样例输入  3

样例输出  2

#include<stdio.h>

void my(int f[],int n)

{

 f[1]=f[2]=1;

 f[3]=2;

 for(int i=4;i<=20;i++)

   f[i]=f[i-1]+f[i-3];  }

int main()

{

 int n,f[20];

 scanf("%d",&n);

 my(f,n);

 printf("%d",f[n]);

 return 0;  }

题目 1257: 超级楼梯

有一楼梯共M级，刚开始时你在第一级，若每次只能跨上一级或二级，要走上第M级，共有多少种走法？

输入

输入数据首先包含一个整数N，表示测试实例的个数，然后是N行数据，每行包含一个整数M（1<=M<=40）,表示楼梯的级数。

输出

对于每个测试实例，请输出不同走法的数量

样例输入

2

2

3

样例输出

1

2

#include<stdio.h>

void myfun(int f[],int n)

{

 f[0]=f[1]=1;

 for(int i=2;i<=40;i++) {

  f[i]=f[i-1]+f[i-2];   }}

int main()  {

 int n,t;

 int f[40];

 scanf("%d",&n);

 myfun(f,n);

 while(n--)  {

  scanf("%d",&t);

  if(t>=2&&t<=40)

   printf("%d\n",f[t-1]);   }

 return 0;  }

题目 1031: [编程入门]自定义函数之字符串反转

写一函数，使输入的一个字符串按反序存放，在主函数中输入并输出反序后的字符串（不包含空格）。

输入  一行字符

输出  逆序后的字符串

样例输入  123456abcdef 

样例输出  fedcba654321

#include<stdio.h>

#include<string.h>

void mychar(char a[],int L,int R)

{

 char t;

 if(L>=R) return ;

  t=a[L];

  a[L]=a[R];

  a[R]=t;

 mychar(a,L+1,R-1);

}

int main()  {

 char a[100];

 int len;

 gets(a);

 len=strlen(a);

    mychar(a,0,len-1);

 puts(a);

 return 0;  }

题目 1093: 字符逆序（C++）

将一个字符串str的内容颠倒过来，并输出。str的长度不超过100个字符。

输入   输入包括一行。 第一行输入的字符串。

输出   输出转换好的逆序字符串。

样例输入   I am a student

样例输出   tneduts a ma I

#include<bits/stdc++.h>

#include<string.h>

using namespace std;

int main()  {

     string a;

     getline(cin,a);

     reverse(a.begin(),a.end());

     cout<<a;

 return 0;  }

题目 1026: [编程入门]数字逆序输出

输入10个数字，然后逆序输出。

输入  十个整数

输出  逆序输出，空格分开

样例输入  1 2 3 4 5 6 7 8 9 0

样例输出  0 9 8 7 6 5 4 3 2 1

#include<stdio.h>

int main()  {

 int a[10],i,j;

 for(i=0;i<10;i++)

   scanf("%d",&a[i]);

 for(i=9;i>=0;i--)

   printf("%d ",a[i]);

 return 0;  }

题目 1931: 蓝桥杯算法提高VIP-逆序排列

编写一个程序，读入一组整数（不超过20个），并把它们保存在一个整型数组中。当用户输入0时，表示输入结束。然后程序将把这个数组中的值按逆序重新存放，并打印出来。例如：假设用户输入了一组数据：7 19 -5 6 2 0，那么程序将会把前五个有效数据保存在一个数组中，即7 19 -5 6 2，然后把这个数组中的值按逆序重新存放，即变成了2 6 -5 19 7，然后把它们打印出来。

输入  输入只有一行，由若干个整数组成，中间用空格隔开，最末尾的整数为0。

输出  输出也只有一行，即逆序排列后的整数，中间用空格隔开，末尾没有空格。

样例输入  7 19 -5 6 2 0

样例输出  2 6 -5 19 7

#include<stdio.h>

void myfun(int a[],int n)  {

 int i,t;

 for(i=0;i<n/2;i++)  {

  t=a[i];

  a[i]=a[n-i-1];

  a[n-i-1]=t;   } }

int main()  {

 int i,j,t,n;

 int a[20];

 for(i=0;i<20;i++)   {

  scanf("%d",&a[i]);

  if(a[i]==0)

    break;   }

 myfun(a,i);

 for(j=0;j<i;j++)

   printf("%d ",a[j]);

 return 0;  }

题目 1999: 回文判断

若一个正整数从左向右读与从右向左读都一样，我们就将其称之为回文数（例如12321、44、3都是回文数）。输入一个正整数，判断它是否是回文数，是则输出YES，否则输出NO。（提示：以字符串形式读取输入的整数）

输入  正整数

输出  YES或NO

样例输入  2332

样例输出  YES

#include<stdio.h>

#include<string.h>

int myhui(char a[],int l,int r)  {

 if(l>r) return 1;

 if(a[l]!=a[r]) return 0;

 return myhui(a,l+1,r-1);  }

int main()  {

 char a[1000];

 int b,len;

 gets(a);

 len=strlen(a);

 b=myhui(a,0,len-1);

 if(b) printf("YES\n");

 else  printf("NO\n");

 return 0;  }

题目 1200: 回文串

回文串是从左到右或者从右到左读起来都一样的字符串，试编程判别一个字符串是否为回文串。

输入  输入一个字符串。串长度<255.

输出  判别输入的字符串是否为回文串，是输出"Y",否则输出"N"。

样例输入  abcba

样例输出  Y

#include<stdio.h>

#include<string.h>

int myhui(char a[],int l,int r)  {

 if(l>r) return 1;

 if(a[l]!=a[r]) return 0;

 return myhui(a,l+1,r-1);  }

int main()  {

 char a[1000];

 int b,len;

 gets(a);

 len=strlen(a);

 b=myhui(a,0,len-1);

 if(b) printf("Y\n");

 else  printf("N\n");

 return 0;  }

第10讲 C++标准模板库（STL）介绍和使用

问题 1219: 数列排序（C++）

将一正整数序列{K1,K2,...,K9}重新排列成一个新的序列。新序列中，比K1小的数都在K1的前面(左面)，比K1大的数都在K1的后面(右面)。

输入   输入有多行,第一行为N表示行数,每行9个整数.

输出   输出N行,按要求进行排序的结果.

样例输入

2

6 8 9 1 2 5 4 7 3

3 5 8 9 1 2 6 4 7

样例输出

3 4 5 2 1 6 8 9 7

2 1 3 5 8 9 6 4 7

#include<bits/stdc++.h>

using namespace std;

int main()

{

int n,k,ki,len;

vector <int> v;

cin>>n;

while(n--) {

cin>>k;

v.push_back(k);

for(int i=1;i<9;i++) {

cin>>ki;

if(ki>k) 

  v.push_back(ki);

else

  v.insert(v.begin(),ki); } 

 len=v.size();

for(int i=0;i<len;i++)

  cout<<v[i]<<' ';

cout<<endl;

    v.clear();  }

return 0;  }

问题 1487: [蓝桥杯][算法提高VIP]不同单词个数统计（C++）

编写一个程序，输入一个句子，然后统计出这个句子当中不同的单词个数。例如：对于句子“one  little  two  little  three  little  boys”，总共有5个不同的单词：one,  little,  two,  three,  boys。

说明：（1）由于句子当中包含有空格，所以应该用gets函数来输入这个句子；（2）输入的句子当中只包含英文字符和空格，单词之间用一个空格隔开；（3）不用考虑单词的大小写，假设输入的都是小写字符；（4）句子长度不超过100个字符。

输入  输入只有一行，即一个英文句子。

输出  输出只有一行，是一个整数，表示句子中不同单词的个数。

样例输入  one little two little three little boys

样例输出  5

#include<bits/stdc++.h>

using namespace std;

int main()  {  

   string ch;

   set <string> s;

   while(cin>>ch)  {

    s.insert(ch);  } 

   int len=s.size();

   cout<<len;

   return 0;  }

题目 2162: [信息学奥赛一本通-T1239]统计数字（C++）

某次科研调查时得到了n个自然数，每个数均不超过1500000000（1.5∗10^9）。已知不相同的数不超过10000个，现在需要统计这些自然数各自出现的次数，并按照自然数从小到大的顺序输出统计结果。

输入

第一行是整数 n，表示自然数的个数；

第2~n+1每行一个自然数。

输出

包含m行（m为n个自然数中不相同数的个数），按照自然数从小到大的顺序输出。每行输出两个整数，分别是自然数和该数出现的次数，其间用一个空格隔开。

样例输入

8

2

4

2

4

5

100

2

100

样例输出

2 3

4 2

5 1

100 2

#include<bits/stdc++.h>

using namespace std;

int main()  {  

   map <int,int> mp;

   int n,key;

   cin>>n;

   while(n--)  {

     cin>>key;

     mp[key]=mp[key]+1;  }

   map<int,int>::iterator it;

   for(it=mp.begin();it!=mp.end();it++)  {

     cout<<it->first<<" "<<it->second<<endl;  }

   return 0;  }

问题 1724: 后缀子串排序（C++）

题目描述

对于一个字符串，将其后缀子串进行排序，例如grain

其子串有：

grain

rain

ain

in

n

然后对各子串按字典顺序排序，即：ain,grain,in,n,rain

输入  每个案例为一行字符串。

输出  将子串排序输出

样例输入

grain

banana

样例输出

ain

grain

in

n

rain

a

ana

anana

banana

na

Nana

#include<bits/stdc++.h> 

using namespace std;

bool cmp(char *s1,char *s2)   {

    return strcmp(s1,s2)<0;  }

int main()   {

    char s[1000];  

    char *str[1000];   

    while(cin>>s)  {  

        int len=strlen(s);  

        for(int i=0;i<len;i++)  

            str[i]=s+i;

        sort(str,str+len,cmp);  

        for(int i=0;i<len;i++)   

            cout<<str[i]<<endl;   }

    return 0;  }

题目 2046: 输出全排列（C++）

给出一个数n，要求你输出1到n的全排列（要求字典序从小到大）(n<=10)

输入  一个数n

输出  包括若干行，每行包含n个数，表示相应的全排列值。

样例输入  4

样例输出

1 2 3 4

1 2 4 3

1 3 2 4

1 3 4 2

1 4 2 3

1 4 3 2

2 1 3 4

2 1 4 3

2 3 1 4

2 3 4 1

2 4 1 3

2 4 3 1

3 1 2 4

3 1 4 2

3 2 1 4

3 2 4 1

3 4 1 2

3 4 2 1

4 1 2 3

4 1 3 2

4 2 1 3

4 2 3 1

4 3 1 2

4 3 2 1

#include<bits/stdc++.h>

using namespace std;

int main()

{

 int a[10]={1,2,3,4,5,6,7,8,9,10};

 int n;

 scanf("%d",&n);

 do  {

   for(int i=0;i<n;i++)

     printf("%d ",a[i]);

   printf("\n");   }

while(next_permutation(a,a+n));

 return 0;  } 

题目 1913: [蓝桥杯][算法提高VIP]排列数（C++）

0、1、2三个数字的全排列有六种，按照字母序排列如下：

012、021、102、120、201、210

输入一个数n  求0~9十个数的全排列中的第n个（第1个为0123456789）。

输入  一行，包含一个整数n

输出  一行，包含一组10个数字的全排列

样例输入  1

样例输出  0123456789

#include<bits/stdc++.h>

#include<string.h>

using namespace std;

int main()  {

 int a[10]={0,1,2,3,4,5,6,7,8,9};

 int n,t=0;

 scanf("%d",&n);

 do  {

  t++;

  if(t==n)  {

   for(int i=0;i<10;i++)

         printf("%d",a[i]);

      break; }

 }while(next_permutation(a,a+10));

  return 0;  }

第11讲 并查集

题目 1732: 连通图（C++）

给定一个无向图和其中的所有边，判断这个图是否所有顶点都是连通的。

输入

每组数据的第一行是两个整数 n 和 m（0<=n<=1000）。n 表示图的顶点数目，m 表示图中边的数目。如果 n 为 0 表示输入结束。随后有 m 行数据，每行有两个值 x 和 y（0<x, y <=n），表示顶点 x 和 y 相连，顶点的编号从 1 开始计算。输入不保证这些边是否重复。

输出

对于每组输入数据，如果所有顶点都是连通的，输出"YES"，否则输出"NO"。

样例输入

4 3

4 3

1 2

1 3

5 7

3 5

2 3

1 3

3 2

2 5

3 4

4 1

7 3

6 2

3 1

5 6

0 0

样例输出

YES

YES

NO

#include<bits/stdc++.h>

#include<string.h>

using namespace std;

int edge[1010][1010];

bool vis[1010];

int n,m;

int b,e;

void dfs(int step)  {

    vis[step]=true;

    for(int i=1;i<=n;++i) {

        if(vis[i]) continue;

        if(edge[step][i]) {

            vis[i]=true;

            dfs(i);    }    }    }

int main()  {

    cin >> n >> m;

    while(n!=0) {

        memset(edge,0,sizeof(edge));

        memset(vis,0,sizeof(vis));

        for(int i=0;i<m;++i) {

            cin >> b >> e;

            edge[b][e]=1;

            edge[e][b]=1;   }

        dfs(1);

        bool flag=true;

        for(int i=1;i<=n;++i) {

            if(!vis[i]) {

                flag=false;break;  }  }

        if(flag) cout << "YES" << endl;

        else cout << "NO" << endl;

        cin >> n >> m;  }

    return 0;  }

题目 2033: 网络互通（C++）

对于有n个住户的小区，我们决定拉网线构成一个网络。

每次，我们可以对两户人家进行连接，让他们之间进行通讯。当然，如果你在此基础之上继续拉网线，能通讯的人将会风一般地增加。

现在，我们已经给若干住户连上了网络，那么，请问某些住户之间是否能通信？

这里，如果两个住户可以连接，那么与其相连的住户同样能相互连接。

输入

第一行是两个数字n（n<100000），m(m<100000)表示住户个数与网线个数。

接下来m行，每行是两个数字xi,xj，表示xi与xj有网络连接。

接下来是两个数x，y表示询问的住户是否能通信。

输出

如果能通信输出Yes，否则输出No

样例输入

5 6

1 4

2 3

3 5

2 4

1 5

1 2

2 5

样例输出  Yes

#include<bits/stdc++.h>

using namespace std;

#define N 100005

int father[N];

void Init(int n)

{

for(int i=1;i<=n;i++)

 father[i]=i;

}

int Find(int x)

{

if(father[x]==x)

return x;

return Find(father[x]);

}

void Union(int x,int y)

{

int fx,fy;

fx=Find(x);

fy=Find(y);

if(x!=y)

father[fx]=fy;

}

int main()

{

int n,m;

scanf("%d%d",&n,&m);

Init(n);

while(m--)

{

int xj,xi;

scanf("%d%d",&xj,&xi);

Union(xj,xi);

}

int x,y;

scanf("%d%d",&x,&y);

if(Find(x)==Find(y))

printf("Yes\n");

else

printf("No\n");

return 0;  }

题目 1744: 畅通工程（C++）

某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路可达即可）。问最少还需要建设多少条道路？

输入

测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数，分别是城镇数目N ( < 1000 )和道路数目M；随后的M行对应M条道路，每行给出一对正整数，分别是该条道路直接连通的两个城镇的编号。为简单起见，城镇从1到N编号。 

    注意:两个城市之间可以有多条道路相通,也就是说

    3 3

    1 2

    1 2

    2 1

    这种输入也是合法的

    当N为0时，输入结束，该用例不被处理。

输出  对每个测试用例，在1行里输出最少还需要建设的道路数目。

样例输入

5 3

1 2

3 2

4 5

0

样例输出   1

#include <cstdio>

#include <deque>

#include<bits/stdc++.h>

using namespace std;

const long long INF = 1000000000;

const int MAX_N = 1000;

class disjointSet {

public:

    int parent[MAX_N];

    disjointSet() {

        for (int i = 0; i < MAX_N; ++i) {

            parent[i] = i;  } }

    int find(int x) {

        if (parent[x] == x) {

            return x;  }

 else {

            return parent[x] = find(parent[x]); } }

    bool unite(int x, int y) {

        int rootX = find(x);

        int rootY = find(y);

        if (rootX == rootY)  {

            return false;  }

        parent[rootY] = rootX;

        return true;  }

    bool same(int x, int y) {

        return find(x) == find(y);  }};

int disjointSetMain()

{

    int x, y, n, m;

    while (~scanf("%d", &n) && n != 0) {

        scanf("%d", &m);

        disjointSet parent = disjointSet();

        for (int i = 1; i <= m; ++i) {

            scanf("%d%d", &x, &y);

            parent.unite(x, y);  }

        int count = 0;

        for (int i = 1; i <= n; ++i) {

            if (parent.parent[i] == i) {

                count ++;   } }

        printf("%d\n", count - 1);  } }

int main()  {

    disjointSetMain();  }

P3367 【模板】并查集（C++）

如题，现在有一个并查集，你需要完成合并和查询操作。

输入格式

第一行包含两个整数 N,MN,M ,表示共有 NN 个元素和 MM 个操作。

接下来 MM 行，每行包含三个整数 Z_i,X_i,Y_iZi,Xi,Yi 。

当 Z_i=1Zi=1 时，将 X_iXi 与 Y_iYi 所在的集合合并。

当 Z_i=2Zi=2 时，输出 X_iXi 与 Y_iYi 是否在同一集合内，是的输出 Y ；否则输出 N 。

输出格式

对于每一个 Z_i=2Zi=2 的操作，都有一行输出，每行包含一个大写字母，为 Y 或者 N 。

输入

2 1 2

1 1 2

2 1 2

1 3 4

2 1 4

1 2 3

2 1 4

输出

Y

N

Y

#include<bits/stdc++.h>

using namespace std;

int i,j,k,n,m,s,ans,f[10010],p1,p2,p3;

int find(int k)  {

    if(f[k]==k)return k;

    return f[k]=find(f[k]);  }

int main()  {

    cin>>n>>m;

    for(i=1;i<=n;i++)

        f[i]=i;

    for(i=1;i<=m;i++)  {

        cin>>p1>>p2>>p3;

        if(p1==1)

            f[find(p2)]=find(p3);

        else

            if(find(p2)==find(p3))

                printf("Y\n");

            else

                printf("N\n");  }

    return 0;  }

P1551 亲戚

题目背景

若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。

题目描述

规定：xx 和 yy 是亲戚，yy 和 zz 是亲戚，那么 xx 和 zz 也是亲戚。如果 xx，yy 是亲戚，那么 xx 的亲戚都是 yy 的亲戚，yy 的亲戚也都是 xx 的亲戚。

输入格式

第一行：三个整数 n,m,pn,m,p，（n,m,p \le 5000n,m,p≤5000），分别表示有 nn 个人，mm 个亲戚关系，询问 pp 对亲戚关系。

以下 mm 行：每行两个数 M_iMi，M_jMj，1 \le M_i,~M_j\le N1≤Mi, Mj≤N，表示 M_iMi 和 M_jMj 具有亲戚关系。

接下来 pp 行：每行两个数 P_i,P_jPi,Pj，询问 P_iPi 和 P_jPj 是否具有亲戚关系。

输出格式

pp 行，每行一个 Yes 或 No。表示第 ii 个询问的答案为“具有”或“不具有”亲戚关系。

输入

1 2

1 5

3 4

5 2

1 3

1 4

2 3

5 6

输出

Yes

No

#include<bits/stdc++.h>

using namespace std;

int n,m,q,f[10010],c,d,a,b;

int fd(int x)

{

 if(f[x]==x)

 return x;

 else 

 return  f[x]=fd(f[x]);  }

void hb(int x,int y)  {

 f[fd(y)]=fd(x);

 return ;  }

int main()  {

 scanf("%d%d%d",&n,&m,&q);

 for(int i=1;i<=n;i++)

 f[i]=i;

 for(int i=1;i<=m;i++)   {

      scanf("%d%d",&c,&d);

      hb(c,d);   }

 for(int i=1;i<=q;i++)  {

  scanf("%d%d",&a,&b);

  if(fd(a)==fd(b))

  printf("Yes\n");

  else

  printf("No\n");  }

 return 0;  }

P1892 [BOI2003]团伙

给定 nn 个人，他们之间有两个种关系，朋友与敌对。可以肯定的是：

与我的朋友是朋友的人是我的朋友

与我敌对的人有敌对关系的人是我的朋友

现在这 nn 个人进行组团，两个人在一个团队内当且仅当他们是朋友。

求最多的团体数。

输入格式

第一行一个整数 nn 代表人数。

第二行一个整数 mm 代表每个人之间的关系。

接下来 mm 行每行一个字符 optopt 与两个整数 p,qp,q

如果 optopt 为 F 代表 pp 与 qq 为朋友。

如果 optopt 为 E 代表 pp 与 qq 为敌人。

输出格式   一行一个整数代表最多的团体数。

输入

4

E 1 4

F 3 5

F 4 6

E 1 2

输出   3

#include<bits/stdc++.h>

using namespace std;

int n,m,f[1001],enm[1001];   

int find(int x)            

{

    while(f[x]!=x) x=f[x]; 

    return x;  }

void hebing(int x,int y)    {

    x=find(x);y=find(y);  

    if(x==y) return;

    f[y]=x;

    return;  }

int main()  {

     cin>>n>>m;

     for(int i=1;i<=n;i++)

        f[i]=i;

    for(int i=1;i<=m;i++)   {

        int p,q;

        char c;

        cin>>c>>p>>q;

        if(c=='F') hebing(p,q);   

        else {

                if(enm[p]==0) enm[p]=find(q);

              else hebing(q,enm[p]);   

              if(enm[q]==0) enm[q]=find(p);

              else hebing(p,enm[q]);   }  }

    int count[1001]={0};

    for(int i=1;i<=n;i++)

        count[find(i)]++;

    int cnt=0;

    for(int i=1;i<=n;i++)

        if(count[i]) cnt++;  

    cout<<cnt;   } 

第12讲 二分查找和快速幂

题目 1710: 数据结构-静态表的顺序查找
用顺序表或者线性链表表示静态查找表时，搜索函数可以采用顺序查找来实现。
通常顺序查找的查找过程是从表中的自后一个记录开始，逐个将记录的关键字和给定的查找值进行比较，如果某个记录的关键字与给定的值比较相等，则说明查找成功；否则如果直到第一个记录，所有的关键字都与给定的值不相等，说明表中没有响应的记录，查找失败。
其查找过程可以描述如下：

在本题中，读入一串整数，另外给定多次查询，判断每一次查询是否找到了相应的整数，如果找到则输出整数相应的位置。
输入
输入的第一行包含2个正整数n和k，分别表示共有n个整数和k次查询。其中n不超过500，k同样不超过500。
第二行包含n个用空格隔开的正整数，表示n个原始记录。
第三行包含k个用空格隔开的正整数，表示k次查询的目标。
输出
只有1行，包含k个整数，分别表示每一次的查询结果。如果在查询中找到了对应的整数，则输出其相应的位置，否则输出-1。
请在每个整数后输出一个空格，并请注意行尾输出换行。
样例输入   8 31 3 5 7 8 9 10 159 2 5
样例输出   5 -1 2 

#include<stdio.h>

int serach(int a[],int n,int x)  {

 for(int i=n-1;i>=0;i--)  {

  if(x==a[i]) return i;   }

 return -1;  }

int main()  {

 int n,k;

 int a[505];

 scanf("%d%d",&n,&k);

 for(int i=0;i<n;i++)

   scanf("%d",&a[i]);

 while(k--)   {

  int x, pos;

  scanf("%d",&x);

  pos=serach(a,n,x);

  printf("%d ",pos);   }

 return 0; }

题目 1711: 数据结构-有序表的折半查找（1710的类似题）
用有序表表示静态查找表时，通常检索函数可以用折半查找来实现。
折半查找的查找过程是：首先确定待查记录所在的范围，然后逐步缩小范围直到找到或者确定找不到相应的记录为止。而每次需要缩小的范围均为上一次的一半，这样的查找过程可以被称为折半查找。
其查找过程可以描述如下：

在本题中读入一串有序的整数，另外给定多次查询，判断每一次查询是否找到了相应的整数，如果找到则输出整数相应的位置。
输入
输入的第一行包含2个正整数n和k，分别表示共有n个整数和k次查询。其中n不超过1000，k同样不超过1000。
第二行包含n个用空格隔开的正整数，表示n个有序的整数。输入保证这n个整数是从小到大递增的。
第三行包含k个用空格隔开的正整数，表示k次查询的目标。
输出
只有1行，包含k个整数，分别表示每一次的查询结果。如果在查询中找到了对应的整数，则输出其相应的位置，否则输出-1。
请在每个整数后输出一个空格，并请注意行尾输出换行。
样例输入  8 31 3 5 7 8 9 10 159 2 5
样例输出  5 -1 2 

#include <stdio.h>

int search(int a[],int n,int x)  {

for(int i=0;i<n;i++)  {

if(x==a[i])  return i;  }

return -1;  }

int main()  {

int a[1005];

int n,k;

scanf("%d%d",&n,&k);

for(int i=0;i<n;i++)

    scanf("%d",&a[i]);

while(k--)  {

int x,pos;

scanf("%d",&x);

pos=search(a,n,x);

printf("%d ",pos);  }

return 0;  }

P2249 【深基13.例1】查找

#include <stdio.h>

int a[1000005];

int search(int a[],int n,int x)  

{

int L,R,mid;

L=0; R=n-1;

while(L<=R)  {

mid=(L+R)/2;

if(x>a[mid]) L=mid+1; 

else  R=mid-1;  }

return a[L]==x? L+1 : -1;   }

int main()   {

int n,k;

scanf("%d%d",&n,&k);

for(int i=0;i<n;i++)

    scanf("%d",&a[i]);

while(k--)  {

int x,pos;

scanf("%d",&x);

pos=search(a,n,x);

printf("%d ",pos);  }

return 0;  }

题目 2163: 信息学奥赛一本通T1240-查找最接近的元素

在一个非降序列中，查找与给定值最接近的元素。

输入

第一行包含一个整数n，为非降序列长度。1 ≤ n ≤ 100000。

第二行包含n个整数，为非降序列各元素。所有元素的大小均在0-1,000,000,000之间。

第三行包含一个整数m，为要询问的给定值个数。1 ≤ m ≤ 10000。

接下来m行，每行一个整数，为要询问最接近元素的给定值。所有给定值的大小均在0-1,000,000,000之间。

输出

m行，每行一个整数，为最接近相应给定值的元素值，保持输入顺序。若有多个值满足条件，输出最小的一个。

样例输入

3

2 5 8

2

10

5

样例输出

8

5

#include<stdio.h> 

int a[1000005];

int serach(int a[],int n,int x)  {

 int L,R,mid;

 L=0;R=n-1;

 while(L<=R)  {

  mid=(L+R)/2;

  if(x>a[mid]) L=mid+1;

  else R=mid-1;   }

 if(L==0) return a[0];

 if(L==n) return a[n-1];

 if(x-a[L-1]<=a[L]-x) return a[L-1];

 else return a[L];   }

int main()  {

 int n,k;

 scanf("%d",&n); 

 for(int i=0;i<n;i++)

   scanf("%d",&a[i]);

 scanf("%d",&k);

 while(k--)   {

  int x, pos;

  scanf("%d",&x);

  pos=serach(a,n,x);

  printf("%d\n",pos);  }

 return 0;  }

题目 2088: 蓝桥杯算法提高VIP-快速幂

给定A, B, P，求(A^B) mod P。

输入

输入共一行。

第一行有三个数，N, M, P。

输出

输出共一行，表示所求。

共10组数据

对100%的数据，A, B为long long范围内的非负整数，P为int内的非负整数。

样例输入  2 5 3

样例输出  2

#include<stdio.h>

typedef long long LL;

LL qpow(LL a,LL b,LL p)

{

 if (b==0) return 1%p;

 if(b%2==1) return (a%p)* qpow(a,b-1,p)%p %p;

 else{

  LL t=qpow(a,b/2,p)%p;

  return (t*t)%p;  } }

int main()

{

 LL a,b,p,t;

 scanf("%lld%lld%lld",&a,&b,&p);

 t=qpow(a,b,p);

 printf("%lld",t);

 return 0;  }

P1226 【模板】快速幂||取余运算

#include <iostream>

using namespace std;

int qmi(int a, int b, int p)

{

    int res = 1;

    while (b)  {

        if (b & 1)

            res = (long long) res * a % p;

        b >>= 1;

        a = (long long) a * a % p;   }

    return res;  }

int main()  {

    int a, b, p;

    scanf("%d%d%d", &a, &b, &p);

    printf("%d^%d mod %d=%d",a,b,p,qmi(a, b, p));

    return 0;  }

————————————————————————

题目 1002: [编程入门]三个数最大值

编写一个程序，输入a、b、c三个值，输出其中最大值。

输入    一行数组，分别为a b c

输出    a b c其中最大的数

样例输入    10 20 30

样例输出    30

#include<stdio.h>

int main()

{

int a,b,c,max;

scanf("%d%d%d",&a,&b,&c);

max=a;

if(b>max) max=b;

if(c>max) max=c;

printf("%d\n",max);

return 0;  }

题目 1057: 二级C语言-分段函数

题目描述
有一个函数如下，写一程序，输入x，输出y值。保留两位小数
输入    无
输出    无
样例输入    1
样例输出    1.00 

#include<stdio.h>

int main()

{

 float x,y;

 scanf("%f",&x);

 if(x<1) y=x;

  else if(x<10) y=2*x-1;

   else if(x>=10) y=3*x-11;

 printf("%.2f\n",y);

 return 0;  }

题目 1058: 二级C语言-求偶数和

题目描述

编制程序，输入n个整数（n从键盘输入，n>0），输出它们的偶数和。

输入  无

输出  无

样例输入

2

1 2

样例输出

2

#include<stdio.h>

int main()

{

 int n,i,x;

 long long sum=0;

 scanf("%d",&n);

 for(i=1;i<=n;i++)  {

  scanf("%d",&x);

  if(x%2==0)

   sum=sum+x;  }

 printf("%lld",sum);

 return 0;  }

题目 1040: [编程入门]实数的打印

题目描述

请设计输出实数的格式，包括：⑴一行输出一个实数；⑵一行内输出两个实数；⑶一行内输出三个实数。实数用"6.2f"格式输出。

输入    一个实数，float范围

输出    输出3行，第一行打印一遍输入的数，第二行打印两遍，第三行打印三遍。 第二行和第三行，用空格分隔同一行的数字。 实数用"6.2f"格式输出。

样例输入    0.618

样例输出

  0.62

  0.62   0.62

  0.62   0.62   0.62

#include<stdio.h>

int main()

{

 float x;

 scanf("%f",&x);

 printf("%6.2f\n",x);

 printf("%6.2f %6.2f\n",x,x);

 printf("%6.2f %6.2f %6.2f",x,x,x);

 return 0;  }

题目 1434: 蓝桥杯历届试题-回文数字

观察数字：12321，123321  都有一个共同的特征，无论从左到右读还是从右向左读，都是相同的。这样的数字叫做：回文数字。
本题要求你找到一些5位或6位的十进制数字。满足如下要求：
该数字的各个数位之和等于输入的整数。

输入： 一个正整数  n  (10< n< 100),  表示要求满足的数位和

输出：

若干行，每行包含一个满足要求的5位或6位整数。 
数字按从小到大的顺序排列。 
如果没有满足条件的，输出：-1 

#include<stdio.h>

int main()

{

   int i,j,n,sum1,sum2,count=0;

   scanf("%d",&n);

   for(i=10000;i<=999999;i++)  {

     j=i;

     sum1=0;

     sum2=0;

     while(j>0)  {

       sum1=sum1*10+j%10;

       sum2+=j%10;

       j=j/10;  }

    if(sum1==i&&sum2==n)  {

      count++;

      printf("%d\n",i);  }  }

   if(count==0)  {

     printf("-1\n");  }

   return 0;  }

题目 1053: 二级C语言-平均值计算

输入10个整数，求它们的平均值，并输出大于平均值的数据的个数。

输入：  10个数

输出：  大于平均数的个数

样例输入：   1 2 3 4 5 6 7 8 9 10

样例输出：   5

#include<stdio.h>

int main()

{

 int i,sum=0,k,t=0;

 int a[10];

 for(i=0;i<10;i++)  {

  scanf("%d",&a[i]);

  sum+=a[i];  }

 k=sum/10;

 for(i=0;i<10;i++)  {

  if(a[i]>k) t++;  }

 printf("%d",t);

 return 0;  }

题目 1246: 第几天

这是一个很经典的题，给定一个日期，输出这个日期是该年的第几天。

输入

输入数据有多组，每组占一行，数据格式为YYYY/MM/DD组成（见样例） ,另外，可以向你确保所有的输入数据是合法的。

输出

对于每组输入数据，输出一行，表示该日期是该年的第几天。

样例输入：

1985/1/20

2006/3/12

样例输出：

20

71

#include <stdio.h>

#include <stdlib.h>

int main()

{

    int year,month,Day;

    while(scanf("%d/%d/%d",&year,&month,&Day)!=EOF)   {

        int i,day[12]={31,28,31,30,31,30,31,31,30,31,30,31};

        for(i=0;i<month-1;i++)

            Day+=day[i];

        if((year%4==0&&year%100!=0)||year%400==0)

            Day++;

        printf("%d\n",Day);  }

    return 0;  }

题目 1065: 二级C语言-最小绝对值

题目描述

输入10个数，找出其中绝对值最小的数，将它和最后一个数交换，然后输出这10个数。

输入    十个数

输出    交换后的十个数

样例输入    10 2 30 40 50 60 70 80 90 100

样例输出    10 100 30 40 50 60 70 80 90 2

#include<stdio.h>

#include<math.h>

int main()

{

   int i,a[10],min,t;

   for(i=0;i<10;i++)

     scanf("%d",&a[i]);

    min=a[0];

    for(i=0;i<10;i++)

     if(fabs(a[i])<fabs(min))

       min=a[i];

    for(i=0;i<10;i++)

     if(a[i]==min)  {

      t=a[i];

      a[i]=a[9];

      a[9]=t;

      break;  }

  for(i=0;i<10;i++)

    printf("%d ",a[i]);

 return 0;  }

题目 1126: C语言训练-字符串正反连接

所给字符串正序和反序连接，形成新串并输出

输入   任意字符串（长度<=50）

输出   字符串正序和反序连接所成的新字符串

样例输入   123abc

样例输出   123abccba321

#include<stdio.h>

#include<string.h>

int main()

{

 char s[60],t[120];

 int i,j;

 gets(s);

 for(i=0,j=0;s[i]!='\0';i++,j++) {

  t[j]=s[i]; }

 for(i=i-1;i>=0;i--,j++) {

  t[j]=s[i]; }

 t[j]='\0';

 printf("%s",t);

 return 0;  }

题目 1206: 字符串问题

字符串处理在计算机中有很多复杂的操作，但是这些复杂的操作都是由基本的字符串操作复合而成，要求编写一字符串颠倒的程序，把字符串中的字符颠倒位置。

输入    输入一