bzoj 1599: [Usaco2008 Oct]笨重的石子 (暴力)

1599: [Usaco2008 Oct]笨重的石子

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 886  Solved: 614
[Submit][Status][Discuss]

Description

贝西喜欢棋盘游戏和角色扮演类游戏所以她说服Farmer John把她带到玩具店,在那里,她购买了三个不同的骰子,这三个质量均匀的骰子,分别有S1,S2,S3个面。(2 <= S1 <= 20; 2 <= S2 <= 20; 2 <= S3 <= 40). 贝西掷啊掷啊掷啊,想要知道出现几率最大的和是多少。 问题给出三个骰子的面数,让你求出出现几率最大的和是多少。如果有很多种和出现的几率相同,那么就输出小的那一个。

Input

*第一行:三个由空格隔开的整数:s1,s2,s3

Output

*第一行:所要求的解

Sample Input

3 2 3

Sample Output

5

输出详解:

这里是所有可能的情况.

1 1 1 -> 3 1 2 1 -> 4 2 1 1 -> 4 2 2 1 -> 5 3 1 1 -> 5 3 2 1 -> 6

1 1 2 -> 4 1 2 2 -> 5 2 1 2 -> 5 2 2 2 -> 6 3 1 2 -> 6 3 2 2 -> 7

1 1 3 -> 5 1 2 3 -> 6 2 1 3 -> 6 2 2 3 -> 7 3 1 3 -> 7 3 2 3 -> 8

5和6出现的几率都是最大的,所以输出5.

暴力。。。

bzoj1603: [Usaco2008 Oct]打谷机 (纱布题)

Time Limit: 5 Sec  Memory Limit: 64 MB
Submit: 774  Solved: 593
[Submit][Status][Discuss]

Description

Farmer John有一个过时的打谷机(收割小麦),它需要带子来带动。发动机驱动轮1总是顺时针旋转的,用来带动转轮2,转轮2来带动转轮3,等等。一共有n(2<=n<=1000)个转轮(n-1条带子)。上面的图解描述了转轮的两种连接方式,第一种方式使得两个轮子旋转的方向相同,第二种则相反。 给出一串带子的信息: *Si—驱动轮 *Di—被动轮 *Ci—连接的类型(0=直接连接,1=交叉连接) 不幸的是,列出的信息是随即的。 作为样例,考虑上面的图解,n=4,转轮1是驱动轮,可以得知最后转轮4是逆时针旋转的。

Input

*第一行:一个数n *第二行到第n行:每一行有三个被空格隔开的数:Si,Di,Ci

Output

*第一行:一个单独的数,表示第n个转轮的方向,0表示顺时针,1表示逆时针。

Sample Input

4
2 3 0
3 4 1
1 2 0

Sample Output

1
思路:傻逼模拟题。。。。排下序。

bzoj 1602: [Usaco2008 Oct]牧场行走 (bfs,优先队列)

Description

N头牛(2<=n<=1000)别人被标记为1到n,在同样被标记1到n的n块土地上吃草,第i头牛在第i块牧场吃草。 这n块土地被n-1条边连接。 奶牛可以在边上行走,第i条边连接第Ai,Bi块牧场,第i条边的长度是Li(1<=Li<=10000)。 这些边被安排成任意两头奶牛都可以通过这些边到达的情况,所以说这是一棵树。 这些奶牛是非常喜欢交际的,经常会去互相访问,他们想让你去帮助他们计算Q(1<=q<=1000)对奶牛之间的距离。

Input

*第一行:两个被空格隔开的整数:N和Q

*第二行到第n行:第i+1行有两个被空格隔开的整数:AI,BI,LI

*第n+1行到n+Q行:每一行有两个空格隔开的整数:P1,P2,表示两头奶牛的编号。

Output

*第1行到第Q行:每行输出一个数,表示那两头奶牛之间的距离。

Sample Input

4 2

2 1 2

4 3 2

1 4 3

1 2

3 2

Sample Output

2

7

 

思路:直接bfs….貌似因为每个点最多只和两个边相连。。。不用优先队列也行?
1A,好爽23333.

bzoj 1601: [Usaco2008 Oct]灌水 (最小生成树)

