Educational Codeforces Round 173 (Rated for Div. 2)

题目链接:Dashboard - Educational Codeforces Round 173 (Rated for Div. 2) - Codeforces
总结:翻译插件用不了了,B题题意一直没看懂,C题出思路了好久才写出来,评价为太久没打了。

A. Coin Transformation

tag:模拟

B. Digits

tag:思维

Description:给定两个数 n , d n, d n,d,写成一个数 d d d d d . . . ddddd... ddddd...,由 n ! n! n! d d d拼接而成。判断 1 − 9 1-9 19中的奇数有哪些数是它的除数。

Solution: 1 1 1显然是;当 n > = 3 n >= 3 n>=3,此时 n ! n! n! 3 3 3的倍数;当d == 5时,5是;7:当n == 3时, 111111 111111 111111是7的倍数。当 n > = 4 n>=4 n>=4时,均为 111111 111111 111111的倍数,因此是7的倍数;9和3相同使用数位和判断。

  • 长度为x的一连串的数是d的倍数,那么长度为nx的一连串数也一定是d的倍数。

C. Sums on Segments

tag:思维

Description:给定一个数组,里面的元素只有一个元素不是-1或1,其余全是-1或1,求所有不同子数组的和。n <= 1e5

Solution:先考虑不含特殊数字,那么能够得到的数是一个连续的区间,范围为[min, max];用特殊数字将其分隔为左右两个区间。

  • 包含特殊数字的变化区间为,从该数字往左右两端扩展到最大值和最小值。
void solve(){int n;cin >> n;vector<int> a(n);int idx = 0;for (int i = 0; i < n; i ++){cin >> a[i];if (a[i] != 1 && a[i] != -1){idx = i;}}int ri = 0, ra = 0;int mi = 0, ma = 0;int ans = 0;int li = 0, la = 0;if (idx != -1){for (int i = idx + 1, t = 0; i < n; i ++){t += a[i];ri = min(ri, t);ra = max(ra, t);}for (int i = idx - 1, t = 0; i >= 0; i --){t += a[i];li = min(li, t);la = max(la, t);}}int rri = 0, rra = 0;int ti = 0, ta = 0;for (int i = idx + 1; i < n; i ++){ti += a[i];ta += a[i];if (ti > 0){ti = 0;}if (ta < 0){ta = 0;}rri = min(rri, ti);rra = max(rra, ta);}int lli = 0, lla = 0;ti = ta = 0;for (int i = idx - 1; i >= 0; i --){ti += a[i];ta += a[i];if (ti > 0){ti = 0;}if (ta < 0){ta = 0;}lli = min(lli, ti);lla = max(lla, ta);}set<int> st;for (int i = lli; i <= lla; i ++)st.insert(i);for (int i = rri; i <= rra; i ++)st.insert(i);for (int i = li + ri; i <= la + ra; i ++)st.insert(i + a[idx]);st.insert(0);cout << st.size() << endl;for (auto i : st){cout << i <<  " ";}cout << endl;}

D. Problem about GCD

tag:数学

Description:给定三个数l, r, G,需要求出a, b满足l <= a <= b <= r, gcd(a, b) == G,满足|a - b|最大,当有多对答案时,输出a最小的一对,否则输出-1 -11 <= l <= r <= 1e18, 1 <= G <= 1e18

Solution:当G == 1时,等价于找出两个互质的数,两个互质的数之间的差距不会太大,直接暴力枚举即可;当G != 1时,先处于G即可。

trick:两个互质的数之间的差距不会太大,枚举的复杂度大概为 l o g 2 log^2 log2

void solve(){int l, r, g;cin >> l >> r >> g;l = (l + g - 1) / g;r = r / g;for (int len = r - l; len >= 0; len --)for (int i = l; i + len <= r; i ++){int j = i + len;if (gcd(i, j) == 1){cout << i * g << " " << j * g << endl;return;}}cout << "-1 -1\n";
}

E. Matrix Transformation

tag:按位思考

Description:给定两个n * m的矩阵a,b,可以对a矩阵执行任意顺序、任意次数的以下两种操作。

  • 对第i行的所有元素,按位与上x;
  • 对第j列的所有元素,按位或上x;

Solution:将矩阵按位分隔为01矩阵,每一位都是独立的。那么两种操作等价于将一行全变为0,将一列全变为0;

  • 为了防止修改原数组,我们反过来操作矩阵b,如果一行全为0或一列全为1则进行标记;注意当一行被标记后,除了该行其余列为1的列需要标记
  • 判断未被标记的元素是否相等即可。
