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

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

阅读量：5369 次

发布时间：2019-06-15

本文共 4137 字，大约阅读时间需要 13 分钟。

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

Time Limit: 10 Sec Memory Limit: 512 MB

Submit: 36 Solved: 15

[][][]

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
      
          2 #include
       
           3 #include
        
            4 #include
         
             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\n",ans);  37     return 0;  38 }

View Code

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

Time Limit: 10 Sec Memory Limit: 512 MB

Submit: 40 Solved: 21

[][][]

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 11 3 2 5 4

Sample Output

HINT

Source

1 #include
      
          2 #include
       
           3 #include
        
            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]
         
          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\n%d\n",top,ans[top]%mod);  53     else printf("%d\n",top);  54     return 0;  55 }

View Code

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

Time Limit: 10 Sec Memory Limit: 512 MB

Submit: 17 Solved: 11

[][][]

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
      
          2 #include
       
           3 #include
        
            4 #include
         
             5 #include
          
              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