分类： 技术

这是个水题，我直接使用了库函数qsort进行了排序，然后输出前五个就可以了，唯一想要说的就是明天或后天把Glibc中的qsort代码看下，学习一下是怎么对超级巨大的数据量进行快速排序的，一个个交换肯定不是，这些都明天再说吧。

#include <stdio.h>
#include <stdlib.h>
#define MAX 300
struct grade{
 int a, b, c;
 int id;
}totle[MAX];
int compare(const void *a, const void *b)
{
 struct grade i = *(struct grade *)a, j = *(struct grade *)b;
 int sum1 = i.a + i.b + i.c,
 sum2 = j.a + j.b + j.c;
 if(sum1 == sum2){
 if(i.a == j.a){
 return i.id - j.id;
 }
 return j.a - i.a;
 }
 return sum2 - sum1;
}

int main(void)
{
 int i;
 int n;
 scanf(%d, &n);
 for(i = 0; i < n; i++){
 totle[i].id = i + 1;
 scanf(%d%d%d, &totle[i].a, &totle[i].b, &totle[i].c);
 }
 qsort(totle, n, sizeof(struct grade), compare);
 for(i = 0; i < 5; i++){
 printf(%d %d\\n, totle[i].id, totle[i].a + totle[i].b +
 totle[i].c);
 }
 return 0;
}

这题困扰了我好几天，详细看了别人的题解，自己反复琢磨，终于琢磨透了。
把我的思路讲一下，f[i][j] 表示第i位(从右向左数, 如12中的1是第二位)，则很容易得到一个DP：
f[i][j] = f[i – 1][j + 1] + f[i – 1][j + 2] + f[i – 1][j + 3] + …. + f[i – 1][n] (n为极限，放在后面讲。)
不用说，用这个递推公式绝对会超时，所以还需要对公式观察一下：
f[i][j] = f[i – 1][j + 1] + f[i – 1][j + 2] + f[i – 1][j + 3] + …. + f[i – 1][n]
上面用红色标记出来的能够用f[i][j + 1] 表示，怎么来的？呵呵，就是因为
f[i][j] = f[i – 1][j + 1] + f[i – 1][j + 2] + f[i – 1][j + 3] + …. + f[i – 1][n] 所以
f[i][j + 1] = f[i – 1][j + 2] + f[i – 1][j + 3] + …. + f[i – 1][n].所以
f[i][j] = f[i][j + 1] + f[i – 1][j + 1]
这就好求了，但是这里需要从大数向小数递减（即j是从n – 1 递减到 1）
然后，我提供一个小剪枝，第i个数的最大值位(1 << k) – j，比如只有一位数字的时候（题目要求至少两位，但是这里只是说明。）当k=3的时候，第一位能够选择的数字是1-7；当有两位数字且k=3是，第二位就只能是1~6而不是1~7了（自己思考下）

还有一个重要的就是需要高精度！！别人都说int要压4位运算，但是这里我压了9位，原因很简单，压4位数的原因是99999^2 > 2^32，就是说当遇到最坏情况下的乘法时，只能使用4位，5位就会溢出；但是这个题目要清楚一点，高精度只用实现加法！所以可以压9位，再多的话也是会超时的。
代码就在下面提供了吧:

#include <stdio.h>
#define MAX 24
#define USED 1000000000
#define max(a, b) ((a)>(b)?(a):(b))
typedef unsigned bignum[MAX];
bignum count[513][513];
bignum ans;

void add(bignum a, bignum b)
{
 int i, j, t;
 int c = max(a[0], b[0]);
 unsigned to = 0;
 if(a[0] < b[0]){
 a[0] = b[0];
 }
 for(i = 0; i < c; i++){
 t = MAX - 1 - i;
 a[t] += b[t] + to;
 to = a[t] / USED;
 if(to > 0){
 a[t] %= USED;
 }
 }
 if(to != 0){
 a[MAX - 1 - i] = to; //狂晕,,, 这里的to写成了t 
 a[0]++;
 }
}

void output(bignum n)
{
 int i, t;
 for(i = MAX - n[0]; i <= MAX - 1; i++){
 printf(%.*d, (i == MAX - n[0]) ? 0 : 9, n[i]);
 }
}

