动漫动画

当前位置:澳门金莎娱乐场网址 > 动漫动画 > 双栈排序,如何分摊秘密

双栈排序,如何分摊秘密

来源:http://www.lfxindai.com 作者:澳门金莎娱乐场网址 时间:2019-11-14 23:17

神漫。喜欢。
我看见的是孤独级s的世界。

很早就学过欧几里得算法,但是一直不知道它的原理。几乎每本算法书都会提到它,但是貌似只有数学书上才会见到它的原理。。。

六、数字世界

在前面几节中我们描述了如何在多人之间分摊秘密的方法,并具体地以如何分摊一个6位的十进制数字为例作了说明。容易看出来,就算密码位数不是6位,而是非常非常长,我们所说的这个方法也同样可行,只需把那个N取得非常非常大。

假如《鹿鼎记》中地图原图大小为一米见方,差不多是边长为40英寸的正方形。如果用每英寸300像素的图像质量来将其数字化,就是一幅12000×12000像素的图像;用24位真彩的话,每个像素可用一个24位的二进制数字来表示;整幅图像就可用一个12000×12000×24=3456000000位的二进制数字来表示。写成电脑文件,大小会有3456000000/(8×1024×1024)≈412兆字节。如果地图的尺寸更大几倍,像素密度更高一些,那么上面估计的文件也会更大一些。当然这是不考虑图像压缩的情况,否则文件可以更小。不过412兆字节或者再多若干倍的存储量也不是不可接受的——尤其如果它事关一个大宝藏的话。

我们取N为23456000000,这个数字比十的十亿次方稍微大些。上面这幅数字化了的地图,就是0到N-1之间的某个数s,即八旗旗主会议试图分摊给八位旗主的秘密。按照前面几节介绍的分摊秘密的方法,摄政王可以用一个好的(也就是能均匀地独立地产生随机数的)随机数产生器产生出7个0到N-1之间的随机数,将它们(的同余类)分别交给前七位旗主,再将s减去这七个数字,将它(的同余类)交给第八位旗主。这就完成了地图秘密的分摊。每位旗主需要记住的,是一个约412兆字节的文件。

这八位旗主中的任何七位联合起来,没有第八位旗主的同意,也无法知晓原地图图像文件到底是0到N-1之间的哪个数。当然,他们还是能知道那个数不会是——比如说——0,因为这意味着那是一张全黑的图像。但这样的“知道”是通过常识推断出来的,就算是不掌握那八个秘密数字的人也可以做到,并非这个分摊策略的弱点。

要分摊的秘密也不一定非要是账号密码或是一幅图像。它也可以是一段文字,数字化后是一个文本文件;也可以是一段录音或录像,数字化后是一个音频或视频文件;或是其他任何格式的文件。只要某个秘密能被数字化,那么我们都可以用前面所说的方式,在若干个人之间分摊秘密。每个人需要掌握的分摊给他的秘密文件的大小,等于原始秘密文件的大小。

 

假设一:这个世界的宇宙规律是:
1普通人类可以成为英雄,且有cba三级越来越高可追求,
2并且普通人能看出c级更强大,cb级能看出a级更强大,
但与此同时存在着一些s级的超级英雄,
3可是一个达到了超s级的英雄只可能被另一个s级的英雄感知,
4其它abc级英雄则都无法感知超s级,
即便偶尔看到踪迹也会因无法理解而曲解。
一个s级永远是s级,不会变成a级,一个a级也无法变成s级。
一个a级可以退化成b级,一个b级可以进化到a级,c级亦然。

前段时间粗粗看了点数论,惊讶于这个原理的奇妙。现在把它通俗地写下来,以免自己忘记。

七、无需所有人都同意的分摊秘密方法

不过正如前面所言,前几节中分摊秘密的方法好是好,但未免过分严格了一点。如果在100个人中这样分摊秘密,万一有个人三长两短把他掌握的数字弄丢了怎么办?那样的话,剩下的99个数字变得对揭晓秘密毫无用处。

