1对兔子,从出生后第三个月起各类月都生一对兔子。小兔子长到第捌个月后每一个月又生一对兔子。假诺兔子都不死,请问第叁个月出生的一对兔子,至少供给繁衍到第多少个月时兔子总数才足以达到N对?

一对兔子,从诞生后第二个月起各种月都生一对兔子。小兔子长到第7个月后各种月又生壹对兔子。假若兔子都不死,请问第三个月出生的壹对兔子,至少供给繁衍到第多少个月时兔子总数才得以完成N对?

7-一 求奇数和(一5 分)
大旨须要测算给定的一层层正整数中奇数的和。
输入格式:
输入在壹行中付出一种类正整数,其间以空格分隔。当读到零或负整数时,表示输入完成,该数字并非处理。
出口格式:
在一行中输出正整数种类中奇数的和。
输入样例:
8 7 4 3 70 5 6 101 -1
出口样例:
116

猥琐中,感觉温馨思想僵硬,于是,计算一些贼有意思的题(坑),会不停立异。。。

输入格式:

输入在一行中付出一个不超过10000的正整数N。

输入格式:

输入在一行中提交二个不超越一千0的正整数N。

#include <stdio.h>
int main()
{
    int num,sum=0;
    scanf("%d",&num);
    while(num>0){
        if(num%2==1){
            sum+=num;
          }
        scanf("%d",&num);
    }
    printf("%d",sum);
    return 0;
}

先上一道简单的入门题:

输出格式:

在1行中输出兔子总数高达N最少须要的月数。

出口格式:

在1行中输出兔子总数高达N最少供给的月数。

7-贰 求给定精度的不难交错种类部分和(15 分)
大旨须求编写程序,总计连串部分和 一 – 1/4 + 1/7 – 百分之十 + …
直到最后一项的相对化值不超过给定精度eps。
输入格式:
输入在一行中提交1个正实数eps。
输出格式:
在壹行中遵守“sum =
S”的格式输出部分和的值S,精确到小数点后7人。标题保险计算结果不超过双精度范围。
输入样例一:
4E-2
出口样例一:
sum = 0.854457
输入样例二:
0.02
输出样例二:
sum = 0.826310

一、单词覆盖还原(数据坚实版)

输入样例:

30

输入样例:

30
#include <stdio.h>
#include <math.h>
int main(){
    int i,flag;
    double sum,num,eps;
    sum=0;
    flag=1;
    i=1;
    scanf("%lf",&eps);
    do{
        num=flag*1.0/(3*i-2);
        sum+=num;
        i++;
        flag=-flag;
    }while(fabs(num)>eps);
    printf("sum = %.6f",sum);
    return 0;
}

标题叙述

在一长串(3<=l<=25伍)中被一再贴有boy和girl两单词,后贴上的或然覆盖已贴上的单词(未有被遮盖的用句点表示),最后各样单词至少有1个字符未有被掩盖。问贴有多少个boy多少个girl?

输出样例:

9
 1 #include <stdio.h>
 2 
 3 int main(void)
 4 {
 5     int N;
 6     int i;
 7     int a = 1, b = 1;
 8 
 9     scanf("%d", &N);
10   
11     for ( i = 2; a < N && b < N; i++ ) {    //兔子的只数恰好是一个Feibonacci数列
12         if ( i % 2 ) {
13             a = a + b;
14         } else {
15             b = b + a;
16         }
17     }
18 
19     if ( N == 1 ) {
20         printf("1\n");
21     } else {
22         printf("%d\n", i);
23     }
24     return 0;
25 }

 

出口样例:

9
 1 #include <stdio.h> 2  3 int main(void) 4 { 5     int N; 6     int i; 7     int a = 1, b = 1; 8  9     scanf("%d", &N);10   11     for ( i = 2; a < N && b < N; i++ ) {    //兔子的只数恰好是一个Feibonacci数列12         if ( i % 2 ) {13             a = a + b;14         } else {15             b = b + a;16         }17     }18 19     if ( N == 1 ) {20         printf("1\n");21     } else {22         printf("%d\n", i);23     }24     return 0;25 }

7-3 求整数的位数及各位数字之和(一5 分)
对于给定的正整数N,求它的位数及其各位数字之和。
输入格式:
输入在一行中付出叁个不超过十
​9​​ 的正整数N。
出口格式:
在一行中输出N的位数及其各位数字之和,中间用三个空格隔开分离。
输入样例:
321
出口样例:
3 6

输入输出格式

输入格式:

一行被被反复贴有boy和girl两单词的字符串。

出口格式:

两行,八个整数。第2表现boy的个数,第二行为girl的个数。

#include <stdio.h>
#include <math.h>
int main(){
    int num,sum=0,count=0;
    scanf("%d",&num);
    while(num>0){
        sum+=num%10;
        num=num/10;
        count++;
    }
    printf("%d %d",count,sum);
    return 0;
}

输入输出样例

输入样例#1:

……boyogirlyy……girl…….

出口样例#1:

4
2

多少范围:

  对于百分之百的数目,满足字符串之间无空格且字符串长度小于十6

 

7-4 最大公约数和最小公倍数(一五 分)
核心供给八个给定正整数的最大公约数和最小公倍数。
输入格式:
输入在1行中提交三个正整数M和N(≤1000)。
输出格式:
在一行中逐条输出M和N的最大公约数和最小公倍数,两数字间以一空格相隔。
输入样例:
511 292
出口样例:
73 2044

