蓝桥杯小白打卡第二天

789. 数的范围

题目描述

给定一个按照升序排列的长度为 $n$ 的整数数组，以及 $q$ 个查询。

对于每个查询，返回一个元素 $k$ 的起始位置和终止位置（位置从 $0$ 开始计数）。

如果数组中不存在该元素，则返回 $-1-1$。

输入格式

• 第一行包含整数 $n$ 和 $q$，表示数组长度和询问个数。
• 第二行包含 $n$ 个整数（均在 $1\sim 10000$ 范围内），表示完整数组。
• 接下来 $q$ 行，每行包含一个整数 $k$，表示一个询问元素。

输出格式

共 $q$ 行，每行包含两个整数，表示所求元素的起始位置和终止位置。

如果数组中不存在该元素，则返回 $-1-1$。

数据范围

• $1\le n\le 100000$
• $1\le q\le 10000$
• $1\le k\le 10000$

输入样例

6 3
1 2 2 3 3 4
3
4
5

输出样例

3 4
5 5
-1 -1

题目解释

首先，面对2分的问题，我们要先找到作用的区间。本道题目的区间为左区间为0，右区间为N-1。随后，我们需要找到一个可以用来划分区间的条件。在这里，我们让mid值大于等于X，从左向右得到满足条件的最后一个值，从而得到大于或等于S值的区间的左端点。随后，我们在此基础之上再次进行二分，L值即为刚才所得的左端点，R值为原先的N-1。随后，我们根据mid的值小于等于X，从左向右得到满足条件的最后一个点，从而得到结果

代码

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


const int N=1e5+10;
int n,q,a[N];

int main(){
    cin>>n>>q;
    for(int i=0;i<n;i++) scanf("%d",&a[i]);//输入
    while(q--){
        int x;
        cin>>x;
        int l=0,r=n-1;
        while(l<r){
            int mid=l+r>>1;
            if(a[mid]>=x) r=mid;//从右边向左，得到满足条件的最后一个
            else l=mid+1;
        }//得到大于或等于x值的区间的左端点
        if(a[l]==x){
            cout<<l<<" ";
            r=n-1;//回复现场
            while(l<r){//在之前判断的基础之上再进行计算，减少了次数
                int mid=l+r+1>>1;
                if(a[mid]<=x) l=mid;
                else r=mid-1;
            }
            cout<<r<<endl;
        }
        else cout<<-1<<" "<<-1<<endl;
    }
    
    
    return 0;
}

95. 费解的开关

游戏规则

1. 灯的布局：有25盏灯排成一个5×5的方形，每盏灯都有一个开关，游戏者可改变其状态。
2. 操作及连锁反应：每一步，游戏者改变某一个灯的状态，与之上下左右相邻的灯也要相应地改变状态。我们用数字1表示一盏开着的灯，用数字0表示关着的灯。例如，对于状态：

10111
01101
10111
10000
11011

改变最左上角的灯的状态后将变成：

01111
11101
11011
10000
11011

再改变正中间的灯后状态将变成：

01111
11001
11001
10100
11011

任务要求

1. 输入格式：
   • 第一行输入正整数n，代表数据中共有n个待解决的游戏初始状态。
   • 以下若干行数据分为n组，每组数据有5行，每行5个字符。每组数据描述了一个游戏的初始状态。各组数据间用一个空行分隔。
2. 输出格式：
   • 一共输出n行数据，每行有一个小于等于6的整数，它表示对于输入数据中对应的游戏状态最少需要几步才能使所有灯变亮。
   • 对于某一个游戏初始状态，若6步以内无法使所有灯变亮，则输出-1。
3. 数据范围：0 < n ≤ 500

输入输出样例

1. 输入样例：

3
00111
01011
10001
11010
11100

11101
11101
11110
11111
11111

01111
11111
11111
11111
11111

2. 输出样例：

3
2
-1

题目思路

首先要明白每一行（除去第一行）的灯的亮灭可以从下一行的灯的亮灭来决定，针对第一行，每一盏灯都可以选择是否按下开关，所以这是一个指数型枚举的问题（指数型枚举是指从n个不同元素中，不考虑元素之间的顺序，将所有可能的子集都列举出来的过程。），随后第一行每个开关都可以选择是否打开，所以对于每一个问题我们是有2^5=32种情况，对于每一种情况我们的第一行都是不同的开关选择，对应着唯一的下面行（除去最后一行）的开关选择，到了最后一行，如果依然存在没有被点亮的灯，那么则认为这个题目无法被满足

代码1

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;
const int N=6;
int g[N][N],backup[N][N];//由于每一个题目都对应着32种情况（32刚好满足32个不同的5位二进制数字），所以我们要提前做一个备份

int dx[5]={0,0,-1,0,1},dy[5]={0,1,0,-1,0};


// 翻转(x, y)位置的灯及其周围四个灯的状态
void turn(int x, int y) {
    for (int i = 0; i < 5; i++) {
        int nx = x + dx[i], ny = y + dy[i];
        if (nx >= 0 && nx < 5 && ny >= 0 && ny < 5) {
            g[nx][ny] ^= 1; // 使用异或操作来翻转状态
        }
    }
}

