正文

ZJOI2017 Day1

IP云
IP云V管理员/1 阅读
11/30
小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

私のZJOI

Day1

2017-3-21 07:52:53

有人在暴力膜

苟……

富贵

无相忘

ZJOI2017交流群 133135071

如果你足够厉害

如果你足够厉害

如果你足够厉害

其实完全可以看那些大佬的ppt ，分享见网址大佬ppt。

ps：其实本人就是抄抄他们ppt，下午最后一节课实在想睡觉就没有认真听了。。。滑稽.jpg

只不过好像有人抄我博客的样子……这也是一种荣幸嘛……好不容易写篇博客然后被抄，也在一种层面上说明我写的博客写得好吧。【逃……

但还是认准我的博客正文链接哦Hash大法好

以下正文

搜索专题

学军中学 周子鑫

题目传送门

  • NOIP2012 普及组 文化之旅
  • NOIP2015 提高组 斗地主
  • NOI2010 方程的解数
  • ZJOI2005 九数码游戏
  • Rikka with Sequence II
  • 十五数码问题
  • SCOI2005 骑士精神
  • NOIP2009 靶型数独
  • hdu4979 A simple math problem
  • N皇后问题
  • NOI2003 智破连环阵
  • SDOI2015 排序
  • 围栏问题by dzy
  • SRM555 MapGuessing（超级图灵机）
  • NOI1997 文件匹配
  • NOI1998 软件安装盘
  • NOI1999 生日蛋糕
  • NOI2000 算符破译
  • ZJOI2014 璀灿光华
  • ZJOI2014 2048

什么是搜索？-Was ist das?

存在

  • 枚举
  • DFS
  • BFS
  • A*
  • 回溯
  • 蒙特卡洛树
  • 散列函数
  • ……

(╯‵□′)╯︵┻━┻瞎几把玩意儿！！

题目

NOIP2012 普及组 文化之旅

（听说讲课者当年只考了30分）

这道题第一眼看上去是NPC，这道题真的是NPC么。

是的。。

根据CCF的官方数据，有100中错误的方法能过掉这道题。比如，只考虑相邻两个城市之间的文化是否排斥，或者只考虑一条合法路径。

正解：乱搜。

乱搞方法

  • 搜索到一条路径
  • 倒着搜
  • 去掉条件的一些条件
NOIP2015 提高组 斗地主

DFS过程中，不考虑单拍、对子、三个或者四个；搜索顺序没关系，最后贪心再来。

搜索中的通用优化

1.搜索折半搜索

例子： 双向广搜 从起点和终点交替搜；或者从两边搜索来。

NOI2010 方程的解数

将后面三项移到等式右边，然后前面部分的M^3的时间内用hash存答案，后面三份也同样，然后求出答案。

(可以用 map )

ZJOI2005 九数码游戏

从给出的矩阵和需要变成的矩阵，然后用hash记录状态；如果出现相同的hash，那么久搜到了。

Pikka with Sequence II

Way One

枚举两个点，作为中位数的贡献点。 

1 2 3 4 5 6 7 8

      ↑     ↑

中间的点都不用。但将左右两边放在一个集合。并且再赋一个 ±1 的权值（中位数左边赋成 1 ，右边是 -1 .然后就可以在集合中折半搜索。[复杂度明显对了]

Way Two

枚举选 i 个数，把序列分成两半，然后就知道中位数落在那个位置，然后就可以和刚才一样用归并【其实并没有听懂】

2.启发式搜索

  • A*——BFS的启发式版本
  • IDA*——前者的迭代加深版

设置搜索上界，先看看搜十步能不能搜到答案；如果不能搜到，那就提高阈值。

引入估价函数，对每一个状态 x ， f(x) = g(x) + h(x) ，其中 g(x) 是目前状态的实际代价，而 h(x) 是目前状态到目标状态的估计代价。

为了保证正确性， h(x) 不能大于当前状态到目标状态的最优值。

特殊的，当 h(x) = 0 时，A* 和 IDA* 算法退化成一般的BFS和迭代加深

十五数码问题（八数码问题的up版） 
1  2  3  4

5  6  7  8

9  10 11 12

13 14    15

一次移动只可能把有数字的移到空格，所以估价函数就用曼哈顿距离。

（限制：在……步数输出 -1 之类的条件出现，那么

一定是IDA*！！！！！！

SCOI2005 骑士精神

