澳门皇冠金沙网站-澳门皇冠844网站

热门关键词: 澳门皇冠金沙网站,澳门皇冠844网站

上海五校赛

主题素材陈诉

总纲:

Problem 1 机器人(robot.cpp/c/pas)

【标题陈述】

早苗出手了新式的Gundam模型。最新一款自然有着与往年不等的效果与利益,那正是它能够自行行走,厉害吧。

早苗的新模型能够遵照输入的指令举办运动,命令满含‘E’、‘S’、‘W’、‘N’二种,分别对应东北西南。试行有个别命令时,它会向对应方向移动叁个单位。作为新型机器人,它可以进行命令串。对于输入的下令串,每一秒它会按命令行动贰次。实行完命令串的结尾叁个限令后,会自行从头起初循环。在0时刻机遇器人位于(0,0)。求T秒后机器人钻探所在地点坐标。

【输入格式】

第1行:叁个字符串,表示早苗输入的通令串,保险最少有1个指令

第2行:二个正整数T

【输出格式】

2个整数,表示T秒时,机器人的坐标。

【样例输入】

NSWWNSNEEWN

12

【样例输出】

-1 3

【数据范围】

对此百分之七十五的数额 T<=500,000 且命令串长度<=5,000

对此百分之百的数量 T<=2,000,000,000 且命令串长度<=5,000

 

【注意】

往西移动,坐标改换改造为(X 1,Y);

向怀化移,坐标退换改动为(X,Y-1);

向南移动,坐标改换改造为(X-1,Y);

往西位移,坐标改动退换为(X,Y 1);

/*
    求出第一次执行完所有命令后的位置,这就是执行完一次命令的相对位移,在求他的时候顺便记录下走每一步的相对位移,以后就可以直接用了
*/
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,t,x,y;
char s[5010];
struct node{
    int x,y;
}pos[5010];//pos[i]表示走i步到达的地点 
int main(){
    freopen("robot.in","r",stdin);
    freopen("robot.out","w",stdout);
    scanf("%s",s 1);scanf("%d",&t);
    n=strlen(s 1);
    for(int i=1;i<=n;i  ){
        if(s[i]=='E')pos[i].x=pos[i-1].x 1,pos[i].y=pos[i-1].y;
        if(s[i]=='S')pos[i].x=pos[i-1].x,pos[i].y=pos[i-1].y-1;
        if(s[i]=='W')pos[i].x=pos[i-1].x-1,pos[i].y=pos[i-1].y;
        if(s[i]=='N')pos[i].x=pos[i-1].x,pos[i].y=pos[i-1].y 1;
    }
    int bei=t/n,yu=t%n;
    x =pos[n].x*bei;y =pos[n].y*bei;
    x =pos[yu].x;y =pos[yu].y;
    printf("%d %d",x,y);
}

 

小Y在探讨数字的时候,开采了一个巧妙的等式方程图片 1,他屈指算了弹指间有众多正整数x知足那个等式,举个例子1和2,未来难点来了,他想清楚从小到大第N个知足那么些等式的正整数,请你用程序帮他企图一下。

1.筛法求素数

Problem 2 数列(seq.cpp/c/pas)

【标题汇报】

a[1]=a[2]=a[3]=1

a[x]=a[x-3] a[x-1]  (x>3)

求a数列的第n项对一千000007(10^9 7)取余的值。

【输入格式】

先是行多个整数T,表示精通个数。

以下T行,每行三个正整数n。

【输出格式】

每行输出多个非负整数表示答案。

【样例输入】

3

6

8

10

【样例输出】

4

9

19

【数据范围】

对于30%的数据 n<=100;

对于60%的数据 n<=2*10^7;

对于100%的数据 T<=100,n<=2*10^9;

做这么些题让自个儿当了一回嘴巴选手

一见倾心开采,它和斐波那契数列的递推式有几分相似

于是想到矩阵连忙幂(有何人首先眼看见那么些题的时候暴力找规律了。。)

矩阵怎么推的?

先看看斐波那契数列的矩阵是怎么推得

f[i]=1*f[i-1] 1*f[i-2]

f[i-1]=1*f[i-1] 0*f[i-2]

故而矩阵就是

1 1 

1 0

也就可以写成

图片 2

图片 3

之所以大家一致来推一下这几个题的矩阵

f[i]=1*f[i-1] 0*f[i-2] 1*f[i-3]

f[i-1]=1*f[i-1] 0*f[i-2] 0*f[i-3]

f[i-2]=0*f[i-1] 1*f[i-2] 0*f[i-3]

矩阵为

1 0 1

1 0 0

0 1 0

剩余的同理

下一场便是矩阵急迅幂的代码难点了

黄学长代码和自己想的不是完全同样

本次照着多打两回,后一次自身写

 

