菜单

LeetCode – 4. Median of Two Sorted Arrays : 逆推法 O(log(min(m,n))))

2019年1月29日 - 金沙编程资讯
<?php
function addBinary($A,$B){
        $C=array();
        $length=count($A);
        $carry=0;
        for($i=$length-1;$i>=0;$i--){
                //当前位的数字逻辑 1+1=0 1+0=1
                $C[$i+1]=($A[$i]+$B[$i]+$carry)%2;
                //进位的数字逻辑  1+1=1 1+0=0
                $carry=intval(($A[$i]+$B[$i]+$carry)/2);
        }   
        $C[$i+1]=$carry;
        return $C; 
}

$A=array(0,1,1,0);
$B=array(1,1,1,1);
$C=addBinary($A,$B);
var_dump($C);

6.取模

设:

A=Sum[i=0 to p](A[i]*0x100000000^i)

B=Sum[i=0 to q](B[i]*0x100000000^i),p>=q

C=Sum[i=0 to n](C[i]*0x100000000^i)=A%B

求模与求商的进程一样,只是由于不要求记录商而愈发简便易行:

重复:

A=A-(A[p]/B[q]-1)*0x100000000^(p-q)*B,直到A

则有:

A=C

下边钻探 x=0 , x=n, y=0, y=m的状态

UVALive 6911—Double Swords(贪心+树状数组(或集合)),uvalive

标题链接

 

problem  description

Last night, Kingdom of Light was attacked by Kingdom of Dark! The queen
of Kingdom of Light, Queen Ar, was captured and locked inside a dark and
creepy castle. The king of Kingdom of Light, King Ash, wants to save the
queen. The castle is guarded by N dragons, conveniently numbered from 1
to N. To save Queen Ar, King Ash must kill all the dragons. The
kingdom’s oracle said that in order to kill the i-th dragon, King Ash
has to slay it with exactly two swords, one in each hand: one sword of
length Ai units, and another sword of length between Bi and Ci ,
inclusive. King Ash can carry unlimited number of swords, and each sword
can be used multiple times. The number of blacksmiths in the kingdom is
limited, so it is important to make as few swords as possible. Besides,
making swords is expensive and takes much time. Determine the minimum
number of swords the kingdom has to make so that King Ash can save Queen
Ar!

Input

The first line of input contains an integer T (T ≤ 20) denoting the
number of cases. Each case begins with an integer N (1 ≤ N ≤ 100, 000)
denoting the number of dragons which have to be killed. The next N lines
each contains three integers: Ai , Bi , and Ci (1 ≤ Ai ≤ 1, 000, 000; 1
≤ Bi ≤ Ci ≤ 1, 000, 000) denoting the swords’ length needed to kill the
i-th dragon as described in the above problem statement.

Output

For each case, output ‘Case #X: Y ’, where X is the case number starts
from 1 and Y is the minimum number of swords the kingdom has to make and
carry in order to defeat all the dragons and save Queen Ar.

Explanation for 1st sample case: The kingdom has to make two swords in
order to defeat one dragon.

Explanation for 2nd sample case: All the dragons can be defeated by
three swords, for example, with lengths of: 3, 6, and 15.

     • The fist dragon can be defeated by swords of length 3 and 6.

     • The second dragon can be defeated by swords of length 6 and 15.

     • The third dragon can be defeated by swords of length 3 and 15.

There also exists other combination of three swords.

Sample Input

4

1

7 6 8

3

3 5 10

6 11 15

3 13 15

4

1 10 20

3 50 60

2 30 40

4 70 80

2

5 100 200

150 1000 2000

Sample Output

Case #1: 2

Case #2: 3

Case #3: 8

Case #4: 3

 

题意:有n条恶龙,须要人还要持两把剑杀死,一把剑要求长为A,另一把剑长度在B~C之间,输入n条龙的A
B C数据须求,求最少要求指点多少把剑?

思路:对于n组恶龙的数目,依据C的深浅从左到右排序。先考虑数据A,即先把长度固定的剑需求的数码确定,有些A相同只计算一次,sum=0,sum+=unique(Ai)。然后考虑长度为距离(B~C)的剑,对于排好序的数目,循环处理,对于区间Bi~Ci
若是距离里不曾剑或者有一把剑且长度和Ai相等,则添加一把剑长为Ci,sum++,那样也许在前面的间隔中冒出,使得剑的数码最少,否则不处理,讲明那些区间中有剑,不要求投入剑。注意:在认清距离中剑的多寡时,用树状数组很便宜查询;

 