void solve(){int n, m;cin >> n >> m;vector a(n + 1, vector<int>(m + 1)), b(n + 1, vector<int>(m + 1));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 ++)cin >> b[i][j];for (int bit = 0; bit <= 30; bit ++){  // 枚举每一位vector<int> row(n + 1), col(m + 1);while (1){auto trow = row, tcol = col;for (int i = 1; i <= n; i ++){bool flag = true;  // 每一位是否相同for (int j = 1; j <= m; j ++){if ((b[i][j] >> bit) & 1 == 1 && tcol[j] == 0){  // 一行全为0flag = false;}}if (flag){trow[i] = 1;;}}for (int i = 1; i <= m; i ++){bool flag = true;  for (int j = 1; j <= n; j ++){if (((b[j][i] >> bit) & 1) == 0 && trow[j] == 0){  // 一列全为1flag = false;}}if (flag){tcol[i] = 1;;}}if (row == trow && col == tcol){break;}row = trow;col = tcol;}for (int i = 1; i <= n; i ++){if (row[i])continue;for (int j = 1; j <= m; j ++){if (col[j])continue;if (((a[i][j] >> bit) & 1) != ((b[i][j] >> bit) & 1)){cout << "No\n";return;}}}}cout << "Yes\n";
}

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

C++--------------树

探索 C 中的树结构&#xff1a;从基础到应用 在 C 编程的世界里&#xff0c;树结构是一种非常重要且强大的数据结构&#xff0c;它在许多领域都有着广泛的应用&#xff0c;从简单的数据存储到复杂的算法实现&#xff0c;树结构都展现出了独特的优势。今天&#xff0c;就让我们一…

Python PyMupdf 去除PDF文档中Watermark标识水印

通过PDF阅读或编辑工具&#xff0c;可在PDF中加入Watermark标识的PDF水印&#xff0c;如下图&#xff1a; 该类水印特点 这类型的水印&#xff0c;会在文件的字节流中出现/Watermark、EMC等标识&#xff0c;那么&#xff0c;我们可以通过改变文件字节内容&#xff0c;清理掉…

centos制作离线安装包

目录 1.yumdownloader与repotrack怎么选择&#xff1f; yumdownloader --resolve repotrack 总结 2.环境准备 3.安装 1.yumdownloader与repotrack怎么选择&#xff1f; yumdownloader --resolve 和 repotrack 都是与 YUM&#xff08;Yellowdog Updater Modified&#xf…

C++的内存四区

文章目录 内存四区1.程序运行前1.1 代码区2.1 全局区2.2 示例 2.程序运行后1.1 栈区1.2 堆区 内存四区 1.程序运行前 在程序编译后&#xff0c;生成了exe可执行程序&#xff0c;未执行该程序前分为两个区域。该区域的数据在程序结束后由操作系统释放. 1.1 代码区 ​存放 CPU …

网络工程师常用软件之PING测试工具

老王说网络&#xff1a;网络资源共享汇总 https://docs.qq.com/sheet/DWXZiSGxiaVhxYU1F ☝☝☝☝☝☝☝☝☝☝☝☝☝☝☝☝☝☝☝☝☝☝☝☝☝☝☝☝☝☝☝☝☝☝☝☝☝☝☝☝☝☝☝☝☝☝ 今天介绍一款好用的PING测试工具&#xff0c;ATKKPING。 ATKKPING的主要功能包括测试…

118.【C语言】数据结构之排序(堆排序和冒泡排序)

目录 1.堆排序 2.冒泡排序 单趟排序的两种情况 情况1.和arr[i]的前一个元素交换,第一次循环结束时i的值为n-1,第二次循环结束时i的值为n-2 情况2.和arr[i]的后一个元素交换,第一次循环结束时i的值为n-2,第二次第一次循环结束时i的值为n-3,... 将单趟排序代码嵌入外循环中…

路由器做WPAD、VPN、透明代理中之间一个

本文章将采用家中TP-Link路由器 路由器进行配置DNS DNS理解知识本文DNS描述参考&#xff1a;网络安全基础知识&中间件简单介绍_计算机网络中间件-CSDN博客 TP LINK未知的错误&#xff0c;错误编号&#xff1a;-22025 TP-LINK 认证界面地址&#xff1a;https://realnam…

Docker部署Sentinel

一、简介 是什么&#xff1a;面向分布式、多语言异构化服务架构的流量治理组件 能干嘛&#xff1a;从流量路由、流量控制、流量整形、熔断降级、系统自适应过载保护、热点流量防护等多个维度来帮助开发者保障微服务的稳定性 官网地址&#xff1a;https://sentinelguard.io/zh-c…

机器学习之KNN算法预测数据和数据可视化

