新普金娱乐网址


数据时期的监察与殖民

一般说来难点总括 一

bzoj1411: [ZJOI二零零六]硬币游戏

  • 二月 25, 2019
  • 数学
  • 没有评论

 5.1 二进制插入

1411: [ZJOI2009]硬币游戏

Time Limit: 10 Sec  Memory
Limit: 162 MB
Submit: 965  Solved: 420
[Submit][Status][Discuss]

有五个三十几人整数n和m,请编写算法将m的二进制数位插入到n的二进制的第j到第i位,个中二进制的位数从没有数到高位且以0开首。

Description

Orez很喜爱玩游戏,他近日注解了一款硬币游戏。他在桌子的边缘上划分出2*n个地方并按顺时针把它们标号为1,2,……,2n,然后把n个硬币放在标号为奇数的职位上。接下来每回按如下操作:在自由多少个硬币之间放上3个硬币,然后将原本的硬币拿走;所放硬币的正面与反面面由它两边的多少个硬币决定,若八个硬币均为正直朝上或反面朝上,则所放硬币为正面朝上,不然为反面朝上。
那么操作T次以往桌子边缘上硬币的气象会是怎样的啊?

给定多少个数int n和int m,同时给定int 数学,j和int i,意义如题所述,请回来操作后的数,保证n的第j到第i位均为零,且m的二进制位数小于等于i-j+1。

Input

文件的率先行李包裹括四个整数n和T。
接下的一行李包裹蕴n个整数,表示最初步桌面边缘的硬币摆放情形,第i个整数ai表示第i个硬币摆放在2*i-三个任务上,ai=1表示尊重朝上,ai=2表示反面朝上。

测试样例:

Output

文件仅包蕴一行,为2n个整数,个中第i个整数bi桌面边缘的第i个岗位上硬币的动静,bi=1表示尊重朝上,bi=2代表反面朝上,bi=0代表没有硬币。

1024,19,2,6

返回:1100

Sample Input

10 5
2 2 2 1 1 1 1 1 1 2

 画图——》移位+或

Sample Output

0 1 0 1 0 1 0 1 0 2 0 1 0 2 0 1 0 1 0 1

多少范围
30%的数据 n≤1000 T≤1000
100%的数据 n≤100000 T≤2^60

 

题解:转自http://blog.csdn.net/PoPoQQQ/article/details/39934161?locationNum=6

首先我们令硬币正面为0 反面为1 那么很简单发觉新硬币的值为两边硬币的异或值
样例也就很好解释了

1-1-1-0-0-0-0-0-0-1-   0
-0-0-1-0-0-0-0-0-1-0   1
0-0-1-1-0-0-0-0-1-1-   2
-0-1-0-1-0-0-0-1-0-1   3
1-1-1-1-1-0-0-1-1-1-   4
-0-0-0-0-1-0-1-0-0-0   5

下一场那题n<=10W 矩阵乘法一定MLE 即便矩阵特殊结构能够干掉一维空间复杂度
O(n^2*logT)的光阴也惊惶失措经受

大家只考虑偶数的行

易知第贰行每种数是原系列该职位左右多少个数的异或

由数学归咎法能够第一^k行每种数是原类别该职位左侧第1^(k-1)个数和左边第二^(k-1)个数的异或

然后将T实行二进制拆分,每位进行三回变换即可 最终再钻探T的奇偶

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<algorithm>
 5 #include<cstring>
 6 #define ll long long
 7 
 8 using namespace std;
 9 
10 ll n,t,a[200000],b[200000];
11 ll f(ll b,ll k)
12 {
13     ll x=b-k,y=b+k;
14     x=(x%(n*2)+n*2-1)%(n*2)+1;
15     y=(y-1)%(n*2)+1;
16     if (k==0) return a[x];
17     if (a[x]==0) return 0;
18     if (a[x]==a[y]) return 1;
19     else return 2;
20 }
21 void work(ll k,ll q)
22 {
23     if (k==0) return;
24     work(k/2,q*2);
25     if (k%2==1)
26     {
27         memset(b,0,sizeof(b));
28         for (ll j=1;j<=n*2;j++)
29             b[j]=f(j,q);    
30         swap(a,b);
31     }
32 }
33 int main()
34 {
35     scanf("%lld%lld",&n,&t);
36     for (ll i=1;i<=n;i++)
37         scanf("%lld",&a[i*2-1]);
38 
39     work(t,1);
40 
41     for (ll i=1;i<n*2;i++)
42         printf("%d ",a[i]);
43     printf("%lld\n",a[n*2]);
44 }

 

