「BZOJ1978」[BJ2010] 取数游戏 game
Description
小 C 刚学了辗转相除法，正不亦乐乎，这小 P 又出来捣乱，给小 C 留了个 难题。 给 N 个数，用 a1,a2…an来表示。现在小 P 让小 C 依次取数，第一个数可以 随意取。假使目前取得 aj，下一个数取ak(k>j)，则ak必须满足gcd(aj,ak)≥L。 到底要取多少个数呢？自然是越多越好！ 不用多说，这不仅是给小 C 的难题，也是给你的难题。
Input
第一行包含两个数N 和 L。 接下来一行，有 N 个数用空格隔开，依次是 a1,a2…an。
Output
仅包含一行一个数，表示按上述取法，最多可以取的数的个数。
Sample Input
5 6
7 16 9 24 6
7 16 9 24 6
Sample Output
3
HINT
选取 3个数16、24、6。gcd(16,24)=8，gcd(24,6)=6。
2≤L≤ai≤1 000 000；
30% 的数据N≤1000；
100% 的数据 N≤50 000
Source
f[i]=max{f[last[x]]+1} x|a[i] && x>=L
last[x]=max{j} x|a[j] j<i
就是记每个约数x最后在哪个位置上TAT 好像表述不清啊
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
#include<iostream> #include<cstring> #include<cstdio> #include<cstdlib> #include<algorithm> #include<queue> #include<cmath> #include<map> #include<queue> #define mod 1000000007 #define inf 2000000000 #define ll long long using namespace std; inline ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,l,ans; int a[50005],f[50005]; int last[1000005]; int main() { n=read();l=read(); for(int i=1;i<=n;i++)a[i]=read(); for(int i=1;i<=n;i++) { int t=sqrt(a[i]); for(int k=1;k<=t;k++) if(a[i]%k==0) { if(k>=l)f[i]=max(f[last[k]]+1,f[i]); if(a[i]/k>=l)f[i]=max(f[last[a[i]/k]]+1,f[i]); last[k]=last[a[i]/k]=i; } ans=max(ans,f[i]); } printf("%d\n",ans); return 0; } |
Subscribe
计数器 9319783
OI 课件=>
OI 课件=>