2022 ICPC 济南 E Identical Parity (扩欧)
2022 ICPC 济南 E. Identical Parity (扩欧)
Problem - E - Codeforces
大意:给出一个 n 和一个 k , 问是否能构造一个长 n 的排列使得所有长 k 的连续子序列和的奇偶性相同。
思路:通过分析可知 , 任两个间隔 k - 1 的元素奇偶性必然相同 , 这样的话 , 问题就转化成了
( n % k )个( ⌊ n k ⌋ + 1 )和( k − n % k )个( ⌊ n k ⌋ )是否能组成( ⌊ n 2 ⌋ )和( n − ⌊ n 2 ⌋ )的问题 (n ~\% ~k ~)个(\left \lfloor \frac{n}{k} \right \rfloor +1)和(k-n~\%~k)个(\left \lfloor \frac{n}{k} \right \rfloor)是否能组成(\left \lfloor \frac{n}{2} \right \rfloor)和(n - \left \lfloor \frac{n}{2} \right \rfloor)的问题 (n % k )个(⌊kn⌋+1)和(k−n % k)个(⌊kn⌋)是否能组成(⌊2n⌋)和(n−⌊2n⌋)的问题
很自然的就可以想到 01 背包去解决这个问题 , 但是显然 n 和 k 的范围太大了 , 无法使用 01 背包去解决这个问题。 于是转化问题 , 考虑现有范围的 x 和 y 是否能满足以下式子。
( ⌊ n k ⌋ + 1 ) ∗ x + ( ⌊ n k ⌋ ) ∗ y = ( ⌊ n 2 ⌋ ) (\left \lfloor \frac{n}{k} \right \rfloor +1)*x~+~(\left \lfloor \frac{n}{k} \right \rfloor)*y = (\left \lfloor \frac{n}{2} \right \rfloor) (⌊kn⌋+1)∗x + (⌊kn⌋)∗y=(⌊2n⌋)
带入扩欧得到通解:
x = x 0 ∗ c g c d ( a , b ) + k ∗ b g c d ( a , b ) x=x_0*{c\over gcd(a,b)}+{k*b\over gcd(a,b)} x=x0∗gcd(a,b)c+gcd(a,b)k∗b
y = y 0 ∗ c g c d ( a , b ) − k ∗ a g c d ( a , b ) y=y_0*{c\over gcd(a,b)}-{k*a\over gcd(a,b)} y=y0∗gcd(a,b)c−gcd(a,b)k∗a
根据已有的 x 的范围 和 y 的范围分别求出两个 k 的范围 , 判断这两个区间是否相交即可。
易错点:是否可以通过 x 的范围求出对应 k 的范围然后带入求 y 的范围 ?显然是可以的 , 但是这样求出的 y 的范围区间是不连续的 , 也就不能判交。
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
const int N = 2e6 + 10;
const int mod = 1e9 + 7;
typedef pair<int,int>PII;int n , t , k;int exgcd(int a , int b , int &x , int &y){if(b == 0){ x = 1; y = 0; return a;}int g = exgcd(b , a % b , y , x);y -= a / b * x;return g;
}signed main(){IOScin >> t;while(t --){cin >> n >> k;if(n % k == 0){int num = n / k , od , ev;ev = n / 2;od = n - ev;if(ev % num == 0 && od % num == 0){cout << "Yes" << "\n";}else{cout << "No" << "\n";}}else{int a = n / k , b = n / k + 1 , c = n / 2;int cntb = n % k , cnta = k - n % k;int x , y , gcds;gcds = exgcd(a , b , x , y);a /= gcds;b /= gcds;c /= gcds;int k1_max = floor((double)(cnta - x * c) / (double) b);int k1_min = ceil((double)(0 - x * c) / (double) b);int k2_max = floor((double)(y * c) / (double) a);int k2_min = ceil((double)(y * c - cntb) / (double) a); if(k1_min > k1_max || k2_min > k2_max){cout << "No\n";}else{if(min(k2_max , k1_max) >= max(k1_min , k2_min)){cout << "Yes\n";}else{cout << "No\n";}}}}return 0;
}
//freopen("文件名.in","r",stdin);
//freopen("文件名.out","w",stdout);
相关文章:
2022 ICPC 济南 E Identical Parity (扩欧)
2022 ICPC 济南 E. Identical Parity (扩欧) Problem - E - Codeforces 大意:给出一个 n 和一个 k , 问是否能构造一个长 n 的排列使得所有长 k 的连续子序列和的奇偶性相同。 思路:通过分析可知 , 任两个间隔 k - 1 的元素奇偶…...

【BUG事务内消息发送】事务内消息发送,事务还未结束,消息发送已被消费,查无数据怎么解决?
问题描述 在一个事务内完成插入操作,通过MQ异步通知其他微服务进行事件处理。 由于是在事务内发送,其他服务消费消息,查询数据时还不存在如何解决呢? 解决方案 通过spring-tx包的TransactionSynchronizationManager事务管理器解…...

