10月11日
上午
问题 A: 一笔画问题
题目描述
如果一个图存在一笔画，则一笔画的路径叫做欧拉路，如果最后又回到起点,那这个路径叫做欧拉回路。
我们定义奇点是指跟这个点相连的边数目有奇数个的点。对于能够一笔画的图,我们有以下两个定理。
定理1:存在欧拉路的条件:图是连通的，有且只有2个奇点。
定理2:存在欧拉回路的条件:图是连通的,有0个奇点。
两个定理的正确性是显而易见的，既然每条边都要经过一次,那么对于欧拉路,除了起点和终点外,每个点如果进入了一次，显然一定要出去一次，显然是偶点。对于欧拉回路.每个点进入和出去次数一定都是相等的，显然没有奇点。
求欧拉路的算法很简单,使用深度优先遍历即可。
根据一笔画的两个定理,如果寻找欧拉回路,对任意一个点执行深度优先遍历;找欧拉路、则对一个奇点执行dfs,时间复杂度为0(m+n),m为边数,n是点数。输入
第1行n,m,有n个点，m条边,以下m行描述每条边连接的两点。
输出
欧拉路或欧拉回路
题解：
tarjan求欧拉路和欧拉回路
问题 B: Ant Trip
题目描述
给你无向图的 N 个点和 M 条边，保证这 M 条边都不同且不会存在同一点的自环边，现在问你至少要几笔才能所有边都画一遍。（一笔画的时候笔不离开纸）
输入
多组数据，每组数据用空行隔开。 对于每组数据，第一行两个整数 N,M 表示点数和边数。接下去 M 行每行两个整数 a,b，表示 a,b 之间有一条边。
输出
对于每组数据，输出答案。
题解：
tarjan求欧拉路
问题 C: 香甜的黄油（butter）
题目描述
农夫John发现做出全威斯康辛州最甜的黄油的方法:糖。把糖放在一片牧场上，他知道N(l<=N<=500)头奶牛会过来舔它,这样就能做出能卖好价钱的超甜黄油。当然，他将付出额外的费用在奶牛上。
农夫John很聪明。像以前的巴甫洛夫,他知道他可以训练这些奶牛,让它们在听到铃声时去一个特定的牧场。他打算将糖放在那里然后下午发出铃声，以至他可以在晚上挤奶
农夫John知道每头奶牛都在各自喜欢的牧场(一个牧场不一定只有一头牛)。给出各头牛在的牧场和牧场间的路线，找出使所有牛到达的“路程和”最短的牧场(他将把糖放在那)。输入
第1行:三个数:奶牛数N,牧场数P(2<=P<=800),牧场间道路数C(1<=C<=1450)。
第2行到第N+l行: 1到N头奶牛所在的牧场号。
第N+2行到第N+C+1行:每行有三个数:相连的牧场A、B,两牧场间距(1<=D<=255),当然,连接是双向的。输出 一行:输出奶牛必须行走的最小的距离和。
题解：
加权最短路问题
问题D: 嗅探器
题目描述
某军搞信息对抗实战演习，红军成功地侵入了蓝军的内部网络，蓝军共有两个信息中心，红军计划在某台中间服务器上安装一个嗅探器，从而能够侦听到两个信息中心互相交换的所有信息，但是蓝军的网络相当的庞大，数据包从一个信息中心传到另一个信息中心可以不止有一条通路。现在需要你尽快地解决这个问题，应该把嗅探器安装在哪个中间服务器上才能保证所有的数据包都能被捕获？
输入
第一行一个整数 n，表示蓝军网络中服务器的数目。 接下来若干行是对蓝军网络的拓扑结构描述，每行是两个整数 i,j，表示编号为 i 和编号为 j 的两台服务器间存在连接（显然连接是双向的），服务器的编号从 1 开始，一行两个 0 表示网络的拓补结构描述结束，再接下来是两个整数 a,b，分别表示两个中心服务器的编号。
输出
输出编号。如果有多个解输出编号最小的一个，如果找不到任何解，输出 No solution。
题解：
tarjan找割点
问题 E: 旅游航道
题目描述
SGOI 旅游局在 SG-III 星团开设了旅游业务，每天有数以万计的地球人来这里观光，包括联合国秘书长，各国总统和 SGOI 总局局长等。旅游线路四通八达，每天都有众多的载客太空飞船在星团的星球之间来往穿梭，他们保证了任意两个星球之间总是可以通过航道到达。 但是，最近由于财政出现了困难，一些太空飞船也过于古老，又没有足够的资金购买新产品，所有只好取消一些航道。如果某一条航道的删除使得一些星球不能到达，那么这条航道是不能删除的，称之为「主要航道」。 SGOI 旅游局局长希望知道主要航道的数目，但是航道较多，他不能手工计算，于是，他委托你写一个程序，计算主要航道数目。
输入
输入文件包含若干组数据。 每组数据的首行有两个数 m,n。星球的编号从 1 到 m。 以下 n 行每行用两个整数 a,b 描述一条航道的信息，表示从星球 a 到星球 b 是有航道的。数据由 SGOI 旅游局提供，你无需担心数据有错。 输入文件以一行0为结束。
输出
输出文件共有 C 行，第 i 行仅有一个数，表示第 i 组输入数据的主要行道数目。
题解：
找割边
问题 F: 汽车加油行驶问题
题目描述
给定一个 N×N 的方形网格，设其左上角为起点◎，坐标为 (1,1) ，X 轴向右为正， Y 轴向下为正，每个方格边长为 1 ，如图所示。
一辆汽车从起点◎出发驶向右下角终点▲，其坐标为 (N,N)。在若干个网格交叉点处，设置了油库，可供汽车在行驶途中加油。汽车在行驶过程中应遵守如下规则: （1）汽车只能沿网格边行驶，装满油后能行驶 K 条网格边。出发时汽车已装满油，在起点与终点处不设油库。 （2）汽车经过一条网格边时，若其 X 坐标或 Y 坐标减小，则应付费用 B ，否则免付费用。 （3）汽车在行驶过程中遇油库则应加满油并付加油费用 A。 （4）在需要时可在网格点处增设油库，并付增设油库费用 C (不含加油费用 A )。 （5）（1）~（4）中的各数N,K,A,B,C 均为正整数， 且满足约束: 2≤N≤100,2≤K≤10。 设计一个算法，求出汽车从起点出发到达终点的一条所付费用最少的行驶路线。
输入
第一行是 N,K,A,B,C的值。 第二行起是一个N×N 的 0-1 方阵,每行 N 个值,至 N+1 行结束。 方阵的第 i 行第 j 列处的值为 1 表示在网格交叉点 (i,j) 处设置了一个油库,为 0 时表示未设油库。各行相邻两个数以空格分隔。
输出
程序运行结束时,输出最小费用。
题解：
bfs
问题 G: 新年好
题目描述
重庆城里有 n 个车站，m 条双向公路连接其中的某些车站。每两个车站最多用一条公路连接，从任何一个车站出发都可以经过一条或者多条公路到达其他车站，但不同的路径需要花费的时间可能不同。在一条路径上花费的时间等于路径上所有公路需要的时间之和。 佳佳的家在车站 1，他有五个亲戚，分别住在车站 a,b,c,d,e。过年了，他需要从自己的家出发，拜访每个亲戚（顺序任意），给他们送去节日的祝福。怎样走，才需要最少的时间？
输入
第一行：n,m 为车站数目和公路的数目。 第二行：a,b,c,d,e 为五个亲戚所在车站编号。 以下 m 行，每行三个整数 x,y,t，为公路连接的两个车站编号和时间。
输出
输出仅一行，包含一个整数 T，为最少的总时间。
题解:
6次最短路
下午
问题 A: [SCOI2010]生成字符串
题目描述
Rzygg最近接到了一个生成字符串的任务，任务需要他把 n 个 1和 m个 0 组成字符串，但是任务还要求在组成的字符串中，在任意的前 k个字符中，1 的个数不能少于 0的个数。现在Rzygg 想要知道满足要求的字符串共有多少个，聪明的程序员们，你们能帮助他吗？
输入
输入数据只有一行，包括 2个数字 n和 m。
输出
输出数据是一行，包括 1个数字，表示满足要求的字符串数目，这个数可能会很大，只需输出这个数除以 20100403 的余数
题解：
这道题求的数值是C（n+m，m）-C（n+m，m-1）
具体推导在这里
问题 B: [SCOI2010]幸运数字
题目描述
在中国，很多人都把6和8视为是幸运数字！
lxhgww也这样认为，于是他定义自己的“幸运号码”是十进制表示中只包含数字6和8的那些号码，比如68，666，888都是“幸运号码”！但是这种“幸运号码”总是太少了，
比如在[1,100]的区间内就只有6个（6，8，66，68，86，88），于是他又定义了一种“近似幸运号码”。lxhgww规定，凡是“幸运号码”的倍数都是“近似幸运号码”，当然，任何的“幸运号码”也都是“近似幸运号码”，比如12，16，666都是“近似幸运号码”。
现在lxhgww想知道在一段闭区间[a, b]内，“近似幸运号码”的个数。
输入
输入数据是一行，包括2个数字a和b
输出
输出数据是一行，包括1个数字，表示在闭区间[a, b]内“近似幸运号码”的个数
题解：
筛，就硬筛，再加亿点点容斥
问题 C: [SCOI2010]股票交易
题目描述
最近 lxhgww又迷上了投资股票，通过一段时间的观察和学习，他总结出了股票行情的一些规律。
通过一段时间的观察，lxhgww预测到了未来 T 天内某只股票的走势，第 i天的股票买入价为每股 APi，第 i 天的股票卖出价为每股 BPi（数据保证对于每个 i，都有 APi≥BPi），但是每天不能无限制地交易，于是股票交易所规定第 iii 天的一次买入至多只能购买 ASi 股，一次卖出至多只能卖出 BSi 股。
另外，股票交易所还制定了两个规定。为了避免大家疯狂交易，股票交易所规定在两次交易（某一天的买入或者卖出均算是一次交易）之间，至少要间隔 W 天，也就是说如果在第 i天发生了交易，那么从第 i+1 天到第 i+W天，均不能发生交易。同时，为了避免垄断，股票交易所还规定在任何时间，一个人的手里的股票数不能超过 MaxP。
在第 1天之前，lxhgww手里有一大笔钱（可以认为钱的数目无限），但是没有任何股票，当然，T天以后，lxhgww想要赚到最多的钱，聪明的程序员们，你们能帮助他吗？
输入
输入数据第一行包括 3 个整数，分别是 T，MaxP，W。
接下来 T 行，第 i行代表第 i−1 天的股票走势，每行4 个整数，分别表示 APi, BPi, ASi, BSi。
输出
输出数据为一行，包括 111 个数字，表示 lxhgww 能赚到的最多的钱数。
题解：
单调队列优化dp