当前位置: 首页 > news >正文

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)和(kn % k)个(kn)是否能组成(2n)和(n2n)的问题

很自然的就可以想到 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+1x + kny=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=x0gcd(a,b)c+gcd(a,b)kb

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=y0gcd(a,b)cgcd(a,b)ka

根据已有的 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 大意&#xff1a;给出一个 n 和一个 k &#xff0c; 问是否能构造一个长 n 的排列使得所有长 k 的连续子序列和的奇偶性相同。 思路&#xff1a;通过分析可知 &#xff0c; 任两个间隔 k - 1 的元素奇偶…...

【BUG事务内消息发送】事务内消息发送,事务还未结束,消息发送已被消费,查无数据怎么解决?

问题描述 在一个事务内完成插入操作&#xff0c;通过MQ异步通知其他微服务进行事件处理。 由于是在事务内发送&#xff0c;其他服务消费消息&#xff0c;查询数据时还不存在如何解决呢&#xff1f; 解决方案 通过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 安装成功&#xff1a; 2. 创建数据根目录及仓库 mkdir -p /usr/local/svn/svnrepository 创建test仓库&#xff1a; svnadmin create /usr/local/svn/test test仓库创建成功&#xff1a; 3. 修改配置test仓库 cd /usr/local/svn/te…...

C语言日常刷题5

文章目录 题目答案与解析1234567、 题目 1、以下叙述中正确的是&#xff08; &#xff09; A: 只能在循环体内和switch语句体内使用break语句 B: 当break出现在循环体中的switch语句体内时&#xff0c;其作用是跳出该switch语句体&#xff0c;并中止循环体的执行 C: continue语…...

【LeetCode-中等题】73. 矩阵置零

题目 题解一&#xff1a;使用标记数组 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 大语言模型的知识库问答系统&#xff0c;提供开箱即用的数据处理、模型调用等能力。同时可以通过 Flow 可视化进行工作流编排&#xff0c;从而实现复杂的问答场景&#xff01; …...

软件工程(十八) 行为型设计模式(四)

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

Socket通信与WebSocket协议

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

新KG视点 | Jeff Pan、陈矫彦等——大语言模型与知识图谱的机遇与挑战

OpenKG 大模型专辑 导读 知识图谱和大型语言模型都是用来表示和处理知识的手段。大模型补足了理解语言的能力&#xff0c;知识图谱则丰富了表示知识的方式&#xff0c;两者的深度结合必将为人工智能提供更为全面、可靠、可控的知识处理方法。在这一背景下&#xff0c;OpenKG组织…...

详解过滤器Filter和拦截器Interceptor的区别和联系

目录 前言 区别 联系 前言 过滤器(Filter)和拦截器(Interceptor)都是用于在Web应用程序中处理请求和响应的组件&#xff0c;但它们在实现方式和功能上有一些区别。 区别 1. 实现方式&#xff1a; - 过滤器是基于Servlet规范的组件&#xff0c;通过实现javax.servlet.Filt…...

List常用的操作

1、看List里是否存在某个元素 contains //省略建立listboolean contains stringList.contains("上海");System.out.println(contains); 如果存在是true&#xff0c;不存在是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 如何颠覆传统教育

胜量老师 来源&#xff1a;BV1Nv4y1H7kC 由Chat GPT引发的对教育的思考&#xff0c;人类文明发展至今一直靠教育完成文明的传承&#xff0c;一个年轻人要经历若干年的学习&#xff0c;才能进入社会投入对文明的建设&#xff0c;而学习中有大量内容是需要记忆和反复训练的。 无…...

Spring(九)声明式事务

Spring整合Junit4和JdbcTemplater如下所示&#xff1a; 我们所使用的junit的jar包不同&#xff0c;可以整合不同版本的junit。 我们导入的依赖如下所示&#xff1a; <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.a…...

java中用HSSFWorkbook生成xls格式的excel(亲测)

SXSSFWorkbook类是用于生成XLSX格式的Excel文件&#xff08;基于XML格式&#xff09;&#xff0c;而不是XLS格式的Excel文件&#xff08;基于二进制格式&#xff09;。 如果你需要生成XLS格式的Excel文件&#xff0c;可以使用HSSFWorkbook类。以下是一个简单的示例&#xff1a…...

做平面设计一般电脑可以吗 优漫动游

