区块链技术博客
www.b2bchain.cn

洛谷题单 算法1-1 模拟和高精度的讲解

这篇文章主要介绍了洛谷题单 算法1-1 模拟和高精度的讲解,通过具体代码讲解7656并且分析了洛谷题单 算法1-1 模拟和高精度的讲解的详细步骤与相关技巧,需要的朋友可以参考下

本文实例讲述了洛谷题单 算法1-1 模拟和高精度的讲解。分享给大家供大家参考文章查询地址https://www.b2bchain.cn/7656.html。具体如下:

1 乒乓球

题目背景
国际乒联现在主席沙拉拉自从上任以来就立志于推行一系列改革,以推动乒乓球运动在全球的普及。其中11分制改革引起了很大的争议,有一部分球员因为无法适应新规则只能选择退役。华华就是其中一位,他退役之后走上了乒乓球研究工作,意图弄明白11分制和21分制对选手的不同影响。在开展他的研究之前,他首先需要对他多年比赛的统计数据进行一些分析,所以需要你的帮忙。

题目描述
华华通过以下方式进行分析,首先将比赛每个球的胜负列成一张表,然后分别计算在11分制和21分制下,双方的比赛结果(截至记录末尾)。

比如现在有这么一份记录,(其中W表示华华获得一分,L表示华华对手获得一分):

WWWWWWWWWWWWWWWWWWWWWWLW

在11分制下,此时比赛的结果是华华第一局11比0获胜,第二局11比0获胜,正在进行第三局,当前比分1比1。而在21分制下,此时比赛结果是华华第一局21比0获胜,正在进行第二局,比分2比1。如果一局比赛刚开始,则此时比分为0比0。直到分差大于或者等于2,才一局结束。

你的程序就是要对于一系列比赛信息的输入(WL形式),输出正确的结果。

输入格式
每个输入文件包含若干行字符串,字符串有大写的W、L和E组成。其中E表示比赛信息结束,程序应该忽略E之后的所有内容。

输出格式
输出由两部分组成,每部分有若干行,每一行对应一局比赛的比分(按比赛信息输入顺序)。其中第一部分是11分制下的结果,第二部分是21分制下的结果,两部分之间由一个空行分隔。

输入输出样例

输入
WWWWWWWWWWWWWWWWWWWW
WWLWE

输出
11:0
11:0
1:1

21:0
2:1

思路:纯模拟,比较水,但是有两点比较坑的地方需要注意。
1 : 在n分制下,只有当场上有选手分数不低于n且两人分数差距不小于2的时候,比赛才能结束。
2:如果比赛刚开始或者上局比赛恰好结束了,那么我们一定要输出下一局的比分0:0.这里比较坑!

import java.util.ArrayList; import java.util.List; import java.util.Scanner;  public class Main {     public static long a,b,c,d;     public static List<String> ans1 =new ArrayList<>();     public static List<String> ans2 =new ArrayList<>();     public static void main(String[] args) {         Scanner sc =new Scanner(System.in);         boolean flag= false;         while (!flag) {             flag=ojbk(sc.nextLine());         }         for(String s:ans1){             System.out.println(s);         }         System.out.println();         for(String s:ans2){             System.out.println(s);         }     }     public static boolean ojbk(String str){         char[] ch = str.toCharArray();         for(char t:ch){             if(t=='W'){                 a++;                 c++;             }else if(t=='L'){                 b++;                 d++;             }else if(t=='E'){                 ans1.add(a+":"+b);                 ans2.add(c+":"+d);                 return true;             }             if((a>=11||b>=11)&&Math.abs(a-b)>=2){                 ans1.add(a+":"+b);                 a=0;                 b=0;             }             if((c>=21||d>=21)&&Math.abs(c-d)>=2){                 ans2.add(c+":"+d);                 c=0;                 d=0;             }         }         return false;     } } 

2 玩具谜题

题目描述
小南有一套可爱的玩具小人, 它们各有不同的职业。

有一天, 这些玩具小人把小南的眼镜藏了起来。 小南发现玩具小人们围成了一个圈,它们有的面朝圈内,有的面朝圈外。如下图:
洛谷题单 算法1-1 模拟和高精度

这时singer告诉小南一个谜題: “眼镜藏在我左数第3个玩具小人的右数第1个玩具小人的左数第2个玩具小人那里。 ”

