头像

晨曦时雨




离线:12小时前



晨曦时雨
15小时前

题目描述

旋转是图像处理的基本操作,在这个问题中,你需要将一个图像逆时针旋转 90 度。

计算机中的图像表示可以用一个矩阵来表示,为了旋转一个图像,只需要将对应的矩阵旋转即可。

输入格式

输入的第一行包含两个整数 n,m,分别表示图像矩阵的行数和列数。

接下来 n 行每行包含 m 个整数,表示输入的图像。

输出格式

输出 m 行,每行包含 n 个整数,表示原始矩阵逆时针旋转 90 度后的矩阵。

数据范围

$1≤n,m≤1,000$

矩阵中的数都是不超过 1000 的非负整数。

输入样例:

2 3
1 5 3
3 2 4

输出样例:

3 4
5 2
1 3

思路

直接一列一列地输出就行了

我们拿输入样例作为例子,每个点的坐标如下↓

(1,1) (1,2) (1,3)

(2,1) (2,2) (2,3)

而输出的时候,坐标如下↓

(1,3)(2,3)

(1,2)(2,2)

(1,1)(2,1)

所以我们输入的时候,每行点的纵坐标不变,横坐标递增:

for(int i=1;i<=n;i++)
{
    for(int j=1;j<=m;j++)
    {
        scanf("%d",&q[i][j]);
    }
}

而输出的时候,每行点的横坐标不变,纵坐标递增:

for(int i=m;i>0;i--)
{
    for(int j=1;i<=n;i++)
    {
        printf("%d ",q[j][i]);//注意这里是q[j][i]
    }
}

代码

#include<iostream>
#include<cstdio>
using namespace std;
int n,m;
int q[1010][1010];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&q[i][j]);
        }
    }
    for(int i=m;i>0;i--)
    {
        for(int j=1;j<=n;j++)
        {
            printf("%d ",q[j][i]);
        }
        printf("\n");
    }
    return 0;
}


活动打卡代码 AcWing 3212. 图像旋转

晨曦时雨
15小时前

题目描述

旋转是图像处理的基本操作,在这个问题中,你需要将一个图像逆时针旋转 90 度。

计算机中的图像表示可以用一个矩阵来表示,为了旋转一个图像,只需要将对应的矩阵旋转即可。

输入格式

输入的第一行包含两个整数 n,m,分别表示图像矩阵的行数和列数。

接下来 n 行每行包含 m 个整数,表示输入的图像。

输出格式

输出 m 行,每行包含 n 个整数,表示原始矩阵逆时针旋转 90 度后的矩阵。

数据范围

$1≤n,m≤1,000$

矩阵中的数都是不超过 1000 的非负整数。

输入样例:

2 3
1 5 3
3 2 4

输出样例:

3 4
5 2
1 3

思路

直接一列一列地输出就行了

我们拿输入样例作为例子,每个点的坐标如下↓

(1,1) (1,2) (1,3)

(2,1) (2,2) (2,3)

而输出的时候,坐标如下↓

(1,3)(2,3)

(1,2)(2,2)

(1,1)(2,1)

所以我们输入的时候,每行点的纵坐标不变,横坐标递增:

for(int i=1;i<=n;i++)
{
    for(int j=1;j<=m;j++)
    {
        scanf("%d",&q[i][j]);
    }
}

而输出的时候,每行点的横坐标不变,纵坐标递增:

for(int i=m;i>0;i--)
{
    for(int j=1;i<=n;i++)
    {
        printf("%d ",q[j][i]);//注意这里是q[j][i]
    }
}

代码

#include<iostream>
#include<cstdio>
using namespace std;
int n,m;
int q[1010][1010];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&q[i][j]);
        }
    }
    for(int i=m;i>0;i--)
    {
        for(int j=1;j<=n;j++)
        {
            printf("%d ",q[j][i]);
        }
        printf("\n");
    }
    return 0;
}



晨曦时雨
17小时前

题目描述

某股票交易所请你编写一个程序,根据开盘前客户提交的订单来确定某特定股票的开盘价和开盘成交量。

该程序的输入由很多行构成,每一行为一条记录,记录可能有以下几种:

  1. buy p s 表示一个购买股票的买单,每手出价为 p,购买股数为 s。
  2. sell p s 表示一个出售股票的卖单,每手出价为 p,出售股数为 s。
  3. cancel i 表示撤销第 i 行的记录。被撤销的记录一定是前两种

如果开盘价为p0,则系统可以将所有出价至少为 p0 的买单和所有出价至多为 p0 的卖单进行匹配。

因此,此时的开盘成交量为出价至少为 p0 的买单的总股数和所有出价至多为 p0 的卖单的总股数之间的较小值。

你的程序需要确定一个开盘价,使得开盘成交量尽可能地大。

如果有多个符合条件的开盘价,你的程序应当输出最高的那一个。

输入格式

输入数据有任意多行,每一行是一条记录。

保证输入合法。股数为不超过 108 的正整数,出价为精确到恰好小数点后两位的正实数,且不超过 10000.00。