Solution:

那道题其实相当粗略,在洛谷上有原题,而且是入门难度的,呵呵呵,初步还一直纠结题意,真是f**k。大家先解读一下样例,首先第四个boy就毫无说了,将来看有三个o,则一定覆盖了3个boy,继续以后看,两个y,则那里覆盖了一个boy,所以一共几个boy,至于girl的大家都能看出来,那里就不多说了。于是大家便能随便得出代码:

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int a,b;string c;
 4 int main()
 5 {
 6     cin>>c;
 7     int l=c.size();
 8     for(int i=0;i<l;i++){
 9     if(c[i]=='b'||c[i+1]=='o'||c[i+2]=='y')a++;
10     if(c[i]=='g'||c[i+1]=='i'||c[i+2]=='r'||c[i+3]=='l')b++;}
11     cout<<a<<endl<<b;
12     return 0;
13 }
#include <stdio.h>
#include <math.h>
int main(){
    int n,m,i,j;
    scanf("%d %d",&n,&m);
    for (i= m; i>0; i-- ){
       if ( m%i == 0 && n%i ==0 )  {
            break;  
       } 
    }
    for(j=n;;j++){
        if(j%m==0&&j%n==0){
            break;
        }
    }
    printf("%d %d",i,j);
    return 0;
}

2、N 色球

【题目叙述】
山山是2个双色球高手,每便必中远近知名。
终有壹天,他初阶嫌弃双色球的水彩太少了,于是发明了
N 色球。
规则如下:
3个口袋里拥有
n 个轻重缓急、形状相同的球,但每一种球标有唯一的数字
您要从那个口袋中摸出
n-1 个球,最终的奖金为那 n-一 个球所标数字的乘积除以 p 的余数。
山山想精晓他获得奖金的只求。
【输入文件】
输入文件
nsq.in 的第 一 行包含 2 个正整数 n,p
其次行李包裹蕴 n
个正整数 a壹,a二…an,表示各样球所标的数字
【输出文件】
输出文件
nsq.out 仅包涵一个实数,表示收获奖金的盼望
答案的相对误差不能够超越一e-陆
【样例输入】
3
100
2 1
7
【样例输出】
7.6666666667
【数据规模】
对于
20%的数据,n≤2000
对于
20%的数据,n≤10^5,ai≤10^5,p=1000000007
对于
60%的数据,n≤10^6,ai≤10^9,p≤1000000007

7-五 找出最小值(20 分)
核心要求编写程序,找出给定壹多重新整建数中的最小值。
输入格式:
输入在壹行中第二付诸一个正整数n,之后是n个整数,其间以空格分隔。
出口格式:
在一行中遵从“min = 最小值”的格式输出n个整数中的最小值。
输入样例:
4 -2 -123 100 0
出口样例:
min = -123

Solution:

首先,期望就无须自身赘述了,大家先转移一下题意,有n个数和多少个p,在那n个数中取n-二个数相乘再对p取模,将富有意况所得值相加除以n。毋庸置疑,共有n种情状,大家能够这么想,对于第i个数,大家不取它,而是把它前边和前边的数相乘取模,那样大家用数组f维护在此在此之前以往的前缀积,因为数量较大,所以我们每一回相乘便取模,同理,用数组b维护从后往前的后缀积,当然也要取模。那样,我们只需在此以前将来扫3回,第i个值=f[i-1]*b[i+1]%p,并累加起来,最终输出累加值除以n就行了。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cmath>
 5 #include<cstring>
 6 #include<queue>
 7 #include<map>
 8 using namespace std;
 9 #define ll long long
10 inline ll gi()
11 {
12     ll a=0;char x=getchar();bool f=0;
13     while((x>'9'||x<'0')&&x!='-')x=getchar();
14     if(x=='-')f=1,x=getchar();
15     while(x>='0'&&x<='9')a=a*10+x-48,x=getchar();
16     return f?-a:a;
17 }
18 ll n,p,a[1000005],f[1000005],b[1000005],tot;
19 int main()
20 {
21     //freopen("nsq.in","r",stdin);
22     //freopen("nsq.out","w",stdout);
23     n=gi(),p=gi();f[0]=1;b[n+1]=1;
24     for(int i=1;i<=n;i++)a[i]=gi(),f[i]=f[i-1]*a[i]%p;
25     b[n+1]=1;
26     for(int i=n;i>=1;i--)b[i]=(b[i+1]*a[i])%p;
27     for(int i=1;i<=n;i++)tot+=(f[i-1]*b[i+1])%p;
28     printf("%.10f",tot*1.0/n);
29     return 0;
30 }
#include <stdio.h>
#include <stdlib.h>

int main(void) {
    int n,num,min;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&num);
        if(i==1){
            min=num;
        }
        if(min>num){
            min=num;
        }
    }
    printf("min = %d",min);
    return EXIT_SUCCESS;
}

 3、Antiprime数

只要3个理所当然数n(n>=一),满意所有小于n的自然数(>=1)的约数个数都小于n的约数个数,则n是二个Antiprime数。譬如:一,
2, 4, 陆, 12, 2肆。

任务:

编三个程序:

一、 从ANT.IN中读入自然数n。

二、 统计不超出n的最大Antiprime数。

三、将结果输出到ANT.OUT中。

输入( antip.in):

输入文件antip.in唯有一个整数,n(1<= n <= 2 000 000 000)。

输出(antip.out):

