当前位置：网站首页>Simple questions peek into mathematics

Simple questions peek into mathematics

2022-08-09 23:11:00 【51CTO】

51 nod It's a good learning site,Not just algorithmic grading,And you can look at other people's excellent code（You can view it after that）.Some of the next questions come from there.

51 nod 1413 Power binary（Simple numbers game·贪心）

题目： http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1413

一个十进制整数被叫做Power binary,当他的十进制表示的时候只由0或1组成.例如0,1,101,110011都是Power binary而2,12,900不是.

当给定一个n的时候,计算一下最少要多少个Power binary相加才能得到n.

Input

       
       单组测试数据.
       
第一行给出一个整数n (1
       
       <
       
       =
       
       n
       
       <=1,000,000)
      
1.
2.

Output

       
       输出答案占一行.
      
1.

Input示例

Output示例

分析：简单的讲,The power binary is just made up0和1组成的十进制数.A bit greedy：than pitch153=111+11*2+10*2;135=111+11*2+1*2

       
       import 
       
       java.
       
       util.
       
       *;
       
       public 
       
       class 
       
       Main {
       
       public 
       
       static 
       
       void 
       
       main(
       
       String[] 
       
       args) {
       
       Scanner 
       
       sc
       
       =
       
       new 
       
       Scanner(
       
       System.
       
       in);
       
       String 
       
       str;
       
       int [] 
       
       m
       
       =
       
       new 
       
       int [
       
       7];
       
       while(
       
       sc.
       
       hasNext()){
       
       str
       
       =
       
       sc.
       
       next();
       
       Arrays.
       
       fill(
       
       m,
       
       0);
       
       int 
       
       length
       
       =
       
       str.
       
       length();
       
       for(
       
       int 
       
       i
       
       =
       
       0;
       
       i
       
       <
       
       length;
       
       i
       
       ++){
       
       m[
       
       i]
       
       =
       
       str.
       
       charAt(
       
       i)
       
       -
       
       48;
       
      }
       
       int 
       
       ans
       
       =
       
       0;
       
       for(
       
       int 
       
       i
       
       =
       
       0;
       
       i
       
       <
       
       length;
       
       i
       
       ++){
       
       if(
       
       m[
       
       i]
       
       >
       
       0){
       
       ans
       
       +=
       
       m[
       
       i];
       
       for(
       
       int 
       
       j
       
       =
       
       i
       
       +
       
       1;
       
       j
       
       <
       
       length;
       
       j
       
       ++){
       
       m[
       
       j]
       
       -=
       
       m[
       
       i];
       
           }
       
       }
       
      }
       
       System.
       
       out.
       
       println(
       
       ans);
       
  }
       
 }
       
}
      
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.

51nod 1381 硬币游戏（简单概率）

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1381

有一个简单但是很有趣的游戏.在这个游戏中有一个硬币还有一张桌子,这张桌子上有很多平行线（如下图所示）.两条相邻平行线之间的距离是1,The radius of the coin is R,然后我们来抛硬币到桌子上,抛下之后硬币有时候会和一些直线相交（相切的情况也算是相交）,有时候不会.

Please do the calculations after a coin toss,该硬币和直线相交数目的期望.

Simple questions peek into mathematics_i++

Input

       
       第一行给出一个整数T,表示有T组数据(1
       
       <
       
       =
       
       T
       
       <=10000).
       
第2行到T+1,Give an integer per lineR.(0
       
       < 
       
       R 
       
       <= 10,000,000,000)
      
1.
2.

Output

       
       对于每一个数据,在一行中输出答案的整数部分即可.
      
1.

Input示例

Output示例

分析：因为r是一个整数,So there are a lot of questions,The number of intersections of circles and lines is 2r+1（相切）和2r两种结果,The latter has a line segment probability of unit length,The former has only one point probability.所以答案就是2r.

The next problem was encountered in the game：
Rectangle

frog has a piece of paper divided into n rows and m columns. Today, she would like to draw a rectangle whose perimeter is not greater than k.

Simple questions peek into mathematics_整除_02

There are 8(out of 9) ways when n=m=2,k=6
Find the number of ways of drawing.

Input

The input consists of multiple tests. For each test:

The first line contains

