Leewings

2.1 The Castle
墙的方位用 1, 2, 4, 8 的组合来表示想到判断墙可以用与 1, 2, 4, 8 的与运算来得到.
构图了之后, 用 floodfill 全图扫一次即可得到房间数和最大的房间大小.
然后枚举删除每个墙, 再由那个房间为起点 floodfill 一遍. 需要注意的是枚举的顺序, 根据题目的约束条件, 应该从西南角开始枚举, 具体枚举允许为外层从西向东, 内层从南到北. 这样就可以求出删除墙后的最大大小和删除的墙的具体方位了.

Leewings

2.1 Ordered Fractions
枚举啊, 利用 gcd 来排除非最简分数…. 注意点编程技巧就好了.
比如说, 使用 sprintf 来记录产生的结果咯~ 还要记录下这个分数的小数形式, 给最后快排结果用..
对了.. 记得开头加上 0/1, 结尾加上 1/1. 那就没什么了.

Leewings

2.1 Sorting A Three-Valued Sequence
这个嘛..
要数学分析一下.
首先, 统计一下有多少个 1, 2, 3.
假设 a 个 1, b 个 2, c 个 3.
那么, 统计, 前 a 个里面有多少个 2 和 3(a2 个 2, a3 个 3); a+1 个到 a+b 个里面多少个 1 和 3(b1, b3); a+b+1 到 n 个里面有多少个 1 和 2(c1, c2).
那么, 结果就是 b1 + c1 + b3, 完了? 没有呢. 可能 1 里面的 3 的个数多于 c 里面 1 的个数, 那么, 多的 3 就会到 2 里面, 这部分要补会. 这部分是: max(0, a3-c1).
这样, 结果就是 b1 + c1 + b3 + max(0, a3-c1).

Leewings

2.1 Healthy Holsteins
背包类问题啊..
可是呢, 数据规模才 2^15 次.. 小啊.
直接枚举选和不选某种饲料~~ 那就是水题来的了.

Leewings

2.1 Hamming Codes
0 是一定要的, 然后从 1 到 2^b 次方里面找 Hamming Codes. 寻找的方法是让待定的数与所有已经得到的数进行异或运算, 统计结果中 1 的个数, 如果 1 个个数大于等于 d, 那么这个数就是 Hamming Codes. 最后输出前 n 个 Hamming Codes 就可以了.

Leewings

2.2 Preface Numbering
模拟 1-3500 内的罗马数字的生成而已…. 其实, 按照数字组合的规律, 是可以使用递推的方法来写的, 但是, 考虑到使用递推, 思考总结的时间加上编程的时间, 不短啊.. 而由于这题数据量小, 模拟复杂度低, 于是直接模拟生成罗马数字来进行计算了.

Leewings

2.2 Subset Sums
太久没做背包类 DP 了.. 然后就是生疏了…. 掌握还是不够熟练啊!
一开始竟然想的是用枚举来做(尽管知道超时..), 然后简单的写了个枚举, 在 20+ 的时候就基本超时了. 虽然知道 USACO 把这题划分到 DP 里了.. 但是, 想了很久都没想到是什么模型.. 唉唉. 后来, 才突然想到, 这不是背包么?
状态转移方程如下(f[i][j] 表示前 i 个数里面组成和为 j 的方案有多少种):

f[i][0] = 1
f[i][j] = f[i – 1][j] + f[i – 1][j – i], i <= j
f[i][j] = f[i – 1][j], i > j

最后注意在输出的时候, 凡是数列的和为奇数的, 这种情况无论如何都无法分组, 都输出 0.

Leewings

2.2 Runaround Numbers
想不到这么弱的一道模拟题会出现在这里…. 训练编程技巧? Orz….
从输入的 m 开始, 按照规则一个个寻找符合条件的数就可以了.. 数据范围可以说是非常小的….

Leewings

2.3 Party Lamps
首先看到这题的数据, 觉得无从下手啊! 然后, 和同学讨论了下..
最后, 得到以下结论:

