[CSP-S模拟测试]:序列(构造)
题目描述
给定$N,A,B$,构造一个长度为$N$的排列,使得:
$\bullet$排列长度为$N$;
$\bullet$最长上升子序列长度为$A$;
$\bullet$最长下降子序列长度为$B$。
我们有$SPJ$,有解任意给出一组,否则说明无解。
输入格式
第一行一个整数$T(1\leqslant T\leqslant 10)$,表示数据组数。
接下来$T$行,每行三个正整数$N$、$A$、$B$。
输出格式
对每组数据:
如果有解,输出两行,第一行一个字符串$Yes$,接下来一行$N$个整数,表示排列。
否则,输出一行一个字符串$No$。
样例
样例输入:
3
4 2 2
4 4 1
4 3 3
样例输出:
Yes
3 4 1 2
Yes
1 2 3 4
No
数据范围与提示
对于全部的测试数据,保证$T\leqslant 10,N\leqslant 10^5,\sum N\leqslant 2\times 10^5
$\bullet$子任务$1$($20$分):$N\leqslant 5$。
$\bullet$子任务$2$($30$分):每组数据均满足$N=A\times B$。
$\bullet$子任务$3$($20$分):$B\leqslant 2$。
$\bullet$子任务$4$($30$分):无特殊限制。
题解
一看就是一个构造题,先从$N=A\times B$入手,我们可以将序列分成$B$块,让这$B$块内部构成长度为$A$的上升序列,$B$块相互之间呈下降序列即可。
举个栗子,当$N=10,A=2,B=5$,我们可以将其构造成:$(9,10),(7,8),(5,6),(3,4),(1,2)$;可以发现,每一个小括号内呈上升,而小括号之间是下降序列。
如果不满足$N=A\times B$,我们还可以接着用这样的思想。
最后来考虑$No$的情况,如果$A+B<N-1$,那么显然不行;如果$A\times B<N$也是不行的。
于是这到题就被解决了。
时间复杂度:$\Theta(N)$。
期望得分:$100$分。
实际得分:$100$分。
代码时刻
#include<bits/stdc++.h>
using namespace std;
int main()
{
int T;scanf("%d",&T);
while(T--)
{
int N,A,B;scanf("%d%d%d",&N,&A,&B);
if(N<A+B-1||N>1LL*A*B){puts("No");continue;}
int len=N-B;puts("Yes");
for(int i=1;i<=B;i++)
{
int now=1;
while(now<A&&len){len--;now++;}
for(int j=N-now+1;j<=N;j++)printf("%d ",j);
N-=now;
}puts("");
}
return 0;
}
rp++
最新文章
- 透过浏览器看HTTP缓存
- 成为JavaGC专家(1)—深入浅出Java垃圾回收机制
- Anroid Studio入门
- 【原创】express3.4.8源码解析之路由中间件
- linux tricks 之数据对齐。
- Spring学习总结(0)——Spring详解
- 如何使用Keil仿真环境查看CPU类型字长?【worldsing笔记】
- 从零开始学习jQuery (十) jQueryUI常用功能实战
- Windows下动态库的隐式调用
- 学习AJAX(一)
- c语言 列出系统进程
- EasyUI - ValidateBox 验证组件
- repeater操作
- Linux FTP 服务器配置简单说明
- css学习_css布局案例
- ES5与ES6对比
- CentOS7离线安装Ambari与HDP
- PHP:第一章——php中的输出函数
- 【VUE】Mac下vue 开发环境搭建,以及目录结构
- 【IT公司笔试面试】75道逻辑推理题及答案
热门文章
- [JS] 鼠标点击文本框清空默认值,离开文本框恢复默认值
- Python 矩阵(线性代数)
- CSU-1120 病毒(最长递增公共子序列)
- Find The Multiple (水题)
- Chrome开发者工具详解(三)之浏览器调试完后如何清除所有的断点
- 2019 上海市大学生网络安全大赛 RE部分WP
- Python webdriver调用Chrome报错
- mysql随机取一条记录
- Linux服务器安装系统之1-LSI阵列卡Raid10配置方法
- do{}while(0);里面有continue