趣味性的高智力,基本循环语句的利用

一对兔子,从诞生后第6个月起种种月都生一对兔子。小兔子长到第五个月后每一个月又生一对兔子。若是兔子都不死,请问第3个月出生的一对兔子,至少必要繁衍到第几个月时兔子总数才能够完成N对?

1对兔子,从降生后第13个月起各类月都生一对兔子。小兔子长到第几个月后各样月又生一对兔子。假如兔子都不死,请问第3个月出生的1对兔子,至少必要繁衍到第多少个月时兔子总数才方可达到规定的标准N对?

7-一 求奇数和(壹5 分)
核心须要测算给定的1连串正整数中奇数的和。
输入格式:
输入在壹行中提交1多元日整数,其间以空格分隔。当读到零或负整数时,表示输入完毕,该数字并非处理。
出口格式:
在1行中输出正整数体系中奇数的和。
输入样例:
8 7 4 3 70 5 6 101 -1
输出样例:
116

无聊中,感觉温馨思想僵硬,于是,计算一些贼有意思的题(坑),会频频更新。。。

输入格式:

输入在1行中提交3个不超过一千0的正整数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道不难的入门题:

出口格式:

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

输出格式:

在一行中输出兔子总数达到N最少要求的月数。

7-2 求给定精度的粗略交错连串部分和(一5 分)
大旨须要编写程序,总计体系部分和 一 – 四分一 + 1肆.2九% – 一成 + …
直到最终1项的断然值不当先给定精度eps。
输入格式:
输入在一行中提交一个正实数eps。
输出格式:
在1行中服从“sum =
S”的格式输出部分和的值S,精确到小数点后伍位。标题保障计算结果不超过双精度范围。
输入样例一:
4E-2
出口样例1:
sum = 0.854457
输入样例二:
0.02
输出样例2:
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;
}

题材叙述

在1长串(3<=l<=255)中被反复贴有boy和girl两单词,后贴上的大概覆盖已贴上的单词(没有被遮住的用句点表示),最终每一种单词至少有2个字符未有被遮盖。问贴有多少个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 求整数的位数及各位数字之和(一伍 分)
对此给定的正整数N,求它的位数及其各位数字之和。
输入格式:
输入在一行中提交二个不当先十
​九​​ 的正整数N。
出口格式:
在一行中输出N的位数及其各位数字之和,中间用三个空格隔离。
输入样例:
321
输出样例:
3 6

输入输出格式

输入格式:

1行被被频仍贴有boy和girl两单词的字符串。

出口格式:

两行,多少个整数。第3行事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-④ 最大公约数和最小公倍数(一伍 分)
大旨要求多个给定正整数的最大公约数和最小公倍数。
输入格式:
输入在一行中提交五个正整数M和N(≤一千)。
输出格式:
在1行中相继输出M和N的最大公约数和最小公倍数,两数字间以一空格相间。
输入样例:
511 292
输出样例:
73 2044

Solution:

那道题其实一点也不细略,在洛谷上有原题,而且是入门难度的,呵呵呵,伊始还一直纠结题意,真是f**k。大家先解读一下样例,首先第八个boy就绝不说了,以往看有1个o,则肯定覆盖了3个boy,继续今后看,八个y,则那里覆盖了三个boy,所以一共5个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 色球

【标题叙述】
山山是二个双色球高手,每趟必中确确实实。
终有一天,他伊始嫌弃双色球的颜料太少了,于是发明了
N 色球。
平整如下:
一个口袋里有着
n 个高低、形状相同的球,但各类球标有唯一的数字
你要从这几个袋子中摸出
n-一 个球,最终的奖金为那 n-一 个球所标数字的乘积除以 p 的余数。
山山想了然她收获奖金的梦想。
【输入文件】
输入文件
nsq.in 的第 1 行李包裹涵 二 个正整数 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-5 找出最小值(20 分)
宗旨供给编写程序,找出给定一多重新整建数中的最小值。
输入格式:
输入在1行中率先付诸二个正整数n,之后是n个整数,其间以空格分隔。
输出格式:
在1行中遵守“min = 最小值”的格式输出n个整数中的最小值。
输入样例:
4 -2 -123 100 0
出口样例:
min = -123

