[HNSDFZ #3]胡策记

这场互测比Round2简单了很多。

题目下载

感觉今天真的很欢乐啊……四个题目中有两个题目数据错误，结果就剩下了我的题(C)和riteme的题(A)有效……

A.密码锁

出题人riteme，编译原理。 之前和riteme回家途中商议好：只要是我们两个出A题，必出编译原理。这次他果出编译原理……

正合我意，这题码了一天QAQ

简化版题意

给定一个表达式，仅有布尔型变量和二元运算符逻辑与“&”、逻辑或“|”、异或“^”、单元运算符非“!”和小括号。变量名两两不同。 求有多少组变量的值，使得表达式的值为真。 例如$a|b|c$有7种方式为真：$(1,1,1)(1,1,0)(1,0,1)(0,1,1)(1,0,0)(0,1,0)(0,0,1)$。

搞法

因为这个题我会搞，所以我也就没有想那些特殊数据怎么干。

我的方法：先把中缀表达式（输入）变成后缀表达式，然后把后缀表达式变成表达式树。 对于非运算，可以在起作用的节点上打标记。

建完树之后进行搜索。我的做法，以使$x$节点为真举例：

用DP(节点x,取值w)表示某个节点$x$的值为对应的$w$。 那么： （假设$x$节点是或运算。）

DP(node,1)=
DP(left,1)*DP(right,1)+         //左子树为真的方案数*右子树为真的方案数
DP(left,1)*DP(right,0)+
DP(left,0)*DP(right,1);

类似地可以做出其他情况。这个函数的代码大约20行。

最开始拿这个程序去跑。结果面对极端数据（全是或）直接TLE。想了一下，然后记忆化搜索。AC。

正解

riteme的正解是不转后缀表达式。用现在编译器流行的搞法来做。 由于std写得比较丑，我的搞法在最后一个数据点比std跑得快0.2s.

代码

我的搞法： http://paste.ubuntu.com/18792757/ （说实话我的代码风格真丑）

B.Unstring

简化版题意

给定确定的主串和带'?'的模式串。 '?'可以匹配任意字符。问主串能否被匹配。

搞法

这题一看就知道是AC自动机，然后就不写了。直接交C++的<regex>正则扩展。 结果WA？然后发现Link的数据有多组字符串，但是题目里面并没有写有多组数据。

于是题目报废。

奇技淫巧

yy出一个奇技淫巧。

对于模式串，我们取三个点：起点、随机点、终点。扫一遍主串，如果这三个点在以$\alpha$为起点处被匹配上，那么我们直接暴力匹配从$\alpha$开始的部分。

如果扫完了主串仍然没有完全匹配的字符串，就是没法匹配。

因为随机点的存在，这个搞法出题人难以卡掉。因为最坏情况，三个点都要被匹配最多次，所以主串必须是模式串的大量重复（但有些地方不相同）。于是又降低了复杂度。

随便写了40行，一测WA了4个点。估计是边界没有讨论好。 跑得比香港记者还快。

总结出做Link的题目的正确姿势：

Step1. 看能不能用C++模板/标准扩展做掉
Step2. 想一些奇技淫巧
Step3. 看数据有没有问题

C.赌徒

我出的水题一道，意在使他们学习一下矩阵加速递推。

简化版题意

一棵树，节点$x$在第$n$天满足权值$F_n=2F_{n-2}+3F_{n-1}$。每个节点有自己对应的$F_1,F_2$。 输入$day$，求第$day$天的节点的权值和最大的简单路径。

所有的东西都是正整数。

分析

首先构造矩阵来加速递推，然后DFS。

一眼看出，一定是从叶子节点走到另一个叶子节点。 DFS：计算出以自己为LCA的最大权值链的权值，然后返回经过自己的到叶子节点的最大权值链。

代码

http://paste.ubuntu.com/18793629/

D.星际争霸

简化版题意

一棵$n$个点的树，边有代价，叶子节点有收益。走到叶子节点之后走回根节点。 多组数据，每组数据有限制：不允许走到某个节点。

在代价限制内最大化收益。

考时想法

题目太长了，先拆题。

考虑所有节点都能走的情况。

DFS一遍，化为数组：f[i]=(代价,收益)

目标变成：在代价范围内找到最大收益。 0-1背包。复杂度$O\left(nt\right)$。

再考虑有节点不能走的情况。 则有一些元素失效。由于DFS将树映射成区间，那么这些失效元素在数组中应该是相邻的。暴力标记这些元素。背包时不取用。

$m$次背包。复杂度$O\left(mnt\right)=25000000000$。

理论上来说要挂。于是不写了，码A题去QAQ

Link和riteme写了这个题，然而都只有25pts。riteme找出数据有问题，于是这题也报废了#喷

标解

确实是背包，但是对于有的地方不能走的情况做了优化。

后记

下次胡策我抽中出A题 23333