1601: [Usaco2008 Oct]灌水

Time Limit: 5 Sec  Memory Limit: 162 MB
Submit: 1624  Solved: 1059
[Submit][Status][Discuss]

Description

Farmer John已经决定把水灌到他的n(1<=n<=300)块农田,农田被数字1到n标记。把一块土地进行灌水有两种方法,从其他农田饮水,或者这块土地建造水库。 建造一个水库需要花费wi(1<=wi<=100000),连接两块土地需要花费Pij(1<=pij<=100000,pij=pji,pii=0). 计算Farmer John所需的最少代价。

Input

*第一行:一个数n

*第二行到第n+1行:第i+1行含有一个数wi

*第n+2行到第2n+1行:第n+1+i行有n个被空格分开的数,第j个数代表pij。

Output

*第一行:一个单独的数代表最小代价.

Sample Input

4
5
4
4
3
0 2 2 2
2 0 3 3
2 3 0 4
2 3 4 0

Sample Output

9

输出详解:

Farmer John在第四块土地上建立水库,然后把其他的都连向那一个,这样就要花费3+2+2+2=9

思路:一开始觉得是dp…..本来打算放弃了。。。后来看到p的值,似乎一定能保证n个点相连。
那么每一个点的水源有两个来源,要么自己建,要么从别人那里来。
然后卡住了QAQ….看了题解。。
好巧妙。。因为自己建水库不好处理,我们可以假设一个源点,认为只有源点有水库,而其他点建水库的价钱认为是修一条源点到那个点的路的价钱,这样就把w[i]转化成了p[i][j]的形式。
然后包括源点在内的n+1个点,求最小生成树。

bzoj1600 [Usaco2008 Oct]建造栅栏 (排列组合)

勤奋的Farmer John想要建造一个四面的栅栏来关住牛们。他有一块长为n(4<=n<=2500)的木板,他想把这块本板切成4块。这四块小木板可以是任何一个长度只要Farmer John能够把它们围成一个合理的四边形。他能够切出多少种不同的合理方案。注意: *只要大木板的切割点不同就当成是不同的方案(像全排列那样),不要担心另外的特殊情况,go ahead。 *栅栏的面积要大于0. *输出保证答案在longint范围内。 *整块木板都要用完。

思路:排列组合。。减法原则。长度为n的木板,有n-1个切点,那么n-1个切点切三刀的方案数就是C(n-1,3) ,但是这里面有不能构成四边形的。

构成四边形的条件是:任意三边之和大于第四边。也就是任意a+b+c>d,可以得到d<n/2

为方便描述,我们不妨认为从左往右切,先且最左边,再切最右边。

并且先讨论最右边的木板是长度最长的。

所以我们最后一刀一定切在n/2之后的地方。

此时无论之前的两刀是怎么切的,由于切完出现的三块的长度和是一定的,所有都一定能构成四边形。

多算的部分就是从n/2点,最左边可以切到3点的方案数。

如果最后一刀切在点i,那么左边还剩下i-1个点,选两个点切,方案数为C(i-1,2)

将多切的方案数sad按照最后一刀的切点累加。

需要注意的是,我们之前为了方便讨论,设最后一个木板是最长的,然而实际上四块木板都有可能是最长的。 所以多切的方案数sad=sad*4

 

哦,听说这题dp也能过。。。。?反正我是想不到。

bc #74 div1 1001 || hdu 5636 Shortest Path (floyd?)

题目链接
题意:有一条n个节点的链,节点i和节点j的距离为abs(i-j)
现在新增加三条边,距离也都为1,然后给出m个询问,每组询问给出两个点s,t,问s,t之间的最短距离。
思路:比赛的时候没搞出来。 观察特点,对于大多数点来说,都是没有直接的改变,只是增加了三条边。总的思路是:之前s到t的距离为abs(s-t),通过枚举中间经过的特殊点,观察是否能使得距离减小。

 

codeforces #346 div 2 D. Bicycle Race (思维,计算几何,公式)

题目链接
题意:给出n+1个点,每次由i点到i+1点,每段线段之间保证不同向或者反向,第一个点和最后一个点保证重合。路径围城的封闭图形中间都是水,问有多少个危险点,使得如果在这个点忘记转弯就会掉进水里。