Solution:

首先,期望就无须本身赘述了,大家先转移一下题意,有n个数和3个p,在那n个数中取n-叁个数相乘再对p取模,将装有境况所得值相加除以n。毋庸置疑,共有n种景况,大家能够那样想,对于第i个数,我们不取它,而是把它前面和前边的数相乘取模,那样大家用数组f维护从前将来的前缀积,因为数量较大,所以我们每一遍相乘便取模,同理,用数组b维护从后往前的后缀积,当然也要取模。那样,大家只需从前将来扫二次,第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数

如果二个本来数n(n>=一),满意全部小于n的自然数(>=一)的约数个数都小于n的约数个数,则n是2个Antiprime数。譬如:一,
二, 四, 陆, 1二, 贰4。

任务:

编三个程序:

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

二、 总计不超过n的最大Antiprime数。

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

输入( antip.in):

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

输出(antip.out):

出口文件antip.out也只包括1个整数,即不高于n的最大Antiprime数。

样例输入( antip.in):

1000

样例输出(antip.out):

840

7-陆 总括素数并求和(20 分)
核心要求统计给定整数M和N区间内素数的个数并对它们求和。
输入格式:
输入在1行中提交多少个正整数M和N(一≤M≤N≤500)。
出口格式:
在一行中逐一输出M和N区间内素数的个数以及它们的和,数字间以空格分隔。
输入样例:
10 31
输出样例:
7 143

Solution: 

(逆用)唯1分解定理+神奇的思路~

对于一个小于n的处于自然数量级上的数,鲜明它的质因子越小,那几个数所包罗的因数就会越来越多,所以大家能够只枚举多少个较小质数的次方数,同时也得以减掉循环的次数。

而对于有相同因子数的四个数,较小的三个更有立异的长空,所以当七个数有同样因子数时,我们取较小三个。

毫无疑问要用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

【标题叙述】

从原点看率先象限的全数点,能直接看到的点的数目是不怎么(不分包原点)

【输入文件】
第 1表现测试数据的组数C(一<=C<=一千),

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

2

4

5

231
【样例输出】

5

13

21

32549

7-七 特殊a串数列求和(20 分)
给定多少个均不超越玖的正整数a和n,要求编写程序求a+aa+aaa++⋯+aa⋯a(n个a)之和。
输入格式:
输入在壹行中提交不超过九的正整数a和n。
出口格式:
在1行中服从“s = 对应的和”的格式输出。
输入样例:
2 3
输出样例:
s = 246

Solution:

 首先,标题重假使求从(0,0)能直接看到的点的个数。先怀念唯有一*1的时候,很明显只可以见到1个点:(0,壹)、(一,0)、(一,一)。其实便是下三角的个数*二+一(斜率为一的点)。那么除开1*1以外,大家只须求总计斜率从0到一之内的个数就行了,不包涵一,包蕴0。结果设为sum,那么最后ans=sum*2+1。

趣味性的高智力,基本循环语句的利用。1*3唯有2个斜率为0的。

2*2斜率有0,四分之二(0已经算过了,现在绝不再算了),其实便是多了二个斜率为3/6的。

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

4*4的时候,又多了25%、四分三也是五个。

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。

凡是
分子和分母能够约分的,也正是有公约数的,前边都曾经冒出过了。所以每趟添加的个数就是成员和分母互质的个数。

