[USACO2003][poj2185]Milking Grid(kmp的next的应用)
题目:http://poj.org/problem?id=2185题意:就是要求一个字符矩阵的最小覆盖矩阵,可以在末尾不完全重合(即在末尾只要求最小覆盖矩阵的前缀覆盖剩余的尾部就行了)分析:先看一维的,对于一个一维字符串的最小覆盖子串首先肯定是它的一个前缀,而这个前缀的最小长度为n-next[n],...
BZOJ 1607: [Usaco2008 Dec]Patting Heads 轻拍牛头 筛法
1607: [Usaco2008 Dec]Patting Heads 轻拍牛头Time Limit: 20 SecMemory Limit: 256 MB题目连接http://www.lydsy.com/JudgeOnline/problem.php?id=1607Description 今天是贝...
BZOJ 1633: [Usaco2007 Feb]The Cow Lexicon 牛的词典
题目1633: [Usaco2007 Feb]The Cow Lexicon 牛的词典Time Limit: 5 Sec Memory Limit: 64 MBSubmit: 401 Solved: 216[Submit][Status]Description没有几个人知道,奶牛有她们自己的字典...
3384/1750: [Usaco2004 Nov]Apple Catching 接苹果
3384/1750: [Usaco2004 Nov]Apple Catching 接苹果Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 18 Solved: 16[Submit][Status][Discuss]Description 很少有人知...
[USACO07NOV] Milking Time
题目链接动态规划转化成 DAG 然后拓扑求解的思路虽然很简单不过感觉这个新思路会很有用!如果两个事件互不影响并且有先后关系,就可以连一条有向边,跑最长路可以得到最后的最优解实际上这还是个背包…… #include <queue> #include <cstdio> #incl...
洛谷P3067 平衡的奶牛群 [USACO12OPEN] meet-in-the-middle
正解:搜索解题报告:先放下传送门QwQ这题就,双向搜索经典题鸭首先dfs应该挺好想到的我jio得?就是我们不用记录左右分别得分多少只要记下差值就好了嘛能get?然后就先搜左边,记录下每个得分的数量然后再搜右边,每搜出一个ans+=之前左边的可能得分数量然后就欧克克了!啊对了,,,还有一个细节卡了我好...
【bzoj1597】[Usaco2008 Mar]土地购买
1597: [Usaco2008 Mar]土地购买Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 3739 Solved: 1376[Submit][Status][Discuss]Description农夫John准备扩大他的农场,他正在考虑N (...
【USACO 2.2.1】序言页码
【题目描述】一类书的序言是以罗马数字标页码的。传统罗马数字用单个字母表示特定的数值,以下是标准数字表:I 1 L 50 M 1000V 5 C 100X 10 D 500最多3个同样的可以表示为10n的数字(I,X,C,M)可以连续放在一起,表示它们的和:III=3CCC=300可表示为5x1...
BZOJ2097[Usaco2010 Dec] 奶牛健美操
我猜我这样继续做水题会狗带和模拟赛的题很像,贪心搞一下。 #include<bits/stdc++.h> using namespace std; int read(){ int x=,f=;char ch=getchar(); while(ch<''||ch>'')...
USACO Section 4.3 Buy low,Buy lower(LIS)
第一眼看到题目,感觉水水的,不就是最长下降子序列嘛!然后写……就呵呵了..要判重,还要高精度……判重我是在计算中加入各种判断。这道题比看上去麻烦一点,但其实还好吧..#include<cstdio>#include<cstring>#include<iostream&g...
[USACO2006][poj3182]The Grove(巧妙的BFS)
题目;http://poj.org/problem?id=3182题意:一个棋盘中间有一个联通块,给你一个起点让你从起点开始绕联通块外围一圈并回到起点,求最小步数。分析:首先根据数据的范围比较小,所以觉得应该是搜索,而且是BFS。朴素的想法是从起点开始BFS 8个方向扩展,不过这样肯定要跪。注意到这...
BZOJ 1699: [Usaco2007 Jan]Balanced Lineup排队
1699: [Usaco2007 Jan]Balanced Lineup排队Description每天,农夫 John 的N(1 <= N <= 50,000)头牛总是按同一序列排队. 有一天, John 决定让一些牛们玩一场飞盘比赛. 他准备找一群在对列中为置连续的牛来进行比赛. 但是...
USACO 5.4 Twofive(DP)
非常不容易的一题,思路就是DP之后输出路径。但是此题,路径和DP的方式不一样,路径要按字典序输出。开始写了一个版本,N 10000的时候就是过不了,后来才发现,自己的写法有问题,无法保证字典序。看了看题解,其实也不是很懂。终于还有3个题,加油了!! /* ID: cuizhe LANG: C++ T...
Floyd | | jzoj[1218] | | [Usaco2009 Dec]Toll 过路费 | | BZOJ 1774 | | 我也不知道该怎么写
写在前面:老师说这一道题是神题,事实上确实如此,主要是考察对Floyd的理解******************************题目.txt********************************跟所有人一样,农夫约翰以着宁教我负天下牛,休教天下牛负我(原文:宁我负人,休教人负我)的...
【USACO 1.5】SuperPrime Rib
/*TASK: sprimeLANG: C++SOLVE: dfs,后面每增加一位,判断当前是否为素数。第一位不能为0 */#include<cstdio>int n;void dfs(int x,int d){ for(int i=;i<=x/i;i++) i...
BZOJ_1601_[Usaco2008_Oct]_灌水_(最小生成树_Kruskal)
描述http://www.lydsy.com/JudgeOnline/problem.php?id=1601有\(n\)个田地需要灌溉,每个田地可以自己引水,花费为\(w[i]\),或者连接其他被灌溉的田地,花费为\(p[i][j]\),求最小花费.分析我第一眼看以为是dp,发现不对...如果田地不...
【CJOJ1372】【洛谷2730】【USACO 3.2.5】魔板
题面Description在成功地发明了魔方之后,鲁比克先生发明了它的二维版本,称作魔板。这是一张有8个大小相同的格子的魔板:1 2 3 48 7 6 5我们知道魔板的每一个方格都有一种颜色。这8种颜色用前8个正整数来表示。可以用颜色的序列来表示一种魔板状态,规定从魔板的左上角开始,沿顺时针方向依次...
USACO 2.2 Party Lamps 派对灯 (lamps)
题目描述在IOI98的节日宴会上,我们有N(10<=N<=100)盏彩色灯,他们分别从1到N被标上号码。这些灯都连接到四个按钮:按钮1:当按下此按钮,将改变所有的灯:本来亮着的灯就熄灭,本来是关着的灯被点亮。按钮2:当按下此按钮,将改变所有奇数号的灯。按钮3:当按下此按钮,将改变所有偶数...
bzoj usaco 金组水题题解(2.5)
bzoj 2197: [Usaco2011 Mar]Tree Decoration树形dp。。f[i]表示处理完以i为根的子树的最小时间。因为一个点上可以挂无数个,所以在点i上挂东西的单位花费就是i所在子树里的最小单位花费。。所以每次求f[i]只要使子树里的数量都满足要求就好了。。i的祖先还要更多的...
bzoj usaco 金组水题题解(1)
UPD:我真不是想骗访问量TAT。。一开始没注意总长度写着写着网页崩了王仓(其实中午的时候就时常开始卡了= =)。。。。损失了2h(幸好长一点的都单独开了一篇)。。。。吓得赶紧分成两坨。。。。TAT。。。。。。。。。。。。。。—————————————————————————————————————...