Codeforces Round#649(Div.2)

A. XXXXX

题意

求不被x整除的最长连续子串的长度

题解

前缀和暴力

#include <bits/stdc++.h>
using namespace  std;
const int maxn=1e5+10;
typedef long long ll;
vector<int >v[10010];
int solve(int k)
{
    int now=1;
    if(v[k].size()==v[k][v[k].size()-1])return -1;
    for (int i=0;i<v[k].size();i++)
    {
        if(v[k][i]!=now)
            return v[k][v[k].size()-1]-now;
        now++;
    }
}
int main()
{
    int t,i,n,x,a[maxn],qz[maxn];
    cin >> t;
    while(t--)
    {
        cin >> n >> x;
        qz[0]=0;
        for(i=0;i<=10000;i++)
            v[i].clear();
        int res=-1;
        for(i=1;i<=n;i++)
        {
            scanf("%d",&a[i]),qz[i]=qz[i-1]+a[i],v[qz[i]%x].push_back(i);
            if(qz[i]%x!=0)
                res=i;
        }
        for(i=0;i<x;i++)
        {
            if(v[i].size()>0)
            {
                int k=solve(i);
                if(k!=-1)
                    res=max(res,k);
            }
        }
        cout << res << endl;
    }
    return 0;
}

B. Most socially-distanced subsequence

题意

给你一个序列p，要求找出它相邻元素绝对值之和最大前提下元素个数最少的子序列

题解

记录极大值点与极小值点即可

#include <bits/stdc++.h>
using namespace  std;
const int maxn=1e5+10;
typedef long long ll;
int main()
{
    int i,t,j,n,a[maxn];
    vector<int >v;
    cin >> t;
    while(t--)
    {
        v.clear();
        scanf("%d",&n);
        for(i=1;i<=n;i++)
            scanf("%d",&a[i]);
        v.push_back(a[1]);
        for(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])
                v.push_back(a[i]);
        v.push_back(a[n]);
        printf("%d\n",v.size());
        for(i=0;i<v.size();i++)
            printf("%d ",v[i]);
        printf("\n");
    }
    return 0;
}

C. Ehab and Prefix MEXs

题意

给出一个数组 a ，要求构造一个数组 b ，使得 a[ i ] = MEX{ b[ 1 ] , b[ 2 ] , ... b[ i - 1 ] , b[ i ] }，a[ i ] 满足小于等于 i

题解

#include <bits/stdc++.h>
using namespace  std;
const int maxn=1e5+10;
typedef long long ll;
int vis[maxn];
int main()
{
    int i,n,a[maxn],b[maxn];
    memset(vis,0,sizeof(vis));
    memset(b,-1,sizeof(b));
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%d",&a[i]),vis[a[i]]=1;
    a[0]=-1;
    for(i=1;i<=n;i++)
        if(a[i]!=a[i-1])
            b[i]=a[i-1];
     int cnt=0;
     for(i=1;i<=n;i++)
     {
         if(b[i]!=-1)
             continue;
         while(vis[cnt])
             cnt++;
         b[i]=cnt++;
     }
     for(i=1;i<=n;i++)
         printf("%d ",b[i]);
    return 0;
}