注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Yavin(某沙茶的代码库)

Star Wars fan and OIer

 
 
 

日志

 
 

Feyat Cup 1.0 题解发布  

2013-03-22 10:25:23|  分类: 日记 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
下面是tex源码
写了我好久啊

\documentclass[14pt,a4paper]{article}
\usepackage{xeCJK}
\usepackage{syntonly}
\usepackage{fancyhdr}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{hyperref}
\setCJKmainfont{文泉驿微米黑}
\pagestyle{fancy}
\lhead{}
\rhead{无论世界是否破碎,我的心向往未来}

\begin{document}
\title{Feyat Cup 1.0 题解}
\author{wyl8899 \& 法法塔}
\maketitle
本次比赛由法法塔这只大沙茶诚邀noip吧吧主wyl8899携手举办。对前来参加与娱乐的各位表示十分的感谢。

祝贺txhwind借第一题18次hunt和第三题手敲的后缀树以绝对优势获得第一名。

unis(= = 我才不是Delayyy君呢~)是唯一成功地解决了前三题的,在此表示膜拜。

前五名中的剩下三位分别是球威,xyjqjb和vfleaking。\\

一些相关的网址
\begin{enumerate}
\item \href{http://tieba.baidu.com/p/2213561049}{比赛起源}
\item \href{http://tieba.baidu.com/p/2220934247}{比赛预告}
\item \href{http://www.contesthunt.tk:777/Contest/Show/Feyat\%20Cup\%201\%EF\%BC\%8E0}{比赛网址}
\item \href{http://www.contesthunt.tk:777/Contest/Standing/Feyat%20Cup%201%EF%BC%8E0}{比赛结果}
\end{enumerate}


wyl8899写了第一三题的题解,而法法塔则是第二四五题的题解的作者。现在申明题目和题解的版权属于作者,可以随便抄袭和使用。

\newpage

\section{wyl8899的扫把}
\subsection{题目大意}
若干堆石子,两人轮流操作,每次操作可以从以下两种中选择:

\begin{enumerate}
\item 从一堆石子里拿走若干个石子(不能不拿);
\item 把某一个石子堆分成两个非空堆(石子总数是不变的)。
\end{enumerate}

给出一个初始局面,问先手是否有必胜策略。

\subsection{出题思路或题目来源}
本着“我们需要一个送分的Problem A”的想法决定弄一题普通博弈论。到最后从Game Theory里Take-and-Break一节找了一个叫做Lasker's Nim的模型。这就是你们见到的A题。

\subsection{题解}
这题需要选手具备一些比较基础的博弈论知识,包括:
\begin{enumerate}
\item SG函数的定义和意义
\item 多个游戏的和的SG函数是各个游戏的SG函数的xor和
\end{enumerate}

我们假设一堆x个石头(U盘)的SG函数为g(x),那么根据定义,有$g(x)=mex( \{ g(i) | 0 \le i \le x \} \cup \{ g(i) \oplus g(x-i) | 0<i<x \} )$,mex(S)表示不在S中的最小自然数,$\oplus$表示异或。

直接计算是O($n^2$)的,可以TLE。一般来说这种时候就要很果断的开始找规律了,我们来打个表...

\begin{tabular}{|l|l|l|l|l|l|l|l|l|l|l|l|l|l|l|}
\hline
x & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & ... \\
\hline
g(x) & 1 & 2 & 4 & 3 & 5 & 6 & 8 & 7 & 9 & 10 & 12 & 11 & 13 & ...\\
\hline
\end{tabular}

于是发现:

\begin{displaymath}
g(x) = \left\{ \begin{array}{ll}
x-1 & \textrm{if $x\%4=0$}\\
x+1 & \textrm{if $x\%4=3$}\\
x & \textrm{else}
\end{array} \right.
\end{displaymath}

这题就结束了。

\newpage

\section{法法塔的奖励}
\subsection{题目大意}
树上的最长不下降子序列。
\subsection{出题思路或题目来源}
本来是想利用\href{http://main.edu.pl/en/archive/oi/18/rod}{POI18 Tree Rotations 2} 和 \href{http://codeforces.com/problemset/problem/261/D}{Codeforces 160 D Maxim and Increasing Subsequence} 的思想共同出道题的,结果yy了还久都没搞出来,于是就有了这个半生不熟的版本。
\subsection{题解}
让我们思考一下最长不下降子序列怎么做?这是个很经典的动态规划问题。如果不会做的话请前往\href{http://www.baidu.com}{here}。
那么本题的暴力做法就显而易见了,我们按照树的逆拓扑序进行动态规划,记$f_i$表示以点i为根的子树,包含点i的最长不下降子序列的长度。设以点i为根的子树中节点的集合为$Q$,转移方程为:$f_i = max( max_{j\in Q,w_j<=w_i}f_j+1, 1 )$。

考虑优化这个转移:如果是链的话,那么就有两种方法(虽然实质是一样的)
\begin{itemize}
\item 运用单调队列进行优化
\item 运用线段数或数状数组
\end{itemize}

这两种方法在这道题上其实都是可以用的。先考虑第一种方法,如果我们对于每棵子树维护好了单调队列,那么转移可以在$logn$的时间内搞定。但是如何维护呢?对于节点i,最简单的思路是暴力建一棵平衡树,比如说treap和splay,扫描以其为根的子树,将所有f值插入,并维护单调性,这方面的写法可以参见sgu277或者NOI2007 cash一题。结果发现时间复杂度是O($n^2logn$),成功跑得比暴力慢。之所以会这么慢,那是因为已经求出的单调队列用过了就丢掉,实在是太浪费了,对于节点i,单调队列中可能的点,只会是其所有儿子对应的单调队列中的元素再加上自己(这个显然吧)。所以我们要做的,只是将这个点的儿子们的单调队列们进行合并,再加入自己。

所以算法就是平衡树的合并。关于平衡树的合并,有一个很经典的做法——启发式合并。我们合并两棵平衡树时,将个数少的那一边的值一个个暴力取出插入到大的那里面。可以证明这样的总时间复杂度是O($nlog^2n$)。所以我们就这样将子树的单调队列合并,查询,然后将自己插入。可以通过本题。

如果是在冬令营上认真听了课的或者关注了\href{https://www.13331.org/}{主席的博客}的,就会知道存在O($nlogn$)的做法,比如说Finger Search(别问我那是什么,我啥也不知道)。本题的标准算法就是主席讲的\href{https://www.13331.org/365.html}{线段树的合并}:

将包含n个元素的线段树合并的时间复杂度是O($nlogn$)。这比启发式合并少了一个log因子。

这样我们就可以套用线段树求最长不下降子序列的算法了。我们对于每个节点不用平衡树,而是用线段维护f的最大值。每次就是询问权值在1-$w_i$中f值的最大值。而之前的合并操作就变成了简单的线段树合并。总时间复杂度是O($nlogn$),问题完美解决。

考场上出现了离线然后利用dfs序的方法。不过在标准解法中并不包含这个,一来考虑到有爆栈的可能,二来本来是想强制在线的,不过我偷懒不想改标程了。

\subsection{杂谈}
考场上有12人过了这题,第一次提交来自与seter神,但是很遗憾地失败了,xyjqjb是第一个通过这道题的,表示祝贺。

大家不妨思考一下如果要求求出最长不下降序列的数量的话怎么做?其实也蛮简单的。

如果本题存在修改权值操作的话怎么做呢?这个我就不知道了。
\newpage

\section{wyl8899的字符串}
\subsection{题目大意}
给定仅含小写字母的字符串A和B。你被允许至多修改A中的一个字符,使得A在B中的匹配长度尽可能的大。A在B中的匹配长度定义为最大的k,使得A[1..k]是B的子串。只需输出最大的匹配长度。

\subsection{出题思路或题目来源}
法法塔提议弄一题字符串,然后把这个问题扔给了我。当然最终的解法也是他先提出的。(法法塔:这题其实来自\href{http://vacdterh.tk/}{wzk\_DterH})

\subsection{题解}
我个人认为这一题思维上的难度不算很大。

记|A|=n,|B|=m,LCP(A,B)为A和B两个串的最长公共前缀。

我们枚举匹配位置i,假设LCP(B[i..m],A)=len,显然应该去修改A[len+1];

从而LCP(B[i..m],修改后的A串)=len+1+LCP(B[i+len+1],A[len+2]),在这些当中取最大值即可。

使用后缀数组可以轻松的完成这个任务,hash加二分也是可以的。

\subsection{闲扯}
很多人的hash都写挂了,我对着notepad.exe发誓我数据的时候根本没有想过卡hash。

正因为出数据的时候没啥想法所以差点放掉了一个奇怪的暴力..

直到出现这个卡时的暴力我才发现这题目本身决定了不方便卡奇怪的做法,要是出成OI题肯定可以骗到80分。

不过既然后缀数组能过...后缀树和后缀自动机也就能过对吧,不过还真有神犇写后缀树...吓尿了(法法塔:这位神犇是\href{http://txhwind.blog.163.com/}{txhwind})。

我写的标程当然就是后缀数组啦,我就不说我把罗穗骞的论文里的30行代码用了一年才背下来。
\newpage

\section{wyl8899和法法塔的游戏}
\subsection{题目大意}
一个序列,每次将一段数异或一个值,或者询问一段区间中与某个数异或结果最小的数是多少。
\subsection{出题背景或题目来源}
这是道博弈论的问题。但其实用到的博弈论的知识却是很少很少的。出这道题的思路是来自于Codeforces 172 Div1 problem B。里面有个有关异或的问题。当时似乎有人是用trie过的,使我感到很是震惊,于是就有了这题的初始——利用trie来解决异或问题(似乎这样的题目最近蛮热门的说)。

但是这也太裸了吧,而且单纯求个最大异或值也太没有意思了。这时我想到了两道题:Codeforces 170 Div1 problem C 和 SRM 565 Div1 500pt。都是博弈问题,刚好和异或可以扯得上关系。后者最终和此题非常相似。而前者则给了一个我一直很困扰的问题:nim游戏中我第一步想取掉最少的棋子怎么破?结果发现我根本就不会做囧。于是只得降低题目难度,确定取某堆的石子。但是这样就太水了不?加入修改操作。就成了现在这个样子。
\subsection{题解}
设$\oplus$为异或。
首先我们发现题意比较纠结,先考虑一个区间的弱菜值怎么求。很简单,假定整个区间的异或和为s,最右端的点为p,设弱菜值为x,那么为了使局面的异或值为0,要求$s \oplus p \oplus (p-x) = 0 \Rightarrow s \oplus p = p-x \Rightarrow x = p - s \oplus p $。所以要求x最大,即要求$ s \oplus p $ 最小。

那么我们维护异或的前缀和。问题变成,在a到b中选择一个前缀和$x$使得$s_i \oplus p \oplus s_x$ 最小。发现$s_i \oplus p$ 是确定的。于是就成了题目大意中所描述的。而减去弱菜值,即将第i个数由原来的x,修改为y。那么我们需要将之后的所有前缀和异或上$x \oplus y$。

正如在出题背景中说的,给定一个数列和多次询问,对于数k,求数a属于那个数列,且$a\oplus k$最大或最小。我们可以将数列中的数的二进制表示建立一个trie,然后将待查询的数往trie里走。由于高位为0低位全部为1都比高位为1要优,所以贪心显然。对于每一位,我们每次只需看看是否可能存在一个数与之异或为0,那么就往trie中对应的节点走,否则就只能走另一边了。

这道题要求对于区间进行询问,所以我们不可能只是维护一个trie吧。对于区间问题,一般做法是线段树,但是我是大沙茶,所以不会。那么我们就分块吧。

我们将数列分成$\sqrt{n}$块。每个块内维护个trie。这样查询操作只需要访问每个块,若查询的区间包含了整个块,那么就直接在trie内查询,否则暴力扫描整个块(这样的块不会超过两个)。

修改操作,暴力扫描要修改的块。若整个块都要被修改,那么直接打上个修改标记delta,表示将该区间内的所有数异或上delta,由于异或满足很多很多性质,所以只需要将询问的数异或上delta就行了。否则暴力修改区间内的所有数,然后重新建立trie(这样的块也不会超过两个)。

于是我们得到了$O(n\sqrt{n}logS)$的算法,其中S为数的大小,这儿不会超过10。经实际检验,比暴力稍稍快一点。这就是正解了。当然啦,我相信经过优化的暴力一定也能过的$\smile$。

\subsection{杂谈}
考场上有两人通过了此题。都是写的暴力,这点我表示非常抱歉,本来数据范围是$10^6$,足够卡掉暴力了,但是不想评测太久,而且自己的暴力写得比较丑,最终将数据范围下调。

其实现在才是关键,本题到底可不可以用线段树做呢?或者是否存在更优的算法,法法塔是个大沙茶,所以想不出,如果有人用更优的算法过了这道题,欢迎联系。

还有个更重要的问题:同样的,是组合游戏,每次询问一个区间,求为了必胜,第一步最少需要取掉多少石子。欢迎对这个问题有思路的同学和我探讨。

\newpage

\section{法法塔的小说}
\subsection{题目大意}
简单Voronoi图和裸的快速傅里叶变换。

\subsection{出题思路与题目来源}
本着一定要出道快速傅里叶变换(FFT)的心态出了这道题。但是裸题是很没有意思的事情,所以想了好久,突然想起了另一个有意思的东西:Voronoi图。我们知道这东西不好写也不好做对吧,但是有一次在Codeforces 168 Div1有位神犇(yangff)给出了评论,提供了O($n^2log_2 n$) 的算法(\href{http://tieba.baidu.com/p/2178197577?pid=29688428273&cid=29722033350&from=prin#29722033350}{here})。似乎很是好写好调———虽然事实证明还是很麻烦的。而后又在AC大神的空间上看到了一道有趣的题目:给定一个凸多边形,如何判断很多条直线是否与其相交。嗯,这个问题似乎蛮有意思的样子。于是就有了现在的题面。

\subsection{题解}
如果知道Voronoi图和快速傅里叶变换的话,那么这道题就是个送分的模板题(如果愿意在考场上手写的话也不拦你,我肯定是复制粘贴了)。

首先介绍Voronoi图,给定平面中N个点,对于每个点Pi,求出平面中距离Pi点比距离其它点更近的点的区域。这样就将平面划分成了很多区域,这就是Voronoi图(定义不标准,意会吧)。

接下来是快速傅里叶变换,它是将多项式变化为一组点值表达式的算法,令用它可以快速实现多项式乘法,也就是这道题的核心。

Voronoi图可以用三角剖分或海岸线算法实现O($nlong$)的复杂度。不过对于本题没什么太大的意义的说。所以可以用上面yangff神牛给出的利用半平面交的算法,也就是对于任意一个点,求出其与其它点连线的中垂线,求半平面交,最终就得到了这个点的最邻近区域。

至于快速傅里叶变换,网上代码一大堆,随便抄一份就行了。手写也不是太难。

至于要具体的算法的话,可以:
\begin{enumerate}
\item \href{http://www.geom.uiuc.edu/~samuelp/del\_project.html}{Voronoi图的分治算法详解}
\item FFT可以直接看《算法导论》。
\end{enumerate}

下面具体讲讲这道题吧,由于有了Voronoi图,我们所需做的,就只是判断一条直线与一个点对应的最邻近区域是否相交。判断直线与凸多边形是否相交,只需判断直线与凸多边形的边是否有交就行了。注意Voronoi图是平面图,边数大小是O($n$)。所以这一步时间复杂度为O($nm$)。于是顺利处理出所有花费时间的二元组数目。设时间为t的二元组数目为$T_t$。

接下来就是对于每个差值c,计算$\sum_{i-j=c}T_i*T_j$。稍稍进行一下转化:$i-j=c \Rightarrow i+(m-j)=c+m$。即求$\sum_{i+(m-j)=c}T_i*T_j$,令$B_{k=m-j}=T_j$,那么转化为求$\sum_{i+k=c}T_i*B_k$。

这是典型的多项式乘法或者卷积的形式。也就是FFT所做的工作,当然似乎有个奇葩时间复杂度的乘法,也许也可以过吧。

\subsection{杂谈}
考场上只有zsyzzsoft交了这道题,虽然他由于没有用FFT进行优化,导致pretest就超时了,不过他的勇气令人钦佩。

为什么本题这么水呢?因为法法塔是个大沙茶,不知道怎么做以下问题:

给定平面图,对于每条直线,求其经过了多少个区间?

如果有神犇知道这个怎么做,那么本题就可以强制要求O($nlogn$)求V图,本题也就会变成代码题了吧。(感觉好没节操啊!)

\newpage
我最大的感想就是我在贴吧上骗了好多好多经验啊!多谢各位了。
\end{document}





  评论这张
 
阅读(1023)| 评论(4)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017