1. 灯的状态实质上是按钮的状态, 所以只讨论按钮的状态, 这样, 就只有 0000~1111 共 16 种状态了;
2. 若按钮状态里面的 1 的个数 > c, 那么, 无法在 c 次内达到此状态;
3. 若按钮状态里面 1 的个数 mod 2 != c mod 2, 那么, 这种状态同样无法在达到(原理就是每两次按下按钮, 可以改变 2 个 1 成 0 或者对 1 的个数不做任何改变(就是按同一个按钮两次), 这样的话, c 次后, 1 的个数跟 c 同奇同偶).

这样一来, 这题就明了多了, 只要枚举按钮的状态, 然后模拟按钮的行为, 最后判断是否符合开闭的条件, 这样就 OK 了.
其实还有一种优化, 就是将灯的个数压缩成 6 个一组, 然后只考虑 6 个灯的变化就好了. 但是, 由于灯最多只有 100 个, 所以, 我就没做这个优化了, 直接开工.
然后还有一点要说的是.. 由于贪心, 认为用 char 数组来做会省事点.. 结果, 由于本人对 char 数组的处理比较嫩, 所以.. 花了大量的时间来对 char 数组进行管理, 而不是真正的编写这道题目的主体, 亏了.. 不过, 后来有点甜头, 就是写快排的时候, 直接利用 strcmp 和 sprintf 省事了不少…. 总之, 因小失大了!!

Leewings

2.3 The Longest Prefix
这题, 很容易想到是 DP 啊..

F[i] = F[i– j] && 与集合匹配 (F[i] 为布尔数组)

表示进行到第 i 个, 从后面往前 j 个之后是否是 true 且这 j 个组成的字符串出现在了集合中.
对于与集合匹配, 一开始想到的是枚举集合元素, 结果, 第一次提交的时候, 最后一个点爆时间了.. 这路子不对…. 后来一想, 啊, 才 200 个长度为 10 的字符串.. 那就哈希吧~ 开个布尔数组 G.

F[i] = F[i – j] && G[s[i, j]]
s[i, j] -> 原字符串 i 到 j 的子串的哈希值
G[s[i, j]] -> 此哈希值是否为 true(在预处理中先将集合元素的哈希值都算出来)

比较郁闷的是.. 第一次去 999999 哈希.. 最后一个点, 答案差 1.. 然后, 999997 哈希.. AC… RP 啊 RP 啊…T_T

Leewings

2.3 Zero Sum
这题的数据量不大, 枚举每个数字前添加什么符号即可. 但是要注意处理好符号的问题.. 还要注意的是, 第一个数字前不可有符号!!
我是边枚举符号边进行计算.. 这样就加大了编程的复杂度.. 其实, 在将所有数字前的符号都确定下来后, 再一次过进行计算, 然后判断结果是否为0决定是否应该输出, 这样的编程复杂度应该会相对小一点.

Leewings

2.3 Money Systems
简单的背包.. 注意处理好边界条件即可.
状态转移方程:

f[i][j] += f[i - 1][j] + f[i][j - m[i]]
m[i] 为第 i 个纸币的面值.
f[i][j] 表示前 i 个数凑成面值为 j 的种类数

Leewings

2.3 Controlling Companies
每输入一个数据, 用数组f记录i公司拥有j公司的多少股份, 并用函数 add 将间接控制的股份加入. 用数组g记录哪些公司被哪些公司控制, 在 add 中, 每当我们得知某公司控制了某公司超过 50% 的股份后, 就用 update 函数更新控股信息。最后扫描数组g输出即可.

Leewings

2.3 Cow Pedigrees
构造二叉树的种类数的 DP, 方程如下:

f[i][j] = f[i][j] + f[i - 1][x] * f[i - 1][j - 1 - x]

i 为层数, j 为结点数, x 为上一层左结点的个数.

Leewings

2.4 The Tamworth Two
没什么好说的.. 直接同步模拟人和牛的行动就可以了….

Leewings

2.4 Overfencing
利用 2.1 castle 的方法来记录地图, 然后分别从两个出口用广搜做 floodfill 就好了.