代码如下:

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <cstring>
#include <cmath>
#include <queue>
#include <set>
#include <bitset>
using namespace std;
const int maxn=1e6+5;
int c[maxn];
bool vis[maxn];
struct Node
{
    int x,y;
    int z;
}node[2*100005];
bool cmp(const Node s1,const Node s2)
{
    if(s1.y==s2.y) return s1.x<s2.x;
    return s1.y<s2.y;
}
int Lowbit(int t)
{
    return t&(t^(t-1));
}
void add(int x)
{
    while(x<maxn){
        c[x]++;
        x+=Lowbit(x);
    }
}
int sum(int x)
{
    int sum=0;
    while(x){
        sum+=c[x];
        x-=Lowbit(x);
    }
    return sum;
}
int main()
{
    int T,Case=1;
    cin>>T;
    while(T--)
    {
        memset(vis,0,sizeof(vis));
        memset(c,0,sizeof(c));
        int N;
        scanf("%d",&N);
        for(int i=0;i<N;i++)
        {
            scanf("%d",&node[i].z);
            if(!vis[node[i].z]){
                add(node[i].z);
                vis[node[i].z]=true;
            }
            scanf("%d%d",&node[i].x,&node[i].y);
        }
        sort(node,node+N,cmp);
        for(int i=0;i<N;i++)
        {
            int t=sum(node[i].y)-sum(node[i].x-1);
            if(t==1&&node[i].z>=node[i].x&&node[i].z<=node[i].y)
                add(node[i].y);
            else if(!t) add(node[i].y);
        }
        printf("Case #%d: %d\n",Case++,sum(maxn-1));
    }
    return 0;
}

 

那题也得以用集合,其实和上边思路大约,用集合判断距离中是还是不是有剑;

在网上看看有人用set写,代码如下:

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <cstring>
#include <cmath>
#include <queue>
#include <set>
#include <bitset>
using namespace std;
struct Node
{
    int x,y;
    int z;
}node[100005];
bool cmp(const Node s1,const Node s2)
{
    if(s1.y==s2.y) return s1.x<s2.x;
    return s1.y<s2.y;
}
set<int>s;
set<int>::iterator it;

int main()
{
    int T,Case=1;
    cin>>T;
    while(T--)
    {
        s.clear();
        int N;
        scanf("%d",&N);
        for(int i=0;i<N;i++)
        {
            scanf("%d",&node[i].z);
            s.insert(node[i].z);
            scanf("%d%d",&node[i].x,&node[i].y);
        }
        sort(node,node+N,cmp);
        int sum=0;
        for(int i=0;i<N;i++)
        {
            it=s.lower_bound(node[i].x);
            if(it!=s.end()&&*it==node[i].z) it++;
            if(it==s.end()||*it>node[i].y){
                if(node[i].z==node[i].y)
                    s.insert(0-node[i].y);
                   //sum++;///set有去重功能;
                else  s.insert(node[i].y);
            }
        }
        printf("Case #%d: %d\n",Case++,s.size()+sum);
    }
    return 0;
}

那般写确实AC了,但自我倍感有BUG 我认真看了先后,想了一个数目:

1

2

4 2 4

4 4 6

毋庸置疑答案是2

运行那几个顺序结果是3

图片 1

 

但是用多重会聚是足以避免那一个BUG的

代码如下:

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <cstring>
#include <cmath>
#include <queue>
#include <set>
#include <bitset>
using namespace std;
const int maxn=1e6+5;
bool vis[maxn];
struct Node
{
    int x,y;
    int z;
}node[100005];
bool cmp(const Node s1,const Node s2)
{
    if(s1.y==s2.y) return s1.x<s2.x;
    return s1.y<s2.y;
}
multiset<int>s;
multiset<int>::iterator it;

int main()
{
    int T,Case=1;
    cin>>T;
    while(T--)
    {
        memset(vis,0,sizeof(vis));
        s.clear();
        int N;
        scanf("%d",&N);
        for(int i=0;i<N;i++)
        {
            scanf("%d",&node[i].z);
            if(!vis[node[i].z]){
                s.insert(node[i].z);
                vis[node[i].z]=true;
            }
            scanf("%d%d",&node[i].x,&node[i].y);
        }
        sort(node,node+N,cmp);
        for(int i=0;i<N;i++)
        {
            it=s.lower_bound(node[i].x);
            if(it!=s.end()&&*it==node[i].z) it++;
            if(it==s.end()||*it>node[i].y){
                s.insert(node[i].y);
            }
        }
        printf("Case #%d: %d\n",Case++,s.size());
    }
    return 0;
}
/*
345
2
4 2 4
4 4 6
2
4 2 4
4 3 4
*/

 

