P9345 夕阳西下几时回题目背景随着夕阳从山间落下最后一丝余晖逐渐暗淡美丽的晚霞终究还是化作一片黑夜。在这番景象中一阵又一阵的乡愁涌上心头远离家乡的游子就算不是病死他乡又何时能回还题目描述夕阳可以被视作由nnn种不同颜色组成的一副图其中第iii种的颜色为aia_iai满足aaa是长度为nnn的排列。定义一个排列的乡愁度为对于所有1≤i≤n1\le i\le n1≤i≤n记bigcd(ai,ai1)b_i\gcd(a_i,a_{i1})bigcd(ai,ai1)。特别地我们认为an1a1a_{n1}a_1an1a1。排列aaa的乡愁度为序列bbb中不同元素的个数。求是否有一个长度为nnn乡愁度为kkk的排列ppp。若有解请输出任意一个排列。输入格式本题有多组测试数据。第一行一个正整数TTT表示测试数据组数。对于每组测试数据一行两个整数n,kn,kn,k。输出格式对于每组测试数据如果不存在这样的排列输出一行一个字符串No否则输出一行一个字符串Yes然后输出一行nnn个正整数p1,p2,…,pnp_1,p_2,\dots,p_np1,p2,…,pn表示你找到的排列。校验器忽略字符串大小写例如YESyEsyes都会被视作答案存在。输入输出样例 #1输入 #13 7 1 6 5 11 4输出 #1Yes 1 2 3 4 5 6 7 No Yes 1 11 9 3 6 7 8 2 5 10 4说明/提示【提示】一个长度为nnn的排列是一个满足111到nnn中的所有正整数恰好出现111次的数组。例如[3,1,2][3,1,2][3,1,2]是一个长度为333的排列而[5,5,1,2,3][5,5,1,2,3][5,5,1,2,3]不是一个排列。【样例 1 解释】对于第一组数据b[1,1,1,1,1,1,1]b[1,1,1,1,1,1,1]b[1,1,1,1,1,1,1]故ppp的乡愁度为111。对于第二组数据可以证明不存在这样的序列。对于第三组数据b[1,1,3,3,1,1,2,1,5,2,1]b[1,1,3,3,1,1,2,1,5,2,1]b[1,1,3,3,1,1,2,1,5,2,1]包含444个不同的元素 —1,2,31,2,31,2,3和555故ppp的乡愁度为444。【数据规模与约定】本题采用捆绑测试。Subtask 14 pointsn≤9n\le 9n≤9∑n≤100\sum n\le 100∑n≤100。Subtask 25 pointsk1k1k1。Subtask 313 points∑n≤200\sum n\le 200∑n≤200。Subtask 430 points对于所有测试数据保证有解。Subtask 548 points无特殊限制。对于100%100\%100%的数据1≤T≤1051\le T\le 10^51≤T≤1053≤n≤3×1053\le n\le 3\times 10^53≤n≤3×1051≤k≤n1\le k\le n1≤k≤n∑n≤6×105\sum n \le 6\times 10^5∑n≤6×105。C实现#includebits/stdc.husingnamespacestd;inta[300010];intmp[300010];intmain(){intt;scanf(%d,t);while(t--){intn,k;scanf(%d%d,n,k);for(inti1;in;i){mp[i]0;}if(k(n/2)){printf(No\n);continue;}printf(Yes\n);a[1]1;intcnt1;for(inti2;in;i){intsumi;if(mp[sum]0){a[cnt]sum;mp[sum]1;sum*2;while(sumk*2){a[cnt]sum;mp[sum]1;sum*2;}}}for(inti1;icnt;i){printf(%d ,a[i]);}printf(\n);}return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容
打卡信奥刷题（3331）用C++实现信奥题 P9345 夕阳西下几时回
P9345 夕阳西下几时回题目背景随着夕阳从山间落下最后一丝余晖逐渐暗淡美丽的晚霞终究还是化作一片黑夜。在这番景象中一阵又一阵的乡愁涌上心头远离家乡的游子就算不是病死他乡又何时能回还题目描述夕阳可以被视作由nnn种不同颜色组成的一副图其中第iii种的颜色为aia_iai满足aaa是长度为nnn的排列。定义一个排列的乡愁度为对于所有1≤i≤n1\le i\le n1≤i≤n记bigcd(ai,ai1)b_i\gcd(a_i,a_{i1})bigcd(ai,ai1)。特别地我们认为an1a1a_{n1}a_1an1a1。排列aaa的乡愁度为序列bbb中不同元素的个数。求是否有一个长度为nnn乡愁度为kkk的排列ppp。若有解请输出任意一个排列。输入格式本题有多组测试数据。第一行一个正整数TTT表示测试数据组数。对于每组测试数据一行两个整数n,kn,kn,k。输出格式对于每组测试数据如果不存在这样的排列输出一行一个字符串No否则输出一行一个字符串Yes然后输出一行nnn个正整数p1,p2,…,pnp_1,p_2,\dots,p_np1,p2,…,pn表示你找到的排列。校验器忽略字符串大小写例如YESyEsyes都会被视作答案存在。输入输出样例 #1输入 #13 7 1 6 5 11 4输出 #1Yes 1 2 3 4 5 6 7 No Yes 1 11 9 3 6 7 8 2 5 10 4说明/提示【提示】一个长度为nnn的排列是一个满足111到nnn中的所有正整数恰好出现111次的数组。例如[3,1,2][3,1,2][3,1,2]是一个长度为333的排列而[5,5,1,2,3][5,5,1,2,3][5,5,1,2,3]不是一个排列。【样例 1 解释】对于第一组数据b[1,1,1,1,1,1,1]b[1,1,1,1,1,1,1]b[1,1,1,1,1,1,1]故ppp的乡愁度为111。对于第二组数据可以证明不存在这样的序列。对于第三组数据b[1,1,3,3,1,1,2,1,5,2,1]b[1,1,3,3,1,1,2,1,5,2,1]b[1,1,3,3,1,1,2,1,5,2,1]包含444个不同的元素 —1,2,31,2,31,2,3和555故ppp的乡愁度为444。【数据规模与约定】本题采用捆绑测试。Subtask 14 pointsn≤9n\le 9n≤9∑n≤100\sum n\le 100∑n≤100。Subtask 25 pointsk1k1k1。Subtask 313 points∑n≤200\sum n\le 200∑n≤200。Subtask 430 points对于所有测试数据保证有解。Subtask 548 points无特殊限制。对于100%100\%100%的数据1≤T≤1051\le T\le 10^51≤T≤1053≤n≤3×1053\le n\le 3\times 10^53≤n≤3×1051≤k≤n1\le k\le n1≤k≤n∑n≤6×105\sum n \le 6\times 10^5∑n≤6×105。C实现#includebits/stdc.husingnamespacestd;inta[300010];intmp[300010];intmain(){intt;scanf(%d,t);while(t--){intn,k;scanf(%d%d,n,k);for(inti1;in;i){mp[i]0;}if(k(n/2)){printf(No\n);continue;}printf(Yes\n);a[1]1;intcnt1;for(inti2;in;i){intsumi;if(mp[sum]0){a[cnt]sum;mp[sum]1;sum*2;while(sumk*2){a[cnt]sum;mp[sum]1;sum*2;}}}for(inti1;icnt;i){printf(%d ,a[i]);}printf(\n);}return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容
