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

P11299 [NOISG 2021 Finals] Fraud 题解

news 来源：原创 2025/8/6 22:25:30

题目背景

你被任命为第 24 届全国信息学奥林匹克竞赛的负责人！

题目描述

本次竞赛共有 N 名参赛者和 2 轮比赛。第 i 名参赛者在第一轮获得了 $A_i$ 分，在第二轮获得了 $B_i$ 分。

每轮比赛分别有一个正整数权重 X 和 Y。第 i 名参赛者的最终得分 $S_i$ 计算公式为：

$S_i = A_i \times X + B_i \times Y$

作为竞赛负责人，你可以自由选择 X 和 Y 的值。

然而，老鼠 Squeaky 贿赂了你，要求你选择某些 X 和 Y，使得 $S_i>S_j$ 对所有 1≤i<j≤N 都成立。如果能做到，他会重金酬谢。

但是，这是否可能呢？

输入格式

第一行包含一个整数 N，表示参赛者的数量。
第二行包含 N 个整数 A1,A2,…,AN，表示第一轮的得分。
第三行包含 N 个整数 B1,B2,…,BN，表示第二轮的得分。

输出格式

输出一行：如果可以实现目标，输出 YES；否则输出 NO。

输入输出样例

输入 #1

2
1 2
2 1

输出 #1

YES

输入 #2

3
2 4 3
4 2 3

输出 #2

NO

输入 #3

2
5 1
0 0

输出 #3

YES

说明/提示

【样例解释】

对于样例 1，选择 X=1 和 Y=2，此时 $S_1$ =1×1+2×2=5， $S_2$ =2×1+1×2=4，满足条件。
对于样例 2，无论如何选择 X 和 Y，都无法满足条件。
对于样例 3，选择任意非零 X 均满足条件，因为 $S_ 1$ $>S_2$ 。

【数据范围】

2 ≤ N ≤ $3 \times 10^5$
0 ≤ $A_i,B_i$ ≤ $10^6$

子任务编号	分值	额外限制条件
1	10	Bi=0
2	25	N=2
3	50	2≤N≤ $10^4$
4	15	无额外限制

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;const int MAXN = 3e5 + 5;
int n, a[MAXN], b[MAXN]; // 上界与下界struct frac {int zi, mu;
} mx, mn;frac make_frac(int a, int b) {if (b < 0) return (frac){-a, -b};else return (frac){a, b};
}frac maxx(frac a, frac b) {if (a.zi * b.mu - b.zi * a.mu < 0) return b;else return a;
}frac minn(frac a, frac b) {if (a.zi * b.mu - b.zi * a.mu < 0) return a;else return b;
}signed main() {cin >> n;for (int i = 1; i <= n; i++) {cin >> a[i];}for (int i = 1; i <= n; i++) {cin >> b[i];}mx = {1000000000, 1};mn = {-1000000000, 1};for (int i = 1; i < n; i++) {if (b[i + 1] > b[i]) {mx = minn(mx, make_frac(a[i + 1] - a[i], b[i] - b[i + 1]));} else if (b[i + 1] < b[i]) {mn = maxx(mn, make_frac(a[i + 1] - a[i], b[i] - b[i + 1]));} else if (a[i + 1] >= a[i]) {cout << "NO" << endl;return 0;}}if (mx.zi * mn.mu - mn.zi * mx.mu <= 0 || mx.zi <= 0) {cout << "NO" << endl;} else {cout << "YES" << endl;}return 0;
}

代码结构解析：

全局变量与结构体介绍：
- MAXN：数组最大长度。
- a[], b[]：分别存储上下界相关数据。
- frac结构体：表示分数，包含分子zi和分母mu。
- make_frac：创建分数并确保分母为正。
- maxx和minn：比较两个分数，返回较大/较小值。
主函数逻辑：
- 输入处理：读取数组a和b的值。
- 初始化上下界：mx（上界）初始化为极大正数，mn（下界）初始化为极大负数。
- 遍历处理相邻元素：
  - 当b[i+1] > b[i]：推导出x的上界，更新mx为更小值。
  - 当b[i+1] < b[i]：推导出x的下界，更新mn为更大值。
  - 当b[i+1] == b[i]：若a[i+1] ≥ a[i]，直接输出"NO"（无法满足条件）。