所以我们还得想出一个办法,能够无需所有人都同意,只需达到规定的某个数目的人数(比如说80个人)同意时,就可以揭开秘密。当然,如果只有低于此数的人合谋,他们将不能增加哪怕一点对真正秘密的了解程度。

先考虑最简单的三个人分摊秘密的问题来。如果只要其中两个人同意就可以揭晓秘密,该怎么分摊?

有个很简单的方法,还是按老规矩把秘密拆成a、b、c三部分,只有拿到所有这三个部分才能揭晓秘密。老板让甲拿a和b,乙拿b和c,丙拿a和c。很显然,任何单个人都无法通过自己手上的那两部分获得任何关于秘密的知识;但是任何两个人在一起,总能凑齐abc三部分,从而得知秘密。

上面这个方法很简单,但不容易推广。我们再看另一种方法。

秘密可以拆成两部分a和b,也可以另外拆成a'和b',还可以再拆成a"和b"。这三种拆法互相独立,所以必须拿到同一种拆法中的两个部分,才能得知秘密。否则的话,比如只拿到a,a'和a",或是只拿到b,a'和b"等等,都无法恢复出原秘密来。然后把a和b分别给甲和乙,a'和b'分别给乙和丙,a"和b"分别给甲和丙(也即a和a"给甲,b和a'给乙,b'和b"给丙)。容易看出,单个人手里并没有任一种拆法中的完整两部分,但甲乙一起就有a和b,乙丙一起就有a'和b',甲丙一起就有a"和b",都能够揭晓秘密。

上面这种分摊秘密的方法同样满足我们的要求,而且有容易推广的好处。用类似的拆法可以实现“非对称”的秘密分摊。比如说,在上面的例子中把a和b分别给甲和乙,a'和b'分别给乙和丙,a"和b"丢弃不用。那么任何单个人都无法知道秘密,而甲乙或乙丙联合则可揭晓秘密,但甲丙联合则不可以。这种方法的关键在于,我们为每个允许揭秘的组合准备了一个拆分。而这个方法可以推广到一般的m个人的情况。

假设现有m个人,而且又有一张“允许揭秘组合”的列表,那么我们就能有一个和上面类似的分摊策略,使得秘密能被揭晓,当且仅当联合在一起的某些人恰好是这张列表中的某组合。用集合论的语言来说,给定m人的集合P,又有P所有子集的集合的一个子集A(即每个A里的元素都是P的一个子集,如果P的某个子集属于A,我们称它是准入集),那么我们可以构造一个分摊策略,使得P的一个子集U中的人联合起来就可以揭晓秘密,当且仅当U包含了某个准入集。

构造的方法很简单:对每一个准入集我们都独立地将秘密s分拆一次,分成k部分,其中k是这个准入集中的人数,然后将这k部分分别给此准入集中的k个人(特别地,如果k=1,也就是准入集中只有一个人,那么他将直接获得秘密s)。容易看出,秘密可以被揭晓当且仅当某拆分的所有部分都可以被收集齐,而这又当且仅当联合起来的人中的一些人可以组成某个准入集。

举个具体的例子。某公司有某秘密,经手人有两个执事甲乙和三个监督人丙丁戊共五人。允许揭晓秘密的条件是:至少有执事甲和任意两个监督人在一起时,或是至少有执事乙和所有三个监督人在一起时。

这时的准入集有四个,即{甲丙丁},{甲丁戊},{甲丙戊},{乙丙丁戊}。我们构造秘密s的同余类的四个(独立的)拆分如下:
[s]=[a1] [a2] [a3]
[s]=[b1] [b2] [b3]
[s]=[c1] [c2] [c3]
[s]=[d1] [d2] [d3] [d4]
对每个准入集作如下的分摊:
[a1]→甲,[a2]→丙,[a3]→丁;
[b1]→甲,[b2]→丁,[b3]→戊;
[c1]→甲,[c2]→丙,[c3]→戊;
[d1]→乙,[d2]→丙,[d3]→丁,[d4]→戊;
按每个人分类,我们有分摊表:
甲←[a1],[b1],[c1];
乙←[d1];
丙←[a2],[c2],[d2];
丁←[a3],[b2],[d3];
戊←[b3],[c3],[d4];
容易验证这样的分摊秘密方法符合我们的要求。

