2025/4/23 心得

第一题。

习题2.1.9 最少翻转次数

题目描述

给定一个01序列，小x每次可以翻转一个元素，即将该元素从0变1或者从1变0。

现在小x希望最终序列是不下降序列，即不会存在相邻两个元素，左边元素的值比右边元素的值大。

请你帮小x求最小翻转次数并能让序列满足不下降的条件。

输入格式

第一行输入一个数n，其中1≤n≤200000；

第二行输入一个由‘0’和‘1’组成的字符串

输出格式

输出一个非负整数，表示翻转次数

样例数据

input

6010110

Copy

output

2

Copy

数据规模与约定

数据范围如题目描述

时间限制：1 \text {s}1s

空间限制：256 \text {MB}256MB

这道题其实求的就是好零的个数。

合和一的个数，一共需要修改的个数。然后加起来求最小值就行了。

但是注意零的个数需要继逆去求。

我因为他是逆气球

，所以说呢球前缀和的时候应该是加

代码如下，

#include<bits/stdc++.h>
using namespace std;
int a[200010],b[200010],c[200010],n,m=99999,q; 
string s;
int main()
{
    freopen("reverse.in","r",stdin);
    freopen("reverse.out","w",stdout);
    cin>>n>>s;
    for(int i=0;i<n;i++)
    {
        if(s[i]=='1')
        a[i]=a[i-1]+1;
        else
        a[i]=a[i-1];
    }
        for(int i=n-1;i>=0;i--)
    {
        if(s[i]=='0')
        b[i]=b[i+1]+1;
        else
        b[i]=b[i+1];
    }
        for(int i=0;i<n;i++)
    {
        m=min(m,a[i-1]+b[i+1]);
    }
    cout<<m;
    return 0;
}

第二题

习题2.1.10 K的倍数

蒜头君定义了一种数叫 suan 数，如果一个数 xx 是 suan 数，那么它必定能被 kk 整除，每次给定一个区间 (l,r](l,r]，保证 l < rl<r，求该区间中有多少个数是 suan 数，其中 kk 为给定的数。

输入格式

第一行两个正整数 n,kn,k，表示有 nn 个询问，kk 意义见题面。

接下来 nn 行，每行两个正整数 l,rl,r，表示一个询问。

输出格式

对于每一个询问，输出一行，表示答案。

样例

输入样例1：

3 51 11 103 15

Copy

输出样例1：

023

Copy

样例解释1：

在该样例中，5,10,15,20,...5,10,15,20,... 为 suan 数。

数据范围与提示

 这道题其实在我以前题解里边儿写过。

追求的是最后一个韩K的量再减第一个含key的量。

但是呢在写的时候发现了一个错误，我没有加换行。

修改过后代码如下，

#include<bits/stdc++.h>
using namespace std;
long long a,n;
int main()
{
    freopen("number.in","r",stdin);
    freopen("number.out","w",stdout);
    cin>>n>>a;
    for(int i=1;i<=n;i++)
    {
        int b,c;
        cin>>b>>c;
        cout<<(c/a)-(b/a)<<endl;
    }
    return 0;
}

第三题。

习题2.1.14 走迷宫

题目描述

牛老师现在在一个迷宫里。

迷宫为nn行mm列的格子，迷宫里的格子分两类：

• 障碍物点，不可以通过，用 ‘#’表示，并遮挡住人的视线。
• 无障碍物点，可以通过，用'.'表示，不能遮挡人的视线。

现在牛老师想知道，她站在迷宫中的某个位置，上下左右四个方向，最多可以看到多少个没有障碍物的格子。

当然，牛老师不能站在障碍物上。

输入格式

第一行两个整数n,mn,m，表示迷宫的大小。

接下来nn行，每行mm个字符，表示迷宫每个格子的状态。

保证字符只会有'#'或'.'两种字符。

输出格式

一个整数，表示答案。

样例数据

input

4 6#..#.......#....#.#.#...

Copy

output

8

Copy

牛老师站在第2行第2列的位置，一共可以看到8个格子，包含自己站的位置。

input

8 8..#...#.....#...##........###..#...#..#.##....#.#...#...###.#..#

Copy

output

13

Copy

数据规模与约定

1 \leq n,m \leq 20001≤n,m≤2000

时间限制：1 \text {s}1s

空间限制：256 \text {MB}256MB

这道题其实就是二维数组将模拟

就是求出除了障碍物以外的每一个点。上下左右的值。和他自己本身加起来。

的值最大。然后再输出它上下左右的点数加自己。

但我第一次写的时候把if循环==写成了=找了好久

，句中代码如下。

#include<bits/stdc++.h>
using namespace std;
int n,m,b[2010][2010];
char a[2010][2010];
int c[2010][2010],d[2010][2010];
int e[2010][2010],ans,sum=-999999,ans1,sum1=-999999;
int main()
{
    freopen("maze.in","r",stdin);
    freopen("maze.out","w",stdout);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>a[i][j];
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(a[i][j]=='.')
            {
                b[i][j]=b[i-1][j]+1;
                c[i][j]=c[i][j-1]+1;
            }
        }
    }
        for(int i=n;i>=1;i--)
    {
        for(int j=m;j>=1;j--)
        {
            if(a[i][j]=='.')
            {
                d[i][j]=d[i+1][j]+1;
                e[i][j]=e[i][j+1]+1;
            }
        }
    }
        for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
        ans=b[i][j]+c[i][j]+d[i][j]+e[i][j]-3;
        sum=max(sum,ans);
        }
    }
    cout<<sum;
    return 0;
}