- 最终判断：
  - 若所有约束条件下，存在x使得 mn ≤ x ≤ mx 且 mx > 0，输出"YES"；否则输出"NO"。

核心思路：

约束条件推导：对于每个相邻元素i和i+1，根据b的变化情况，推导x的上下界：
- b[i+1] > b[i]：x需满足上界，取所有上界的最小值。
- b[i+1] < b[i]：x需满足下界，取所有下界的最大值。
- b[i+1] == b[i]：若a不满足非递增，直接无解。
最终验证：检查上下界是否有效（下界≤上界且上界为正）。

示例分析：

假设输入为：

3
2 5 7
3 1 4

则：

代码会遍历相邻元素，计算x的约束，最终判断是否存在满足条件的正数x。若存在，输出"YES"，否则"NO"。

总结：

通过分数运算和交叉相乘比较，高效处理了所有约束条件，确保在O(n)时间内完成判断。

P11299 [NOISG 2021 Finals] Fraud 题解

题目背景你被任命为第 24 届全国信息学奥林匹克竞赛的负责人！ 题目描述本次竞赛共有 N 名参赛者和 2 轮比赛。第 i 名参赛者在第一轮获得了分，在第二轮获得了分。每轮比赛分别有一个正整数权重 X 和 Y。第 i 名参赛者的最终得分计算公式为&a…...

编程日记 2025/8/6 22:25:30

AI时代下你需要和想要了解的英文缩写含义

在AI智能时代下，越来愈多的企业都开始重视并应用以及开发AI相关产品，这个时候都会或多或少的涉及到英文，英文还好，但是如果是缩写，如果我们没有提前了解过，我们往往很难以快速Get到对方的意思。在这里&…...

编程日记 2025/8/1 18:15:38

大数据平台简介

一、分布式系统基础架构 （一）定义与核心特征分布式系统是由多台计算机（节点）通过网络协作组成的系统，对外表现为一个统一整体。其核心特征包括： 去中心化：节点平等或分角色协作（如…...

编程日记 2025/8/6 2:01:25

电脑端移植至手机平板：攻克难题，仙盟架构显神通——仙盟创梦IDE

在将电脑端应用移植到手机和平板的过程中，常面临诸多棘手问题。像 1.x 号关闭按钮因位置设计欠佳，难以被用户精准点击，字体过小导致阅读与操作不便等。未来之窗仙盟创梦凭借创新的仙盟架构，巧妙且高效地化解了这些困扰开发者与用户…...

编程日记 2025/7/31 18:45:36

基于Python的中国象棋小游戏的设计与实现

基于Python的中国象棋小游戏的设计与实现第一章绪论1.1 研究背景1.2 研究意义第二章需求分析2.1 需求分析2.1.1核心功能需求2.1.2 用户体验需求2.1.3 衍生功能需求 2.2 可行性分析2.2.1 技术可行性2.2.2 经济可行性2.2.3 市场可行性2.2.4 法律与合规性第三章概要设计3.1 …...

编程日记 2025/8/2 19:36:11

HCIP --- OSPF综合实验

一、拓扑图二、实验要求 1，R5为ISP，其上只能配置IP地址;R4作为企业边界路由器，出口公网地址需要通过PPP协议获取，并进行chap认证。 2，整个0SPF环境IP基于172.16.0.8/16划分。 3，所有设备均可访问R5的环…...

编程日记 2025/8/4 1:28:34

【OpenGL】OpenGL学习笔记-1：VS2019配置OpenGL开发环境

在Visual Studio 2019中可以通过手动配置库文件或NuGet包管理器快速安装的方法配置OpenGL环境，详细步骤如下： 一、打开VS2019，创建新的控制台项目二、方法一：手动配置GLEW/GLFW/GLAD库 GLFW是窗口管理和输入事件的基础设施&…...

编程日记 2025/8/6 22:22:55