输出格式

你需要输出一行,包含两个数,以一个空格分隔。

第一个数是开盘价,第二个是此开盘价下的成交量。

开盘价需要精确到小数点后恰好两位。

数据范围

对于 100% 的数据,输入的行数不超过 5000。

$0<p≤10^4$

$1≤s≤10^8$

数据保证一定存在某个开盘价使得成交量不为 0。
保证输入合法。数据保证 cancel 指令只会取消 buysell 记录。

输入样例:

buy 9.25 100
buy 8.88 175
sell 9.00 1000
buy 9.00 400
sell 8.92 400
cancel 1
buy 100.00 50

输出样例:

9.00 450

思路

(本人只是一个蒟蒻,所以在这里就直接写暴力枚举的了,想看前缀和+双指针的小伙伴可以看一下y总的代码)

为了方便表示,我们可以定义一个结构体,每次输入的时候,判断输入的是买还是卖,分别进行处理】

如果输入的是撤销,那么就把撤销的句子标记一下(这句话也要标记,因为到后面我们要对没有标记的句子进行处理)

根据题意,我们将大于p0的买股加到一起,再把小于p0的卖股加到一起,取一个最小值

然后再定义一个初值为0的两个数,方便比较

注意1:在最后比较的时候,大于和等于的情况要分开写,因为&&的运算及比||高,结果不一样的

注意2:本题s的数据范围是$1≤s≤10^8$,所以可能爆int,要用long long

代码

#include<iostream>
#include<cstdio>
using namespace std;
int n;
struct record
{
    int type;
    double p;
    int s;
    bool is_del;
}d[5010];
int main()
{
    string type;
    while(cin>>type)
    {
        if(type=="buy")
        {
            double p;
            int s;
            cin>>p>>s;
            d[++n]={1,p,s};
        }
        else if(type=="sell")
        {
            double p;
            int s;
            cin>>p>>s;
            d[++n]={2,p,s};
        }
        else
        {
            int id;
            cin>>id;
            d[id].is_del=1;
            d[++n].is_del=1;
        }
    }
    double resp=0;
    long long  ress=0;
    for(int i=1;i<=n;i++)
    {
        if(d[i].is_del==0)
        {
            double p=d[i].p;
            long long  s1=0,s2=0;
            for(int j=1;j<=n;j++)
            {
                if(d[j].is_del==0)
                {
                    if(d[j].type==1&&d[j].p>=p) s1+=d[j].s;
                    else if(d[j].type==2&&d[j].p<=p) s2+=d[j].s;
                }
            }
            long long  t=min(s1,s2);
            if(t>ress||t==ress&&p>resp)
                resp=p,ress=t;
        }
    }
    printf("%.2lf %lld\n", resp, ress);
    return 0;
}


活动打卡代码 AcWing 3209. 集合竞价

晨曦时雨
17小时前

题目描述

某股票交易所请你编写一个程序,根据开盘前客户提交的订单来确定某特定股票的开盘价和开盘成交量。

该程序的输入由很多行构成,每一行为一条记录,记录可能有以下几种:

  1. buy p s 表示一个购买股票的买单,每手出价为 p,购买股数为 s。
  2. sell p s 表示一个出售股票的卖单,每手出价为 p,出售股数为 s。
  3. cancel i 表示撤销第 i 行的记录。被撤销的记录一定是前两种

如果开盘价为p0,则系统可以将所有出价至少为 p0 的买单和所有出价至多为 p0 的卖单进行匹配。

因此,此时的开盘成交量为出价至少为 p0 的买单的总股数和所有出价至多为 p0 的卖单的总股数之间的较小值。

你的程序需要确定一个开盘价,使得开盘成交量尽可能地大。

如果有多个符合条件的开盘价,你的程序应当输出最高的那一个。

输入格式

输入数据有任意多行,每一行是一条记录。

保证输入合法。股数为不超过 108 的正整数,出价为精确到恰好小数点后两位的正实数,且不超过 10000.00。

输出格式

你需要输出一行,包含两个数,以一个空格分隔。

第一个数是开盘价,第二个是此开盘价下的成交量。

开盘价需要精确到小数点后恰好两位。

数据范围

对于 100% 的数据,输入的行数不超过 5000。

$0<p≤10^4$

$1≤s≤10^8$

数据保证一定存在某个开盘价使得成交量不为 0。
保证输入合法。数据保证 cancel 指令只会取消 buysell 记录。

输入样例:

buy 9.25 100
buy 8.88 175
sell 9.00 1000
buy 9.00 400
sell 8.92 400
cancel 1
buy 100.00 50

输出样例:

9.00 450

思路

(本人只是一个蒟蒻,所以在这里就直接写暴力枚举的了,想看前缀和+双指针的小伙伴可以看一下y总的代码)

为了方便表示,我们可以定义一个结构体,每次输入的时候,判断输入的是买还是卖,分别进行处理】

如果输入的是撤销,那么就把撤销的句子标记一下(这句话也要标记,因为到后面我们要对没有标记的句子进行处理)