#include<iostream>
#include<cstdio>
#include<cstring>
#define mod 1000000007
using namespace std;
typedef long long matrix[3][3];
matrix stan={{0,0,1},{1,0,0},{0,1,1}},tmp;
int t,n;
inline void mul(matrix a,matrix b,matrix c){
    memset(tmp,0,sizeof(tmp));
    for(int k=0;k<3;k  )
        for(int i=0;i<3;i  )
            for(int j=0;j<3;j  )
                tmp[i][j]=(tmp[i][j] a[i][k]*b[k][j]);
    for(int i=0;i<3;i  )for(int j=0;j<3;j  )c[i][j]=tmp[i][j]%mod;
}
int main(){
    freopen("Cola.txt","r",stdin);
    /*freopen("seq.in","r",stdin);
    freopen("seq.out","w",stdout);*/
    scanf("%d",&t);
    for(int i=1;i<=t;i  ){
        scanf("%d",&n);
        matrix a={{1,0,0},{0,1,0},{0,0,1}},b;
        memcpy(b,stan,sizeof(b));
        n-=3;
        while(n){
            if(n&1)
            mul(a,b,a);
            mul(b,b,b);
            n>>=1;
        }
        int ans=(a[2][0] a[2][1] a[2][2])%mod;
        printf("%dn",ans);
    }
}

 

 

 

 

(图片 4意味着按位异或运算)

2.欧几Reade算法

Problem 3 虫洞(holes.cpp/c/pas)

【标题陈诉】

N个虫洞,M条单向跃迁路线。从二个虫洞沿跃迁路径到另二个虫洞要求成本一定量的燃料和1单位时间。虫洞有白洞和黑洞之分。设一条跃迁路线两端的虫洞品质差为delta。

1.从白洞跃迁到黑洞,消耗的燃料值收缩delta,若该条路线消耗的燃料值变为负数的话,取为0。

2.从黑洞跃迁到白洞,消耗的燃料值增添delta。

3.路径两端均为黑洞或白洞,消耗的燃料值不扭转。

用作压轴题,自然不会是如此简约的最短路难题,所以每过1单位时间黑洞变为白洞,白洞变为黑洞。在航空进度中,能够挑选在多个虫洞停留1个单位时间,如若当前为白洞,则不消耗燃料,否则消耗s[i]的燃料。以往请你求出从虫洞1到N最少的燃料消耗,保险一定存在1到N的门路。

【输入格式】

第1行:2个正整数N,M

第2行:N个整数,第i个为0表示虫洞i初始时为白洞,1代表黑洞。

第3行:N个整数,第i个数表示虫洞i的性能w[i]。

第4行:N个整数,第i个数表示在虫洞i停留消耗的燃料s[i]。

第5..M 4行:每行3个整数,u,v,k,表示在并未有影响的图景下,从虫洞u到虫洞v须要成本燃料k。

【输出格式】

贰个整数,表示最少的燃料消耗。

【样例输入】

4 5

1 0 1 0

10 10 100 10

5 20 15 10

1 2 30

2 3 40

1 3 20

1 4 200

3 4 200

【样例输出】

130

【数据范围】

对于30%的数据: 1<=N<=100,1<=M<=500

对于60%的数据: 1<=N<=1000,1<=M<=5000

对于100%的数据: 1<=N<=5000,1<=M<=30000

                  在那之中五分二的数据为1<=N<=三千的链

                  1<=u,v<=N, 1<=k,w[i],s[i]<=200

【样例表达】

按照1->3->4的路线。

输入描述

3.扩展欧几Reade

第一行是多少个正整数图片 5),表示查询次数。

4.最小公倍数

随之有T行,每行有三个正整数图片 6),表示小Y的查询。

5.斐波那契

出口描述

6.快速幂

对于每一个查询N,输出第N个满足题中等式的正整数,并换行。

7.独一讲授定理

[示例1]

8.中夏族民共和国剩余定理

输入

412310

9.欧拉函数

输出

12418

 

思路:

第一大家可以打表,在数码小的场合下找规律:

在1~100之间寻找满足规律的数,并转成二进制


第四个数 1 1 // 二进制1位的个数为1
第4个数 2 10 // 二进制2位的个数为1
第4个数 4 100 // 二进制3位的个数为2
第4个数 5 101
第5个数 8 1000// 二进制4位的个数为3
第6个数 9 1001
第7个数 10 1010
第8个数 16 一千0 // 二进制5位的个数为5
第9个数 17 10001
第10个数 18 10010
第11个数 20 10100
第12个数 21 10101
第11个数 32 100000 // 二进制6位的个数为8
第14个数 33 100001
第15个数 34 100010
第16个数 36 100100
第17个数 37 100101
第18个数 40 101000
第19个数 41 101001
第20个数 42 101010
第22个数 64 一千000 // 二进制7位的个数为13
第22个数 65 1000001
第23个数 66 1000010
第24个数 68 1000100
第25个数 69 1000101
第26个数 72 1001000
第27个数 73 1001001
第28个数 74 1001010
第29个数 80 1010000
第30个数 81 1010001
第31个数 82 1010010
第32个数 84 1010100
第33个数 85 1010101


