OI路程 – 第 10 页

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日

Noip 2007 提高组字符串的展开解题报告

　　麻烦的题目，第一次只拿了30分，代码如下：

#include <stdio.h>
char str[101];
char ans[1500];
int i, j;
int a, b, c;
int spell = 0;

void init(void)
{
        scanf("%d%d%d\n", &a, &b, &c);
        if(a == 2){
                spell = 0x20;
        }
}

void put(char c1, char c2)
{
        int k;
        if(c1 > c2){
                return;
        }
        if(c == 1){
                if(a != 3){
                        for(k = 0; k < b; k++){
                                ans[j++] = c1 – spell;
                        }
                }else{
                        for(k = 0; k < b; k++){
                                ans[j++] = ‘‘;
                        }
                }
                put(c1 + 1, c2);
        }else{
                if(a != 3){
                        for(k = 0; k < b; k++){
                                ans[j++] = c2 – spell;
                        }
                }else{
                        for(k = 0; k < b; k++){
                                ans[j++] = ‘‘;
                        }
                }
                put(c1, c2 – 1);
        }
}

void change(void)
{
        int k;
        if((str[i – 1] >= str[i + 1]) ||
                (isalpha(str[i – 1]) && !isalpha(str[i +1])) ||
                (isdigit(str[i – 1]) && !isdigit(str[i +1]))){
                                //忘记写!了
                ans[j++] = str[i];
                return ;
        }
        put(str[i – 1] + 1, str[i + 1] – 1);
}

int main(void)
{
        int len;
//      freopen("abc.txt", "r", stdin);
        init();
        scanf("%s", str);
        len = strlen(str);
        //刚刚忘记给len赋值了.
        for(i = j = 0; i < len; i++){
                if(str[i] == ‘-‘){
                        change();
                }else{
                        ans[j++] = str[i];
                }
        }
        ans[j] = ‘\0’;
        printf("%s\n", ans);
//      getch();
        return 0;
}

　　后来认为是要处理整数，就是说比如：10-12展开就是101112，写了好久~！~！~！，还是错了，再一看数据，根本就不用。
　　代码如下：
#include <stdio.h>
#include <ctype.h>
#include <string.h>
char str[101];
int i, j;
int a, b, c;
int spell;

void init(void)
{
        scanf("%d%d%d\n", &a, &b, &c);
        if(a == 2){
                spell = 0x20;
        }
}

void putcha(char c1, char c2)
{
        int k;
        if(c1 > c2){
                return;
        }
        if(a == 3){
                for(k = 0; k < b; k++){
                        putchar(‘‘);
                }
                putcha(c1 + 1, c2);
                return;
        }
        if(c == 1){
                for(k = 0; k < b; k++){
                        putchar(c1 – spell);
                }
                putcha(c1 + 1, c2);
        }else{
                for(k = 0; k < b; k++){
                        putchar(c2 – spell);
                }
                putcha(c1, c2 – 1);
        }
}

int getcount(int n)
{
        int m = 0;
        while(n){
                n /= 10;
                m++;
        }
        return m;
}

void putnum(int c1, int c2)
{
        int k, r;
        if(a == 3){
                while(c1 <= c2){
                        r = getcount(c1);
                        for(k = 0; k < r b; k++){
                                putchar(‘‘);
                        }
                        c1++;
                }
                return;
        }
        if(c == 1){
                while(c1 <= c2){
                        r = getcount(c1);
                        for(k = 0; k < b; k++){
                                printf("%d", c1);
                                j += r;
                        }
                        c1++;
                }
        }else{
                while(c1 <= c2){
                        r = getcount(c2);
                        for(k = 0; k < b; k++){
                                printf("%d", c2);
                                j += r;
                        }
                        c2–;
                }
        }
}