澳门金莎娱乐场网址,前面的构造中没有排除某一个准入集A是另一个准入集B的真子集的情况。如果准入集A是准入集B的真子集,容易看出准入集B是不必要作为准入集而存在的,因为凑够了B中的人就必定已经凑够了A中的人,可以用为A所作的那个拆分来揭示秘密,完全没有必要再单独为B作一个拆分。所以为实用起见,我们可以假设准入集之间互不包含。

(待续)

 

假设二:这个世界的宇宙规律是:
1即便人出生时携带c或b或a或s四种基因其一,
各占四分之一,
2但携带s基因的人必须具备更高更多天赋更强能力,
才能保护自己的s基因不被扼杀。
所以会有一些普通人其实也是携带s基因的。
所以s级会被广泛当做傻白甜或小独美看待,
而a级会获得普通人和bc级英雄的认可,
可是超s级的琦玉老师才不在意那些呢:p
真好。

欧几里得算法是求两个数的最大公约数的算法,我们首先假设有两个数a和b,

by  GeneralLiu

其中a是不小于b的数,记a被b除的余数为r,,那么a可以写成这样的形式:

 

a = b*q r
其中q是整数。

NOIP2008 双栈排序 

现在假设a和b的一个约数为u,那么a和b都能被u整除,

 

a = su
b = t
u
s和t都是整数。

题目大意

这样可以得出

给出一个1~n的排列

r = a - bq = su - (tu)q = (s - tq)u

能否通过两个栈的出栈进栈操作

所以r也能被u整除,一般规律如下

完成从大到小排序

a和b的约数也整除它们的余数r,所以a和b的任一约数同时也是b和r的约数。

如果不能 输出 0

反过来可以得出

能就 输出字典序最小的操作方案

b和r的约数同时也是a和b的约数。

(题目要求详情见洛谷链接  没错,就是上面那个)

这是因为对b和r每一个约数v,有

 

b = kv
r = c
v

假设现在你已经了解 题目的要求 以及细节

所以a = b*q r = (k*v)*q c*v = (k*q c)*v
于是

 

a和b的最大公约数res, 就是b和r的最大公约数。

设b和r的最大公约数为r1, r和r1的最大公约数为r2...

那么res也是r和r1的最大公约数,也是r1和r2……

那我就在博客 try 着去重现

上面这个规律就是欧几里得算法的数学核心。
因为a>b,可以看出余数r(n)会越来越小,最终变成0;
当r(n) = 0时,因为任意数和0的最大公约数就是这个数本身,所以r(n-1)和r(n)的最大公约数就是r(n-1), 所以r(n-1)就是a和b的最大公约数。

培训时 mzx dalao 讲课时的情景

写成c语言函数是这样的:

选中下文查看分析

1
2
3
4
5
6
7
8
9
unsigned int Gcd(unsigned int M,unsigned int N){
    unsigned int Rem;
    while(N){
        Rem = M % N;
        M = N;
        N =Rem;
    }
    return Rem;
}

设 a<b<c<d...<n ;也可以理解为 a=1,b=2 , c=3.....

 

  “ 先不要管 双栈排序

可以发现这里没有要求M>=N;这是因为如果那样,循环会自动交换它们的值。

  先想想 单栈排序

