算法 – 第 10 页

NOIp 2005 提高组 1 谁拿了最多奖学金

　　十分简单的题目，以前写过，以为是普及组里最垃圾的题目（普及组的水平都不算），就是算分然后判断，也没什么要注意的（对我来说要注意的就是我错过的地方，这个题目是少量的一次性AC的题目。），代码如下（比以前写的好看很多！）：

#include <stdio.h>
struct pep{
char name[21];
int grade;
};

int getgrade(int a, int b, char c, char d, int e)
{
        int n = 0;
        if(a > 80 && e > 0){
                n += 8000;
        }
        if(a > 85 && b > 80){
                n += 4000;
        }
        if(a > 90){
                n += 2000;
        }
        if(a > 85 && d == ‘Y’){
                n += 1000;
        }
        if(b > 80 && c == ‘Y’){
                n += 850;
        }
        return n;
}

int main(void)
{
        struct pep t, max;
        int a, b, e;
        char c, d;
        int n, i;
        int ans = 0;
        max.grade = 0;
        scanf("%d\n", &n);
        for(i = 0; i < n; i++){
                scanf("%s %d %d %c %c %d\n", t.name, &a, &b, &c, &d, &e);
                t.grade = getgrade(a, b, c, d, e);
                ans += t.grade;
                if(t.grade > max.grade){
                        max = t;
                }
        }
        printf("%s\n%d\n%d\n", max.name, max.grade, ans);
        return 0;
}

2010年9月5日

NOIp 2006 提高组 4 2^k进制数

　　这题我以前写过的，现在就当是再温习一遍吧，思路就是递推（也就是动态规划）根据一个公式推导出来的DP方程，首先我用f[i][j]表示第i位数以j开头的数字共有多少个，那么最容易得到的一个转移方程是：
　　f[i][j] = f[i – 1][j + 1] + f[i – 1][j + 2] + ……. + f[i – 1][n – 1] + f[i – 1][n].
　　但是这个方程给我们的感觉就是一个字——太慢了，为什么这么慢呢？因为它就是这么慢，要把所有的一个个相加一次，但是注意到上面我画红的部分！就是用这个公式，这部分能够表示成啥？很简单啊：
　　f[i][j + 1] = f[i – 1][j + 2] + ……. + f[i – 1][n – 1] + f[i – 1][n].
　　那么智商高一点的人就看到玄机了，能够把f[i][j]简化成如下的形式：
　　f[i][j] = f[i][j + 1] + f[i – 1][j + 1]
　　如此一来程序就清晰多了，代码也很好写，要注意的是搜索时j是从后向前搜索，我还是使用面向对象的思想，先封装了一套int类型的，然后再修改成高精度类型的，int类型的（40分）如下：

#include <stdio.h>
typedef int num;
num f[61][513];
num ans;

void give(num a, int b)
{
a = b;
}

void add(num a, num b)
{
a += b;
}

void output(num a)
{
printf("%d", a);
}

int main(void)
{
        int i, j;
        int n, s, k, t, l;
        scanf("%d%d", &s, &n);
        k = 1 << s;
        for(i = 0; i < k; i++){
                give(&f[0][i], 1);
        }
        t = n / s;
        for(i = 1; i <= t; i++){
                for(j = k – i – 1; j >= 1; j–){
                        add(&f[i][j], &f[i][j + 1]);
                        add(&f[i][j], &f[i – 1][j + 1]);
                }
        }
        for(i = 1; i < t; i++){
                for(j = k – i – 1; j >= 1; j–){
                        add(&ans, &f[i][j]);
                }
        }
        l = n – t s;
        if(l == 0){
                l = k;
        }else{
                l = 1 << l;
        }
        for(i = 1; i < l; i++){
                add(&ans, &f[t][i]);
        }
        output(&ans);
        printf("\n");
        return 0;
}
　　详细修改了一番之后，发现主函数中错了，后来详细修改了一番，弄得我以为高精度写错了，仔细检查之后发现两个地方错了，第一个是数组开小了，本来是num f[61][513]，后来发现要使用f[513][513]，再一个就是不能够直接使用用(n – 1)/s，因为如果用30000/1（k = 1, w = 30000）的话那数组又会显得小了，需要f[30000][513]，但是实际上又跟本用不到（因为k很小时最多只有!((1 << k) – 1)种情况，那样的情况很少）。
　　所以最终修改了一大番，确定了AC代码：

