Codeforces Round 948 (Div. 2) A~D

A. Little Nikita (思维)

题意:

A A A决定用一些立方体建一座塔。一开始,塔上没有任何立方体。在一次移动中,小 A A A要么正好把 1 1 1 个立方体放到塔顶,要么正好从塔顶移走 1 1 1 个立方体。存不存在一种可能使得在走了 n n n 步之后,塔顶正好有 m m m 个立方体?

分析:

n ≥ m n \ge m nm并且 n , m n,m n,m奇偶性一样才符合题意,否则不可以。

代码:

#include <bits/stdc++.h>

using namespace std;

int main() {
    int T;
    cin >> T;
    while (T--) {
        int n, m;
        cin >> n >> m;
        if (n >= m && (n - m) % 2 == 0) {
            cout << "Yes" << endl;
        } else {
            cout << "No" << endl;
        }
    }
    return 0;
}

B.Binary Colouring (思维)

题意:

给你一个正整数 x x x 。请找出下列条件成立的任意整数数组 a 0 , a 1 , … , a n − 1 a_0, a_1, \ldots, a_{n-1} a0,a1,,an1

  • 1 ≤ n ≤ 32 1 \le n \le 32 1n32 ,
  • a i a_i ai 1 1 1 0 0 0 − 1 -1 1
  • x = ∑ i = 0 n − 1 a i ⋅ 2 i x = \displaystyle{\sum_{i=0}^{n - 1}{a_i \cdot 2^i}} x=i=0n1ai2i ,
  • 不存在同时满足 a i ≠ 0 a_{i} \neq 0 ai=0 a i + 1 ≠ 0 a_{i + 1} \neq 0 ai+1=0 的下标 i i i

保证存在一个有效的数组。

分析:

如果没有相邻两项必有一项为 0 0 0的限制,那么就是写出 n n n的二进制形式。如果 n n n的二进制有大于等于 2 2 2 1 1 1相邻,将最低位置为 − 1 -1 1,最高位的后一项置为 1 1 1,双指针判断即可。

代码:

#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;

int main() {
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        vector<int> a(32), b(32);
        for (int i = 0; i <= 31; i++) {
            if (n >> i & 1) {
                a[i] = 1;
                b[i] = 1;
            } else {
                a[i] = 0;
                b[i] = 0;
            }
        }
        for (int i = 0; i < 32;) {
            if (a[i] != 0 && b[i + 1] != 0) {
                int pos = i;
                while (a[i] != 0 && i <= 31) {
                    i++;
                    b[i] = 0;
                }
                a[i] = 1;
                b[pos] = -1;
                b[i] = 1;
                if (i == 32)
                    break;
            } else {
                i++;
                if (i == 32)
                    break;
            }
        }
        cout << 32 << endl;
        for (int i = 0; i < 32; i++) {
            cout << b[i] << " ";
        }
        cout << endl;
    }
    return 0;
}

C.Nikita and LCM(数学)

题意:

假设有一个长度为 n n n 的整数数组 a a a 。如果数组的一个子序列的最小公倍数 ( L C M ) (LCM) (LCM)不包含在 a a a 中,称该子序列为特殊序列。空子序列的 L C M LCM LCM 等于 0 0 0
询问 a a a 的最长特殊子序列的长度是多少?

分析:

如果所有数的最小公倍数大于数组中最大值,那么就可以全选。否则数组中所有数一定都是最小公倍数的约数,那么我们就能保证最终选出来的数组的最小公倍数一定也是其约数。那么我们枚举可能的约数然后判断一遍即可。

代码:

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
const int mod = 998244353;

LL gcd(LL a, LL b) {
    return b == 0 ? a : gcd(b, a % b);
}