输出文件antip.out也只蕴涵三个平头,即不高于n的最大Antiprime数。

样例输入( antip.in):

1000

样例输出(antip.out):

840

7-陆 总计素数并求和(20 分)
主旨须求计算给定整数M和N区间内素数的个数并对它们求和。
输入格式:
主干循环语句的使用,贼有意思。输入在壹行中付出八个正整数M和N(壹≤M≤N≤500)。
出口格式:
在1行中各样输出M和N区间内素数的个数以及它们的和,数字间以空格分隔。
输入样例:
10 31
出口样例:
7 143

Solution: 

(逆用)唯1分解定理+神奇的笔触~

对于3个小于n的介乎一定数额级上的数,鲜明它的质因子越小,这几个数所包括的因数就会愈多,所以大家得以只枚举几个较小质数的次方数,同时也能够减掉循环的次数。

而对于有1样因子数的多少个数,较小的贰个更有立异的半空中,所以当多个数有同等因子数时,大家取较小三个。

早晚要用long
long! 能够去探访那篇注解:

 

 1 #include<cstdio>  
 2 #include<cmath>  
 3 #define ll long long  
 4 ll n,maxx,num[12]={0,2,3,5,7,11,13,17,19,21,23},ans;  
 5 inline void findd(ll now,ll tot,ll u,ll v)  
 6 {  
 7     if(maxx<tot || (tot==maxx && ans>now))  
 8     {  
 9         maxx=tot;ans=now;  
10     }  
11     if(v>=11) return;  
12     for(ll i=1;i<=u;i++)  
13     {  
14         now*=num[v];  
15         if(now>n) return;  
16         findd(now,tot*(1+i),i,v+1);  
17     }  
18 }  
19 int main()  
20 {  
21     freopen("antip.in","r",stdin);  
22     freopen("antip.out","w",stdout);  
23     scanf("%lld",&n);  
24     findd(1,1,500,1);  
25     printf("%lld\n",ans);  
26     return 0;  
27 }
#include <stdio.h>
#include <math.h>
int main(){
    int n,m,sum=0,num=0;
    scanf("%d %d",&m,&n);
    for(int i=m;i<=n;i++){
        int count=0;
        for(int j=1; j<=i; j++) {
            if(i%j==0) {
                count++;
            }
        }
        if(count==2) {
            num++;
            sum+=i;
        }
    }
    printf("%d %d",num,sum);
    return 0;
}

4、Vrisible Lattice Points

【标题叙述】

从原点看率先象限的全数点,能一贯看看的点的数额是多少(不包蕴原点)

【输入文件】
第 ①行为测试数据的组数C(一<=C<=一千),

以下C行,每行李包裹蕴贰个数N(壹<=N<=一千),表示所求的可视范围。
【输出文件】
对此每壹组测试数据,输出一行贰个数,表示答案。
【样例输入】
4

2

4

5

231
【样例输出】

5

13

21

32549

7-7 特殊a串数列求和(20 分)
给定五个均不抢先九的正整数a和n,须求编写程序求a+aa+aaa++⋯+aa⋯a(n个a)之和。
输入格式:
输入在一行中付出不超越九的正整数a和n。
输出格式:
在一行中依据“s = 对应的和”的格式输出。
输入样例:
2 3
输出样例:
s = 246

Solution:

 首先,标题重假诺求从(0,0)能直接观望的点的个数。先怀念唯有1*壹的时候,很强烈只能见到一个点:(0,1)、(一,0)、(一,一)。其实就是下三角的个数*2+1(斜率为一的点)。那么除开一*一以外,大家只供给总括斜率从0到一里面的个数就行了,不包蕴壹,包涵0。结果设为sum,那么最后ans=sum*2+1。

1*三只有3个斜率为0的。

2*2斜率有0,1贰分之伍(0已经算过了,以往绝不再算了),其实正是多了多个斜率为一半的。

3*3的时候,又多了1/3、2/3两个。

4*四的时候,又多了1/4、百分之七10五也是多个。

5*5的时候,又多了1/5、2/5、3/5、4/5这4个。

……

从上面简单发现规律,对于n*n,能够从(0,0)连接受(n,0)到(n,n)上,斜率将会是1/n,2/n…(n-壹)/n。

凡是
分子和分母可以约分的,相当于有公约数的,前边都已经面世过了。所以每便添加的个数就是成员和分母互质的个数。

那便是说难点就转换到了,对于3个数n,求小于n的与n互质的数的个数,其实就是欧拉函数吧~~!

 

 1 #include <iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 #define maxn 1000008
 7 long long phi[maxn];
 8 void getphi()
 9 {
10     for(int i=1; i<maxn; i++) phi[i]=i;
11     for(int i=2; i<maxn; i+=2) phi[i]>>=1;
12     for(int i=3; i<maxn; i+=2)
13         if(phi[i]==i)
14         {
15             for(int j=i; j<maxn; j+=i)
16                 phi[j]=phi[j]/i*(i-1);
17         }
18     phi[1]=3;
19     for(int i=2; i<maxn; i++)
20         phi[i]=phi[i-1]+2*phi[i];
21 }
22 int main()
23 {
24     getphi();
25     int n,ca=0,t;
26     scanf("%d",&t);
27     while(t--)
28         scanf("%d",&n),
29         printf("%d %d %lld\n",++ca,n,phi[n]);
30     return 0;
31 }

 

