题目链接：Power Sequence
题意：
给你n个数vi，你可以对这个序列进行两种操作
1、可以改变其中任意个vi的位置，无成本
2、可以对vi进行加1或减1，每次操作成本为1
如果操作之后的vi（设v数组下标从1到n）满足：如果存在一个数c，使得每一个vi都满足vi==ci
你需要输出这个满足题意得vi数组构成所需的最小成本
题解：
题目要求1<=ai<1e9，那么可以说所有vi都加起来得数量级是1e9，那么也就说如果cn，那么c这个数就不可取
因为我们c可以取1，那么成本最大也是在1e9数量级
所以就暴力枚举c因子就行，这个c得范围我随便定了一个范围，具体见代码
代码：
1 #include<stdio.h> 2 #include<string.h> 3 #include<algorithm> 4 #include<iostream> 5 using namespace std; 6 typedef long long ll; 7 const int maxn=1e5+10; 8 const int INF=1e9; 9 char s[maxn]; 10 ll v[maxn]; 11 long long pf(ll a, ll b) 12 { 13 ll res = 1; 14 while (b--) 15 res *= a; 16 return res; 17 } 18 int main() 19 { 20 ll n; 21 scanf("%lld",&n); 22 v[0]=1; 23 for(ll i=1; i<=n; ++i) 24 { 25 scanf("%lld",&v[i]); 26 } 27 sort(v+1,v+n+1); 28 ll sum; 29 sum=100000000000000; 30 if (n >= 36) 31 { 32 sum = 0; 33 for (ll i = 1; i <= n; i++) 34 sum += v[i] - 1; 35 printf("%lld\n", sum); 36 return 0; 37 } 38 for (ll k = 1; k <= 100000; k++) 39 { 40 long long temp = 0, flag = 1,tmp=1; 41 for (ll i = 1; i <= n; i++) 42 { 43 if (tmp >= n * 1000000000) 44 { 45 flag = 0; 46 break; 47 } 48 temp += abs(v[i] - tmp); 49 tmp*=k; 50 } 51 if (flag) 52 sum = min(temp, sum); 53 } 54 printf("%lld\n",sum); 55 return 0; 56 }
题目链接：Multiples of Length
题意：
给你n个数vi，每次操作你可以选取一个区间[l,r]，区间长度len=r-l+1，那么你可以对这个区间内的vi加上len的倍数，这个倍数可以是负数，即-1*len
你必须要在3个操作内使得所有vi变为0，请输出这3个操作
题解：
我们设v数组下标从1到n，你可以先对区间[1,n-1]上的vi都加上(n-1)*vi，那么再使v[n]变成n*v[n]。那么最后在对区间[1,n]内的所有vi减去n*vi就行
代码：
1 #include<stdio.h> 2 #include<string.h> 3 #include<algorithm> 4 #include<iostream> 5 using namespace std; 6 typedef long long ll; 7 const int maxn=1e5+10; 8 const int INF=1e9; 9 ll v[maxn]; 10 int main() 11 { 12 ll n; 13 scanf("%lld",&n); 14 15 for(ll i=1;i<=n;++i) 16 { 17 scanf("%lld",&v[i]); 18 } 19 if(n==1) 20 { 21 printf("1 1\n"); 22 printf("%lld\n",-1*v[1]); 23 printf("1 1\n0\n"); 24 printf("1 1\n0\n"); 25 return 0; 26 } 27 printf("1 %lld\n",n-1); 28 for(ll i=1;i<n;++i) 29 { 30 if(i==n-1) 31 printf("%lld\n",(n-1)*v[i]); 32 else printf("%lld ",(n-1)*v[i]); 33 } 34 35 printf("%lld %lld\n",n,n); 36 printf("%lld\n",n*v[n]-v[n]); 37 38 printf("1 %lld\n",n); 39 for(ll i=1;i<=n;++i) 40 { 41 if(i==n) 42 printf("%lld\n",-1*n*v[i]); 43 else printf("%lld ",-1*n*v[i]); 44 } 45 return 0; 46 }
Codeforces Round #666 (Div. 2) Power Sequence、Multiples of Length 思维
原文：https://www.cnblogs.com/kongbursi-2292702937/p/13590668.html