数据分析作业四-基于用户及物品数据进行内容推荐
## 导入支持库 import pandas as pd import matplotlib.pyplot as plt import sklearn.metrics as metrics import numpy as np from sklearn.neighbors import NearestNeighbors from scipy.spatial.distance import correlation from sklearn.metrics.pairwise import pairwi…...

在腾讯云服务器OpenCLoudOS系统中安装svn(有图详解)
1. 安装svn yum -y install subversion 安装成功: 2. 创建数据根目录及仓库 mkdir -p /usr/local/svn/svnrepository 创建test仓库: svnadmin create /usr/local/svn/test test仓库创建成功: 3. 修改配置test仓库 cd /usr/local/svn/te…...
C语言日常刷题5
文章目录 题目答案与解析1234567、 题目 1、以下叙述中正确的是( ) A: 只能在循环体内和switch语句体内使用break语句 B: 当break出现在循环体中的switch语句体内时,其作用是跳出该switch语句体,并中止循环体的执行 C: continue语…...

【LeetCode-中等题】73. 矩阵置零
题目 题解一:使用标记数组 public void setZeroes(int[][] matrix) {int m matrix.length;int n matrix[0].length;boolean[] row new boolean[m];boolean[] col new boolean[n];for(int i0; i< m;i){for(int j 0;j<n;j){if (matrix[i][j] 0) row[i]col…...
本地部署 FastGPT
本地部署 FastGPT 1. FastGPT 是什么2. 部署 FastGPT 1. FastGPT 是什么 FastGPT 是一个基于 LLM 大语言模型的知识库问答系统,提供开箱即用的数据处理、模型调用等能力。同时可以通过 Flow 可视化进行工作流编排,从而实现复杂的问答场景! …...

软件工程(十八) 行为型设计模式(四)
1、状态模式 简要说明 允许一个对象在其内部改变时改变它的行为 速记关键字 状态变成类 类图如下 状态模式主要用来解决对象在多种状态转换时,需要对外输出不同的行为的问题。比如订单从待付款到待收货的咋黄台发生变化,执行的逻辑是不一样的。 所以我们将状态抽象为一…...

Socket通信与WebSocket协议
文章目录 目录 文章目录 前言 一、Socket通信 1.1 BIO 1.2 NIO 1.3 AIO 二、WebSocket协议 总结 前言 一、Socket通信 Socket是一种用于网络通信的编程接口(API),它提供了一种机制,使不同主机之间可以通过网络进行数据传输和通信…...

新KG视点 | Jeff Pan、陈矫彦等——大语言模型与知识图谱的机遇与挑战
OpenKG 大模型专辑 导读 知识图谱和大型语言模型都是用来表示和处理知识的手段。大模型补足了理解语言的能力,知识图谱则丰富了表示知识的方式,两者的深度结合必将为人工智能提供更为全面、可靠、可控的知识处理方法。在这一背景下,OpenKG组织…...

详解过滤器Filter和拦截器Interceptor的区别和联系
目录 前言 区别 联系 前言 过滤器(Filter)和拦截器(Interceptor)都是用于在Web应用程序中处理请求和响应的组件,但它们在实现方式和功能上有一些区别。 区别 1. 实现方式: - 过滤器是基于Servlet规范的组件,通过实现javax.servlet.Filt…...
List常用的操作
1、看List里是否存在某个元素 contains //省略建立listboolean contains stringList.contains("上海");System.out.println(contains); 如果存在是true,不存在是false 2、看某个元素在List中的索引号 .indexOf List<String>stringList new Ar…...

Android studio APK切换多个摄像头(Camera2)
1.先设置camera的权限 <uses-permission android:name"android.permission.CAMERA" /> 2.布局 <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas.android.com/apk/res/android"and…...
ChatGPT 对教育的影响,AI 如何颠覆传统教育
胜量老师 来源:BV1Nv4y1H7kC 由Chat GPT引发的对教育的思考,人类文明发展至今一直靠教育完成文明的传承,一个年轻人要经历若干年的学习,才能进入社会投入对文明的建设,而学习中有大量内容是需要记忆和反复训练的。 无…...

Spring(九)声明式事务
Spring整合Junit4和JdbcTemplater如下所示: 我们所使用的junit的jar包不同,可以整合不同版本的junit。 我们导入的依赖如下所示: <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.a…...
java中用HSSFWorkbook生成xls格式的excel(亲测)
SXSSFWorkbook类是用于生成XLSX格式的Excel文件(基于XML格式),而不是XLS格式的Excel文件(基于二进制格式)。 如果你需要生成XLS格式的Excel文件,可以使用HSSFWorkbook类。以下是一个简单的示例:…...
做平面设计一般电脑可以吗 优漫动游
平面设计常用的软件如下:Photoshop、AutoCAD、AI等。其中对电脑配置要求高的是AutoCAD,可运行AutoCAD的软件均可运行如上软件。 做平面设计一般电脑可以吗 AutoCAD64位版配置要求:AMDAthlon64位处理器、支持SSE2技术的AMDOpteron处理器、…...

设计模式备忘录+命令模式实现Word撤销恢复操作
文章目录 前言思路代码实现uml类图总结 前言 最近学习设计模式行为型的模式,学到了备忘录模式提到这个模式可以记录一个对象的状态属性值,用于下次复用,于是便想到了我们在Windows系统上使用的撤销操作,于是便想着使用这个模式进…...

Linux centos7 bash编程小训练
训练要求: 求比一个数小的最大回文数 知识点: 一个数字正读反读都一样,我们称为回文数,如5、11、55、121、222等。 我们训练用bash编写一个小程序,由我们标准输入一个整数,计算机将显示出一个比这个数小…...

创作2周年纪念日-特别篇
创作2周年纪念日-特别篇 1. 与CSDN的机缘2. 收获3. 憧憬 1. 与CSDN的机缘 很荣幸,在大学时候,能够接触到CSDN这样一个平台,当时对嵌入式开发、编程、计算机视觉等内容比较感兴趣。后面一个很偶然的联培实习机会,让我接触到了Pych…...

51c自动驾驶~合集58
我自己的原文哦~ https://blog.51cto.com/whaosoft/13967107 #CCA-Attention 全局池化局部保留,CCA-Attention为LLM长文本建模带来突破性进展 琶洲实验室、华南理工大学联合推出关键上下文感知注意力机制(CCA-Attention),…...

3.3.1_1 检错编码(奇偶校验码)
从这节课开始,我们会探讨数据链路层的差错控制功能,差错控制功能的主要目标是要发现并且解决一个帧内部的位错误,我们需要使用特殊的编码技术去发现帧内部的位错误,当我们发现位错误之后,通常来说有两种解决方案。第一…...

如何将联系人从 iPhone 转移到 Android
从 iPhone 换到 Android 手机时,你可能需要保留重要的数据,例如通讯录。好在,将通讯录从 iPhone 转移到 Android 手机非常简单,你可以从本文中学习 6 种可靠的方法,确保随时保持连接,不错过任何信息。 第 1…...

uniapp微信小程序视频实时流+pc端预览方案
方案类型技术实现是否免费优点缺点适用场景延迟范围开发复杂度WebSocket图片帧定时拍照Base64传输✅ 完全免费无需服务器 纯前端实现高延迟高流量 帧率极低个人demo测试 超低频监控500ms-2s⭐⭐RTMP推流TRTC/即构SDK推流❌ 付费方案 (部分有免费额度&#x…...

听写流程自动化实践,轻量级教育辅助
随着智能教育工具的发展,越来越多的传统学习方式正在被数字化、自动化所优化。听写作为语文、英语等学科中重要的基础训练形式,也迎来了更高效的解决方案。 这是一款轻量但功能强大的听写辅助工具。它是基于本地词库与可选在线语音引擎构建,…...
Go 语言并发编程基础:无缓冲与有缓冲通道
在上一章节中,我们了解了 Channel 的基本用法。本章将重点分析 Go 中通道的两种类型 —— 无缓冲通道与有缓冲通道,它们在并发编程中各具特点和应用场景。 一、通道的基本分类 类型定义形式特点无缓冲通道make(chan T)发送和接收都必须准备好࿰…...

力扣热题100 k个一组反转链表题解
题目: 代码: func reverseKGroup(head *ListNode, k int) *ListNode {cur : headfor i : 0; i < k; i {if cur nil {return head}cur cur.Next}newHead : reverse(head, cur)head.Next reverseKGroup(cur, k)return newHead }func reverse(start, end *ListNode) *ListN…...

GO协程(Goroutine)问题总结
在使用Go语言来编写代码时,遇到的一些问题总结一下 [参考文档]:https://www.topgoer.com/%E5%B9%B6%E5%8F%91%E7%BC%96%E7%A8%8B/goroutine.html 1. main()函数默认的Goroutine 场景再现: 今天在看到这个教程的时候,在自己的电…...
MySQL 索引底层结构揭秘:B-Tree 与 B+Tree 的区别与应用
文章目录 一、背景知识:什么是 B-Tree 和 BTree? B-Tree(平衡多路查找树) BTree(B-Tree 的变种) 二、结构对比:一张图看懂 三、为什么 MySQL InnoDB 选择 BTree? 1. 范围查询更快 2…...

手机平板能效生态设计指令EU 2023/1670标准解读
手机平板能效生态设计指令EU 2023/1670标准解读 以下是针对欧盟《手机和平板电脑生态设计法规》(EU) 2023/1670 的核心解读,综合法规核心要求、最新修正及企业合规要点: 一、法规背景与目标 生效与强制时间 发布于2023年8月31日(OJ公报&…...