#include <math.h>
#include <stdio.h>
#define max(a, b) ((a)>(b)?(a):(b))
#define used 100000000
#define bits ((int)log10(used))
#define MAX 26
typedef struct{
int num[MAX];
int len;
}num;
num f[513][513];
//数组开小了
num ans;

void give(num a, int b)
{
        int i;
        for(i = 0; b != 0; i++){
                a->num[i] = b % used;
                b /= used;
        }
        a->len = i;
}

void add(num a, num b)
{
        int i;
        int len = max(a->len, b->len);
        int re = 0;
        for(i = 0; i < len; i++){
                a->num[i] += b->num[i] + re;
                re = a->num[i] / used;
                a->num[i] %= used;
        }
        if(re > 0){
                a->num[i] = re;
                len++;
        }
        a->len = len;
}

void output(num a)
{
        int i;
        int len = a->len, num = a->num;
        printf("%d", num[len – 1]);
        len–;
        for(i = len – 1; i >= 0; i–){
                printf("%.*d", bits, num[i]);
        }
}

int main(void)
{
        int i, j;
        int n, s, k, t, l;
        scanf("%d%d", &s, &n);
        k = 1 << s;
        t = (n – 1) / s + 1;
        if(t > k){                     //一直没写这个~!! 所以可能会出现各种想象不到的情况, 如:t = 3000
                t = k;
        }
        for(i = 0; i < k; i++){
                give(&f[0][i], 1);
        }
        for(i = 1; i < t; i++){
                for(j = k – i – 1; j >= 1; j–){
                        add(&f[i][j], &f[i][j + 1]);
                        add(&f[i][j], &f[i – 1][j + 1]);
                }
        }
        for(i = 1; i < t; i++){
                for(j = k – i – 1; j >= 1; j–){
                        add(&ans, &f[i][j]);
                }
        }
        l = n % s;
        if(l == 0){
                l = k;
        }else{
                l = 1 << l;
        }
        for(i = 1; i < l; i++){
                add(&ans, &f[t – 1][i]);
        }
        output(&ans);
        printf("\n");
        return 0;
}

2010年9月3日

Noip 2006 提高组 3 作业调度方案

　　大部分OJ的题目全部都少了一些，原题见
　　 http://zqynux.blog.163.com/blog/static/167499597201062811365761/
　　就是简单的贪心，但是要考虑的是首先，A任务的工序2必须在工序1之后完成，而且当满足前面一个条件时（工序2必须在工序1之后完成），尽可能的把任务向前面插：

　　代码如下：
#include <stdio.h>
#define max(a, b) ((a)>(b)?(a):(b))
int order[361];
int mch[19][19];
int time[19][19];
int count[19];
int cpu[19][400];
int used[19];
int ans;

int main(void)
{
        int i, j, k, c, l;
        int m, n, t, s;
        scanf("%d%d", &m, &n);
        for(i = 0; i < m n; i++){
                scanf("%d", &order[i]);
                order[i]–;
        }
        for(i = 0; i < n; i++){
                for(j = 0; j < m; j++){
                        //把n写成了m
                        scanf("%d", &mch[i][j]);
                        mch[i][j]–;
                }
        }
        for(i = 0; i < n; i++){
                for(j = 0; j < m; j++){
                        //把n写成了m
                        scanf("%d", &time[i][j]);
                }
        }
        for(i = 0; i < m n; i++){
                t = order[i];
                s = count[t]++;
                k = used[t];
                while(1){
                        while(cpu[mch[t][s]][k]){
                                k++;
                        }
                        c = 0;
                        while(cpu[mch[t][s]][k + c] == 0 && c < time[t][s]){
                                c++;
                        }
                        if(c == time[t][s]){
                                c = 0;
                                while(c < time[t][s]){
                                        cpu[mch[t][s]][k + c] = 1;
                                        c++;
                                }
                                break;
                        }
                        k += c;
                }
                used[t] = k + time[t][s];
                ans = max(ans, used[t]);
        }
        printf("%d\n", ans);
        return 0;
}