#include <stdio.h>
#include <math.h>
int main(){
    int a,n,sum=0,count;
    scanf("%d %d",&a,&n);
    count=a;
    for(int i=1;i<=n;i++){
        sum+=a;
        a=a*10+count;
    }
    printf("s = %d",sum);
    return 0;
}

5、与运算

【标题叙述】
给定 n
个数,找出五个,使得它们经过与运算后结果最大。
留神,选出来的三个数在原数组中的地方无法平等,可是数值可以一如既往。
【输入格式】
率先行一个整数
n,表示数字个数。
第三行 n
个数,表示给定的数。
【输出格式】
三个整数表示答案。
【样例输入】
3
1 2
1
【样例输出】
1
【数据范围】
对于
百分之二十的数据点,n <= 1000
对此其余1/5的数据点,只有 0 和 一
对于
百分之百的数据点,n <= 壹仟00, 0 <= 数值 <= 10^玖

7-8 猜数字游戏(壹伍 分)
猜数字娱乐是令游戏机随机产生叁个十0以内的正整数,用户输入多少个数对其展开猜度,须要您编写程序自动对其与自由发生的被猜数进行比较,并提醒大了(“Too
big”),照旧小了(“Too
small”),相等表示猜到了。若是猜到,则截至程序。程序还必要总括猜的次数,假设2次猜出该数,提醒“Bingo!”;如若二回以内猜到该数,则提醒“Lucky
You!”;假使跨越一回不过在N(>三)次以内(包涵第N次)猜到该数,则提醒“Good
Guess!”;若是超越N次都并未有猜到,则提醒“Game
Over”,并停止程序。假若在抵达N次从前,用户输入了二个负数,也出口“Game
Over”,并甘休程序。
输入格式:
输入第三行中提交三个不超过拾0的正整数,分别是游戏机爆发的随意数、以及估量的最大次数N。最终每行给出3个用户的输入,直到出现负数甘休。
出口格式:
在1行中输出每一回估摸相应的结果,直到输出猜对的结果或“Game
Over”则截止。
输入样例:
58 4
70
50
56
58
60
-2
输出样例:
Too big
Too small
Too small
Good Guess!

Solution:

尽管从最高的1位向下找,假若那些人为一的数多于多个就取出那一个数,把其他数踢出,然后再取出的这一个数里面继续下1位的如出一辙的拍卖,笔者就用递归写的,最后留下的七个数的相与值会最大。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long
 4 #define il inline
 5 #define M 100005
 6 il ll gi()
 7 {
 8     int a=0;char x=getchar();bool f=0;
 9     while((x>'9'||x<'0')&&x!='-')x=getchar();
10     if(x=='-')x=getchar(),f=1;
11     while(x>='0'&&x<='9')a=a*10+x-48,x=getchar();
12     return f?-a:a;
13 }
14 int a[M],n;
15 il int getand(int *num,int len,int w)
16 {
17     int s[len],sta=0;
18     memset(s,0,sizeof(s));
19     int b=0;
20     for(int i=w;i>=0;i--)
21     {
22         for(int j=1;j<=len;j++)
23         {
24             if(num[j]&(1<<i)){
25             b++;
26             s[++sta]=num[j];
27             }
28         }
29         if(b>1)
30         {
31         int ret=getand(s,sta,i-1)+(1<<i);
32         return ret;
33         }
34     b=0;sta=0;
35     }
36 return 0;
37 }
38 int main()
39 {
40     
41     n=gi();
42     for(int i=1;i<=n;i++)a[i]=gi();
43     cout<<getand(a,n,31);
44     return 0;
45 }
/*
 ============================================================================
 Name        : 猜数字游戏(.c
 Author      : 
 Version     :
 Copyright   : Your copyright notice
 Description : Hello World in C, Ansi-style
 ============================================================================
 */

#include <stdio.h>
#include <stdlib.h>

int main(void) {
    int num, times;
    scanf("%d %d", &num, &times);
    int i = 0, guess;
    while (i < times) {

        scanf("%d", &guess);
        if (guess < 0) {
            printf("Game Over\n");
            break;
        }
        if (guess > num) {
            printf("Too big\n");
        }
        if (guess < num) {
            printf("Too small\n");
        }
        if (guess == num) {
            if (i == 0) {
                printf("Bingo!\n");
            } else if (i < 3) {
                printf("Lucky You!\n");
            }
            if (i >= 3) {
                printf("Good Guess!\n");
            }
                break;
        }
        i++;
    }
    if (i >= times) {
        printf("Game Over\n");
    }
    return EXIT_SUCCESS;
}

 陆、斐波拉契

题材叙述

小 C
养了壹部分很讨人喜欢的兔子。 有一天,小 C
突然意识兔子们都是严苛根据伟大的物文学家斐波那契提议的模子来进展
繁衍:壹对兔子从降生后第5个月起,每种月刚初始的时候都会产下1对小兔子。大家只要,
在全体进程中兔子不会合世任何意外。

小 C
把兔子按出生顺序,把兔子们从 壹 开始标号,并且小 C 的兔子都是 壹 号兔子和
1 号兔子的遗族。借使某两对兔子是还要出生的,那么小 C
会将父母标号更小的一对先行标 号。

假诺大家把那种涉及用画图下来,前五个月大概正是这么的:

金沙注册送58 1

其间,壹个箭头 A
→ B 表示 A 是 B 的先世,相同的颜料代表同1个月出生的兔子。

