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

题解:P14127 [SCCPC 2021] K-skip Permutation

题解:P14127 [SCCPC 2021] K-skip Permutation

题意

构造一个长度为 \(n\) 的排列 \(P\),使得 \(f(P,k)\) 最大。

对于 \(f(P,k)\) 的定义:对于一个 \(n\) 的排列 \(P=p_1,p_2,\cdots,p_n\)\(f(P,k)\) 表示满足 \(1 \le i <n\)\(p_i+k=p_{i+1}\)\(i\) 的个数。

算法 tag

构造。

数据规模与约定

\(1 \le n,k \le 10^6\)

题解

核心思路

观察题目可以发现,最优的策略是将 \(1\)\(n\) 的数按\(k\) 的余数分组。具体来说,对于每个余数 \(r\),组 \(r\) 包含的数为 \(r,r+k,r+2k,\cdots\),直到超过 \(n\) 为止。

例如,当 \(k=3,n=7\) 时,分组结果为:

  • \(1,4,7\) 满足条件
  • \(2,5\) 满足条件
  • \(3,6\) 满足条件

注意:每个组内的元素必须从小到大,这样才能满足相邻两个元素的差为 \(k\) 的条件,而且最大化答案。

正确性验证

  • 每个组内的元素差为 \(k\),一个大小为 \(s\) 的组能贡献 \(s-1\) 个满足条件的答案。
  • 总满足条件的答案为所有组的 \((s_i-1)\) 之和,即 \(\sum (s_i-1)=n-m\)\(m\) 为非空组数量),这是理论最大值。

CODE

#include <bits/stdc++.h>
using namespace std;
/*====================*/
using ll=long long;
/*====================*/
#define endl '\n'
/*====================*/
void Solve()
{int n,k;cin>>n>>k;for(int r=1;r<=k;r++) {for(int x=r;x<=n;x+=k) {cout<<x<<" ";}}cout<<endl; 
}
/*====================*/
int main()
{ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr);int T=1;//cin>>T;while(T--)Solve();return 0;
}

注:本文已被 luogu 审核通过至 P14127 题解区

http://www.hskmm.com/?act=detail&tid=26542

相关文章:

  • 题解:[P11184 带余除法]
  • 10 8
  • 2025双氧水厂家权威推荐榜:优质生产与稳定供应实力之选
  • 英国AI数据中心发展规划:技术挑战与产业反馈
  • 2025 年工业风机厂家最新推荐排行榜:涵盖离心高温防腐耐磨防爆等类型设备实力厂商精选高温/防腐/耐磨/防爆/除尘/不锈钢/锅炉风机厂家推荐
  • 2025 年拉力试验机厂家最新推荐榜单:聚焦专精特新企业技术实力与口碑,助力钢铁、线缆、轨道交通等行业精准选购
  • 2025 年最新推荐!种植牙医院权威榜单:聚焦连锁品牌与万级手术室,助您精准选靠谱口腔机构西宁种植牙口腔医院/西宁种植牙齿美容/西宁种植牙美容医院推荐
  • 高考数学易错考点01 | 临阵磨枪 - 教程
  • 2025 年西宁口腔医院最新推荐排行榜:实力解析与全周期口腔服务指南西宁口腔医院/西宁口腔美容/西宁口腔整形/西宁口腔正畸/西宁口腔修复推荐
  • 2025 年试验机厂家最新推荐榜单:专精特新企业深度解析,含疲劳 / 压力 / 液压万能等设备优质厂家水泥压力/压剪/锚链拉伸整形机/链条拉伸整形机厂家推荐
  • 2025 年最新推荐西安路灯厂家排行榜:市政 / LED / 智慧 / 太阳能 / 农村路灯优质企业全景指南
  • 2025 最新红绿灯厂家推荐排行榜:实力厂家技术与口碑深度解析,交通信号设备优选指南交通信号/路口红绿灯厂家推荐
  • 2025 土工材料厂家最新推荐榜:中铁合作厂商领衔,技术 / 案例双维度厂家深度甄选指南土工布/土工膜/土工格栅/复土工合膜厂家推荐
  • 2025 年帐篷源头厂家最新推荐排行榜:涵盖应急救灾 / 户外充气 / 露营充气 / 野营等品类,精选实力企业助采购
  • Claude Code完整安装部署指南:支持Windows/Linux/macOS三平台详细教程
  • 2025 杀虫公司最新推荐榜:权威筛选公司,靶向消杀与长效质保选购全指南
  • 2025 年电缆桥架生产厂家最新推荐榜单:聚焦北方 / 河北区域及多类型桥架,精选优质品牌深度解析瓦楞/防火/模压/镀锌桥架厂家推荐
  • rtthread学习笔记系列 -- 13 线程
  • 2025 年淋膜机厂家最新推荐排行榜:覆盖纸张 / 无纺布 / 高速 / 全自动等多类型设备,精选优质企业助力精准选购
  • 2021年度十大前沿科技研究盘点
  • 2025 商事律师咨询最新推荐榜:权威甄选专业法律服务品牌武汉公司法商事/武汉股东纠纷股权/武汉商事争议解决/武汉公司法股权律师推荐
  • 2025 最新推荐:全国开锁公司口碑排行榜权威甄选,含智能锁专项服务与紧急上门品牌详解全国/汽车保险柜/汽车锁/保险柜/智能/快速上门开锁公司推荐
  • CSP - J 讲义内容与CSP - S 讲义内容对比
  • 云安全挑战与AI时代防护策略
  • python“锈化”库替代,性能更快的库
  • 大语言模型时代计算语言学新进展
  • 用新媒体给产业园招商 - 智慧园区
  • 30年后摘得诺奖,一个叛逆“东亚小孩”的胜利
  • 2025年诺贝尔物理学奖揭晓,其中两位得主曾获“墨子量子奖”
  • 诺贝尔奖各种统计数据