网站备案是免费的吗,浙江省建设厅官网,淮北做网站的公司,舆情网站设计题目链接#xff1b;
D-构造mex_牛客周赛 Round 59 (nowcoder.com)
题目描述#xff1a; 输出和输出描述#xff1a; 输入样例#xff1a; 3 6 3 3 7 4 3 6 6 0 输出样例#xff1a; NO YES 4 0 1 2 YES 1 1 1 1 1 1 分析#xff1a;
数学思维题#xff0c;赛后看了一…题目链接
D-构造mex_牛客周赛 Round 59 (nowcoder.com)
题目描述 输出和输出描述 输入样例 3 6 3 3 7 4 3 6 6 0 输出样例 NO YES 4 0 1 2 YES 1 1 1 1 1 1 分析
数学思维题赛后看了一下比率182/3788。
对n和k的大小进行分类讨论:
n k
nk的情况一定输出是0因为极端的情况下n最多能达到的是0 1 2 ... n - 1到达不了k - 1那么第一个没有的整数是: n就不再是k了。
n k
这个就是 0 1 2 ... n - 1又因为n k, 所以第一个没有的是整数就是n,也即是k只需要判断前n项和是不是等于s的也即是 s (n - 1) * n / 2 ? YES : NO;
例子 s 6, n 4, k 4 输出的是:
0 1 2 3
n k
对k的特殊情况进行讨论
k 0
k等于0的情况下能组成的最小值是 1 * n如果s小于最小值的话那就是不可能的输出NO,否则的话可以先输出n-1个1然后最后在输出最后一个 s - (n - 1)即可。
例子 s 11, n 5, k 0; 那么构造的是: 0 0 0 0 11
k 1
k等于1的情况下能组成的最小值是0(n个0)。
但是要注意s等于1就要输出NO了因为我输出n-1个0最后在输出一个1但是这个1和k一样因此我想把这个1换成2或者0但是发现换为0的那么就需要一个0去加1换为2的话就需要一个0减去1那么就变味负的了因此输出NO
例子: s 1, n 4, k 1 输出的是: NO
s不等于1的时候可以先输出n-1个0然后在输出最后一个 s - (n - 1) * 0。
例子: s 3, n 4, k 1 输出的是: 0 0 0 3
k 其他
这个是最复杂的情况了。k等于其他(2, 3, 4, ....)的情况下的最小值是: (0 1 2 .....k - 1 0 0 0 0 0 0 )也即是 (k - 1) * k / 2 (n - k) * 0要是当前的s小于这个最小值的话直接输出NO。
先去分配0 到 (k - 1)这n个数那么还剩下和为s- k * (k - 1) / 2, n - k个数。
贪心的做法先分配 n - k - 1个0在把最后一个数的值为s- k * (k - 1) / 2。但是需要注意的是 这个值是不是等于k的。
要是等于k的话就出现了k我就会让这个最后一个数减去1然后让1到k-1后面的0 0 0 0 中任意一个0改为1即可但是需要注意的是1到k-1的后面有没有0没有的话就不可以。
例子 s 9, n 4, k 4 输出的是
按照之前的思路输出的是
0 1 2 3 4,但是发现出现了4因此我就会让4减去1然后让蓝色部分的一个0加上1但是发现蓝色部分没有0的出现因此正确的输出是NO,那可不可以让红色部分的某一个加1当然不可以红色部分某一个加1了第一个没有的整数就不再是k了。
例子 s 9, n 10, k 4 刚开始构造的是:
0 1 2 3 0 0 0 0 0 4
出现了k因此我会让蓝色部分的第一个0加1让最后这个数-1即可也就是变为了:
0 1 2 3 1 0 0 0 0 3
要是不等于k的话无论是大于还是小于直接输出即可。
例子 s 8, n 10, k 4 输出的是:
0 1 2 3 0 0 0 0 0 2
代码
#includebits/stdc.h
#define int long long
#define endl \nusing namespace std;signed main() {int t;cin t;while(t -- ) {int s, n, k;cin s n k;if(n k ){if(s ! (n - 1) * n / 2) {cout NO endl;} else {cout YES endl;for(int i 0; i n; i ) {cout i ;}cout endl;}continue;}if(n k ) {cout NO endl;} else {int a[n 10];if(k 0) {if(s 1 * n) {//最小是 n * 1 cout NO endl;} else {cout YES endl;for(int i 1; i n - 1; i ) {cout 1 ;}cout s - (n - 1) endl;}} else if(k 1) {if(s 1) {cout NO endl;} else {cout YES endl;for(int i 1; i n - 1; i ) {cout 0 ;}cout s endl;}} else {
// cout sum k * (k - 1) / 2 endl;
// cout s s endl;// 最小是 k * (k - 1) / 2if(s k * (k - 1) / 2 0 * (n - k)) {cout NO endl;} else {int b[n 10];//k个了 for(int i 0; i k - 1; i ) {a[i] i;}int sum s - (k - 1) * k / 2;int gs n - k; // 剩余的个数 //cout sum sum gs gs endl;for(int i 1; i gs - 1; i ) {b[i] 0;}b[gs] sum;if(sum k) {if(gs 1) {cout NO endl;continue;}b[1] 1;b[gs] sum - 1;}cout YES endl;for(int i 0; i k - 1; i ) {cout a[i] ;}for(int i 1; i gs; i ) {cout b[i] ;}cout endl;}}}}return 0;
}运行结果
