cow专题

【POJ】3660 Cow Contest floyd（可以拓扑排序？）

Cow Contest Time Limit: 1000MS Memory Limit: 65536KTotal Submissions: 6925 Accepted: 3792 Description N (1 ≤ N ≤ 100) cows, conveniently numbered 1..N, are participating i

BFS —— POJ 3278 Catch That Cow

对应POJ题目：点击打开链接 Catch That Cow Time Limit: 2000MS Memory Limit: 65536KTotal Submissions: 54686 Accepted: 17096 Description Farmer John has been informed of the location of a fugitive cow

USACO Section 2.3 Cow Pedigrees

题意： N个节点深度为K 的正则二叉树求树有几种形态思路：一开始以为是数学题… 看了byvoid的题解才知道是dp… 每棵树由根节点、左子树、右子树构成由此得状态转移树=左子树*右子树节点数和深度是影响答案的属性所以令dp[i][j]表示i个节点深度在j以内的树的形态数深度在j以内的树又两个深度在j-1以内的树和一个根节点构成设左子树k个节

Codeforces 283. B. Cow Program记忆化搜索

output standard output Farmer John has just given the cows a program to play with! The program contains two integer variables, x and y, and performs the following operations on a sequence a1, a2, ..

【POJ3270】【Cow Sorting】

Cow Sorting Time Limit: 2000MS Memory Limit: 65536KTotal Submissions: 6411 Accepted: 2488 Description Farmer John's N (1 ≤ N ≤ 10,000) cows are lined up to be milked in the evening. Each

【POJ3268】【Silver Cow Party】【反向dij】【sizeof失效】

Silver Cow Party Time Limit: 2000MS Memory Limit: 65536KTotal Submissions: 15522 Accepted: 7039 Description One cow from each of N farms (1 ≤ N ≤ 1000) conveniently numbered 1..N is going

POJ 1985 Cow Marathon（树的直径）

题目链接题意：给出一棵树，求出这个树的直径解答：任选一点进行dfs，会找到一个最远点s，在以这个最远点s进行dfs，会找到一个最远点是t，那么s-t就是树的直径。 //#include<bits/stdc++.h>#include<cstdio>#include<algorithm>#include<vector>#include<cstring>using namespace

POJ 2184 Cow Exhibition （处理负值的01背包）

【题目链接】：click here~~ 【题意】：题意：给定n头牛的聪明指数S和幸福指数F，如果存在S的和TS>=0与F的和TF>=0同时成立时，输出TS与TF的和的最大值sum，否则，输出0。【思路】：转化问题，求s和为某个固定值时候最大的f和值，然后遍历这些所有的s和以及对应的f和值，求出总和总和最大的那个。那么这样就是一个0-1背包问题，可以把s值理解

poj3278--Catch That Cow

Catch That Cow Time Limit: 2000MS Memory Limit: 65536KTotal Submissions: 43680 Accepted: 13615 Description Farmer John has been informed of the location of a fugitive cow and wants to catch h

poj3267--The Cow Lexicon(dp:字符串组合)

The Cow Lexicon Time Limit: 2000MS Memory Limit: 65536KTotal Submissions: 8211 Accepted: 3864 Description Few know that the cows have their own dictionary with W (1 ≤ W ≤ 600) words, each con

POJ 2375 Cow Ski Area (强连通分量)

题目地址：POJ 2375 对每个点向与之相邻并h小于该点的点加有向边。然后强连通缩点。问题就转化成了最少加几条边使得图为强连通图，取入度为0和出度为0的点数的较大者即可。注意，当强连通分量只有一个的时候，答案是0，而不是1. 代码如下： #include <iostream>#include <string.h>#include <math.h>#include <queue>

C++ P2883 [USACO07MAR]牛交通Cow Traffic

题目描述随着牛的数量增加，农场的道路的拥挤现象十分严重，特别是在每天晚上的挤奶时间。为了解决这个问题，FJ决定研究这个问题，以能找到导致拥堵现象的瓶颈所在。牧场共有M条单向道路，每条道路连接着两个不同的交叉路口，为了方便研究，FJ将这些交叉路口编号为1..N,而牛圈位于交叉路口N。任意一条单向道路的方向一定是是从编号低的路口到编号高的路口，因此农场中不会有环型路径。同时，可能存在某两个交叉

[POJ 3045] Cow Acrobats （贪心）

POJ - 3045 有若干头牛叠罗汉，每头牛有一个冒险值，为在其上面所有牛的重量，减去其力量值问如何使得最大的冒险值最小挑战上面的题，本来想着用二分答案的方法做虽然觉得自己的思路没什么问题，但是 WA了百度了一发题解，发现这题正解是贪心首先直观感觉力量大的，体重轻的应该在下面，但这有两个因素，不好确定可利用调整法试图找出答案假设我已经找到了答案排列（猜想答案序列

POJ3270 cow sorting 【polya】

题目描述：给你一个数字序列（每个数字唯一），每次你可以交换任意两个数字，代价为这两个数字的和，问最少用多少代价能把这个序列按升序排列好。题目的具体做法是参考刘汝佳的《算法艺术与信息学奥赛》大概思路是：以后再用别种方法解， 1.找出初始状态和目标状态。明显，目标状态就是排序后的状态。 2.画出置换群，在里面找循环。例如，数字是8 4 5 3 2 7 明显，

POJ-1946 Cow Cycling DP