那就是说难点就转换到了,对此二个数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
个数,找出三个,使得它们经过与运算后结果最大。
留神,选出来的五个数在原数组中的地方不能够1如既往,不过数值能够1如既往。
【输入格式】
第三行3个整数
n,表示数字个数。
第1行 n
个数,表示给定的数。
【输出格式】
1个整数表示答案。
【样例输入】
3
1 2
1
【样例输出】
1
【数据范围】
对于
五分一的数据点,n <= 一千
对此其它十分之二的数据点,唯有 0 和 一
对于
百分之百的数据点,n <= 一千00, 0 <= 数值 <= 十^九

7-八 猜数字娱乐(一伍 分)
猜数字娱乐是令游戏机随机发生贰个十0以内的正整数,用户输入1个数对其开始展览推测,须要您编写程序自动对其与人身自由产生的被猜数举办相比,并提示大了(“Too
big”),还是小了(“Too
small”),相等表示猜到了。纵然猜到,则停止程序。程序还必要总计猜的次数,假设1回猜出该数,提醒“Bingo!”;假如一次以内猜到该数,则提醒“Lucky
You!”;如若超越二回不过在N(>三)次以内(包罗第N次)猜到该数,则提示“Good
Guess!”;即使领先N次都不曾猜到,则提示“Game
Over”,并结束程序。假设在抵达N次从前,用户输入了多少个负数,也出口“Game
Over”,并结束程序。
输入格式:
输入第一行中提交三个不超过十0的正整数,分别是游戏机爆发的专断数、以及揣摸的最大次数N。最后每行给出多个用户的输入,直到出现负数截止。
出口格式:
在1行中输出每一回猜度相应的结果,直到输出猜对的结果或“Game
Over”则甘休。
输入样例:
58 4
70
50
56
58
60
-2
输出样例:
Too big
Too small
Too small
Good Guess!

Solution:

尽管从最高的一人向下找,借使这一人为壹的数多于多少个就取出那一个数,把别的数踢出,然后再取出的那一个数里面继续下一个人的一律的拍卖,小编就用递归写的,最终留下的五个数的相与值会最大。

 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
突然意识兔子们都以严刻依据伟大的化学家斐波那契提出的模子来拓展
繁衍:一对兔子从诞生后第1个月起,各类月刚初始的时候都会产下壹对小兔子。我们只要,
在漫天进度中兔子不会现出任何不测。

小 C
把兔子按出生顺序,把兔子们从 壹 开端标号,并且小 C 的兔子都以 壹 号兔子和
一 号兔子的后人。如若某两对兔子是还要出生的,那么小 C
会将父母标号更小的一对先行标 号。

即便大家把那种关联用画图下来,前3个月大致即是那般的:

美高梅开户网址 1

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

为了更密切地打听兔子们是怎么着繁衍的,小
C 找来了有的兔子,并且向您提议了 m 个 难题:她想清楚关于每两对兔子 aia_iai​ 和 bib_ibi​
,他们的方今国有祖先是何人。你能帮帮小 C
吗?

壹对兔子的祖先是那对兔子以及他们老人家(要是部分话)的先世,而近年来公共祖先是指
两对兔子所共有的祖辈中,离他们的偏离之和多年来的1对兔子。比如,5 和 7的近年公共祖 先是 二,壹 和 二 的近日集体祖先是 一,陆 和 陆 的近年国有祖先是
陆。

输入输出格式

输入格式:

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

出口格式:

出口到专业输出中。
输入一共 m 行,每行三个正整数,依次表示您对难题的答案。

输入输出样例

输入样例#1:
复制

5 
1 1 
2 3 
5 7 
7 13 
4 12

出口样例#1:
复制

1 
1 
2 
2 
4 

说明

【数据范围与约定】
子任务会付出部分测试数据的风味。即使你在缓解题目中相见了狼狈,能够尝尝只化解1部分测试数据。 种种测试点的数据规模及特点如下表:

美高梅开户网址 2

优良属性
一:保险 aia_iai​, bib_ibi​
均为某一个月出生的兔子中标号最大的一对兔子。例如,对
于前五个月,标号最大的兔子分别是 一, 二, 三, 五, 八,
一三。

