Codeforces Round #695 (Div. 2)(AB)

A：http://codeforces.com/contest/1467/problem/A

题意：

有

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
using namespace std;
const int maxn  = 1e5+10;
typedef long long ll;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n ;
        cin>>n;
        if(n==1)
            cout<<"9"<<endl;
        else if(n==2)
            cout<<"98"<<endl;
        else if(n==3)
            cout<<"989"<<endl;
        else
        {
        //    cout<<"?";
            cout<<"989";
            int ans=0;
            for(int i=4;i<=n;i++)
            {
                cout<<ans;
                ans++;
                if(ans==10)
                    ans=0;
            }    
            cout<<endl;
        }
    }
    return 0;
    
}

B：http://codeforces.com/contest/1467/problem/B

题意：

危险值为所以谷点和尖点的数目之和。

唯一的一次操作是，将一个数字变为任意一个数字。

求操作后的最小危险值。

解析：

刚开始，以为一个危险点的修改，可以将它本身以及周围都变成安全点。其实不然。

首先，一个危险点ai，要想把它变成安全点，要么变为ai-1，要么变为ai+1

此时，ai变为安全点，但是ai-1或ai+1，可能因此变为危险点。

所以考虑每一个点的时候，要将ai分别变成ai-1和ai+1，来综合求最小值。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
using namespace std;
const int maxn  = 3e5+50;
const int inf=99999999;
typedef long long ll;
ll a[maxn],vis[maxn];
int n ;
int check(int i)
{
    if(i==1||i==n)
        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;
        return 0 ;
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        cin>>n;
        for(int i=1;i<=n;i++)
            cin>>a[i];
        int cnt = 0 ;
        for(int i=2;i<n;i++)
        {
            if((a[i]>a[i-1]&&a[i]>a[i+1])||(a[i]<a[i-1]&&a[i]<a[i+1]))
                cnt++;
        }        
        int minn = inf ; 
    //    cout<<cnt<<"--"<<endl;
        for(int i=2;i<n;i++)
        {
            int mdl = a[i-1],md=a[i],mdr=a[i+1];
            int sum = cnt;            
            int c=check(i-1)+check(i)+check(i+1);
            a[i]=mdl;
            int c2=check(i-1)+check(i)+check(i+1);
            sum=sum-(c-c2);
            minn=min(minn,sum);
            
            
            sum=cnt;
            a[i]=mdr;
            c2=check(i-1)+check(i)+check(i+1);
            sum=sum-(c-c2);
            minn=min(minn,sum);
            a[i]=md;
            
        }
        cout<<min(minn,cnt)<<endl;
    }
    return 0;    
}
//9
//1 4 1 1 4 1 4 1 4

Codeforces Round #695 (Div. 2)(AB)

推荐阅读