int main(void)
{
 int i, j;
 int top, limit;
 int k, w, n;
 scanf(%d%d, &k, &w);
 n = w / k;
 top = limit = (1 << k) - 1;
 if(w - n * k > 0){
 top = (1 << (w - n * k)) - 1;
 n++;
 }
 if(limit < n){
 n = limit;
 }
 for(i = 1; i <= limit; i++){
 count[1][i][0] = 1;
 count[1][i][MAX - 1] = 1;
 }
 for(i = 2; i <= n; i++){
 for(j = limit - i + 1; j >= 1; j--){
 add(count[i][j], count[i - 1][j + 1]);
 add(count[i][j], count[i][j + 1]);
 }
 }
 for(i = 2; i < n; i++){
 for(j = 1; j <= limit; j++){
 add(ans, count[i][j]);
 }
 }
 for(j = 1; j <= top; j++){
 add(ans, count[i][j]);
 }
 output(ans);
 return 0;
}

这题二话不说, 用map[i][j]表示坐标为i, j的点是什么颜色的.. 很快就写出来了, 但是内存超过了,, 内存最多16MB.
没办法, 只好另辟思路, 但是在数据压缩方面我又很弱, 就看标程也花了两三天的时间, 今天终于是看懂了..
用rect记录所有矩形的坐标以及相应的颜色.
程序具体的步骤如下:

输入A, B, N. 记录第一个矩形: (0, 0) (A, B), 颜色为1
接着读入其余的矩形, 设当前是第i个
对i之前所有的矩形迭代, 此时迭代到的是第j个.
判断i是否完全包含j, 即: i.x1 >= j.x1 && i.x2 >= j.x2 && i.y1 <= j.y1 && i.y2 >= j.y2..
若全包围的话, 将第j个矩形删除.
如果没包围的话, 就判断i会将j拆分成几个矩形, 并将j删除, 再分别拆分的矩形分别放入rect中.

/*
LANG: C
ID: zqy11001
PROG: rect1
*/
#include <stdio.h>
#include <string.h>
#define MAX 10001
#define getint(i) scanf(%d, &i)
#define loop(i, j, k, l)\\
if(a.i l b.i){\\
 t = a;\\
 t.j = b.k;\\
 tmp[n++] = t;\\
 a.i = b.i;\\
}

struct rect{
 int t;
 int x1, x2, y1, y2;
}rect[MAX];
int rr;
int color[2500];

int func(struct rect a, const struct rect b, struct rect *tmp)
{
 int n;
 struct rect t;
 if(b.x1 >= a.x2 || b.x2 <= a.x1 || b.y1 >= a.y2 || b.y2 <= a.y1){
 return 0;
 }
 if(b.x1 <= a.x1 && b.x2 >= a.x2 && b.y1 <= a.y1 && b.y2 >= a.y2){
 return -1;
 }

 n = 0;
 loop(x1, x2, x1, <=);
 loop(x2, x1, x2, >=);
 loop(y1, y2, y1, <=);
 loop(y2, y1, y2, >=);
 return n;
}

int main(void)
{
 int n, nr, m;
 int a, b, i, j, k;
 struct rect t[4], cur;
 freopen(rect1.in, r, stdin);
 freopen(rect1.out, w, stdout);
 getint(a);
 getint(b);
 getint(n);

 rect[0].x1 = rect[0].y1 = 0;
 rect[0].x2 = a;
 rect[0].y2 = b;
 rect[0].t = 1;

 rr = 1;
 for(i = 1; i <= n; i++){
 scanf(%d%d%d%d%d, &rect[rr].x1, &rect[rr].y1, 
 &rect[rr].x2, &rect[rr].y2, &rect[rr].t);
 cur = rect[rr++];
 nr = rr - 1;
 for(j = 0; j < nr; j++){
 m = func(rect[j], cur, t);
 if(!m){
 continue;
 }
 if(m < 0){
 memmove(rect + j, rect + j + 1,
 sizeof(struct rect) * (rr - j - 1));
 j--;
 rr--;
 nr--;
 continue;
 }
 rect[j] = t[--m];
 while(m--){
 rect[rr++] = t[m];
 }
 }
 }
 memset(color, 0, sizeof(color));
 for(i = 0; i < rr; i++){
 color[rect[i].t - 1] += (rect[i].x2 - rect[i].x1) *
 (rect[i].y2 - rect[i].y1);
 }

 for(i = 0; i < 2500; i++){
 if(color[i]){
 printf(%d %d\\n, i + 1, color[i]);
 }
 }
 return 0;
}

从这一题开始,, 以后题目我就不贴上来了… 自己去看吧..

这一题开始肯本看不懂,, 后来是反反复复看标程看懂了..

首先要理解这么一个式子吧(算是式子吧“)

已经求出了j-1个丑数,, 现在求第j个丑数

