跳至正文

NOIP 2008 提高组 双栈排序 解体报告

  • OI路程

  这个题目我的思路很简单,就是读入一个数据,判断是否小于s1的顶元素,如果是则讲数据压入s1,否则该数据是否小于s2的顶元素,如果是则将它压入栈s2。然后再判断s1的顶是否等于当前需要输出的值(就是安顺序来是不是对的),如果是就输出b。再同样判断s2,如果是就输出d。
  很可惜,只有30分,代码如下:
#include <stdio.h>
int num[1000];
int s1[1000], s2[1000];
int t1, t2;
char ans[2000];
int len;

void add(char ch)
{
        ans[len++] = ch;
}

int main(void)
{
        int n;
        int i, j, r, t;
        scanf("%d", &n);
        for(i = 0; i < n; i++){
                scanf("%d", &num[i]);
        }
        s1[0] = s2[0] = 10000;
        for(i = 1, j = 0; i <= n;){
                r = j;
                if(s1[t1] > num[j] && j < n){
                        s1[++t1] = num[j++];
                        add(‘a’);
                }else if(s2[t2] > num[j] && j < n){
                        s2[++t2] = num[j++];
                        add(‘c’);
                }
                t = i;
                if(s1[t1] == i){
                        t1–;
                        add(‘b’);
                        i++;
                }
                if(s2[t2] == i){
                        t2–;
                        i++;
                        add(‘d’);
                }
                if(t == i && r == j){
                        printf("0\n");
                        return 0;
                }
        }
        for(i = 0; i < 2  n; i++){
                if(i != 0){
                        printf(" ");
                }
                printf("%c", ans[i]);
        }
        printf("\n");
        return 0;
}
  继续学习中。。
  额, 照着网上一个人抄的(当然是在理解的前提下, 再自己徒手打出来的.), 竟然没有AC, 然后试了试他自己的代码, 也没AC
  思路是这样的, 对于这样的数据i < j < k 且 num[k] < num[i] < num[j] 的情况下,i和j一定不能在同一个栈中,不然就是无解的情况,你想想啊,如果小的先入栈,大的又入栈,这能有解码?所以这里使用了二分图染色的算法,具体的解释看这位大牛和另一位的Blog: 
  http://www.byvoid.com/blog/noip2008-twostack/

  http://zhc105.info/blog/2010/06/双栈排序.html
  下面那个是90分的代码,上面那个是100分的代码。
  先贴代码吧:
#include <stdio.h>
#define minnum(a, b) ((a)<(b)?(a):(b))
int num[1000];
int min[1000];
int map[1000][1000];
int count[1000];
int color[1000];

void add(int i, int j)
{
        map[i][count[i]++] = j;
}

int fill(int i, int c)
{
        int j, t;
        color[i] = c;
        for(j = 0; j < count[i]; j++){
                t = map[i][j];
                if(color[t] == –1 && !fill(t, c ^ 1)){
                        return 0;
                }else if(color[t] == c){
                        return 0;
                }
        }
        return 1;
}

int s1[1000], s2[1000];
int t1, t2;

int main(void)
{
        int n;
        int i, j;
        char 
tmp;
        memset(min, 0x7Fsizeof(min));
        memset(color, 0xFFsizeof(color));
        scanf("%d", &n);
        for(i = 0; i < n; i++){
                scanf("%d", &num[i]);
        }
        for(i = n – 1; i >= 0; i–){
                min[i] = minnum(min[i + 1], num[i]);
        }
        for(i = 0; i < n; i++){
                for(j = i + 1; j < n; j++){
                        if(num[i] < num[j] && num[i] > min[j]){
                                add(i, j);
                                add(j, i);
                        }
                }
        }
        for(i = 0; i < n; i++){
                if(color[i] == –1){
                        if(!fill(i, 0)){
                                printf("0\n");
                                return 0;
                        }
                }
        }
        j = 0;
        tmp = "";
        for(i = 1; i <= n; ){
                if(s1[t1] == i){
                        printf("%sb", tmp);
                        t1–, i++;
                        continue;
                }
                if(s2[t2] == i && (j >= n || color[j])){
                        printf("%sd", tmp);
                        t2–, i++;
                        continue;
                }
                if(!color[j]){
                        printf("%sa", tmp);
                        tmp = " ";
                        s1[++t1] = num[j++];
                }else{
                        printf("%sc", tmp);
                        tmp = " ";
                        s2[++t2] = num[j++];
                }
        }
        printf("\n");
//      getch();
        return 0;
}

  但是将上述代码稍加修改后,就能够AC了:
#include <stdio.h>
#define minnum(a, b) ((a)<(b)?(a):(b))
int num[1000];
int min[1001];
int map[1000][1000];
int count[1000];
int color[1000];

void add(int i, int j)
{
        map[i][count[i]++] = j;
}

int fill(int i, int c)
{
        int j, t;
        color[i] = c;
        for(j = 0; j < count[i]; j++){
                t = map[i][j];
                if(color[t] == –1 && !fill(t, c ^ 1)){
                        return 0;
                }else if(color[t] == c){
                        return 0;
                }
        }
        return 1;
}

int s1[1000], s2[1000];
int t1, t2;

int main(void)
{
        int n;
        int i, j;
        char *tmp;
        scanf("%d", &n);
        for(i = 0; i < n; i++){
                scanf("%d", &num[i]);
        }
        min[n] = 10001;
        for(i = n – 1; i >= 0; i–){
                min[i] = minnum(min[i + 1], num[i]);
        }
        for(i = 0; i < n; i++){
                for(j = i + 1; j < n; j++){
                        if(num[i] < num[j] && num[i] > min[j]){
                                add(i, j);
                                add(j, i);
                        }
                }
        }

        for(i = 0; i < n; i++){
                color[i] = –1;
        }

        for(i = 0; i < n; i++){
                if(color[i] == –1){
                        if(!fill(i, 0)){
                                printf("0\n");
                                return 0;
                        }
                }
        }
        j = 0;
        tmp = "";
        for(i = 1; i <= n; ){
                if(s1[t1] == i){
                        printf("%sb", tmp);
                        t1–, i++;
                        continue;
                }
                if(s2[t2] == i && (j >= n || color[j])){
                        printf("%sd", tmp);
                        t2–, i++;
                        continue;
                }
                if(!color[j]){
                        printf("%sa", tmp);
                        tmp = " ";
                        s1[++t1] = num[j++];
                }else{
                        printf("%sc", tmp);
                        tmp = " ";
                        s2[++t2] = num[j++];
                }
        }
        printf("\n");
//      getch();
        return 0;
}

发表回复

您的电子邮箱地址不会被公开。