2010年9月2日

NOIp 2006 提高组 2 金明的预算方案

　　首先要考虑的是，如果没有主件和附件的话，那题目将会非常的简单，那这就是最简单的01背包了，但是麻烦的是题目有主件和附件。那我们怎么办呢？不做了？开玩笑，既然你走了OI这条路，那就千万别回头！那我能不能用01背包来处理这个题目呢？当然是能的，注意题目中的这句话“每个主件可以有0个、1个或2个附件。附件不再有从属于自己的附件。”额，这个条件有什么用呢？当然有用啦，那么我就可以转化为01背包了，先只考虑主件，那就可以进行01背包了，然后对每个主件进行记录，每个主件拥有多少个附件，哪些附件，然后再进行动态规划就能解决了。
　　我把思路再整理一下，就是说先判断主件是否该买，如果它有一个附件的话，那么再考虑是否要购买这一个附件；如果有两个附件的话，那么就考虑是否购买第一个附件，第二个附件或者两个附件一起买（考虑他们的时候就一定要加上主件！）
　　代码如下，提交了两次，问题出在一个符号上：

#include <stdio.h>
#define max(a, b) ((a)>(b)?(a):(b))
struct thing{
        int priece, cost;
        struct {
                int priece, cost;
        }sub[2];
        int len;
}buy[60];
int num[60];
int len;
int f[32001];

int main(void)
{
        int m, n;
        int i, j, k;
        int a, b, c;
        struct thing t;
        scanf("%d%d", &m, &n);
        for(i = 0; i < n; i++){
                scanf("%d%d%d", &a, &b, &c);
                if(c == 0){
                        num[len++] = i;
                        buy[i].priece = a b;
                        buy[i].cost = a;
                }else{
                        t = &buy[c – 1];
                        t->sub[t->len].priece = a * b;
                        t->sub[t->len].cost = a;
                        t->len++;
                }
        }
        for(i = 0; i < len; i++){
                t = &buy[num[i]];
                for(j = m; j >= t->cost; j–){
                        f[j] = max(f[j], f[j – t->cost] + t->priece);
                        for(k = 0; k < t->len; k++){
                                if(j – t->cost – t->sub[k].cost >= 0){
                                        f[j] = max(f[j], f[j – t->cost – t->sub[k].cost] + t->priece + t->sub[k].priece);
                                }
                        }
                        if(t->len == 2 && (j – t->cost – t->sub[0].cost – t->sub[1].cost >= 0)){
                                f[j] = max(f[j], f[j – t->cost – t->sub[0].cost – t->sub[1].cost] + t->priece + t->sub[0].priece + t->sub[1].priece);
                                                //把减法写成了加法,,
                        }
                }
        }
        printf("%d\n", f[m]);
        return 0;
}

2010年9月2日

NOIP 2006 提高组 1 能量项链

　　因为以前做过这一题，所以很快就写出来了，不过在一个细节的地方纠结了好久，具体位置见注释。
　　思路和以前是一样的，f[i][j] = max(map[i] map[i + a] map[i + j] + f[i][a] + f[i + a][j – i]); f[i][j]表示从第i个珠子往后j个所能获得的最大能量，然后代码就写出来了：

#include <stdio.h>
int n;
int map[200];
unsigned f[100][101];

void deal(int a, int b)
{
        int i;
        unsigned max = 0, t;
        for(i = 1; i < b; i++){
                t = map[a] map[a + i] map[a + b]
                                        //这里的a+b写成了a + i + 1
                        + f[a][i] + f[(a + i) % n][b – i];
                if(t > max){
                        max = t;
                }
        }
        f[a][b] = max;
}