思路:搞了半天没搞出来qaq

 

From the track description follows that Maria moves the way that the water always located to the right from her, so she could fall into the water only while turning left. To check if the turn is to the left, let’s give every Maria’s moves directions a number: moving to the north — 0, moving to the west — 1, to the south — 2 and to the east — 3. Then the turn is to the left if and only if the number of direction after performing a turn dir is equal to the number before performing a turn oldDir plus one modulo 4.

This solution has complexity O(n).

 

以及还有一个O(1)的做法。。太神啦。。。

One can solve this problem in alternative way. Let the answer be equal to x (that means that the number of inner corners of 270 degrees equals x, but the number of inner corners of 90 degrees to n - x). As soon as the sum of the inner corners’ values of polygon of n vertices is equal to 180 × (n - 2), thenx × 270 + (n - x) × 90 equals to 180 × (n - 2). This leads us to , being the answer for the problem calculated in O(1).

 

codeforces #346 div 2 C. Tanya and Toys (暴力乱搞)

题目链接
题意:有1E9个礼物,第i个礼物价钱是i,然后现在已经有n个不重复的礼物,a[i],m元钱,想尽可能多得买不同种类的礼物,还能买多少个。
思路:先不考虑已经买的,从1连续买到k,然后考虑子啊这个区间内已经买的,等于实际上没有花钱。
反正就是暴力搞啊搞啊。。我也不知道怎么搞。。
结果最后。。方案数为0的时候。。。最后一个答案我是单独输出的。。忘了判断了。。。所以会输出两个0.宝宝心里苦啊。。。。。。。。

codeforces #346 div 2 B. Qualifying Contest (排序)

题目链接
题意:给出选手个数n,下面n行每个选手的信息“名字 区域编号 分数”.保证每个区域至少两个选手。问每个区域能否唯一确定一支二人的队伍(尽可能选分数高的,当要选的人里有分数相同的则不能确定。
思路:排序啊。。。然后搞啊。。结果发现思路没缕清。。。在某一个区域中,决定是否能唯一确定队伍的是第二个人和第三个人的成绩,和第一个人无关。
特殊处理一个区域只有两个人参加的,这种情况肯定能唯一确定队伍。
妈蛋,这种傻逼题卡了一个小时。。。。

codeforces #346 div 2 A. Round House

题目链接

水题
乱搞。

codeforces 484 B Maximum Value (暴力乱搞)

题目链接
题意:给出n个元素的序列,求出最大的a[i]%a[j] (i>=j)
思路:没思路。。。。

Let us iterate over all different aj. Since we need to maximize , then iterate all integer x (suchx divisible by aj) in range from 2aj to M, where M — doubled maximum value of the sequence. For each such x we need to find maximum ai, such ai < x. Limits for numbers allow to do this in time O(1) with an array. After that, update answer by value . Total time complexity is O(nlogn + MlogM)

题解也没有特别懂。。。感觉和筛法有点类似。

不过学到了一个o(1)时间得到小于x的最大数是多少的做法。

Sort the array and just maintain another array A of 10^6 elements where index i stores element just smaller than i

For example consider sorted array [2,4,7,11], then

A(0 indexed) will be [-1,-1,-1,2,2,4,4,4,7,7,7,7,11...]

-1 means no element is smaller than i.

见代码中的b数组。

 

 

 

 

codeforces 652 B. z-sort (简单构造)

题目链接
题意:给出n个元素的序列,问能否得到一个新的序列,使得奇数位置非递减排列,偶数位数非递增排列。
思路:感觉一定可以啊。。。排序以后直接构造。。。

codeforces 334 B. Eight Point Sets (暴力)

题目链接
题意:给出8个点,问能否构成一个8元素集合,使得x1

codeforces 137 C. History (sorting,贪心)

题目链接
题意:给出n个时间的开始和截止时间,保证没有两个时间的开始或者截止时间相同,问有多少个时间被包含在其他事件中。即aj < ai and bi < bj. 思路:没有两个事件的时间相同很关键。 那么我们可以直接按照开始时间为关键字排序,然后结束时间取之前发生了的(可能还没发生完)时间的结束时间的最大值即可。