当前位置：首页 > article >正文

蓝桥杯赛前冲刺-枚举暴力和排序专题1（包含历年蓝桥杯真题和AC代码）

article 2024/12/23 9:26:29

连号区间数（第四届蓝桥杯省赛C++B组,第四届蓝桥杯省赛JAVAB组）

递增三元组（第九届蓝桥杯省赛C++B组,第九届蓝桥杯省赛JAVAB组）

特别数的和（第十届蓝桥杯省赛C++B组,第十届蓝桥杯省赛JAVAB组）

错误票据（第四届蓝桥杯省赛C++A/B组,第四届蓝桥杯省赛JAVAA/B组）

回文日期

连号区间数（第四届蓝桥杯省赛C++B组,第四届蓝桥杯省赛JAVAB组）

小明这些天一直在思考这样一个奇怪而有趣的问题：

在 1∼N1∼N 的某个排列中有多少个连号区间呢？

这里所说的连号区间的定义是：

如果区间 [L,R][L,R] 里的所有元素（即此排列的第 LL 个到第 RR 个元素）递增排序后能得到一个长度为 R−L+1R−L+1 的“连续”数列，则称这个区间连号区间。

当 NN 很小的时候，小明可以很快地算出答案，但是当 NN 变大的时候，问题就不是那么简单了，现在小明需要你的帮助。

输入格式

第一行是一个正整数 NN，表示排列的规模。

第二行是 NN 个不同的数字 PiPi，表示这 NN 个数字的某一排列。

输出格式

输出一个整数，表示不同连号区间的数目。

数据范围

1≤N≤100001≤N≤10000,
1≤Pi≤N1≤Pi≤N

输入样例1：

4
3 2 4 1

输出样例1：

输入样例2：

5
3 4 2 5 1

输出样例2：

样例解释

第一个用例中，有 77 个连号区间分别是：[1,1],[1,2],[1,3],[1,4],[2,2],[3,3],[4,4][1,1],[1,2],[1,3],[1,4],[2,2],[3,3],[4,4]
第二个用例中，有 99 个连号区间分别是：[1,1],[1,2],[1,3],[1,4],[1,5],[2,2],[3,3],[4,4],[5,5]

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 10010;
int a[N];
int main()
{
    int n;
    cin>>n;
    int ans=0;
    int r=0,l=10010;
    for (int i = 1; i <= n; i ++ )cin>>a[i];
    for(int i=1;i<=n;i++)
    {
         r=0,l=10010;
        for(int j=i;j<=n;j++){
            l=min(l,a[i]);
            r=max(r,a[j]);
            if(()==(r-l))ans++;
        }
    }
    cout<<ans<<endl;
    return 0;
}

递增三元组（第九届蓝桥杯省赛C++B组,第九届蓝桥杯省赛JAVAB组）

给定三个整数数组

A=[A1,A2,…AN]A=[A1,A2,…AN],
B=[B1,B2,…BN]B=[B1,B2,…BN],
C=[C1,C2,…CN]C=[C1,C2,…CN],

请你统计有多少个三元组 (i,j,k)(i,j,k) 满足：

1≤i,j,k≤N1≤i,j,k≤N
Ai<Bj<CkAi<Bj<Ck

输入格式

第一行包含一个整数 NN。

第二行包含 NN 个整数 A1,A2,…ANA1,A2,…AN。

第三行包含 NN 个整数 B1,B2,…BNB1,B2,…BN。

第四行包含 NN 个整数 C1,C2,…CNC1,C2,…CN。

输出格式

一个整数表示答案。

数据范围

1≤N≤1051≤N≤105,
0≤Ai,Bi,Ci≤1050≤Ai,Bi,Ci≤105

输入样例：

输出样例：

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 1e5+10;
int a[N],b[N],c[N],x[N];
int n;
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ )cin>>a[i];
    for (int i = 1; i <= n; i ++ )cin>>b[i];
    for (int i = 1; i <= n; i ++ )cin>>c[i];
    for(int i=1;i<=n;i++){
        int t=0;
        for(int j=1;j<=n;j++)
        {
            if(b[i]>a[j])t++;
        }
        x[i]=t;
    }
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(c[i]>b[j])ans+=x[j];
        }
    }
    cout<<ans<<endl;
    return 0;
    
}

特别数的和（第十届蓝桥杯省赛C++B组,第十届蓝桥杯省赛JAVAB组）

小明对数位中含有 2、0、1、92、0、1、9 的数字很感兴趣（不包括前导 00），在 11 到 4040 中这样的数包括 1、2、9、101、2、9、10 至 32、3932、39 和 4040，共 2828 个，他们的和是 574574。

请问，在 11 到 nn 中，所有这样的数的和是多少？

输入格式

共一行，包含一个整数 nn。