小南发现, 这个谜题中玩具小人的朝向非常关键, 因为朝内和朝外的玩具小人的左右方向是相反的: 面朝圈内的玩具小人, 它的左边是顺时针方向, 右边是逆时针方向; 而面向圈外的玩具小人, 它的左边是逆时针方向, 右边是顺时针方向。

小南一边艰难地辨认着玩具小人, 一边数着:

singer朝内, 左数第3个是archerr。

archerr朝外,右数第1个是thinker。

thinker朝外, 左数第2个是write。

所以眼镜藏在writer这里!

虽然成功找回了眼镜, 但小南并没有放心。 如果下次有更多的玩具小人藏他的眼镜, 或是谜題的长度更长, 他可能就无法找到眼镜了 。 所以小南希望你写程序帮他解决类似的谜題。 这样的谜題具体可以描述为:

有 n个玩具小人围成一圈, 已知它们的职业和朝向。现在第1个玩具小人告诉小南一个包含m条指令的谜題, 其中第 z条指令形如“左数/右数s个玩具小人”。 你需要输出依次数完这些指令后,到达的玩具小人的职业。

输入格式
输入的第一行包含两个正整数 n,m,表示玩具小人的个数和指令的条数。

接下来 n 行,每行包含一个整数和一个字符串,以逆时针为顺序给出每个玩具小人的朝向和职业。其中 0 表示朝向圈内,1 表示朝向圈外。 保证不会出现其他的数。字符串长度不超过 10且仅由小写字母构成,字符串不为空,并且字符串两两不同。整数和字符串之间用一个空格隔开。

接下来 m 行,其中第 ii 行包含两个整数ai ,si,表示第 i 条指令。若 ai=0,表示向左数si
个人;若 ai=1,表示向右数si个人。 保证 ai不会出现其他的数,1≤si<n。

输出格式
输出一个字符串,表示从第一个读入的小人开始,依次数完 m 条指令后到达的小人的职业。

输入输出样例
输入
7 3
0 singer
0 reader
0 mengbier
1 thinker
1 archer
0 writer
1 mogician
0 3
1 1
0 2
输出
writer
输入
10 10
1 C
0 r
0 P
1 d
1 e
1 m
1 t
1 y
1 u
0 V
1 7
1 1
1 4
0 5
0 3
0 1
1 6
1 2
0 8
0 4
输出
y