integer

n,m,k

(1≤n,m≤5⋅104,0≤k≤109).

Output

For each test, write

integer which denotes the number of ways of drawing.

Sample Input

       
       2 2 6
       
1 0
       
50000 1000000000
      




Sample Output

       
       8
       
0
       
1562562500625000000
       
分析：
      
1.
2.
3.
4.

Continue to imagine：当i=3呢,那么(m-1+1)-->(m-3+1);所以设q=min(n,k/2-1),j=k/2-i.

Simple questions peek into mathematics_i++_03

51nod 1393 0和1相等串

http://www.51nod.com/onlineJudge/questionCode.html#problemId=1393¬iceId=23885

给定一个0-1串,Please find a substring that is as long as possible,其中包含的0与1的个数相等.

Input

       
       一个字符串,只包含01,长度不超过1000000.
      
1.

Output

       
       一行一个整数,最长的0与1The length of an equal number of substrings.
      
1.

Input示例

Output示例

分析：To make the stats change,将所有的0变成-1,一次遍历.观察规律：

1 0 0 0 1

0 1 0 -1 -2 -1

Calculated data reflect changing trends. 寻找sum[i]=sum[j] Length is the maximumj-i.

       
       #include <iostream> 
       
       //Be sure to let the calculated data change
       
       #include <cstdio>
       
       #include <cstring>
       
       #include <map>
       
       using 
       
       namespace 
       
       std;
       
       const 
       
       int 
       
       maxn
       
       =
       
       1e6
       
       +
       
       5;
       
       char 
       
       str[
       
       maxn];
       
       int 
       
       p[
       
       maxn];
       
       int 
       
       main()
       
{
       
       //freopen("cin.txt","r",stdin);
       
       while(
       
       ~scanf(
       
       "%s",
       
       str
       
       +
       
       1)){
       
       int 
       
       length
       
       =
       
       strlen(
       
       str
       
       +
       
       1);
       
       int 
       
       ans
       
       =
       
       0;
       
       memset(
       
       p,
       
       0,
       
       sizeof(
       
       p));
       
       map
       
       <
       
       int,
       
       int
       
       > 
       
       mp; 
       
       //默认0
       
       for(
       
       int 
       
       i
       
       =
       
       1;
       
       i
       
       <=
       
       length;
       
       i
       
       ++){
       
       if(
       
       str[
       
       i]
       
       ==
       
       '1') 
       
       p[
       
       i]
       
       =
       
       p[
       
       i
       
       -
       
       1]
       
       +
       
       1;
       
       else 
       
       p[
       
       i]
       
       =
       
       p[
       
       i
       
       -
       
       1]
       
       -
       
       1;
       
       if(
       
       mp[
       
       p[
       
       i]]
       
       ==
       
       0
       
       &&
       
       p[
       
       i]
       
       !=
       
       0)
       
       mp[
       
       p[
       
       i]]
       
       =
       
       i;
       
       if(
       
       i
       
       !=
       
       1){
       
       ans
       
       =
       
       max(
       
       ans,
       
       i
       
       -
       
       mp[
       
       p[
       
       i]]);
       
       //cout<<i<<" "<<p[i]<<" "<<mp[p[i]]<<endl;
       
            }
       
        }
       
       printf(
       
       "%d\n",
       
       ans);
       
    }
       
       return 
       
       0;
       
}
      
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.

学习了别人的代码（来自“Attitude determines destiny”）：Lengthens the width of the array,Similar to the hashing idea above.It can be seen that there is no needSTL确实快了好多.400ms VS 31ms

       
       #define LEN 1000001
       
       int 
       
       v[
       
       LEN
       
       *
       
       2];
       
       char 
       
       s[
       
       LEN];
       
       int 
       
       main()
       