输出格式

共一行，包含一个整数，表示满足条件的数的和。

数据范围

1≤n≤100001≤n≤10000

输入样例：

输出样例：

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int check(int i)
{
    while(i)
    {
        int t=i%10;
        if(t==0||t==1||t==2||t==9)return true;
        i/=10;
    }
    return false;
}
int main()
{
    int n,ans=0;
    cin>>n;
    for(int i=1;i<=n;i++)
        if(check(i))ans+=i;
        
    cout<<ans<<endl;
    return 0;
}

错误票据（第四届蓝桥杯省赛C++A/B组,第四届蓝桥杯省赛JAVAA/B组）

某涉密单位下发了某种票据，并要在年终全部收回。

每张票据有唯一的ID号。

全年所有票据的ID号是连续的，但ID的开始数码是随机选定的。

因为工作人员疏忽，在录入ID号的时候发生了一处错误，造成了某个ID断号，另外一个ID重号。

你的任务是通过编程，找出断号的ID和重号的ID。

假设断号不可能发生在最大和最小号。

输入格式

第一行包含整数 NN，表示后面共有 NN 行数据。

接下来 NN 行，每行包含空格分开的若干个（不大于100个）正整数（不大于100000），每个整数代表一个ID号。

输出格式

要求程序输出1行，含两个整数 m,nm,n，用空格分隔。

其中，mm表示断号ID，nn表示重号ID。

数据范围

1≤N≤1001≤N≤100

输入样例：

2
5 6 8 11 9 
10 12 9

输出样例：

7 9

#include<iostream>
#include<algorithm>
#include <vector>
using namespace std;
const int N=105;
vector<int>a;
int main()
{
    int m=-1,n=-1,k=0;
    cin>>k;
    while(k--)
    {
        cin>>m
    }
    for(int i=0;i<k;i++)cin>>a[i];
    sort(a,a+k);
    for(int i=0;i<k;i++)cout<<a[i]<<endl;
    for(int i=0;i<k-1;i++)
    {
        if(a[i]==a[i+1])n=a[i];
        if((a[i]!=a[i+1])&&(a[i+1]-a[i]!=1))m=a[i];
    }
    cout<<m<<' '<<n<<endl;
    return 0;
}

回文日期

在日常生活中，通过年、月、日这三个要素可以表示出一个唯一确定的日期。

牛牛习惯用 88 位数字表示一个日期，其中，前 44 位代表年份，接下来 22 位代表月份，最后 22 位代表日期。

显然：一个日期只有一种表示方法，而两个不同的日期的表示方法不会相同。

牛牛认为，一个日期是回文的，当且仅当表示这个日期的 88 位数字是回文的。

现在，牛牛想知道：在他指定的两个日期之间（包含这两个日期本身），有多少个真实存在的日期是回文的。

一个 88 位数字是回文的，当且仅当对于所有的 ii(1≤i≤81≤i≤8) 从左向右数的第 ii 个数字和第 9−i9−i 个数字（即从右向左数的第 ii 个数字）是相同的。

例如：

对于 20162016 年 1111 月 1919 日，用 88 位数字 2016111920161119 表示，它不是回文的。
对于 20102010 年 11 月 22 日，用 88 位数字 2010010220100102 表示，它是回文的。
对于 20102010 年 1010 月 22 日，用 88 位数字 2010100220101002 表示，它不是回文的。

输入格式

输入包括两行，每行包括一个 88 位数字。

第一行表示牛牛指定的起始日期 date1date1，第二行表示牛牛指定的终止日期 date2date2。保证 date1date1 和 date2date2 都是真实存在的日期，且年份部分一定为 44 位数字，且首位数字不为 00。

保证 date1date1 一定不晚于 date2date2。

输出格式

输出共一行，包含一个整数，表示在 date1date1 和 date2date2 之间，有多少个日期是回文的。

输入样例：

20110101
20111231

输出样例：

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int month[13]={0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
bool check(int data)
{
    int y=data/10000;
    int m=data%10000/100;
    int d=data%100;
    if(m<=0||m>12)return false;
    if(d==0||m!=2&&d>month[m])return false;
    if(m==2){
        bool leap=((y%400==0)||(y%100!=0&&y%4==0));
        if(leap==true&&d>29)return false;
        if(leap==false&&d>28)return false;
    }
    return true;
}
int main()
{
    int d1,d2;
    cin>>d1>>d2;
    int ans=0;
    for(int i=1000;i<100000;i++)
    {
        int data=i,x=i;
        for(int i=0;i<4;i++)data=data*10+x%10,x/=10;
        if(d1<=data&&data<=d2&&check(data))ans++;
    }
    cout<<ans<<endl;
    return 0;
}

查看全文

http://www.kler.cn/a/6548.html