6911—Double
Swords(贪心+树状数组(或集合)),uvalive 标题链接

五个n位二进制数分别存储在多个n元数组A和B中,那五个整数的和存在一个n+1元的数组C中
答:
此难点关键是洞察相加进位的难题,元素1+1 =0 并且往前进一位
ADD-BINARY(A,B)
  C=new integer[A.length+1]
  carry=0
  for i=A.length downto 1
    C[i+1]=(A[i]+B[i]+carry)%2
    carry=(A[i]+B[i]+carry)/2
  C[i]=carry

3.减法

设:

A=Sum[i=0 to p](A[i]*0x100000000^i)

B=Sum[i=0 to q](B[i]*0x100000000^i),p>=q

C=Sum[i=0 to n](C[i]*0x100000000^i)=A-B

显然:

C[i]不是几乎地等于A[i]-B[i],因为一旦A[i]

C[i-1]时也恐怕发生了借位,所以总结C[i]时还要减去上次的借位值。

如果用carry[i]记录每便的借位则有:

C[i]=A[i]+carry[i]*0x100000000-B[i]-carry[i-1]

其中carry[-1]=0

若A[i]>B[i]则carry[i]=0;反之则carry[i]=1

若C[p]=0,则n=p-1;反之则n=p

则职分转换为, 已知 A,B ,
求满意上述原则的 MAX(C1),MIN(C2)
 

 

10.素数测试

数论学家利用费马小定理( a^(p-1)%p=1,其中p是质数,a是整数
)探究出了四种素数测试方法,方今最快的算法是拉宾Miller测试算法,测试N是素数的经过如下:

(1)总计奇数M,使得N=(2^r)*M+1

(2)选拔随机数A

(3)对于任意i

(4)或者,若A^M MOD N = 1,则N通过随机数A的测试

(5)让A取不一致的值对N进行5次测试,若一切因此则判定N为素数

若N 通过四回测试,则N 不是素数的几率为 25%,若N 通过t 次测试,则N
不是素数的几率为1/4^t。事实上取t 为5 时,N 不是素数的几率为 1/128,N
为素数的票房价值已经高于99.99%。

在骨子里运用中,可首先用300—500个小素数对N
进行测试,以坚实拉宾米勒测试通过的几率,从而增强测试速度。而在转变随机素数时,选拔的随机数最好让
r=0,则可省去手续(3) 的测试,进一步进步测试速度。

5.除法

设:

A=Sum[i=0 to p](A[i]*0x100000000^i)

B=Sum[i=0 to q](B[i]*0x100000000^i),p>=q

C=Sum[i=0 to n](C[i]*0x100000000^i)=A/B

由于不能将B 对A
“试商”,我们只能够转换成B[q]对A[p]的试商来获得一个类似值,

据此我们不可见向来总计C。可是,我们可以一步一步地逼近C

显然:

(A[p]/B[q]-1)*0x100000000^(p-q)

令:

X=0

重复:

A=A-X*B,X=X+(A[p]/B[q]-1)*0x100000000^(p-q),直到A

则有:

X=C

注意:

由于大数可领悟为0x100000000进制,所以对于随意大数A*0x100000000^k

都等价于将A 的数组中的各因素左移k 位,不必总结;同样,除法则相当于于右移

可以看到要落成log(m+n)这些等级,
合并那条路走不通.

4.乘法

设:

A=Sum[i=0 to p](A[i]*0x100000000^i)

B=Sum[i=0 to q](B[i]*0x100000000^i),p>=q

C=Sum[i=0 to n](C[i]*0x100000000^i)=A*B

显然:

C=Sum[i=0 to q](A*B[i]*0x100000000^i)

而(A*B[i]*100000000^i)=Sum[j=0 to
p](A[j]*B[i]*0x100000000^(i+j))

所以C=Sum[i=0 to q](Sum[j=0 to
p](A[j]*B[i]*0x100000000^(i+j)))

因此:

C[i]=Sum[j=0 to
q](A[i-j]*B[j])+carry[i-1]-carry[i]*0x100000000

其中carry[-1]=0

carry[i]=(Sum[j=0 to q](A[i-j]*B[j])+carry[i-1])/0x100000000

n=p+q-1,若carry[n]>0,则n=n+1,C[n]=carry