平面设计常用的软件如下&#xff1a;Photoshop、AutoCAD、AI等。其中对电脑配置要求高的是AutoCAD&#xff0c;可运行AutoCAD的软件均可运行如上软件。 做平面设计一般电脑可以吗 AutoCAD64位版配置要求&#xff1a;AMDAthlon64位处理器、支持SSE2技术的AMDOpteron处理器、…...

设计模式备忘录+命令模式实现Word撤销恢复操作

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

Linux centos7 bash编程小训练

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

创作2周年纪念日-特别篇

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

【Axure高保真原型】引导弹窗

今天和大家中分享引导弹窗的原型模板&#xff0c;载入页面后&#xff0c;会显示引导弹窗&#xff0c;适用于引导用户使用页面&#xff0c;点击完成后&#xff0c;会显示下一个引导弹窗&#xff0c;直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...

AI Agent与Agentic AI:原理、应用、挑战与未来展望

文章目录 一、引言二、AI Agent与Agentic AI的兴起2.1 技术契机与生态成熟2.2 Agent的定义与特征2.3 Agent的发展历程 三、AI Agent的核心技术栈解密3.1 感知模块代码示例&#xff1a;使用Python和OpenCV进行图像识别 3.2 认知与决策模块代码示例&#xff1a;使用OpenAI GPT-3进…...

Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信

文章目录 Linux C语言网络编程详细入门教程&#xff1a;如何一步步实现TCP服务端与客户端通信前言一、网络通信基础概念二、服务端与客户端的完整流程图解三、每一步的详细讲解和代码示例1. 创建Socket&#xff08;服务端和客户端都要&#xff09;2. 绑定本地地址和端口&#x…...

C++.OpenGL (20/64)混合(Blending)

混合(Blending) 透明效果核心原理 #mermaid-svg-SWG0UzVfJms7Sm3e {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-icon{fill:#552222;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-text{fill…...

C#学习第29天:表达式树(Expression Trees)

目录 什么是表达式树&#xff1f; 核心概念 1.表达式树的构建 2. 表达式树与Lambda表达式 3.解析和访问表达式树 4.动态条件查询 表达式树的优势 1.动态构建查询 2.LINQ 提供程序支持&#xff1a; 3.性能优化 4.元数据处理 5.代码转换和重写 适用场景 代码复杂性…...

PostgreSQL——环境搭建

一、Linux # 安装 PostgreSQL 15 仓库 sudo dnf install -y https://download.postgresql.org/pub/repos/yum/reporpms/EL-$(rpm -E %{rhel})-x86_64/pgdg-redhat-repo-latest.noarch.rpm# 安装之前先确认是否已经存在PostgreSQL rpm -qa | grep postgres# 如果存在&#xff0…...

Linux系统部署KES

1、安装准备 1.版本说明V008R006C009B0014 V008&#xff1a;是version产品的大版本。 R006&#xff1a;是release产品特性版本。 C009&#xff1a;是通用版 B0014&#xff1a;是build开发过程中的构建版本2.硬件要求 #安全版和企业版 内存&#xff1a;1GB 以上 硬盘&#xf…...

实战设计模式之模板方法模式

概述 模板方法模式定义了一个操作中的算法骨架&#xff0c;并将某些步骤延迟到子类中实现。模板方法使得子类可以在不改变算法结构的前提下&#xff0c;重新定义算法中的某些步骤。简单来说&#xff0c;就是在一个方法中定义了要执行的步骤顺序或算法框架&#xff0c;但允许子类…...

sshd代码修改banner

sshd服务连接之后会收到字符串&#xff1a; SSH-2.0-OpenSSH_9.5 容易被hacker识别此服务为sshd服务。 是否可以通过修改此banner达到让人无法识别此服务的目的呢&#xff1f; 不能。因为这是写的SSH的协议中的。 也就是协议规定了banner必须这么写。 SSH- 开头&#xff0c…...

多元隐函数 偏导公式

我们来推导隐函数 z z ( x , y ) z z(x, y) zz(x,y) 的偏导公式&#xff0c;给定一个隐函数关系&#xff1a; F ( x , y , z ( x , y ) ) 0 F(x, y, z(x, y)) 0 F(x,y,z(x,y))0 &#x1f9e0; 目标&#xff1a; 求 ∂ z ∂ x \frac{\partial z}{\partial x} ∂x∂z​、 …...