根据题意,我们将大于p0的买股加到一起,再把小于p0的卖股加到一起,取一个最小值

然后再定义一个初值为0的两个数,方便比较

注意1:在最后比较的时候,大于和等于的情况要分开写,因为&&的运算及比||高,结果不一样的

注意2:本题s的数据范围是$1≤s≤10^8$,所以可能爆int,要用long long

代码

#include<iostream>
#include<cstdio>
using namespace std;
int n;
struct record
{
    int type;
    double p;
    int s;
    bool is_del;
}d[5010];
int main()
{
    string type;
    while(cin>>type)
    {
        if(type=="buy")
        {
            double p;
            int s;
            cin>>p>>s;
            d[++n]={1,p,s};
        }
        else if(type=="sell")
        {
            double p;
            int s;
            cin>>p>>s;
            d[++n]={2,p,s};
        }
        else
        {
            int id;
            cin>>id;
            d[id].is_del=1;
            d[++n].is_del=1;
        }
    }
    double resp=0;
    long long  ress=0;
    for(int i=1;i<=n;i++)
    {
        if(d[i].is_del==0)
        {
            double p=d[i].p;
            long long  s1=0,s2=0;
            for(int j=1;j<=n;j++)
            {
                if(d[j].is_del==0)
                {
                    if(d[j].type==1&&d[j].p>=p) s1+=d[j].s;
                    else if(d[j].type==2&&d[j].p<=p) s2+=d[j].s;
                }
            }
            long long  t=min(s1,s2);
            if(t>ress||t==ress&&p>resp)
                resp=p,ress=t;
        }
    }
    printf("%.2lf %lld\n", resp, ress);
    return 0;
}


活动打卡代码 AcWing 3208. Z字形扫描

晨曦时雨
18小时前

题目描述

在图像编码的算法中,需要将一个给定的方形矩阵进行 Z 字形扫描(Zigzag Scan)。

给定一个 n×n 的矩阵,Z 字形扫描的过程如下图所示:

BC9AB31D-0306-4912-A628-9E617C74A929.png

对于下面的 4×4 的矩阵,

1 5 3 9
3 7 5 6
9 4 6 4
7 3 1 3

对其进行 Z 字形扫描后得到长度为 16 的序列:1 5 3 9 7 3 9 5 4 7 3 6 6 4 1 3。

请实现一个 Z 字形扫描的程序,给定一个 n×n 的矩阵,输出对这个矩阵进行 Z 字形扫描的结果。

输入格式

输入的第一行包含一个整数 n,表示矩阵的大小。

输入的第二行到第 n+1 行每行包含 n 个正整数,由空格分隔,表示给定的矩阵。

输出格式

输出一行,包含 n×n 个整数,由空格分隔,表示输入的矩阵经过 Z 字形扫描后的结果。

数据范围

1 ≤ n ≤ 500,
矩阵元素为不超过 1000 的正整数。

输入样例:

4
1 5 3 9
3 7 5 6
9 4 6 4
7 3 1 3

输出样例:

1 5 3 9 7 3 9 5 4 7 3 6 6 4 1 3

写法一 找规律

思路

可以把整个方格分成单数行和双数行,单数行向上、双数行向下进行输出,当然要确保不越界

单数行横纵坐标相加不是2的倍数,双数行的横纵坐标相加是2的倍数

实际上在这个方格阵中,左上角是一种情况,右下角是一种情况,但是如果我们将这个方格阵补全↓
1614326815870_BC34186C-D89A-4e77-8671-3D7A38CA9A74.png
我们就只要考虑左上角那一种情况,然后输出方格阵范围中的数就行了

注意:此题的输入数据范围最大为250 000,数据一旦超过100 000,就尽量使用scanf和printf,可以提高速度

c++代码

#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
    int a[510][510],n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            scanf("%d",&a[i][j]);
        }
    }
    for(int i=2;i<=n*2;i++)
    {
        if(i%2)//如果为双数行
        {
            for(int j=1;j<i;j++)//j为行,从小到大意味着从上到下输出
            {
                if(j>=1&&j<=n&&i-j>=1&&i-j<=n)
                    printf("%d ",a[j][i-j]);
            }
        }
        else//如果为单数行
        {
            for(int j=i-1;j>=1;j--)//j为行,从大到小意味着从下到上输出
            {
                if(j>=1&&j<=n&&i-j>=1&&i-j<=n)
                    printf("%d ",a[j][i-j]);
            }
        }
    }
    return 0;
}

写法二 直接暴力枚举

(做好心理准备,会很长)

这种写法是我自己想出来的,一共有四种方向:0代表向右,1代表向左下,2代表向下,3代表向右下
d用来存储这个格子是通过哪种方式(哪个方向)走过来的,起点默认为从3走过来(因为通过画图可以发现,大部分向右走的格子都是从3过来的)
然后……就是画图,画图可以得到各个格子对应的d,然后找从哪个方向走过来的格子应该走向那个方向
e.g.
4x4的格子:
3->0->1->2->3->3->0->1->1->1->0->3->3->2->1->0
5x5的格子:
3->0->1->2->3->3->0->1->1->1->2->3->3->3->3->2->1->1->0->3->3->2->1->0