//说明x刚好满足条件2.
            if (x === 0) {
                var MAX_C1 = B[y - 1];
            }
            else if (y === 0) {
                var MAX_C1 = A[x - 1];
            }
            else {
                var MAX_C1 = A[x - 1] > B[y - 1] ? A[x - 1] : B[y - 1];
            }

            if (x === A.length) {
                var MIN_C2 = B[y];
            }
            else if (y === B.length) {
                var MIN_C2 = A[x];
            }
            else {
                var MIN_C2 = A[x] > B[y] ? B[y] : A[x];
            }

            if ((A.length + B.length) % 2 == 0) {
                return (MAX_C1 + MIN_C2) / 2;
            }
            else {
                return MAX_C1 * 1.0;
            }

1.大数储存

RSA 信赖大数运算,近来主流RSA 算法都成立在512
到1024位的造化运算之上。而半数以上的编译器只好辅助到64位的平头运算,即大家在运算中所使用的整数必须低于等于64位,即:0xffff,
ffff,ffff.ffff,也就是18446744073709551615,那远远达不到RSA
的须要,于是要求特地成立大数运算库来化解这一标题。

最简便的法门是将命局当作数组举行拍卖,也就是将命运用0-9那十个数字组合的数组进行表
示,然后模拟人们手工举行“竖式总计”的进度编写其加减乘除函数。可是如此做作用很低,因为二进制为1024位的大数其十进制也有三百多位,对于其余一种
运算,都需要在多少个有数百个元素的数组空间上做多重循环,还须要广大非凡的空中存放统计的进退位标志及中间结果。此外,对于某些特殊的运算而言,选择二进
制会使计量进度大大简化,那种大数表示方法转化成二进制分明非常麻烦,所以在某些实例中则索性采纳了二进制数组的不二法门来记录大数,这样效能就更低了。

一个卓有效用的立异措施是将命局表示为一个n 进制数组,对于眼前的32位系统而言n
可以取值为2
的32次方,即0x10000,0000,借使将一个二进制为1024位的运气转化成0x10000,0000进制,它就变成了32位,而每一位的取值范围就
不是二进制的0—1或十进制的0—9,而是0-0xffff,ffff,大家刚刚可以用一个无符号长整数来表示这一数值。所以1024位的命局就是一个有
32个元素的unsigned long数组,针对unsigned
long数组举行各样运算所需的巡回规模至多32次而已。而且0x10000,0000
进制与二进制,对于电脑来说,大概是一回事,转换卓殊不难。

例如大数18446744073709551615,等于 ffffffff
ffffffff,就一定于十进制的99:有两位,每位都是ffffffff。而18446744073709551616
等于00000001 00000000 00000000,就一定于十进制的100:有三位,首位是1
,其它两位是0,如此等等。在事实上行使中,“数字”数组的排列顺序接纳低位在前高位在后的主意,这样,大数A
就足以便宜地用数学表明式来表示其值:A=Sum[i=0 to
n](A[i]*0x100000000 ^ i)(其中Sum
表示求和,A[i]意味着用以记录A的数组的第i个因素,^表示乘方)。

其余整数运算最后都能分解成数字与数字之间的运算,在0x100000000
进制下其“数字”最大达到0xffffffff,其数字与数字之间的运算,结果也毫无疑问超越了现阶段32连串的字长。在VC++中,存在一个__int64
类型可以拍卖64位的平头,所以并非操心这一标题,而在其他编译系统中如若不存在64位整形,就须要运用更小的进制形式来囤积大数,例如WORD类型
(16位)可以用来代表0x10000 进制,但功用更高的方法如故使用32位的DWORD
类型,只不过将0x100000000
进制改成0x40000000进制,那样三个数字举办四则运算的最大结果为
0x3fffffff*
0x3fffffff,小于0xffffffff,只是无法大概地用高位低位来将运算结果拆分成七个“数字”。

Example 2:

2.加法

设:

A=Sum[i=0 to p](A[i]*0x100000000^i)

B=Sum[i=0 to q](B[i]*0x100000000^i),p>=q

C=Sum[i=0 to n](C[i]*0x100000000^i)=A+B

显然:

C[i]不是简简单单地等于A[i]+B[i],因为假设C[i]>0xffffffff就须要进位,当然计算

C[i-1]时也恐怕暴发了进位,所以总括C[i]时还要加上上次的进位值。

如果用carry[i]记录每趟的进位则有:

C[i]=A[i]+B[i]+carry[i-1]-carry[i]*0x100000000