import java.util.*;

public class BinInsert {
    public int binInsert(int n, int m, int j, int i) {
        return n|(m<<j);
    }
}

 

5.2 二进制小数

有二个介于0和第11中学间的实数,类型为double,重返它的二进制表示。倘若该数字不恐怕精确地用三十几人以内的二进制表示,再次回到“Error”。

给定三个double num,表示0到1的实数,请再次回到三个string,代表该数的二进制表示依旧“Error”。

测试样例:

0.625

返回:0.101

照着二进制和十进制小数的数学关系做正是了:乘2与1比

import java.util.*;

public class BinDecimal {
    public String printBin(double num) {
        StringBuffer res=new StringBuffer();
        res.append("0");
        res.append(".");
        for(int i=0;i<33;i++) {
            if(i==32) return "Error";
            num=num*2;
            if(num-1==0){
                res.append("1");
                break;
            }else if(num-1>0){
                res.append("1");
                num=num-1;
            }else{
                res.append("0");
            }
        }
        return res.toString();
    }
}

 

 本来,有时间足以试试跟0.5之类的做减法;思路大致

 

5.3 最接近的数

蛮力法都还没做出来,等头脑清醒一点再做;

 

5.4 ((n&(n-1))==0)的含义

 从卓越到一般再到独特:A&B==0

 

5.5 整数转化

编排多个函数,鲜明须求转移多少个位,才能将整数A转变成整数B。

给定几个整数int A,int B。请重回必要变更的数位个数。

测试样例:

10,5

返回:4

计数就好,注意用while

import java.util.*;

public class Transform {
    public int calcCost(int A, int B) {
        // 直接的思路,直接干,然后计数就好了嘛
        int count=0;
        int index=0;
        if (A==B) return count;
        while (A!=B) {
            if((A&(1<<index))!=(B&(1<<index))){
                count++;
                A=A^(1<<index);
            }
            index++;
        }
        return count;
    }
}

 

细节:用num^(1<<index)来改变某1个人的值;

 

5.6 奇偶位交流

请编写程序调换3个数的二进制的奇数位和偶数位。(使用越少的命令越好)

给定2个int x,请重临交换后的数int。

测试样例:

10

返回:5

import java.util.*;

public class Exchange {
    public int exchangeOddEven(int x) {
        // 首先,实现功能,就是从头开始,两位两位的跳
        //问题在于如何判断结束,不如再弄一个数字,慢慢赋值
        int[] tmp=new int[2];
        //int y=0;
        //int res=0;
        int index=0;
       // int slow=0;
        tmp[0]=x;tmp[1]=0;
        while(x!=tmp[1]){
            swap(tmp,index);
            index=index+2;
        }

        return tmp[0];
    }

    void swap(int[] tmp,int index) {
        int first=0;
        int second=0;
        int xx=tmp[0];
        //int yy=tmp[1];

        first=xx&(1<<index);
        second=xx&(1<<(index+1));
        if (first!=0) first=1;
        if (second!=0) second=1;

        //先清零再置位
        tmp[0]=(tmp[0]&(~(1<<index)))|(second<<index);
        tmp[0]=(tmp[0]&(~(1<<(index+1))))|(first<<(index+1));

        //更新y
        tmp[1]=(tmp[1]|(first<<index))|(second<<(index+1));       


    }
}

 

 关键点在于while的告一段落条件吧,对于自身而言;

巧妙方法:先对具备奇数位操作,再是偶数位,再或一下

return (((x & 0xaaaaaaaa)>>1)) | (((x & 0x55555555)<<1));

 

 

5.7 找出缺点和失误的平头

