| |
|
开发:
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 mex≥1 。因为图联通,必定存在某条链同时含有 0 1,因此 m e x ≥ 2 mex≥2 mex≥2 。 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,n≥kx 。 这里总结了式子:当 x , y ≥ 1 x,y ≥ 1 x,y≥1 k × x ≤ y , k m a x = ? y x ? × x k\times x ≤ y,k_{max}=\lfloor \frac y x \rfloor \times x k×x≤y,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×x≥y,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题意: 思路:和环形博弈有异曲同工之妙,但是没想出来。奇数时先手必败,偶数先手时可以转化为奇数后手的情况,此时必胜。 AC代码:https://codeforces.com/contest/493/submission/156282913 |
|
|
上一篇文章 下一篇文章 查看所有文章 |
|
开发:
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- |
|
网站联系: qq:121756557 email:121756557@qq.com IT数码 |