BZOJ 1827: [Usaco2010 Mar]gather 奶牛大集会

DescriptionBessie正在计划一年一度的奶牛大集会,来自全国各地的奶牛将来参加这一次集会。当然,她会选择最方便的地点来举办这次集会。每个奶牛居住在 N(1<=N<=100,000) 个农场中的一个,这些农场由N-1条道路连接,并且从任意一个农场都能够到达另外一个农场。道路i连接农场A_i和B_i(1 <= A_i <=N; 1 <= B_i <= N),长度为L_i(1 <= L_i <= 1,000)。集会可以在N个农场中的任意一个举行。另外,每个牛棚中居住者C_i(0 <= C_i <= 1,000- 阅读剩余部分 -

BZOJ 1782: [Usaco2010 Feb]slowdown 慢慢游

Description每天Farmer John的N头奶牛(1 <= N <= 100000,编号1…N)从粮仓走向他的自己的牧场。牧场构成了一棵树,粮仓在1号牧场。恰好有N-1条道路直接连接着牧场,使得牧场之间都恰好有一条路径相连。第i条路连接着A_i,B_i,(1 <= A_i <= N; 1 <= B_i <= N)。奶牛们每人有一个私人牧场P_i (1 <= P_i <= N)。粮仓的门每次只能让一只奶牛离开。耐心的奶牛们会等到他们的前面的朋友们到达了自己的私人牧场后才离开。首先奶牛1离开,前往P_1;然后是奶牛2,以- 阅读剩余部分 -

BZOJ 2705: [SDOI2012]Longge的问题

DescriptionLongge的数学成绩非常好,并且他非常乐于挑战高难度的数学问题。现在问题来了:给定一个整数N,你需要求出∑gcd(i, N)(1<=i <=N)。Input一个整数,为N。Output一个整数,为所求的答案。Sample Input6Sample Output15HINT对于60%的数据,0<N<=2^16。对于100%的数据,0<N<=2^32。Code#include <cstdio> #include <cmath> #define long long long using names- 阅读剩余部分 -

1741: [Usaco2005 nov]Asteroids 穿越小行星群

Description贝茜想驾驶她的飞船穿过危险的小行星群.小行星群是一个NxN的网格(1≤N≤500),在网格内有K个小行星(1≤K≤10000). 幸运地是贝茜有一个很强大的武器,一次可以消除所有在一行或一列中的小行星,这种武器很贵,所以她希望尽量地少用.给出所有的小行星的位置,算出贝茜最少需要多少次射击就能消除所有的小行星.Input第1行:两个整数N和K,用一个空格隔开.第2行至K+1行:每一行有两个空格隔开的整数R,C(1≤R,C≤N),分别表示小行星所在的行和列.Output一个整数表示贝茜需要的最少射击次数,可以消除所有的小行星Sample Input3 4 - 阅读剩余部分 -

【模板】Dijkstra 单源最短路径

Problemhttps://www.luogu.org/problem/show?pid=3371Code#include <queue> #include <cmath> #include <cstdio> #include <cstring> #include <cstdlib> #include <iostream> #include <algorithm> #include <set> using namespace std; const int N = 10010; - 阅读剩余部分 -

BZOJ 3403: [Usaco2009 Open]Cow Line 直线上的牛

Description约翰的N只奶牛(编为1到N号)正在直线上排队.直线上开始的时候一只牛也没有.接下来发生了S(1≤S≤100000)次事件,一次事件可能是以下四种情况之一:一只奶牛加入队伍的左边(输入“AL”).一只奶牛加入队伍的右边(输入“AR”).K只队伍左边奶牛离开(输入“DLK”).K只队伍右边奶牛离开(输入“DRK”).请求出最后的队伍是什么样.数据保证离开的奶牛不会超过队伍里的奶牛数,最后的队伍不空Input第1行输入S,之后S行每行描述一次事件,格式如题目描述所示Output由左到右输出队伍最后的情况Sample Input10 A L A L A R A- 阅读剩余部分 -

BZOJ 4292: [PA2015]Równanie

Description对于一个正整数n,定义f(n)为它十进制下每一位数字的平方的和。现在给定三个正整数k,a,b,请求出满足a<=n<=b且k*f(n)=n的n的个数。Input第一行包含三个正整数k,a,b(1<=k,a,b<=10^18,a<=b)。Output输出一个整数,即满足条件的n的个数。Sample Input51 5000 10000Sample Output3HINT满足的3个n分别为7293,7854和7905。Solution虽然数据范围很大,但是仔细想想平方和最大的数也就 18 个 9,9^2 18 = 1458,发- 阅读剩余部分 -

BZOJ 1050: [HAOI2006]旅行comf

Description给你一个无向图,N(N<=500)个顶点, M(M<=5000)条边,每条边有一个权值Vi(Vi<30000)。给你两个顶点S和T,求一条路径,使得路径上最大边和最小边的比值最小。如果S和T之间没有路径,输出”IMPOSSIBLE”,否则输出这个比值,如果需要,表示成一个既约分数。 备注: 两个顶点之间可能有多条路径。Input第一行包含两个正整数,N和M。下来的M行每行包含三个正整数:x,y和v。表示景点x到景点y之间有一条双向公路,车辆必须以速度v在该公路上行驶。最后一行包含两个正整数s,t,表示想知道从景点s到景点t最大最小速度- 阅读剩余部分 -

BZOJ 1024: [SCOI2009]生日快乐

Descriptionwindy的生日到了,为了庆祝生日,他的朋友们帮他买了一个边长分别为 X 和 Y 的矩形蛋糕。现在包括windy,一共有 N 个人来分这块大蛋糕,要求每个人必须获得相同面积的蛋糕。windy主刀,每一切只能平行于一块蛋糕的一边(任意一边),并且必须把这块蛋糕切成两块。这样,要切成 N 块蛋糕,windy必须切 N-1 次。为了使得每块蛋糕看起来漂亮,我们要求 N块蛋糕的长边与短边的比值的最大值最小。你能帮助windy求出这个比值么?Input包含三个整数,X Y N。1 <= X,Y <= 10000 ; 1 <= N <= 1- 阅读剩余部分 -

BZOJ 1008: [HNOI2008]越狱

Description监狱有连续编号为1...N的N个房间,每个房间关押一个犯人,有M种宗教,每个犯人可能信仰其中一种。如果相邻房间的犯人的宗教相同,就可能发生越狱,求有多少种状态可能发生越狱Input输入两个整数M,N.1<=M<=10^8,1<=N<=10^12Output可能越狱的状态数,模100003取余Sample Input2 3Sample Output6Solution简单的排列组合问题,用到了快速幂。Code#include <cstdio> #include <algorithm> #define long- 阅读剩余部分 -

BZOJ 1003: [ZJOI2006]物流运输

Description物流公司要把一批货物从码头A运到码头B。由于货物量比较大,需要n天才能运完。货物运输过程中一般要转停好几个码头。物流公司通常会设计一条固定的运输路线,以便对整个运输过程实施严格的管理和跟踪。由于各种因素的存在,有的时候某个码头会无法装卸货物。这时候就必须修改运输路线,让货物能够按时到达目的地。但是修改路线是一件十分麻烦的事情,会带来额外的成本。因此物流公司希望能够订一个n天的运输计划,使得总成本尽可能地小。Input第一行是四个整数n(1<=n<=100)、m(1<=m<=20)、K和e。n表示货物运输所需天数,m表示码头总数,- 阅读剩余部分 -

BZOJ 1645: [Usaco2007 Open]City Horizon 城市地平线

DescriptionFarmer John has taken his cows on a trip to the city! As the sun sets, the cows gaze at the city horizon and observe the beautiful silhouettes formed by the rectangular buildings. The entire horizon is represented by a number line with N (1 <= N <= 40,000) buildings. Build- 阅读剩余部分 -

BZOJ 2100: [Usaco2010 Dec]Apple Delivery

Description贝西有两个又香又脆的红苹果要送给她的两个朋友。当然她可以走的C(1<=C<=200000)条“牛路”都被包含在一种常用的图中,包含了P(1<=P<=100000)个牧场,分别被标为1..P。没有“牛路”会从一个牧场又走回它自己。“牛路”是双向的,每条牛路都会被标上一个距离。最重要的是,每个牧场都可以通向另一个牧场。每条牛路都连接着两个不同的牧场P1_i和P2_i(1<=P1_i,p2_i<=P),距离为D_i。所有“牛路”的距离之和不大于2000000000。现在,贝西要从牧场PB开始给PA_1和PA_2牧场各送一个- 阅读剩余部分 -