首页 > 其他分享 >CF1712B Woeful Permutation 题解

CF1712B Woeful Permutation 题解

时间:2022-08-15 17:33:14浏览次数:78  
标签:putchar int 题解 scanf CF1712B Woeful operatorname

题目传送门

题目简介

  • 给定一个正整数 \(n\),构造一个数列 \(p\),使 \(1\) 到 \(n\) 中每一个数都出现且只出现 \(1\) 次。

  • 求最大的 \(\sum\limits_{i=1}^n\operatorname{lcm}(i, p_i)\),并输出取得最大值时的数列。

思路

基础知识:\(\operatorname{lcm}(a,b)=\dfrac{a\times b}{\operatorname{gcd}(a,b)}\)。

\(\operatorname{gcd}(a,a+1)=1\)。

根据上面两个知识,我们可以得到相邻两项的 LCM 即为他们的乘积,根据贪心的思想,我们从后往前遍历,将相邻两项的位置互换,这样每次都会使相对较大的两个数相乘,使最终的结果最大,其中如果 \(n\) 是奇数,\(1\) 的位置不变即可。

代码

#include <bits/stdc++.h>
using namespace std;
int t,n;
int main() {
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		if(n&1){
			putchar('1');
			putchar(' ');
			for(int i=2;i<=n;i+=2){
				printf("%d %d ",i+1,i);
			}
			putchar('\n');
		}
		else{
			for(int i=1;i<=n;i+=2){
				printf("%d %d ",i+1,i);
			}
			putchar('\n');
		}
	}
	return 0;
} 

标签:putchar,int,题解,scanf,CF1712B,Woeful,operatorname
From: https://www.cnblogs.com/Dregen-Yor/p/16589026.html

相关文章

  • Codeforces Round #813 (Div. 2) 题解A~E2
    https://codeforces.com/contest/1712估计也就我赛中才D都写不出来了A题题意:给你一个数组和一个正整数\(k\),每次可以选择数组的任意两个数交换,问你最少交换多少次能使......
  • CF1714C 题解
    题目大意找到最小的数字,使该数字每一位上的数字的和等于给定的数字\(s\),且其中的所有数字都不同,即所有数字都是唯一的。解法这题的数据很水,暴力就能过,从小到大枚举每......
  • ubuntu dpkg问题解决
    问题今天玩ubuntu发现以下报错:dpkgwasinterrupted,youmustmanuallyrunsudodpkg–configure-atocorrecttheproblem 解决sudorm/var/lib/apt/lists/l......
  • LGP8474题解
    很萌萌的数数题。考虑设\(dp[n]\)表示\(n\)的答案。考虑对于一个长度为\(n\)的排列,令排列的所有元素\(+1\),然后塞一个\(1\)进去。容易发现,逆序对增加的数量和......
  • Gym102798 CCPC2020威海E加强版 题解
    原题link把\(m\)和\(a_i\)的上界改成\(200\),其他不变.基本思路:枚举\(S\),求出\(p(S)\)表示集合\(S\)中的怪兽被打死的概率,答案就是\(\sum_{S}|S|p(S)\).而这......
  • AtCoder Beginner Contest 264部分题解(a~d)
    A题题目大意:打印“atcoder"中从第l个到第r个字母参考代码:#include<bits/stdc++.h>usingnamespacestd;#defineintlonglong#defineIOSios_base::sync_with_std......
  • 【问题解决】解决使用aliyuncdn加速的域名证书不同步问题
    今天登录上博客发现好家伙资源链全挂了,进去一看发现是证书到期了,但是我回服务器查看证书发现证书已经更新而且是有效状态,清缓存一类的都尝试过了,依旧不行,然后网上找到了一......
  • AcWing周赛62-64 中比较有意思的小题题解
    AcWing周赛62-64(选讲)感觉比较思维4502.集合操作https://www.acwing.com/problem/content/4505/根据题意,肯定要使得所取的最大值最大,平均值最小。又因为每次放进来的的......
  • T265119 拯救公主--题解
    题目描述公主索菲亚被关在一个有大小一样的方格构成的四四方方的迷宫里面,索菲亚就站在其中一个方格子上,拯救方案是这样的:要用一些地砖把公主所在的方格子之外的格子都铺上......
  • CF1712题解(E,F)
    E题意是让你求满足\(lcm(i,j,k)\geqi+j+k\)的三元组个数。我们通常都有一个直观感觉,lcm应该是各数之积级别的,换句话说,不满足\(lcm(i,j,k)\geqi+j+k\)的三元组个数......