蓝桥杯 第三场 小白入门赛

这篇具有很好参考价值的文章主要介绍了蓝桥杯 第三场 小白入门赛。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

召唤神坤

  • 有意思🤔(ikun)。
  • 虽然是第一题但也要配得上神坤的身份。

思路1

  • 枚举分母,选择一个数据结构来选出分母两侧最大的两个数做分子。
  • 2s常数大些也无碍。
  • 我选择好写的ST表

思路2

  • 写两个 d p dp dp 分别表示 1 1 1 i i i 的最大值, i i i n n n 的最大值。再枚举。
  • 这个不放码了看的别人的思路。
signed main() {

    int T = 1;
//    T = read();
    while (T--) {
        int n = read();
        vector<int> a(n + 1), logn(n + 1);
        vector<vector<int>> f(n + 1, vector<int>(30));
        for (int i = 1; i <= n; ++i) f[i][0] = a[i] = read();
        logn[0] = -1;
        for (int i = 1; i <= n; ++i) logn[i] = logn[i >> 1] + 1;
        for (int j = 1; j <= logn[n]; ++j) {
            for (int i = 1; i + (1 << j) - 1 <= n; ++i) {
                f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
            }
        }
        int ans = 0;
        for (int i = 2; i < n; ++i) {
            int l = 1, r = i - 1, s = logn[r - l + 1];
            int wi = max(f[l][s], f[r - (1 << s) + 1][s]);
            l = i + 1, r = n, s = logn[r - l + 1];
            int wk = max(f[l][s], f[r - (1 << s) + 1][s]);
            ans = max(ans, (wi + wk) / a[i]);
        }
        write(ans);
    }
    return 0;
}

聪明的交换策略

分析

  • 依据题意就是要么 0 0 0 1 1 1 右,要么 1 1 1 0 0 0 右。
  • 考虑 0 0 0 左还是 0 0 0 右即可。考虑 1 1 1 也行一样的。
signed main() {

    int T = 1;
//    T = read();
    while (T--) {
        int n = read();
        string s; cin >> s;
        vector<int> pos;
        for (int i = 0; i < s.size(); ++i) {
            if (s[i] ^ '1') pos.push_back(i);
        }
        int ans = 1e17, tmp1 = 0, tmp2 = 0;
        for (int i = 0; i < pos.size(); ++i) tmp1 += pos[i] - i;
        ans = min(ans, tmp1);
        for (int i = pos.size() - 1, j = n - 1; i >= 0; --i, --j) tmp2 += j - pos[i];
        ans = min(ans, tmp2);
        write(ans);
    }
    return 0;
}

怪兽突击

ps:总觉得codeforces做过。。

思路

  • 枚举每个 i i i (当然要小于等于 k k k )。
signed main() {

    int T = 1;
//    T = read();
    while (T--) {
        int n = read(), k = read();
        vector<int> a(n + 1), b(n + 1);
        for (int i = 1; i <= n; ++i) a[i] = read();
        for (int i = 1; i <= n; ++i) b[i] = read();
        priority_queue<int, vector<int>, greater<int>> pq;
        int ans = 1e17, cnt = 0;
        for (int i = 1; i <= n && i <= k; ++i) {
            cnt += a[i];
            pq.push(a[i] + b[i]);
            ans = min(ans, cnt + (k - i) * pq.top());
        }
        write(ans);
    }
    return 0;
}

蓝桥快打

思路

  • 根据 A , C A,C A,C 可以得出攻击次数的范围, B ≤ n ⋅ x B\leq n\cdot x Bnx
signed main() {

    int T = 1;
    T = read();
    while (T--) {
        int a = read(), b = read(), c = read();
        int r = a / c + (a % c > 0);
        writeln(b / r + (b % r > 0));
    }
    return 0;
}

奇怪的段

思路

  • d p dp dp
  • 方程: d p i = m a x ( d p i − 1 , j , d p i − 1 , j − 1 ) + a i ⋅ p j dp_i=max(dp_{i-1,j},dp_{i-1,j-1})+a_i\cdot p_j dpi=max(dpi1,j,dpi1,j1)+aipj
  • 注意有负数
signed main() {

    int T = 1;
//    T = read();
    while (T--) {
        int n = read(), k = read();
        vector<int> a(n + 1), p(k + 1);
        vector<vector<int>> dp(n + 1, vector<int>(201, -1e15));
        dp[0][0] = 0;
        for (int i = 1; i <= n; ++i) a[i] = read();
        for (int i = 1; i <= k; ++i) p[i] = read();
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= k; ++j) {
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + a[i] * p[j];
            }
        }
        write(dp[n][k]);
    }
    return 0;
}