由此可得:
d为0的格子可能向1,3的方向走
d为1的格子可能向0,1,2的方向走
d为2的格子可能向1,3的方向走
d为3的格子可能向0,2,3的方向走

然后进行一系列的判断(详细判断见下代码)

#include<iostream>
using namespace std;
int a[1010][1010];
int main()
{
    int n,x=1,y=1;
    cin>>n;
    int dx[4]={0,1,1,-1},dy[4]={1,-1,0,1},d=3;//四个方向及d的初值
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cin>>a[i][j];//输入
        }
    }
    for(int i=1;i<=n*n;i++)
    {
        cout<<a[x][y]<<' ';
        if(d==3)//如果是从3过来的
        {
            if(x==1&&y!=n)//在最上面一行,y!=n表示不在最左边的一列
            {
                x+=dx[0];//向0的方向走
                y+=dy[0];
                d=0;
            }
            else if(y==n)//如果在最左边一列
            {
                x+=dx[2];//向2的方向走
                y+=dy[2];
                d=2;
            }
            else//因为只有向0,2,3的方向走,所以接下来只能向3走
            {
                x+=dx[3];
                y+=dy[3];
                d=3;
            }
        }
        else if(d==0)//如果是从0过来的
        {
            if(x==1)//如果在最上面的一行
            {
                x+=dx[1];//向1的方向走
                y+=dy[1];
                d=1;
            }
            else if(x==n)//如果在最下面一行
            {
                x+=dx[3];//向3的方向走
                y+=dy[3];
                d=3;
            }
        }
        else if(d==1)//如果是从1过来的
        {
            if(y==1&&x!=n)//在最左边一列
            {
                x+=dx[2];//向2的方向走
                y+=dy[2];
                d=2;
            }
            else if(x==n)//在最下面一行
            {
                x+=dx[0];//向0的方向走
                y+=dy[0];
                d=0;
            }
            else//排除两种,接下来只能向1的方向走
            {
                x+=dx[1];
                y+=dy[1];
                d=1;
            }
        }
        else if(d==2)//如果是从2过来的
        {
            if(y==1)//如果在最左边一行
            {
                x+=dx[3];//向3的方向走
                y+=dy[3];
                d=3;
            }
            else if(y==n)//如果在最右边一列
            {
                x+=dx[1];//向1的方向走
                y+=dy[1];
                d=1;
            }
        }
    }
    return 0;
}

写法二纯属自己想的,不喜勿喷O(∩_∩)O~



活动打卡代码 AcWing 3207. 门禁系统

晨曦时雨
19小时前

题目描述

涛涛最近要负责图书馆的管理工作,需要记录下每天读者的到访情况。

每位读者有一个编号,每条记录用读者的编号来表示。

给出读者的来访记录,请问每一条记录中的读者是第几次出现。

输入格式

输入的第一行包含一个整数 n,表示涛涛的记录条数。

第二行包含 n 个整数,依次表示涛涛的记录中每位读者的编号。

输出格式

输出一行,包含 n 个整数,由空格分隔,依次表示每条记录中的读者编号是第几次出现。

数据范围

1≤n≤1000,

读者的编号为不超过 n 的正整数。

输入样例:

5
1 2 1 1 3

输出样例:

1 1 2 3 1

思路

这题数据范围比较小,用什么方法都可以做,比较好写的做法是哈希表,直接用数组当做哈希表

如果想知道当前数x出现的次数,就是s[x]出现的次数

代码

#include<iostream>
using namespace std;
const int N=1010;
int n;
int s[N][N];
int main()
{
    cin>>n;
    while(n--)
    {
        int x;
        s[x]++;
        cout<<s[x]<<' ';
    }
    return 0;
}



晨曦时雨
19小时前

题目描述

我们把一个数称为有趣的,当且仅当:

1.它的数字只包含 0,1,2,3,且这四个数字都出现过至少一次。

2.所有的 0 都出现在所有的 1 之前,而所有的 2 都出现在所有的 3 之前。

3.最高位数字不为 0。

因此,符合我们定义的最小的有趣的数是 2013。

除此以外,4 位的有趣的数还有两个:2031 和 2301。

请计算恰好有 n 位的有趣的数的个数。

由于答案可能非常大,只需要输出答案除以 109+7 的余数。

输入格式

输入只有一行,包括恰好一个正整数 n。

输出格式

输出只有一行,包括恰好 n 位的整数中有趣的数的个数除以 109+7 的余数。

数据范围

4≤n≤1000

输入样例:

4

输出样例:

3

思路(数学解法)

一共要放n位,0,1是有限制的,2,3是有限制的,但是0,1和2,3之间是没有任何限制的,所以我们在放的时候,可以先放0,1再放2,3。先考虑那些未知放0,1,然后剩余的位置放2,3