思路:根据玩具的朝向,模拟就好了。

  import java.util.Scanner;  public class Main {     public static void main(String[] args){          Scanner sc = new Scanner(System.in);          int n = sc.nextInt();          int m = sc.nextInt();          Node[] nodes = new Node[n];          for(int i=0;i<n;i++){              nodes[i]=new Node();              nodes[i].next=sc.nextInt();              nodes[i].name=sc.next();          }          int index = 0;          for(int i=0;i<m;i++){              int t1 = sc.nextInt(); //0左 1右              int t2 = sc.nextInt(); //数t2人                  if(nodes[index].next==0){ //0圈内 1圈外                      if(t1==0){                          index = (index-t2+n)%n;                      }else{                          index = (index+t2)%n;                      }                  }else{                      if(t1==0){                          index = (index+t2)%n;                      }else{                          index = (index-t2+n)%n;                      }                  }          }          System.out.print(nodes[index]);     } } class Node{     int next;     String name;      public Node() {     }      public Node(int next, String name) {         this.next = next;         this.name = name;     }      public String toString() {         return name;     } } 

3 生活大爆炸

题目描述
石头剪刀布是常见的猜拳游戏:石头胜剪刀,剪刀胜布,布胜石头。如果两个人出拳一 样,则不分胜负。在《生活大爆炸》第二季第8集中出现了一种石头剪刀布的升级版游戏。

升级版游戏在传统的石头剪刀布游戏的基础上,增加了两个新手势:

斯波克:《星际迷航》主角之一。

蜥蜴人:《星际迷航》中的反面角色。

这五种手势的胜负关系如表一所示,表中列出的是甲对乙的游戏结果。
洛谷题单 算法1-1 模拟和高精度

现在,小 A和小 B尝试玩这种升级版的猜拳游戏。已知他们的出拳都是有周期性规律的,但周期长度不一定相等。例如:如果小A以“石头-布-石头-剪刀-蜥蜴人-斯波克”长度为 66 的周期出拳,那么他的出拳序列就是“石头-布-石头-剪刀-蜥蜴人-斯波克-石头-布-石头-剪刀-蜥蜴人-斯波克-…”,而如果小B以“剪刀-石头-布-斯波克-蜥蜴人”长度为 5 的周期出拳,那么他出拳的序列就是“剪刀-石头-布-斯波克-蜥蜴人-剪刀-石头-布-斯波克-蜥蜴人-…”

已知小 A和小 B 一共进行 N 次猜拳。每一次赢的人得 1 分,输的得 0 分;平局两人都得 0分。现请你统计 N次猜拳结束之后两人的得分。

输入格式
第一行包含三个整数:N,AN_BN,分别表示共进行 N 次猜拳、小 A出拳的周期长度,小 B 出拳的周期长度。数与数之间以一个空格分隔。第二行包含 NA个整数,表示小 A出拳的规律,第三行包含 NB个整数,表示小 B 出拳的规律。其中,0 表示“剪刀”,1 表示“石头”,2表示“布”,3 表示“蜥蜴人”,4表示“斯波克”。数与数之间以一个空格分隔。

输出格式
输出一行,包含两个整数,以一个空格分隔,分别表示小 A、小 B的得分。

输入输出样例
输入
10 5 6
0 1 2 3 4
0 3 4 2 1 0
输出
6 2
输入
9 5 5
0 1 2 3 4
1 0 3 2 4
输出
4 4、

  import java.util.Scanner;  public class Main {     public static int ans1,ans2 ;     public static int n,na,nb;     public static void main(String[] args){         Scanner sc = new Scanner(System.in);         n = sc.nextInt();         na= sc.nextInt();         nb= sc.nextInt();         int[] a = new int[na];         int[] b = new int[nb];         int index1 = 0;         int index2 = 0;         for(int i=0;i<na;i++){             a[i] = sc.nextInt();         }         for(int i=0;i<nb;i++){             b[i] = sc.nextInt();         }         for(int i=0;i<n;i++){             ok(a[index1],b[index2]);             index1 = (index1+1)%na;             index2 = (index2+1)%nb;         }         System.out.print(ans1+" "+ans2);     }     public static void ok(int x,int y){         if(x==0){             if(y==2||y==3){                 ans1++;             }else if(y==1||y==4){                 ans2++;             }         }else if(x==1){             if(y==0||y==3){                 ans1++;             }else if(y==2||y==4){                 ans2++;             }         }else if(x==2){             if(y==1||y==4){                 ans1++;             }else if(y==0||y==3){                 ans2++;             }         }else if(x==3){             if(y==2||y==4){                 ans1++;             }else if(y==0||y==1){                 ans2++;             }         }else if(x==4){             if(y==0||y==1){                 ans1++;             }else if(y==2||y==3){                 ans2++;             }         }     } } 

4 The Tamworth Two

题目描述

两只牛逃跑到了森林里。Farmer John 开始用他的专家技术追捕这两头牛。你的任务是模拟他们的行为(牛和 John)。

追击在 10×10 的平面网格内进行。一个格子可以是:一个障碍物,两头牛(它们总在一起),或者 Farmer John。两头牛和 Farmer John 可以在同一个格子内(当他们相遇时),但是他们都不能进入有障碍的格子。

一个格子可以是:

. 空地;

  • 障碍物;
    C 两头牛;
    F Farmer John。
    这里有一个地图的例子:





.F…


…C…

.
..
牛在地图里以固定的方式游荡。每分钟,它们可以向前移动或是转弯。如果前方无障碍(地图边沿也是障碍),它们会按照原来的方向前进一步。否则它们会用这一分钟顺时针转 90 度。 同时,它们不会离开地图。

Farmer John 深知牛的移动方法,他也这么移动。

每次(每分钟)Farmer John 和两头牛的移动是同时的。如果他们在移动的时候穿过对方,但是没有在同一格相遇,我们不认为他们相遇了。当他们在某分钟末在某格子相遇,那么追捕结束。

读入十行表示地图。每行都只包含 10 个字符,表示的含义和上面所说的相同。保证地图中只有一个 F 和一个 C。F 和 C 一开始不会处于同一个格子中。

计算 Farmer John 需要多少分钟来抓住他的牛,假设牛和 Farmer John 一开始的行动方向都是正北(即上)。 如果 John 和牛永远不会相遇,输出 0。

输入格式
输入共十行,每行 10 个字符,表示如上文描述的地图。

输出格式
输出一个数字,表示 John 需要多少时间才能抓住牛们。如果 John 无法抓住牛,则输出 0。

输入输出样例
输入




.F…


…C…

.
..
输出
49

思路:模拟。需要注意两点。
1:牛和人脸的朝向问题。由于只能向前走,我采用了数组取模的方式来获得前进的方向。
2:如果追不上,何时终止?如果这里不处理的话,肯定会超时。那么何时才终止模拟呢?不难想到,当牛和人同时同一朝向进入之前来过的格子,此时我们终止程序,因为进入了死循环,两者永远不能相遇。我采用专属值的方式来进行标记。即人的横坐标加人的纵坐标10+牛的横坐标100+牛的纵坐标1000+人的脸的朝向10000+牛的朝向*100000.

  import java.util.Scanner; public class Main {     public static int x1,y1,x2,y2,t1,b1,n1,n2;     public static int[] book = new int[1000005];     public static char[][] ch = new char[10][];     public static int[][] next = {{-1,0},{0,1},{1,0},{0,-1}}; //上 右 下 左     public static void main(String[] args){         Scanner sc = new Scanner(System.in);         for(int i=0;i<10;i++){             ch[i] = sc.next().toCharArray();         }         for(int i=0;i<10;i++){             for(int j=0;j<ch[i].length;j++){                 if(ch[i][j]=='F'){ //人的初始坐标                     x1 = i;                     y1 = j;                 }                 if(ch[i][j]=='C'){//牛的初始坐标                     x2 = i;                     y2 = j;                 }                 b1 = x1+y1*10+x2*100+y2*1000+(n1+1)*10000+(n2+1)*100000;                 book[b1]=1;             }         }         int tx1 = x1;         int ty1 = y1;         int tx2 = x2;         int ty2 = y2;         while(true){             if(     (tx1+next[n1][0])>=0&&(ty1+next[n1][1])>=0 &&                     (tx1+next[n1][0])<10&&(ty1+next[n1][1])<10 &&                     ch[tx1+next[n1][0]][ty1+next[n1][1]]!='*'){                 tx1 = tx1+next[n1][0];                 ty1 = ty1+next[n1][1];             }else{                 n1 = (n1+1)%4;             }             if(     (tx2+next[n2][0])>=0&&(ty2+next[n2][1])>=0                     &&(tx2+next[n2][0])<10&&(ty2+next[n2][1])<10                     &&ch[tx2+next[n2][0]][ty2+next[n2][1]]!='*'){                 tx2 = tx2+next[n2][0];                 ty2 = ty2+next[n2][1];             }else{                 n2 = (n2+1)%4;             }             t1++;             if(tx1==tx2&&ty1==ty2){                 System.out.print(t1);                 break;             }             b1 = tx1+ty1*10+tx2*100+ty2*1000+(n1+1)*10000+(n2+1)*100000;             if(book[b1]==1){                 System.out.print(0);                 break;             }             book[b1]=1;         }     } } 

5 麦森数

题目描述
形2^P -1的素数称为麦森数,这时PP一定也是个素数。但反过来不一定,即如果P是个素数,2^P -1不一定也是素数。到1998年底,人们已找到了37个麦森数。最大的一个是P=3021377,它有909526位。麦森数有许多重要应用,它与完全数密切相关。

任务:从文件中输入P(1000<P<3100000),计算2^P -1的位数和最后500位数字(用十进制高精度数表示)

输入格式
文件中只包含一个整数P(1000<P<3100000)

输出格式
第一行:十进制高精度数2^P -1的位数。

第2-11行:十进制高精度数2^P -1的最后500位数字。(每行输出50位,共输出10行,不足500位时高位补0)

不必验证2^P -1与P是否为素数。

输入输出样例
输入
1279
输出
386
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000104079321946643990819252403273640855
38615262247266704805319112350403608059673360298012
23944173232418484242161395428100779138356624832346
49081399066056773207629241295093892203457731833496
61583550472959420547689811211693677147548478866962
50138443826029173234888531116082853841658502825560
46662248318909188018470682222031405210266984354887
32958028878050869736186900714720710555703168729087

思路:2^P 的位数是p*lg2+1,而最后500位我们可以模10的500次方获得,此题考察的是高精度和快速幂,我用的java,所以高精度的题我就不仔细写了。。。

  import java.math.BigInteger; import java.util.Scanner; public class Main {     static int p;     static BigInteger bTwo = new BigInteger("2");     static BigInteger bTen   = BigInteger.TEN.pow(500);     public static void main(String[] args){        Scanner  sc = new Scanner(System.in);        p = sc.nextInt();        System.out.println((int)(p*Math.log10(2))+1);        //System.out.println();         char[] ch = powBig(bTwo).subtract(BigInteger.ONE).toString().toCharArray();         int len = ch.length;         int nn = 0;         while(len<500){             System.out.print(0);             nn++;             len++;             if(nn%50==0){                 System.out.println();             }         }         for(int i=0;i<ch.length;i++){             System.out.print(ch[i]);             nn++;             if(nn%50==0){                 System.out.println();             }         }    }    public static BigInteger powBig(BigInteger b){ //快速幂 2的p次方模10的500次方         BigInteger ans = BigInteger.ONE;         while(p>0){             if((p&1)==1){                 ans = ans.multiply(b);                 ans = ans.mod(bTen);             }             b = b.multiply(b);             b = b.mod(bTen);             p >>=1;        }         return ans;    } } 

6 最大乘积

题目描述
一个正整数一般可以分为几个互不相同的自然数的和,如 3=1+23=1+2,4=1+34=1+3,5=1+4=2+35=1+4=2+3,6=1+5=2+46=1+5=2+4。

现在你的任务是将指定的正整数 nn 分解成若干个互不相同的自然数的和,且使这些自然数的乘积最大。

输入格式
只一个正整数 nn,(3 leq n leq 100003≤n≤10000)。

输出格式
第一行是分解方案,相邻的数之间用一个空格分开,并且按由小到大的顺序。

第二行是最大的乘积。

输入输出样例
输入
10
输出
2 3 5
30
思路:用到了数论里的简单知识,一个数分成若干不相等的数,我们尽可能的把n分成更多份(都大于1)那样乘积最大。
以2004为例,由于把2004分拆成若干个互不相等的自然数的和的分法只有有限种,因而一定存在一种分法,使得这些自然数的乘积最大。

若1作因数,则显然乘积不会最大。把2004分拆成若干个互不相等的自然数的和,因数个数越多,乘积越大。为了使因数个数尽可能地多,我们把2004分成2+3…+n直到和大于等于2004。

若和比2004大1,则因数个数至少减少1个,为了使乘积最大,应去掉最小的2,并将最后一个数(最大)加上1。

若和比2004大k(k≠1),则去掉等于k的那个数,便可使乘积最大。

例如15:s=2+3+4+5+6刚好大于15,s-15=5,所以把5去掉。

又例如13:s=2+3+4+5刚好大于13,s-13=1,所以去掉2,并把5加1,即3 4 6。

 import java.math.BigInteger; import java.util.Arrays; import java.util.Scanner; public class Main {     public static void main(String[] args){       Scanner sc = new Scanner(System.in);       int n = sc.nextInt();       int[] ans = new int[10000];       int t = 2;       int s = 0;       int index = 0;       while(s<n){           s+=t;           ans[index++]=t;           t++;       }       if(s!=n) {           if(s-n>1){               int del = s - n;               ans[del - 2] = t - 1;               index--;               Arrays.sort(ans, 0, index);           }else{               index-=1;               ans[index-1]++;           }       }       BigInteger aa = new BigInteger("1");       for(int i=0;i<index;i++){           System.out.print(ans[i]+" ");           aa=aa.multiply(new BigInteger(ans[i]+""));       }       System.out.print("n"+aa);     } } 

本文地址https://www.b2bchain.cn/7656.html

赞(0) 打赏
部分文章转自网络,侵权联系删除b2bchain区块链学习技术社区 » 洛谷题单 算法1-1 模拟和高精度的讲解
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

b2b链

联系我们联系我们