{
       
       int 
       
       len,
       
       dis
       
       =
       
       0,
       
       ret
       
       =
       
       0;
       
       scanf(
       
       "%s",
       
       s);
       
       len
       
       =
       
       strlen(
       
       s);
       
       memset(
       
       v,
       
       -
       
       1,
       
       sizeof(
       
       v));
       
       for(
       
       int 
       
       i
       
       =
       
       0;
       
       i
       
       <
       
       len;
       
       i
       
       ++)
       
    {
       
       if(
       
       s[
       
       i]
       
       ==
       
       '1')
       
       dis
       
       ++;
       
       else
       
       dis
       
       --;
       
       if(
       
       v[
       
       dis
       
       +
       
       LEN]
       
       ==-
       
       1
       
       &&
       
       dis
       
       !=
       
       0)
       
        {
       
       v[
       
       dis
       
       +
       
       LEN]
       
       =
       
       i;
       
        }
       
       else
       
        {
       
       if(
       
       ret
       
       <
       
       i
       
       -
       
       v[
       
       dis
       
       +
       
       LEN])
       
       ret
       
       =
       
       i
       
       -
       
       v[
       
       dis
       
       +
       
       LEN];
       
        }
       
    }
       
       printf(
       
       "%d\n",
       
       ret);
       
}
      
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.

51nod 1417 天堂里的游戏（博弈&数学推导）

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1417

······

正当Noder惊魂未定的时候,走来一个美女,要求和他一起玩个数学游戏.美女提议：“让我们各自亮出硬币的一面,或正或反.如果我们都是正面,那么我给你A元,如果我们都是反面,我给你B元（A + B为偶数）.剩下的情况你给我（A + B） / 2元就可以了.

Noder知道这个游戏他多半要输,可他并不在乎,他只想让自己输的慢一点.

那么你来帮美女计算一下,她选择出正面的概率应该是多少（以最简分数形式输出）？

当Noder输光了钱后从草地上醒来,吉普赛姑娘已经不见了,只留下了这样一张塔罗牌,上面印有那个美女的照片.

Simple questions peek into mathematics_整除_04

关于样例的解释：

美 Female took(3/8,5/8)这个方案,不论Noder采用什么方案,都是不能改变局面的.如果全部出正面,每次的期望收益是 (3+3+3-2-2-2-2-2)/8=-1/8元;如果全部出反面,每次的期望收益也是(-2-2-2+1+1+1+1+1)/8=-1/8元.而任 What strategy is nothing more than a linear combination of the above two strategies,所以期望还是-1/8元.

Input

       
       第1行：一个数T,表示后面用作输入测试的数的数量（1 
       
       <
       
       = 
       
       T 
       
       <= 20).
       
第2 - T + 1行：每行2个数A, B中间用空格分隔.(1 
       
       <
       
       = 
       
       A, 
       
       B 
       
       <= 10^9,且A + B为偶数).
      
1.
2.

Output

       
       输出共T行,对应美女选择正面的概率,以最简分数形式输出,具体请参看输出样例.
      
1.

Input示例

Output示例

分析：

       
       Based on sample analysis,The result should be the same for all selected heads and tails,In the end, women must win.Then let the probability that a woman chooses a head is x,正面的A元-->a,反面的B元-->b,
       
There is such an equation：
      
1.
2.

Simple questions peek into mathematics_html_05

Simple questions peek into mathematics_i++_06

Simple questions peek into mathematics_整除_07

       
       import 
       
       java.
       
       util.
       
       *;
       
       public 
       
       class 
       
       Main {
       
       static 
       
       long 
       
       gcd(
       
       long 
       
       a,
       
       long 
       
       b){
       
       return 
       
       b
       
       >
       
       0
       
       ?
       
       gcd(
       
       b,
       
       a
       
       %
       
       b):
       
       a;
       
    }
       
       public 
       
       static 
       
       void 
       
       main(
       
       String[] 
       
       args) {
       
       Scanner 
       
       sc
       
       =
       
       new 
       
       Scanner (
       
       System.
       
       in);
       
       long 
       
       t
       
       =
       
       sc.
       
       nextInt(),
       
       a,
       
       b;
       
       for(
       
       int 
       
       k
       
       =
       
       0;
       
       k
       
       <
       
       t;
       
       k
       
       ++){
       
       a
       
       =
       
       sc.
       
       nextInt();
       
       b
       
       =
       
       sc.
       
       nextInt();
       
       long 
       
       q1
       
       =
       
       a
       
       +
       
       3
       
       *
       
       b;
       
       long 
       
       q2
       
       =
       
       4
       
       *(
       
       a
       
       +
       
       b);
       
       long 
       
       r
       
       =
       
       gcd(
       
       q1,
       
       q2);
       
       //System.out.println(q1+" "+q2+" "+r);
       
       q1
       
       =
       
       q1
       
       /
       
       r;
       
       q2
       
       =
       
       q2
       
       /
       
       r;
       
       System.
       
       out.
       
       println(
       
       q1
       
       +
       
       "/"
       
       +
       
       q2);
       
        }
       
    }
       
}
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.

