2.单词（word） 题目描述 FJ想计算他的N(1<=N<=1000)只奶牛的名字的好听度，每个奶牛的名字是一个长度不超过1000的英文字母串。他创建了一个好名字的集合，数量为M(1<=M<=100)，每个好名字的长度不超过30，奶牛的名字中每包含一个好名字(“包含”不一定要求连续)，那么它的好听度就加1。所有的名字都不区分大小写，如名字“Bessie”包含“Be”、“sI”、“EE”、“Es”,但是不包含“eB”。 现在请你帮FJ计算每个奶牛名字的好听度。 输入 第1行: 2个用空格隔开的整数N 和 M； 第2…N+1行: 第i+1行为第i个奶牛的名字； 第N+2…...

3.牛车（cowcar） 题目描述 高速公路上有N(1<=N<=50,000)只奶牛，编号为1…N，每头牛都开着自己的车，第i头牛的车速为S_i(1<=S_i<=1,000,000)km/h，告诉公路上一共有M个车道(1<=M<=N)。为了安全起见，每头牛都遵循以下原则：同车道前面有x头牛，牛的车速就会降低D乘X(0<=D<=5,000)KM/h，当然不会降到0以下，所以车速应该max(S_i-D*X,0)。由于车距很大，所以即使后面的车比前面的车快，你也不用担心会发生碰撞。 高速公路上有一个最低限速L(1<=L<=1,000,000...

4.危险系数（danger） 题目描述 FJ在一条船上，海上有N(1<=N<=100)个岛，编号为1…N，现在他的任务是按照一个给定的访问次序A_1,A_2,….A_M去探索这M(2<=M<=10,000)个岛屿，已经知道任意两个岛屿之间的危险系数，让你找出一个探索序列，只需满足你的探索序列包含给定的A_1…A_M这个序列就可以(不一定要连续)，使得总的危险系数最小。 输入 第1行：两个数, N 和 M 第 2…M+1行：第i+1行表示给定的序列中第i个岛屿A_i 第M+2…N+M+1行：每行N个整数，表示岛屿之间的危险系数，左对角线上一定是0。 输出 输出满足要求的最...

模拟赛16总结 T1 比赛时知道是递归， 调试了很久大样例都炸了， 弄来弄去都一样， 于是去做另一题， 最后只有30分， 后面想了想发现没判断奇数和偶数， 判断完后AC T2 不会其他的办法， 比赛时就打了暴力， 尝试了许多办法， 都没有对， 交了个暴力上去还AC了 T3 比赛时用的贪心， 思路和正解一样， 样例也对了， 最后才30分， 后来才知道错误， a[i]-d*x[i]<l这里的x[i]应该是x[j]， 犯了低级错误， 改过来就AC了 T4 十分简单就可以看出是个最短路， spfa，dij，Floyd都可以 我看到n并不大， 就用了最简单的Floyd， 最后AC 不够仔细，很多细...

1.【GDKOI训练】纸牌游戏（card） 题目描述 Bessie 是一头非常喜欢纸牌的奶牛，虽然她没有大拇指，但她对纸牌有近乎痴迷的喜爱。不幸的是，牛群中的其他牛都不是好的对手。他们的水平真的很差。他们总是以一种完全可预测的方式来玩纸牌！尽管如此，Bessie 仍然可以选择如何获胜。 Bessie 和她的朋友Elsie 在玩一个简单的纸牌游戏，她们拿了一付有2n 张卡片的牌，牌上的数字编号为1- 2n ，并将其均分成两份，一份卡片给Bessie 和一份卡片给Elsie。 然后两人开始玩牌，一共进行n 轮， 在每一轮中，Bessie 和Elsie 都打一张卡，谁的牌大就得一分。 神奇的Bess...

2.【GDKOI训练】音乐节拍（mnotes） 题目描述 FJ准备教他的奶牛弹奏一首歌曲，歌曲由N(1<=N<=50,000)种音节组成，编号为1到N，而且一定按照从1到N的顺序进行弹奏，第i种音节持续B_i(1<=B_i<=10,000)个节拍，节拍从0开始计数，因此从节拍0到节拍B_1-1弹奏的是第1种音节，从B_1到B_1+B_2-1弹奏的是第2种音节，依此类推。 最近奶牛对弹琴不感兴趣了，他们感觉太枯燥了。所以为了保持奶牛们注意力集中，FJ提出Q(1<=Q<=50,000)个问题，问题的格式都是“第T次节拍弹奏的是哪种音节” 每个问题对应一个T_i(...

3.【GDKOI训练】电视游戏问题（vidgame） 题目描述 农夫约翰的奶牛们游戏成瘾！本来FJ是想要按照陶教授的做法拿她们去电击戒瘾的，可是后来他发现奶牛们玩游戏之后比原先产更多的奶。很明显，这是因为满足的牛会产更多的奶。但是，奶牛们在哪个才是最好的游戏平台这个问题上产生了巨大的分歧。一只奶牛想要买一台Xbox 360来跑《光晕3》；另外一只奶牛想要一台任天堂Wii来跑《任天堂明星大乱斗X》；第三只奶牛想要在PlayStation 3上面玩《潜龙谍影4》，顺便还能看某些高画质的电影。 FJ想要在给定的预算内购入一些游戏平台和一些游戏，使他的奶牛们生产最多的奶牛以养育最多的孩子。FJ研究了N...

4.【GDKOI训练】过路费（toll） 题目描述 跟所有人一样，农夫约翰以着宁教我负天下牛，休叫天下牛负我的伟大精神，日日夜夜苦思生财之道。为了发财，他设置了一系列的规章制度，使得任何一只奶牛在农场中的道路行走，都要向农夫约翰上交过路费。 农场中由N（1 <= N <= 250）片草地（标号为1到N），并且有M（1 <= M <= 10000）条双向道路连接草地A_j和B_j（1 <= A_j <= N; 1 <= B_j <= N）。奶牛们从任意一片草地出发可以抵达任意一片的草地。FJ已经在连接A_j和B_j的双向道路上设置一个过路费L_j（...

模拟赛17总结 T1 比赛时开始用暴力， 数据没过， 就用了快排和比较大小， 最后就AC了 T2 比赛时用了二分， 自己弄的大数据直接就卡掉了， 二分出了问题但找不出原因， 提交上去只有70分， 后来看到判断有问题， 改完就成功AC了 T3 开始以为就是个分组背包， 后来样例都过不了， 就用了个01背包， 答案就有些接近了， 最后将dp分为两部分， 1是买这个游戏， 就进行01背包， 2是不买这个游戏， 就跳过，  最后找最大就AC了 T4 比赛用了暴力spfa， 得了30分， 听讲解才知道是个Floyd， 利用中间的k， 进行一些操作， 就AC了 感觉有点进步，但是还要加油！！ 下面附本次比...

1.【GDKOI2004】石子游戏（game） 题目描述 小勇和小实是对好朋友，他们经常一起游戏。 今天他们玩的游戏是这样的：有一个由正方形石头铺成的地板，它的高是2，长度是N。 例如以下是N=3的情况：  现在他们轮流在上面放上长宽分别是1和2的矩形石块，可以横放也可以竖放，但要刚好铺在地板上两个未被覆盖的正方形石头上，当某人不能放上去时他就输了。 例如，某次游戏可能是这样的，小实横放石块在左上面，如下：  然后小勇横放石块在右下面，如下：  这时小实不能再放石块了，所以他输了。小勇比较礼让，他让小实先放。当然，以上的方法可能不是最好的，现在假如他们都绝顶聪明，请你编程判断究竟谁会赢。 输入...

2.【GDKOI2004】汉诺塔（hanoi） 题目描述 古老的汉诺塔问题是这样的：用最少的步数将N个半径互不相等的圆盘从1号柱利用2号柱全部移动到3号柱，在移动的过程中小盘要始终在大盘的上面。 现在再加上一个条件：不允许直接把盘从1号柱移动到3号柱，也不允许直接把盘从3号柱移动到1号柱。 把盘按半径从小到大用1到N编号。每种状态用N个整数表示，第i个整数表示i号盘所在的柱的编号。则N=2时的移动方案为： (1,1)=>(2,1)=>(3,1)=>(3,2)=>(2,2)=>(1,2)=>(1,3)=>(2,3)=>(3,3) 初始状态为第0步，...

2.Icy Perimeter 题目描述 Farmer John要开始他的冰激凌生意了！他制造了一台可以生产冰激凌球的机器，然而不幸的是形状不太规则，所以他现在希望优化一下这台机器，使其产出的冰激凌球的形状更加合理。 机器生产出的冰激凌的形状可以用一个N×N（1≤N≤1000）的矩形图案表示，例如：  每个’.‘字符表示空的区域，每个’#‘字符表示一块1×1的正方形格子大小的冰激凌。 不幸的是，机器当前工作得并不是很正常，可能会生产出多个互不相连的冰激凌球（上图中有两个）。一个冰激凌球是连通的，如果其中每个冰激凌的正方形格子都可以从这个冰激凌球中其他所有的冰激凌格子出发重复地前往东、南、西、北...

3.【GDKOI2004】城市统计（city） 题目描述 中山市的地图是一个nn的矩阵，其中标号为1的表示商业区，标号为0的表示居民区。为了考察市内居民区与商业区的距离，并对此作出评估，市长希望你能够编写一个程序完成这一任务。 居民区i到商业区的距离指的是到距离它最近的商业区j的距离(|Xi-Xj|+|Yi-Yj|)（你可以理解为他们的行列分别作差），而你将统计的是对于城市中的每一个区域k，以它为中心的(2r+1)(2r+1)的矩阵区域内所有居民区到商业区的距离总和。结果同样以n*n的矩阵形式输出。 输入 第一行为t，表示以下有t组数据，每组数据之间以空行隔开，以下： 第一行为n,r(1&lt...

4.【GDKOI2004】香樟树（camphor） 题目描述 被誉为江南四大名木之一的香樟树很有特色，它的树皮粗糙，质地却很均匀，从来没有白杨树的斑斑驳驳、没有柳树的肿瘤结节；树枝树干一分为二、二分为四一路长去，不会偷工减料也不会画蛇添足；树冠的形态是球形的，在天空中画出优美的曲线。 除了上述优点之外，香樟树还有一个秘密武器。那就是……………………它凭借朴实、厚重的优秀品格赢得了小狐狸的青睐！！！ 话说有一天，小狐狸正在湖边散步，忽然一阵风吹来，她赶紧闭上眼睛。当她再次睁开眼睛时，发现美丽的湖畔多出了一排整齐的香樟树。小狐狸非常兴奋，她对每棵树都观察入微，并且数出了它们的叶子个数。她觉得如果相...