其中carry[-1]=0

若A[i]+B[i]+carry[i-1]>0xffffffff,则carry[i]=1;反之则carry[i]=0

若carry[p]=0,则n=p;反之则n=p+1

中位数为 median = (MAX(C1) + MIN(C2)) /2
 (m+n 为偶数) 或 MAX(C1)  (m+n为奇数). (将median放在C1)

9.乘模运算

结余的题材就是乘模运算了,对于A*B % N,如若A、B
都是1024位的天命,先统计A*B,再%
N,就会生出2048位的中游结果,倘若不行使动态内存分配技术就亟须将命局定义中的数组空间扩张一倍,那样会促成大量的浪费,因为在一大半气象下不会
用到那额外的一倍空间,而使用动态内存分配技术会使大数存储失去屡次三番性而使运算进度中的循环操作变得至极麻烦。所以总计的要害条件就是要防止总括A*B。

由于:

A*B=A*(Sum[i=0 to n](B[i]*0x100000000^i))

所以:

A*B % N = (Sum[i=0 to n]((A*B[i])*0x100000000^i)) % N

可以用一个循环求得:

C=0;

FOR i=0 to n

C=C+A*B[i]*0x100000000 % N

RETURN C

实在,有一种Montgomery算法可以更快地做到数次循环往复的乘模运算,然而其规律涉及较多的数论知识,且完结起来相比坚苦,对进程虽有提升,经测试也不会当先一个数量级,所以暂且不予考虑。

7.二元三次方程

在RSA 算法中,往往要在已知A、M的境况下,求 B,使得
(A*B)%M=1。即一定于求解B、N都是未知数的二元一回不定方程
A*B-M*N=1,的纤维整数解。

而针对性不定方程ax-by=1
的微乎其微整数解,古今中外都进行过详细的钻研,西方有资深的欧几里德算法,即辗转相除法,中国有秦九韶的“大衍求一术”。欧几Reade算法是一种递归算法,相比易于精晓:

例如:11x-49y=1,求x

(a) 11 x – 49 y = 1    49%11=5 ->

(b) 11 x –  5 y = 1    11%5 =1 ->

(c)    x –  5 y = 1

令y=0 代入(c)得x=1

令x=1 代入(b)得y=2

令y=2 代入(a)得x=9

同理可使用递归算法求得任意
ax-by=1(a、b互质)的解,实际上通过分析归咎将递归算法转换成非递归算法就变成了大衍求一术。

则有:

11.输入输出

运气的输入输出是透过字符串来形成的,事实上很简单完毕,例如按照十进制格式举办拍卖,则:

输入:

X=0

FOR i=0 TO n

X=X*10

X=X+(int)(str[n]-48)

RETURN X

输出:

str=

WHILE(X>0)

str=(char)(X%10-48)+str

RETURN str

要满意条件1: 很简单满足….

8.幂模运算

幂模运算是RSA 焦点算法,最直白地控制了RSA
算法的品质,针对连忙幂模运算这一课题,许多上天现代数学家提议了汪洋的缓解方案。经常都是先将幂模运算化简为乘模运算。

例如求D=C^15 % N,由于:

a*b % n = (a % n)*(b % n) % n

所以:

C1=C*C % N       =C^2 % N

C2=C1*C % N      =C^3 % N

C3=C2*C2 % N     =C^6 % N

C4=C3*C % N      =C^7 % N

C5=C4*C4 % N     =C^14 % N

C6=C5*C % N      =C^15 % N

即:

对于E=15的幂模运算可诠释为6个乘模运算

概括分析以上措施能够发现对于任意E,可接纳以下算法计算D=C^E % N:

D=1

WHILE E>=0

IF E为奇数

D=D*C % N

D=D*D % N

E=E-1

IF E为偶数

D=D*D % N

E=E/2

RETURN D

再加以分析会发觉,要清楚D 何时需乘 C,不必要频繁对E
举办减一或除二的操作,只须要验证E 的二进制个位是0 依旧1
就可以了,而且从左至右验证和从右至左验证都行,反而从左至右验证更简短:

若E=Sum[i=0 to n](E[i]*2^i),0<=E[i]<=1(E为二进制)

D=1

FOR i=n TO 0

D=D*D % N

IF E[i]=1

D=D*C % N

RETURN D

要满意条件3: C1.length ==
C2.length
 (或 C1.length  == 1+ C2.length , 将median放在C2) , 设C1中
来自A的个数为x, 来自B的个数为y, 要满足

相关文章

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图