3407: [Usaco2009 Oct]Bessie's Weight Problem 贝茜的体重问题 Time Limit: 3 Sec Memory Limit: 128 MB Submit: 88 Solved: 79 [Submit][Status][Discuss] Description 贝茜像她的诸多姊妹一样，因为从约翰的草地吃了太多美味的草而长出了太多的赘肉．所以约翰将她置于一个及其严格的节食计划之中．她每天不能吃多过H(5≤日≤45000)公斤的干草．贝茜只能吃一整捆干草；当她开始吃一捆干草的之后就再也停不下来了．她有一个完整 的N(1≤N≤500)捆可以给她当作晚餐的干草的清单．她自然想要尽量吃到更多的干草．很 …

1655: [Usaco2006 Jan] Dollar Dayz 奶牛商店 Time Limit: 5 Sec Memory Limit: 64 MB Submit: 353 Solved: 190 [Submit][Status][Discuss] Description Farmer John goes to Dollar Days at The Cow Store and discovers an unlimited number of tools on sale. During his first visit, the tools are selling variously for $1, $2, and $3. …

1653: [Usaco2006 Feb]Backward Digit Sums Time Limit: 5 Sec Memory Limit: 64 MB Submit: 349 Solved: 258 [Submit][Status][Discuss] Description FJ and his cows enjoy playing a mental game. They write down the numbers from 1 to N (1 <= N <= 10) in a certain order and then sum adjacent numbers to produce a new list …

#include <iostream> #include <vector> #include <cstring> #include <set> #include <algorithm> #include <cstdio> using namespace std; const int N=1E4+7; int n,k,Q; int siz; int pos[N]; int sum[N]; int dis[N]; bool vis[N]; vector < pair<int,int> > edge[N]; struct node { int …

题目链接 题意：一棵树，给出n-1个边权，然后q组查询，每组查询询问两个点之间的距离。 思路： dfs跑出根到每个点的距离，设为dis[i] 那么u,v两点的距离就是ans = dis[u]+dis[v]-2*dis[lca(u,v)]; 其中lca(u,v)为u,v的最近公共祖先。 这个式子是利用容斥，其实也很直观。。不理解的话画个图就好。 所以终点就是求两个点的LCA. 据说有好多种做法。今天学习了大概是最简单的一种？ 学习链接 //parent为并查集，FIND为并查集的查找操作 //QUERY为询问结点对集合 //TREE为基图有根树 Tarjan(u) visit[u] = true for each (u, v) in …

转载自： 原文链接 树边，前向边，后向边，横叉边，应该说，不是一个图本身有的概念，应该是图进行DFS时才有的概念。图进行DFS会得到一棵DFS树（森林），在这个树上才有了这些概念。对图进行DFS，可以从任意的顶点开始，遍历的方式也是多样的，所以不同的遍历会得到不同的DFS树，进而产生不同的树边，前向边，后向边，横叉边。所以这4种边，是一个相对的概念。 在图的遍历中，往往设置了一个标记数组vis的bool值来记录顶点是否被访问过。但有些时候需要改变vis值的意义。令vis具有3种值并表示3种不同含义 vis = 0,表示该顶点没没有被访问 vis = 1,表示该顶点已经被访问，但其子孙后代还没被访问完，也就没从该点返回 vis = …

1652: [Usaco2006 Feb]Treats for the Cows Time Limit: 5 Sec Memory Limit: 64 MB Submit: 290 Solved: 226 [Submit][Status][Discuss] Description FJ has purchased N (1 <= N <= 2000) yummy treats for the cows who get money for giving vast amounts of milk. FJ sells one treat per day and wants to maximize the money he …

1651: [Usaco2006 Feb]Stall Reservations 专用牛棚 Time Limit: 10 Sec Memory Limit: 64 MB Submit: 700 Solved: 393 [Submit][Status][Discuss] Description Oh those picky N (1 <= N <= 50,000) cows! They are so picky that each one will only be milked over some precise time interval A..B (1 <= A <= B <= 1,000,000), …

1650: [Usaco2006 Dec]River Hopscotch 跳石子 Time Limit: 5 Sec Memory Limit: 64 MB Submit: 440 Solved: 290 [Submit][Status][Discuss] Description Every year the cows hold an event featuring a peculiar version of hopscotch that involves carefully jumping from rock to rock in a river. The excitement takes place on a long, …

Time Limit: 5 Sec Memory Limit: 64 MB Submit: 504 Solved: 265 [Submit][Status][Discuss] Description The cows are building a roller coaster! They want your help to design as fun a roller coaster as possible, while keeping to the budget. The roller coaster will be built on a long linear stretch of land of length L (1 …