Codeforces 209 div2 D. Pair of Numbers

题目：D. Pair of Numbers

思路：预处理每个数最右边和最左边能够整除它的下标，然后暴力，记得去重，不然会Wa

 tag ：dp + 预处理

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>
#include <map>
using namespace std;
#define maxn 300010
int l[maxn],r[maxn],num[maxn];
vector<int>ans;
int main()
{
    ans.clear();
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&num[i]);
        l[i]=r[i]=i;
    }
    int index;
    for(int i=2;i<=n;i++)
    {
        index=i-1;
        while(num[index]%num[i]==0 && index>=1)
            index=l[index]-1;
        l[i]=l[index+1];
    }
    for(int i=n-1;i>=1;i--)
    {
        index=i+1;
        while(num[index]%num[i]==0 && index<=n)
            index=r[index]+1;
        r[i]=r[index-1];
    }
    int mx=-1;
    for(int i=1;i<=n;i++)
    {
        //printf("%d %d %dn",l[i],num[i],r[i]);
        //mx=max(mx,r[i]-l[i]);
        if(mx<r[i]-l[i])
        {
            ans.clear();
            mx=r[i]-l[i];
            ans.push_back(l[i]);
        }
        else if(mx==r[i]-l[i])
        {
            ans.push_back(l[i]);
        }
    }
    ans.erase(unique(ans.begin(),ans.end()),ans.end());
    printf("%d %dn",ans.size(),mx);
    sort(ans.begin(),ans.end());
    for(int i=0;i<ans.size();i++)
    {
        printf("%d",ans[i]);
        if(i+1==ans.size())
            printf("n");
        else
            printf(" ");
    }
    return 0;
}

最后

以上就是天真仙人掌为你收集整理的Codeforces 209 div2 D. Pair of Numbers的全部内容，希望文章能够帮你解决Codeforces 209 div2 D. Pair of Numbers所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。