为了更加细致地了然兔子们是什么繁衍的,小
C 找来了一些兔子,并且向您建议了 m 个 难点:她想精晓关于每两对兔子 aia_iai​ 和 bib_ibi​
,他们的近日集体祖先是什么人。你能帮帮小 C
吗?

一对兔子的祖先是那对兔子以及他们老人家(假若有的话)的先世,而近来公共祖先是指
两对兔子所共有的祖辈中,离他们的距离之和不久前的1对兔子。比如,5 和 7的近年公共祖 先是 2,1 和 二 的近年来集体祖先是 一,6 和 6 的近年国有祖先是
6。

输入输出格式

输入格式:

从标准输入读入数据。
输入第一行,包括一个正整数 m。 输入接下去 m 行,每行包括 贰个正整数,表示 aia_iai​ 和 bib_ibi​

出口格式:

出口到正式输出中。
输入1共 m 行,每行一个正整数,依次表示您对难点的答案。

输入输出样例

输入样例#1:
复制

5 
1 1 
2 3 
5 7 
7 13 
4 12

输出样例#1:
复制

1 
1 
2 
2 
4 

说明

【数据范围与约定】
子职务会提交部分测试数据的特点。假使您在消除标题中蒙受了艰苦,能够尝试只解决一部分测试数据。 各样测试点的多少规模及特色如下表:

金沙注册送58 2

奇异性能一:有限扶助 aia_iai​, bib_ibi​
均为某一个月出生的兔子中标号最大的壹对兔子。例如,对
于前6个月,标号最大的兔子分别是 1, 二, 三, 5, 8,
1三。

特殊质量二:保障 ∣ai−bi∣≤壹|a_i-b_i|\le 1∣ai​−bi​∣≤1

7-玖 兔子繁衍难点(15 分)
一对兔子,从诞生后第7个月起各种月都生一对兔子。小兔子长到第13个月后每一种月又生壹对兔子。倘使兔子都不死,请问第三个月出生的一对兔子,至少供给繁衍到第多少个月时兔子总数才足以完成N对?
输入格式:
输入在1行中付出2个不超过10000的正整数N。
输出格式:
在1行中输出兔子总数达到N最少须要的月数。
输入样例:
30
出口样例:
9

Solution:

难点来自于洛谷的一回月赛,考的时候在ka哥提示下AC,值得一提那题其实很不难,关键是思路。

解法:斐波拉契

思路:广大人直接诶想到了lca吧,但对那道题显著是不得以的。我们思量列出几项斐波拉契数来搜寻规律:[1]
[2] [3] [4 5] [6 7 8] [9 10 11 12
13]…我们着眼一下上述的几项,同多个[]中的是同时出生的,我们发现第i个月出生的兔子恰巧就是它上个月事先的兔子所生,而且对于一个数x,它的一直老爹正是x-fi,所以大家能够对此每一趟询问(a,b),将a、b中较大的数先往前跳到它的爹爹,然后相比较此时a和b的尺寸是还是不是同样,若想同则输出该数,若不一致则重复上述手续继续往前跳。说的切近不太知道,可是大家协调列一列应该很不难见到。举个例子:尽管作者要询问8和1一的近年来国有祖先是什么人,大家先对11往前跳,即1壹-八拿走了三,此时可比三和八的大大小小,不对等,so用较大的数8继续往前跳,即8-五=叁,此时3和三相等了,所以三正是11和8的近年公共祖先。

注意:题目中数据较大到了十的11遍方,所以要开long
long,其它必须得预处理出斐波拉契中的前60项(因为数量只有10的1五遍方,斐波拉契的第40项刚好当先了多少范围),然后正是读入优化(数据有300多万次询问而且数还那么大),最后在可比时最棒二分查找节省时间。

代码量超少,关键是思路有点得考虑。

 

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long
 4 #define il inline
 5 ll m,a,b;
 6 il ll gi()
 7 {
 8     ll a=0;char x=getchar();bool f=0;
 9     while((x<'0'||x>'9')&&x!='-')x=getchar();
10     if(x=='-')x=getchar(),f=1;
11     while(x>='0'&&x<='9')a=a*10+x-48,x=getchar();
12     return f?-a:a;
13 }
14 ll c[1000000];
15 il void find(ll a,ll b)
16 {
17     if(a<b)swap(a,b);
18     if(a==b){printf("%lld\n",a);return;}
19     int w=lower_bound(c,c+62,a)-c;
20     find(b,a-c[w-1]);
21 }
22 int main()
23 {
24     m=gi();
25     c[0]=1;c[1]=1;
26     for(int i=2;i<=61;i++)c[i]=c[i-1]+c[i-2];//printf("%lld\n",c[i]);
27     while(m--)
28     {
29         a=gi(),b=gi();
30         find(a,b);
31     }
32     return 0;
33 }
#include <stdio.h>
#include <math.h>
int main(){
    int rabbit_one,rabbit_two=1,month=1,x=1,y=1;
    scanf("%d",&rabbit_one);
    while(rabbit_two<rabbit_one){
        rabbit_two=x+y;
        x=y;
        y=rabbit_two;
      month++;
    }
    if(month==1){
        printf("1");
    }else{
        printf("%d",month+1);
    }
    return 0;
}

 7、圆圈

 

