Rockdu's Blog

策策同学特别喜欢逛公园。 公园可以看成一张 N 个点 M 条边构成的有向图，且没有自环和重边。其中 1 号点是公园的入口， N 号点是公园的出口，每条边有一个非负权值，代表策策经过这条边所要花的时间。 策策每天都会去逛公园，他总是从 1 号点进去，从 N 号点出来。 策策喜欢新鲜的事物，他不希望有两天逛公园的路线完全一样，同时策策还是一个特别热爱学习的好孩子，他不希望每天在逛公园这件事上花费太多的时间。如果 1 号点到 N 号点的最短路

题目描述 组合数 Cnm" role="presentation" style="position: relative;">CmnCnmC_n^m 表示的是从 n" role="presentation" style="position: relative;">nnn 个物品中选出 m" role="presentation" style="position: relative;">mmm 个物品的方案数。举个例子，从 (1,2,3) 三个物品中选择两个物品可以有 (1,2),(1,3),(2,3) 这三种选择方法。根据组合数的定义，我们可以给出计算组合数 Cnm" rol

D.zip 题解：http://blog.leanote.com/post/rockdu/e0377a8fae3b C.zip 题解：http://blog.leanote.com/post/rockdu/b64d2eb333a1 E.zip 题解：http://blog.leanote.com/post/rockdu/7f516d26797b

题解 for C：逃亡 首先我们看看这道题的部分分： 对于30%" role="presentation" style="position: relative;">30%30%30\%的数据，我们写个爆搜搜过去就可以了。 对于60%" role="presentation" style="position: relative;">60%60%60\%的数据，注意到n,m" role="presentation" style="position: relative;">n,mn,mn,m为100" role="present

题解 for D：希望 D.pdf 我们来看看这道题的部分分： 首先明确本题的贪心策略：一旦有放置魔法符文的方案就放，这个贪心策略是显然正确的。 对于Subtask1" role="presentation" style="position: relative;">Subtask1Subtask1Subtask1：枚举树上O(N2)" role="presentation" style="position: relative;">O(N2)O(N2)O(N^2)条路径，每一条路径都O(N)" role="presentation" style="position: re

题解 for E：最后的斗争 E.pdf 带标号边-双联通图计数。 先看这道题的部分分： 对于30%" role="presentation" style="position: relative;">30%30%30\% 的数据，我们写一个dfs，找出所有的N" role="presentation" style="position: relative;">NNN个点的边-双联通图打表即可获得。 仍然是对于30%" role="presentation" style="position: relative;">30%

地址：https://loj.ac/problem/2567 看来在组合计数的路上，还有很长一段路要走啊…… 首先ai,bi≤109" role="presentation" style="position: relative;">ai,bi≤109ai,bi≤109a_i,b_i\leq 10^9，显然dp" role="presentation" style="position: relative;">dpdpdp不能和值域有关。 考虑最终的答案，发现答案统计的时候每一个学校只是在分界点之间做前缀和。 考虑O(n)" role="presen

地址：https://loj.ac/problem/2587 先来说说我和这道题的故事吧。作为APIO2018最良心得分题，放在T3的位置是真的阴……当打完了T1,T2的暴力后，才发现T3貌似很好拿分，想的是把T1，T2的二档暴力打完后来慢慢拿T3的分。于是就被坑进T1了。T3最后只打了有环和链的、n<=10的。树的档都没看到，血亏。知道了点双树(圆方树)后，这道题就很送分了。对于圆点统计从不同子树中选出两个点的方案，对于方点统计从不同子树选出三个点的方案，加起来就行了。细节比较多，详见注释#include<cstdio> #include<cstring> #i

地址：https://loj.ac/problem/2586  说一说我和这道题的故事吧。打完T1的5分后我又来看到了T2。一看完了又不会，赶快打了个7分暴力。再想想，我貌似可以拿Subtask2的12分，准备打完T1来码。然后T1的400个set死活打不出来……于是乎这道题是彻底凉了。一下来就听见很多人码了个KD-tree爆艹T2，什么鬼？？？？不过正解貌似是个线段树维护扫描线，没人写……  然后为了练习KDtree，今天又搬出这道题来。思路大概是一个节点维护能框住下面所有圆的最小矩形。嗯……就是把圆并近似成矩形判相交剪枝然后骗分。这个做法在考场上就能得到87分，都怪当年

地址：https://loj.ac/problem/2585 说一说我和这道题的故事吧。APIO2018现场：和moonzero在一个考室，前一天才好不容易会使用linux系统后一天就要上考场了，非常的方。打开problems，首先映入眼帘的便是 A.新家。毫不犹豫先打了5分暴力，然后去打了T3，T2的暴力。回头来准备肝T1，发现自己会Subtask2的7分暴力。然后死也没调出来，400个set把自己送胸牌了。下来moonzero告诉我他更窒息，写了400个splay………………嗯，叙旧就叙到这里了，前几天又想起这道题，发现有了思路。接下来我们来看看APIO这道亲民的码农题的做法吧。首先我们容