LL lcm(LL a, LL b) {
    return a * b / gcd(a, b);
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; i++)
            cin >> a[i];
        sort(a.begin(), a.end());
        set<int> tmp;
        for (int i = 0; i < n; i++)
            tmp.insert(a[i]);
        bool ok = 0;
        for (int i = 0; i < n; i++) {
            if (a[n - 1] % a[i])
                ok = 1;
        }
        if (ok) {
            cout << n << endl;
            continue;
        }
        int ans = 0;
        auto check = [&](int x) -> int {
            if (tmp.find(x) != tmp.end())
                return 0;
            int g = 1;
            int cnt = 0;
            for (int i = 0; i < n; i++) {
                int num = lcm(g, a[i]);
                if (x % num)
                    continue;
                cnt++;
                g = num;
            }
            if (g != x)
                return 0;
            return cnt;
        };
        for (int i = 1; i * i <= a[n - 1]; i++) {
            if (a[n - 1] % i)
                continue;
            ans = max(ans, check(i));
            ans = max(ans, check(a[n - 1] / i));
        }
        cout << ans << endl;
    }
    return 0;
}

D.XORificator (字符串)

题意:

给一个仅由 0 0 0 1 1 1组成 n × m n \times m n×m 矩阵。你可以反转一次所选行中的所有值。规定矩阵中的一列如果正好包含一个 1 1 1,则被视为特殊列。在至多进行一次操作的情况下,请找出最多有多少列可以被特殊化。

分析:

我们发现对于每一列,若它们对答案有贡献,一共有 n n n种情况,且这 n n n种情况一定各不相同,那么我们把各列的这些情况全部记录下来,同时记录出现次数,记作 c n t cnt cnt
我们将字符串记作哈希值,那么答案就是 c n t cnt cnt 中的最大值。这样我们同时也知道答案对应的字符串哈希值 n u m num num,我们重新枚举各列对答案的贡献 t m p tmp tmp,当 t m p = n u m tmp=num tmp=num 即找到对应的字符串。

代码:

#include <bits/stdc++.h>

using namespace std;
using ULL = unsigned long long;
const int maxn = 3e5 + 5;
static const ULL mod = (1ull << 61) - 1;
ULL power[maxn];
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<ULL> dist(mod / 2, mod - 1);
const ULL base = dist(rnd);

static inline ULL add(ULL a, ULL b) {
    a += b;
    if (a >= mod)
        a -= mod;
    return a;
}

static inline ULL mul(ULL a, ULL b) {
    __uint128_t c = __uint128_t(a) * b;
    return add(c >> 61, c & mod);
}

ULL merge(ULL h1, ULL h2, int len2) {
    return add(mul(h1, power[len2]), h2);
}

void init() {
    power[0] = 1;
    for (int i = 1; i < maxn; i++)
        power[i] = mul(power[i - 1], base);
}

ULL query(const vector<ULL> &s, int l, int r) {
    return add(s[r], mod - mul(s[l - 1], power[r - l + 1]));
}

vector<ULL> build(const string &s) {
    int sz = s.size();
    vector<ULL> hashed(sz + 1);
    for (int i = 0; i < sz; i++) {
        hashed[i + 1] = add(mul(hashed[i], base), s[i]);
    }
    return hashed;
}

int main() {
    init();
    int T;
    cin >> T;
    while (T--) {
        int n, m;
        cin >> n >> m;
        vector<string> s(m);
        for (int i = 0; i < m; i++)
            s[i].resize(n);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                cin >> s[j][i];
            }
        }
        unordered_map<ULL, int> mp;
        vector<vector<ULL>> tmp(m, vector<ULL>(n));
        for (int i = 0; i < m; i++) {
            auto hash = build(s[i]);
            for (int j = 1; j <= n; j++) {
                ULL hash1 = query(hash, 1, j - 1);
                ULL hash2 = ULL(s[i][j - 1] ^ 1);
                ULL hash3 = query(hash, j + 1, n);
                tmp[i][j - 1] = merge(merge(hash1, hash2, 1), hash3, n - j);
                mp[tmp[i][j - 1]] += 1;
            }
        }
        int maxval = -1;
        ULL ans = 0;
        for (auto &[x, y]: mp) {
            if (y > maxval) {
                maxval = y;
                ans = x;
            }
        }
        auto get = [&]() {
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (tmp[i][j] == ans) {
                        s[i][j] ^= 1;
                        cout << s[i] << endl;
                        return;
                    }
                }
            }
        };
        cout << maxval << endl;
        get();
    }
    return 0;
}

赛后交流

在比赛结束后,会在交流群中给出比赛题解,同学们可以在赛后查看题解进行补题。