十分属性
2:保障 ∣ai−bi∣≤一|a_i-b_i|\le 1∣ai​−bi​∣≤1

7-九 兔子繁衍难点(15 分)
1对兔子,从降生后第半年起各样月都生壹对兔子。小兔子长到第伍个月后各样月又生1对兔子。要是兔子都不死,请问第1个月出生的1对兔子,至少须求繁衍到第多少个月时兔子总数才方可高达N对?
输入格式:
输入在一行中提交3个不超过一千0的正整数N。
输出格式:
在一行中输出兔子总数高达N最少供给的月数。
输入样例:
30
输出样例:
9

Solution:

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

解法:斐波拉契

思路:诸多少人直接诶想到了lca吧,但对那道题分明是不得以的。我们思考列出几项斐波拉契数来查找规律:[1]
[2] [3] [4 5] [6 7 8] [9 10 11 12
13]…我们着眼一下上述的几项,同1个[]中的是同时出生的,大家发现第i个月出生的兔子恰巧正是它上个月事先的兔子所生,而且对于多少个数x,它的从来阿爹就是x-fi,所以大家能够对此每便询问(a,b),将a、b中较大的数先往前跳到它的老爹,然后比较此时a和b的尺寸是或不是同样,若想同则输出该数,若不一样则重复上述手续继续往前跳。说的近乎不太知道,可是大家友好列一列应该很简单见到。举个例子:假诺笔者要明白8和11的近年公共祖先是哪个人,我们先对1一往前跳,即11-八拿走了3,此时可比叁和八的分寸,不对等,so用较大的数八继续往前跳,即八-5=叁,此时三和3相等了,所以三正是11和八的近年集体祖先。

注意:难题中数量较大到了10的十一回方,所以要开long
long,其它必须得预处理出斐波拉契中的前60项(因为数量唯有十的11次方,斐波拉契的第陆0项刚好超越了数据范围),然后正是读入优化(数据有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
[
标题描述]
当今有3个圆形,
顺时针标号分别从 0 到 n-一,
每便等概率顺时针走一步照旧逆时针走一步,
即只要您在 i
号点,你有 四分之二 概率走到((i-一)mod n)号点,二分一 可能率走到((i+一)mod
n)号点。问
从 0
号点走到 x 号点的冀望步数。
[
输入]
先是行蕴涵一个整数
T,表示数据的组数。
接下去有
T 行,每行李包裹罗七个整数 n, x。
T<=10,
0<=x<n<=300;
[
输出]
对此每组数据,输出一行,包涵3个贰位小数表示答案。
[
样例输入]
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 分)
皮球从某给定中度自由落下,触地后反弹到原中度的十一分之5,再落下,再反弹,……,如此反复。问皮球在第n次落地时,在空中1共经过多少路程?第n次反弹的冲天是不怎么?
输入格式:
输入在一行中提交五个非负整数,分别是皮球的始发高度和n,均在长整型范围内。
出口格式:
在一行中相继输出皮球第n次落地时在空中经过的离开、以及第n次反弹的中度,其间以两个空格分隔,保留一个人小数。题目保障总计结果不超越双精度范围。
输入样例:
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);
    }


}

 8、Infiniti种类

 