结果大家开掘答案在二进制下其位数是满意斐波这契规律的

例:当N等于70时,答案的二进制为:100一千10

70-1-1-1-2-3-5-8-13-21=15

可见1 1 1 2 3 5 8 13 21=55,即9位二进制(第53个数对应一千00000)

15-1-1-1-2-3-8=0

可见1 1 1 2 3 5 8=15,即6位二进制(第拾几个数对应100010)

相加可得100一千10,转变为十进制即为290

所以得把给定的n拆成多少个斐波那契数的和,并标志一下老是用到第多少个斐波那契数,每一遍num加上1<<就可以。

得呱呱叫学学左移运算符啦!!!!

#include<bits/stdc  .h> using namespace std;int main(){    long long a[65],num,n,d;    int t,i;         a[0]=a[1]=a[2]=1;    for (i=3;i<60;i  )        a[i]=a[i-1] a[i-2];         cin>>t;    while(t--)    {        cin>>n;        num=0;        while        {            i=0;            while(n>=a[i])            {                n-=a[i];                i  ;             }            d=1;            num =(d<<(i-1));        }        cout<<num<<endl;    }    return 0;}

1.筛法求素数:

用筛法求素数的基本思维是:把从1初始的、某一限量内的正整数从小到汉朝序排列, 1不是素数,首先把它筛掉。剩下的数中采用最小的数是素数,然后去掉它的翻番。依次类推,直到筛至n截止。

瞩目:最小的素数为2,所以筛时应留神从2起首

进度比方:

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

1不是素数,去掉。剩下的数中2微细,是素数,去掉2的翻番,余下的数是:

3 5 7 9 11 13 15 17 19 21 23 25 27 29

剩余的数中3小小,是素数,去掉3的倍数,如此下去直到全部的数都被筛完,求出的素数为:

2 3 5 7 11 13 17 19 23 29

代码:

 1 #include<iostream>
 3 #include<cstdio>
 5 #include<cmath>
 7 using namespace std;
 9 int vis[1000];
11 int main()
13 {
15     int n;
17     cin>>n;
19     for(int i=2;i<=sqrt(n) 1;i  )
21      {
23         if(vis[i]==0)
25          {
27             for(int j=i*2;j<=n;j =i)//从i*2开始筛,i--2*i由i之前筛去
29              {
31                 vis[j]=1;
33               }
35          }
37      }
39      for(int i=2;i<=n;i  ) 
41       {
43         if(vis[i]==0)
45          { 
47             cout<<i<<" "; 
49           }
51       } 
53 }

 

1453 计算素数个数 2

光阴限制: 1 s

空中范围: 25四千 KB

主题材料等第 : 白银 Gold

难题陈诉 Description

判断[a,b]中素数的个数

输入描述 Input Description

输入共1行,a,b两数

出口描述 Output Description

出口共1行,输出素数的个数

样例输入 Sample Input

3 5

样例输出 Sample Output

2

数据范围及提示 Data Size & Hint

对于100%的数据,a,b≤5000,000

 

 1 #include<iostream>
 2  #include<cstdio>
 3  #include<cmath>
 4   using namespace std;
 5   const int N=5000000;
 6   int vis[N];
 7   int main()
 8   {
 9       int l,r;
10      cin>>l>>r;
11      vis[0]=1;
12      vis[1]=1;
13      for(int i=2;i<=sqrt(r) 1;i  )
14       {
15           if(vis[i]==0)
16            {
17                for(int j=i*2;j<=r;j =i)
18                 {
19                     vis[j]=1;
20                  }
21            }
22       }
23       int ans=0;
24       for(int i=l;i<=r;i  )
25        {
26            if(vis[i]==0)
27             {
28                 ans  ;
29             }
30        }
31        cout<<ans;
32  }

 

——————————————————————————————————

——————————————————————————————————

2.欧几Reade辗转相除求最大协议数:

gcd函数的为主质量:

gcd(a,b)=gcd(b,a)=gcd(-a,b)=gcd(|a|,|b|)

折腾相除法比方:

若a<b,则a/b=0(余a);

求(319,377):

∵ 319÷377=0(余319)

∴(319,377)=(377,319);

∵ 377÷319=1(余58)

∴(377,319)=(319,58);

本文由澳门皇冠金沙网站发布于编辑程序,转载请注明出处:上海五校赛