IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 【5.7】Codeforces 刷题 -> 正文阅读

[数据结构与算法]【5.7】Codeforces 刷题

B. Simple Game

题意:给 n,m (m <= n),求一个数 a(1<= a <=n), 使得当 c 在 1 到 n 的整数中 随机取值时 ,|c-a| < |c-m| 成立的概率最大。

思路:特判 n=m=1。然后判断 n-1 和 m-n 的大小,哪边更大选哪边。

AC代码:https://codeforces.com/contest/570/submission/156198893


C. Phoenix and Towers

题意:给你 n 个数, 要求你把这些数字分成 m 组, 使得任意两组之间的差值不超过 x .

思路:贪心。。优先队列维护,选当前高度最小的加上去。因为保证了 h i ≤ x h_i ≤ x hi?x ,因此必定存在解,任意顺序添加都可。题解 CF1515C 【Phoenix and Towers】


C. Ehab and Path-etic MEXs

题意:

在这里插入图片描述

思路:

首先分析。定义 m e x = max ? { M E X ( u , v ) } mex = \max\{MEX(u,v)\} mex=max{MEX(u,v)} 。因为 0 必定存在某条链中,因此 m e x ≥ 1 mex≥1 mex1 。因为图联通,必定存在某条链同时含有 0 1,因此 m e x ≥ 2 mex≥2 mex2

2 就是一个下界,我们思考能否构造出这样的下界。思考后发现 mex=2 的情况只与 0 1 2 同时有关,当这三个数出现在一条链中 mex > 2 ,否则 mex = 2。什么时候不在一条链上呢?我们利用非链无根树的性质:必定存在某个节点存在至少三棵子树。我们找到这样的点,把 0 1 2 分配上去即可。

AC代码:https://codeforces.com/contest/1325/submission/156203262


B. Moderate Modular Mode

题意:给定两个偶数 x , y x,y x,y

求一个 n ∈ [ 1 , 2 × 1 0 18 ] n \in [1,2\times10^{18}] n[1,2×1018] 满足 n ? m o d ? x = y ? m o d ? n n \bmod x = y \bmod n nmodx=ymodn

一个测试点有多组数据,数据保证有解

思路:关键在于 x < y 的情况。找到小于等于 y 的最大 x 的倍数 kx,然后取中间值即可。可以保证 n ? m o d ? k x = n ? m o d ? x , n ≥ k x n \bmod {kx}=n \bmod x,n≥kx nmodkx=nmodx,nkx

这里总结了式子:当 x , y ≥ 1 x,y ≥ 1 x,y1

k × x ≤ y , k m a x = ? y x ? × x k\times x ≤ y,k_{max}=\lfloor \frac y x \rfloor \times x k×xy,kmax?=?xy??×x

k × x < y , k m a x = ? y ? 1 x ? × x k\times x < y,k_{max}=\lfloor \frac {y-1} x \rfloor \times x k×x<y,kmax?=?xy?1??×x

k × x ≥ y , k m i n = ? y x ? × x k\times x ≥ y,k_{min}=\lceil \frac y x \rceil \times x k×xy,kmin?=?xy??×x

k × x > y , k m i n = ? y + 1 x ? × x k\times x > y,k_{min}=\lceil \frac {y+1} x \rceil \times x k×x>y,kmin?=?xy+1??×x

AC代码:https://codeforces.com/contest/1603/submission/156282752


D. Vasya and Chess

题意:

在这里插入图片描述
题解:CF493D Vasya and Chess 题解

思路:和环形博弈有异曲同工之妙,但是没想出来。奇数时先手必败,偶数先手时可以转化为奇数后手的情况,此时必胜。

AC代码:https://codeforces.com/contest/493/submission/156282913

  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2022-05-10 12:08:32  更:2022-05-10 12:11:15 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年11日历 -2024/11/26 3:54:49-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码