int main(){
    int n;//一种有n种需要被解决的问题
    cin>>n;
    while(n--){
        for(int i=0;i<5;i++){
            for(int j=0;j<5;j++){
                scanf("%1d",&g[i][j]);//特别注意这个地方是1d，因为题目所给数字是链接在一起的，所以需要用1d来用来区分，当然这个地方也可以使用char数组
            }
        }//完成输入
        //接下来进行第一行的开关，对于这一个待解决的问题，有32种情况，那么我们在最开始先设置一个答案值为6，将这个值与每一种情况所得结果进行对比，取最小值
        int ans=7;
        for(int i=0;i<32;i++){
            //按照5位二进制数，进行每一种情况
            //情况一：
            //首先完成备份
            int res=0;//创建一个临时存储的变量,该变量为局部变量，必须赋值
            memcpy(backup,g,sizeof g);
            for(int j=0;j<5;j++){
                if((i>>j)&1==1){
                    turn(0,4-j);
                    res++;
                }//如果这一位&的结果为1，那么就要进行开关的转换
            }//完成第一行开关
            
            for(int h=0;h<4;h++){
                for(int l=0;l<5;l++){
                    if(g[h][l]==0){
                      turn(h+1,l);
                      res++;
                    } 
                }//遍历除去最后一行的所有，如果发现为0，则在下一行的该位置打开开关
            }
            
            //接下来要对结果进行检验，如果最后一行依然存在为0的情况，那么就证明无法满足题目条件
            bool flag=true;
            for(int l=0;l<5;l++){
                if(g[4][l]==0) flag=false;
            }
            if(flag) ans=min(ans,res);//如果可以，就把两个值中的最小值赋给ans
            //最后要回复现场
            memcpy(g,backup,sizeof g);
        }
        //完成了所有32种情况的遍历
        if(ans>6) cout<<"-1"<<endl;
        else cout<<ans<<endl;
    }
    
    
    return 0;
}

代码2（区别在于读取数据的方式不同，同时也是y总代码）

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 6;

char g[N][N], backup[N][N];
int dx[5] = {-1, 0, 1, 0, 0}, dy[5] = {0, 1, 0, -1, 0};

void turn(int x, int y)
{
    for (int i = 0; i < 5; i ++ )
    {
        int a = x + dx[i], b = y + dy[i];
        if (a < 0 || a >= 5 || b < 0 || b >= 5) continue;   // 在边界外，直接忽略即可
        g[a][b] ^= 1;
    }
}

int main()
{
    int T;
    cin >> T;
    while (T -- )
    {
        for (int i = 0; i < 5; i ++ ) cin >> g[i];

        int res = 10;
        for (int op = 0; op < 32; op ++ )
        {
            memcpy(backup, g, sizeof g);
            int step = 0;
            for (int i = 0; i < 5; i ++ )
                if (op >> i & 1)
                {
                    step ++ ;
                    turn(0, i);
                }

            for (int i = 0; i < 4; i ++ )
                for (int j = 0; j < 5; j ++ )
                    if (g[i][j] == '0')
                    {
                        step ++ ;
                        turn(i + 1, j);
                    }

            bool dark = false;
            for (int i = 0; i < 5; i ++ )
                if (g[4][i] == '0')
                {
                    dark = true;
                    break;
                }

            if (!dark) res = min(res, step);
            memcpy(g, backup, sizeof g);
        }

        if (res > 6) res = -1;

        cout << res << endl;
    }

    return 0;
}

1208. 翻硬币

问题描述

小明正在玩一个“翻硬币”的游戏。桌上放着排成一排的若干硬币。我们用 * 表示正面，用 o 表示反面（是小写字母，不是零）。

例如，可能情形是：**oo***oooo。如果同时翻转左边的两个硬币，则变为：oooo***oooo。

现在小明的问题是：如果已知了初始状态和要达到的目标状态，每次只能同时翻转相邻的两个硬币，那么对特定的局面，最少要翻动多少次呢？

我们约定：把翻动相邻的两个硬币叫做一步操作。

输入格式

两行等长的字符串，分别表示初始状态和要达到的目标状态。

输出格式

一个整数，表示最小操作步数。

数据范围

输入字符串的长度均不超过 100。数据保证答案一定有解。

输入输出样例

输入样例 1

**********
o****o****

输出样例 1

5

输入样例 2

*o**o***o***
*o***o**o***

输出样例 2

1

题目思路

和上一个题目费解的开关类似，都是改变一个的值，同时会改动其他的值

是费解的开关的简易版

题目代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N=110;
char o[N],a[N];
int ans;

void turn(int x){
    if(o[x]=='*') o[x]='o';
    else o[x]='*';
}

int main(){
    cin>>o>>a;//接受起始状态和目标状态
    int len=strlen(o);
    for(int i=0;i<len-1;i++){
        if(o[i]==a[i]) continue;
        turn(i),turn(i+1);
        ans++;
    }
    if(a[len-1]==o[len-1]) cout<<ans;
    
    return 0;
}