群号: 704572101,赛后大家可以一起交流做题思路,分享做题技巧,欢迎大家的加入。

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

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

相关文章

目标检测数据集 - 城市道路行驶车辆检测数据集下载「包含VOC、COCO、YOLO三种格式」

​​​数据集介绍&#xff1a;城市道路行驶车辆检测数据集&#xff0c;真实监控场景高质量图片数据&#xff0c;涉及场景丰富&#xff0c;比如城市道路快速行驶车辆、城市道路慢速行驶车辆、城市道路密集行驶车辆、城市道路夜间低光行驶车辆数据等。数据集标注标签划分为 "…

Qt报错:libvlc开发的程序,出现Direct3D output全屏窗口

问题描述&#xff1a; 在qt中开发重播模块时&#xff0c;第一次在窗口正常播放&#xff0c;点击重播按钮后会弹出新的Direct3D output窗口播放视频 分析&#xff1a; 因为libvlc_media_player_set_hwnd 这个函数 设置了不存在的窗口句柄&#xff0c;导致vlc视频播放窗口没有嵌…

python-题库篇-为什么数组下标从0 开始而不是 1

为什么很多编程语言要把 0 作为第一个下标索引&#xff0c;而不是直观的 1 呢&#xff1f; 这个问题 Dijkstra 已经解答过了&#xff0c;没错&#xff0c;就是你知道的 Dijkstra&#xff0c;Dijkstra 最短路径算法&#xff0c;荷兰语全名是 Edsger Wybe Dijkstra&#xff0c;于…

【一百零五】【算法分析与设计】分解质因数,952. 按公因数计算最大组件大小,204. 计数质数,分解质因数,埃式筛

分解质因数 题目&#xff1a;分解质因数 题目描述 给定一个正整数 n&#xff0c;编写一个程序将其分解为质因数&#xff0c;并按从小到大的顺序输出这些质因数。 输入格式 一个正整数 n&#xff0c;其中 n 的范围是 1 < n < 10^18。 输出格式 按从小到大的顺序输出 n 的质…

【NoSQL数据库】Redis命令、持久化、主从复制

Redis命令、持久化、主从复制 redis配置 Redis命令、持久化、主从复制Redis数据类型redis数据库常用命令redis多数据库常用命令1、多数据库间切换2、多数据库间移动数据3、清除数据库内数据 key命令1、keys 命令2、判断键值是否存在exists3、删除当前数据库的指定key del4、获取…

品牌控价数据监测频次

品牌控价首先需对全网品牌相关链接进行数据监测&#xff0c;涵盖页面价与到手价&#xff0c;促销信息监测必不可少&#xff0c;如平台优惠券、店铺券、满减券、新人券、会员券等&#xff0c;因其优惠信息和价格随时可能变化&#xff0c;故监测频次要合理设置以实现全网数据的准…

硬件26、EDA绘制板框

1、放置-板框-矩形 2、在pcb上绘制出需要大小的板框 3、设置板框四个角为圆弧状&#xff0c;在右侧属性栏设置圆角半径

【python】成功解决“ModuleNotFoundError: No module named ‘timm’”错误的全面指南

成功解决“ModuleNotFoundError: No module named ‘timm’”错误的全面指南 一、引言 在Python编程中&#xff0c;经常会遇到各种导入模块的错误&#xff0c;其中“ModuleNotFoundError: No module named ‘timm’”就是一个典型的例子。这个错误意味着你的Python环境中没有安…

自动驾驶仿真:python和carsim联合仿真案例

文章目录 前言一、Carsim官方案例二、Carsim配置1、车辆模型2、procedure配置3、Run Control配置 三、python编写四、运行carsim五、运行python总结 前言 carsim内部有许多相关联合仿真的demo&#xff0c;simulink、labview等等都有涉及&#xff0c;这里简单介绍下python和car…

使用kubespray部署k8s生产环境

使用kubespray部署k8s生产环境 系统环境 OS: Static hostname: test Icon name: computer-vm Chassis: vm Machine ID: 22349ac6f9ba406293d0541bcba7c05d Boot ID: 83bb7e5dbf27453c94ff9f1fe88d5f02 Virtualization: vmware Operating System: Ubuntu 22.04.4 LTS Kernel: L…

