5.18-5.20 VJ training

A题

一开始想用暴力循环，但是发现，我找的思路不对。。。然后就在纸上写了2，4，6的结果，发现好像是个递推，然后就试了试（因为8的时候没手算出来，所以死马当活马医），用递推打了个表，然后直接输出对应的元素就行。

#include<bits/stdc++.h>
using namespace std;
int a[31];
int main()
{
    int i;
    a[1] = 2;
    for(i = 2;i<=15;i++)
    {
        a[i] = 2*a[i-1]+2;
    }
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        cout<<a[n/2]<<endl;
    }
}

B题

这个题说实话，，，没有思路，然后问了问大哥，给了点提示之后，发现自己太过于纠结样例了，导致看不懂，这个题的话首先要判断数组的元素种类是否超过他给的周期，如果超过，直接输出-1；如果没超过就去重然后输出，如果不够一个周期然后补1，最后要注意输出的时候直接按照最大周期输出就行。

#include<bits/stdc++.h>
using namespace std;
int main()
{
    set<int > s;
    int n;
    cin>>n;
    while(n--)
    {
        s.clear();
        int l,p;
        set<int >::iterator it;
        cin>>l>>p;
        int t;
        int i;
        for(i = 0;i<l;i++)
        {
            cin>>t;
            s.insert(t);
        }
        if(s.size()>p)
            cout<<-1<<endl;
        else if(s.size()==p)
        {cout<<p*l<<endl;
            for(int j = 0;j < l;j++){
            for(it = s.begin();it!=s.end();it++)
            {
                cout<<*it<<" ";
            }
            }
            cout<<endl;
        }
        else if(s.size()<p)
        {
            cout<<p*l<<endl;
            for(int j = 0;j<l;j++){
            for(it = s.begin();it!=s.end();it++)
            {
                cout<<*it<<" ";
            }
            for(int i = 0;i<(p-s.size());i++)
                cout<<"1 ";
            }
            cout<<endl;
        }
    }
}

C题

直接暴力模拟，关键点是因为a，b的大小不一定，导致同样的方法价格可能不同，所以要比较两种走路的方法花费的大小，然后取最小就行了。

ps：两种方法分别是：

（1）先将两个坐标中小的用方法一减到零，然后用方法二将另一个坐标变成0；

（2）先将两个坐标中小的用方法一变成另一个坐标，然后用方法二将两个坐标同时变为0。

#include<iostream>
#include<cmath>
using namespace std;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        long long x,y,a,b;
        cin>>x>>y>>a>>b;
        long long sum,sum2;
        sum = b*min(x,y)+abs(x-y)*a;
        sum2 = a*x+a*y;
        cout<<min(sum,sum2)<<endl;
    }
}

D题

如果字符串中有0、1两种元素，那就直接输出2倍原数组长度的“01”；如果只有一种元素，直接原地输出。

#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
using namespace std;
int main()
{
    char s[10000];
    int t;
    cin>>t;
    while(t--)
    {
        scanf("%s",&s);
        int len = strlen(s);
        int i;
        int flag=1;
        for(i = 0;i < len-1;i++)
        {
            if(s[i]!=s[i+1])
            {
                flag = 0;
                break;
            }
        }
        if(flag==1)
            cout<<s<<endl;
        else

        {
            for(i = 0;i < len;i++)
                {
                    cout<<"10";
                    if(i==len-1)
                        cout<<endl;
                }
        }
    }
}

E题

就是判断两个区间是否有交集，上网百度了一下判断两个集合是否有交集的方法，get到了新思路

#include<iostream>
using namespace std;
int main()
{
    int n,t;
    cin>>t;
    while(t--)
    {
        cin>>n;
        int a,b,c,d;
        cin>>a>>b>>c>>d;
        int sa,ea,sb,eb;
        sa = n*(a-b);
        ea = n*(a+b);
        sb = c-d;
        eb = c+d;
        if(max(sa,sb)<=min(ea,eb))
            cout<<"Yes"<<endl;
        else cout<<"No"<<endl;

    }
}

F题

一开始想用滑动窗口，但是发现他的长度不确定，循环感觉会tle，求助了一下大佬，学了一下前缀和，然后，啊真香，就是注意边界，绕乱了好几次，awsl

#include<bits/stdc++.h>
using namespace std;
int a[200001] ;
int c[200001];
int main()
{
    int t;cin>>t;
    while(t--)
    {
        int cnt = 0;
        int k,n;
        cin>>n>>k;
        int i;
        for(i = 1;i<=n;i++)
        cin>>a[i];
        for(int i = 1;i<=n;i++)
        {
            if(a[i-1]<a[i]&&a[i]>a[i+1])
            {
                cnt++;
            }
            c[i] = cnt;
        }
        int maxm = 0,p = 1;
        for(i = 1;i<=n-k+1;i++)
        {
            if(maxm<c[i+k-2]-c[i])
            {
                maxm = c[i+k-2]-c[i];
                p = i;
            }
        }
        cout<<maxm+1<<" "<<p<<endl;
    }
}