ICPCCamp 2017 Ideas


Camp资料汇总: Google Drive

Progress: 16

给定一个无向图,求它的所有联通的点导出子图数量,对2取模。

解法 将统计{% math %}(\sum{G} 1) \text{mod } 2{% endmath %}改为统计{% math %}(\prod{G} 2^{c(G)}) \text{mod } 4{% endmath %},其中{%math%}c(G){%endmath%}表示{%math%}G{%endmath%}的连通块数量,两种统计法显然等价。第二种统计法相当于用两种颜色给点染色,要求同一连通块的点颜色相同。在转化一下就相当于给每个点染三种颜色(黑/白/灰,灰表示不取这个点),要求一条边两端的点颜色(如果是黑白的话)相同。

将原题改为选取边集的一个子集,统计所有使原图连通的选边方案数,对2取模,也可以用相同的解法。转化后相当于将原图的点染黑白两种颜色,如果一条边两端的点同色就可以选取,否则不能。那么对于一种染色方案,如果存在这样的一条边就会产生两种方案,将所有点反色有对应另一种方案,一共四种,模4后就没有了。只有原图是二分图的情况,黑白染色后每条边两端颜色都不同,都不能选取,那么就只有两种染色方案。因此,这道题就变成了二分图判定问题。


有面值为{%math%}1,2,\ldots,n{%endmath%}的硬币分别有{%math%}a_1,a_2,\ldots,a_n{%endmath%}枚,求可以拼成的不同面额硬币的方案数。

解法 记{%math%}L=\text{lcm}(1,2,\ldots,n),A=\sum_{i=1}^{n}ai \cdot i{%endmath%},结论是解集{%math%}S={\sum{i=1}^{n}x_i\cdot i: 0\leq x_i \leq a_i}{%endmath%}是若干个首项在{%math%}[0,n\cdot L]{%endmath%},末项在{%math%}[A-n\cdot L, A]{%endmath%},公差为{%math%}L{%endmath%}的等差数列的并。证明可以看handout-day-1中的D题题解。据说这里的两个{%math%}n \cdot L{%endmath%}可以改进到{%math%}2 \cdot L{%endmath%}。


*一类奇怪的形状求面积并的方法*:两两求交找出关键点,抠出边界,使用格林公式

{%math%} \begin{aligned} \iint{D}(\frac{\partial Q}{\partial x} - \frac{\partial P}{\partial y})dxdy = \oint{L^+}(Pdx+Qdy) \end{aligned} {%endmath%}

(并不懂,打出来爽爽)~


To be continued…