首页 > 其他分享 >JOISC 2018 题解

JOISC 2018 题解

时间:2024-02-12 11:44:22浏览次数:34  
标签:begin langle matrix dfrac JOISC right 2018 题解 rangle

JOISC 2018

loj 上有几乎全部的题目,写了题意的就是 loj 上没有的。

D1T1

简单题。

根据颜色段均摊的结论,每个点到根的路径上颜色段的总和是 \(O(n\log n)\) 的,于是直接每次暴力找颜色段即可。复杂度 \(O(n\log^2n)\)。

提交记录

D1T2

又是计算几何。

我们需要画出一条闭合折线,并且能够把正方形包围。

考虑我们一定是把已有栅栏用新的栅栏连起来,或者是让已有栅栏和正方形边界连起来。因为栅栏不能在正方形内,我们把两个栅栏连接起来一定不会只用正方形一条边界的一部分,这样一定是不优的,因此我们可以把只把正方形的四个角当成栅栏,这样我们就只需要考虑连接两个栅栏的贡献了。

对于每一对栅栏,我们求出连接这两个栅栏最小的代价和这条线段。如果这条线段和正方形有交,我们就不能选,而且我们用其他方式连接这两个。现在问题就变成了找最小的环使得包含这个正方形。

对于判包含,我们可以从正方形中引出一条射线,如果这条射线经过了折线奇数次,就说明被包含了。

于是对于每一对栅栏,我们求出连接这两个点的线段经过了射线多少次,这样我们的问题就是求一个经过射线次数为奇数的最小环,可以用 Floyd 解决。

复杂度 \(O(n^3)\)。

提交记录

D1T3

简单计数题。

显然可以想到按行 DP,然后维护当前还可以放帐篷有几列。设 \(f[i][j]\) 表示考虑了前 \(i\) 行,有 \(j\) 列还可以放帐篷,转移有 4 种:

  1. 这一行不放帐篷,\(f[i][j]\leftarrow f[i-1][j]\);
  2. 这一行放两个帐篷,\(f[i][j]\leftarrow f[i-1][j+2]\binom{j+2}{2}\);
  3. 这一行放一个帐篷,且以后不会和其他帐篷在同一行,\(f[i][j]\leftarrow 4f[i-1][j+1](j+1)\);
  4. 这一行和这一列之前一行放帐篷,\(f[i][j]\leftarrow f[i-2][j+1](j+1)(i-1)\)。

复杂度 \(O(nm)\)。

提交记录

D2T1

题目等价于求有多少个排列满足有 \(k-1\) 个位置满足 \(p_i>p_{i+1}\),这就是欧拉数。

即一个排列中满足 \(p_i<p_{i+1}\) 的位置(记作升高)有 \(k\) 个,那么这样的排列个数就是欧拉数 \(\left\langle\begin{matrix}n\\k\end{matrix}\right\rangle\)。

我们考虑从小到大加入数。加入 \(n\) 时,有 4 种方法:

  1. 放在开头,升高不变,从 \(\left\langle\begin{matrix}n-1\\k\end{matrix}\right\rangle\) 转移过来。
  2. 放在末尾,升高多 1,从 \(\left\langle\begin{matrix}n-1\\k-1\end{matrix}\right\rangle\) 转移过来。
  3. 插入到升高中,这样不会新产生升高,有 \(k\left\langle\begin{matrix}n-1\\k\end{matrix}\right\rangle\) 种。
  4. 不插入到升高中,有 \((n-k-1)\left\langle\begin{matrix}n-1\\k-1\end{matrix}\right\rangle\) 种。

于是有

\[\left\langle\begin{matrix}n\\k\end{matrix}\right\rangle=(k+1)\left\langle\begin{matrix}n\\k\end{matrix}\right\rangle+(n-k)\left\langle\begin{matrix}n\\k\end{matrix}\right\rangle \]

然后根据 \(\left\langle\begin{matrix}n\\1\end{matrix}\right\rangle=2^n-n-1\),我们猜测 \(\left\langle\begin{matrix}n\\k\end{matrix}\right\rangle=\sum\limits_{i=0}^k(-1)^i\binom{n+1}{i}(k+1-i)^n\)。

可以通过递推式来证明。

因为 \(f(x)=x^n\) 是完全积性函数,于是可以用线性筛来求,复杂度 \(O(n)\)。

提交记录

D2T2

提交答案题。容易想到这 \(k\) 条边一定是连成菊花图,那么就可以考虑爬山。

我们每次先选定中心点 \(rt\),然后枚举选择与哪些点相连,但是估价函数是 \(O(n^2)\) 的,很耗时,那么不妨改成 \(\sum dis(rt,i)\)。

对于初始态,可以对枚举每个点作为中心点,然后按度数从大到小选取作为初始状态,选择较小的几组即可。

提交记录

D2T3

容易发现每个人都是隔 \(t_i\) 时间移动 \(d_i\) 单位,那么求出 \(t_i\) 即可。而且 \(t_i\) 一定是 \(t_{i-1}\) 的若干倍,可以简单求出。最后询问时二分即可。

提交记录