void change(void)
{
        int k;
        if((isalpha(str[i – 1]) && !isalpha(str[i + 1])) && (isdigit(str[i – 1]) && !isdigit(str[i + 1]))){
                                //忘记写!了
                putchar(str[i]);
                return ;
        }
        if(isalpha(str[i – 1]) && (str[i – 1] < str[i + 1])){
                putcha(str[i – 1] + 1, str[i + 1] – 1);
        }else if(isdigit(str[i – 1])){
                int k, r, d;
                for(d = i – 1; d >= 0 && isdigit(str[d]); d–){
                        ;
                }
                sscanf(&str[d + 1], "%d–%d", &k, &r);
                if(k < r){
                        putnum(k + 1, r – 1);
                }else{
                        putchar(‘-‘);
                }
        }else{
                        putchar(‘-‘);
        }
}

int main(void)
{
        int len;
        init();
        scanf("%s", str);
        len = strlen(str);
        //刚刚忘记给len赋值了.
        for(i = j = 0; i < len; i++){
                if(str[i] == ‘-‘){
                        change();
                }else{
                        putchar(str[i]);
                }
        }
        printf("\n");
        return 0;
}
　　正确代码还在撰写中。。。
　　辛辛苦苦修改了一次，还只有70分，这个代码就不发上来了吧。
　　根据数据修改了好几次，第一次没考虑到–的情况，第二次忘记考虑当a=2而转换数字时的情况。
　　代码如下：
#include <stdio.h>
#include <ctype.h>
#include <string.h>
char str[101];
int i;
int a, b, c;
int spell;

void init(void)
{
        scanf("%d%d%d\n", &a, &b, &c);
        if(a == 2){
                spell = 0x20;
        }
}

void output(char c1, char c2)
{
        int k;
        if(a == 3){
                while(c1 <= c2){
                        for(k = 0; k < b; k++){
                                putchar(‘‘);
                        }
                        c1++;
                }
                return ;
        }
        if(isdigit(c1)){
                //要考虑数字但是a=2的情况
                while(c1 <= c2){
                        for(k = 0; k < b; k++){
                                putchar(c1);
                        }
                        c1++;
                }
        }else if(c == 1){
                while(c1 <= c2){
                        for(k = 0; k < b; k++){
                                putchar(c1 – spell);
                        }
                        c1++;
                }
        }else{
                while(c1 <= c2){
                        for(k = 0; k < b; k++){
                                putchar(c2 – spell);
                        }
                        c2–;
                }
        }
}

void change(void)
{
        int k;
        if((i == 0) || (str[i – 1] >= str[i + 1])){
                putchar(‘-‘);
                return;
        }
        if((isdigit(str[i – 1]) && isdigit(str[i + 1])) ||
                (isalpha(str[i – 1]) && isalpha(str[i + 1]))){
                output(str[i – 1] + 1, str[i + 1] – 1);
        }else{
                putchar(‘-‘);
        }
}

int main(void)
{
        int len;
        init();
        scanf("%s", str);
        len = strlen(str);
        //刚刚忘记给len赋值了.
        for(i = 0; i < len; i++){
                if(str[i] == ‘-‘){
                        change();
                }else{
                        putchar(str[i]);
                }
        }
        printf("\n");
        return 0;
}

2010年8月19日

NOIP 2007 统计数字解题报告

　　这一题我的思路(应该)是O(nlogn)的，就是进行一趟快排加上对数组进行一次扫描。
　　快排直接调用库函数，扫描就是用j记录当前自然数，c记录当前自然数出现的次数，如果num[i]和j相同，c++；不同就输出j和c，然后j=num[i], c = 1。在循环结束后还要将最后一个自然数输出。
　　下面贴出代码：
#include <stdio.h>
int num[200000];

int com(const void a, const void b)
{
return (int )a – (int )b;
}

int main(void)
{
        int n;
        int i, j, c;
        scanf("%d", &n);
        for(i = 0; i < n; i++){
                scanf("%d", &num[i]);
        }
        qsort(num, n, sizeof(int), com);
        j = num[0];
        //是num[0] 不是num[j]
        c = 1;
        // c 要从1开始而不是0
        for(i = 1; i < n; i++){
                if(num[i] != j){
                        printf("%d %d\n", j, c);
                        j = num[i];
                        c = 1;
                        // c 要从1开始而不是0
                }else{
                        c++;
                }
        }
        printf("%d %d\n", j, c);
        return 0;
}

2010年8月18日

分类： OI路程