圆圈
c c ircle
.cpp/in/out
1s /
128M
[
标题描述]
现行反革命有二个圆形,
顺时针标号分别从 0 到 n-1,
每一趟等可能率顺时针走一步照旧逆时针走一步,
即只要您在 i
号点,你有 二分之一 可能率走到((i-1)mod n)号点,十一分之5 可能率走到((i+一)mod
n)号点。问
从 0
号点走到 x 号点的企盼步数。
[
输入]
首先行李包裹罗三个平头
T,表示数据的组数。
接下去有
T 行,每行李包裹括七个整数 n, x。
T<=10,
0<=x<n<=300;
[
输出]
对于每组数据,输出一行,包括二个二人小数表示答案。
[
样例输入]
3
3
2
5
4
10
5
[
样例输出]
2.0000
4.0000
25.0000
[
数据范围]
对于 30%
的数据,n<=20
对于 50%
的数据,n<=100
对于 70%
的数据,n<=200
对于
100%的数据,n<=300

7-10 高空坠球(20 分)
皮球从某给定中度自由落下,触地后反弹到原高度的1/二,再落下,再反弹,……,如此频仍。问皮球在第n次落地时,在空中壹共经过多远?第n次反弹的惊人是有点?
输入格式:
输入在一行中付出五个非负整数,分别是皮球的起来中度和n,均在长整型范围内。
出口格式:
在1行中各样输出皮球第n次落地时在空间经过的偏离、以及第n次反弹的冲天,其间以3个空格分隔,保留1位小数。标题保障总结结果不超过双精度范围。
输入样例:
33 5
出口样例:
94.9 1.0

Solution:

题材来源
sdut 287八:
梦想公式:
E[x]=0
(x==0);
E[x]=0.5*(E[x-1]+1)+0.5*(E[x+1]+1);
(x!=0)
移项得,-E[i-1]*0.5+E[i]*0.5-E[i+1]*0.5=1
n
个方程高斯消元求解。因为各个方程唯有多个不为零周全,所以当 TLE
能够恰到好处剪枝。

实则能够一贯打表,然后轻易察觉规律。详见代码。

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 int t,n,x;
 5 int main()
 6 {
 7     freopen("circle.in","r",stdin);
 8     freopen("circle.out","w",stdout);
 9     scanf("%d",&t);
10     while(t--)
11     {
12         scanf("%d%d",&n,&x);
13         printf("%d.0000\n",(n-x)*x);
14     }
15     return 0;
16 }
#include <stdio.h>
int main(void) {
    int i, n;
    double distance, height;
    scanf("%lf%d", &height, &n);
    if(n==0) {
        printf("0.0 0.0\n");
    } else {
        distance = height;
        for(i=1;i<n;i++){
                height = height / 2;
                distance = distance + height * 2;
        }
        printf("%.1f %.1f\n", distance, height/2);
    }


}

 八、Infiniti体系

 

