A.Wizard of Orz
題意：給你個數n，輸出n位，求操作一次后的所能得到的最大值，
操作是選擇一個位置i，然后與其相鄰的位置會和他相差1. 以此類推，
思路：盡量使得首位為9，所以選擇第二位為8，則是最優的，輸出9890123456789…
#include<bits/stdc++.h>
using namespace std;
int main()
{
string s1="0123456789";
int i,j,n,t;
cin>>t;
while(t--){
cin>>n;
if(n>=3){
cout<<"989";
n-=3;
}
else {
if(n==1){
cout<<9<<endl;
continue;
}
else if(n==2) {
cout<<98<<endl;
continue;
}
else if(n==3){
cout<<989<<endl;
continue;
}
n-=3;
}
for(i=0;i<n;i++){
cout<<s1[i%10];
}
cout<<endl;
}
}
B. Hills And Valleys
題意：能更改一個位置的數，求更改完之后山峰和山谷的和最小
思路：因為更改一個數只會影響到相鄰的，并且最優的情況是將那個數更改為和左邊相等或者和右邊相等兩種方案，所以列舉一下所有的下標，每個下標可以有兩種可能的更改，再與原方案做對比，
#include<bits/stdc++.h>
using namespace std;
const int maxn=3e5+100;
int a[maxn];
int judge(int i,int n){
if(i+1==n||i==0){
return 0;
}
if((a[i]>a[i-1]&&a[i]>a[i+1])||(a[i]<a[i+1]&&a[i]<a[i-1])){
return 1;
}
else
return 0;
}
int main()
{
int n,i,j,t;
cin>>t;
while(t--){
cin>>n;
for(i=0;i<n;i++){
cin>>a[i];
}
int ans=0;
for(i=1;i<n-1;i++){
if((a[i]>a[i-1]&&a[i]>a[i+1])||(a[i]<a[i+1]&&a[i]<a[i-1])){
ans++;
}
}
int cnt=0,ans1=0;
for(i=1;i<n-1;i++){
int m1=a[i-1],m2=a[i],m3=a[i+1];
int a1=judge(i,n),b1=judge(i-1,n),c1=judge(i+1,n);
int sum1=a1+b1+c1;
a[i]=m1;
cnt=(judge(i,n)+judge(i-1,n)+judge(i+1,n));
ans1=max(sum1-cnt,ans1);
cnt=0;
a[i]=m3;
cnt=(judge(i,n)+judge(i-1,n)+judge(i+1,n));
ans1=max(sum1-cnt,ans1);
cnt=0;
a[i]=m2;
}
cout<<ans-ans1<<endl;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/246884.html
標籤：其他
上一篇：【Codeforces 1467D】 Sum of Paths | dp、思維
下一篇：策略模式