局部LDblock 绘图 1. 查看显著位点附近基因情况链接pvalue显著位点文件 ln -s ~/yiyaoran/GWAS/my_GWAS_J/P3.GWAS/01.tassel/mlm_output.manht_figure.sigSite.out . #也可以自己筛选awk $2 9 && $4 < 0.000028481 mlm_output.manht_input>368_GWAS.snpsnp两…...

编程日记 2025/8/2 13:36:39

WinForms开发基础：实现带X按钮的ClearableTextBox控件

前言我们经常看到这样的带X按钮的输入框如果使用WinForms开发中，该如何进行设计，普通的TextBox控件如何进行改造？为了提升用户体验，在TextBox文本框内添加一个“x”按钮，方便用户一键清除内容。本文将介绍如何通过继…...

编程日记 2025/8/6 22:22:56

直线轴承常规分类知多少？

直线轴承的分类方式多样，以下是从材质、结构形状和常规系列三个维度进行的具体分类： 按主要材质分类外壳材质：常见的有不锈钢，具有良好的耐腐蚀性，适用于一些对环境要求较高、易受腐蚀的工作场景；轴承…...

编程日记 2025/8/6 8:20:49

算法期末复习

算法期末复习 1.单选题 \1. 二分搜索算法是利用( A)实现的算法。 A. 分治策略 B. 动态规划法 C. 贪心法 D. 回溯法 \2. 回溯法解旅行售货员问题时的解空间树时( C ) 。 A. 子集树 B. 深度优先生成树 C. 排序树 D. 广度优先生成树 \3. 下列算法中通常以自底向上的方式求解最…...

编程日记 2025/8/5 14:13:04

LeetCode 5：最长回文子串

1、题目描述给你一个字符串 s，找到 s 中最长的回文子串。示例 1: 输入：s "babad" 输出："bab" 解释："aba" 同样是符合题意的答案。示例 2: 输入：s "cbbd" 输出&#…...

编程日记 2025/8/1 5:31:13

2025年4月19日记录大模型出现的计算问题

2025年4月19日记录大模型出现的计算问题，用了四个大模型计算json的数值，3个错误，1个正确问题 Class Train Val answer 2574 853 screen 5025 1959 blackBoard 7847 3445 teacher 8490 3228 stand…...

编程日记 2025/7/26 16:22:58

Python语法系列博客 · 第3期数据结构入门（列表、元组、字典、集合）

上一期小练习解答（第2期回顾） ✅ 练习1：判断一个数是正数、负数还是零 num float(input("请输入一个数：")) if num > 0:print("正数") elif num < 0:print("负数") else:print("零&q…...

编程日记 2025/8/4 1:25:03

【对Linux文件权限的深入理解】

Linux文件权限 Linux下权限概念概念相关命令 Linux的文件权限管理1.文件访问者的分类（⼈）文件类型和访问权限（事物属性）文件权限值的表示方法⽂件访问权限的相关设置方法目录的权限（比较重要）粘滞位 Linux下…...

编程日记 2025/8/2 22:11:25

2025.04.19【Spider】| 蜘蛛图绘制技巧精解

Basic multi-group radar chart Start with a basic version, learn how to format your input dataset Radar chart with ggradar A Spider chart made using the ggradar package and a lot of customization.A work by Tuo Wang 文章目录 Basic multi-group radar chartRa…...

编程日记 2025/8/3 4:29:57

AtCoder ABC402 A~D 题解

A - CBC 题目大意给点字符串 S S S，输出其中所有大写字母。思路根据题意模拟即可。代码 #include <cstdio> #include <iostream> #include <algorithm> using namespace std;int main() {string s;cin >> s;for (int i 0; i &l…...

编程日记 2025/8/5 19:40:01

双指针算法（部分例题解析)

快慢指针左右指针前言双指针，它通过设置两个指针来遍历数据，从而实现高效的查找、排序、去重等操作。双指针算法的核心在于通过合理地移动这两个指针，减少不必要的遍历，提高算法的效率。 283. 移动零 - 力扣（LeetCo…...

编程日记 2025/7/28 13:53:47

PHP怎样判断浏览器类型和浏览器语言？

