最新要闻
- 别只用来发电了 太阳能制氢突破!10倍效率 成本还更低
- 全球即时看!全球首个全功能无线底座问世:干掉线缆 满足4K/60Hz带宽
- 今头条!豆瓣9.6分 《中国奇谭》凭什么让国漫再次封神?
- 全球要闻:Intel Arc A750显卡深入测试:性能RTX 3060、功耗RTX 3070
- 天天微速讯:官方批准ARJ21国产客机改货机!最大运力10吨
- 天天微资讯!3.2K/165hz屏!联想第四代ThinkBook 16P发布: 配独特触点接口
- 每日速讯:汤姆·汉克斯谈好莱坞裙带关系:本就是家族产业
- 【天天播资讯】雷蛇灵刃18游戏本发布:18寸240Hz大屏、RTX 4090显卡替代台式机
- 特斯拉再降价 Model 3创历史新低!老车主亏哭了 山顶买车血亏6万
- 耗资两亿的《三体》 在《中国奇谭》面前毫无价值
- 每日焦点!TCL华星展示最新带鱼屏模组:暗处无限接近0nit
- 天天热议:矿卡的阴影已经过去了 板卡一哥华硕率先表态:显卡库存已正常
- 全球观速讯丨遇到查酒驾猛打方向盘 结果巧了:直接一步到位
- 全球快资讯:无视油车 特斯拉Model Y成英国12月最畅销汽车
- 世界播报:售价超2万元!世界首款真无线电视现身CES:电池供电不插线
- 世界观热点:国人不再迷信日本车 日产2022年累计销量105万:同比暴跌超1/5
手机
iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?
警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案
- iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?
- 警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案
- 男子被关545天申国赔:获赔18万多 驳回精神抚慰金
- 3天内26名本土感染者,辽宁确诊人数已超安徽
- 广西柳州一男子因纠纷杀害三人后自首
- 洱海坠机4名机组人员被批准为烈士 数千干部群众悼念
家电
环球微速讯:Codeforces Round #842 (Div. 2) A-E
比赛链接
(资料图片仅供参考)
A
题意
给一个数 \(k\) 找到最大的 \(x\) ,满足 \(1 \leq x < k\) 且 \(x!+(x-1)!\) 是 \(k\) 的倍数。
题解
知识点:数学。
猜测 \(x = k-1\) ,证明 \((k-1)! + (k-2)! = (k-1+1) \cdot(k-2)! = k \cdot (k-2)!,k \geq 2\) 。
因此 \(x = k-1\) 。
时间复杂度 \(O(1)\)
空间复杂度 \(O(1)\)
代码
#include #define ll long longusing namespace std;bool solve() { int k; cin >> k; cout << k - 1 << "\n"; return true;}int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int t = 1; cin >> t; while (t--) { if (!solve()) cout << -1 << "\n"; } return 0;}
B
题意
给一个长为 \(n\) 的排列,每次操作从排列中取出 \(k\) 个数,从小到大排序好放回排列尾部。问最少操作多少次,才能将原排列变成从小到大排序好的排列。
题解
知识点:贪心。
注意到每次操作都会把数字放到尾部,不会影响之前数字的相对位置。因此为了使得操作最小化,我们先找到不用选的数字有多少,显然我们需要从 \(1\) 开始递增往后找。设 \(pos\) 是第一个要选的数字,那么答案便是 \(\Big\lceil \dfrac{n - pos + 1}{k} \Big\rceil\) 。
时间复杂度 \(O(n)\)
空间复杂度 \(O(n)\)
代码
#include #define ll long longusing namespace std;int a[100007];bool solve() { int n, k; cin >> n >> k; for (int i = 1;i <= n;i++) cin >> a[i]; int pos = 1; for (int i = 1;i <= n;i++) { if (pos == a[i]) pos++; } cout << (n - pos + 1 + k - 1) / k << "\n"; return true;}int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int t = 1; cin >> t; while (t--) { if (!solve()) cout << -1 << "\n"; } return 0;}
C
题意
给出 \(n\) 个数 \(a_i\) ,要求两个长为 \(n\) 的排列 \(p,q\) 使得 \(a_i = \max(p_i,q_i)\) 。
题解
知识点:构造。
先记录每个数字出现的位置 \(pos[a[i]]\) ,随后从小到大构造:
- 数字没出现过,那么可以放入队列 \(qu\) ,用于补齐出现两次的数字的空位。
- 数字只出现了一次,假设出现在 \(a_i\) ,那么令 \(p_i = q_i = a_i\) 是最优的。因为 \(p_i,q_i\) 其中一个可以更小,但小的数字可能要用于填充别的地方,所以最优解是填两个相等的。
- 数字出现了两次,假设出现在 \(a_i = a_j = a\) ,那么令 \(p_i = q_j = a\) ,设 \(qu\) 里队首元素为 \(x\) ,令 \(q_i = p_j = x\) 。因为是从小到大构造,所以 \(qu\) 里的元素一定是比 \(a\) 小的,所以可以用来填充空位;如果队空,则无解。
- 数字出现三次及以上,无解。
时间复杂度 \(O(n)\)
空间复杂度 \(O(n)\)
代码
#include #define ll long longusing namespace std;int a[200007];int p[200007], q[200007];vector pos[200007];bool solve() { int n; cin >> n; for (int i = 1;i <= n;i++) cin >> a[i], pos[i].clear(); for (int i = 1;i <= n;i++) pos[a[i]].push_back(i); queue qu; for (int i = 1;i <= n;i++) { if (pos[i].size() > 2) return false; if (pos[i].size() == 0) qu.push(i);//空闲数字放入队列 else if (pos[i].size() == 1) { p[pos[i][0]] = i; q[pos[i][0]] = i; }//可以用小的但不是最优的 else { if (qu.empty()) return false;//没有空闲的小的数字,无解 p[pos[i][0]] = i; p[pos[i][1]] = qu.front(); q[pos[i][0]] = qu.front(); q[pos[i][1]] = i; qu.pop(); } } cout << "YES" << "\n"; for (int i = 1;i <= n;i++) cout << p[i] << " \n"[i == n]; for (int i = 1;i <= n;i++) cout << q[i] << " \n"[i == n]; return true;}int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int t = 1; cin >> t; while (t--) { if (!solve()) cout << "NO" << "\n"; } return 0;}
D
题意
给一个长为 \(n\) 的排列,每次可以选择两个数交换,问最少交换几次可以使得排列逆序数为 \(1\) 。
题解
知识点:枚举,数学。
关于这类排列的题,都可以先进行一个构造,连接所有 \(i \to a[i]\) ,图中会形成若干个环,称为置换环。例如 \(2,3,4,1,5\) ,可以得到 \(1,2,3,4\) 构成的环和 \(5\) 构成的环( \(5\) 是自环)。
我们进行一次交换操作 \((i,j)\),将使得 \(i \to a_i,j \to a_j\) 两条边变成 \(i \to a_j,j \to a_i\) 。这个操作在图中可以做到以下两个结果之一:
- 一个环被裂解成两个环
- 两个环被合并成一个环
前提是不破坏相对元素的位置,例如 \(1,3,2,4\) 环不可能分解成 \(1,2\) 和 \(3,4\) 环;\(1,2\) 和 \(3,4\) 环也不可能合并成 \(1,3,2,4\) 环。
举个例子,我们对 \(2,3,4,1,5\) 交换 \((2,4)\) ,则排列变成 \(2,1,4,3,5\) ,图中边 \(2 \to 3,4\to 1\) 变成 \(2 \to 1,4 \to 3\) ,即 \(1,2,3,4\) 环被拆成 \(1,2\) 和 \(3,4\) 两个环;或者交换 \((4,5)\) ,则排列变成 \(2,3,4,5,1\) ,图中边 \(4 \to 1,5 \to 5\) 变成 \(4 \to 5,5 \to 1\) ,即 \(1,2,3,4\) 和 \(5\) 环被合成为 \(1,2,3,4,5\) 环。
回到题目。题目要求的最终状态化成图后,实际上就是一组相邻元素成环,剩下的元素自环。
我们对原排列化为置换环图,假设这些环中已经有至少一组相邻元素(环中位置不一定需要相邻,因为可以通过操作使其相邻),如 \(1,4,2\) 环就有 \(1,2\) 两个相邻元素,我们可以在之后的操作中保留这组元素,把其他元素全都操作成自环即可;如果没有,那么先将元素都操作成自环,再多一次操作把一组相邻元素合并成环,如排列 \(3,4,5,2,1\) 有 \(1,3,5\) 和 \(2,4\) 环,一个相邻元素都没有。
假设 \(n\) 个元素的图中有 \(cnt\) 个环,那么如果我们需要把环中元素都操作成自环,实际上需要操作 \(n-cnt\) 次,因为每个环保留一个元素,剩下的元素都需要通过操作挪出来。再考虑相邻元素的结论,如果有相邻元素那么可以少操作一次 \(n-cnt-1\) ;否则需要多操作一次 \(n-cnt+1\) 。
环的实现可以看代码,和并查集类似但简单许多。
时间复杂度 \(O(n)\)
空间复杂度 \(O(n)\)
代码
#include #define ll long longusing namespace std;int a[200007];int fa[200007];bool solve() { int n; cin >> n; for (int i = 1;i <= n;i++) cin >> a[i], fa[i] = -1; int ans = n; for (int i = 1;i <= n;i++) { if (fa[i] != -1) continue; int j = i; ans--;//一个环减一次, while (fa[j] == -1) { fa[j] = i;//环内元素的根设为i j = a[j]; } } bool ok = 0; for (int i = 1;i <= n - 1;i++) ok |= fa[i] == fa[i + 1];//环内有一队相邻元素,可以少操作一次 cout << ans + (ok ? -1 : 1) << "\n"; return true;}int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int t = 1; cin >> t; while (t--) { if (!solve()) cout << -1 << "\n"; } return 0;}
E
题意
对一个长度为 \(3n\) 的排列 \(p\),有两种操作:
- 对前 \(2n\) 个元素从小到大排序
- 对后 \(2n\) 个元素从小到大排序
定义 \(f(p)\) 为将排列 \(p\) 通过操作从小到大排序好的最少次数。
现在给出一个 \(n\) ,求长度为 \(3n\) 的 \((3n)!\) 个排列的 \(f(p)\) 之和。
题解
知识点:容斥原理,排列组合。
显然,对于任意排列 \(p\) ,\(f(p) \leq 3\) ,只要使用操作 \(1,2,1\) 就能排序好。
现在分类讨论 \(f(p)\) ,求对应的种类数。注意到,求精确 \(f(p) = 1,2,3\) 的种类数比较困难,因此考虑求 \(f(p) \leq 1,f(p)\leq 2,f(p) \leq 3\) 的情况,最后作差即可。
- \(f(p) = 0\)
显然只有一种 \(1,\cdots,3n\) 。
- \(f(p) \leq 1\)
至多一次操作就可以排序好,那么一定是前 \(n\) 个或者后 \(n\) 个元素已经排好了,其他元素自由排列,对剩下部分操作一次即可。
前 \(n\) 个元素排好了,后 \(2n\) 个自由排列,一共 \((2n)!\) 种。同理,后 \(n\) 个元素排好了也有 \((2n)!\) 种。
当然,最后需要减去交集,即前 \(n\) 个元素和后 \(n\) 个元素同时排好了,则中间 \(n\) 个元素自由排列,有 \(n!\) 种。
因此,最终有 \(2 (2n)! - n!\) 种。
- \(f(p) \leq 2\)
至多两次操作就可以排序好,那么元素 \([1,n]\) 需要出现在 \([1,2n]\) 的区间里,其他元素自由排列,这样对 \([1,2n]\) 操作一次前 \(n\) 个就排好了,再对 \([n+1,3n]\) 操作一次即可,同理元素 \([2n+1,3n]\) 出现在 \([n+1,3n]\) 其他元素自由排列也可以,只需要最多操作两次。
元素 \([1,n]\) 出现在 \([1,2n]\) ,那么在 \(2n\) 个位置里选 \(n\) 个位置放这 \(n\) 个元素,并且这 \(n\) 个元素可以自由排列,剩下 \(2n\) 个元素也可以自由排列,因此有 \(C_{2n}^n \cdot n!\cdot (2n)!\) 种。同理,元素 \([2n+1,3n]\) 出现在 \([n+1,3n]\) 也有 \(C_{2n}^n \cdot n!\cdot (2n)!\) 种。
最后减去交集部分,即元素 \([1,n]\) 出现在 \([1,2n]\) 同时元素 \([2n+1,3n]\) 出现在 \([n+1,3n]\) 。直接算比较困难,考虑设元素 \([1,n]\) 种有 \(i\) 个元素出现在 \([n+1,2n]\) 中,则元素 \([1,n]\) 有 \(n-i\) 个元素出现在 \([1,n]\) 中。于是,对于元素 \([1,n]\) ,在 \([1,n]\) 选 \(n-i\) 个位置,在 \([n+1,2n]\) 选 \(i\) 个位置,并任意排列,有 \(C_{n}^{n-i} \cdot C_{n}^{i} \cdot n!\) 种;对于元素 \([2n+1,3n]\) ,因为 \([n+1,2n]\) 有 \(i\) 个 \([1,n]\) 的元素,所以在 \([n+1,3n]\) 有 \(2n-i\) 个位置可以选,其中中选 \(n\) 个,并任意排列,有 \(C_{2n-i}^n \cdot n!\) 种;剩下 \(n\) 个元素任意排列有 \(n!\) 种,共有 \(C_{n}^{n-i} \cdot C_{n}^{i} \cdot n! \cdot C_{2n-i}^n \cdot n! \cdot n!\) 种。 最终把 \(i \in [0,n]\) 累加一遍就是交集部分。
因此,最终有 \(2\cdot C_{2n}^n \cdot n!\cdot (2n)! - \sum_{i=0}^n (C_{n}^{n-i} \cdot C_{n}^{i} \cdot n! \cdot C_{2n-i}^n \cdot n! \cdot n!)\) 种。
- \(f(p) \leq 3\)
全排列即可,共有 \((3n)!\) 种。
最后,做差就可以得到 \(f(p) = 1,2,3\) 的种类数,分别加权和即可。
时间复杂度 \(O(n)\)
空间复杂度 \(O(n)\)
代码
#include #define ll long longusing namespace std;int M;int qpow(int a, int k) { int ans = 1; while (k) { if (k & 1) ans = 1LL * ans * a % M; k >>= 1; a = 1LL * a * a % M; } return ans;}int fac[3000007], invfac[3000007];void init(int n) { fac[0] = 1; for (int i = 1;i <= n;i++) fac[i] = 1LL * fac[i - 1] * i % M; invfac[n] = qpow(fac[n], M - 2); for (int i = n;i >= 1;i--) invfac[i - 1] = 1LL * invfac[i] * i % M;}int C(int n, int m) { if (n < m || m < 0) return 0; return 1LL * fac[n] * invfac[m] % M * invfac[n - m] % M;}int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int n; cin >> n >> M; init(3 * n); int ans[4]; ans[0] = 1; ans[1] = (1LL * 2 * fac[2 * n] % M - fac[n] + M) % M; ans[2] = 1LL * 2 * C(2 * n, n) % M * fac[n] % M * fac[2 * n] % M; for (int i = 0;i <= n;i++) { ans[2] = (ans[2] - 1LL * C(n, i) * C(n, n - i) % M * fac[n] % M * C(2 * n - i, n) % M * fac[n] % M * fac[n] % M + M) % M; } ans[3] = fac[3 * n]; ans[1] = (ans[1] - ans[0] + M) % M; ans[2] = ((ans[2] - ans[1] + M) % M - ans[0] + M) % M; ans[3] = (((ans[3] - ans[2] + M) % M - ans[1] + M) % M - ans[0] + M) % M; int res = ((ans[1] + 1LL * 2 * ans[2] % M) % M + 1LL * 3 * ans[3] % M) % M; cout << res << "\n"; return 0;}
-
环球微速讯:Codeforces Round #842 (Div. 2) A-E
比赛链接A题意给一个数$k$找到最大的$x$,满足$1 leqx<k$且$x!+(x-1)!$是$k$的倍数。题解知识点:数学。猜测$x=k-1$
来源: 环球微速讯:Codeforces Round #842 (Div. 2) A-E
焦点速读:使用KVM创建OEL虚拟机
别只用来发电了 太阳能制氢突破!10倍效率 成本还更低
全球即时看!全球首个全功能无线底座问世:干掉线缆 满足4K/60Hz带宽
今头条!豆瓣9.6分 《中国奇谭》凭什么让国漫再次封神?
全球要闻:Intel Arc A750显卡深入测试:性能RTX 3060、功耗RTX 3070
今日快讯:内网渗透-PTH&PTK&PTT哈希票据传递
天天微速讯:官方批准ARJ21国产客机改货机!最大运力10吨
天天微资讯!3.2K/165hz屏!联想第四代ThinkBook 16P发布: 配独特触点接口
每日速讯:汤姆·汉克斯谈好莱坞裙带关系:本就是家族产业
【天天播资讯】雷蛇灵刃18游戏本发布:18寸240Hz大屏、RTX 4090显卡替代台式机
特斯拉再降价 Model 3创历史新低!老车主亏哭了 山顶买车血亏6万
耗资两亿的《三体》 在《中国奇谭》面前毫无价值
内网信息收集
今日观点!day03-模块化编程
今日最新!vue中$children的理解
每日焦点!TCL华星展示最新带鱼屏模组:暗处无限接近0nit
天天热议:矿卡的阴影已经过去了 板卡一哥华硕率先表态:显卡库存已正常
全球观速讯丨遇到查酒驾猛打方向盘 结果巧了:直接一步到位
全球快资讯:无视油车 特斯拉Model Y成英国12月最畅销汽车
世界播报:售价超2万元!世界首款真无线电视现身CES:电池供电不插线
记录--微信调用jssdk全流程详解
最新:LaTeX 进阶语法
世界观热点:国人不再迷信日本车 日产2022年累计销量105万:同比暴跌超1/5
当前热讯:又见白菜价 梅捷2TB SSD硬盘到手554元(每GB不到3毛)
HTC Vive XR眼镜发布:双2K屏、配有可拆卸电池
最资讯丨四川一地再现土坑酸菜 工人用脚踩 网友无奈:眼不见为净
每日视讯:Redmi K60/K60 Pro对比拆解:做工用料良心!性价比刚刚的
【吐槽贴】项目经理的进阶日常:项目要收尾了,我却慌了
当前滚动:三亚民宿老板称一个月赚回三年亏损:20万一晚酒店已售罄
焦点关注:谁说微星不做AMD显卡了!RX 7900终于亮相 只是有点敷衍
天天快播:红魔8 Pro系列即将再次开卖:3999元起 首销曾被抢购一空
云南发现2.44亿年前“奇异罗平龙”化石:身长超半米 像蜥蜴
马化腾服不服?李彦宏:百度研发强度、投入国内最牛 比腾讯高
通讯!Git管理版本详细教程
世界快播:手工实现一个ORM小框架
【天天播资讯】AIRIOT答疑第5期|如何使用低代码业务流引擎?
亲测有效! Bypass V1.15.5 12306分流抢票助手 for Windows
每日视讯:比亚迪仰望:那年我翻山跨海 横扫车圈无对手
信息:联想Yoga Book 9i双屏笔记本发布:两块13寸2.8K触摸屏
当前视讯!AMD锐龙7000智酷版上架!6核不过1549元 可能有惊喜
天天观焦点:女子吐槽智能电视会员乱象:看什么都收费
环球速递!国产秀肌肉!全球首款8K激光电视来了:海信打造、画质细数毛
【世界快播报】保存用户登录状态之Session和JWT
【世界热闻】three.js场景地形导出到物理引擎
网站变更检测、监控、警报丨WebSite-Watcher功能简介
基于Python的K-Means遥感影像聚类
苹果iOS app上架流程
世界观察:《阿凡达2》接招!国产科幻大片走出国门 《流浪地球2》将在澳新上映
消息!特斯拉国产车型大幅降价 副总裁陶琳回应:坚持以成本定价
Win11 2023开年更新Build 25272发布:干掉中文版大BUG!更加流畅稳定
特斯拉降价 网友翻出蔚来李斌2年前视频:价格稳定是对用户负责
天天新消息丨智能电视视频会员一充再充!体验太差了
全球即时:gget: 一款强大的基因组参考数据库的高效查询工具
学习笔记——过滤器链;监听器;Servlet、Filter、Listener的注解方式开发
Model 3要破20万节奏!特斯拉国产车型大幅降价 老车主晒图被割韭菜
redhat 9.1 安装docker
天天通讯!nginx: [error] CreateFile() “D:\nginx1.20.1/logs/nginx.pid“ failed (2: The
学习笔记——过滤器的匹配规则
国产特斯拉大幅降价被业内看好 带火供应链:大批概念股飞涨
【天天播资讯】特斯拉 2023第一个交易日:市值缩水一个推特
天天播报:CDPR赔偿1267万!《赛博朋克2077》集体诉讼案终于告一段落
当前热点-汽车博主为小米汽车打抱不平:部分媒体只会道听途说
北斗授时产品(GPS北斗授时设备)加NTP时间服务器设计思路
世界最资讯丨学习笔记——过滤器、过滤器的HelloWord、过滤器生命周期
【全球新要闻】A. Greatest Convex【Codeforces Round #842 (Div. 2)】
【天天速看料】如何安全的保存用户密码
焦点热讯:灵雀云入选2022 EDGE AWARDS「创新场景50」年度最佳场景实践榜单
全球播报:联想ThinkPhone真机亮相:经典ThinkPad涂装抢眼
【世界独家】恒驰5首次OTA升级来了!低温续航性能提升
当前消息!超越日本!印度成全球第三大汽车市场 平均千人36辆
吴京参演 《中国乒乓之绝地反击》定档大年初一:春节档已有7部新片
男子和白骆驼合影被攻击!专家提醒:骆驼战斗力惊人
环球热文:使用python编写端口扫描工具
QFramework v1.0 使用指南 工具篇:15. 补充内容:GridKit 二维格子数据结构
速读:【从零开始学爬虫】采集食品行业最新报价数据
Redmi 12C支持内存扩展:4GB内存手机瞬间变6GB 699元性价比更高了
全球消息!RTX 4050加持!联想发布Yoga AIO 9i一体机:设计惊艳
国产车型大降价 新款特斯拉Model X/S售价公布:超100万
【焦点热闻】小米13被低估了!网友没想到小米13相机能有这么大惊喜
天天日报丨三件套抄底:李锦记锦珍大桶生抽+金蚝油+黄豆酱 19.6元
每日热闻!数据结构:ST表 学习笔记
快资讯:ESP32 I2C 总线主模式通信程序
天天观点:创新的概念、设计和生产鞋类和鞋类软件丨Jevero及Botcha 3D功能简介
学习笔记——书城项目第五阶段之购物车数量的修改、精度问题的处理
世界观速讯丨《人民日报》炮轰手机预装应用不能删:占内存、鸡肋、广告满天飞
【当前热闻】240W闪充卷王!真我GT Neo5即将登场:有两种版本
全球动态:TCL华星宣布品牌形象升级:全新Logo正式上线
12月汽车投诉榜:丰田包揽前三甲 踩的同一个“坑”
世界快资讯:PS5主机千万别再长期竖向放置了!维修人士:会导致APU液金泄露 造成永久损坏
当前关注:阿汤哥驾F14爽片《壮志凌云2》惜败!《阿凡达2》成2022年票房冠军 赢麻
快资讯丨回顾2022
全球简讯:春节放假7天要调休!除夕火车票明日开抢
骁龙8 Gen2首发!高通正式推出卫星通信:3秒发出信息、可实现双向收发
每日视讯:Intel怕吗!AMD锐龙7000史上最强核显 这性能不得了
好用的工具
世界最资讯丨Python中的注释和input函数的使用
世界视讯!被骗好久!宰相刘罗锅真的是一个罗锅吗?1.9米帅男一枚
环球视讯!5位退役也未曾飞天的航天员首次公开!他们也是英雄
天天精选!在我电脑里 这是唯一的一个360产品