int main(void)
{
        int i, j;
        unsigned max;
//      freopen("abc.txt", "r", stdin);
        scanf("%d", &n);
        for(i = 0; i < n; i++){
                scanf("%d", &map[i]);
                map[i + n] = map[i];
        }
        for(j = 2; j <= n; j++){
                for(i = 0; i < n; i++){
                        deal(i, j);
                }
        }
        max = 0;
        for(i = 0; i < n; i++){
                if(max < f[i][n]){
                        max = f[i][n];
                }
        }
        printf("%d\n", max);
//      getch();
        return 0;
}

2010年9月1日

NOIp 2007 提高组 4 树网的核

　　这个题目网上有很多题解，不过直接照抄的话确实不太好，我还是说说我自己的过程吧。
　　首先，可以知道的是“核”越长越好，确实说不太清楚，看下面的图吧：

　　如果核是A-B的话，A-B距离X的值为B到X的距离，假设为x，即B至X的距离，但是如果核是A-C的话，那么A-C距离X的值就会小于x，所以“核”还是越长越好！
　　后只需要从一条直径上寻找核就可以了，为什么的话，我觉得吧，最好的“核”选择有两点，第一点如上所述，越长越好；我觉得第二点就是越靠近中点越好，至于为什么的话，你自己想想，中点距离所有点的最长距离就是半径，而重点之外的就会大于半径，那么不就是长了？所以的话还是越靠近中点越好，所以从一条直径搜索应该是够了的（我知道这样解释是行不通的，但是我自己也不知道是什么原因，只好这么说了。）
　　直径的寻找就是随意使用一个点寻找最远的距离的节点，这就是一条直径的一端，然后从最远距离的节点出发再寻找一次最远距离，这就构成了一条直径，至于为什么，距离一个节点最远的距离为什么一定是一条直径的一端，我的理解是距离一个节点最远的距离一定是距离中点的距离加上半径的长度，也就是说最远的距离是先经过中点再去寻找半径。
　　寻找到了半径再根据s求枚举所有的核的可能，这里要注意的一点就是（我烦的错误），寻找d(F, V)的时候是先取距离整条边最长的节点，然后取所有边（核）中最小的一个。
　　代码附上：

#include <stdio.h>
#include <string.h>
#define bzero(a, b) memset((a), 0, (b))
int n, s;
int map[300][300];

int ans = 10000000;

int used[300];
int prev[300];
int dist[300];
int max, loc;

void d(int i, int sum)
{
        int j;
        used[i] = 1;
        if(sum > max){
                loc = i;
                max = sum;
        }
        for(j = 0; j < n; j++){
                if(!used[j] && map[i][j]){
                        dist[j] = sum + map[i][j];
                        prev[j] = i;
                        d(j, dist[j]);
                }
        }
}

void dfs(int node)
{
        bzero(used, sizeof(used));
        bzero(prev, sizeof(prev));
        bzero(dist, sizeof(dist));
        max = 0;
        prev[node] = –1;
        d(node, 0);
}

int lis[300];
int lenth;

void find(void)
{
        int i;
        dfs(0);
        dfs(loc);
        i = loc;
        while(i != –1){
                lis[lenth++] = i;
                i = prev[i];
        }
}

int tmp[90000];

//先删除本路径, 再逐个dfs,, 再恢复路径
void deal(int a, int b)
{
        int i, m;
        //删除本路劲
        for(i = a; i < b; i++){
                tmp[i – a] = map[lis[i]][lis[i + 1]];
                map[lis[i]][lis[i + 1]] = 0;
                map[lis[i + 1]][lis[i]] = 0;
        }
        //获取距离本路径最远的距离
        m = 0;
        for(i = a; i <= b; i++){
                dfs(lis[i]);
                if(m < max){
                        m = max;
                }
        }
        //更新ans
        if(ans > m){
                ans = m;
        }
        //恢复路径
        for(i = a; i < b; i++){
                map[lis[i]][lis[i + 1]] = tmp[i – a];
                map[lis[i + 1]][lis[i]] = tmp[i – a];
        }
}

