首页 > 其他分享 >2. 4 蓝桥练习5题

2. 4 蓝桥练习5题

时间：2024-02-04 22:37:30浏览次数：29  
标签：const int ll 练习 cin long times 蓝桥

2. 4 蓝桥练习5题

今天写的几个题都挺有意思的，码量不大，主要是思维。藕还得多练QAQ

1.[P8669 蓝桥杯 2018 省 B] 乘积最大

题意：给定 \(N\) 个整数 \(A_1, A_2,\cdots, A_N\)。请你从中选出 \(K\) 个数，使其乘积最大。

请你求出最大的乘积，由于乘积可能超出整型范围，你只需输出乘积除以 \(1000000009\)（即 \(10^9+9\)）的余数。

注意，如果 \(X<0\)， 我们定义 \(X\) 除以 \(1000000009\) 的余数是 \(0-((0-x)\bmod 1000000009)\)。

思路：贪心+分类讨论

先排个序。如果\(K\)是偶数的话，我们考虑2个2个取。我们肯定优先两个正的或两个负的(保证答案是正数)，实在没办法了才会考虑一正一负的情况(\(N=K的情况\))。我们排好序之后两头取，选大的。如果是偶数的话，把ans初始化为当前的最大值，注意如果当前最大值都是<0的(即全为负)，那么最后介个也是负数，用\(f\)标记一下。然后k变成偶数，按照偶数是做法写。

// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 9;
const int N = 2e5 + 10;
ll a[N];
int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int n,k; cin>>n>>k;
    for(int i = 1;i <= n; i++)
        cin>>a[i];
    sort(a+1,a+1+n);
    ll ans = 1;
    int l = 1,r = n;
    int f = 1;
    if(k % 2){
        ans *= a[r];
        if(ans < 0)
            f = -1;
        r--;
        k--;
    }
    
    while(k)
    {
        ll pre = a[l]*a[l+1];
        ll suf = a[r]*a[r-1];
        if(f * pre > f * suf)
            ans *= pre%mod,ans %= mod,l += 2;
        else ans *= suf%mod,ans %= mod,r -= 2;
        k -= 2;
    }
    cout<<ans<<"\n";

    return 0;
}

2.[P8625 蓝桥杯 2015 省 B] 生命之树

题意：对于一棵树，找到其点权和最大的一个连通分量（注意可以为空），输出这个连通分量的点权和。

思路：树形\(dp\)，考虑每个点为根\(u\)的情况下它的子树\(v\)最大点权和。

\(dp[u] += max(dp[v],0)\)

// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
int n,a[N];
vector<int>e[N];
ll dp[N];
void dfs(int u,int fa)
{
    //cout<<"u = "<<u<<"\n";
    dp[u] = a[u];
    for(auto v : e[u])
    {
        if(v == fa)continue;
        dfs(v,u);
        dp[u] += max(dp[v],0ll);
    }

}

int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
  
    cin>>n;
    for(int i = 1;i <= n; i++)
        cin>>a[i];
    for(int i = 1;i < n; i++)
    {
        int u,v; cin>>u>>v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs(1,0);
    ll ans = 0;
    for(int i = 1;i <= n; i++)
    {
        ans = max(ans,dp[i]);
    }
    cout<<ans<<"\n";
    return 0;
}

3.[P8782 蓝桥杯 2022 省 B] X 进制减法

题意：两个\(X\)进制数，求差最小值。最小为2进制。

思路：\(X\)进制是怎么求的呢？举个例子：最低数位为二进制，第二数位为十进制，第三数位为八进制，则\(X\)进制数\(321\)转化为十进制是什么呢？

\(a[i]\)数值：3 2 1

\(c[i]\)进制：8 10 2

\(d[i]\)权值：\(1\times2\times10\) \(1\times2\) 1

通式就是：\(d[i] = a[i]\prod_{k = 1}^{i-1}c[k](c[0] = 1)\)

那么对于\(X\)进制\(321\)转为\(10\)进制就是：\(20\times 3 + 2\times 2+1\times 1 = 65\)

好的了解了以上，我们来考虑本题。本题是要求差值最小。因为题目保证了\(A\ge B\),想要\(A-B\)的值尽量小，每一位的权值也要尽量小。因为是指数基本增长的，\(A\)变大会比\(B\)更快。如果想让每一位的权值尽量小，每一位的进制也得尽量小。那么我们考虑贪心，每一位的进制取\(max(a[i],b[i])+1\),如果\(<2\)的话置为\(2\)。记得开$long $ \(long\)。

// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
ll n,la,lb,a[N],b[N],c[N],d[N];
int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    cin>>n;
    cin>>la;
    for(int i = la;i >= 1; i--)
        cin>>a[i];
    cin>>lb;
    for(int i = lb;i >= 1; i--)
        cin>>b[i];
    for(int i = 1;i <= max(la,lb); i++)
    {
        c[i] = max(a[i],b[i])+1;
        if(c[i]<2)c[i] = 2;
    }
    d[1] = 1;
    for(int i = 2;i <= max(la,lb);i++)
        d[i] = (d[i-1]*c[i-1])%mod;
    ll t1 = 0,t2 = 0;
    for(int i = 1;i <= la;i++)
        t1 += (a[i]*d[i])%mod,t1 %= mod;

    for(int i = 1;i <= lb;i++)
        t2 += (b[i]*d[i])%mod,t2 %= mod;
    cout<<(t1-t2+mod)%mod<<"\n";
    
    return 0;
}

4.[P8683 蓝桥杯 2019 省 B] 后缀表达式

题意：给定 \(N\) 个加号、 \(M\) 个减号以及 \(N+M+1\) 个整数 \(A_1,A_2,\cdots,A_{N+M+1}\)，小明想知道在所有由这 \(N\) 个加号、 \(M\) 个减号以及 \(N+M+1\) 个整数凑出的合法的后缀表达式中，结果最大的是哪一个。

请你输出这个最大的结果。

例如使用 1 2 3 + -，则 2 3 + 1 - 这个后缀表达式结果是 \(4\)，是最大的。

思路：这题很有意思，想了很久。后缀表达式是可以加括号滴。

比如

0 2
1 2 3

答案应该是4。因为3-(1-2) = 4。如果直接贪心的话求出来是3-2-1 = 0。

那么怎么办哩？

我们先考虑简单的，如果全是加号，那么答案一定是直接全部加起来就行了。

那么如果有减号存在呢？

一个负数通过加括号和减号来变成正数

对于\(-a\)我们是不是可以\(-(a)\)变成正数。多个负数呢？比如\(a,b,c\)都是负数，那么\(-(a+b+c)\)就是正数了。

我们发现了什么？是不是只要有一个负号，我们就可以把若干个负数变成正数啦。我们考虑多加上大数，减去小数。我们考虑把max放首相，min放后面，构成以下表达式。

\(max-(min±①)±②\)

其他数：

  1. 正数 + ：放在②
  2. 负数 - ：放在②
  3. 正数 - : 放在①
  4. 负数 + ：放在①

我们发现无论怎么放都是正数，完美解决。

// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;

ll a[N];
int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int n,m; cin>>n>>m;
    int k = n+m+1;
    for(int i = 1;i <= k; i++)
        cin>>a[i];
    sort(a+1,a+1+k);
    ll ans = 0;
    if(m==0)
    {
        for(int i = 1;i <= k; i++)
            ans += a[i];
    }
    else{
        ans = a[k]-a[1];
        for(int i = 2;i < k; i++)
            ans += abs(a[i]);
    }
    cout<<ans<<"\n";
    return 0;
}

5.[P8783 蓝桥杯 2022 省 B] 统计子矩阵

题意：给定一个 \(N \times M\) 的矩阵 \(A\)，请你统计有多少个子矩阵 (最小 \(1 \times 1\), 最大 \(N \times M)\) 满足子矩阵中所有数的和不超过给定的整数 \(K\)。

思路：看见这个第一反应就是二维前缀和+枚举。枚举4维肯定是不行的，我就想枚举左上角和左下角的x再二分y。结果。。。还是TLE了hh。

// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int long long
const int mod = 1e9 + 7;
const int N = 5e2 + 10;
ll n,m,k;
ll a[N][N],s[N][N];
bool judge(int x1,int y1,int x2,int y2)
{
    ll sum = s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1];
    return sum <= k;
}
signed main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    cin>>n>>m>>k;
    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++)
            s[i][j] = s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];



    ll ans = 0;
    for(int i = 1;i <= n; i++)
    {
        for(int j = 1;j <= m; j++)
        {
            int last = m;
            for(int k = i;k <= n; k++)
            {
                int x1 = i,y1 = j;
                int x2 = k,y2;
                int l = j, r = last;
                while(l<=r)
                {
                    int mid = (l+r)>>1;
                    if(judge(x1,y1,x2,mid))l = mid+1;
                    else r = mid-1;
                }
                y2 = l-1;
                if(y2<y1)break;
                last = y2;
                ans += (y2-y1+1);
            }
        }
    }
    cout<<ans<<"\n";
    return 0;
}

以上代码只有80分。那么得把log优化掉怎么办哩。我们考虑双指针。

枚举\(x_1，x_2\),用双指针维护\(y_1和y_2\)

\(l\)表示\(y_1\)，\(r\)表示\(y_2\)。我们不断右移\(r\)，直到第一次不合法。那么当前\(r\)也不用再继续往后了，因为后面就更不行了，我们右移左指针\(l\)，直到第一个合法位置，同时保证\(l\le r\)。然后更新答案，加上\(r-l+1\)。

// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int long long
const int mod = 1e9 + 7;
const int N = 5e2 + 10;
ll n,m,k;
ll a[N][N],s[N][N];

signed main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    cin>>n>>m>>k;
    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++)
            s[i][j] = s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];


    ll ans = 0;
    for(int i = 1;i <= n; i++)//x1
    {
        for(int j = i;j <= n; j++)//x2
        {
            for(int l = 1,r = 1;r <= m; r++)//y1,y2
            {
                while(l <= r &&s[j][r] - s[i - 1][r] - s[j][l - 1] + s[i - 1][l - 1] > k)l++;
                ans += r-l+1;
            }
        }
    }
    cout<<ans<<"\n";
    return 0;
}

标签：const,int,ll,练习,cin,long,times,蓝桥
From： https://www.cnblogs.com/nannandbk/p/18007109

相关文章

  • redis+python练习小问题
     1、“cannot import name 'Redis' from 'redis'"//python文件名用了“redis.py”，改成其他的就好了。这个一定要注意，很容易犯这种错，想要做什么功能，就用这个功能命名。2、NameError:name 'redis' is not defined//我开始是fromredisimportRedis，改成importredis，......
  • 2.3 蓝桥杯练习3题
    2.3蓝桥杯练习3题1.[P9241蓝桥杯2023省B]飞机降落题意：\(N\)架飞机准备降落到某个只有一条跑道的机场。其中第\(i\)架飞机在\(T_{i}\)时刻到达机场上空，到达时它的剩余油料还可以继续盘旋\(D_{i}\)个单位时间，即它最早可以于\(T_{i}\)时刻开始降落，最晩可以于\(T_{i......
  • c语言小练习——字符串长度、拷贝、拼接、比较
    /* 使用c语言知识实现下面程序: 1,实现strlen函数的功能 2,实现strcpy函数的功能 3,实现strcat函数的功能 4,实现strcmp函数的功能 不允许使用已有的str函数*/1#define_CRT_SECURE_NO_WARNINGS2#include<stdio.h>3#include<string.h>4#include<stdbool.h>5#......
  • P5587 打字练习
    P5587打字练习打字练习题目描述R君在练习打字。有这样一个打字练习网站，给定一个范文和输入框，会根据你的输入计算准确率和打字速度。可以输入的字符有小写字母、空格和.（英文句号），输入字符后，光标也会跟着移动。输入的文本有多行，R君可以通过换行键来换行，换行后光标移动到下......
  • C++编程练习||创建一个名为Rational的类，进行分数运算。
    题目：创建一个名为Rational的类，进行分数运算。创建一个名为Rational的类，进行分数运算。用整数变量表示类的private数据－numerator（分子）和denominator（分母）。提供一个带默认值的构造函数，并且它应该以简化的形式保存分数。例如分数2/4应在对象中保存为numerator为1，denominator为2的形式。......
  • C++编程练习||Account类：创建一个名为Account的类，银行可以使用它表示客户的银行帐户||I
    1.Account类题目：创建一个名为Account的类，银行可以使用它表示客户的银行帐户。这个类应该包括一个类型为double的数据成员，表示帐户余额。这个类提供一个构造函数，它接受初始余额并用它初始化数据成员。这个构造函数应当确认初始余额的有效性，保证它大于或等于0。否则，余额应设置为0......
  • JAVA数组练习代码
    一维数组的有序插入思路代码点击查看代码importjava.util.Scanner;/***@authorLittleBear*@date2024-02-02-16:57*/publicclassseqInsertion{publicstaticvoidmain(String[]args){System.out.println("pleaseinputyournum:");......
  • 【2024.02.02】构图练习（糖水肖像）
    图源糖水日记作者的午饭饭，侵删采用摄影师泰罗所说的描绘法去观察每一张图的构图与线条可以观察到除非是夜景，一般来说感光度都会拉很低，避免噪点光圈值一般都会控制在2附近及以下，为了达到更好的的一个背景虚化效果说实话描绘了几张后感觉背景确实不是那么重要，只要控制好前景部分......
  • 2.1 蓝桥杯练习5题
    2.1蓝桥杯练习5题1.[P8623蓝桥杯2015省B]移动距离题意：X星球居民小区的楼房全是一样的，并且按矩阵样式排列。其楼房的编号为$1,2,3,\cdots$。当排满一行时，从下一行相邻的楼往反方向排号。比如：当小区排号宽度为\(6\)时，开始情形如下：12345612111098......
  • 洛谷 P8687 [蓝桥杯 2019 省 A] 糖果
    题意有\(m\)种口味，每次\(k\)颗一袋出售，给你\(n\)包均为\(k\)颗的糖果，求最少买几袋可以吃到所有口味的糖果。思路暴力对\(n\)包糖果做组合。如果找到其中一种包含了所有口味，将所有满足的方案取糖果包数最小即可。时间复杂度\(\mathcal{O(2^n)}\)。正解考虑状......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99