AtCoder Beginner Contest 347 A~F

AtCoder Beginner Contest 347 A~F - 知乎 (zhihu.com)

Tasks - AtCoder Beginner Contest 347

A.Divisible(循环)

代码

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

void solve() {
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        if (a % k == 0) {
            cout << a / k << ' ';
        }
    }
    cout << endl;
}

int main() {
    solve();
    return 0;
}

B.Substring(枚举,set)

代码

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

set<string> St;
void solve() {
    string s;
    cin >> s;
    int n = s.size();
    for (int i = 0; i < n; i++) {
        string str = "";
        for (int j = i; j < n; j++) {
            str += s[j];
            St.insert(str);
        }
    }
    cout << St.size() << endl;
}

int main() {
    solve();
    return 0;
}

C.Ideal Holidays(哈希)

分析

坑点:没有告诉你当天是星期几,那么我们可以认为,只要存在一种方案使得计划全部成立即可,开始是星期几我们可以随意决定。

由于星期数是循环的,即以�+�为一个周期进行循环,那么我们可以利用类似哈希表的思想,让所有的天数通过取模落在�+�天内,并记录所有取模后的结果。

然后,只要满足以下两个条件之一,就表示一定存在合法的方案:

条件1:取模后的最大最小值之差小于�

如下图,由于我们可以决定开始时是星期几,那么只要取模后的区间大小小于等于�(即取模后的最大最小值之差小于�),那么就可以将区间最小值修改为一周的开始,此时所有取模后的结果均会落在前�天内。

条件2:将数组排序,存在数组中相邻两项之差大于�

如下图,虽然最大最小值之差很大,但由于中间空出了一段长度大于等于�的区间,那么通过循环让这段空出的区间来到后半部分,那么所有计划也会落在前�天内。

如果上述两种情况均不满足,那么就表示当前情况无解。

代码

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

vector<int> v;

void solve() {
    ll n, a, b;
    cin >> n >> a >> b;
    ll minn = 1e18, maxn = -1e18;
    for (int i = 0; i < n; i++) {
        ll t;
        cin >> t;
        t--;
        t %= (a + b);
        v.push_back(t);
        maxn = max(maxn, t);
        minn = min(minn, t);
    }
    sort(v.begin(), v.end());
    for (int i = 1; i < n; i++) {
        if (v[i] - v[i - 1] > b) {
            cout << "Yes" << endl;
            return;
        }
    }
    if (maxn - minn >= a) cout << "No" << endl;
    else cout << "Yes" << endl;
}

int main() {
    solve();
    return 0;
}

D.Popcount and XOR(思维)

代码

#include<bits/stdc++.h>

typedef long long LL;
using namespace std;

int x[105], y[105], c[105];

void solve() {
    LL a, b, C;
    cin >> a >> b >> C;
    int pos = 0, cnt = 0;
    while (C) {
        if (C & 1) cnt++;
        c[pos++] = C % 2;
        C /= 2;
    }
    for (int i = 0; i <= 62; i++) {
        if (c[i] == 1) {
            if (a > b) {
                x[i] = 1;
                a--;
            } else {
                y[i] = 1;
                b--;
            }
        }
    }
    for (int i = 0; i <= 62; i++) {
        if (x[i] + y[i] == 0 && a > 0 && b > 0) {
            a--, b--;
            x[i] = y[i] = 1;
        }
    }
    if (a != 0 || b != 0) {
        cout << -1 << endl;
        return;
    }
    LL X = 0, Y = 0;
    for (int i = 62; i >= 0; i--) {
        X = X * 2 + x[i];
        Y = Y * 2 + y[i];
    }
    cout << X << ' ' << Y << endl;
}

int main() {
    solve();
    return 0;
}

E.Set Add Query

代码

#include<bits/stdc++.h>

typedef long long LL;
using namespace std;
const int N = 2e5 + 5e2;

set<int> S;

LL n, q, sz[N], pre[N], ans[N];
vector<int> in[N], out[N];

void solve() {
    cin >> n >> q;
    for (int i = 1; i <= q; i++) {
        int x;
        cin >> x;
        if (S.find(x) == S.end()) {
            S.insert(x);
            in[x].push_back(i);
        } else {
            S.erase(x);
            out[x].push_back(i);
        }
        sz[i] = S.size();
        pre[i] = pre[i - 1] + sz[i];
    }
    for (int i = 1; i <= n; i++) out[i].push_back(q + 1);
    for (int i = 1; i <= n; i++) {
        int len = in[i].size();
        for (int j = 0; j < len; j++) {
            ans[i] += pre[out[i][j] - 1] - pre[in[i][j] - 1];
        }
        cout << ans[i] << ' ';
    }
    cout << endl;
}

