P2885 [USACO07NOV]电话线Telephone Wire
P2885 [USACO07NOV]电话线Telephone Wire最近，Farmer John的奶牛们越来越不满于牛棚里一塌糊涂的电话服务于是，她们要求FJ把那些老旧的电话线换成性能更好的新电话线。 新的电话线架设在已有的N(2 <= N <= 100,000)根电话线杆上， 第i根...
3360: [Usaco2004 Jan]算二十四
3360: [Usaco2004 Jan]算二十四Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 6 Solved: 6[Submit][Status][Discuss]Description 写一个程序，给出D(2≤D≤10)个数字，按原顺序...
USACO Section 2.4: Bessie Come Home
因为题目给了边的信息，所以比较适用bell-man的方法 /* ID: yingzho1 LANG: C++ TASK: comehome */ #include <iostream> #include <fstream> #include <string> #i...
BZOJ2199: [Usaco2011 Jan]奶牛议会
趁此机会学了一下2-SAT。以前的2-SAT都是用并查集写的，只能应用于极小的一部分情况，这次学了一正式的2-SAT，是用一张有向图来表示其依赖关系。2-SAT的介绍参见刘汝佳《训练指南》。 /*****************************************************...
【USACO 2.4.1】两只塔姆沃斯牛
【题目描述】两只牛逃跑到了森林里。农夫John开始用他的专家技术追捕这两头牛。你的任务是模拟他们的行为(牛和John)。追击在10x10的平面网格内进行。一个格子可以是：一个障碍物, 两头牛(它们总在一起), 或者 农民John. 两头牛和农民John可以在同一个格子内(当他们相遇时)，但是他们都不...
【BZOJ】【1662】/【POJ】【3252】 【USACO 2006 Nov】Round Number
数位DP同上一题Windy数预处理求个组合数然后同样的方法，这次是记录一下0和1的个数然后搞搞Orz cxlove /************************************************************** Problem: 1662 User: ...
BZOJ 1664: [Usaco2006 Open]County Fair Events 参加节日庆祝( dp )
先按时间排序( 开始结束都可以 ) , 然后 dp( i ) = max( dp( i ) , dp( j ) + 1 ) ( j < i && 节日 j 结束时间在节日 i 开始时间之前 ) answer = max( dp( i ) ) ( 1 <= i <= ...
[USACO12MAR] 花盆Flowerpot
类型：二分+单调队列传送门：>Here<题意：给出$N$个点的坐标，要求根据$x$轴选定一段区间$[L,R]$，使得其中的点的最大与最小的$y$值之差$\geq D$。求$Min\{R-L\}$解题思路一道单调队列的好题思想依然是转化。我们熟知的单调队列的作用也就是滑动窗口——定长区间滚...
【USACO17JAN】Promotion Counting晋升者计数 线段树+离散化
题目描述The cows have once again tried to form a startup company, failing to remember from past experience that cows make terrible managers!The cows, conv...
bzoj1670【Usaco2006 Oct】Building the Moat 护城河的挖掘
1670: [Usaco2006 Oct]Building the Moat护城河的挖掘Time Limit: 3 Sec Memory Limit: 64 MBSubmit: 387 Solved: 288[Submit][Status][id=1670" style="color:blue;...
bzoj 1670: [Usaco2006 Oct]Building the Moat护城河的挖掘 -- 凸包
1670: [Usaco2006 Oct]Building the Moat护城河的挖掘Time Limit: 3 Sec Memory Limit: 64 MBDescription为了防止口渴的食蚁兽进入他的农场，Farmer John决定在他的农场周围挖一条护城河。农场里一共有N(8<...
1668: [Usaco2006 Oct]Cow Pie Treasures 馅饼里的财富
1668: [Usaco2006 Oct]Cow Pie Treasures 馅饼里的财富Time Limit: 3 Sec Memory Limit: 64 MBSubmit: 498 Solved: 289[Submit][Status]Description最近，奶牛们热衷于把金币包在面粉...
bzoj 1668: [Usaco2006 Oct]Cow Pie Treasures 馅饼里的财富【记忆化搜索+剪枝】
c[x][y]为从(x,y)到(n,m)的最大值，记忆化一下有个剪枝是因为y只能+1所以当n-x>m-y时就算x也一直+1也是走不到(n,m)的，直接返回0即可#include<iostream>#include<cstdio>using namespace std;c...
BZOJ 1668: [Usaco2006 Oct]Cow Pie Treasures 馅饼里的财富( dp )
dp , dp[ i ][ j ] = max( dp[ k ][ j - 1 ] ) + G[ i ][ j ] ( i - 1 <= k <= i + 1 , dp[ k ][ j - 1 ] > 0 )一开始没注意到要 dp[ k ][ j - 1 ] > 0 才能取 ...
【BZOJ】1668: [Usaco2006 Oct]Cow Pie Treasures 馅饼里的财富（dp）
http://www.lydsy.com/JudgeOnline/problem.php?id=1668裸dp。。f[i][j]表示i行j列最大能拿到f[i][j]=max(f[i+1][j-1], f[i-1][j-1], f[i][j-1])+a[i][j] 当f[i+1][j-1], f[i-...
BZOJ1666: [Usaco2006 Oct]Another Cow Number Game 奶牛的数字游戏
1666: [Usaco2006 Oct]Another Cow Number Game 奶牛的数字游戏Time Limit: 5 Sec Memory Limit: 64 MBSubmit: 502 Solved: 432[Submit][Status]Description奶牛们又在玩一种无...
USACO翻译：USACO 2014 MARCH GOLD P2 Sabotage
1.破坏{DOLD题2}sabotage.pas/c/cpp【问题描述】农夫约翰的头号敌人保罗决定破坏农民约翰的挤奶设备。挤奶设备排成一行，共N（3<= N <=100000）台挤奶机，其中第i个台挤奶机生产M_i单位（1 <= M_i<=10,000）的牛奶。保罗计划切断一...
usaco 月赛 2005 january sumset
2013-09-18 08:23打表找规律w[i]:=w[i-1]; 奇w[i]:=w[i-1]+w[i div 2]; 偶//By BLADEVILvar w :array[..] of longint; i ...
[usaco18Feb] New Barns
题意每次新建一个节点，并与一个已知节点连边。（或者不连）。多次询问以某个已知点点出发的最远路径长度。分析显然，在任何时候图都是一个森林。由树的直径算法可知，与某点最远距的点必然是树的直径的一段。那么考虑在lct中维护直径。实现一篇精彩的LCT,应该像少女穿的迷你裙,越短越好。——林语堂 （误#inc...
Luogu P2852 [USACO06DEC]牛奶模式Milk Patterns
题目链接 \(Click\) \(Here\)水题。利用\(Height\)的性质维护一个单调栈即可。#include <bits/stdc++.h>using namespace std;#define LL long longconst int N = 1000010;int n,...