你好赵伟

这个屌丝很懒，什么也没留下！

热门标签

2021年第一场蓝桥杯c++_蓝桥杯c++题目分值

作者：你好赵伟 | 2024-03-24 14:28:44

踩

蓝桥杯c++题目分值

题目目录

填空题
编程题

蓝桥杯分值：5,5,10,10,15（填空题）||15,20,20,25,25（编程题）

填空题

第一题：空间（单位换算）

参考答案：67108864
在这里插入图片描述
分析：
32位二进制数需要占4个字节（一个字节8bit）， $256 M B = 256 * 1024 K B = 256 * 1024 * 1024$ 字节，所以一共可以存储的32位二进制整数的数量就是 $256 * 1024 * 1024 / 4$

#include <bits/stdc++.h>

using namespace std;

int main()
{
    cout<<256*1024*1024/4<<endl;
    return 0;
}

1
2
3
4
5
6
7
8
9
10

第二题：卡片（纯模拟）

参考答案：3181

在这里插入图片描述
写法一：

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int a[10];
    for(int i=0;i<=9;i++)
        a[i]=2021;
    for(int i=1;;i++)
    {
        int k=i;
        while(k)
        {
            int r=k%10;
            if(a[r]==1){cout<<i<<endl;return 0;}
            a[r]--;
            k/=10;
        }
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

写法二：stringstream

#include <bits/stdc++.h>

using namespace std;

string int_str(int i)//整型转字符串
{
    string output;
    stringstream convert;
    convert<<i;//向流中传值
    convert>>output;//实现任意类型的转换
    return output;
}

int main()
{
    int i=1;
    int none=0;
    while(1)
    {
        string s=int_str(i);
        none+=count(s.begin(),s.end(),'1');//记录1出现的次数
        if(none>=2021)break;
        else i+=1;
    }
    cout<<i<<endl;

    return 0;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

第三题：直线（模拟）

参考答案：40257
在这里插入图片描述
分析：
总的直线数=斜直线+横直线+竖直线。横直线和竖直线都十分容易统计，分别是21和20个，因此重点来统计不同斜直线的个数。每条直线可用：y=kx+b来表示，所以一组不同的{k,b}可以代表不同的直线。所以本题的关键点是来用集合来存放并统计不同的斜直线个数。

set的主要功能就是相当于一个插入后能自动排序的数组（从小到大）。但是要注意一个数值在set中只能出现1次或0次；

set当中是不保存重复元素的。

感觉这个模拟的话，你就需要熟练的掌握STL容器来满足自己的需要。而且像这种都double的题目就一定要注意精度问题。

#include<bits/stdc++.h>

using namespace std;
struct point
{
    int x;//横坐标
    int y;//纵坐标
};

int main()
{
    vector<point>p;//存放所有点
    for(int i=0;i<=19;i++)
        for(int j=0;j<=20;j++)
    p.push_back({i,j});
    int len=p.size();
    set<pair<double,double>>lines;//存放斜直线y=kx+b
    for(int i=0;i<len;i++)
        for(int j=0;j<len;j++)
    {
        if(p[i].x!=p[j].x&&p[i].y!=p[j].y)//统计所有斜线的情况
        {
            double k=(p[j].y-p[i].y)*1.0/(p[j].x-p[i].x);
            double b=(p[j].y*(p[j].x-p[i].x)-p[j].x*(p[j].y-p[i].y))*1.0/(p[j].x-p[i].x);
            //不要用double b=p[j].y-k*p[j].x;这种方法，避免k造成精度爆炸
            lines.insert(pair<double,double>(k,b));
        }
    }
    cout<<lines.size()+20+21<<endl;//总的直线=斜直线+横直线+竖直线

    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

第四题：货物摆放（分解因子）

参考答案：2430

写法一：暴力法
我们分解得到他的所有因数

#include<bits/stdc++.h>

using namespace std;
const int N=1010;//约数个数不用很多
long long a[N];//来保存他的因数

int main()
{
    long long n=2021041820210418;
    long long m=0;
    for(int i=1;i<n/i;i++)//n/i 等于sqrt(n)
    {
        if(n%i==0)
        {
            if(i==n%i)
                a[m++]=i;
            else {
                a[m++]=n/i;
                a[m++]=i;
            }
        }
    }
    long long res=0;
    for(int i=0;i<m;i++)
        for(int j=0;j<m;j++)
        for(int z=0;z<m;z++)
    {
        if(a[i]*a[j]*a[z]==n)res++;
    }
    cout<<res<<endl;

    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

写法二：
这个写法二跟写法一类似，但是又不完全类似

#include<bits/stdc++.h>

using namespace std;

const long long n=2021041820210418;

int main()
{
    vector<long long>factor;//存放所有的因数
    for(int i=1;i<sqrt(n);i++)
    {
        if(n%i==0)
        {
            factor.push_back(i);
            factor.push_back(n/i);
        }
    }
    //枚举情况
    int ans=0;
    int len=factor.size();//因数
    for(int i=0;i<len;i++)
        for(int j=0;j<len;j++)
        if(n%(factor[i]*factor[j])==0)
        ans++;
    cout<<ans<<endl;
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

写法三：运用数论的方法
在这里插入图片描述

#include <bits/stdc++.h>
using namespace std;

vector<long long int> primeNum, primeVal;
// 将x质因数分解
void CalaPrime(long long int x) {
  printf("%lld = ", x);
  for (long long int i = 2; i * i <= x; i++) {
    if (x % i == 0) {
      int num = 0;
      while (x % i == 0) {
        x /= i;
        num++;
      }
      primeNum.push_back(num);
      primeVal.push_back(i);
    }
  }
  if (x > 1) {
    primeNum.push_back(1);
    primeVal.push_back(x);
  }

  for (unsigned int i = 0; i < primeNum.size(); i++) {
    if (i != 0) {
      printf("  *  ");
    }
    printf("\n(%lld ^ %lld)", primeVal[i], primeNum[i]);
  }
  printf("\n");
}

int main() {
  CalaPrime(2021041820210418);

  long long int ans = 0;
  ans = 3 * 3 * 3 * 3 * 3;
  ans *= 10;

  printf("ans = %lld\n", ans);
  return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

写法四：根据质因数的情况
大佬分析！！

#include<stdio.h>
#include<math.h>
#define n 2021041820210418 
int main(){
	long long int i,j;
	int sum = 0;      //统计式子个数的变量 
	for(i=1;i<=sqrt(n);i++){
		if(n%i == 0){  //i是n的第一个因数 
			for(j=i;j<=sqrt(n/i);j++){ //j从i开始循环,保证了i<=j 
				if(n/i%j == 0){  //j是n的第二个因数 
					if(i==j && j==n/i/j){sum++;}
					else if(i==j || j==n/i/j || i==n/i/j){sum+=3;}
					else {sum+=6;}
					//printf("%lld  %lld %lld %d \n",i,j,n/i/j,sum); //检测代码
				}	
			}
		}
	}
	printf("%d",sum);
} 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

第五题：路径（单源最短路）

在这里插入图片描述

在这里插入图片描述
dijstra算法普遍会比较快（0.6s），floyd算法比较慢（52s）

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

typedef long long ll;
const ll inf = 1e12;
int vis[2050];
ll e[2050][2050], dis[2050];

ll gcd(ll a, ll b)   //求最大公因数
{
	return a % b == 0 ? b : gcd(b, a % b);
}

ll lcm(ll a, ll b)	//求最小公倍数
{
	return a * b / gcd(a, b);
}

int main()
{
	fill(dis, dis + 2050, inf);
	fill(e[0], e[0] + 2050 * 2050, inf);
	for (int i = 1; i <= 2021;i++)
	{
		for (int j = 1; j <= 21;j++)    //21步以内有效
		{
			int k = i + j;  //i为起点，k为终点
			if (k > 2021)
				break;
			e[i][k] = e[k][i] = lcm(i, k);
		}
	}
	dis[1] = 0;
	//最短路径模板  dijstra算法
	for (int i = 1; i <= 2021;i++)
	{
		ll u = -1, minn = inf;
		for (int j = 1; j <= 2021;j++)//找到起点
		{
			if (!vis[j] && dis[j] < minn)
			{
				minn = dis[j];
				u = j;
			}
		}
		if (u == -1)//说明没有找到起点
			break;
		vis[u] = 1;
		for (int v = 1; v <= 2021;v++)
		{
			if (!vis[v])
				dis[v] = min(dis[v], e[u][v] + dis[u]);
		}
	}
	cout << dis[2021];
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

这个是大佬写的嗷！写了floyd算法和dijstra算法，唯一的缺点就是不太好理解。大家可以将他们的运行时间进行比较一下

#include <bits/stdc++.h>
using namespace std;

const int maxn = 2021;

vector<int> u[maxn + 52];
vector<int> v[maxn + 52];
int disDijk[maxn + 52];
int disFloyd[maxn + 52][maxn + 52];
bool vis[maxn + 52];

// 初始化建图，u[i][j]表示i的第j条出边编号，v[i][j]表示i的第j条边的长度，也就是i和u[i][j]的距离
void InitGroup() {
  for (int i = 1; i <= maxn; i++) {
    for (int j = i + 1; j <= maxn; j++) {
      if (j - i <= 21) {
        u[i].push_back(j);
        v[i].push_back(i * j / __gcd(i, j));
        u[j].push_back(i);
        v[j].push_back(i * j / __gcd(i, j));
      }
    }
  }
}

// floyd算法计算最短路，disFloyd[i][j] 表示i到j的最短距离
void Floyd() {
  // 初始化disFloyd为一个较大值
  memset(disFloyd, 0x3f, sizeof(disFloyd));
  for (unsigned int i = 1; i <= maxn; i++) {
    for (unsigned int j = 0; j < v[i].size(); j++) {
      disFloyd[i][u[i][j]] = v[i][j];
      disFloyd[u[i][j]][i] = v[i][j];
    }
  }

  // 执行floyd算法
  for (int k = 1; k <= maxn; k++) {
    for (int i = 1; i <= maxn; i++) {
      for (int j = 1; j <= maxn; j++) {
        disFloyd[i][j] = disFloyd[j][i] = min(disFloyd[i][j], disFloyd[i][k] + disFloyd[k][j]);
      }
    }
  }
  printf("floyd ans = %d\n", disFloyd[1][maxn]);
}

// Dijkstra算法计算最短路，disDijk[i]表示i距离结点1的最短距离
void Dijkstra() {
  memset(disDijk, 0x3f, sizeof(disDijk));
  memset(vis, 0, sizeof(vis));

  disDijk[1] = 0;

  for (int i = 1; i <= maxn; i++) {
    int curMin = 0x3f3f3f3f;
    int curIndex = -1;
    for (int j = 1; j <= maxn; j++) {
      if (vis[j]) {
        continue;
      }
      if (curMin > disDijk[j] || curIndex == -1) {
        curMin = disDijk[j];
        curIndex = j;
      }
    }
    vis[curIndex] = true;

    for (unsigned int j = 0; j < u[curIndex].size(); j++) {
      int t = u[curIndex][j], val = v[curIndex][j];
      disDijk[t] = min(disDijk[t], disDijk[curIndex] + val);
    }
  }
  printf("Dijkstra ans = %d  vis = %d\n", disDijk[2021], vis[2021]);
}

int main() {
  InitGroup();
//  Floyd();
  Dijkstra();

  return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84

编程题

第六题：时间显示（模拟）

在这里插入图片描述
注意所给的是毫秒哦！
这题涉及到的知识点是：取模，时间计算
感觉这道题目就是很容易弄昏。
接下来有两种写法，看你们能理解哪一个就看哪一个把！<个人偏爱第二个>
写法一：

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int main()
{
    ll t;
    cin>>t;
    t=t%(24*60*60*1000);//先把他转化为一天之间的毫秒
    int h=t/(1000*60*60);//小时
     int m=t%(60*60*1000);//分钟
     m=m/60000;//除以分钟
    int s=t/1000%60;//秒

    printf("%02d:%02d:%02d",h,m,s);
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

写法二：

#include <bits/stdc++.h>
using namespace std;

int main() {

  long long int dayMs = 24 * 60 * 60 * 1000; //一天包含多少毫秒
  long long int n;
  scanf("%lld", &n);

  // 扣除整天的描述之后，得到最后一天剩下了多少毫秒
  n = n % dayMs;
  // 忽略毫秒，得到还剩多少秒
  n = n / 1000;

  // 一小时3600秒，走过了多少个完整的3600秒就代表当前小时数是多少
  int hour = n / (3600);

  // 扣除整小时之后剩下的秒数，可以走过多少个完整的60秒就代表当前分钟数是多少
  int minutes = (n - hour * 3600) / 60;

  // 走完全部的完整60秒之后剩下的秒数就是秒数
  int second = n % 60;

  printf("%02d:%02d:%02d\n", hour, minutes, second);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

第七题：砝码称重

在这里插入图片描述

有限制的选择问题我们叫做背包问题
写法一： 但他的这个方法我着实没看懂

#include <iostream>
#define N 102
#define MAX_WEIGHT 100005
using namespace std;

int n, m, k, w[N], sum_weight, ans;
bool dp[N][MAX_WEIGHT << 2];

int main() {
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> w[i];
		sum_weight += w[i];
	}
	dp[0][sum_weight * 2] = true;
	//我的理解是由于有正数和负数的存在，我们把sum_weight理论上当作0
	for (int i = 1; i <= n; ++i) {
		for (int j = sum_weight; j <= sum_weight * 2+1; ++j) {
			dp[i][j] = dp[i][j] || dp[i - 1][j] || dp[i - 1][j - w[i]] || dp[i - 1][j + w[i]];//不放，放左边，放右边
		}
	}
	for (int i = 1; i <= sum_weight; ++i) {
		if (dp[n][sum_weight+ i] || dp[n][sum_weight - i]) {
		    cout<<sum_weight+i<<endl;
			++ans;
		}
	}
	cout << ans;
	return 0;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

写法二：

#include<bits/stdc++.h>

using namespace std;
const int N=110,M=200010;
#define B m/2
int w[N];
bool f[N][M];

int main()
{
    int n;
    cin>>n;
    int m=0;
    for(int i=1;i<=n;i++)
        {
            cin>>w[i];
            m+=w[i];
        }
        f[0][B]=true;//以B作为理论原点
        for(int i=1;i<=n;i++)
            for(int j=-m;j<=m;j++)
            {
                f[i][j+B]=f[i-1][j+B];
                if(j-w[i]>=-m)f[i][j+B] |=f[i-1][j-w[i]+B];//因为是bool数组，只要一个满足了就可以，所以用|
                if(j+w[i]<=m)f[i][j+B] |=f[i-1][j+w[i]+B];
            }
            int res=0;
            for(int j=1;j<=m;j++)
                if(f[n][j+B])//由于他是最后对称的，所以我们只用算一边就可以了
                res++;
            cout<<res<<endl;

            return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

写法三：

#include<iostream>
#include<cmath>

using namespace std;
const int N = 110, M = 200010;
int f[N][M]; // 表示从前i个砝码选 总重量为j的集合 
int n,w[N]; 
int sum; //表示砝码可以称出的最大重量 

int main(){
    cin >> n;
    for(int i = 1; i <= n; i ++){
        cin >> w[i];
        sum += w[i];
    } 

    f[0][0] = true; // 初始化从前0个选重量为0 该方式存在

    for(int i = 1; i <= n; i ++){
        for(int j = 0; j <= sum; j ++){
            f[i][j] = f[i - 1][j] + f[i - 1][abs(j - w[i])] + f[i - 1][j + w[i]];
            // f[i - 1][j]表示不选的方案数 ,f[i - 1][j + w[i]]表示选择+w[i]的方案数，f[i - 1][j - w[i]]表示选择-w[i]的方案数 
            //-sum和sum本质是一样的 故使用绝对值 
        }
    } 

    for(int j = 1; j <= sum; j ++){
        if(f[n][j]) ans ++; //如果方案数不为0 说明可以凑出重量为j 所以ans++
    }

    cout << ans;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

写法四：我看不懂，但我大为震撼

#include<iostream>
#include<bitset>
using namespace std;
const int N = 105, M = 100005;
int g[N], n;
bitset<M> S;
int main(){
    scanf("%d", &n);
    for(int i = 0; i < n; i ++ ){
        scanf("%d", &g[i]);
    }
    S[0] = 1;
    for(int i = 0; i < n; i ++ ){
        S |= S << g[i];
    }
    for(int i = 0; i < n; i ++ ){
        S |= S >> g[i];
    }
    cout << S.count() - 1 << endl;
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

第八题：杨辉三角

在这里插入图片描述
由于这个左右是对称的，所以，我们在找的时候只用考虑左边就可以了。

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

using namespace std;

typedef long long LL;

int n;
/*
    组合数和杨辉三角：第i行第j列的数都是组合数C(i, j) （i，j从0开始）
        C(n, 1) = n --> 对应从左向右看斜着的第二列！ ---> 一定有解
    由于杨辉三角左右对称（C(a, b) == C(a, a-b)），又由于找第一次出现，因此一定在左边，右边可以直接删掉！

            1  ---> C(0, 0)
          1 
        1   2  ---> C(2, 1)
      1   3                             ---> C(2n, n)
    1   4   6  ---> C(4, 2)
  1   5   10
1   6   15  20 ---> C(6, 3)

    n最大1e9，C(34, 17) > 1e9, C(32, 16) < 1e9，因此只要枚举前16个斜行即可！


    性质：
        1. 每一斜行从上到下递增
        2. 每一横行从中间到两边依次递减

    因此我们直接从中间对称轴倒序二分找起即可!

        C(r, k)对应的顺序值为：(r + 1) * r / 2 + k + 1

        二分的左右端点：l：2k，r：max(n, l)
            右端点一定不能比左端点小！
            特例：否则当n=1时，会出问题！

*/
// C(a, b) = a!/b!(a-b)! = a * (a-1) .. b个 / b!
LL C(int a, int b){
    LL res = 1;
    for(int i = a, j = 1; j <= b; i --, j ++){
        res = res * i / j;
        // 大于n已无意义，且防止爆LL
        if(res > n) return res;
    }
    return res;
}

bool check(int k){
    // 二分该斜行,找到大于等于该值的第一个数
    // 左边界2k，右边界为max(l, n)取二者最大即可！
    //上边界 l=2k，下边界 r=n（如果内层斜行都没找到，一定出现在第2行，因为C1n=n）
    int l = 2 * k, r = max(n, l);
    while(l < r){
        int mid = l + r >> 1;
        if(C(mid, k) >= n) r = mid;
        else l = mid + 1;
    }
    if(C(r, k) != n) return false;
    // C(r, k)的从0开始的顺序！
    cout << 1ll * (r + 1) * r / 2 + k + 1 << endl;//等差求和公式
    return true;
}

int main(){
    cin >> n;
    // 从第16斜行枚举即可！
    for(int k = 16; ; k --)
        if(check(k)) break;
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

很好，读了大学两年，等差等比公式给你忘光光！

等差数列{an}的通项公式为：an=a1+(n-1)d。前n项和公式为：Sn=n*a1+n(n-1)d/2或Sn=n(a1+an)/2 。
等比数列{an}求和公式：Sn=na1(q=1)，Sn=[a1(1-q)^n]/(1-q)（q≠1）
1
2

第九题：双向排序

在这里插入图片描述

首先我们来看看两个暴力法：虽然TLE了，但是我们能拿60分，及格了哈哈哈哈，够了够了嘻嘻
在这里插入图片描述

#include<bits/stdc++.h>

using namespace std;
const int N=100010;
int a[N];
bool cmp(int a,int b)
{
    return a>b;//降序
}

int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    cin>>a[i];
    while(m--)
    {
        int p,q;
        cin>>p>>q;
        if(p==0)sort(a+1,a+q+1,cmp);
        else sort(a+q,a+n+1);
    }
    for(int i=1;i<=n;i++)
        cout<<a[i]<<" ";


    return 0;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

这个时候，咱明知道会t的暴力，就尽量少用STL好吧，STL实属比数组慢了一些

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;

// 自定义降序排序谓词
bool cmp(int a, int b)
{
	return a > b;
}

int main()
{
	int n = 0; //序列长度
	int m = 0; //操作次数
	cin >> n >> m; //输入序列长度、操作次数
	vector<int> a;
	for (int i = 1; i <= n; i++)
		a.push_back(i); // 原数列
	for (int i = 0; i < m; i++)
	{
		int p, q;
		cin >> p >> q; // 输入排序类型、参数（排序临界点）
		if (p == 0)
			sort(a.begin(), a.begin() + q, cmp); //降序
		else
			sort(a.begin() + q - 1, a.end()); //升序
	}
	for (int i = 0; i < n;i++)
	{
		cout << a[i] << " ";
	}
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

正确解法：栈
这个题目有两个操作，前缀降序，后缀升序
这个数列的初始状态是升序的，那么我们就可以找规律了哇~
大佬！！！他解析的还是不错的！

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

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 100010;

int n, m;
PII stk[N];
int ans[N];

int main()
{
    scanf("%d%d", &n, &m);
    int top = 0;
    while (m -- )
    {
        int p, q;
        scanf("%d%d", &p, &q);
        if (!p)
        {
            while (top && stk[top].x == 0) q = max(q, stk[top -- ].y);//栈不是空的，且是降序的话，我们就保留最大的那个数
            while (top >= 2 && stk[top - 1].y <= q) top -= 2;//如果这个前缀和不是连续的，那我们要删除比他小的元素
            stk[ ++ top] = {0, q};
        }
        else if (top)//栈要非空
        {
            while (top && stk[top].x == 1) q = min(q, stk[top -- ].y);
            while (top >= 2 && stk[top - 1].y >= q) top -= 2;
            stk[ ++ top] = {1, q};
        }
    }
    int k = n, l = 1, r = n;
    for (int i = 1; i <= top; i ++ )
    {
        if (stk[i].x == 0)
            while (r > stk[i].y && l <= r) ans[r -- ] = k -- ;
        else
            while (l < stk[i].y && l <= r) ans[l ++ ] = k -- ;
        if (l > r) break;
    }
    if (top % 2)
        while (l <= r) ans[l ++ ] = k -- ;
    else
        while (l <= r) ans[r -- ] = k -- ;

    for (int i = 1; i <= n; i ++ )
        printf("%d ", ans[i]);
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

第十题：括号序列

合法括号序列所要满足的条件:
条件一：左右括号数量相同
条件二:任意前缀左括号数一定要不小于右括号数

从前往后扫描，比较左括号与右括号的数量，如果cnt<0的时候，我们需要添加一个左括号，最后如果cnt>0,那此时cnt为所需要添加的数量是多少。但我们这道题求的是方案数，所以我们在这里就要分析左括号有多少个添加的方案，右括号有多少个添加的方案
在这里插入图片描述

这个就相当于01背包
$f [i] [j] = f [i - 1] [j + 1] + f [i] [j - 1]$

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

using namespace std;

typedef long long LL;

const int N = 5010, MOD = 1e9 + 7;

int n;
char str[N];
LL f[N][N];

LL work()
{
    memset(f, 0, sizeof f);
    f[0][0] = 1;//当一个数据都没有的时候是1
    for (int i = 1; i <= n; i ++ )
        if (str[i] == '(')
        {
            for (int j = 1; j <= n; j ++ )
                f[i][j] = f[i - 1][j - 1];
        }
        else
        {
            f[i][0] = (f[i - 1][0] + f[i - 1][1]) % MOD;//防止下标越界，我们对于f[i][0]进行特判
            for (int j = 1; j <= n; j ++ )
                f[i][j] = (f[i - 1][j + 1] + f[i][j - 1]) % MOD;
        }

    for (int i = 0; i <= n; i ++ )
        if (f[n][i])//我们需要的就是长度为len添加括号的合法情况
        //而从前往后遍历出现的第一个有可能的情况就是需要括号数最少的情况
        //因为左括号可以加很多个，我们仅需添加最少的情况
            return f[n][i];
    return -1;
}

int main()
{
    scanf("%s", str + 1);
    n = strlen(str + 1);
    LL l = work();
    reverse(str + 1, str + n + 1);
    for (int i = 1; i <= n; i ++ )
        if (str[i] == '(') str[i] = ')';
        else str[i] = '(';
    LL r = work();
    printf("%lld\n", l * r % MOD);
    return 0;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/你好赵伟/article/detail/302932