D3T1

传送门

题意:Alice 有一个 \(n\) 个点的无向图,她可以给 Bob 传一个点数不超过 \(n+12\) 的无向图,点会被打乱,Bob 需要还原出这张图。

思路:一开始以为不用还原标号,后来才发现连标号都要还原。

既然和标号相关,而且还多了 \(\log n+2\) 个点,那么不难想到二进制分组。

难点在于怎么确定用来二进制分组的那 10 个点。

因为多了 2 个点,记为 \(u,v\),我们可以先用 \(u\) 和处了 \(v\) 之外的点连边,再用 \(v\) 和那 10 个点连边。

然后考虑怎么确定这 10 个点的顺序。我们发现,第 1 个点的度数一定比第 10 个点的度数大,于是可以把这 10 个点连成一条链,这样就可以求出顺序了。

提交记录

D3T2

考场上想到了根号分治,但是没想到是对询问根号分治。

考虑我们有两种做法,一种是每次询问 \(O(n)\) 求答案,一种是提前求出到每个点距离前 \(k\) 大的点,于是就可以根号分治,如果询问中删掉的点数小于 \(B\),就用提前预处理出的距离前 \(B\) 大的点来求,否则就暴力 \(O(n)\) 跑一遍,复杂度是 \(O(nB+QB+n\dfrac{Q}{B})=O(\sqrt{nq(n+q)})\)。

提交记录

D3T3

巨大 DP。

首先自然是把左括号看成 1,右括号看成 -1,那么条件就是翻转(同时反转)前后前缀和非负。

那么现在分成 4 种,两侧都合法,翻转前合法翻转后不合法,翻转前不合法翻转后合法,翻转前后都不合法。

第一种情况,等同于是合法括号串,容易 \(O(n^2)\) 解决。

第二种情况和第三种情况本质相同。

记前缀和为 \(s_i\),我们要翻转的区间肯定覆盖了第一个 \(s_i<0\) 的位置 \(p\),而且显然是 \(s_i\) 越大越好,那么 \(s_l\) 就是 \(s_1\sim s_p\) 中的最大值。

对于 \(i>r\) 的部分,翻转后为 \(s_i-s_n\),显然是合法的。

记 \(s_l=a,s_n=b\),那么有 \(s_r=a+\dfrac{b}{2}\)。如果 \(a-\dfrac{b}{2}\ge 0\),那么 \((l,p]\) 中存在满足条件的 \(r\)。否则就需要满足 \(s_p\sim s_r\) 中最大值不超过 \(2a\)。记 \(t_i=s_i-s_n\),那么有 \(t_r=a-\dfrac{b}{2}\),限制是 \([p,r]\) 中 \(t_i\) 最大值不超过 \(2(a-\dfrac{b}{2})\)。

于是可以枚举 \(a-\dfrac{b}{2}\) 然后 DP。前缀需要记录当前和历史最前缀和,可以维护 \(f[i][a]\) 表示 \(s_i=-1\) 且 \(\max s_i=a\);后缀可以维护 \(g[i][j][k]\) 表示 \(t_i=j\),\(k\in\{0,1\}\) 表示是否确定了 \(r\)。

最终答案是 \(\sum\sum f[i][a]g[i][-b-1][a+\dfrac{d}{2}<0]\)。

然后是第四种情况。我们找到第一个 \(s_i=-1\) 的位置 \(p\) 和 \(s_i-s_n=-1\) 的最大的位置 \(q\),设 \(s_1\sim s_p\) 中最大值为 \(a\),\(s_n=b\),\(s_q\sim s_n\) 中最大值为 \(c\),如果 \(a+\dfrac{b}{2}\le c\),我们以 \(s_1\sim s_p\) 中最大值位置为左端点,取 \(s_q\sim s_n\) 中第一个等于 \(a+\dfrac{b}{2}\) 为右端点,然后就可以类似上一种的情况转移。如果 \(a+\dfrac{b}{2}>c\),翻转后就是 \(a+\dfrac{b}{2}\le c\) 的情况。最后要减去 \(a+\dfrac{n}{2}=c\) 的情况。

复杂度 \(O(n^3)\)。

提交记录

D4T1

经典反悔贪心模型,我们取一个位置后把这个位置两边的数减去自己这个答案加入考虑范围,这样之后取这个数就相当于是把这次的操作反悔了。

提交记录

D4T2

首先可以用 \(n\) 次确定一个在边界上的数,然后考虑每次二分出贴近当前已经确定的部分的数。

具体地,假设当前二分的是 \(mid\),如果我们询问所有未确定的大于等于 \(mid\) 的数,再询问一次加入边界的结果,就可以知道边界上的数和 \(mid\) 的大小关系。

总次数 \(O(n+2n\log n)\)。

提交记录

D4T3

没想到图论还有 DDP。容易想到对于任意两点,维护最短路和初边、终边都不一样的次短路,但是这样是假的,有时候只会限制出边、终边中的一个,于是我们就维护 4 条路径。记 \(s,t\) 为初边终边,那么就是以下 4 种:

  1. \((s_1,t_1)\),最短路;
  2. \((s_2,t_2)\),其中 \(s_2\ne s_1,t_2\ne t_1\);
  3. \((s_3,t_3)\),其中 \(s_3\ne s_1,t_3\ne t_2\);
  4. \((s_4,t_4)\),其中 \(s_4\ne s_2,t_4\ne t_1\)。

