2013年蓝桥杯C++组真题解析2

2019-03-15  本文已影响0人  你要好好学习呀
题目7:错误票据

某涉密单位下发了某种票据,并要在年终全部收回。
每张票据有唯一的ID号。全年所有票据的ID号是连续的,但ID的开始数码是随机选定的。
因为工作人员疏忽,在录入ID号的时候发生了一处错误,造成了某个ID断号,另外一个ID重号。
你的任务是通过编程,找出断号的ID和重号的ID。
假设断号不可能发生在最大和最小号。
要求程序首先输入一个整数N(N<100)表示后面数据行数。
接着读入N行数据。
每行数据长度不等,是用空格分开的若干个(不大于100个)正整数(不大于100000)
每个整数代表一个ID号。

要求程序输出1行,含两个整数m n,用空格分隔。
其中,m表示断号ID,n表示重号ID
例如:
用户输入:
2
5 6 8 11 9
10 12 9
则程序输出:
7 9


/*
istringstream-用于执行C++风格的串流的输入操作
ostringstream-用于执行C风格的串流的输出操作
*/
#include <bits/stdc++.h>
using namespace std;
//输入N行数据,每行的数据数和数据总数是不确定的,要找出断号数据和重号数据。
//先输出断号数据,再输出重号数据
//关键在于字符串的处理和转化
void s2i(string &str,int &num)
{
    stringstream ss;//stringstream可以支持C风格的输入输出操作
    ss<<str;//流插入运算符 <<
    ss>>num;//流提取运算符 >>
}
int line;
const int MaxN=10000;//最大的数据总数为100*100
int data[MaxN];
int main(){
    scanf("%d",&line);
    getchar();//把换行符吃掉
    int index=0;//读出的数据数,最终的到的是数据总数
    for(int i=0;i<line;i++)
    {
        string s;
        getline(cin,s);//字符串s为输入的一行数据
        istringstream iss(s);//把s封装到istringstream
        string tmp;
        while(getline(iss,tmp,' ')){//将iss中的数据按照空格进行切分,切分后的每一个数据都放在tmp中
            s2i(tmp,data[index++]);//先取内容,再+1
        }
    }
    //数据输入是乱序的,要进行排序
    sort(data,data+index);//index表示数据长度
    int a,b;
    for(int i=1;i<index;i++ )
    {
        if(data[i]==data[i-1]+2)
            a=data[i]-1;//断号
        if(data[i]==data[i-1])
            b=data[i];//重号
    }
    printf("%d %d",a,b);
    return 0;
}
题目8:翻硬币

小明正在玩一个“翻硬币”的游戏。
桌上放着排成一排的若干硬币。我们用 * 表示正面,用 o 表示反面(是小写字母,不是零)。
比如,可能情形是:**oo***oooo
如果同时翻转左边的两个硬币,则变为:oooo***oooo
现在小明的问题是:如果已知了初始状态和要达到的目标状态,每次只能同时翻转相邻的两个硬币,那么对特定的局面,最少要翻动多少次呢?
我们约定:把翻动相邻的两个硬币叫做一步操作,那么要求:
程序输入:
两行等长的字符串,分别表示初始状态和要达到的目标状态。每行的长度<1000
程序输出:
一个整数,表示最小操作步数
例如:
用户输入:
**********
o****o****
程序应该输出:
5
再例如:
用户输入:
*o**o***o***
*o***o**o***
程序应该输出:
1

//最简单的方法是找规律--分成段,每一段有两个不同,每一段最后一个不同所在的位置-第一个不同所在的位置的总和
//题目没有说明,就不要考虑无解的情况--有奇数个不同
#include <bits/stdc++.h>
using namespace std;