void work(void)
{
        int i, j;
        int d;
        for(i = 0; i < lenth; i++){
                //寻找尽可能长的核
                d = map[lis[i]][lis[i + 1]];
                for(j = i + 1; j < lenth && d <= s; j++){
                        d += map[lis[j]][lis[j + 1]];
                }
                //获取此核的长度, 并更新ans
                deal(i, j – 1);
        }
}

int main(void)
{
        int i;
        int a, b, c;
        scanf("%d%d", &n, &s);
        for(i = 1; i < n; i++){
                scanf("%d%d%d", &a, &b, &c);
                a–, b–;
                map[a][b] = map[b][a] = c;
        }
        //寻找半径,, 然后用lis数组记录半径的线路
        find();
        //寻找最小的偏心距,,  用ans记录
        work();
        printf("%d\n", ans);
        return 0;
}

2010年8月31日

TYVJ 第三题滑雪解题报告

题目:

背景 Background

成成第一次模拟赛第三道

描述 Description

　　trs喜欢滑雪。他来到了一个滑雪场，这个滑雪场是一个矩形，为了简便，我们用r行c列的矩阵来表示每块地形。为了得到更快的速度，滑行的路线必须向下倾斜。

　　例如样例中的那个矩形，可以从某个点滑向上下左右四个相邻的点之一。例如24-17-16-1，其实25-24-23…3-2-1更长，事实上这是最长的一条。

输入格式 Input Format

输入文件

第1行: 两个数字r，c(1<=r,c<=100)，表示矩阵的行列。

第2..r+1行:每行c个数，表示这个矩阵。

输出格式 Output Format

输出文件

仅一行: 输出1个整数，表示可以滑行的最大长度。
我的解答:

　　我以为题目就是要找出连续的最大的数字呢, 就是说顺着路径找出最大的~! 一提交,, 40分..
#include <stdio.h>
int map[100][100];
int n, m;

int getv(int x, int y)
{
        if(x < 0 || x >= m || y < 0 || y >= n){
                return –1;
        }
        return map[x][y];
}

int main(void)
{
        int i, j;
        int k;
        int a, b;
//      freopen(“abc.txt”, “r”, stdin);
        scanf(“%d%d“, &m, &n);
        for(i = 0; i < m; i++){
                for(j = 0; j < n; j++){
                        scanf(“%d“, &map[i][j]);
                        if(map[i][j] == 1){
                                a = i;
                                b = j;
                        }
                }
        }
        k = 1;
        while(k < m * n){
                if(getv(a – 1, b) == k + 1){
                        a = a – 1;
                        k++;
                        continue;
                }
                if(getv(a + 1, b) == k + 1){
                        a = a + 1;
                        k++;
                        continue;
                }
                if(getv(a, b – 1) == k + 1){
                        b = b – 1;
                        k++;
                        continue;
                }
                if(getv(a, b + 1) == k + 1){
                        b = b + 1;
                        k++;
                        continue;
                }
                break;
        }
        printf(“%d\n“, k);
//      getch();
        return 0;
}

　　后来又以为是求最大的顺序(不一定是1 2 3, 也可以是1 3 4,) 就是跳跃式前进的, 结果是30分..

#include <stdio.h>
int map[100][100];
int n, m;

int getv(int x, int y)
{
        if(x < 0 || x >= m || y < 0 || y >= n){
                return –1;
        }
        return map[x][y];
}