51nod 1433 0和5（整除的规律）

题目： http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1433

小K手中有n张牌,每张牌上有一个一位数的数,这个字数不是0就是5.小K从这些牌在抽出任意张（不能抽0张）,排成一行这样就组成了一个数.使得这个数尽可能大,而且可以被90整除.

注意：

1.This number has no leading0,

2.小KNot all cards need to be used.

Input

       
       Each test data entry total2行.
       
第一行给出一个n,表示n张牌.(1
       
       <
       
       =
       
       n
       
       <=1000)
       
第二行给出n个整数a[0],a[1],a[2],…,a[n-1] (a[i]是0或5 ) 表示牌上的数字.
      
1.
2.
3.

Output

       
       共一行,Indicates that the cards made up of the given cards can be used90The largest number that is divisible,如果没有答案则输出”-1”（没有引号）
      
1.

Input示例

Output示例

分析：2k,3k,5kDivisible sum of numbers2,3,5Some connections,所有被2Divisible numbers are all even numbers,那么能被2The numbers that are divisible by multiples of are also even,即m%2=0,m是偶数; n%(2k)=0,n也是偶数;m%3=0,m各位上的数字之和是3的倍数,能被9The sum of the digits of the digits of the divisible digits is also the same9的倍数;能被5Divisible numbers are either at the end0要么是5,能被10Integer must be at the end of the digit0.

       
       import 
       
       java.
       
       util.
       
       *; 
       
       public 
       
       class 
       
       Main {
       
       static 
       
       int 
       
       min(
       
       int 
       
       a,
       
       int 
       
       b){  
       
       return 
       
       a
       
       <
       
       b
       
       ?
       
       a:
       
       b; }
       
       public 
       
       static 
       
       void 
       
       main(
       
       String[] 
       
       args) {
       
       Scanner 
       
       sc
       
       =
       
       new 
       
       Scanner (
       
       System.
       
       in);
       
       int 
       
       n,
       
       a,
       
       five,
       
       zero;
       
       while(
       
       sc.
       
       hasNext()){
       
       n
       
       =
       
       sc.
       
       nextInt();
       
       five
       
       =
       
       0;
       
       for(
       
       int 
       
       i
       
       =
       
       0;
       
       i
       
       <
       
       n;
       
       i
       
       ++){
       
       a
       
       =
       
       sc.
       
       nextInt();
       
       if(
       
       a
       
       ==
       
       5) 
       
       five
       
       ++; 
       
         }
       
       zero
       
       =
       
       n
       
       -
       
       five;
       
       int 
       
       k
       
       =
       
       five
       
       /
       
       9;
       
       k
       
       =
       
       min(
       
       k,
       
       zero);
       
       if(
       
       k
       
       >
       
       0){
       
       for(
       
       int 
       
       i
       
       =
       
       0;
       
       i
       
       <
       
       k;
       
       i
       
       ++){
       
       for(
       
       int 
       
       j
       
       =
       
       0;
       
       j
       
       <
       
       9;
       
       j
       
       ++) 
       
       System.
       
       out.
       
       printf(
       
       "5");
       
                }
       
       //for(int i=0;i<k;i++) 
       
       for(
       
       int 
       
       i
       
       =
       
       0;
       
       i
       
       <
       
       zero;
       
       i
       
       ++) 
       
       System.
       
       out.
       
       printf(
       
       "0");
       
       System.
       
       out.
       
       println();
       
         }
       
       else {
       
       if(
       
       zero
       
       ==
       
       0){  
       
       System.
       
       out.
       
       println(
       
       -
       
       1); 
       
       continue; }
       
       System.
       
       out.
       
       println(
       
       0);
       
         }
       
        }
       
 }
       
}
      
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.
31.