- 博客(35)
- 收藏
- 关注
RSS订阅原创 安全多方计算基础——秘密分享的两种方案
秘密分享(Secret Sharing):Shamir阈值秘密分享方案：该方案基于拉格朗日插值法，支持n个参与方中的任意t个可以联合解开秘密数据。A的目的是将其秘密数据a0a_0a0共享给S1,S2,⋯ ,SnS_1,S_2,\cdots,S_nS1,S2,⋯,Sn，那么他先生成一个t−1t-1t−1次多项式f(x)=a0+a1x+a2x2+⋯+at−1xt−1f(x)=a_0+a_1x+a_2x^2+\cdots+a_{t-1}x^{t-1}f(x)=a0+a1x+a2x2+⋯+at−
2021-09-07 23:11:55
1392
原创 安全多方计算基础——ABY框架（Arithmetic部分）
今天看了秘密分享架构中的ABY架构，尤其看了Arithmetic sharing部分，对于该秘密分享机制下的加法与乘法的计算有了一定的了解，而且了解了如何通过Pailler同态加密方法产生c=axb的三元组。但是对于OT-Base产生三元组的方法不太了解，明天会对非对称加密体系，安全分享公钥的方法还有Diffie-Hellman算法进行学习以求更加熟悉OT-Base办法也欢迎各位大佬光临我的博客啦！1). Share Semantics:1. Shared values:对于一个数xxx的l字节Ar
2021-09-07 23:07:55
3590
1
原创 点分治 水题集合
由于考场上想出点分治可是不会写（2333 蒟蒻花了一天写点分治qwq 3365: [Usaco2004 Feb]Distance Statistics 路程统计Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 389 Solved: 224[Submit][Status][Discuss]Descript...
2018-04-04 20:12:33
217
转载 概率期望动态规划
原文地址：https://www.cnblogs.com/Paul-Guderian/p/7624039.html 虽然概率DP有许多数学期望的知识，但是终究无法偏离动态规划的主题。动态规划该有的特点继续保留，另外增添了一些概率期望的神秘色彩。1~8题出处：hdu4576 poj2096 zoj3329 &...
2018-03-21 11:05:26
760
原创 [JXOI2018模拟]攻略世界树 网络流+建图
BackgroundT3Description这是在ALO世界线上。为了帮助桐子救出本子娜，ALfheim Online的多个工会展开了针对世界树的攻略活动。但是在攻略之前，必须策划好进攻方案。策划进攻方案之前也要先完成基础人员分组。在ALO中的小组分配中大致有四种定位，队长，战士，牧师，法爷。一个标准的小队应当拥有这四种人至少...
2018-03-16 10:33:49
400
原创 [JXOI2018模拟] way 树形dp+启发式合并
题目大意：给n个点的有根树，每个点有个权值和大小，q个询问，每个询问为x，s，意为在x子树中，选出大小之和不超过s的点，其中最大权值和是多少。考场上写个暴力，考后顺便就学了启发式合并。 启发式合并也就是一种思想，即把小的合并到大的上去，可以优化时间复杂度。 每次直接把重儿子的dp数组赋给该点，然后再对轻儿子进行背包#include<bits/stdc++.h>#def...
2018-03-14 09:20:39
270
原创 [CF600E] Lomsat gelral 树上启发式合并
树上启发式合并qwq，一听就是很高级的算法，其实也不难。 这个算法主要也只能应用于：子树统计无修改操作算法实现过程首先进行轻重链剖分，和树剖不同的是，我们每次先dfs轻儿子，暴力统计答案大小，并且暴力删除轻儿子产生的影响。最后dfs重儿子，就是为了保留下重儿子的影响。 那时间复杂度为什么是对的呢？ 只有dfs到轻边时，才会将轻边的子树中合并到上一级的重链，树链剖分...
2018-03-14 07:50:06
277
原创 [BZOJ1503]郁闷的出纳员 动态开点权值线段树模板
自己摸索着写的指针版动态开点权值线段树，也没有那么毒瘤。。 对于提高或者降低工资，我们可以移动最低工资线，同时记录工资变化多少用于对新人的处理，那么就不用对每个人的工资进行操作了。特别的，对于减工资的操作，我们可以写一个clear函数，把[-N，最低工资线-1]的所有节点全部赋为0，意思是把所有低于工资线的员工删掉。 最终离职的员工=总的加入的员工-最终剩下的员工#include<...
2018-03-10 09:22:08
459
转载 priority_queue 优先队列 STL
C++优先队列的基本使用方法 #include<iostream> #include<functional> #include<queue>using namespace std;struct node{ friend bool operator< (node n1, no...
2018-02-22 10:58:33
177
转载 期望&概率dp总结
原文地址：http://blog.csdn.net/qq_31759205/article/details/54730101 总算刷完kuangbin期望&概率专题了，下面总结一下心得和题解！1.期望dp期望dp通常逆推，即从结果推向初始状态，也可以用记忆化搜索进行dp；E=Σp1*(E1+X1)+Σp2*(E+X2)其中E为当前状态的期望，E1为下一个状态的期望，p...
2018-02-13 10:32:51
542
转载 贪心法求树的最小支配集,最小点覆盖,最大独立集
原文地址（转自 Ashly的博客）定义:最小支配集:对于图G = (V, E) 来说,最小支配集指的是从 V 中取尽量少的点组成一个集合, 使得 V 中剩余的点都与取出来的点有边相连.也就是说,设 V’ 是图的一个支配集,则对于图中的任意一个顶点 u ,要么属于集合 V’, 要么与 V’ 中的顶点相邻. 在 V’ 中除去任何元素后 V’ 不再是支配集, 则支配集 V’ 是极小支配集.称G 的...
2018-02-08 14:46:36
243
原创 [BZOJ3262]陌上花开 三维偏序 CDQ分治+树状数组 模板
cdq分治似乎是一种特殊的分治，一般的分治中[l,mid]与[mid+1,r]是基本上没有关系的，然而cdq分治中[l,mid]中可能会对[mid+1,r]的答案造成影响。我们可以运用排序、数据结构或者cdq来进行降维操作。cdq分治的框架(下文代码转自Dirge的博客)：void cdq(int l,int r){ if(l==r) return; int mid=(...
2018-02-06 11:30:58
248
原创 [BZOJ3155]Preprefix sum
题目要求的是∑i=1n∑j=1iaj'>∑i=1n∑j=1iaj∑i=1n∑j=1iaj\sum\limits_{i=1}^n\sum\limits_{j=1}^ia_j 原式=∑j=1n∑i=jnaj=∑j=1n(n−j+1)∗aj=n∗∑j=1naj−&
2018-01-30 20:12:01
176
原创 [BZOJ2179]大整数乘法 快速傅里叶变换
看了下menci大佬的博客，虽然看那么一点懂，然而还是毅然决然地决定背代码2333qwq 模板源自hzwer神犇，50行多厉害！#include #define N 131072#define pi acos(-1)#define ll long longusing namespace std;typedef complexdouble> E;int n,m,L;char ch
2018-01-30 18:18:15
359
原创 [BZOJ1174] Toponyms 字典树模板
刚刚学字典树，于是乎打了一个模板。不得不说好像会卡空间。。反正写了一个错误的代码2333 Trie树数组版：#include#define maxn 500010using namespace std;int trie[maxn][53],f[maxn],sz=1,ans,n;string s;void add(){ int rt=0; for(int i=0
2018-01-24 11:09:13
275
原创 [BZOJ1305] dance 最大流+二分
据说这是一种套路qwq（雾 首先拆点，把每一个人拆成‘喜欢点’和‘不喜欢点’，从每个男生的‘喜欢点’向自己的‘不喜欢点’连接容量为k的边，从每个女生的‘不喜欢点’向每个女生连接容量为k的边。对于男生i喜欢男生j，由男生i的‘喜欢点’向女生j的‘喜欢点’连接容量为1的点（因为两人只能跳1首歌）。对于男生i不喜欢女生j，由男生i的’不喜欢点’向女生j的‘不喜欢点’连接一条容量为1的边。 接下来，从
2018-01-23 20:40:16
156
原创 [BZOJ2427] 软件安装 tarjan缩点+树形背包
这题显然是背包，然而我们发现连边后会存在强连通分量，而由于有奥妙重重的依赖关系，所以当我们选择强连通分量中某个点的时候，整个强连通分量都要选。所以我们缩点，用一虚拟源点向入度为0的点连边，跑树形背包就行了#include#include#include#include#include#include#define maxn 120#define maxm 510using
2018-01-19 10:35:25
250
原创 [BZOJ1452] Count 二维树状数组
随便翻一道题目，然后是二维树状数组 实际上和普通的树状数组也是差不多的 也是对两维进行lowbit然后操作 求某一个矩形容斥一下就行了#include#define maxn 310#define maxc 110using namespace std;int n,q,m,co[maxn][maxn];int lowbit(int v) {return v&(-v);}str
2018-01-19 08:28:06
269
原创 [BZOJ1565]植物大战僵尸 最大权闭合图
BZOJ1565 题目有点长qwq，读了很久才看懂。 这似乎是一道最大权闭合图的裸题，但是我们发现存在植物互相保护这种情况，即建出来的图不一定是DAG。那么我们可以拓扑排序找环，然后把环忽略。然后把不可攻击的点（即环上的点）不与虚拟源点和虚拟汇点连边，那么就不会影响答案了。 这题也更加加深了对该建模方式的理解，即如果需要获得正权的收益，且该点通过奇妙重重的方式连接到对面（负权点），那么一定要
2018-01-18 15:59:18
322
原创 [BZOJ1468]Tree 点分治模板
点分治是针对树上路径所提出的算法. 首先先找重心,重心指的是把该点删去使得各连通块大小最大值最小的点. 每一条路径都有且只有两种情况: 1. 经过重心,这里我们直接每次更新deep值,直接算.如果存在某个i,j其到重心的路径有重合,即这是一条非简单路径,那么我们递归子问题然后减去就行,也算是一种容斥吧 2. 不经过重心,直接递归求解了. BZOJ1468#include#inclu
2018-01-12 10:55:00
169
原创 [DP]斜率优化学习小结
蒟蒻花了一个晚上研究斜率优化qwq 不过大概还是搞明白了.斜率优化是啥其实是一种优化动态规划的方法.我认为斜率优化是建立在决策单调性的基础上的.如对于形如这样的状态转移方程f[i]=min/max(f[j]+xxx(ji))f[i]= min/max(f[j]+xxx(j其复杂度为O(n2)O(n^2)而我们通过化式子来得到无论对于哪一个i,在j点进行决策一定要比k点进行决策更优,可以
2018-01-08 09:26:45
261
原创 [BZOJ1497] 最大权闭合子图+最小割+最大流
BZOJ1497 好吧，看到ARC085的E题好像是个最大权闭合子图，于是就去学习了一下，顺便复习一下dinic，最大流最小割定理。 每个客户群向需要选的两个类型连边，然后由原点向客户连边权为获利的边，基站向汇点连边权为所需消耗价格的边，所有正权值之和减去最小割就是答案了，画图显然。 最小割可以转化为最大流，于是乎跑一个dinic模板就行了 #include #incl
2018-01-06 11:08:59
250
原创 [NOIP模拟] 跨时代 状压DP
题意(背景省略) 演唱会的第一站，公司临时跟当地的消防局借了n个栏杆，打算用这n个栏杆围出一个矩形。而麻烦的是，这些栏杆有长有短，这就给围场地带来了一些难度。(每个栅栏可用可不用) 所以公司聘请你来写一个程序，计算用这n个栏杆最多围出面积多大的矩形。 数据范围: n⩽16n\leqslant16 li⩽15 li\leqslant15Solutionn⩽16n\leqslan
2018-01-06 10:42:44
177
原创 [BZOJ1858]序列操作 线段树
BZOJ1858 这题是不错的线段树练习题. 注意查询的时候返回一个节点而不是一个具体的数,否则无法做到合并信息并上传. 还好一个小时就写完啦#include#include#include#include#include#include#define maxn 100010using namespace std;int n,m,a[maxn];struct tree{
2018-01-05 16:27:31
280
原创 [BZOJ1412]狼和羊的故事
BZOJ1412 其实很容易想到割啦.然后再想一想就可以想到最小割啦. 割就是你选定一些边,把这些边去掉使得源点与汇点不连通.完全符合题目的意思呀. 又最小割等于最大流,跑一遍最大流就行啦#include#include#include#include#include#include#define maxn 10500#define inf 0x3f3f3f3fusi
2018-01-05 16:22:30
228
原创 [BZOJ2763] 飞行路线 dijkstra+堆
BZOJ2763 我们发现该题最棘手的问题就是如何处理k了. 于是乎我们可以这样考虑,把一个点拆成k个点,即k层.其中第i层第j个点表示当Alice和Bob花费了i个免费机会,到达了j点. 那么连边跑一个dijkstra就行啦
2018-01-05 16:08:48
205
原创 [Atcoder ARC085 F] NRE 线段树优化dp
Atcoder ARC085 F NRE 海明距离好像不知道是什么东西，这道题目还是直接看DOFY dalao的题解的。 似乎这道题目只能有一种设计状态的方法，其他方法都会GG。 设f[i][j]表示[a(i+1),aj]中全部填1，[1,i]的海明距离最小值。 好吧状态有点绕，不过我们考虑区间覆盖，覆盖某个区间的时候可能会覆盖到后面的一段连续的数，所以可以如此设计状态（骚）
2018-01-02 18:57:18
353
原创 [Luogu2014]选课 树形DP
Luogu2014 其实一眼就秒掉了这个树形dp，然后想了想转移，然而有些细节还是调了很久 首先整个图不一定是联通的，那么我们考虑把森林转化为树，即建立一个”源点“，然后把0向所有入度为0的点加边，就变成了一棵树。 我们又发现一个节点可能有多个儿子，不好处理，于是我们可以用一个惯用的方法——多叉树转二叉树，也可以叫左儿子右兄弟表示。顾名思义，新树节点的左儿子是原树的儿子，新树节点的右儿子是这个
2018-01-02 11:45:19
211
原创 [BZOJ2301]Problem b 莫比乌斯反演+容斥
题意明确，就是求∑i=ab∑j=cdgcd(i,j)==k\sum\limits_{i=a}^{b}\sum\limits_{j=c}^{d}gcd(i,j)==k 首先容易发现容斥定理，转化为求 ∑i=1n∑j=1mgcd(i,j)==k\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}gcd(i,j)==k 我们设f(d)=∑i=1n∑j=1m(gcd(i
2017-12-31 16:10:31
277
原创 [网络流24题] 软件补丁问题
Luogu2761 似乎这不是一道网络流的题目qwq，发现n很小，于是我们可以考虑状态压缩，也只是2202^{20}种状态，对于状态a可以到达状态b，则连接一条时间的边。跑一遍spfa就行了 但是这题更加坑的是卡空间，我们发现一条一条边建了之后空间会炸。于是乎用每次spfa时暴力枚举m种补丁， 免去建边的空间（传说中的时间换空间？2333)
2017-12-27 10:16:00
259
原创 [网络流24题] 星际转移问题
Luogu2754 由于这题每一天飞船所在的位置都不一样，所以一开始想了很久，不知道如何建边，不过后来突然一想，既然每天都不一样那就以每天建边。 1. 把源点向每天的地球连infinf边，每天的月球向汇点连infinf边 2. 对于第ii天的jj星球，向i+1i+1天的jj星球连infinf边 3. 对于第ii天aa可以到达bb那么连接一条从ii天aa星到i+1i+1天bb星的权值为容量的边
2017-12-27 10:14:06
236
原创 [Atcoder ARC088 D]Wide Flip
Atcoder ARC 088 D 想了半个小时的结论，结果没想出来。 我们可以考虑第kk位和第k+1k+1位，若这两位不同的话，说明我们至少要进行一次不同时包括这两个字符的flipflip操作，而观察这个操作，flipflip[1,m]和flipflip[m+1,n]的本质是相同的。所以我们设函数F(S)=min(max(k,n−k))F(S)=min(max(k,n-k)) 我们可以发现K
2017-12-27 10:13:16
528
原创 [网络流24题]最长上升子序列问题
PowerOj1741 对于第一个小问我们可以跑一遍dp，求得ans1，和f[]数组，f[i]表示以i结尾的最长上升子序列 对于第二问和第三问，我们考虑把第i个数拆成两个点，ai与bi。 考虑这样建边： 1. 连接ai，bi，限制为1的边 2. 如果f[i]等于ans1，那么连接bi，t，限制为1的边 3. 如果f[i]等于1，连接s，ai，限制为1的边 4. 如果f[i]=f[j]+
2017-12-21 09:59:58
294
原创 [BZOJ1801] 中国象棋 dp
我们可以考虑到每一列都是互不影响的 于是乎可以定义状态f[i][j][k]f[i][j][k]表示第i行，j列已经被填了两次，k列已经被填了一次，转移则可以直接由上一行转移过来。 1. 不填 即f[i][j][k]=f[i−1][j][k]f[i][j][k]=f[i-1][j][k] 2. 填一个 f[i][j][k]+=f[i−1][j−1][k+1]∗(k+1)f[i][j][k]
2017-12-21 09:56:19
180
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人