当0,1的个数不同的时候,方案一定不一样:(因为0,1每个数至少出现一次,所以从2开始枚举)

当0,1有2个的时候,2,3有n-2个

当0,1有3个的时候,2,3有n-3个

当0,1有4个的时候,2,3有n-4个

……

当0,1有n-2个的时候,2,3有2个

我们不妨设0,1共有k位,2,3共有n-k位

因为第3条规定首位不能为0,所以第一个数不能填0,即前两个数不能填0,1(因为第1条规定0必须在1的前面)

所以我们只能在剩下的n-1个位置中取两个位置填上0,1,然后再填2,3

k位的0,1再继续进行分类:

我们设0有t位,1有k-t位

因为0必须在1之前,所以一旦t确定了,整个数就确定了(即前t位一定为0,后k-t位一定为1

所以0,1的所有不同的方案数完全取决于t的不同的选择的数量

0至少要有1位,所以大于等于1,1也至少有1位,所以小于等于k-1,所以k-1≥t≥1,所以t一共有k-1中选法

同理,2,3,一共有n-k位,所以一共有n-k-1种选法

所以计算公式为$\displaystyle\sum_{k=2}^{n-2}C_{n-1}^k(k-1)(n-k-1)$

接下来求一下k到n-1的组合数

用递推的方法来求

$C_a^b$=$C_{a-1}^b$+$C_{a-1}^{b-1}$

这个式子的推导过程:(报名算法基础课的小伙伴可以看一下AcWing 885. 求组合数 I)

比如说我们要这a个球里面选b个球,然后我们随便取一个球数来

然后我们就可以把情况分成两类:一种是选这个球,一种是不选这个球

那么我们总共的方案数之和应该是这两种方案之和

选这个球的话,相当于我们要在剩余的a-1个球里面选b-1个球,即$C_{a-1}^{b-1}$

不选这个球的话,相当于我们要在剩余的a-1个球里选b个球,即$C_{a-1}^b$

所以我们总共的方案数就是$C_a^b$=$C_{a-1}^b$+$C_{a-1}^{b-1}$

代码

#include<iostream>
using namespace std;
typedef long long LL;
const int N=1010,MOD=1e9+7;
int n;
int c[N][N];
int main()
{
    cin>>n;
    for(int i=0;i<=n;i++)
    {
        for(int j=0;j<=i;j++)
        {
            if(!j) c[i][j]=1;
            else c[i][j]=(c[i-1][j]+c[i-1][j-1])%MOD;
        }
    }
    long long int res=0;
    for(int k=2;k<=n-2;k++)
    {
        //res=(res+(LL)c[n-1][k]*(k-1)%MOD*(n-1-k)%MOD);//如果数据范围比较大的话,用这种写法
        res=(res+(LL)c[n-1][k]*(k-1)*(n-1-k))%MOD;//这题的数据范围较小,可以最后取模
    }
    cout<<res<<endl;
}

附:Dp解法

AcWing 3195. 有趣的数(寒假每日一题)



分享 vector用法

介绍

vector收录在STL里,是一种特殊的数据结构。它的中文名字叫做“动态数组”或者“不定长数组”,有时也被翻译成“容器”。

说白了,vector就是一个功能强大的数组。

头文件

<vector>

声明

vector <数据类型> 动态数组名

如果你想赋初值,你可以:
vector <int> M(a,b)->在M里装a个b

vector <int> N(a)->在N里装a个0

当然你也可以:
vector <int> A

vector <int> B(A)->一个和A一模一样的动态数组

vector <int> C(B..begin()+l,B.end()-r)->继承B动态数组下标[l.B.end()-r)的值(注意:下标从0开始,函数用法见下)

注:[l.B.end()-r)是数学中的"左闭右开",意思就是这一数组中包含B里的第l个数,但是不包含B.end()-r这个数

(附上代码,大家可以自己试一下)

#include<iostream>
#include<vector>
using namespace std;
int main() 
{
    int l,r;
    vector <int> A(10);
    cout<<"A的长度为"<<A.size()<<endl<<endl;
    cout<<"A里的值:"<<endl<<endl;
    for(int i=0;i<A.size();i++)
    {
        A[i]=i;
        cout<<'<'<<i<<'>'<<' '<<A[i]<<endl;
    }
    cout<<endl;
    cout<<"接下来将对B进行如下定义:"<<endl<<endl;
    cout<<"B(A.begin()+l,A.end()-r)"<<endl<<endl;
    cout<<"请输入l=";
    cin>>l;
    cout<<endl;
    cout<<"请输入r=";
    cin>>r;
    cout<<endl;
    vector <int> B(A.begin()+l,A.end()-r);
    cout<<"B的长度为"<<B.size()<<endl<<endl;
    cout<<endl<<"B里的值:"<<endl<<endl;
    for(int i=0;i<B.size();i++)
    {
        cout<<"<"<<i<<'>'<<' '<<B[i]<<endl;
    }
    return 0;
}

vector的析构函数

动态数组名.~vector<该数组的数据结构>();

vector的自带函数

我们以vector <int> v;为例:

(注意:vector的下标从0开始)

1.v.at(i);

返回v[i]的值,当然,你也可以直接写成v[i]

2.v.size();

返回v数组元素的总个数

3.v.front();

返回v数组第一个元素的值

4.v.back();

返回v数组最后一个元素的值

5.v.clear();

清空v数组

6.v.begin();

返回v数组第一个元素的地址

7.v.end();

返回v数组最后一个数之后的地址

8.v.empty();

判断v数组是否为空,是空返回1(true),非空返回0(false)

9.v.swap(v1);swap(v,v1);

v1是另一个动态数组,将v和v1的元素交换

10.v.capacity();

返回v数组能够容纳的元素数量

11.v.resize();

将v数组的长度设为k

(附上一段代码,大家可以感受一下)

#include<iostream>
#include<vector>
using namespace std;
int b,j,m,n;
int main()
{
    cout<<"请输入v数组的元素个数:";
    cin>>n;
    vector <int> v(n);
    cout<<endl;
    cout<<"当前已成功定义v数组"<<endl<<endl; 
    for(int i=0;i<n;i++)
    {
        cout<<"请输入第"<<i<<"个元素:";
        cin>>v[i]; 
        cout<<endl;
    }
    cout<<"请输入想要查询的第m个值:";
    cin>>m;
    cout<<endl;
    cout<<"当前动态数组的第m个元素为;"<<v.at(m)<<endl<<endl;
    cout<<"当前动态数组共有 "<<v.size()<<" 个元素"<<endl<<endl;
    cout<<"当前动态数组的第一个元素为:"<<v.front()<<endl<<endl; 
    cout<<"当前动态数组的最后一个元素为:"<<v.back()<<endl<<endl; 
    cout<<"当前动态数组的第一个元素的地址为:"<<v.front()<<endl<<endl; 
    cout<<"当前动态数组的最后一个元素之后的地址为:"<<v.front()<<endl<<endl; 
    cout<<"是否要对当前动态数组的长度进行修改?是则输入1,否则输入0:";
    cin>>b;
    cout<<endl;
    if(b==1)
    {
        cout<<"请输入将要修改成的长度:";
        cin>>j;
        cout<<endl;
        v.resize(j);
    }
    cout<<"当前动态数组的元素个数为:"<<v.size()<<endl<<endl;
    cout<<"当前动态数组的容量为:"<<v.capacity()<<endl<<endl;

    cout<<"请输入v1数组的元素个数:";
    cin>>n;
    cout<<endl;
    vector <int> v1(n);
    cout<<"当前已成功定义v1数组"<<endl<<endl; 
    for(int i=0;i<v1.size();i++)
    {
        cout<<"请输入第"<<i<<"个元素:";
        cin>>v1[i]; 
        cout<<endl;
    }
    cout<<"请输入想要查询的第m个值:";
    cin>>m;
    cout<<endl;
    cout<<"当前动态数组的第m个元素为;"<<v1.at(m)<<endl<<endl;
    cout<<"当前动态数组共有 "<<v1.size()<<" 个元素"<<endl<<endl;
    cout<<"当前动态数组的第一个元素为:"<<v1.front()<<endl<<endl; 
    cout<<"当前动态数组的最后一个元素为:"<<v1.back()<<endl<<endl; 
    cout<<"当前动态数组的第一个元素的地址为:"<<v1.front()<<endl<<endl; 
    cout<<"当前动态数组的最后一个元素之后的地址为:"<<v1.front()<<endl<<endl; 
    cout<<"是否要对当前动态数组的长度进行修改?是则输入1,否则输入0:";
    cin>>b;
    cout<<endl;
    if(b==1)
    {
        cout<<"请输入将要修改成的长度:";
        cin>>j;
        cout<<endl;
        v1.resize(j);
    }
    cout<<"当前动态数组的元素个数为:"<<v1.size()<<endl<<endl;
    cout<<"当前动态数组的容量为:"<<v1.capacity()<<endl<<endl;
    cout<<"是否交换v和v1,是则输入1,否则输入0:";
    cin>>b;
    if(b==1)
    {
        swap(v,v1);
        cout<<"v1数组里的元素为:"<<endl<<endl;
        for(int i=0;i<v.size();i++)
        {
            cout<<v[i]<<' ';
        }
        cout<<"v1数组里的元素为:"<<endl<<endl;
        for(int i=0;i<v1.size();i++)
        {
            cout<<v[i]<<' ';
        }
    }
    cout<<endl;
    cout<<"感受完函数的使用你也快快去尝试一下吧O( ∩ _  ∩)O~" ;
    return 0;
}

vector的插入

std库提供了好几种插入,这里讲最为常用的三种

1.v.pusb_back(a);

在v数组的尾部插入数a

2.v.insert(v.begin()=k,a)

在下标k的前面插入数a

3..insert(v.begin()+k,p,a)

在下标k前面插入p个a

vector的删除

1.v.pop_back()

删除最后一个元素

2.v.erase(v.begin()+k)

删除下标为k的数,返回下一个位置的下标

3.v.erase(v.begin()+l,v.end()-r)

删除下标[l,v.end()-r)的元素

vector的内存机制

给大家几个规律:

1.设当前v.capacity()=c,v.size()=s;如果s=c+1,那么c就会加倍。

2.当动态数组内的元素比动态数组长度多一时,动态数组长度翻倍!

3.求vector最多能装多少个元素,我们可以用函数:v.max_size();来得到。

下列是一个常用的数据结构对应的max_size();

bool -> 4294967295

char -> 4294967295

int-> 1073741823

unsigned int -> 1073741823

float -> 1073741823

double-> 536870911

long long -> 536870911

unsigned long long ->536870911

string类型的vector

我们有的时候会看到把vector写成二维数组的形式,比如ops[i][j],i就代表这是vector里的第i个元素,而j就代表这是vector里第i个元素的第j个字符

#include<iostream>
#include<vector>
#include<string>
using namespace std;
int main()
{
    vector<string> s;
    string str;
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>str;
        s.push_back(str);
    }
    for(int i=0;i<s.size();i++)
    {
        cout<<s[i]<<endl;
        for(int j=0;j<s[i].size();j++)
        {
            cout<<s[i][j]<<' ';
        }
        cout<<endl;
    }
    return 0;
}
本篇分享来自C20182030Epic的博客,稍微改动了一下,在上CCF-CSP认证辅导课的时候y总说到了vector,于是自己学习了一下vector,感觉挺好用的,因为是自己学的,所以可能有写的不对的地方,所以请大家多多指教