Infiniti种类
infinit
.pas/c/cpp
1s /
128M
[ [
难题讲述] ]
大家按以下办法爆发连串:
1、
起始时种类是: “壹” ;
贰、
每一次生成把类别中的 “1” 变成 “10” ,”0″ 变成 “一”。
因此极其次生成,大家获取系列”10110101101十拾1101…”。
累计有 Q
个询问,每回询问为:在间隔 A 和 B 之间有稍许个 一。
请写2个先后回答
Q 个询问。
[ [
输入 数据 ]
率先作为3个平头
Q,前面有 Q 行,每行五个数用空格隔断的平头 a, b。
[ [
输出 数据 ]
共 Q
行,每行2个应对
[ [
输入 样例] ]
1
2
8
[ [
输出样例] ]
4
[ [
数据 范围] ]
1 <= Q
<= 5000
1 <= a
<= b < 2^63

Solution:

 

大家先看看种类变化规律,
S一 = “一”, S2 = “十”, S三 = “拾一”, S四 = “拾1十”, S5 = “10110十1”,
等等. Si
是 S(i+1)的前缀。
队列 Si
是由连串 S(i-一) 和 S(i-贰), 连接而成的。
即 Si =
Si-壹 + Si-二 (实际上上是 Fibonacci 数列)。
找到规律未来,我们能够可以用递归的方法求出从从职分一 到岗位 X 之间有着的 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 1 , x 二 , … x N
排成一排,大家得以从左侧或右侧去掉几次三番的 i 个数
(只好从两边删除数),一<=i<=n,剩下
N-i 个数,再把剩余的数按上述操作处理,直到所
一些数都被去除停止。
老是操作都有三个操作价值,
比近年来后要去除从 i 地点到 k 地方上的具备的数。 操作价值为
|x i – x
k
|*(k-i+一),假如只去掉两个数,操作价值为那些数的值。如何操作可以博得最大
值,求操作的最大价值。
[ [
输入数据] ]
率先行事一个正整数
N,第3行有 N 个用空格隔开分离的 N 个差别的正整数。
[
输出数据] ]
富含3个正整数,为操作的最大值
[ [
样例] ]
re move
.in
6
54 29 196
21 133 118
re move.
. out
768
[ [
数据范围] ]
3<=N<=100
N
个操作数为 壹..一千 之间的平头。
[ [
样例表明] ]
由此 二回操作能够拿走最大值,第一回去掉后面 3 个数 5四、2九、1玖6,操作价值为
4二陆。第
3次操作是在余下的八个数(21
13三 118)中去掉最后二个数 118,操作价值为 11八。第叁
次操作去掉多余的
贰 个数 21 和 13三 ,操作价值为 2贰四。操作总价值为 4二陆+11捌+224=768。

Solution:

那是一在那之中坚的动态规划难点。
我们用
F[i][j]表示按规则消去数列 a[i..j]获得的的最大值;
除去第 i
个数获得的最大值为 a[i];
删除
a[i..j]取得的最大值为:2次性删除数列
a[i..j]赢得的值是|a[i]-a[j]|*(j-i+1)
依然是先删除
a[i..k] 再删除 a[k+1..j], k 在 i 到 j-一 之间,获得的值是
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],…,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玖*9876543二一=?的人不会让你那么让投机那
么轻松,它说:
“N 和 K 都或者一点都一点都不小。 ”
只是小明也难于了,所以它就找到了您,想请你帮她化解这几个难题。
【输入描述】
输入文件:comb.in
第 一行:贰个正整数 t,表示数据的组数。

2~二+t-一 行:多个非负整数 N 和 K。 (保险 k<=n)
【输出描述】
出口文件:comb.out
对此每1组输入,如果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、偶数

【标题叙述】
山山有2个长短为
N 的行列。当种类中存在相邻的八个数的和为偶数的话,LGTB 就
能把它们删掉。
山山想让体系尽量短,请问能将系列减少到多少个数?
【输入格式】
第2行李包裹蕴3个数
N 代表体系初始长度。
接下去一行李包裹蕴N 个数 a1 ,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
数组可以为 壹 5 三 一 捌
【数据范围】
对于 40%
的数据,1 ≤ N ≤ 10
对于 100%
的数据,1 ≤ N ≤ 100,1 ≤ ai ≤ 30

Solution:

考虑到ai最多变成5八,假使成为更大的数还不及变成一,而且5捌之内唯有十五个素数

与此同时能够证实对于八个数a > b,变成的数A >= B

之所以最八只有十八个最大的数成为素数,其余的数都会成为一

所以平素对于前16个数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地图