这次考的是HNOI 2015 day2
心路历程
已经准备好了全程骗分的心态。。。
先看一遍题。。
第一题貌似是个数学题？
第二题好像是毒瘤代码题。。还强制在线？
第三题。。。毫无头绪,必然神题,先不想
看第一题,预备想30分钟
三十分钟过去了。。没想出正解,但是已经发现很多很有用的性质(其实离正解只有一步之遥了。。。)
感觉很可做,继续杠!
又三十分钟过去了。。感觉是DP,但是这个形式怎么DP啊啊啊心烦意乱地卡在同一个地方,还是没想出来。。
不行,感觉正解一定很神。。。先暴力一把,于是写了(以为)50分的暴力后做第二题。。
想了二十分钟。。必然代码难度高,感觉不很可做,毕竟想出来了也不能一次写A啊。。
于是想暴力,写了20分的大力和20分的大力树DP。。
时间久过去两个多小时了
第三题。。暴力有30分么？
花了10+分钟才搞懂题意,在树上?
然后准备写个
O(N!)
的大力过30分
又30分钟过去了。。
我败了。。暴力也写不出来。。
感觉
O(3^N * N!)
很好写,但是拿不到分吧(flag)。。
时间只有20分钟了,好像也干不了什么了,回去看看第一题吧,说不定搞出来呢(flag)
看了一下第一题,然后一分钟展开了一下递推式
咦!
这个不是可以直接记忆化么
啊我zz,为啥一开始没想到展开这个式子啊啊啊不好只有20min了赶快抢救!!
然后。。写出来了但是没调出来。。
最后交了个期望50分的暴力
开始评测
第一题只有10分?
第二题RE只有20什么鬼。。
第三题挂了,输出0拿到5分
JeremyGuo和Ender都搞出了第一题..
Ender最后一题写了
O(3^N * N!)
的大力然后拿到30分？？
SunIsMe好像直接放弃第一题一样。。然后暴力拿了50
然后我35分又垫底辣。。
事后
第一题就是差了一步。。
后来发现我一个细节想错了。。
想题到心烦意乱时应该先去搞搞其他题啊,思路卡壳也不要总是钻到一个地方出不来。。可以想想从别的方面下手
代码能力还是不行啊,难写的题根本不敢写,一般的题爆炸几率好像也非常大。。
有的时候还是高估了自己的能力,应该缩短一下思考时间,想不出来暴力算了,花时间检查正确性可能更重要。。
没事没事还有下次
题目以及解题报告
第一题
「恒逸，你相信灵魂的存在吗？」
郭恒逸和姚枫茜漫步在枫音乡的街道上。望着漫天飞舞的红枫，枫茜突然问出
这样一个问题。
「相信吧。不然我们是什么，一团肉吗？要不是有灵魂……我们也不可能再见
到你姐姐吧。」
恒逸给出了一个略微无厘头的回答。枫茜听后笑了笑。
「那你仔细观察过枫叶吗？」
说罢，枫茜伸手，接住了一片飘落的枫叶。
「其实每一片枫叶都是有灵魂的。你看，枫叶上不是有这么多脉络吗？我听说，
枫叶上有一些特殊的位置，就和人的穴位一样。脉络都是连接在这些穴位之间的。
枫树的灵魂流过每片枫叶的根部，沿着这些脉络，慢慢漫进穴位，沁入整片枫叶。
也是因为这个原因，脉络才都是单向的，灵魂可不能倒着溜回来呢。」
恒逸似懂非懂地点了点头。枫茜接着说了下去。
「正是因为有了灵魂，每片枫叶才会与众不同。也正是因为有了灵魂，每片枫
叶也都神似其源本的枫树，就连脉络也形成了一棵树的样子。但如果仔细看的话，
会发现，在脉络树之外，还存在其它的非常细的脉络。虽然这些脉络并不在树上，
但他们的方向也同样顺着灵魂流淌的方向，绝不会出现可能使灵魂倒流的回路。」
恒逸好像突然想到了什么。
「那这些脉络岂不是可以取代已有的脉络，出现在脉络树上？」
枫茜闭上了眼睛。
「是啊，就是这样。脉络树并不是唯一的。只要有一些微小的偏差，脉络树就
可能差之万里，哪怕是在这同一片枫叶上。就像我们的故事，结局也不是唯一的。
只要改变一个小小的选项，故事流程可能就会被彻底扭转。」
「真是深奥啊……」
恒逸盯着这片红枫，若有所思地说。枫茜继续说道。
「还不止如此呢。所有的脉络都不会永恒存在，也不会永恒消失。不管是脉络
树上的脉络，还是之外的细小脉络，都是如此。存在的脉络可能断开消失，消失的
脉络也可能再次连接。万物皆处在永恒的变化之中，人与人之间的羁绊也是。或许
有一天，我们与大家的羁绊也会如同脉络一样，被无情地斩断。或许我们也终将成
为“枫音乡的过客”。或许这一切都会是必然，是枫树的灵魂所决定的……」
枫茜的眼角泛起了几滴晶莹剔透的泪珠。恒逸看着这样的枫茜，将她抱入怀中。
「别这样想，枫茜。就算脉络断开，也有可能还会有新的脉络树，也还会与枫
树的根相连。这样的话，我们的羁绊仍然存在，只是稍微绕了一些远路而已。无论
如何，我都不会离开你的。因为你是我穷尽一生所寻找的，我的真恋啊！」
两人的目光对上了。枫茜幸福地笑了，把头埋进了恒逸的怀抱。从远方山上的
枫林中，传来了枫的声音。
【问题描述】
不妨假设枫叶上有 n个穴位，穴位的编号为 1 ~ n。有若干条有向的脉络连接
着这些穴位。穴位和脉络组成一个有向无环图——称之为脉络图（例如图 1），穴
位的编号使得穴位 1 没有从其他穴位连向它的脉络，即穴位 1 只有连出去的脉络；
由上面的故事可知，这个有向无环图存在一个树形子图，它是以穴位 1为根的包含
全部n个穴位的一棵树——称之为脉络树（例如图 2和图 3给出的树都是图1给出
的脉络图的子图）；值得注意的是，脉络图中的脉络树方案可能有多种可能性，例
如图2和图 3就是图 1给出的脉络图的两个脉络树方案。
脉络树的形式化定义为：以穴位 r 为根的脉络树由枫叶上全部 n个穴位以及 n
– 1 条脉络组成，脉络树里没有环，亦不存在从一个穴位连向自身的脉络，且对于
枫叶上的每个穴位 s，都存在一条唯一的包含于脉络树内的脉络路径，使得从穴位
r 出发沿着这条路径可以到达穴位 s。
现在向脉络图添加一条与已有脉络不同的脉络（注意：连接 2个穴位但方向不
同的脉络是不同的脉络，例如从穴位3到4的脉络与从4到3的脉络是不同的脉络，
因此，图 1 中不能添加从 3 到 4 的脉络，但可添加从 4 到 3 的脉络），这条新脉络
可以是从一个穴位连向自身的（例如，图 1 中可添加从 4 到 4 的脉络）。原脉络图
添加这条新脉络后得到的新脉络图可能会出现脉络构成的环。
请你求出添加了这一条脉络之后的新脉络图的以穴位 1 为根的脉络树方案数。
由于方案可能有太多太多，请输出方案数对 1,000,000,007 取模得到的结果。
解题报告
这题背景好长啊。。而且好像是xxx?
人物名字很值得吐槽。。@JeremyGuo
首先发现一个很好的性质:
DAG的生成树个数为每个非1节点的入度乘积
比较好理解,每个节点的父节点只能有一个即可
不出现不连通的情况可以递归的思考,想想就会,我不在赘述。
然后考虑加入一条边的情况
加入一条边后,只有选中这条边才会出现环,用总方案数减去有环的方案数即可
对每条环单独考虑,先钦定这条环上的所有边被选中了,那么其他边无论怎么选都非法,于是选择这条路径造成的的非法方案数为
总方案数/环路上所有点的入度乘积
,然后把总答案减去选
每条环路造成的非法方案数
就可以了,这样是不会重复减去的,原理比较简单我就偷个懒不解释了。。
此时答案即为:
$$total – \sum_{foreach:path} total \times ({\prod_{i=path.begin()}^{path.end()}radius(i)})^{-1}$$
考虑如何快速计算
每条环路造成的非法方案数
之和,(考试时卡在了这里。。。就差一点QAQ)
比较容易发现这个是可以记忆化的
递推式为$$dp(u) = \sum_{u->v} dp(v) \times radius(u)^{-1}$$
其中
radius(u)
表示点u的入度
初始值
dp(x)
为
total
然后就可以直接搞了。。
代码
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <climits>
#include <cmath>
#include <cstring>
#include <ctime>
typedef long long LL;
const int MAXN = 201000;
const LL MOD = 1000000007;
LL rad_in[MAXN];
int N, M, X, Y;
bool vis[MAXN], tag[MAXN];
struct Node {
int v, nxt;
} d[MAXN*3];
int head[MAXN], etot;
inline int addEdge(int a, int b) {
etot ++;
d[etot].v = b;
d[etot].nxt = head[a];
head[a] = etot;
return etot;
}
LL total = 0;
inline LL advPow (LL a, int b) {
LL ret = 1;
a %= MOD;
while(b) {
if(b & 1) ret *= a, ret %= MOD;
a *= a;
a %= MOD;
b >>= 1;
}
return ret;
}
LL plans[MAXN];
void dfs1(int u) {
if(vis[u]) return ;
vis[u] = true;
for(int e = head[u]; e; e = d[e].nxt) {
dfs1(d[e].v);
if(tag[d[e].v]) tag[u] = true;
}
}
LL dp[MAXN];
void dfs2(int u) {
if(!tag[u]) return ;
if(dp[u]) return ;
if(u == X) {dp[u] = total*advPow(rad_in[u], MOD-2)%MOD; return ;}
dp[u] = 0;
LL inv = advPow(rad_in[u], MOD-2);
for(int e = head[u]; e; e = d[e].nxt) {
dfs2(d[e].v);
if(tag[d[e].v]) {
dp[u] += inv * dp[d[e].v] % MOD;
dp[u] %= MOD;
}
}
}
int main () {
int a, b;
scanf("%d%d%d%d", &N, &M, &X, &Y);
for(int i = 1; i<=M; i++) {
scanf("%d%d", &a, &b);
addEdge(a, b);
rad_in[b] ++;
}
total = 1;
rad_in[Y] ++;
for(int i = 2; i<=N; i++)
total *= rad_in[i], total %= MOD;
if(Y == 1) {printf("%lld\n", total); return 0;}
vis[X] = tag[X] = true;
dfs1(Y), dfs2(Y);
printf("%lld\n", ((total-dp[Y])%MOD+MOD)%MOD);
}
<-貌似crayon最经有点抽风
Join the discussion