题目描述

给出一个字符串和多行文字,在这些文字中找到字符串出现的那些行。

你的程序还需支持大小写敏感选项:当选项打开时,表示同一个字母的大写和小写看作不同的字符;当选项关闭时,表示同一个字母的大写和小写看作相同的字符。

输入格式

输入的第一行包含一个字符串 S,由大小写英文字母组成。

第二行包含一个数字,表示大小写敏感的选项,当数字为 0 时表示大小写不敏感,当数字为 1 时表示大小写敏感。

第三行包含一个整数 n,表示给出的文字的行数。

接下来 n 行,每行包含一个字符串,字符串由大小写英文字母组成,不含空格和其他字符。

输出格式

输出多行,每行包含一个字符串,按出现的顺序依次给出那些包含了字符串 S 的行。

数据范围

$1≤n≤100$,

每个字符串的长度不超过 100。

输入样例:

Hello
1
5
HelloWorld
HiHiHelloHiHi
GrepIsAGreatTool
HELLO
HELLOisNOTHello

输出样例:

HelloWorld
HiHiHelloHiHi
HELLOisNOTHello

样例解释

在上面的样例中,第四个字符串虽然也是 Hello,但是大小写不正确。

如果将输入的第二行改为 0,则第四个字符串应该输出。

思路

