籟·来·也

1001 Vowel Counting

题意：给定一串大小写字母组成的字符串，要求进行特定的格式化，其中元音字母全部变大写，辅音字母全部变小写。
做法：Dead Do

1002 The plan of city rebuild

题意：一开始给定一个l个点e1条边的无向图，然后再新加n个点和e2条边，最后再删除m个点（点删除后连着点的边也一起删除了），最后求剩下的图的最小生成树。
做法：加边操作，删边操作（可以不删，直接讲删去的点标记下即可），最后就是个裸的最小生成树。

1003 Marriage Match II

题意：N女N男，有些女男之间有边，某些女女之间是朋友，女男之间可以速配当且仅当女男之间有边，或者女的朋友和该男之间有边。每一轮要进行一次完全匹配，问最多能进行

多少轮这样的完全匹配，其中一个女的不能在某两轮选同一个男的。
做法：首先利用并查集处理朋友关系，构出女男之间的二分图。然后二分答案，假设当前需要匹配X轮，构图，源点到每个女、每个男到汇点流量都是X，女男之间有关系则连边，

最大流等于NX则表示可以完成X轮。

1004 Simplify The Circuit

题意：题没看，别人和我讲的，大概就是有N行并联关系的电阻电路，每行由数字和’-'字符组成，每个被’-'分开的数字是一个电阻，一行中的电阻是串联关系，最后求并联电路的总电阻。
做法：简单的模拟即可，每行中的数字加起来就是一行的电阻总值，每行的值的倒数和再取倒数就是并联电路的总值。这题还不存在短路的情况，所以几乎不会出什么问题。

1005 The Mystery of Triangle

题意：给一个整数N，把一个等边三角形划分成N*N个小正三角形，问划分后的图中一共有多少的三角形，多少个菱形，多少个平行四边形。
做法：分别人肉或者暴力机肉推出前几项，然后用整数序列网搜出公式即可。为了方便可以使用java的高精度，避免出错。根据resty大牛的介绍，可以根据手推直接推出公式的，于是数学太弱不会，只好作弊了……

1006 Tnine

题意：有8个工人，N<=500个工程，每个工程有固定的开始/结束时间、需要人数和收益。保证所有的工程时间不会重叠。每个工程用什么人是可以随意选择的。一个工人完成一个工程后，必须至少休息一天，不能第二天继续干另外一个工程。某些组合一起工作会有额外的收益，当某个工程的组合包含的多种组合的时候，取其中较大的额外收益。问如何安排人来做工程，使得总收益最大。
做法：首先预处理一下，得到每种组合的额外收益。因为题目保证工程的时间不重合，所以把所有工程按照时间排序，然后就可以dp了。dp[i][j]表示做了前i个工程，j的二进制表示第i个工程人员。当某一个工程和上一个工程不是紧挨的时候，j这维是没有用的，因为所有人这个工程都可以使用；而当两个工程是紧挨的时候，根据上一个工程的人员组合，可以确定当前工程可以使用的人员组合。于是转移的复杂度是2^8，于是总复杂度是2^16*500，可以接受。

1007 Nightmare Ⅱ

题意：800 x 800的迷宫，有一个男的，一个女的，两个女的，剩下的格子有空地和墙两种。每个回合所有鬼都会向外扩展两格，然后男的可以走3格，女的走1格。鬼扩散出来的鬼还可以再扩散，切扩散不会被墙阻止。每一个回合都是鬼先扩散，然后男女走。男女要在碰到鬼之前相遇，问最少几回合可以相遇。
做法：根据每个格子离两个鬼的距离，可以首先预处理出每个格子被鬼扩散到的时间。然后就是BFS了，每轮男的走3格，女的走1格，走之前要判断这个格子是否在行动前就被鬼扩散到了，走到的格子也必须是没有被鬼覆盖到的。这题看起来没什么特别难的地方，其实还是很难写对的，比赛时候AC率不到5%……

1008 Need for Speed

题意：一条直线上，警察抓小偷，警察在后面，小偷在前面，距离为S，两者都是从做匀加速直线运动。给定两个人的初速度和加速度，问警察多久能追到小偷，或者永远追不到。
做法：物理题。。。直接列方程，求解即可，记得2次方程可能会退化成1次，wa了一次；还有1次会退化成0次，又wa一次-_-太弱了。。。

1009 Aqua Splash

题意：本题的加强版本见ZOJ 2902，一看到这题就想到当年很土的watashi……20*20的格子，某些格子里有水泡，水泡大小为1-3的时候是正常状态，大于等于4的时候就会爆炸，然后向上下左右各放出一个水滴，第一个碰到的水泡大小会+1，如果超过3了则会继续连锁反应。现在给定初始所有水泡的大小，然后给某一个水泡进行+1操作，问经过连锁反应后是否所有水泡都破裂了。
做法：题目说了每秒分成两部分，第一部分是所有大于等于4的水泡爆炸，第二部分是所有水泡吸收水滴。这样就大大降低了难度，直接按照这个进行模拟即可，很难写错……