- 2024-02-12P4559 [JSOI2018] 列队 题解
题目链接:列队半年前mark的题,结果现在一下子就会做了。顺便写写我的手玩过程和复杂度说明。考虑比较特殊的情况:比较特殊的,发现从黑色到红色区间我们无论咋选择,由于\(\left|a_{right}-a_{left}\right|\),这玩意如果\(right\)表示红色的一边,那么这个绝对值可以直接拆掉,那么
- 2023-09-17题解 LOJ2549【[JSOI2018] 战争】
problem给你两个平面凸多边形\(A,B\),\(Q\)次询问,每次询问是一个向量\(\vecv\),回答\(A\)与\(B+\vecv\)是否有交。\(n,Q\leq10^5\)。solution观察闵可夫斯基和(Minkowskysum)的定义,若将这个运算定义为\((*)::[Point]\to[Point]\to[Point]\),则满足:\[A*B=\{
- 2023-08-26[JSOI2018] 潜入行动
题目描述外星人又双叒叕要攻打地球了,外星母舰已经向地球航行!这一次,JYY已经联系好了黄金舰队,打算联合所有JSOIer抵御外星人的进攻。在黄金舰队就位之前,JYY打算事先了解外星人的进攻计划。现在,携带了监听设备的特工已经秘密潜入了外星人的母舰,准备对外星人的通信实施监听。外
- 2023-06-09JSOI2018 部分题解
目录潜入行动防御网络列队潜入行动一眼直接DP。设\(f_{i,j,0/1,0/1}\)表示\(i\)子树内放了\(j\)个监听设备,\(i\)是否被子结点覆盖,\(i\)是否放了监听设备,\(i\)子树内除了\(i\)都被覆盖的方案数。转移是一个树形背包,时间复杂度\(\mathcal{O}(nk)\),只是常数有点大。
- 2023-05-25P4557 [JSOI2018]战争 题解
闵可夫斯基和前言入门建议看吉老师(吉如一)的计算几何入门到放弃。感觉应该是讲的最通俗易懂的了。本文借鉴了Winxp的博客,以及吉老师视频中的思路。写这篇博客的初衷是因为我作为一个初学者,此题里的题解对我来说理解起来不算太难,但是实现起来细节比较多,题解里也没有很详细地去解
- 2022-12-28[JSOI2018]机器人
题目描述一个\(n\timesm\)的网格,有一个机器人一开始在\((1,1)\),每次机器人可以向右或向下走一步,\((i,m)\)的右边是\((i,1)\),\((n,j)\)的下边是\((1,j)\),机器人需要不重
- 2022-10-03【树上背包】洛谷 P4516 [JSOI2018] 潜入行动
P4516[JSOI2018]潜入行动省选/NOI-、树上背包计数题意略设状态为\(dp[u][j][0/1][0/1]\),u点子树放了j个装置,u点有没有放装置,u点有没有被监听的方案数。对