数组A包括了0到n的拥有整数,但中间缺失了一个。对于那个标题,我们设定限制,使得二回操作无法赢得数组number里有个别整数的全部内容。唯一的可用操作是了然数组中第i个要素的二进制的第j位(最低位为第0位),该操作的小运复杂度为常数,请设总计法,在O(n)的岁月内找到那一个数。

给定贰个数组number,即具有盈余的数按从小到大排列的二进制各位的值,如A[0][1]代表剩下的第3个数二进制从低到高的第几人。同时给定3个int n,意义如题。请重回缺点和失误的数。

测试样例:

[[0],[0,1]]

返回:1

没意思。。不做。。

依据书上的思绪:一般的是任何加起来,少那些正是越发;

这一个的话,就奇偶缺点和失误来做就行!!!

 

总结

5.3
和5.8没解决,5.7不想做,其余做完了,对位运算,依然自如是第②位的,思路要灵活些,什么快慢指针,递归,数组,字符串都足以用起;

 

—————拓展————————–

1.1&1.7 见  数组与字符串http://www.cnblogs.com/andy1202go/p/5759047.html

 

17.1 无缓存交流

请编写二个函数,函数内不接纳别的权且变量,直接交流多少个数的值。

给定一个int数组AB,其第零个成分和率先个成分为待调换的值,请回来调换后的数组。

测试样例:

[1,2]

返回:[2,1]

笔者的思绪是一向的公式退出来就好啊:

import java.util.*;

public class Exchange {
    public int[] exchangeAB(int[] AB) {
        AB[0]=AB[0]+AB[1];
        AB[1]=-(AB[1]-AB[0]);
        AB[0]=AB[0]-AB[1];
        return AB;
    }
}

 

书上的位运算解法没看懂。。。。

a=a^b;
b=a^b;//懂了,b=(a^b)^b=a;
a=a^b;

 

妈蛋,有点决心!!!

 

 

 

 

18.1 另类加法

无须加号的加法

重点思路:位运算;

相似:捣腾出进位再开始展览相加之类的

public class Solution {
    public int getSum(int a, int b) {
        int[] array=new int[]{a,b};
        getReal(array);
        int sum=array[0]|array[1];
        return sum;
    }

    public void getReal(int[] array)
    {
        int jinWei=array[0]&array[1];
        int mask=~jinWei;
        int huo=array[0]|array[1];
        array[0]=mask&huo;
        array[1]=jinWei<<1;
        int state=array[0]&array[1];

        if (state!=0){
            getReal(array);
        }
    }
}

 进阶:高级一点的递归

import java.util.*;

public class UnusualAdd {
    public int addAB(int A, int B) {
         if (A==0) return B;
        if (B==0) return A;
        int a=A^B,b=(A&B)<<1;
        return addAB(a,b);
    }
}

 

 

18.4 有几个2

请编写多个主意,输出0到n(包罗n)中数字2面世了四次。

给定一个正整数n,请重返0到n的数字中2涌出了三回。

测试样例:

10

返回:1

诚如思路,每二个数如此看下来就好

import java.util.*;

public class Count2 {
    public int countNumberOf2s(int n) {
        //要全部,看起来就像是递归
        int count=0;
        if (n<2) return count;
        for(int i=2;i<=n;i++) {
            count+=num2(i);
        }
        return count;
    }

    int num2(int n){
        int count=0;
        while(n>0){
            if (n%10==2){
                count++;
            }
            n=n/10;
        }
        return count;
    }

}

 

算法复杂度太大,时间太长。

找规律,得下边(我tm还没搞懂)

import java.util.*;

public class Count2
{
    public int countNumberOf2s(int n)
    {
        int result = 0;
        for(int i=1;i<=n;i*=10)
        {
            result+=(n/i+7)/10*i+(n/i%10==2?n%i+1:0)  ;      
        }
        return result;


    }
}

 

每十倍循环一下,然后对那么些十倍中有稍许2展开演算。

最初始想的是用递归,不是很好做,而且也是每3个这样搞,时间也太长。

 

相关文章

No Comments, Be The First!
近期评论
    分类目录
    功能
    网站地图xml地图