获取浏览器类型 $_SERVER[HTTP_USER_AGENT]包含了用户代理字符串，该字符串包含了浏览器、操作系统等信息。通过分析这个字符串，可以大致判断用户使用的浏览器类型。 <?phpfunction getBrowserType() {$userAgent $_SERVER[HTTP_USER_AGENT];$brow…...

编程日记 2025/8/6 14:56:20

利用 i2c 快速从 Interface 生成 Class

利用 i2c 快速从 Interface 生成 Class（支持 TS & ArkTS） 在日常 TypeScript 或 ArkTS 开发中，需要根据 interface 定义手动实现对应的 class，这既重复又容易出错。分享一个命令行工具 —— interface2class，简称…...

编程日记 2025/8/6 9:12:13

Vue+Notification 自定义消息通知组件支持数据分页实时更新

效果图： message.vue 消息组件子组件 <template><div class"custom-notification"><div class"content"><span click"gotoMessageList(currentMessage.split()[1])">{{ currentMessage.split()[0] }}</…...

编程日记 2025/8/5 7:25:06

机械设计【】技术要求（实际使用）

目录台板技术要求加工件技术要求钣金件技术要求工装型腔技术要求铝型材框架技术要求装配体技术要求焊接件技术要求1（外形尺寸≥1500mm）焊接件技术要求2（外形尺寸＜1500mm）焊接件技术要求3（不锈钢）其他要求台板技术要求 1.台板下表面周边不倒角，其余未注倒角C0.5； 2.去…...

编程日记 2025/8/6 19:31:18

遨游科普：防爆平板是指什么？有哪些应用场景？

在石油开采平台的炽热甲板、化工园区的反应釜旁、矿井巷道的瓦斯弥漫区，总能看到一群手持特殊设备的作业人员。他们手中的平板并非寻常消费电子产品，而是专门应对极端环境的防爆平板。防爆平板承载着工业安全的核心诉求，其技术演进与应用拓展…...

编程日记 2025/7/30 5:54:19

【GCC】gcc编译学习

文章目录 1. 过程2. 常用命令选项3. 多个源文件编译参考内容 1. 过程 step1 : 预处理，生成.i文件（预处理器cpp） gcc -E [源文件] -o [生成的.i文件] gcc -E test.c -o test.istep2 : 汇编，将预处理后的文件转换为汇编语言生成.s…...

编程日记 2025/7/30 22:09:25

不确定与非单调推理的可信度方法

可信度方法是肖特里菲（E.H.Shortliffe)等人在确定性理论（Theoryof Comfirmation)的基础上，结合概率论等提出的一种不确定性推理方法，首先在专家系统MYCIN中得到了成功的应用。由于该方法比较直观、简单，而且效果也比较好，因而受到人们的重视。目前，许多专家系统都是基于…...

编程日记 2025/8/4 14:49:19

个人自用-导入安装Hexo

因为本人原来就有备份好的资料，所以重新安装起来会很方便，这个教程也只适合我自己用但是所有的命令行都要在Git的命令行里面使用（因为我就是这样操作的） 1 安装Git Git的官网 Git git --version 这个是查看Git的版本 git --…...

编程日记 2025/8/1 19:15:37

2025年最新版 Git和Github的绑定方法，以及通过Git提交文件至Github的具体流程(详细版)

文章目录 Git和Github的绑定方法与如何上传至代码仓库一. 注册 GitHub 账号二.如何创建自己的代码仓库：1.登入Github账号，完成登入后会进入如下界面：2.点击下图中红色框选的按钮中的下拉列表3.选择New repostitory4.进入创建界面后&#xff0…...

编程日记 2025/8/3 1:55:03

Java 动态代理实现

Java 动态代理实现一、JDK动态代理二、CGLIB动态代理三、动态代理的应用场景四、JDK代理与CGLIB代理比较动态代理是Java中一种强大的技术，它允许在运行时创建代理对象，用于拦截对目标对象的方法调用。一、JDK动态代理 JDK动态代理是Java标准库提供的代…...

编程日记 2025/7/27 16:54:39

从零开始搭建CLIP模型实现基于文本的图像检索

目录 CLIP原理简介代码实现参考链接 CLIP原理简介论文链接，源码链接 CLIP模型由OpenAI在2021年提出，利用双Decoder（Dual Encoder）的架构来学习图像和文本之间的对应关系，是多模态大模型的开创之作，为后续许…...

