首页 > 代码库 > HDU 5875 Function -2016 ICPC 大连赛区网络赛

HDU 5875 Function -2016 ICPC 大连赛区网络赛

题目链接

技术分享

网络赛的水实在太深,这场居然没出线zzz,差了一点点,看到这道题的的时候就剩半个小时了。上面是官方的题意题解,打完了才知道暴力就可以过,暴力我们当时是想出来了的,如果稍稍再优化一下估计就过了zzz。去年有一场现场赛也是n=1000,n^3过了,看来关键时刻实在做不出来就得大胆暴力啊。

 

#include <bits/stdc++.h>using namespace std;typedef long long ll;const int maxn=1e5+5;int a[maxn],nex[maxn];int main(){    int t;    scanf("%d",&t);    while(t--)    {        int n;        scanf("%d",&n);        for(int i=1; i<=n; i++)            scanf("%d",&a[i]);        for(int i=1; i<=n; i++)        {            nex[i]=-1;            for(int j=i+1; j<=n; j++)                if(a[j]<=a[i])                {                    nex[i]=j;                    break;                }        }        int q;        scanf("%d",&q);        while(q--)        {            int l,r;            scanf("%d%d",&l,&r);            int ans=a[l];            for(int i=nex[l]; i<=r; i=nex[i])            {                if(i==-1)break;                ans%=a[i];            }            printf("%d\n",ans);        }    }    return 0;}

 

HDU 5875 Function -2016 ICPC 大连赛区网络赛