这题……直接暴力就行了

而且……这个暴力枚举C++里面还有一个函数:

就是string里的a.find(s)函数,这个函数是返回原串在当前串第一次出现的位置
如果找不到会返回-1,此函数的时间复杂度是O(nm)的

如果,只是如果,数据范围较大的话我们可以用kmp来做,这种做法可以吧时间复杂度做成$O(n)$的

另外C++里还有一种函数,就是strstr函数

代码$O(n^2)$

#include<iostream>
using namespace std;
const int N=110;
string get(string str)
{
    string res;
    for(auto c:str)//这是C++11包含一种新的for循环,称为基于范围的for循环,可以简化对数组元素的遍历
        res+=tolower(c);
    return res;
}
int main()
{
    string s;
    cin>>s;
    int n;
    bool type;
    cin>>type>>n;
    while(n--)
    {
        string str;
        cin>>str;
        if(type && str.find(s)!=-1) cout<<str<<endl;
        else if(!type&&get(str).find(get(s))!=-1) cout<<str<<endl;//注意两个字符串都要变成小写
    }
    return 0;
}

关于get()函数里的那个循环,给大家两篇博客进行参考
Blog
Blog



活动打卡代码 AcWing 3199. 命令行选项

题目描述

请你写一个命令行分析程序,用以分析给定的命令行里包含哪些选项。

每个命令行由若干个字符串组成,它们之间恰好由一个空格分隔。

这些字符串中的第一个为该命令行工具的名字,由小写字母组成,你的程序不用对它进行处理。

在工具名字之后可能会包含若干选项,然后可能会包含一些不是选项的参数。

选项有两类:带参数的选项和不带参数的选项。

一个合法的无参数选项的形式是一个减号后面跟单个小写字母,如 -a-b

而带参数选项则由两个由空格分隔的字符串构成,前者的格式要求与无参数选项相同,后者则是该选项的参数,是由小写字母,数字和减号组成的非空字符串。

该命令行工具的作者提供给你一个格式字符串以指定他的命令行工具需要接受哪些选项。

这个字符串由若干小写字母和冒号组成,其中的每个小写字母表示一个该程序接受的选项。