小蓝的反击

ps:是个区间求解问题,涉及基础数论。

思路

  • 枚举每一个 i i i ,找到最小位置 j j j 满足 A ∣ ∏ k = i j 1 a k ,    B ∣ ∏ k = i j 2 a k A| \prod_{k=i}^{j_1}a_k,\;B|\prod_{k=i}^{j_2}a_k Ak=ij1ak,Bk=ij2ak
  • 如果 j 1 j_1 j1 不存在那么往后再也不能整除 A A A 了。如果 j 2 j_2 j2 不存在,那么从 j 1 j_1 j1 n n n 都能整出 A A A 。都存在只有 j 2 > j 1 j_2 >j_1 j2>j1 才对答案有贡献。
  • A , B A,B A,B 质因数分解记录因子和各因子数量。
  • A , B A,B A,B 每一个因子做前缀和。
  • 二分枚举区间询问是否存在(该有的因子和数量都要满足)。

ps:前缀和那儿显然是个二维的,试想质因数分解有可能出现因数很大的情况,第二维是因数大小会 M E L MEL MEL ,所以第二维应该为数量,而数量最多是10(前十个质数相乘已经 > 1 0 9 >10^9 >109 )。看题解有个 d p dp dp 的,巨,我不会。文章来源地址https://www.toymoban.com/news/detail-797945.html

signed main() {
    auto getFactor = [&] (int v) {
        vector<pii> vec;
        for (int i = 2; i <= v / i; ++i) {
            if (!(v % i)) {
                vec.push_back({i, 0});
                while (!(v % i)) v /= i, ++vec.back().second;
            }
        }
        if (v ^ 1) vec.push_back({v, 1});
        return vec;
    };
    int T = 1;
//    T = read();
    while (T--) {
        int n = read(), a = read(), b = read();
        auto vec1 = getFactor(a), vec2 = getFactor(b);
        vector<vector<int>> prefa(n + 1, vector<int>(10)), prefb(n + 1, vector<int>(10));
        for (int i = 1; i <= n; ++i) {
            int u = read();
            for (int j = 0; j < vec1.size(); ++j) {
                int tmp = u, v = vec1[j].first;
                while (!(tmp % v)) {
                    ++prefa[i][j];
                    tmp /= v;
                }
                prefa[i][j] += prefa[i - 1][j];
            }
            for (int j = 0; j < vec2.size(); ++j) {
                int tmp = u, v = vec2[j].first;
                while (!(tmp % v)) {
                    ++prefb[i][j];
                    tmp /= v;
                }
                prefb[i][j] += prefb[i - 1][j];
            }
        }
        auto find = [&] (int i, int j, int cnt, int op) {
            int l = i, r = n, tmp = op? prefb[i - 1][j]: prefa[i - 1][j];
            int ans = -1;
            while (l <= r) {
                int mid = (l + r) >> 1, v = op? prefb[mid][j]: prefa[mid][j];
                if (v - tmp >= cnt) ans = mid, r = mid - 1;
                else l = mid + 1;
            }
            return ans;
        };
        long long int ans = 0;
        for (int i = 1; i <= n; ++i) {
            int pos1 = i;
            for (int j = 0; j < vec1.size(); ++j) {
                int pos = find(i, j, vec1[j].second, 0);
                if (pos ^ -1) pos1 = max(pos1, pos);
                else {
                    pos1 = -1;
                    break;
                }
            }
            if (pos1 == -1) break;
            int pos2 = i;
            for (int j = 0; j < vec2.size(); ++j) {
                int pos = find(i, j, vec2[j].second, 1);
                if (pos ^ -1) pos2 = max(pos2, pos);
                else {
                    pos2 = -1;
                    break;
                }
            }
            if (pos2 == -1) ans += (n - pos1 + 1) * 1ll;
            else if (pos2 > pos1) ans += (pos2 - pos1) * 1ll;
        }
        // write(ans);
        cout << ans;
    }
    return 0;
}