对于每一个素数p乘以一个最小的丑数, 能使积大于第j-1个丑数

在这些乘积中寻找最小的一个即位第j个丑数.

用pindex[i]表示对于第i个素数乘以的最小丑数是多少..

/*
LANG: C
ID: zqy11001
PROG: humble
*/
#include 
#include 
#define MAX 100
#define getint(i) scanf(%d, &i)
#define insert(i) hum[count++] = i

long hum[1000001];
int pindex[MAX];
int prime[MAX];
int count;

int main(void)
{
 int k, n;
 int i;
 int min, m;
 freopen(humble.in, r, stdin);
 freopen(humble.out, w, stdout);
 getint(k);
 getint(n);
 for(i = 0; i < k; i++){
 getint(prime[i]);
 }

 insert(1);
 memset(pindex, 0, sizeof(int)*k);
 while(count <= n){
 min = 0x7FFFFFFF;
 for(i = 0; i < k; i++){
 while(prime[i] * hum[pindex[i]] <= hum[count - 1]){
 pindex[i]++;
 }

 if(prime[i] * hum[pindex[i]] < min){
 min = prime[i] * hum[pindex[i]];
 m = i;
 }
 }
 insert(min);
 }

 printf(%d\\n, hum[n]);
 return 0;
}

Score Inflation

The more points students score in our contests, the happier we here at the USACO are. We try to design our contests so that people can score as many points as possible, and would like your assistance.

We have several categories from which problems can be chosen, where a "category" is an unlimited set of contest problems which all require the same amount of time to solve and deserve the same number of points for a correct solution. Your task is write a program which tells the USACO staff how many problems from each category to include in a contest so as to maximize the total number of points in the chosen problems while keeping the total solution time within the length of the contest.

The input includes the length of the contest, M (1 <= M <= 10,000) (don’t worry, you won’t have to compete in the longer contests until training camp) and N, the number of problem categories, where 1 <= N <= 10,000.

Each of the subsequent N lines contains two integers describing a category: the first integer tells the number of points a problem from that category is worth (1 <= points <= 10000); the second tells the number of minutes a problem from that category takes to solve (1 <= minutes <= 10000).

Your program should determine the number of problems we should take from each category to make the highest-scoring contest solvable within the length of the contest. Remember, the number from any category can be any nonnegative integer (0, one, or many). Calculate the maximum number of possible points.

PROGRAM NAME: inflate
INPUT FORMAT
Line 1:  M, N — contest minutes and number of problem classes 
Lines 2-N+1:  Two integers: the points and minutes for each class

SAMPLE INPUT (file inflate.in)
300 4
100 60
250 120
120 100
35 20

OUTPUT FORMAT
A single line with the maximum number of points possible given the constraints.
SAMPLE OUTPUT (file inflate.out)
605


描述
学生在我们USACO的竞赛中的得分越多我们越高兴。

我们试着设计我们的竞赛以便人们能尽可能的多得分,这需要你的帮助。

我们可以从几个种类中选取竞赛的题目,这里的一个"种类"是指一个竞赛题目的集合,解决集合中的题目需要相同多的时间并且能得到相同的分数。你的任务是写一个程序来告诉USACO的职员,应该从每一个种类中选取多少题目,使得解决题目的总耗时在竞赛规定的时间里并且总分最大。输入包括竞赛的时间,M(1 <= M <= 10,000)(不要担心,你要到了训练营中才会有长时间的比赛)和N,"种类"的数目1 <= N <= 10,000。后面的每一行将包括两个整数来描述一个"种类":

第一个整数说明解决这种题目能得的分数(1 <= points <= 10000),第二整数说明解决这种题目所需的时间(1 <= minutes <= 10000)。你的程序应该确定我们应该从每个"种类"中选多少道题目使得能在竞赛的时间中得到最大的分数。

来自任意的"种类"的题目数目可能任何非负数(0或更多)。

计算可能得到的最大分数。

格式
PROGRAM NAME: inflate

INPUT FORMAT：

(file inflate.in)

第 1 行: M, N–竞赛的时间和题目"种类"的数目。

第 2-N+1 行: 两个整数:每个"种类"题目的分数和耗时。

OUTPUT FORMAT：

(file inflate.out)

单独的一行包括那个在给定的限制里可能得到的最大的分数。

SAMPLE INPUT
300 4
100 60
250 120
120 100
35 20
SAMPLE OUTPUT
605


======================== 华丽的分割线 ========================
　　标准的无限背包,, 看<<背包9讲>>

