begin.lydsy 入门OJ题库：3611-3613：神炎皇、降雷皇、幻魔皇

3611: [noip2016十连测第八场]神炎皇

Time Limit: 10 Sec Memory Limit: 512 MB
Submit: 36 Solved: 15
[Submit][Status][Web Board]

Description

http://www.lydsy.com/JudgeOnline/upload/201610/test8888.rar

神炎皇乌利亚很喜欢数对，他想找到神奇的数对。
对于一个整数对(a,b)，若满足a+b<=n且a+b是ab的因子，则成为神奇的数对。请问这样的数对共有多少呢？

Input

一行一个整数n,n<=100000000000000

Output

一行一个整数表示答案，保证不超过64位整数范围。

Sample Input

Sample Output

HINT

Source

 1 #include<cmath>  
 2 #include<cstdio>  
 3 #include<cstring>  
 4 #include<algorithm>  
 5 #define ll long long  
 6 using namespace std;  
 7 ll n,m,ans;  
 8 int prime[10000010],phi[10000010];  
 9 bool p[10000010];  
10 inline void shai()  
11 {    
12     phi[1]=1;   
13     for(int i=2;i<=m;++i)  
14      {  
15         if(!p[i])  
16          {  
17             p[i]=1;  
18             prime[++prime[0]]=i;  
19             phi[i]=i-1;  
20          }  
21         for(int j=1;j<=prime[0];++j)  
22          {  
23             if((ll)i*prime[j]>m) break;  
24             p[i*prime[j]]=1;  
25             if(i%prime[j]) phi[i*prime[j]]=phi[i]*(prime[j]-1);  
26              else {phi[i*prime[j]]=phi[i]*prime[j]; break; }  
27          }  
28         ans+=(ll)phi[i]*(ll)(n/i/i);  
29      }  
30 }  
31 int main()  
32 {  
33     scanf("%lld",&n);  
34     m=sqrt(n);  
35     shai();  
36     printf("%lld
",ans);  
37     return 0;  
38 }

View Code

3612: [noip2016十连测第八场]降雷皇

Time Limit: 10 Sec Memory Limit: 512 MB
Submit: 40 Solved: 21
[Submit][Status][Web Board]

Description

http://www.lydsy.com/JudgeOnline/upload/201610/test8888.rar

降雷皇哈蒙很喜欢雷电，他想找到神奇的电光。哈蒙有n条导线排成一排，每条导线有一个电阻值，神奇的电光只
能从一根导线传到电阻比它大的上面，而且必须从左边向右传导，当然导线不必是连续的。哈蒙想知道电光最多能
通过多少条导线，还想知道这样的方案有多少。

Input

第一行两个整数n和type。type表示数据类型
第二行n个整数表示电阻。
n<=100000,电阻值不超过100000

Output

第一行一个整数表示电光最多能通过多少条导线。
如果type=1则需要输出第二行，表示方案数，对123456789取模。

Sample Input

5 1
1 3 2 5 4

Sample Output

3
4

HINT

Source

 1 #include<cstdio>  
 2 #include<cstring>  
 3 #include<algorithm>  
 4 #define mod 123456789  
 5 using namespace std;  
 6 int f[100010],top,g[100010],ans[100010];  
 7 int a[100010],nxt[100010],p[100010],num[100010],tot;  
 8 int n,opt;  
 9 inline void add(int x,int y,int val)  
10 {  
11     tot++; a[tot]=y; nxt[tot]=p[x]; p[x]=tot; num[tot]=val;  
12 }  
13 inline void solve(int x,int val)  
14 {  
15     if(x==1) {add(x,val,1); ans[x]++; return;}  
16     int cnt=0;  
17     for(int i=p[x-1];i!=-1;i=nxt[i])  
18      if(a[i]>=val) break;  
19       else cnt+=num[i],cnt%=mod;  
20     ans[x]+=cnt; ans[x]%=mod;  
21     add(x,val,cnt%mod);  
22 }  
23 inline void ask(int nm,int len,int x)  
24 {  
25     int l=1,r=len,mid;  
26     while(l<=r)  
27      {  
28         mid=(l+r)>>1;  
29         if(f[mid]<x) l=mid+1;  
30          else r=mid-1;  
31      }  
32     f[l]=x;   
33     if(opt==1) g[nm]=l,solve(l,x);  
34 }  
35 int main()  
36 {  
37     int i,j;  
38     memset(p,-1,sizeof(p));  
39     memset(nxt,-1,sizeof(nxt));  
40     scanf("%d%d",&n,&opt);  
41     for(i=1;i<=n;++i)  
42      {  
43         int x;  
44         scanf("%d",&x);  
45         if(x>f[top])   
46          {  
47             f[++top]=x;  
48             if(opt==1) g[i]=top,solve(top,x);  
49           }   
50          else ask(i,top,x);  
51      }  
52     if(opt==1) printf("%d
%d
",top,ans[top]%mod);  
53     else printf("%d
",top);  
54     return 0;  
55 }

View Code

3613: [noip2016十连测第八场]幻魔皇

Time Limit: 10 Sec Memory Limit: 512 MB
Submit: 17 Solved: 11
[Submit][Status][Web Board]

Description

http://www.lydsy.com/JudgeOnline/upload/201610/test8888.rar

幻魔皇拉比艾尔很喜欢斐波那契树，他想找到神奇的节点对。所谓斐波那契树，根是一个白色节点，每个白色节点
都有一个黑色节点儿子，而每个黑色节点则有一个白色和一个黑色节点儿子。神奇的节点对则是指白色节点对。请
问对于深度为n的斐波那契树，其中距离为i的神奇节点对有多少个？拉比艾尔需要你对于1<=i<=2n的所有i都求出
答案。

Input

一行一个正整数n,n<=5000

Output

一行2n个整数表示答案，对123456789取模。

Sample Input

Sample Output

0 2 3 3 1 1 0 0 0 0

HINT

Source

 1 #include<iostream>  
 2 #include<cstdio>  
 3 #include<algorithm>  
 4 #include<cstring>  
 5 #include<cmath>  
 6 #define N 10003  
 7 #define p 123456789  
 8 #define LL long long  
 9 using namespace std;  
10 LL n,m,f[N],w[N],b[N],sum[N];  
11 LL ans[N];  
12 int main()  
13 {  
14     scanf("%I64d",&n);  
15     f[1]=1; f[2]=1;  
16     for (int i=3;i<=5000;i++)  
17      f[i]=(f[i-1]+f[i-2])%p;  
18     w[1]=1; w[2]=0; w[3]=1; w[4]=1;  
19     for (int i=5;i<=5000;i++) w[i]=(w[i-1]+w[i-2])%p;  
20     for (int i=1;i<=5000;i++) sum[i]=(sum[i-1]+w[i])%p;  
21     for (int i=1;i<n;i++)  
22      ans[i]=sum[n-i]*w[i+1]%p;  
23     for (int i=1;i<n;i++)  
24      for (int j=1;j<n;j++)  
25       ans[i+j]=(ans[i+j]+(sum[n-max(i,j)+1]-1)*w[i]%p*w[j+1])%p;  
26     for (int i=1;i<=2*n;i++)  
27      cout<<ans[i]<<" ";  
28     cout<<endl;  
29 }

View Code