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)对奶牛之间的距离。

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所需的最 …

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

。。。。天天划水 药丸 妈的智障。

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

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

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

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

题目链接

水题 乱搞。

 1/* ***********************************************
 2Author :111qqz
 3Created Time :2016年03月30日 星期三 23时59分47秒
 4File Name :code/cf/#346/A.cpp
 5************************************************ */
 6
 7#include <cstdio>
 8#include <cstring>
 9#include <iostream>
10#include …

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

Let us iterate over all different _a__j_. Since we need to maximize  , then iterate all integer _x_ (such_x_ divisible by _a__j_) in range from 2_a__j_ to _M_, where _M_ — …

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

题目链接 题意：给出8个点，问能否构成一个8元素集合，使得x1/* *********************************************** Author :111qqz Created Time :2016年03月31日 星期四 13时39分27秒 File Name :code/cf/problem/334B.cpp ************************************************ */

#include #include #include #include #include #include #include #include

题目链接 题意：给出n个时间的开始和截止时间，保证没有两个时间的开始或者截止时间相同，问有多少个时间被包含在其他事件中。即aj < ai and bi < bj.

思路：没有两个事件的时间相同很关键。 那么我们可以直接按照开始时间为关键字排序，然后结束时间取之前发生了的（可能还没发生完）时间的结束时间的最大值即可。

题目链接 题意：给出n个互不相同的元素和k,构成一个集合，使得集合中不存在两个元素满足y=kx,问能构成这样的集合的最大size是多少。 思路：set大法好。很重要的一点是题目中明确说每个元素都不重复。然后每次删掉元素x和元素xk,因为这两个元素最多留一个，然后答案+1. 需要注意k=1的特殊情况。

题目链接 题意：有n天的旅行，但是只剩下了m天的旅行记录，记录格式为d[i],h[d[i]]，表示第i个记录是第d[i]天的，高度为h[d[i]],相邻两天的高度之差的绝对值不超过1.问满足以上条件的最大的h是多少。无解输出impossible. 思路：为了练习二分。 二分高度，然后check是否合法。注意边界，所以可以添加两个点。

题目链接 题意：没图不好描述，有中文题面中文题面，直接看吧。 思路：据说这道题有三种做法。 当时比赛一种都不会。

先说一种：做法是把格子看成点，可以到达的相邻格子之间看成有边相连，然后倒过来用并查集判断无向图的连通性。具体做法是：先统计初始所有空的位置，然后把所有要增加的山都加上（先统计空的位置是因为山之后要去掉，而去掉以后要得到该点的标号），然后将把所有空的点以及china(设标号为n*m+1)点,和india(**设标号为n*m+2) **点通过并查集来合并..可以从上往下从左往右，每次只需要判断上面的点和左边的点是否有空，如果有就用并查集合并。 china点和india点特殊搞就好。

题目链接 題意：已知一个包含 nn 个元素的正整数集合 SS，设 f(S)f(S) 为集合 SS 中所有元素的异或(XOR)的结果。 如：S={1,2,3}, 则 f(S) = 0f(S)=0。

给出集合 SS，你需要计算 将所有 f(s)进行异或后的值, s⊆S.

题目链接 题意；给出一个字符串，只由小写字母组成，可以任意排列，但是不能减少字符，问最多能得到多少个回文串，答案9+7

思路：排列组合题。 首先考虑无解的情况。统计出每个字母出现的次数，当字符串长度为奇数而且出现次数为奇数的字母的个数多于1个时无解，或者当字符串长度为偶数，出现次数为奇数的字母的个数多于0个时无解。 接下来，由于是回文串，只需要考虑len/2的情况，另一半是一一对应的。 其实就是一共有len/2的元素，其中有一些重复的，然后全排列。 多重元素的排列问题。 答案为(len/2)! % （cnt[1]!）% (cnt[2]!)…即可 哦要先把cnt降序排一下，只考虑cnt[i]>1的元素，然后因为是要 …

比赛链接

两题QAQ

A：7分钟1A 有n个大人m个小孩乘公交车，票价每人一元，一个大人最多免费带一个小孩，没有大人陪同的小孩不能乘车。 问是否有解，如果有解输出所有乘客付的钱的可能的最小值和可能的最大值。

题目链接

题意：将正整数n(n<=1E9)，拆分成k个（k<=1E9）个**互不相等的正整数，**并且使得k个正整数的乘积最大。如果可以拆分，输出最大乘积，否则输出-1.