题目描述
组合数 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
题解 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这道亲民的码农题的做法吧。首先我们容
很套路的一道题，做过无限之环来看这道题还是十分好想的因为我比较菜，考试的时候就没能想出来。按照套路，把格子黑白染色，然后考虑图的特点，到一个地方一定拐弯。并且，对于一条回路来说，正向和反向的贡献都是一样的。接下来，我们指定黑、白格子的流向，考虑一个白格子的流出一定是某个黑格子的流入。那么就好办了，我们规定黑格子横进竖出，白格子横出竖进。这样我们把问题抽象成一张图，对于每一个格子可以选择从进向自己连边，自己向出连边，相当于每种进的方案都可以选择两种出去的方案。但是题目还有一个隐含条件，一个点只能经过一条流量，也就是出入度都是1，想到限制出入度便想到了最小路劲覆盖的模型。于是，初步的构图便完成了。
Description在Byteland一共有n个城市，编号依次为1到n，它们之间计划修建n(n-1)/2条单向道路，对于任意两个不同的点i和 j，在它们之间有且仅有一条单向道路，方向要么是i到j，要么是j到i。换句话说，这是一个n个点的竞赛图。Byte asar居住在1号城市，他希望从1号城市出发，沿着单向道路不重复地访问一些城市，使得访问的城市数尽可能多。 请写一个程序，帮助Byteasar计算有多少种道路修建方式，使得从1号点出发的最长简单路径经过点数恰好为k，由 于答案可能很大，请对P取模输出 Input第一行包含两个正整数n,P，表示点数和模数。 2≤P≤1e9,N<=200
Rockdu's Blog