int main() {
    solve();
    return 0;
}

F.Non-overlapping Squares(思维)

分析

对于所有的方案,必然可以将三个网格的位置分为以下六种。

代码(来自官方题解)

//from atcoder Offcial
#include <iostream>
#include <vector>
#include <ranges>
#include <numeric>
#include <algorithm>

int main() {
    using namespace std;
    static constexpr auto chmax{[](auto &&x, const auto &y) {
        if (x < y) x = y;
        return x;
    }};
    static constexpr auto max{[](const auto &x, const auto &y) {
        if (x < y) return y;
        return x;
    }};

    unsigned N, M;
    cin >> N >> M;

    // sum[i][j] := the sum of the M x M square whose top-left cell is (i, j)
    auto sum{[N, M] {
        vector A(N + 1, vector<unsigned long>(N + 1));
        for (auto &&row: A | views::take(N))
            for (auto &&a: row | views::take(N))
                cin >> a;

        // Let A[i][j] ← ∑_{i≤k,j≤l} A[k][l]
        for (unsigned row_index{N}; auto &&row : A | views::reverse){
        inclusive_scan(rbegin(row), rend(row), rbegin(row), plus<>{});
        if (row_index < N)
            ranges::transform(row, A[row_index + 1], begin(row), plus<>{});
        --row_index;
    }

        // sum[i][j] = A[i][j] - A[i+M][j] - A[i][j+M] + A[i+M][j+M]
        vector sum(N - M + 1, vector<unsigned long>(N - M + 1));
        for (unsigned i{}; i <= N - M; ++i)
            for (unsigned j{}; j <= N - M; ++j)
                sum[i][j] = A[i][j] - A[i + M][j] - A[i][j + M] + A[i + M][j + M];
        return sum;
    }()};

    // cumulative max of sum[i][j] from the top-left
    // m[i][j] = max_{k≤i,l≤j} sum[k][l]
    const auto max_UL{[](auto cells) {
        for (unsigned row_index{}; auto &&row : cells){
        inclusive_scan(begin(row), end(row), begin(row), max);
        if (row_index)
            ranges::transform(row, cells[row_index - 1], begin(row), max);
        ++row_index;
    }
        return cells;
    }};

    // flip the board horizontally
    const auto h_flip{[](auto &&cells) {
        for (auto &&row: cells)
            ranges::reverse(row);
        return cells;
    }};
    // flip the board vertically
    const auto v_flip{[](auto &&cells) {
        ranges::reverse(cells);
        return cells;
    }};

    const auto upper_left{max_UL(sum)}; // cumulative max from the top-left
    h_flip(sum); // flip horizontally
    const auto upper_right{h_flip(max_UL(sum))}; // cumulative max from the top-right
    v_flip(sum); // flip vertically
    const auto lower_right{h_flip(v_flip(max_UL(sum)))}; // cumulative max from the bottom-right
    h_flip(sum); // flip vertically
    const auto lower_left{v_flip(max_UL(sum))}; // cumulative max from the bottom-left
    v_flip(sum); // return to the original state

    unsigned long ans{};

    // Fix a square
    for (unsigned i{}; i < N - M + 1; ++i)
        for (unsigned j{}; j < N - M + 1; ++j) {
            if (M <= i && i + M < N - M + 1) // three squares arranged vertically; fix the center square
                chmax(ans, upper_left[i - M].back() + sum[i][j] + lower_right[i + M].front());
            if (M <= j && j + M < N - M + 1) // three squares arranged horizontally; fix the center square
                chmax(ans, upper_left.back()[j - M] + sum[i][j] + lower_right.front()[j + M]);
            if (M <= i) { // T-shaped
                if (j + M < N - M + 1) // bottom left
                    chmax(ans, upper_left[i - M].back() + lower_right[i][j + M] + sum[i][j]);
                if (M <= j) // bottom right
                    chmax(ans, upper_left[i - M].back() + lower_left[i][j - M] + sum[i][j]);
            }
            if (M <= j) { // ト-shaped
                if (i + M < N - M + 1) // bottom right
                    chmax(ans, lower_left.front()[j - M] + lower_right[i + M][j] + sum[i][j]);
                if (M <= i) // top right
                    chmax(ans, lower_left.front()[j - M] + upper_right[i - M][j] + sum[i][j]);
            }
            if (i + M < N - M + 1) { // 亠 -shaped
                if (j + M < N - M + 1) // top-left
                    chmax(ans, lower_right[i + M].front() + upper_right[i][j + M] + sum[i][j]);
                if (M <= j) // top-right
                    chmax(ans, lower_right[i + M].front() + upper_left[i][j - M] + sum[i][j]);

            }
            if (j + M < N - M + 1) { // ㅓ -shaped
                if (i + M < N - M + 1) // top-left
                    chmax(ans, upper_right.back()[j + M] + lower_left[i + M][j] + sum[i][j]);
                if (M <= i) // bottom-left
                    chmax(ans, upper_right.back()[j + M] + upper_left[i - M][j] + sum[i][j]);
            }
        }

    cout << ans << endl;
    return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/515201.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

如何申请Telegram机器人 | 推送通知

一、前言 利用Telegram机器人推送通知&#xff0c;需要在环境变量填入正确的TG_BOT_TOKEN以及TG_USER_ID&#xff0c;以下教程简明阐述如何获取Token以及UserID 二、获取步骤 1、首先在Telegram上搜索BotFather机器人。需要注意的是&#xff0c;搜索结果中选择ID为BotFather…

基于向量数据库搭建自己的搜索引擎

前言【基于chatbot】 厌倦了商业搜索引擎搜索引擎没完没了的广告&#xff0c;很多时候&#xff0c;只是需要精准高效地检索信息&#xff0c;而不是和商业广告“斗智斗勇”。以前主要是借助爬虫工具&#xff0c;而随着技术的进步&#xff0c;现在有了更多更方便的解决方案&…

Maven--lib分离的打包方式

就是把lib包和source源码分开打包。优势就是&#xff0c;面对频繁更新的应用场景时&#xff0c;可以只更新源码包&#xff08;当然&#xff0c;前提是你的依赖没有增减&#xff09;。尤其是使用jenkins更新项目时&#xff0c;会省去很多时间吧&#xff1f; 不同项目的 lib之间不…

【C++练级之路】【Lv.18】哈希表(哈希映射,光速查找的魔法)

快乐的流畅&#xff1a;个人主页 个人专栏&#xff1a;《算法神殿》《数据结构世界》《进击的C》 远方有一堆篝火&#xff0c;在为久候之人燃烧&#xff01; 文章目录 引言一、哈希1.1 哈希概念1.2 哈希函数1.3 哈希冲突 二、闭散列2.1 数据类型2.2 成员变量2.3 默认成员函数2.…

保研线性代数复习3

一.基底&#xff08;Basis&#xff09; 1.什么是生成集&#xff08;Generating Set&#xff09;&#xff1f;什么是张成空间&#xff08;Span&#xff09;&#xff1f; 存在向量空间V(V&#xff0c;&#xff0c;*)&#xff0c;和向量集&#xff08;xi是所说的列向量&#xff…

【软件工程】概要设计

1. 导言 1.1 目的 该文档的目的是描述学生成绩管理系统的概要设计&#xff0c;其主要内容包括&#xff1a; 系统功能简介 系统结构简介 系统接口设计 数据设计 模块设计 界面设计 本文的预期读者是&#xff1a; 项目开发人员 项目管理人员 项目评测人员&#xff08;…

算法设计与分析实验报告python实现(串匹配问题、采用分治法求解最大连续子序列和问题、用分治策略求众数问题、最近点对问题)

一、 实验目的 1&#xff0e;加深学生对算法设计方法的基本思想、基本步骤、基本方法的理解与掌握&#xff1b; 2&#xff0e;提高学生利用课堂所学知识解决实际问题的能力&#xff1b; 3&#xff0e;提高学生综合应用所学知识解决实际问题的能力。 二、实验任务 1、串匹配问…

Docker安装mysql并且设置主从

Docker安装部署mysql 下载镜像 docker pull mysql:5.7.35查看镜像 docker images启动 直接启动不挂载文件 docker run -p 3306:3306 --name mysql -e MYSQL_ROOT_PASSWORD123456 -d mysql:5.7.35挂载文件 docker run -p 3306:3306 --name mysql \ -v /usr/local/docker/m…

正则表达式与JSON序列化:去除JavaScript对象中的下划线键名

&#x1f31f; 前言 欢迎来到我的技术小宇宙&#xff01;&#x1f30c; 这里不仅是我记录技术点滴的后花园&#xff0c;也是我分享学习心得和项目经验的乐园。&#x1f4da; 无论你是技术小白还是资深大牛&#xff0c;这里总有一些内容能触动你的好奇心。&#x1f50d; &#x…

【Java EE】关于Maven

文章目录 &#x1f38d;什么是Maven&#x1f334;为什么要学Maven&#x1f332;创建⼀个Maven项目&#x1f333;Maven核心功能&#x1f338;项目构建&#x1f338;依赖管理 &#x1f340;Maven Help插件&#x1f384;Maven 仓库&#x1f338;本地仓库&#x1f338;私服 ⭕总结 …

STM32G系 编程连接不上目标板,也有可能是软件不兼容。

由于一直用的老版本STM32 ST-LINK Utility 4.20 &#xff0c;找遍了所有问题&#xff0c;SWD就是连不上目标板。 电源脚 VDDA 地线&#xff0c;SWD的四条线&#xff0c;还是不行&#xff0c;浪费了一天&#xff0c;第二天才想起&#xff0c;是不是G系升级了 SWD协议。结果下载…

从汇编看函数调用

文章目录 函数调用流程栈相关寄存器及的作用简介寄存器功能指令功能 栈函数的括号{}正括号反括号 参数传递传值&#xff0c;变量不可改传指针&#xff0c;变量可改C 传引用 函数调用实例 函数调用流程 目标&#xff1a;函数调用前后栈保持不变 保存main函数的寄存器上下文移…

【HTML】简单制作一个3D动画效果重叠圆环

目录 前言 开始 HTML部分 CSS部分 效果图 总结 前言 无需多言&#xff0c;本文将详细介绍一段代码&#xff0c;具体内容如下&#xff1a; 开始 首先新建文件夹&#xff0c;创建两个文本文档&#xff0c;其中HTML的文件名改为[index.html]&#xff0c;CSS的…

Tensorflow2.0笔记 - 自定义Layer和Model实现CIFAR10数据集的训练

本笔记记录使用自定义Layer和Model来做CIFAR10数据集的训练。 CIFAR10数据集下载&#xff1a; https://www.cs.toronto.edu/~kriz/cifar-10-python.tar.gz 自定义的Layer和Model实现较为简单&#xff0c;参数量较少&#xff0c;并且没有卷积层和dropout等&#xff0c;最终准确率…

Java—抽象方法与接口

声明&#xff1a;以下内容是根据B站黑马程序员的Java课程&#xff0b;博主自己的理解整理而成&#xff0c;课程很好&#xff0c;适合初学者学习。 关于此类题目&#xff0c;重要的是识别出用什么来实现&#xff0c;到底是接口还是抽象方法&#xff0c;还是共有的属性等等&…

医用三维影像PACS系统源码 一套成熟的PACS系统应具备哪些核心要素?

医用三维影像PACS系统源码 一套成熟的PACS系统应具备哪些核心要素&#xff1f; PACS及影像存取与传输系统”( Picture Archiving and Communication System)&#xff0c;为以实现医学影像数字化存储、诊断为核心任务&#xff0c;从医学影像设备&#xff08;如CT、CR、DR、MR、…

ZZS-7/1G212分合闸电源综合控制装置 220VAC 板前接线 JOSEF约瑟

系列型号&#xff1a; ZZS-7G/1分闸、合闸、电源监视综合控制装置&#xff1b; ZZS-7G/11分闸、合闸、电源监视综合控制装置&#xff1b; ZZS-7G/23分闸、合闸、电源监视综合控制装置&#xff1b; ZZS-7G/24分闸、合闸、电源监视综合控制装置&#xff1b; ZZS-7/1G11分闸、合闸…

21.兼容性测试

考试频率低&#xff1b; 一般考兼容性测试会结合web测试&#xff1b;&#xff08;兼容性矩阵&#xff09; 主要议题&#xff1a; 1.兼容性测试概述 2.硬件兼容性测试 最低配置不讲究工作负载&#xff0c;意思是软件能够运行的最低要求环境&#xff1b; 推荐配置&#xff0c…

修复503 Service Unavailable Error问题

近期我们网网站经常出现503 Service Unavailable Error&#xff0c;在此之前我们的网站从未出现过这种问题&#xff0c;我们向虚拟主机提供商Hostease咨询后&#xff0c;了解到503 Service Unavailable错误是指服务器暂时无法处理请求&#xff0c;通常是由于服务器过载、维护、…

Python数据结构与算法——数据结构(链表、哈希表、树)

目录 链表 链表介绍 创建和遍历链表 链表节点插入和删除 双链表 链表总结——复杂度分析 哈希表(散列表) 哈希表介绍 哈希冲突 哈希表实现 哈希表应用 树 树 树的示例——模拟文件系统 二叉树 二叉树的链式存储 二叉树的遍历 二叉搜索树 插入 查询 删除 AVL树 …