Meet in the Middle

-
课件：MITM

blue  
MEET IN THE MIDDLE  
问题  
暴力  
优化的暴力  
MITM  
正解  
MITM  
Meet-in-the-Middle.  
就是个暴力。但是跑得比初级的暴力要快很多。  
核心思想是分治。将大问题转化为两个小问题来暴力求解。  
中间相遇。  
什么时候可以使用MITM？  
问题可以“在中间相遇”的时候。  
BFS  
一般来说，广搜的搜索范围随着搜索层数递增。  
那么，我们可以采用“双向广搜”的方式，来减少一些不必要  
的搜索过程。  
T
S
T
S
MITM  
切题时间到QAQ  
例题  
你我只隔六步  
给定一个社交网络（无向图）。  
给出两个人的名字，回答这两个人是否最多相隔6个好友。  
MITM  
双向搜索。  
在BFS的过程中，最多拓展3层。  
搜索图  
分赃  
你和blue合伙抢劫土豪Link，获得了40个金币，每个金币有相  
应的价值。  
询问是否能把所有金币分成两堆，价值之和相同。  
暴力  
MITM  
离散对数  
暴力  
MITM  
负数次幂  
blue  
END  
网上没有找到多少关于MITM的资料，找到了也只有“中途相遇攻击”……
然后在Google上找到一篇英文文档：http://www.infoarena.ro/blog/meet-in-the-middle
确实写得很好。MITM的原理就是，优化指数级暴力，尝试用双向搜索的方法解决问题。
具体见课件。

评论

发表评论

此博客中的热门博文

高中地理必修一知识点总结

-
图片
1 高中地理必修一知识点 宇宙中的地球 1.1地球的宇宙环境 天体系统：天体之间因万有引力相互吸引和相互绕转形成天体系统。结构层次(略) 可见宇宙：也称为“已知宇宙”，是指人类已经观测到的有限宇宙，半径约为140亿光年。 地球存在生命的条件： 外部条件：稳定的太阳光照 大、小行星各行其道，使地球处于比较安全的宇宙环境中 内部条件：日地距离适中(1.5亿千米)——适宜的温度 地球体积质量适中且原始大气经长期演化—适于生物呼吸的大气 地球内部水汽逸出形成水圈 1.2太阳对地球的影响 一、太阳辐射：太阳以电磁波的形式向宇宙空间放射的能量。 1能量来源：太阳中心的核聚变反应(4个氢原子核聚变成氦原子核，并放出大量能量); 2特点：太阳辐射是短波辐射，能量主要集中在波长较短的可见光部分; 3意义：维持地表温度，地球上大气运动、水循环和生命活动等运动的主要动力，人类生产和生活的主要能源。 太阳常数：表示太阳辐射能到达大气层上界的能量指标，大小为8.24焦/cm2.分。 二：太阳活动对地球的影响 1太阳的外部结构：指太阳的大气结构，从里到外分为光球、色球和日冕三层 2对地球的影响：(太阳黑子是太阳活动强弱的标志，周期约为11年) 1.3地球的运动 一、地球公转和自转的基本特征 公转 自转 轨道 近似正圆的椭圆 方向 自西向东（北天极上空看逆时针） 自西向东（北极上空看逆时针，南极上空看顺时针） 周期 恒星年（365d6h9m10s） 恒星日（23时56分4秒）一真正周期 角速度 平均1º/日 近日点（1月初）一最快远日点（7月初）一最慢 各地相等，每小时15º（两极除外）
阅读全文

【CF961F】k-substrings