题目大意：公牛比赛，给出的信息有n只公牛，每只牛具有e能量，要求跑d圈所花费的最少时间，同时这n只公牛当中领头跑的牛需要耗费k*k的能量才能跑k圈，其他牛则只需要耗费k的能量。若当中的公牛能量全部耗尽，此时可以舍弃这只公牛，完成到达d个圈的奔跑也是成功的。 Dp[i][j][k] 表示i头牛，每头牛花费了j能量，跑了k圈所花费的最少时间 #include <stdio.h>#i

POJ 3660 Cow Contest 传递闭包确定名次

题目来源：POJ 3660 Cow Contest 题意：n头牛下面m行每行x y 代表牛x打败了牛y 问有几头牛的最终排名是确定的思路：传递闭包如果x打败了y 令a[x][y]=1 并且a[y][x]=-1 其他不知道的都为0 然后floyd 最后对于每头牛数一下是否有n-1个1或者-1(就是不为0) 如果有n-1个不为0 说明该牛和其他牛都确定了状态 #include <c

poj3270 Cow Sorting 置换群

题意：有一个序列，你需要将通过交换使得序列最后单调增。每次交换的代价为交换的两个数的和，求将序列变成单调增地最小代价和。思路：如果有一个序列：8 4 5 3 2 7 ，那么最终的序列为：2 3 4 5 7 8 。如果视作是一个置换群的作用，那么可以写出循环之积：（8 2 7）（4 3 5）。对于每个循环，每个数都至少被交换一次，所以我们应该用循环中的最小值和每个数交换，设循环数的最小值

poj_3278_Catch That Cow_201407241728

Catch That Cow Time Limit: 2000MS Memory Limit: 65536KTotal Submissions: 45959 Accepted: 14400 Description Farmer John has been informed of the location of a fugitive cow and wants to catch h

poj 3623 Best Cow Line, Gold(贪心)

题目大意：从旧的一串字符串中从头或者从尾取数，排列成一个新串，使得新串的字典序最小。解题思路：很明显，这是一个贪心，用了暴力求解。标记两个数，l 和 r 分别表示头和尾的下标。如果头部的字典序小，那么输出头部的，如果尾部的字典序小，那么输出尾部的。如果他们两个是相同的字符，那么继续往下找，直到找到第一个不相等的，或者头下标大于等于尾下标（此时，说明字符串对称，随便输出一个），输出字

POJ3278 Catch That Cow(BFS) 坑爹的RE

Catch That Cow Time Limit: 2000MS Memory Limit: 65536K Description Farmer John has been informed of the location of a fugitive cow and wants to catch her immediately. He starts at a point N (0 ≤ N

POJ 2375 Cow Ski Area（强连通）

POJ 2375 Cow Ski Area 题目链接题意：给定一个滑雪场，每个点能向周围4个点高度小于等于这个点的点滑，现在要建电缆，使得任意两点都有路径互相可达，问最少需要几条电缆思路：强连通缩点，每个点就是一个点，能走的建边，缩点后找入度出度为0的个数的最大值就是答案，注意一开始就强连通了答案应该是0 代码： #include <cstdio>#include

HDU 2838 Cow Sorting

题目链接~~> 做题感悟：开始做时感觉很难，顿时有种百度的想法不过还是坚持了下来. 解题思路：和求逆序数差不多这题是求和。可以开两个数组一个用于记录比当前数小的个数，以记录已经出现的比当前数小的和。这样 best = sum (出现的所有数的和) - 比它小的数的和 + （前面所有数的个数 - 比当前数小的个数） * 当前数的值 . sum - 比它小的数的和即：前面比它大的数的和

POJ - 3268 Silver Cow Party （往返最短路，Floyd，Dijkstra 2次优化）

题目传送门题意：求往返最短路的最大值。 1、先想到Floyd结果超时了。 2、先用1次Dijkstra求出各点到X的距离，然后再用N-1次算出X到各点的距离。 485ms AC。 3、先用1次Dijkstra算各点到X的距离，然后用相反的邻接表的Dijkstra算出点X到各点的距。 0ms AC了！直接Floyd：TLE #define _CRT_SECURE_N

spoj1182 Sorted bit squence/[USACO2003 Dec]Cow Queueing

题目链接：SPOJ的->http://www.spoj.com/problems/SORTBIT/ 题目大意：约翰给每头奶牛用一个数字编号，这些奶牛在集合时，会将自己编号转换成二进制表示，并按照以下规则排队： • 首先，编号的二进制中1 出现次数较少的排在队伍的前面； • 其次，如果1 的数量一样多，那么编号较小的排在前面；举个例子，从4 到15，有12 个数字，顺序应该是 100; 10

[USACO2003 Dec]Cow Queueing数数的梦 (基础水数位DP带注释！)

题目链接：http://acm.tju.edu.cn/toj/showp2839.html(真的找不到链接了) 题目大意：给你一个范围A~B，求出在整数A 到B之间，0到9这十个数字，分别出现了多少次？ 1≤A，B≤10^18 样例输入 129 137 样例输出 1 10 2 9 1 1 1 1 0 1 题解：数位DP 我的第一道数位DP。。尽管是基础水题但是搞了好久

bzoj1697[Usaco2007 Feb] Cow Sorting牛排序

题目链接：bzoj1697 题目大意： N（1 <= N <= 10,000）头牛排队。农夫想把牛按脾气的大小排序（从小到大）。每一头牛的脾气都是一个在1到100，000之间的整数并且没有两头牛的脾气值相同。在排序过程中，可以交换任意两头牛的位置。需要X+Y秒来交换脾气值为X和Y的两头牛。求把所有牛排好序的最短时间。题解：置换跟bzoj1119差不多 #include<cstdi