玄学IDA*

3.Dancing Links(舞蹈链)

简介：

解决一类覆盖问题的通用框架，本质上只是常数优化，但非常强。

在交互式题目中还原上面的操作

双向链表删除节点操作 

L[R[x]] <- L[x]

R[L[x]] <- R[x]

撤销删除操作： 

L[R[x]] <- x

R[L[x]] <- x
题目（精确覆盖）

给定一个由0和1组成的矩阵，问是否能找到一个行的集合，使得集合中的集合每一列都恰好都包含一个1.

Tag:精确覆盖（DLX算法）

用Dangcing Links 可以常数优化。

什么玩意儿(╯‵□′)╯︵┻━┻

用 U，D，L，R 四个指针来表示每个1在矩阵中的关系

NOIP2009 靶型数独
hdu4979 A simple math problem
N皇后问题

方案数：用公式 O(1)

位运算优化：

  1. Matrix67博客

    可以跑到N <= 13
  2. N<=1000爬山，模拟退火？？(╯‵□′)╯︵┻━┻
  3. DLX算法：

    每一行每一列的限制是精确覆盖，而对角线上是 对角线上最多有一个 。于是方法就是先不管斜对角线的列[不用保证至少一个]，所以只要搜索前面的精确覆盖。

4.剪枝

NOI2003 智破连环阵
  1. dp求估价函数，
SDOI2015 排序

其实本道题只用看做一个线段树一样的东西。。交换内外层对方案数没有影响。剪枝如下：

  1. 大层是连续递增时，小块不用交换。
  2. 选择合法的交换方法就递归下去。

复杂度： T(4n*2)

围栏问题by dzy

DLX

SRM555 MapGuessing（超级图灵机）

集训队作业

NOI1997 文件匹配
NOI1998 软件安装盘
NOI1999 生日蛋糕
NOI2000 算符破译

一块块的数字位数可以在枚举算符位置之后进行可行性剪枝。

ZJOI2014 璀灿光华
ZJOI2014 2048

写一个AI？？恐惧……

但是直接爆搜，记忆化状态，于是在20s时间和1G~2G内存中，A掉65536.

STL

杭州二中 陆宇暄

2017-3-21 14:00:41

题目传送门

  • BZOJ 3545 [ONTAK2012]Peaks
  • Codeforces Round#85 D
  • HNOI2009 梦幻布丁改变

默认该弄的东西： 

#include<bits/std++.h>

using namespace std;

定义

iterator 迭代器(iter)

link 指针(lk)

function 函数(func)

node 指针(node)

（iterator和link差不多的）

不常用的算法库函数

1.unique

去重 

lk unique( lk begin, lk end );

2.nth_element

求出第k小的数 

lk nth_element( lk begin, lk nth, lk end, func less );

3.自定义一个函数： 

struct ex {

    bool operator() (const node& a, const node& b) {

        ……

    }

}

4.binary_search

返回bool类型

5.equal_range 

pair<lk,lk>equal_range(lk begin, lk end, node val, func less );

6.lower_bound和upper_bound

神奇的东西

1.priority_queue

变成小根堆的方法： 

priority_queue< int, vector<int>, greater<int> > Q;

2.set&map

平衡树用set实现时，重载运算符。

遍历map： 

for( set<node>::iterator it = S.begin(); it != S.end(); ++ it )

启发式合并。

3.vector

vector的push_back()实现方式：

先开一个小的数组，push_back()到一定程度之后，那么就再开辟一个两倍的数组，然后copy进去。

所以复杂度是均摊 O(1)

insert()操作

1e5次的vector的insert()和7e5次set的insert()速度差不多

但是开了O2并没有变快。

更加神奇的东西 

__gnu_cxx::hash_set

__gnu_cxx::hash_map

__gnu_cxx::rope

__gnu_pbds::priority_queue

__gnu_pbds::tree

1.__gnu_cxx::hash_set

hash实现set

头文件： 

include<ext/hash_set>

可以直接使用成set，但是唯一的区别是用iterator遍历的时候不是有序的

（然而在hash表上维护一个链表，可以做到 O(n) 的遍历）

然而，hash_set的实现时：

  1. 开一个大小为20的桶
  2. 如果冲突，那么就再开一个40的桶，重新hash一遍

hash表启发式合并，复杂度 O(logn) 

hash_set< node, hash_er, e_qual >

func::hash_er{

    ……

}