-
图片
【CF961F】k-substrings 题意 给定一个长度为  n  的字符串  S 我们设  S  的  k-子串  是  S[k … n - k + 1] ，设字符串  t  是字符串  T  的  奇正确前后缀  当且仅当满足以下条件： t  长度为奇数 |t| < |T| t  是  T  的  border （既是前缀又是后缀） 对于  k = 1 … n / 2  上取整，求  S  的  k-子串  的最长  奇正确前后缀  长度。无解输出  -1 2 ≤ n ≤ 1,000,000 官方题解 枚举某个前缀（指题目要求的相同前后缀中的前缀）的中心位置  i ，那么对应后缀的中心位置已经确定了（ n - i + 1 ），可以二分答案求出对于每个中心位置  i  最大的符合要求的相同前后缀（设长度为  2 * x + 1 ），然后更新  ans[i - x]  为  2 * x + 1 ；最后把每个  ans[i]  用  ans[i - 1] - 2  尝试更新一下 其实以上做法也基于这个结论？ ans[i - 1] <= ans[i] + 2 ，这个可以容易地用反证法证明（类似  kmp  ） 因此从  ans[(n + 1) / 2]  开始求就行了 参考代码： # pragma GCC optimize( "Ofast,no-stack-protector,unroll-loops,fast-math" ) # pragma GCC target( "sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native" ) # include "bits/stdc++.h" # define mem(x) memset((x), 0, sizeof((x))) # define il __attribute__((always_inline)) using namespace std ; typedef long long ll; typedef long double ld; typedef uns
阅读全文

偷税与漏税的区别

-
图片
偷税是指 纳税人 以 不缴或者少缴税款 为目的，采取各种 不公开 的手段， 隐瞒真实情况 ， 欺骗 税务机关的行为。 （目的不同） 按照新《税收征管法》第六十三条的规定，偷税的手段主要有以下几种： 一是伪造(设立虚假的账簿、记账凭证)、变造(对账簿、记账凭证进行挖补、涂改等)、隐匿和擅自销毁账簿、记账凭证； 二是在账簿上多列支出(以冲抵或减少实际收入)或者不列、少列收入； 三是不按照规定办理纳税申报，经税务机关通知申报仍然拒不申报； 四是进行虚假的纳税申报，即在纳税申报过程中制造虚假情况，比如不如实填写或者提供纳税申报表、财务会计报表及其他的纳税资料等。 对偷税行为，税务机关一经发现，应当追缴其不缴或者少缴的税款和滞纳金，并依照本法的有关规定追究其相应的法律责任。构成偷税罪的，应当依法追究刑事责任。 偷税是指纳税人故意违反税收法规，采用欺骗、隐瞒等方式逃避纳税的违法行为。如为了少缴纳或不缴纳应纳税款。有意少报、瞒报应税项目、销售收入和经营利润；有意虚增成本、乱摊费用，缩小应税所得额；转移财产、收入和利润；伪造、涂改、销毁帐册票据或记账凭证等。 偷税损害了国家利益，触犯了国家法律，情节严重的构成偷税罪，属于破坏社会主义经济秩序罪的一种，对构成偷税罪的要依法惩处。根据 《刑法》 的规定，对于偷税，除了补缴少缴或未缴的税款以外，还要根据情节的轻重分别给予五倍以下的罚款，或者五倍以上的罚金和三年以下的有期徒刑或者三年以上七年以下的有期徒刑。 漏税是纳税人 无意识 地 漏缴或者少缴税款 的行为。 （无意漏了是小事，故意偷税是大事） 漏税是由于纳税人不熟悉税法规定和财务制度，或者由于工作粗心大意等原因造成的。如错用税率，漏报应税项目，少计应税数量，错算销售金额和经营利润等。 漏税与偷税有着性质上的区别，判定漏税的关键是并非故意，因而在处理上也不同。税法规定，对漏税者，税务机关应当令其限期照章补缴所漏税款，逾期未缴的，从漏税之日起，按日加收一定的滞纳金。 1988年12月27日国务院发布的 《关于整顿税收秩序加强税收管理的决定》 规定： 对临时经营者漏税的，可以按照规定扣留其部分货物，限期缴纳； 对逾期仍未缴纳的，经县(市)以上税务局长批准，可以将所扣留的货物变价抵缴其应缴纳的税款、滞纳金和罚款。 要从根本上杜绝
阅读全文