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

 

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

那意味着 只要找到 x (C1中 A元素的多少) ,
使得A,B 满意 条件2即可. 此话怎讲?

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 标题链接

<?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);

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,只是不能够大概地用高位低位来将运算结果拆分成八个“数字”。

在取得最终结果的时候要也要咬定:

多少个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

Example 1:

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
为素数的票房价值已经超(英文名:jīng chāo)越99.99%。

在实际利用中,可首先用300—500个小素数对N
举行测试,以拉长拉宾Miller测试通过的几率,从而狠抓测试速度。而在云谲波诡随机素数时,选用的随机数最好让
r=0,则可省去手续(3) 的测试,进一步进步测试速度。

一个(x,y)的撤并如图:

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算法可以更快地成功多次巡回的乘模运算,不过其规律涉及较多的数论知识,且已毕起来比较费心,对速度虽有升高,经测试也不会领先一个数额级,所以暂且不予考虑。

There are two sorted arrays nums1 and nums2 of size m and n respectively.

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

那多种状态, 对应的是

7.二元一回方程

在RSA 算法中,往往要在已知A、M的气象下,求 B,使得
(A*B)%M=1。即一对一于求解B、N都是未知数的二元两次不定方程
A*B-M*N=1,的微小整数解。

而针对性不定方程ax-by=1
的蝇头整数解,古今中外都开展过详细的探讨,西方有出名的欧几Reade算法,即辗转相除法,中国有秦九韶的“大衍求一术”。欧几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互质)的解,实际上通过分析归结将递归算法转换成非递归算法就变成了大衍求一术。

nums1 = [1, 3]
nums2 = [2]

The median is 2.0

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

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

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

Example 2:

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

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

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 位,不必总计;同样,除法则相当于右移

即满意  y = (m + n + 1) /2  – x
 (利用除2向下取整,合并两种状态)

发表评论

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