发现还是写的不通俗...

  (一个 稍微凌乱点的 序列能单栈,

 

    就是 " b a d c... n "这种不是太乱的) 

  当然,大多数情况是不能单栈排序的,

  (就是出现形如 " b c a " 这种又乱了些序列时)

  当单栈排序行不通时

  就试试双栈排序

  (拿上一个" b c a"来讲

    如果双栈 可以 b进栈1 c进栈2 a进栈1 a出栈1 b出 c出...

   这种不是很恶心的 序列 是可以双栈的)

  那双栈什么时候也会虚呢?

  (其实双栈很容易虚的

    不信 把上一个" b c a "加一个d

    变成" b c d a "试试

    点到为止)

  现在对于本题来说已经可以了

  (不能双栈直接 输出 NO

    能的话 优先 栈1 字典序最小嘛)

  但还是拓展一下

  双栈虚了,三栈行不?

  (咦,刚才的 " b c d a "用三栈可以耶

    但再加一个 e 的话

    就是 " b c d e a "

    那么三栈也虚了)

  ......”

好了 “聪明的读者,看到这你一定明白了”by 刘汝佳

 

假设有 a b c d e 五个数

出现  b c d a 时 双栈不能解决 可三栈能

出现  b c d e a 时三栈就不能了

到这儿,规律已出

现在 能否用 N 栈排序的问题已经解决

那么就剩字典序最小的问题了

其实贪心去优先用第一个栈就好

 

现在思路已经 缕出

至于代码实现

分两步:

1:判断能否双栈

  维护一个mind[]数组  mind[i] 表示末尾 i 个数的最小值 // 代码 24行

  若 满足一个 i<j<k && s[k]<s[i]<s[j] //代码 25~28 行

  说明 第 i 和第 j 个不能单栈 

  就 把 i 到 j 连一条边 表示 i ,j  不能同栈

  最后抽象成 二分图判断 即可 // 代码 29~31行

  

2:输出操作序列

   依题目要求即可

  不必细说

  看代码 

 

代码

 

 1 #include<iostream>
 2 #include<stack>
 3 #include<algorithm>
 4 #define N 1005
 5 using namespace std;
 6 int mind[N],n,s[N],color[N],mp[N][N];
 7 stack<int> s1,s2;//两个栈 
 8 void dfs(int u,int c){ // 二分图 染色 
 9     color[u]=c;
10     for(int i=1;i<=n;i  )
11       if(mp[u][i]){
12           if(color[i]==c){ // 不能双栈 退出 
13               cout<<0;
14               exit(0);
15           }
16           if(!color[i])
17             dfs(i,-c);
18       }
19 }
20 int main(){
21     cin>>n;
22     for(int i=1;i<=n;i  )cin>>s[i];
23     mind[n 1]=N;
24     for(int i=n;i>=1;i--)mind[i]=min(mind[i 1],s[i]);//维护mind[] 
25     for(int i=1;i<n;i  )  // 枚举 判断 能否单栈 
26       for(int j=i 1;j<=n;j  )
27         if(s[i]<s[j]&&mind[j 1]<s[i]) 
28           mp[i][j]=mp[j][i]=1; // 连边 
29     for(int i=1;i<=n;i  )
30       if(!color[i])
31         dfs(i,1);// 优先 染色 为1 进栈1 保证 字典序 最小 
32     int aim=1; // 表示 目前应该是 该aim 出栈 (因为是个排列嘛) 
33     for(int i=1;i<=n;i  ){ // n 次进栈 
34         if(color[i]==1){
35             cout<<"a ";
36             s1.push(s[i]);
37         }
38         else{
39             cout<<"c ";
40             s2.push(s[i]);
41         }
42         // 该出栈时 就出栈 诶~ 
43         while( (!s1.empty()&&s1.top()==aim) || (!s2.empty()&&s2.top()==aim) ){
44             if(!s1.empty()&&s1.top()==aim){
45                 cout<<"b ";
46                 s1.pop();
47             }
48             else{
49                 cout<<"d ";
50                 s2.pop();
51             }
52             aim  ; // 出一个 加一个 
53         }
54     }
55     return 0;
56 }

 

本文由澳门金莎娱乐场网址发布于动漫动画,转载请注明出处:双栈排序,如何分摊秘密

关键词:

上一篇:本剧最强者的烦恼,我的英雄学院

下一篇:没有了