int main(void)
{
        int i, j;
        int k, t, s;
        int a, b;
        int d, f;
//      freopen(“abc.txt”, “r”, stdin);
        scanf(“%d%d“, &m, &n);
        for(i = 0; i < m; i++){
                for(j = 0; j < n; j++){
                        scanf(“%d“, &map[i][j]);
                        if(map[i][j] == 1){
                                a = i;
                                b = j;
                        }
                }
        }
        k = 1;
        while(k < m * n){
                s = 10000000;
                t = getv(a – 1, b);
                if(t > k && t < s){
                        d = a – 1;
                        f = b;
                        s = t;
                }
                t = getv(a + 1, b);
                if(t > k && t < s){
                        d = a + 1;
                        f = b;
                        s = t;
                }
                t = getv(a, b – 1);
                if(t > k && t < s){
                        d = a;
                        f = b – 1;
                        s = t;
                }
                t = getv(a, b + 1);
                if(t > k && t < s){
                        d = a;
                        f = b + 1;
                        s = t;
                }
                if(t == k){
                        break;
                }
                a = d;
                b = f;
                k = s;
        }
        printf(“%d\n“, k);
//      getch();
        return 0;
}

2010年8月27日

TYVJ 第二题第K极值

　　思路很简单, 将数据进行一次排序, 取第t个和倒数第t个, 然后倒数第t个减去第t个, 再判断差是否为素数..
　　听前辈们说NOIp不能使用库函数qsort, 而我一老使用, 为了避免考试0分的情况, 这里就自己写了一个快排, 当快拍的元素少于15个时就使用插入排序进行排序.
　　代码如下:

#include <stdio.h>
#include <math.h>
#define swap(a, b) do{\
        if(!((a) ^ (b))){\
                break;\
        }\
        (a) ^= (b);\
        (b) ^= (a);\
        (a) ^= (b);\
}while(0)
unsigned long map[10000];

int compare(int a, int b)
{
        return a – b;
}

void insert_sort(unsigned long *a, int start, int end)
{
        int i, j;
        int key;
        for(i = start + 1; i <= end; i++){
                key = a[i];
                for(j = i – 1; j >= 0 && compare(key, a[j]) < 0; j–){
                        a[j + 1] = a[j];
                }
                a[j + 1] = key;
        }
}

int getmiddle(unsigned long a[], int s, int e)
{
        int m;
        m = (s + e) / 2;
        if(compare(a[m], a[s]) < 0){
                swap(a[m], a[s]);
        }
        if(compare(a[s], a[e]) > 0){
                swap(a[s], a[e]);
        }
        if(compare(a[m], a[e]) > 0){
                swap(a[m], a[e]);
        }
        return m;
}

void quick_sort(unsigned long *a, int start, int end)
{
        int middle;
        int len = end – start + 1;
        int i, j;
        unsigned key;
        if(len <= 15){
                insert_sort(a, start, end);
                return;
        }
        middle = getmiddle(a, start, end);
        key = a[middle];
        swap(a[end – 1], a[middle]);
        i = start;              //除去三值的头
        j = end – 1;           //除去三值的尾
        while(i < j){
                while(compare(a[++i], key) < 0){
                }
                while(compare(a[–j], key) > 0){
                }
                if(i < j){
                        swap(a[i], a[j]);
                }
        }
        swap(a[i], a[end – 1]);
        quick_sort(a, start, i – 1);
        quick_sort(a, i + 1, end);
}

int isprime(unsigned long n)
{
        int limit = sqrt(n);
        int i;
        if(n == 1 || n == 0){
                return 0;
        }
        for(i = 2; i <= limit; i++){
                if(n % i == 0){
                        return 0;
                }
        }
        return 1;
}

int main(void)
{
        int n, t, i;
        unsigned long ans;
        scanf(“%d%d“, &n, &t);
        for(i = 0; i < n; i++){
                scanf(“%d“, &map[i]);
        }
        quick_sort(map, 0, n – 1);

        ans = map[n – t] – map[t – 1];
        if(isprime(ans)){
                printf(“YES\n“);
        }else{
                printf(“NO\n“);
        }
        printf(“%d\n“, ans);

        return 0;
}

2010年8月27日

NOIp 2007 第三题矩阵取数游戏