机器学习及KNN算法 目录 机器学习及KNN算法机器学习基本概念概念理解步骤为什么要学习机器学习需要准备的库 KNN算法概念算法导入常用距离公式算法优缺点优点&#xff1a;缺点︰ 数据可视化二维界面三维界面 KNeighborsClassifier 和KNeighborsRegressor理解查看KNeighborsRegr…

Java包装类型的缓存

Java 基本数据类型的包装类型的大部分都用到了缓存机制来提升性能。 Byte,Short,Integer,Long 这 4 种包装类默认创建了数值 [-128&#xff0c;127] 的相应类型的缓存数据&#xff0c;Character 创建了数值在 [0,127] 范围的缓存数据&#xff0c;Boolean 直接返回 True or Fal…

施耐德变频器ATV320系列技术优势:创新与安全并重

在工业自动化领域&#xff0c;追求高效、安全与智能已成为不可阻挡的趋势。施耐德变频器ATV320系列凭借其强大的设计标准和全球认证&#xff0c;成为能够帮助企业降低安装成本&#xff0c;提高设备性能的创新解决方案。 【全球认证&#xff0c;品质保障】ATV320 系列秉持施耐德…

Excel批量设置行高,Excel表格设置自动换行后打印显示不全,Excel表格设置最合适的行高后打印显示不全,完美解决方案!!!

文章目录 说个问题&#xff08;很严重&#xff01;&#xff01;&#xff01;&#xff09;写个方案会Python看这里Python环境搭建不存在多行合并存在多行合并 不会Python看这里 说个问题&#xff08;很严重&#xff01;&#xff01;&#xff01;&#xff09; 平时处理Excel表格…

洛谷 P1014:Cantor 表

【题目来源】https://www.luogu.com.cn/problem/P1014https://www.acwing.com/problem/content/5510/【题目描述】 现代数学的著名证明之一是 Georg Cantor 证明了有理数是可枚举的。 他是用下面这一张表来证明这一命题的&#xff1a; 1/1 1/2 1/3 1/4 1/5 … 2/1 2/2 …

C语言基础:指针(数组指针与指针数组)

数组指针与指针数组 数组指针 概念&#xff1a;数组指针是指向数组的指针&#xff0c;本质上还是指针 特点&#xff1a; 先有数组&#xff0c;后有指针 它指向的是一个完整的数组 一维数组指针&#xff1a; 语法&#xff1a; 数据类型 (*指针变量名)[行容量][列容量]; 案…

华为管理变革之道:奋斗文化与活力

目录 企业文化是什么&#xff1f; 为什么活下去是华为的文化&#xff1f; 活下来&#xff0c;是华为公司的最低纲领&#xff0c;也是华为公司的最高纲领&#xff01; 资源终会枯竭&#xff0c;唯有文化才能生生不息 企业文化之一&#xff1a;以客户为中心 企业文化之二&a…

JS面试题|[2024-12-26]

1.事件委托是什么 又叫事件代理&#xff0c;原理就是直接利用了事件冒泡的机制来实现&#xff0c;也就是说把子元素的事件绑定到了父元素的身上&#xff0c;如果子元素阻止了事件冒泡&#xff0c;那么委托也就不成立了。 阻止事件冒泡&#xff1a;event.stopPropagation() addE…

upload-labs关卡记录12

直接上传一句话木马&#xff0c;发现提示&#xff1a; 很明显这是一个白名单&#xff0c;而且不是前端的js检查&#xff0c;而是服务端的检查&#xff0c;因此我们使用bp抓包&#xff0c;改一下文件类型试试&#xff1a; 找到包之后&#xff0c;我们对content-type进行一个更改…

ArkTs组件(2)

一.下拉列表组件&#xff1a;Select 1.接口 Select(options: Array<SelectOption>) 参数名类型必填说明optionsArray<SelectOption>是设置下拉选项。 SelectOption对象说明 名称类型必填说明valueResourceStr是 下拉选项内容。 iconResourceStr否 下拉选项图片…

J9学习打卡笔记

&#x1f368; 本文为&#x1f517;365天深度学习训练营 中的学习记录博客&#x1f356; 原作者&#xff1a;K同学啊 IInception v3算法实战 网络结构InceptionAInceptionBInceptionCReductionAReductionB辅助分支个人总结 import os, PIL, random, pathlib import torch impor…

软考和 PMP 哪个含金量更高点?

软考高项比较适用于计算机 IT 行业&#xff0c;而 PMP 不受行业限制&#xff0c;各行各业都适用&#xff0c;没有哪个含金量更高的说法 至于哪个更合适&#xff0c;看你想去国企还是民企&#xff0c;国企软考吃香&#xff0c;外企PMP 吃香 下面说下两者具体有什么区别&#x…