e_qual{

    ……

}

__hash_map同理

常数不小，但是比set大。但还是建议自己写。

2.__gnu_cxx::rope 

include<ext/rope>

rope<node>

可支持一堆操作的字符串

可持久化平衡树维护的序列

操作： 

void push( node x )

void insert( int pos, node x )

void erase( int pos, node x )

void replace( int pos, node x )

rope <node> substr( int pos, int len )

node at( int x )

但是rope的复杂度是 O(log(len))

【感觉和string类差不多的操作】

只要存一下历史版本就可以持久化

可以当做可持久化数组用（但是常数有点大，内存要32倍用）

__gnu_pbd::priority_queue 

include<ext/pb_ds/priority_queue.hpp>

_gnu_pbds::priority_queue< node, less<node>, head_tag >

可以搞各种各样的堆。

heap_tag默认pairing_heap_tag

用法和std::priority_queue 

a.join(b)

把a和b合并变成a，并把b清空（复杂度 O(logn) ） 

point_iterator it = a.push(x)

a.erease(iter)

a.modify(iter, x)

事实上可以自己写个左偏树，但常数比手写大一点。

__gnu_pbds::tree 

include<ext/pb_ds/assoc_container.hpp>

include<ext/pb_ds/tree_policy.hpp>


tree<key,value,less<key>,tag=rb_tree_tag,tree_order_statistics_node_update >

//黑人问号.jpg

同样 

a.join(b)//同__gnu_pbds::priority_queue中的a.join(b)

a.split(key, b)//把b清空，然后把a中大于key的元素拆分到b

例题

二维点修改矩形求和
给定一个序列，

支持以下操作：修改一个元素，求第l个到第r个最早的一个w的位置 

map< int, set< int > >
支持插入修改覆盖翻转循环位移的动态字符串 
__gnu_cxx::rope

覆盖的话，维护一个全A的rope，全B的rope，全C的rope……

翻转就……维护两个rope，一正一反

BZOJ 3545 [ONTAK2012]Peaks 
__gnu_pbds::tree
CF85D
HNOI2009梦幻布丁 
hash_set<int>

splay、线段树的启发式合并

水题选讲

杭州二中 吴某某

2017-3-21 16:09:20

1.
  • 你有一排 n 个水杯，每个水杯最多能装 mi 的水，初始有 si 的水量，每秒增加 ri 的水量
  • Q 次询问，每次询问在事件 t 把[ l, r ]之间的水杯里的水喝完，并回答喝了多少水。

segment tree

相同时间被喝完的一段是可以通过二位数电直接计算这一段的贡献。

喝完的水杯可以缩在一起

每次询问之前将首尾的拆开

2.
  • n 个点（ x1, y1 )
  • 可以再每个点上建一个建筑，这个建筑是以该店为斜边中心的等腰直角三角形，并且斜边必须平行于 x 轴或 y 轴。
  • 所有建筑的边长必须一样，问最大边长
  • n <= 60

首先二分答案。

然后每个节点拆分成四个直角三角形。

然后简单

3.
  • 你有一个 n * m 的01矩阵
  • 你可以翻转任意一行或者任意一列
  • 最小化最终矩阵中1的个数
  • n <=20, m <=10^5
4.
  • 给一张有向图，Alex要从点1逃到点 n ，Bob在一些边上设卡。
  • 要求每个从点1到点 n 的路径（路径支持经过重复点）都只有一条边设卡， 每条边设卡有代价，问最小代价。
  • n <=200, m <=2000

直接跑最小割，但是要建立一条反向的且代价无穷大的边。

5.
  • 给你一个字符串集合X
  • 等几率从字符串集合中挑出 K 个字符串（可以重复）并拼成一个大字符串
  • 问 S 在大字符串中的期望出现次数
  • | S | <= 500, | X | <= 50, | Xi | <= 50, K <= 1e12

暴力DP，f(i, j)balabala……

然而后面的就是Matrix Fast Power了

或者跑一个BM（什么东西(╯‵□′)╯︵┻━┻）

6.
  • 给你一个DAG，有些节点是终止节点
  • 求一个字符串的后缀自动机使得与该DAG同构
  • 保证存在解
  • n <= 200, m <= 2000

首先，DAG是什么？？

考虑SAM的性质

显然……

我实在太困了，遂停止记笔记。去看ppt吧

大佬的ppt

相关阅读

目录[+]