Linux中,ll 命令 列出目录的内容

文章目录 1、2、3、4、5、 1、 在Linux中&#xff0c;ll 通常是一个别名&#xff08;alias&#xff09;用于 ls -l 命令。ls 命令用于列出目录的内容&#xff0c;而 -l 选项会以长格式&#xff08;long format&#xff09;显示信息&#xff0c;包括文件或目录的权限、所有者、…

系统工程与信息系统基础

三、企业信息化 目的&#xff1a;提高企业的竞争力 信息化需求&#xff1a; 战略需求&#xff1a;提升组织的竞争能力 运作需求&#xff1a;实现信息化战略目标、运作策略、人才培养的需要 技术需求&#xff1a;信息技术层面上对系统的完善、升级、集成 企业信息化方法&…

echarts legend. icon的展示

默认展示 icon展示circle圆形rect矩形roundRect圆角矩形triangle三角形diamond菱形pin水滴arrow箭头none不显示

semaphore | 使用web界面的ansible来批量运维 linux、windows主机

Ansible 的现代化 UI &#xff0c;可以轻松管理和运行 Ansible playbook&#xff0c;功能强大&#xff0c;操作简单&#xff0c;支持中文。 文章目录 一、系统功能说明二、系统安装2.1 直接安装2.2 docker 安装 三、系统使用3.1 建立存储库3.2 编写代码3.3 建立主机配置3.3 建立…

AMD 在 Computex 2024 宣布7月推出 Zen 5 锐龙 9000 处理器并展示 Ryzen 9000 CPU 和 AI PC 架构

AMD在台湾台北举行的Computex 2024上揭开了Ryzen 9、7和5系列中四款新的4nm Zen 5驱动的Ryzen 9000处理器的盖子&#xff0c;新的Zen 5架构芯片将于7月上市。将每周期指令数&#xff08;IPC&#xff09;吞吐量提高16%。AMD声称新的旗舰Ryzen 9 9950X在游戏方面比英特尔的竞争对…

记录第一次http转https

之前小程序用的后端是咸虾米老师的&#xff0c;昨天写小程序就想着自己又不是不会写&#xff1f;用自己的吧&#xff0c;然后发现微信小程序要域名是https协议的。看来又得学新东西了Q-Q 查了下大概要这么几个步骤 1.购买ssl证书 2.通过naginx配置ssl证书 3.将以前的http重定…

“JS逆向 | Python爬虫 | 动态cookie如何破~”

案例目标 目标网址:aHR0cHMlM0EvL21hdGNoLnl1YW5yZW54dWUuY29tL21hdGNoLzI= 本题目标:提取全部 5 页发布日热度的值,计算所有值的加和,并提交答案 常规 JavaScript 逆向思路 JavaScript 逆向工程通常分为以下三步: 寻找入口:逆向工程的核心在于找出加密参数的生成方式。…

【代码审计】star7th/showdoc:v3.2.4 Phar反序列化写webshell

目录 漏洞速览 复现 漏洞速览 微步在线X情报社区-威胁情报查询_威胁分析平台_开放社区 主要就是两步&#xff0c;sql注入拿到用户token&#xff0c;再以用户身份上传恶意phar包打phar反序列化 因为文件上传对用户权限没有限制&#xff0c;故本文对sql注入部分不做探讨。…

引入AI图像识别技术,优化旧物回收系统的分类与识别流程

技术革新的必要性&#xff1a; 在旧物回收领域&#xff0c;随着回收量的不断增长和旧物种类的日益丰富&#xff0c;传统的分类与识别方法已经无法满足现代回收系统的需求。因此&#xff0c;引入AI图像识别技术成为了优化旧物回收流程、提高分类准确性与效率的必然选择。 AI图…

python-字符替换

[题目描述] 给出一个字符串 s 和 q 次操作&#xff0c;每次操作将 s 中的某一个字符a全部替换成字符b&#xff0c;输出 q 次操作后的字符串输入 输入共 q2 行 第一行一个字符串 s 第二行一个正整数 q&#xff0c;表示操作次数 之后 q 行每行“a b”表示把 s 中所有的a替换成b输…