Leewings

2.4 Cow Tours
处理完数据后,

1. Floyd-Warshall, 求出原图各点间的最短距离.
2. 求出点 i 与其所能连通的最远点间的距离 longest[i](1 < i <= n).
3. 利用1、2 所得的数据求点 i 所在的图的直径 dia[i] (1 < i <= n).
4. 枚举未连通的两点 i, j, (1 < i, j <= n)

则新的可能的直径

d = longest[i] + dist(i, j) + longest[j];

取 dia[i], dia[j], d 中的最大值为新图的直径(因为有可能原图的直径比 d 长, 那 d 就不是直径了);

ans = min(max(dia[i], dia[j], d))

Leewings

2.4 Bessie Come Home
很直接的 Floyd 一下就好了…. 注意这句话: “Sometimes, two (potentially self-same) pastures are connected by more than one path.”所以要在输入的时候选择最短的一条来保留.

Leewings

2.4 Fractions to Decimals
模拟分数转小数的过程就好了. 注意恶心的输出要求每 76 个字符一行….
判断循环的方法: 记录出现过的余数, 只要已记录的余数再次出现, 那么这之间的数就是循环节了.

Leewings

3.1 Agri-Net
经典的最小生成树, 直接用 Prim 就可以了.

Leewings

3.1 Score Inflation
完全背包, 方程如下:

for (i = 0; i < n; i++)
        for (j = w[i]; j <= m; j++)
            f[j] = max(f[j], f[j - w[i]] + v[i]);

Leewings

3.1 Humble Numbers
为了编写方便, 将 1 当作第 0 个丑数.
对每个给出的质数 a, 从最小的丑数开始, 找到一个丑数 b 使得 c = a * b 恰好大于目前最大的丑数. 那么 min(c) 就是下一个丑数了.
优化: 对于每个质数, 记录它进行到了哪个丑数, 下次寻找丑数的时候直接从记录的位置开始.

Leewings

3.1 Stamps
DP 即可.

初始状态: f[0] = 0; f[i] = MAX_INT;
状态方程: f[i] = min(f[i – v[j]] + 1)

其中, f[i] 表示面值为 i 所需的最少邮票张数; v[j] 表示邮票的面值.
当出现 f[i] > k 时, 即可输出答案为 i – 1.

Leewings