编程日记 2025/7/30 1:09:19

健康养生之道

在快节奏的现代生活中，健康养生不再是中老年人的专属话题，越来越多的人开始意识到，合理的养生方式是保持良好身体状态和生活质量的关键。饮食养生是健康的基石。遵循 “食物多样、谷类为主” 的原则，保证每天摄入足够的蔬菜、…...

编程日记 2025/7/28 6:27:25

基于autoware.1.14与gazebo联合仿真进行Hybrid A* 算法规划控制代价地图版

1.首先安装autoware ，大家可以以下一下博客进行安装，如果缺少库什么的直接问ai安装对应的库就行。ubuntu18.04安装Autoware1.14---GPU版最全环境配置说明_autoware1.14安装教程-CSDN博客安装成功后运行： source install/setup.bash roslau…...

编程日记 2025/7/24 7:48:09

5G基站设计难题：尺寸、重量、功耗和散热

设计5G基站的工程师们必须应对能源消耗、重量、尺寸和散热等问题，这些因素会影响到设计决策。 5G新空口（NR）采用了多用户大规模多输入多输出（MU-MIMO）技术、集成接入与回传（IAB）技术&#xff0…...

编程日记 2025/8/3 13:02:23

【leetcode100】分割等和子集

1、题目描述给你一个只包含正整数的非空数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。示例 1： 输入：nums [1,5,11,5] 输出：true 解释：数组可以分割成 [1, 5, 5] 和 [11…...

编程日记 2025/8/1 13:43:10

sed命令笔记250419

sed命令笔记250419 sed（Stream Editor）是 Linux/Unix 系统中强大的流编辑器，主要用于对文本进行过滤和转换（按行处理）。它支持正则表达式，适合处理文本替换、删除、插入等操作。以下是 sed 的详细解析&…...

编程日记 2025/8/1 22:03:25

LinearLayout 线性布局

目录 Android LinearLayout（线性布局）简单介绍与使用示例一、效果介绍二、布局文件（XML） 三、Java 代码四、程序运行效果五、总结在 Android 移动应用开发中，LinearLayout（线性布局）…...

编程日记 2025/8/5 4:13:41

System.in 详解

System.in 详解 System.in 是 Java 提供的标准输入流（InputStream 类型），默认关联键盘输入，通常用于从控制台读取用户输入。由于它是字节流（InputStream），直接使用较麻烦，一般会配合…...

编程日记 2025/8/3 1:31:16

JAVA IO、BIO、NIO、AIO及零拷贝

概述 IO，常写作 I/O，是 Input/Output 的简称，是 Input/Output 的简称，即输入/输出。通常指数据在内部存储器（内存）和外部存储器（硬盘、优盘等）或其他周边设备之间的输入和输出。目前有三种 IO 共存。分别是 BIO、NIO 和 AIO。 BIO 全称 Block-IO 是一种同步且阻塞的…...

编程日记 2025/7/30 5:54:13

AI预测3D新模型百十个定位预测+胆码预测+去和尾2025年4月19日第57弹

从今天开始，咱们还是暂时基于旧的模型进行预测，好了，废话不多说，按照老办法，重点8-9码定位，配合三胆下1或下2，杀1-2个和尾，再杀6-8个和值，可以做到100-300注左右。 (1)定…...

编程日记 2025/8/5 1:33:37

REST 架构详解：从概念到应用的全面剖析

REST（Representational State Transfer）即表述性状态转移，是一种用于构建网络应用程序的架构风格和设计理念，由计算机科学家罗伊・菲尔丁（Roy Fielding）在 2000 年提出。以下是关于它的详细介绍&#xff1a…...

编程日记 2025/7/30 5:54:08

SICAR程序标准功能块 FB1512 “Robot_kuka_FB“

1、FB1512功能块截图 2、FB1512 功能块引脚功能定义一、输入引脚 EN：使能输入，决定功能块是否执行。IDENTIFIER（WSTRING#"FW010_R01"）：设备标识，指定关联的机器人设备。OPMODE_USER_INTERFACE_OUT：操作模式输入，定义机器人工作模式（如手动、自动），数据源…...

编程日记 2025/8/5 1:10:19

win安装软件

win安装软件 jdk安装 jdk安装首先去官网下载适合系统版本的JDK，下载地址： http://www.oracle.com/technetwork/java/javase/downloads/index.html进入下载页面，如下图： 首先选择：Accept License Agreement单选按钮&…...

编程日记 2025/8/3 23:04:13

文本生成与采样策略 (Text Generation Sampling)

我们已经学习了如何构建和训练一个基于 Transformer Decoder-only 的语言模型。模型训练的目标是学习预测给定前缀下下一个 token 的概率分布。但是，训练完成后，我们如何利用这个模型来生成全新的、连贯的文本呢？这就涉及到推理过程和采样策略。推理是模型投入实际使用、生…...

编程日记 2025/8/3 12:18:22

为什么 waitress 不支持 WebSocket？

waitress 是一个纯 Python 实现的 WSGI 服务器，主要用于生产环境部署 Python Web 应用。但它不支持 WebSocket 协议，因为它只实现了 WSGI 规范，而 WebSocket 协议需要 ASGI（Asynchronous Server Gateway Interface）支持…...

编程日记 2025/7/31 22:35:39

[C++] 高精度加法(作用 + 模板 + 例题)

高精度加法-目录高精度加法用途高精度加法模板string转数位数组int 转数位数组(附加型知识点)高精度输出高精度加法函数大合集!!! 高精度加法用途高精度加法通常用于加很大的数(真的很大, 超unsigned long long的那种). 高精度加法模板注: 本篇数组下标0(x[0])存储的是该…...

编程日记 2025/7/29 18:59:02

python程序的流程

三大基本流程： 顺序结构、分支结构（又称为选择结构）、循环结构分支结构又分为单分支、双分支、多分支从键盘上输入一个数字，并输出奇数或偶数 #从键盘上输入一个数字，并输出奇数或偶数 nint(input("n ")…...

编程日记 2025/7/31 9:52:05

基于大模型的下肢静脉曲张全流程预测与诊疗方案研究报告

目录一、引言 1.1 研究背景与意义 1.2 研究目的与创新点 1.3 研究方法与数据来源二、下肢静脉曲张概述 2.1 定义与病理生理 2.2 风险因素与临床表现 2.3 诊断方法与现有治疗手段三、大模型预测原理与构建 3.1 大模型技术简介 3.2 预测模型的数据收集与预处理 3.…...

编程日记 2025/8/6 13:38:26

Android 应用wifi direct连接通信实现

一. 打开Wi-Fi direct 1.必须启用Wi-Fi功能：在设备设置中开启Wi-Fi主开关（即使未连接路由器） 关闭冲突功能：若已开启「热点共享」或连接到其他Wi-Fi网络，需先关闭相关功能以避免硬件占. <!-- Wi-Fi Direct 核心权限…...

编程日记 2025/7/30 8:05:12

AI写代码工具分享：Cursor 高效使用攻略与实战秘籍

写在前面在软件开发领域，效率和生产力是永恒的追求。集成开发环境（IDE）作为开发者的核心工具，其能力直接影响着开发速度和质量。近年来，人工智能（AI）的浪潮席卷了各个行业，编程领域也不例外。Cursor IDE 正是这股浪潮中的佼佼者，它以 AI-First 的理念，在广受欢迎的…...

编程日记 2025/8/6 21:38:45

关于viewpager常见的泄漏

在一个页面中如果有用到tab，有需要进行fragment的切换，经常就看到了private var fragments arrayListOf<Fragment>()private fun initFragment() {arguments?.let {hopeToPosition it.getInt(IntentConstant.MAIN_PAGE_GO, 0)workoutType it.…...

编程日记 2025/8/3 22:02:27

vue3专题1------父组件中更改子组件的属性

理解 Vue 3 中父组件如何引用子组件的属性是一个很重要的概念。这里涉及到 defineExpose 和 ref 这两个关键点。方法：使用 defineExpose 在子组件中暴露属性，然后在父组件中使用 ref 获取子组件实例并访问暴露的属性。下面我将详细解释这个过程&…...

编程日记 2025/8/5 3:40:38