　　题目困扰了我很久，后来才知道，该怎么解题。
　　这题说是说矩阵取数，但是仔细看看能够知道，和矩阵没什么关系，只每行的最大值有关，因为每行之间的最大没有任何关系。那么就将矩阵取数转变成了对数组取数，对数组取数很容易看出来是DP，DP方程如下：f[i][j] = max( 2 map[i] + 2 f[i + 1][j], 2 map[j] + 2 f[i][j – 1] )。最初状态是f[i][i] = 2 map[i]。f[i][j]的是i~j之间的能够取的最大值。
　　方程我还解释一下，比如第一个数据吧：

　　　　　2 3

　　　　　1 2 3

　　　　　3 4 2

　　我只说明第一行，f[0][0] = 2, f[1][1] = 4, f[2][2] = 6，然后f[0][1] = max( 2 map[0] + 2 f[1][1], 2 map[1] + 2 f[0][0] ) = 10，也就是说"1 2"这两个数据应该先取1再去二，然后f[1][2] = 14.f[0][2] = 82..
　　就是这样的思路，其实思路我三天前就有了，但是因为数据太大，2^80以上，用long long 都装不下，那只能使用高精度了，但是实在很难下手啊。
　　怎么办？没办法了，只好先用int来写，然后封装起来，再把int改成高精度，啥？这句话没看懂？
　　意思就是说我先写了下面第一段代码，没用高精度，只得了40分，但是下面这个代码的框架封装的很好，然后直接将几个函数修改一下就能够使用高精度了：
#include <stdio.h>
#include <string.h>
/ ===============对使用"数"类型的封装=============== /
typedef struct{
int num;
}num;

void give(num a, int n)
{
a->num = n;
}

void add(num a, num b)
{
a->num += b->num;
}

void addnum(num a, int n)
{
a->num += n;
}

void copy(num a, num b)
{
a->num = b->num;
}

int compare(num a, num b)
{
return a->num – b->num;
}

void output(num a)
{
printf("%d\n", a->num);
}

/ ===============程序的实现=============== /

num f[80][80];
num ans;
num s1, s2;
int map[80];

void srch(int n)
{
        int i, k;
        num t;
        memset(f, 0, sizeof(f));
        for(i = 0; i < n; i++){
                give(&f[i][i], map[i]);
                addnum(&f[i][i], map[i]);
        }
        for(k = 1; k < n; k++){
                for(i = 0; i < n – k; i++){
                        copy(&s1, &f[i + 1][i + k]);
                        addnum(&s1, map[i]);
                        copy(&s2, &f[i][i + k – 1]);
                        addnum(&s2, map[i + k]);
                        if(compare(&s1, &s2) < 0){
                                t = &s2;
                        }else{
                                t = &s1;
                        }
                        copy(&f[i][i + k], t);
                        add(&f[i][i + k], t);
                }
        }
}

int main(void)
{
        int m, n;
        int i, j;
        memset(&ans, 0, sizeof(ans));
        scanf("%d%d", &n, &m);
        for(i = 0; i < n; i++){
                for(j = 0; j < m; j++){
                        scanf("%d", &map[j]);
                }
                srch(m);
                add(&ans, &f[0][m – 1]);
        }
        output(&ans);
        return 0;
}
　　高精度的代码等下发上来。

#include <stdio.h>
#include <string.h>
#include <math.h>
/ =====================高精度实现部分===================== /
#define max(a, b) ((a)>(b)?(a):(b))
#define TOTAL 40
const int used = 100000000;
#define bits ((int)log10(used))
typedef struct{
int num[TOTAL];
int len;
}num;

static void deal(num a)
//防止高精度的漏洞.
//如:used = 10000, give(a, 10000), give(a, 1), give(b, 10000), add(a, b)
//此时a为20001而不是10001
{
        int i;
        for(i = a->len; i < TOTAL; i++){
                a->num[i] = 0;
        }
}

void give(num a, int n)
{
        int i;
        for(i = 0; n; i++){
                a->num[i] = n % used;
                n /= used;
        }
        a->len = i;
        deal(a);
}