到了这里,关于蓝桥杯 第三场 小白入门赛的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【蓝桥杯】信号覆盖范围——BFS(java题解)

    小蓝负责一块区域的信号塔安装,整块区域是一个长方形区域,建立坐标轴后,西南角坐标为 (0, 0), 东南角坐标为 (W, 0), 西北角坐标为 (0, H), 东北角坐标为 (W, H)。其中 W, H 都是整数。 他在 n 个位置设置了信号塔,每个信号塔可以覆盖以自己为圆心,半径为 R 的圆形(包

    2023年04月09日
    浏览(41)
  • 零基础小白怎么准备蓝桥杯-蓝桥杯竞赛经验分享

    博主在蓝桥杯中获得过十四届Java B 组的省一国二,本文为大家介绍一下蓝桥杯并分享一下自己的参赛经验。 ​ 蓝桥杯全称《蓝桥杯全国软件和信息技术专业人才大赛》,是由国信蓝桥和工信部举办的全国性IT学科赛事。全国1200余所高校参赛,累计参赛人数超过40万人。蓝桥

    2024年02月04日
    浏览(51)
  • 2020第11届蓝桥杯矩阵的真·详细题解

    本文章主要面向算法初学者、蓝桥杯参赛者。 今天重温一手第十三届的统计子矩阵,搜索的时候发现了第十一届的矩阵题,然后看了下网上的文章,好家伙! 全网对于此题没有高质量的文章和解答思路,全是贴个代码最多说一两句别的话,代码里注释都没几行,对于初学者

    2023年04月16日
    浏览(40)
  • 第十四届蓝桥杯编程题部分代码题解

    C. 冶炼金属 最大值就是取 a / b a / b a / b 的最小值,最小值就是二分找到满足 m i d ∗ ( b i + 1 ) ≥ a i mid * (b_i + 1) ≥ a_i mi d ∗ ( b i ​ + 1 ) ≥ a i ​ 的最小值 D. 飞机降落 全排列枚举所有降落方案,然后判断即可 E. 接龙数列 状态定义: f [ i , j ] f[i, j] f [ i , j ] 为前 i i i 个数,

    2023年04月11日
    浏览(43)
  • 第14届蓝桥杯C++A组题解

    不会写 枚举第i行 二进制枚举状态 然后check(i)是否合法,如果合法就dfs(i+1) check是核心 判断第上一行是否==A[i][j] 判断第i行是否小于等于A且,c+3=A 判断下一行是否小于等于A且,c+6=A 按位做就好了 比如 5 1 2 3 4 5 bit=0 数组变成 10101 bit=1 数组变成 01100 单独考虑bit=0,模2意义

    2023年04月09日
    浏览(31)
  • 入门小白,使用ubuntu,使用docker或者docker-compose搭建家庭个人网盘nextcloud,外网通过IPV6域名访问。第三篇--配置 ddns-go 以及 dynv6

    由于在第一篇中说过,放弃使用ipv4 连接 优点,家里设备都可以拥有一个 ipv6公网地址 缺点,地址会变。。。 缺点,公司网络网络下,可能访问不到。。。 所以采用ddns-go 配置 dynv6的方案 即使设备的ipv6地址变化了,也不用你做额外的事,一切交给系统就行。 不用写代码,不

    2024年02月06日
    浏览(51)
  • 第十一届蓝桥杯国赛JavaB组题解

    思路: 枚举 1 到 2020 的每个数,依次判断即可。 代码: 解法一:(比较慢但是容易想) b f s bfs b f s ,先将给出的点加入队列中,并且加到集合里。记录扩散的步数,初始化为2020,然后对队列中的每一个同一层的节点在四个方向上扩散,当扩散的点不在集合里时,把它加到

    2024年02月08日
    浏览(55)
  • 2022蓝桥杯C++B组国赛真题题解

    目录 A:2022 B:钟表 C:卡牌 D:最大数字 E:出差 F:费用报销 G:故障 H:机房 I:齿轮 J:搬砖 问题描述 将 2022 拆分成 10 个互不相同的正整数之和, 总共有多少种拆分方法? 注意交换顺序视为同一种方法, 例如 2022=1000+1022 和 1022+1000 就视为同一种方法。 答案提交 这是一道结果填空的

    2024年02月06日
    浏览(44)
  • 2019 第十届蓝桥杯省赛A组题解

    本次试题难度(对专业算法竞赛选手来说)不大,但是考验基本的编程基本功和数学思维。估计完成80%即可获得省一进入决赛(根据一些公开的反馈,如果有准确数据请告诉我),因此更多的是需要细心。 至于C/C++还是Java我觉得不重要,因为题目除了顺序有点不同,内容是一

    2023年04月09日
    浏览(47)
  • 蓝桥杯31天真题冲刺|题解报告|第二十八天

    大家好,我是snippet,今天是我们刷题的第二十八天,距离我们刷题活动结束也就只有几天了,最近刷题有点迷茫了,下面是我今天的题解 目录 一、路标设置 题目链接:P3853 [TJOI2007]路标设置 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 题目内容: 解题思路: 代码: 题目链接

    2023年04月08日
    浏览(35)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包