Baileysok


私信TA

用户名:H2030819055

访问量:517

签 名:

勇闯天涯 superX

等  级
排  名 944
经  验 2445
参赛次数 10
文章发表 6
年  龄 20
在职情况 学生
学  校 贺州学院
专  业 软件工程

  自我简介:

勇闯天涯 superX

TA的其他文章

第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: 字符串问题

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

输入    输入一

 

0.0分

0 人评分

  评论区