void add(num a, num b)
        //这里有个bug, a和b 不能相同
{
        int i;
        int len = max(a->len, b->len);
        int re = 0;

        for(i = 0; i < len; i++){
                a->num[i] += b->num[i] + re;
                re = a->num[i] / used;
                if(re > 0){
                        a->num[i] %= used;
                }
        }
        a->len = len;
        if(re > 0){
                a->len++;
                a->num[i] = re;
                //掉了 a->num[i] = re; 这一行
        }
}

void addnum(num a, int n)
{
        int i;
        int re = 0;
        for(i = 0; n; i++){
                a->num[i] += (n % used) + re;
                n /= used;
                re = a->num[i] / used;
                if(re > 0){
                        a->num[i] %= used;
                }
        }
        a->len = max(i, a->len);
        if(re > 0){
                a->num[i] += re;
                //写成了=re;
                a->len = max(i + 1, a->len);
        }
}

void copy(num a, num b)
{
memcpy(a, b, sizeof(num));
}

int compare(num a, num b)
{
        if(a->len != b->len){
                return a->len – b->len;
        }

        int i;
        for(i = a->len – 1; i >= 0; i–){
                                //是i–不是i++
                if(a->num[i] != b->num[i]){
                        return a->num[i] – b->num[i];
                }
        }
        return 0;
        return a->num – b->num;
}

void output(num a)
{
        int i;
        int len = a->len, num = a->num;
        printf("%d", num[len – 1]);
        len–;
        for(i = len – 1; i >= 0; i–){
                printf("%.d", bits, num[i]);
        }
        printf("\n");
}

/ =====================主函数部分===================== /

num f[80][80];
num ans;
num s1, s2;
int map[80];

void srch(int n)
{
        int i, k;
        num t;
        memset(f, 0, sizeof(f));
        for(i = 0; i < n; i++){
                give(&f[i][i], 2 * map[i]);
        }
        for(k = 1; k < n; k++){
                for(i = 0; i < n – k; i++){
                        copy(&s1, &f[i + 1][i + k]);
                        addnum(&s1, map[i]);
                        copy(&s2, &f[i][i + k – 1]);
                        addnum(&s2, map[i + k]);

                        if(compare(&s1, &s2) < 0){
                                t = &s2;
                        }else{
                                t = &s1;
                        }
                        copy(&f[i][i + k], t);
                        add(&f[i][i + k], t);
                }
        }
}

int main(void)
{
        int m, n;
        int i, j;
        memset(&ans, 0, sizeof(ans));
        scanf("%d%d", &n, &m);
        for(i = 0; i < n; i++){
                for(j = 0; j < m; j++){
                        scanf("%d", &map[j]);
                }
                srch(m);
                add(&ans, &f[0][m – 1]);
        }
        output(&ans);
        return 0;
}

2010年8月24日

NOIP 1998 普及组巧妙填数解题报告

　　很简单的一个题目，没一次AC，因为忘记判断0了，有可能出现十位或个位上有零的情况，代码：
#include <stdio.h>
#include <string.h>
int sum;
int used[10];
int ck[10];

int check(int n)
{
        int t;
        while(n){
                t = n % 10;
                if(ck[t] || (t == 0)){
                        //要考虑不能为0的情况
                        return 0;
                }
                ck[t] = 1;
                n /= 10;
        }
        return 1;
}

void srch(int now)
{
        int i;
        if(now == 3){
                memset(ck, 0, sizeof(ck));
                if(check(sum) && check(2 sum) && check(3 sum)){
                        printf("%d %d %d\n", sum, 2 sum, 3 sum);
                }
                return;
        }
        sum = ((sum << 3) + (sum << 1));
        //sum *= 10;
        for(i = 1; i <= 9; i++){
                sum += i;
                srch(now + 1);
                sum -= i;
        }
        sum /= 10;
}

int main(void)
{
srch(0);
}

2010年8月19日

分类： 算法

分类：算法