int main()
{
    string src;
    string target;
    getline(cin,src);
    getline(cin,target);
    int n=src.length();
    int ans=0;
    int start=-1;
    for(int i=0;i<n;i++)
    {
        if(src[i]!=target[i])
        {
            if(start==-1)//还没标记第一个位置
            {
                start=i;
            }else{//第一个位置已经标记,现在已经找到了第二个不同的位置
                ans=(i-start);
                start=-1;//便于接下来找第二段不同
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}
题目9:带分数

100 可以表示为带分数的形式:100 = 3 + 69258 / 714
还可以表示为:100 = 82 + 3546 / 197
注意特征:带分数中,数字1~9分别出现且只出现一次(不包含0)。
类似这样的带分数,100 有 11 种表示法。
题目要求:
从标准输入读入一个正整数N (N<1000*1000)
程序输出该数字用数码1~9不重复不遗漏地组成带分数表示的全部种数。
注意:不要求输出每个表示,只统计有多少表示法!
例如:
用户输入:
100
程序输出:
11
再例如:
用户输入:
105
程序输出:
6
资源约定:
峰值内存消耗 < 64M
CPU消耗 < 3000ms

#include<bits/stdc++.h>
using namespace std;
//生成1-9的全排列,先尝试在可能的位置插入+,再尝试在可能的位置插入/,验算等式,计数
//注意后边的两个串是可以整除的,涉及到整数的除法问题的思考
int parse(const char *arr,int pos,int len){
    int ans=0;
    int t=1;//基数从1开始
    for(int i=pos+len-1;i>=pos;i--)
    {
        ans+=(arr[i]-'0')*t;//单个字符转换为数字:-‘0’
        t*=10;
    }
    return ans;
}
int main()
{
    int ans=0;
    int n;
    scanf("%d",&n);
    string s="123456789";
    do{
            const char *str=s.c_str();
            for(int i=1;i<=7;i++)//i代表加号前的串的长度
            {
                /*string a=s.substr(0,i);//substr不能够反复使用,耗时比较厉害,会造成运行超时
                int inta=atoi(a.c_str());//字符串转整数
                */
                int inta=parse(str,0,i);
                if(inta>=n) break;

                for(int j=1;j<=9-i-1;j++)//代表加号和除号之间的串的长度
                {
                    /*string b=s.substr(i,j);
                    string c=s.substr(i+j);//除号后面的串
                    int intb=atoi(b.c_str());//atoi()函数将数字格式的字符串转换为整数类型。例如,将字符串“12345”转换成数字12345。
                    int intc=atoi(c.c_str());//int atoi(const char* str)
                    */
                    int intb=parse(str,i,j);
                    int intc=parse(str,i+j,9-i-j);
                    if(intb % intc==0&&(inta+intb/intc)==n){
                        ans++;
                    }

                }
            }
    }while(next_permutation(s.begin(),s.end()));
    cout<<ans<<endl;
    return 0;
}
题目10:连号区间数

小明这些天一直在思考这样一个奇怪而有趣的问题:
在1~N的某个全排列中有多少个连号区间呢?这里所说的连号区间的定义是:
如果区间[L, R] 里的所有元素(即此排列的第L个到第R个元素)递增排序后能得到一个长度为R-L+1的“连续”数列,则称这个区间连号区间。
当N很小的时候,小明可以很快地算出答案,但是当N变大的时候,问题就不是那么简单了,现在小明需要你的帮助。

输入格式:
第一行是一个正整数N (1 <= N <= 50000), 表示全排列的规模。
第二行是N个不同的数字Pi(1 <= Pi <= N), 表示这N个数字的某一全排列。
输出格式:
输出一个整数,表示不同连号区间的数目。

示例:
用户输入:
4
3 2 4 1
程序应输出:
7

用户输入:
5
3 4 2 5 1
程序应输出:
9

解释:
第一个用例中,有7个连号区间分别是:[1,1], [1,2], [1,3], [1,4], [2,2], [3,3], [4,4]
第二个用例中,有9个连号区间分别是:[1,1], [1,2], [1,3], [1,4], [1,5], [2,2], [3,3], [4,4], [5,5]

资源约定:
峰值内存消耗 < 64M
CPU消耗 < 5000ms

//连号区间内有序且连续例:连号区间123,-最大值-最小值等于R-L;非连号区间:124,-最大值-最小值不等于R-L
#include<bits/stdc++.h>
using namespace std;
int n;
int arr[50000];
int ans=0;
int main()
{
   scanf("%d",&n);
   for(int i=0;i<n;i++)
   {
       scanf("%d",&arr[i]);
   }
   for(int j=0;j<n;j++)
   {
       int max=arr[j];
       int min=arr[j];
       for(int i=j;i<n;i++)
       {
           if(arr[i]>max) max=arr[i];
           if(arr[i]<min) min=arr[i];
           if(i==j) ans++;
           else{
            if(max-min==i-j) ans++;//形成连号区间
           }

       }
   }
   cout<<ans<<endl;
   return 0;
}
上一篇下一篇

猜你喜欢

热点阅读