如果该小写字母后面紧跟了一个冒号,它就表示一个带参数的选项,否则则为不带参数的选项。

例如,ab:m: 表示该程序接受三种选项,即 -a(不带参数),-b(带参数),以及 -m(带参数)。

命令行工具的作者准备了若干条命令行用以测试你的程序。

对于每个命令行,你的工具应当一直向后分析。

当你的工具遇到某个字符串既不是合法的选项,又不是某个合法选项的参数时,分析就停止。

命令行剩余的未分析部分不构成该命令的选项,因此你的程序应当忽略它们。

输入格式

输入的第一行是一个格式字符串,它至少包含一个字符,且长度不超过 52。

格式字符串只包含小写字母和冒号,保证每个小写字母至多出现一次,不会有两个相邻的冒号,也不会以冒号开头。

输入的第二行是一个正整数 N,表示你需要处理的命令行的个数。

接下来有 N 行,每行是一个待处理的命令行,它包括不超过 256 个字符。该命令行一定是若干个由单个空格分隔的字符串构成,每个字符串里只包含小写字母,数字和减号。

输出格式

输出有 N 行。其中第 i 行以 Case i: 开始,然后应当有恰好一个空格,然后应当按照字母升序输出该命令行中用到的所有选项的名称,对于带参数的选项,在输出它的名称之后还要输出它的参数。

如果一个选项在命令行中出现了多次,只输出一次。

如果一个带参数的选项在命令行中出现了多次,只输出最后一次出现时所带的参数。

数据范围

1≤N≤20,

对于每组数据,所有命令行工具的名字一定相同,且由小写字母构成。

输入样例:

albw:x
4
ls -a -l -a documents -b
ls
ls -w 10 -x -w 15
ls -a -b -c -d -e -l

输出样例:

Case 1: -a -l
Case 2:
Case 3: -w 15 -x
Case 4: -a -b

思路

这题又双叒叕是一道模拟题……

CCF-CSP的第3题有很大的概率会出模拟题(而且会很长),这题y总说还是比较短的……(原谅我是一个蒟蒻)

建议大家如果没看懂题就再多读几遍,(y总说有的题广度提就要读上一个小时,但代码很短)毕竟考试的时候没有题解让你看,尽量在考试之前炼成读题的能力(文科生吃香)

不过我们在模拟之前要想一下怎么把所有的信息存下来

首先,我们要存一下每个符号有无参数:

那么我们可以开两个bool数组,一个记录没有参数的,另一个记录没有参数的

然后,我们想一下怎么对有参数的符号进行处理:

其实我们只要把每次输入的值覆盖掉就行了,这样我们就只会保留后一次出现的数字

那么再考虑一下答案怎么存:

存答案的话我们可以用string来存

这题运用到了一些stringstream和vector的知识,大家可以参考一下stringstream用法vector用法

代码

#include<iostream>
#include<sstream> 
#include<vector>
#include<string>
using namespace std;
int n;//如果不手动初始化为0的话,就必须在这里定义,否则会WA(555~)
bool o1[30],o2[30];
string ans[30];
int main()
{
    string str;
    cin>>str;//输入定义的变量
    for(int i=0;i<str.size();i++)
    {
        if(i+1<str.size()&&str[i+1]==':')//有参数选项
        {
            o2[str[i]-'a']=1;//将字符转换成数字并标记
            i++;//跳过':'
        }
        else
        {
            o1[str[i]-'a']=1;//将字符转换成数字并标记
        }
    }
    cin>>n;
    getchar();//将n后面的回车过滤掉 
    for(int i=1;i<=n;i++)
    {
        getline(cin,str);
        stringstream ssin(str);//将str复制到ssin
        vector <string> ops;//定义一个动态数组
        cout<<"Case "<<i<<":";//输出
        while(ssin>>str) ops.push_back(str);//运用stringstream的特性对str进行单词分割
        for(int i=0;i<26;i++) ans[i].clear();//清空,否则会影响本次运行
        for(int i=1;i<ops.size();i++)
        {
            if(ops[i][0]!='-'||ops[i][1]<'a'||ops[i].size()!=2) break;//判断此位是不是变量
            //因为输入变量的时候开头一定是'-',并且长度一定是2,<'a'是判断是不是数字
            int k=ops[i][1]-'a';//将字符转换为数字进行存储
            if(o1[k]) ans[k]="*";
            //因为下面会对ans的长度进行判断,为了防止ans为空,随意存入一个字符进行标记
            else if(o2[k]&&i+1<ops.size())  ans[k]=ops[i+1],i++;
            //如果是有参数选项,将他后面输入的字符进行存储
            else break;//否则直接跳出
        }
        for(int i=0;i<26;i++)//因为输入的诠释小写字母,所以字母最多有26个
        {
            if(ans[i].size())//判断有没有这个变量
            {
                cout<<" -"<<(char)(i+'a');//先将变量输出
                if(o2[i]) cout<<' '<<ans[i];//如果是有参数选项,将参数输出
            }
        }
        cout<<endl;//别忘了换行
    }
    return 0;
}