串珠子[BZOJ2560]

题目描述铭铭有$n$个十分漂亮的珠子和若干根颜色不同的绳子。现在铭铭想用绳子把所有的珠子连成一个整体。 现在已知所有的珠子互不相同,用整数$1$到$n$编号。对于第$i$个珠子和第$j$个珠子,可以选择不用绳子连接,或者在$c_{i,j}$根不同颜色的绳子中选择一根将它们连接。如果把珠子看作点,把绳子看作边,将所有珠子连成一个整体即为所有点构成一个连通图。特别地,珠子不能和自己连接。 铭铭希...

逃亡「GDOI2017」

【题目描述】兔兔和蛋蛋是一对cp,她们的国家目前正发生战乱,所以她们正在决定是否一起逃离这个国家。 该国家有$n$个城市,城市之间的道路形成一棵有向树。只能从父节点城市走到子节点城市。$1$号城市是首都,从城市$1$可以到达所有城市。每个城市都有一支军队,编号为$i$的城市其军队的攻击力为$b_i$,如果城市$i$能到达城市$j$,且$b_i > b_j$(城市 i 军队的攻击力大于城...

宝藏「NOIP2017」

【题目描述】参与考古挖掘的小明得到了一份藏宝图,藏宝图上标出了$n$个深埋在地下的宝藏屋,也给出了这$n$个宝藏屋之间可供开发的$m$条道路和它们的长度。 小明决心亲自前往挖掘所有宝藏屋中的宝藏。但是,每个宝藏屋距离地面都很远,也就是说,从地面打通一条到某个宝藏屋的道路是很困难的,而开发宝藏屋之间的道路则相对容易很多。 小明的决心感动了考古挖掘的赞助商, 赞助商决定免费赞助他打通一条从地面到...

集合选数[HNOI2012]

【问题描述】《集合论与图论》这门课程有一道作业题,要求同学们求出{$1, 2, 3, 4, 5$}的所有满足以 下条件的子集:若$x$在该子集中,则$2x$和$3x$不能在该子集中。同学们不喜欢这种具有枚举性质的题目,于是把它变成了以下问题:对于任意一个正整数$n\le100000$,如何求出{$1, 2,…, n$} 的满足上述约束条件的子集的个数(只需输出对$1,000,000,001$...