这些路径可以用 \((min,+)\) 矩阵维护,然后这就是 DDP。

现在的问题是怎么求这 4 条路径。

因为和边关系密切,我们可以把无向边拆成两条有向边,然后求边间的最短路。

复杂度 \(O(m^2\log m+4^3n\log n)\)。

提交记录

标签:begin,langle,matrix,dfrac,JOISC,right,2018,题解,rangle
From: https://www.cnblogs.com/Xttttr/p/18013753

相关文章

  • JOISC 2017 题解
    JOISC2017loj上有几乎全部的题目,写了题意的就是loj上没有的。D1T1开场放大。首先,对于一个点,它最后覆盖的一定是一个矩形,这就意味着如果我们知道了\(u,d,l,r\)操作各用了多少次,他们之间的顺序是不重要的,我们可以直接当做把一种操作做完再做剩下的操作,这样就可以做到\(O(......
  • JOISC 2016 题解
    JOISC2016loj上有几乎全部的题目,写了题意的就是loj上没有的。D1T1一开始把题目看错了,还写了棵线段树。把询问离线,倒着扫一遍,就变成了求最长不上升子序列,用树状数组维护即可。提交记录D1T2来自Kubic的神仙做法。考虑Filp一个位置和剩下所有位置,记录每个数作为答案......
  • JOISC 2015 题解
    JOISC2015loj上有几乎全部的题目,写了题意的就是loj上没有的。D1T1简单题。因为\(k\)很小,考虑依次确定最后第\(i\)位是什么。我们倒序考虑所有操作,维护最后第\(i\)位当前在第几位,就可以一直推下去。提交记录D1T2直接暴力复杂度就是\(O(k4^k)\)的,可以通过。提交......
  • JOISC 2014 题解
    JOISC2014loj上有几乎全部的题目,写了题意的就是loj上没有的。D1T1想到了最短路的做法,不过可能还需要整体二分,复杂度至少有2log。有复杂度更优秀的贪心做法。把边按时间倒序加边,然后从终点开始dfs来更新每个点可以的最晚出发时间,每条边走之后肯定就不会再让答案变优了,......
  • CF1628E Groceries in Meteor Town 题解
    题目链接点击打开链接题目解法感觉就是很多个套路组合出来,但我有些套路都不会/ll套路1看到从一点出发,到其他点的路径上的最大权,可以想到\(kruskal\)生成树(这提示我不仅是图可以用\(kruskal\)生成树,树也可以捏)我们建大根的\(kruskal\)生成树,那么将问题转化成了找一个......
  • 图上的游戏 题解
    「2020集训队论文」图上的游戏。算法\(1\):给定点集\(S\),\(|S|=n\),其中有\(m\)个好点。每次可以询问指定点集中是否存在好点,求所有好点。询问次数\(O(\min\{m\logn,n\})\)。对\(S\)分治,若当前不存在好点则退出。每个好点被询问\(\lceil\logn\rceil\)次,分治次......
  • CF1715E Long Way Home题解
    题解注意到\(k\)是一个很小的数,我们考虑分层图是否可做,这时航线有\(n^2\)条,我们可能会建出\((k+1)m+kn^2\)条边,空间会炸掉,然而单单从分层图的角度来优化,是困难的。对于\(m=0\)的情况。考虑\(\text{dp}\),定义\(dp_{i,j}\)表示乘坐不超过\(i\)次航班到达\(j\)的最......
  • CF1928E 题解
    \(\textbf{ProblemStatement}\)给定\(n,x,y,s\),构造长度为\(n\)的序列\(a\),满足:\(a_1=x\)。\(\foralli\in[2,n],a_i=a_{i-1}+y\)或者\(a_i=a_{i-1}\bmody\)。\(\sum\limits_{i=1}^na_i=s\)。给出构造或报告无解。\(\sumn,\sums\le......
  • 题解 AT_mujin_pc_2016_c【オレンジグラフ】
    本文中点的编号从\(0\)开始。显然,题目中要求橙色的边构成极大的二分图。枚举二分图左右部分别有哪些点。特别地,钦定\(0\)号点是左部点。将所有跨左右部的边染为橙色,如果所有点通过橙色的边连通,就得到了一组合法的解;如果不连通,显然可以将更多的边染成橙色,使得所有点连通。//......
  • 题解 ABC336G【16 Integers】
    萌萌BEST定理练习题。赛时几乎做出来了,但写挂了,现在在火车上没事干就给补了。考虑建图,图中共有\(8\)个节点,节点的编号是\((\mathbb{Z}/2\mathbb{Z})^3\)的每个元素。对于每个四元组\((i,j,k,l)\in(\mathbb{Z}/2\mathbb{Z})^4\),在图中连\(X_{i,j,k,l}\)条\((i,j,k)\to(j......