3.1 Contact
根据长度逐位枚举全部的二进制串, 将它们都转换为十进制, 统计对应十进制及长度的重复次数.
再根据题目的限制快排一遍.
最后按照输出要求将十进制转换为二进制输出(注意前导的“0”）就好啦.

Leewings

3.1 Shaping Regions
线段树 + 离散化的应用.
我的方法是对 x 轴进行离散化, 每次对某个矩形就只用插入这个矩形在这一列的情况(当然, 要是那矩形不在这一列上就忽略啊). 具体点呢, 就是从 0 – a 扫, 每一列按照倒序来插入, 这样简化了覆盖的问题. 在插入这一列的数据时, 覆盖上一列形成的线段树, 并做相应的统计(就是统计插入这一列, 相应的颜色会增加多少面积). 但是, 这样会给最后一个点卡住的….
加一个小小的优化, 保存上一列覆盖时的情况(即保存上一列中哪些矩形是插入到线段树的了)以及它们的那个颜色增加了多少面积; 然后在处理这一列的时候, 不急着插入, 先统计这一列矩形的情况, 若与上一列的情况相同, 就直接把上一列的数据再加上去, 然后到下一列, 这样就不需要每一列都覆盖线段树再统计, 省下了不少时间的.
最后就是提交上去 AC 了.

Leewings

3.2 Factorials
一道比较简单的题目.
分析下便可知, 能产生 0 的就质数只有 2 和 5 相乘, 所以可用以下方法来解题:
在乘某个数的时候, 先对这个数进行质因数分解, 将 2 和 5 额外提出来. 然后将剩余部分乘到结果中, 结果只保留最后一位(当然, 也可以保留全部, 拿来练习高精度乘法是个不错的选择~).
最后, 由于一个 2 和一个 5 相乘才能产生一个 0, 而 2 的个数是绝对比 5 多的, 所以额外多提出的 2 要乘回到结果中.
这样就可以将这个结果输出, 完美 AC 了.

Leewings

@凉: 不好意思哦, 我目前只是提供了 feed 输出..

Leewings

3.2 Stringsobits
简单的组合题.
根据组合数的规律从高位到低位倒推出哪些位置是 1 就可以了.

Leewings

3.2 Spinning Wheels
水题… 360s 所有轮子都会回到原始状态, 所以直接模拟 0~359s 内轮子的运动就可以了……

Leewings

3.2 Feed Ratios
水题.. 菜鸟的方法是枚举(也就 100*100*100 的规模)….. 注意有 0 的情况–..
据说简单的方法是用线性代数来解方程…. 小菜我不会的….

Leewings

3.2 Magic Squares
组合题啊….
宽搜, 对每个结点从 A-C 分别模拟变换, 每次变换后将得到的序列算出它是在由 1-8 这 8 个数字组成的 8 位数中的第几个, 最大是 8!. 这样就可以解决判重的问题了.

Leewings

3.2 Sweet Butter
SPFA 呀~
太标准了…. 不多说…..

Leewings

3.3 Riding The Fences
很基本的欧拉回路的问题~ 不过要注意这题阴人的地方….
1. 会出现这样的数据:

83
1 2
1 2
1 2
2 1
2 1
....

2. 不一定有 1 这个点的..

Leewings

3.3 Shopping Offers
水题..
5维的背包….
耐心和细心的编~

Leewings

3.3 Home on the Range
各位观众, 这又是一道水题….
map[i][j] -> 地图信息
f[i][j] -> map[i][j] 这个点 + 这一行之前的点有多少个 1, 如 101111 这一行, 得到的 f[i][k] 为 101234;
g[i][j] -> map[i][j] 这个点 + 这一列之前的点有多少个 1, 如 111111 这一列, 得到的 f[k][j] 为 123456;
get[i][j] – > 以 map[i][j] 为右下角的正方形的边长最大值;
sq[k] -> 以 k 为边长的正方形的个数;

最后枚举正方形的边长 k:

if (get[i - 1][j - 1] >= k - 1 && f[i][j] >= k && g[i][j] >= k)
{
    sq[k]++;
    get[i][j] = k;
}

Leewings

3.3 Camelot
19 个点的题目….

1. 按骑士的走法构建所有点对之间的最短路 d[i][j][k][l](即 从[i, j] 跳到 [k, l] 所要的最少步数), 我是对每个点 BFS 了一遍的..
2. 构建王到达所有点的最少步数 kingdist[i][j], 我又 BFS 了一次..
3. 不理王先, 枚举每个骑士们的汇点, 得出骑士们汇聚在这点的最少步数
   dist[i, j] = ∑d[knight[k].x][knight[k].y][i][j]
4. 要考虑王了, 再次枚举点 [i][j] 作为汇点.
5. 枚举去带王的那个骑士 knight[k]
6. 枚举王在哪个点给骑士带走, 就计算了咯

   ans = min(dist[i][j] - d[knight[k].x][knight[k].y][i][j] + d[knight[k].x][knight[k].y][kinglocation.x][kinglocation.y] + kingdist[i][j])
   kinglocation: 王在给骑士带走的那个点
   kingdist: 王走到这用了多少步

7. 王也有可能自己走到汇点, 所以

   ans = min(ans, dist[i][j] + kingdist[i][j])

这样肯定是超时的, 要加优化:

1. 可行性剪枝: 经证明, 王要是给带走, 一定在王走 1 步之内的区域, 所以在第 6 步最多只用枚举王和王周边的第一圈这 9 个位置(其实我是看了题解才知道的.. 证明我也不会..)
2. 最优化剪枝: 还是在第 6 步

   if (dist[i][j] - d[knight[k].x][knight[k].y][i][j] >= ans)

   直接枚举下一个骑士了吧….

在枚举中要请注意那些骑士无法到达的点.

Leewings

3.3 A Game
我的思路很直观.

d[i]      -> 原始数据
g[i][j]   -> i 到 j 的数字的和
f[i][j].f -> 作为先手取得的分数
f[i][j].l -> 作为后手取得的分数

方程:

f[i][j].f = max(d[i] + f[i + 1][j].l, f[i][j - 1].l + d[j]);
f[i][j].l = g[i][j] - f[i][j].f;

最后就是输出 f[0][n - 1].f 和 f[0][n - 1].l 了.

Leewings

3.4 American Heritage
已知前序和中序求后序的水题….
贴上我研究出来的求后序函数的”精简”代码吧..(要是用 pascal 来写, 就轻松多了……..)

1
2
3
4
5
6
7
8

void getpost(char *pre, char *mid)
{
    if (!strlen(pre) || !strlen(mid)) return;
    char *p = strchr(mid, pre[0]), tmp1[26] = "\0", tmp2[26] = "\0";
    getpost(strncpy(tmp1, pre, strlen(mid) - strlen(p) + 1) + 1, strncpy(tmp2, mid, strlen(mid) - strlen(p)));
    getpost(pre + strlen(mid) - strlen(p), ++p);
    fprintf(fout, "%c", pre[0]);
}

Leewings

3.4 Electric Fence
很简单的数学题啊….
可以用传说中的皮克定理.. 但是菜鸟不懂什么皮克怎么办呢?
我们可以这样考虑, 设 x 轴上的那条边为底边, 剩下两条是侧边.
三角形内部的点数 = 这个三角形外接长方形的所有点(包括边) – 两侧边与长方形两边围成的两个直角三角形的所有点(包括边) – 底边上的所有点 + 3(原三角形的 3 个顶点被重复计数了)
写成 C, 就是读入之后直接:

fprintf(fout, "%d\n", ((p > n ? p : n) + 1) * (m + 1) - Del(n, m) - Del((p > n ? p - n : n - p), m) - (p + 1) + 3);

Del 就是返回侧边与长方形两边围成的直角三角形的总点数, 具体计算方法:
[这个直角三角形外接长方形(注意, 不一定是原来那个长方形了)的所有点 + 对角线经过的点]/ 2
如果不再加上对角线上的点, 则在除 2 的时候就把对角线(即直接三角形的斜边)上的点给分成两份了.
算对角线经过的点可以去枚举.. 当然, 有更简单的方法.
可以证明, 一条在第一象限的线段 AB, 端点 A 在原点, 且端点 B(n, m) 的坐标都是整数, 那么这条线段经过的整点数为 gcd(n, m) + 1, gcd 为最大公约数.

Leewings

3.4 Raucous Rockers
DP 啊.

f[i][j][k] -> 前 i 首歌放在 j 张碟里, 且最后一张还剩 k 分钟.
如果不选第 i 首歌:
f[i][j][k] = f[i - 1][j][k];
如果选第 i 首, 分为第 j 张碟是否为新碟:
f[i][j][k] = max(f[i][j][k], f[i - 1][j][k + time[i]] + 1, f[i - 1][j - 1][0] + 1);

Leewings

3.4 Closed Fences
BT 的计算几何…. 对着样例过的.. 不堪回首……
忽略吧..

Leewings

4.1 Beef McNuggets
数论的题目..

1. 无解: 输入数据有 1
2. 无限解: 输入数据不互质
3. 有限解: 上限一定是最大两个数据的最小公倍数

嗯.. 背包就好了.

Leewings

4.1 Fence Loop
把边看成点(注意区分左右端点, 即若边 1 连接到边 2 的左端点, 那就只能从边 2 的右端点边下一边了), 对每个边直接套用一次 dijkstra.

Leewings

4.2 Cryptcowgraphy
难度很大的一道 DFS.. DFS 本身不难想, 就是枚举 ‘COW’ 的位置, 直至没有 ‘COW’ 了就判断是不是达到目标了. 但是单纯这样只能过很少的点.. 难点就在于在加优化.
优化:

1. hash 判重
2. 可行性剪枝: 若当前串的相邻 ‘C’ ‘O’ ‘W’ 间的子串在目标串中未出现, 就可以剪枝了.
3. 优化搜索顺序: 先搜 ‘O’, 再搜 ‘C’, 最后倒序搜 ‘W’

Leewings

4.1 Fence Rails
DFS..比 Cryptcowgraphy 要简单.
二分能得到的木块的数目, 然后在 dfs 的时候枚举每个木块(rail)的来源木板(board). 重点也是在优化上.

1. 设要切 n 块木块, 则选择最小的 n 块木块来切.
2. 优化搜索顺序: 在搜索的时候, 木块(在 1 的基础上)和木板都从大到小割.
3. 可行性剪枝: 如果切剩的木板(就是无法切下任何木块了)的总和大于木板总长减去要切的木块总长, 那么一定无解的了, 剪吧.

Leewings

4.2 Drainage Ditches
基本的网络流.. 不管用哪个算法都能过的..
我拿来练 dinic 了….

Leewings

4.2 The Perfect Stall
直接飞个匈牙利上去就 AC 了..

Leewings

4.2 Cowcycles
跟着 comment 走….
小技巧, 在复制数组的时候用 memcpy 会快 N 多的~

Leewings

4.2 Job Processing
贪心, 不断的将物品放到用时最短的机器上(就是机器空闲时 + 机器动作需要的时间), 那么 A 中工作时间最长的机器就是 A 需要的时间了.
对于 B, 第一步同 A 处理, 第二步就是将 B 机器加工零件的时间与 A 的逆序相加, 即 B[i] = B[i] + A[n - i + 1]. 最终 B 的答案就是 MAX(B[i]) 了.

Leewings

4.3 Buy Low, Buy Lower
第一问就很简单啦, 就是求最长不下降子序列.
麻烦就麻烦在第二问, 要求有多少个, 还是要不重复的..
关于有多少个, 用 d[i] 表示第 i 天的股价, f[i] 表示最长不下降子序列的长度, g[i] 表示到第 i 天时的最优值的方法数则

1. 若 d[j] > d[i], 且 f[j] >= f[i], 则 g[i] = g[j];
2. 若 d[j] > d[i], 且 f[j] + 1 = f[i], 则 g[i] = g[i] + g[j].

解决重复的方法是做个 Link, link[i] 表示在 i 后面的第一个大于 d[i] 的数的位置, 如 link[9] = 13 表示第 9 天的股价小于等于第 10 – 12 天的但小于第 13 天的; 如果没有符合条件的数, 那么 link[i] = 0;
这样的话, 在 2 的那里加个判断,

if (!link[j] || link[j] > i) g[i] += g[j];

还要注意的是, g 的值会很大, 所以要用高精加来处理.

Leewings

4.4 Pollutant Control
先用 dinic 算出最大流, 再用 flood_fill 来算割线.
其中还要有很多技巧.. 有空再专门写篇文章来说吧.

Leewings

5.4 TeleCowmunication
由于这也是网络流的题目, 我就先跳来做了..
跟 4.4 的 Pollutant Control 一样的算法, 只不过是在初始化的时候先把点拆成边再做.

Leewings

4.3 Street Race

1. 删除每个点, 然后从起点 DFS, 看还能不能到达终点, 如果不能, 那就是必经之点了.
2. 显然, 第二问的中间点肯定是必经之点, 那么, 枚举必经之点, 每次 DFS 该点, 然后删除该点再从起点 DFS. 如果两次 DFS 访问到的点有交集(除去必经之点), 那么这个点就不是中间点.

Leewings

4.3 Letter Game
简单模拟就好了…. 读题最重要!! 读好题了也就 KO 了..

Leewings

4.4 Shuttle Puzzle
可以搜索, 不过很麻烦..
用数学构造或是分析都能找到简单无比的规律, 说出来就不好玩了~(我就是被说出来了..)

Leewings

4.3 The Primes
暴力枚举, 不过要在枚举的顺序上优化….
这题太烦了!!