/*
LANG: C
ID: zqy11001
PROG: inflate
*/
#include <stdio.h>
#define getint(i) scanf(%d, &i)
#define max(a, b) ((a)>(b)?(a):(b))

int f[10001];

int main(void)
{
 int n, m;
 int i, j, t;
 int a, b;
 freopen(inflate.in, r, stdin);
 freopen(inflate.out, w, stdout);
 getint(m);
 getint(n);
 for(i = 1; i <= n; i++){
 scanf(%d%d, &a, &b);
 for(j = b; j <= 10000; j++){
 t = f[j - b] + a;
 f[j] = max(f[j], t);
 }
 }
 printf(%d\\n, f[m]);
 return 0;
}

Agri-Net
Russ Cox
Farmer John has been elected mayor of his town! One of his campaign promises was to bring internet connectivity to all farms in the area. He needs your help, of course.

Farmer John ordered a high speed connection for his farm and is going to share his connectivity with the other farmers. To minimize cost, he wants to lay the minimum amount of optical fiber to connect his farm to all the other farms.

Given a list of how much fiber it takes to connect each pair of farms, you must find the minimum amount of fiber needed to connect them all together. Each farm must connect to some other farm such that a packet can flow from any one farm to any other farm.

The distance between any two farms will not exceed 100,000.

PROGRAM NAME: agrinet
INPUT FORMAT
Line 1:  The number of farms, N (3 <= N <= 100). 
Line 2..end:  The subsequent lines contain the N x N connectivity matrix, where each element shows the distance from on farm to another. Logically, they are N lines of N space-separated integers. Physically, they are limited in length to 80 characters, so some lines continue onto others. Of course, the diagonal will be 0, since the distance from farm i to itself is not interesting for this problem. 

SAMPLE INPUT (file agrinet.in)
4
0 4 9 21
4 0 8 17
9 8 0 16
21 17 16 0

OUTPUT FORMAT
The single output contains the integer length that is the sum of the minimum length of fiber required to connect the entire set of farms.

SAMPLE OUTPUT (file agrinet.out)
28

描述
农民约翰被选为他们镇的镇长！他其中一个竞选承诺就是在镇上建立起互联网，并连接到所有的农场。当然，他需要你的帮助。约翰已经给他的农场安排了一条高速的网络线路，他想把这条线路共享给其他农场。为了使花费最少，他想铺设最短的光纤去连接所有的农场。你将得到一份各农场之间连接费用的列表，你必须找出能连接所有农场并所用光纤最短的方案。每两个农场间的距离不会超过100000

格式
PROGRAM NAME: agrinet

INPUT FORMAT:

(file agrinet.in)

第一行： 农场的个数，N（3<=N<=100）。

第二行..结尾: 后来的行包含了一个N*N的矩阵,表示每个农场之间的距离。理论上，他们是N行，每行由N个用空格分隔的数组成，实际上，他们限制在80个字符，因此，某些行会紧接着另一些行。当然，对角线将会是0，因为不会有线路从第i个农场到它本身。

OUTPUT FORMAT:

(file agrinet.out)

只有一个输出，其中包含连接到每个农场的光纤的最小长度。

SAMPLE INPUT
4
0 4 9 21
4 0 8 17
9 8 0 16
21 17 16 0
SAMPLE OUTPUT
28



======================= 华丽的分割线 =======================
　　这一题就是最小生成树的问题, 说来复杂… 自己看数据结构吧..

/*
LANG: C
ID: zqy11001
PROG: agrinet
*/
#include <stdio.h>
#define getint(i) scanf(%d, &i)
#define MAX 100
#define INF 1e6

int map[MAX][MAX];
int visited[MAX];
int path[MAX];

int main(void)
{
 int n;
 int i, j, k;
 int min, m, tot = 0;
 freopen(agrinet.in, r, stdin);
 freopen(agrinet.out, w, stdout);
 getint(n);
 for(i = 0; i < n; i++){
 for(j = 0; j < n; j++){
 getint(map[i][j]);
 }
 }

 for(i = 0; i < n; i++){
 path[i] = map[0][i];
 }
 visited[0] = 1;
 for(i = 1; i < n; i++){
 min = INF;
 for(j = 0; j < n; j++){
 if(!visited[j] && min > path[j]){
 min = path[j];
 m = j;
 }
 }
 visited[m] = 1;
 tot += min;
 for(j = 0; j < n; j++){
 if(visited[j] == 0 && map[m][j] < path[j]){
 path[j] = map[m][j];
 }
 }
 }
 printf(%d\\n, tot);
 return 0;
}