不过种类
infinit
.pas/c/cpp
1s /
128M
[ [
难题讲述] ]
大家按以下办法发出体系:
一、
起头时类别是: “一” ;
二、
每一次生成把类别中的 “1” 变成 “十” ,”0″ 变成 “一”。
因此极其次生成,大家获取种类”101十拾110110十110一…”。
1共有 Q
个询问,每便询问为:在区间 A 和 B 之间有稍许个 1。
请写多个主次回答
Q 个询问。
[ [
输入 数据 ]
率先行事贰个整数
Q,前面有 Q 行,每行七个数用空格隔断的平头 a, b。
[ [
输出 数据 ]
共 Q
行,每行1个回复
[ [
输入 样例] ]
1
2
8
[ [
输出样例] ]
4
[ [
数据 范围] ]
1 <= Q
<= 5000
1 <= a
<= b < 2^63

Solution:

 

小编们先看看类别变化规律,
S一 = “一”, S贰 = “拾”, S3 = “十壹”, S四 = “十110”, S五 = “十1十101”,
等等. Si
是 S(i+1)的前缀。
队列 Si
是由类别 S(i-一) 和 S(i-2), 连接而成的。
即 Si =
Si-一 + Si-二 (实际上上是 Fibonacci 数列)。
找到规律现在,大家得以能够用递归的主意求出从从位置一 到岗位 X 之间具有的 1 的个数,
用1个函数 F
计算,结果为 f(b)-f(a-一)。
现实的参见:
日子复杂度为:
O(Q * log MAX_VAL)
此题须要先找出数学规律,
再进用递归达成。 主要考察选手的数学思维能力和递归程序的实
现。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cmath>
 5 #include<cstring>
 6 using namespace std;
 7 #define ll long long
 8 ll q,x,y,f[100];
 9 inline ll gi()
10 {
11     ll a=0;char x=getchar();bool f=0;
12     while((x<'0'||x>'9')&&x!='-')x=getchar();
13     if(f=='-')x=getchar(),f=1;
14     while(x>='0'&&x<='9')a=a*10+x-48,x=getchar();
15     return f?-a:a;
16 }
17 inline ll find(ll l,ll k)
18 {
19     if(l==0)return 0;
20     if(l==f[k])return f[k-1];
21     else if(l<=f[k-1])return find(l,k-1);
22     return f[k-2]+find(l-f[k-1],k-2);
23 }
24 int main()
25 {
26     freopen("infinit.in","r",stdin);
27     freopen("infinit.out","w",stdout);
28     q=gi();f[0]=1;f[1]=1;
29     for(int i=2;i<=91;i++)f[i]=f[i-1]+f[i-2];
30     while(q--){
31     x=gi();y=gi();
32     printf("%lld\n",find(y,91)-find(x-1,91));
33     }
34     return 0;
35 
36 }

9、删数

[ [
难题讲述] ]
有 N
个分裂的正整数数 x 一 , x 二 , … x N
排成壹排,我们得以从左边或右侧去掉三番五次的 i 个数
(只能从两边删除数),壹<=i<=n,剩下
N-i 个数,再把结余的数按以上操作处理,直到所
局地数都被删去截至。
每一趟操作都有一个操作价值,
比如今后要刨除从 i 地点到 k 地方上的有所的数。 操作价值为
|x i – x
k
|*(k-i+一),假设只去掉二个数,操作价值为这些数的值。怎么样操作能够获得最大
值,求操作的最大价值。
[ [
输入数据] ]
先是表现三个正整数
N,第1行有 N 个用空格隔绝的 N 个差别的正整数。
[
输出数据] ]
包蕴一个正整数,为操作的最大值
[ [
样例] ]
re move
.in
6
54 29 196
21 133 118
re move.
. out
768
[ [
数据范围] ]
3<=N<=100
N
个操作数为 1..一千 之间的整数。
[ [
样例表明] ]
经过 三回操作能够收获最大值,第一回去掉前边 三 个数 5四、2九、1玖陆,操作价值为
4二陆。第
2次操作是在剩余的四个数(21
133 118)中去掉最终三个数 11八,操作价值为 11捌。第1
次操作去掉多余的
② 个数 贰一 和 13三 ,操作价值为 2二肆。操作总价值为 42陆+11八+2贰肆=76八。

Solution:

那是八个着力的动态规划难点。
我们用
F[i][j]表示按规则消去数列 a[i..j]收获的的最大值;
删去第 i
个数获得的最大值为 a[i];
删除
a[i..j]赢得的最大值为:一遍性删除数列
a[i..j]取得的值是|a[i]-a[j]|*(j-i+1)
抑或是先删除
a[i..k] 再删除 a[k+1..j], k 在 i 到 j-1 之间,获得的值是
F[i][k]+F[k+1][j].
作者们取得气象转移方程:
F[i][i]=a[i],
for i=1..N
对于随意的
i<j,有:
F[i][j]=max{|a[i]-a[j]|*(j-i+1),
f[i][i]+f[i+1][j],
F[i][i+1]+F[i+2][j]金沙注册送58,,…,F[i][j-1]+F[j][j]}
F[1,n]为所求的解
岁月复杂度:o(N^3);
此题供给选手对算法的光阴复杂度举办分析,
简单的探寻是不可能在显著时间内求出结果, 必
需使用便捷的算法,首要调查选手接纳高效算法——动态规划化解难点的能力

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cmath>
 5 #include<cstring>
 6 #include<vector>
 7 #include<queue>
 8 using namespace std;
 9 int n,ans,a[505],f[505][505];
10 int main()
11 {
12     freopen("remove.in","r",stdin);
13     freopen("remove.out","w",stdout);  
14     scanf("%d",&n);  
15     for(int i=1;i<=n;i++)  
16     {  
17         scanf("%d",&a[i]);  
18         f[i][1]=a[i];  
19     }  
20     for(int j=2;j<=n;j++)   
21     for(int i=1;i<=n-j+1;i++)  
22     {  
23         f[i][j]=j*fabs(a[i]-a[i+j-1]);  
24         for(int k=1;k<j;k++)  
25         f[i][j]=max(f[i][j],f[i][k]+f[k+i][j-k]);  
26     }  
27     for(int i=1;i<=n;i++)ans=max(ans,f[i][n]);    
28     printf("%d",ans); 
29     return 0;
30 }

 10、组合数

【标题叙述】
新近教师教了小明怎么算组合数,小明又想到了三个标题。
。 。
小明定义
C(N,K)表示从 N 个要素中不重复地挑选 K 个成分的方案数。
小明想驾驭的是
C(N,K)的奇偶性。
自然,那个整天都老是用竖式算
12345678玖*98765432一=?的人不会让您那么让祥和那
么轻松,它说:
“N 和 K 都大概非常的大。 ”
然而小明也举步维艰了,所以它就找到了你,想请你帮他化解那些标题。
【输入描述】
输入文件:comb.in
第 壹行:1个正整数 t,表示数据的组数。

2~二+t-一 行:五个非负整数 N 和 K。 (保险 k<=n)
【输出描述】
输出文件:comb.out
对于每一组输入,就算C(N,K)是奇数则输出 壹,不然输出 0。
【样例输入】
3
1
1
1
0
2
1
【样例输出】
1
1
0
【数据范围】
对于 30%
的数据,n<=10^2 t<=10^4
对于 50%
的数据,n<=10^3 t<=10^5
对于
100%的数据,n<=10^8 t<=10^5
【预备知识

C(n, 0) =
C(n, n) = 1 (n > 0;)
C(n, k) =
C(n − 1, k − 1) + C(n − 1, k) (0 < k < n)

Solution:

假定本题你还思虑定式的用高精度计算,那你就夭折了。
(能够得一些分)
主旨首要调查数学知识。
方法一:统计
n!质因子中 二 的个数
n! = 2^a
* M
a=[n/2]+[n/(2^2)]+[n/(2^3)]+
… +[n/(2^g)] (2^(g+1)>n>=2^g)
申明:加法原理
为此
C(N)K 质因子中 二 的个数为 F = f(N) – f(K) – f(N – K)
若 F 大于
0,则为偶数,等于零为奇数。
*措施2:由
Lucas 定理妥善 k==(k&n)时为奇数,不然为偶数。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 using namespace std;
 5 int t,n,k;
 6 int gi() {
 7     int a=0;bool f=0;char c=getchar();
 8     while (c>'9'||c<'0') {if (c=='-') f=1;c=getchar();}
 9     while (c>='0'&&c<='9') {a=a*10+c-'0';c=getchar();}
10     return f?-a:a;
11 }
12 
13 int main() {
14     freopen("comb.in","r",stdin);
15     freopen("comb.out","w",stdout);
16     t=gi();
17     int ans;
18     while (t--) {
19         n=gi();k=gi();
20         ans=(n&k)==k?1:0;
21         cout<<ans<<endl;
22     }
23     return 0;
24 }

 11、偶数

【题目叙述】
山山有一个长度为
N 的行列。当体系中留存相邻的三个数的和为偶数的话,LGTB 就
能把它们删掉。
山山想让类别尽量短,请问能将类别裁减到多少个数?
【输入格式】
率先行包蕴贰个数
N 代表类别伊始长度。
接下去壹行李包裹蕴N 个数 a一 ,a2 ,…,aN ,代表系列。
【输出格式】
输出包括一个数代表操作后系列最短长度
【样例输入】
10
1 3 3 4 2
4 1 3 7 1
【样例输出】
2
【数据范围】
对于 50%
的数据,1 ≤ N ≤ 1000
对于 100%
的数据,1 ≤ N ≤ 10 5 ,0 ≤ ai ≤ 10 9

Solution:

设想到三番五次的1段奇偶性相同的数字才能被删去,所以向来贪心即可,用栈完成

 1 #include<iostream>
 2 #include<cstdio>
 3 #pragma GCC optimize(2)
 4 using namespace std;
 5 #define ll long long 
 6 #define il inline
 7 ll a[100005],s[100005];
 8 il ll gi()
 9 {
10     ll a=0;char x=getchar();bool f=0;
11     while((x<'0'||x>'9')&&x!='-')x=getchar();
12     if(x=='-')x=getchar(),f=1;
13     while(x>='0'&&x<='9')a=a*10+x-48,x=getchar();
14     return f?-a:a;
15 }
16 int main()
17 {
18     freopen("even.in","r",stdin);
19     freopen("even.out","w",stdout);
20     ll n=gi(),t=0;
21     for(int i=1;i<=n;i++){
22     a[i]=gi();
23     if(!t)s[++t]=a[i];
24     else if(s[t]+a[i]&1)s[++t]=a[i];
25     else t--;
26     }
27     cout<<t;
28     return 0;
29 }

12、序列

【题目叙述】
山山有二个长度为
N 的行列 A,今后他想协会二个新的尺寸为 N 的连串
B,使得 B
中的任意五个数都互质。
同时她要使
最小。
请输出最小值。
【输入格式】
首先行李包裹括三个数
N 代表体系起首长度
接下去一行李包裹蕴N 个数 A1 , A2 ,…, AN ,代表连串 A
【输出格式】
输出包含壹行,代表最小值
【样例输入】
5
1 6 4 2
8
【样例输出】
3
【样例表达】
样例中 B
数组可以为 一 伍 3 一 捌
【数据范围】
对于 40%
的数据,1 ≤ N ≤ 10
对于 100%
的数据,1 ≤ N ≤ 100,1 ≤ ai ≤ 30

Solution:

设想到ai最多变成5八,要是改为越来越大的数还不及变成一,而且58之内只有拾伍个素数

并且能够表达对于多少个数a > b,变成的数A >= B

于是最五只有17个最大的数成为素数,别的的数都会化为1

就此直接对于前拾四个数dp,dp[i][j]意味着到第i个数,哪些素因子被用过了,开支至少为多少。枚举一个数来转换即可

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cmath>
 5 #include<cstring>
 6 using namespace std;
 7 #define smax(x,tmp) x=max((x),(tmp))
 8 #define smin(x,tmp) x=min((x),(tmp))
 9 const int INF=0x3f3f3f3f;
10 const int prime[] = {0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53};
11 int n,a[105],f[17][1<<17],pdd[105];
12 inline bool cmp(int a,int b){return a>b;}
13 int main()
14 {
15     freopen("seq.in","r",stdin);
16         freopen("seq.out","w",stdout);
17         scanf("%d",&n);
18     for(int i=1;i<=n;i++)scanf("%d",&a[i]);
19         sort(a+1,a+n+1,cmp);
20     for(int i=1;i<=58;i++)
21         for(int j=1;j<=16;j++)
22             if(i<prime[j])break;
23             else if(i%prime[j]==0)pdd[i]|=(1<<j-1);
24         memset(f,0x3f,sizeof(f));
25         f[0][0]=0;
26     for(int i=1;i<=min(n,16);i++)
27         for(int j=0;j<(1<<16);j++)
28                 for(int k=1;k<=58;k++)
29                 if(!(pdd[k]&j))smin(f[i][j|pdd[k]],f[i-1][j]+abs(a[i]-k));
30     int ans=INF;
31     for(int j=0;j<(1<<16);j++)smin(ans,f[min(n,16)][j]);
32     if(n>16)for(int i=17;i<=n;i++)ans+=abs(a[i]-1);
33        printf("%d",ans);
34     return 0;
35 }

 

相关文章

网站地图xml地图