[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(nt)$

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

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

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

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

标解

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

后记

下次胡策我抽中出A题 23333


CC0协议 @ ruanxingzhi 2017. CC0是啥玩意?
Home apps close