设为首页收藏本站
切换到窄版

鱼C论坛

 找回密码
 立即注册
鱼C论坛»论坛 › 技术交流 › C\C++交流 › 关于openjudge的无解题
12下一页
返回列表 发新帖
查看: 2875|回复: 31

[已解决]关于openjudge的无解题

[复制链接]
匿名鱼油
匿名鱼油  发表于 2021-7-18 10:14:54 |阅读模式

马上注册，结交更多好友，享用更多功能^_^

您需要 登录 才可以下载或查看，没有账号？立即注册

x
本帖最后由 匿名 于 2021-7-19 15:31 编辑 
#include<bits/stdc++.h>
#define N 4000
char a[10001][N];
char* antemp;
void add(char* a1,char* a2)
{
        int jw = 0;
        for(int j = 1;j < N;a1++,a2++,j++)
        {
                *a1 = *a1+ *a2 + jw;
                jw = *a1 / 10;*a1 %= 10;
        }
}
void sub(char* a1,char* a2)
{
        int jw = 0;
        for(int j = 1;j < N;a1++,a2++,j++)
        {
                *a1 = *a1 - *a2 - jw;
                if(*a1 < 0)
                {
                        *a1 += 10;jw = 1;
                }
                else 
                {
                        jw = 0;
                }
        }
}
void mul(char* a1,int n)
{
        int jw = 0;
        for(int j = 1;j < N;a1++,j++)
        {
                *a1 = (*a1) * n + jw;
                jw = *a1 / 10; *a1 %= 10;
        }
}
void pri(char* s)///OK
{
        char * f=s + N - 1;
        for(; f > s && *f == 0;f--);
        for(; f >= s;f--)
        {
                putchar(*f + 48);
        }
        putchar('\n');
}
int main()
{
        antemp = a[0];
        int n,b;
        scanf("%d",&b);
        memset(a,0,sizeof(a));
        a[1][0] = 1;
        a[2][0] = 3;
        a[3][0] = 3;
        a[4][0] = 8;
        a[5][0] = 2;
        a[6][0] = 7;
        a[5][1] = 1;
        a[6][1] = 2;
        for(n = 7;n <= b;n++)
        {
                memset(antemp,0,N);
                add(a[n],a[n-1]);
                add(antemp,a[n-2]);
                mul(antemp,3);
                add(a[n],antemp);
                sub(a[n],a[n-3]);
                memset(antemp,0,n);
                add(antemp,a[n-5]);
                mul(antemp,2);
                sub(a[n],antemp);
                memset(antemp,0,n);
                add(antemp,a[n-6]);
                mul(antemp,4);
                sub(a[n],antemp);
        }
        pri(a[b]);
        return 0;
}
这是一个有可能过的（至少思路没问题）
https://oj.nbdp.net/status.php?problem_id=3249&jresult=4
这是另一个网站上的同一个题，但对时间比较宽松

我的思路：
如果能做一个把输入的内容提取出来到文件/网页上的话
打表就有可能了

可能吗？
最佳答案
月排行榜 / 总排行榜
人造人
2021-7-19 22:50:32
我也试着写了一个，同样是超时
我特别不喜欢这类题目，为了效率，要把代码写的非常没有可读性
我尝试着修改这个代码来通过测试，但是我放弃了，因为代码越改越差，我开始怀疑了，为了通过这个测试，把代码写成那样值得吗？
我放弃了写那样的代码，那样的代码看着难受



如果能做一个把输入的内容提取出来到文件/网页上的话
输入的内容？
输出的内容？
是把所有的可能输出出来？
我正是这样写代码的
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

// *************************************** matrix *************************************
typedef struct {
    int *data;
    size_t width;
    size_t height;
} matrix_t;

matrix_t *matrix_init(size_t width, size_t height) {
    matrix_t *matrix = malloc(sizeof(*matrix));
    if(!matrix) return NULL;
    matrix->width = width;
    matrix->height = height;
    matrix->data = malloc(sizeof(*matrix->data) * matrix->width * matrix->height);
    if(!matrix->data) {free(matrix); return NULL;}
    memset(matrix->data, 0, sizeof(*matrix->data) * matrix->width * matrix->height);
    return matrix;
}

void matrix_deinit(matrix_t *matrix) {
    if(matrix) free(matrix->data);
    free(matrix);
}

void matrix_print(const matrix_t *matrix) {
    if(!matrix) return;
    for(size_t h = 0; h < matrix->height; ++h) {
        for(size_t w = 0; w < matrix->width; ++w) {
            printf("%d ", matrix->data[h * matrix->width + w]);
        }
        printf("\n");
    }
}

void matrix_set(matrix_t *matrix, size_t x, size_t y, int value) {
    if(!matrix) return;
    if(x >= matrix->width) return;
    if(y >= matrix->height) return;
    matrix->data[y * matrix->width + x] = value;
}

int matrix_get(const matrix_t *matrix, size_t x, size_t y, bool *status) {
    if(!matrix || x >= matrix->width || y >= matrix->height) {
        if(status) *status = 0;
        return -1;
    }
    if(status) *status = 1;
    return matrix->data[y * matrix->width + x];
}

matrix_t *matrix_clone(const matrix_t *matrix) {
    if(!matrix) return NULL;
    matrix_t *dst = matrix_init(matrix->width, matrix->height);
    memcpy(dst->data, matrix->data, sizeof(*matrix->data) * matrix->width * matrix->height);
    return dst;
}

bool matrix_compare(const matrix_t *a, const matrix_t *b) {
    if(a == b) return true;
    if(!a || !b) return false;
    if(a->width != b->width) return false;
    if(a->height != b->height) return false;
    if(memcmp(a->data, b->data, sizeof(*a->data) * a->width * a->height)) return false;
    return true;
}

matrix_t *matrix_reverse(const matrix_t *matrix) {
    matrix_t *r = matrix_init(matrix->width, matrix->height);
    for(size_t h = 0; h < r->height; ++h) {
        for(size_t w = 0; w < r->width; ++w) {
            matrix_set(r, w, h, matrix_get(matrix, r->width - w - 1, h, NULL));
        }
    }
    return r;
}

// **************************************** list **************************************
typedef struct list_node_tag {
    matrix_t *matrix;
    struct list_node_tag *next;
} list_node_t;

typedef struct {
    list_node_t *node;
    size_t size;
} list_t;

list_t *list_init(void) {
    list_t *list = malloc(sizeof(*list));
    if(!list) return NULL;
    list->node = NULL;
    list->size = 0;
    return list;
}

size_t list_size(const list_t *list) {
    if(!list) return 0;
    return list->size;
}

bool list_empty(const list_t *list) {
    if(!list) return true;
    return list_size(list) == 0;
}

bool list_insert(list_t *list, size_t index, const matrix_t *matrix) {
    if(!list) return false;
    if(index > list_size(list)) return false;
    list_node_t *n = malloc(sizeof(*n));
    if(!n) return false;
    n->matrix = (matrix_t *)matrix;
    list_node_t **p = &list->node;
    while(index--) p = &(*p)->next;
    n->next = *p; *p = n;
    ++list->size; return true;
}

bool list_get(const list_t *list, size_t index, matrix_t **matrix) {
    if(!list) return false;
    if(index >= list_size(list)) return false;
    list_node_t *p = list->node;
    while(index--) p = p->next;
    *matrix = p->matrix; return true;
}

bool list_append(list_t *list, const matrix_t *matrix) {
    if(!list) return false;
    return list_insert(list, list_size(list), matrix);
}

bool list_delete(list_t *list, size_t index) {
    if(!list) return false;
    if(index >= list_size(list)) return false;
    list_node_t **p = &list->node;
    while(index--) p = &(*p)->next;
    list_node_t *temp = *p;
    *p = temp->next;
    matrix_deinit(temp->matrix); free(temp);
    --list->size; return true;
}

bool list_clear(list_t *list) {
    if(!list) return false;
    while(!list_empty(list)) list_delete(list, 0);
    return true;
}

void list_deinit(list_t *list) {
    if(!list) return;
    list_clear(list); free(list);
}
// ************************************************************************************

void change_value(matrix_t *matrix, size_t type, size_t x, size_t y, int value) {
    switch(type) {
        case 0: {
            matrix_set(matrix, x, y, value);
            matrix_set(matrix, x + 1, y, value);
        } break;
        case 1: {
            matrix_set(matrix, x, y, value);
            matrix_set(matrix, x, y + 1, value);
        } break;
        case 2: {
            matrix_set(matrix, x, y, value);
            matrix_set(matrix, x + 1, y, value);
            matrix_set(matrix, x, y + 1, value);
            matrix_set(matrix, x + 1, y + 1, value);
        } break;
    }
}

bool find_space(const matrix_t *matrix, size_t type, size_t *x, size_t *y) {
    switch(type) {
        case 0: {
            for(size_t h = 0; h < matrix->height; ++h) {
                for(size_t w = 0; w < matrix->width - 1; ++w) {
                    if(matrix_get(matrix, w, h, NULL) != 0) continue;
                    if(matrix_get(matrix, w + 1, h, NULL) != 0) continue;
                    *x = w; *y = h; return true;
                }
            }
        } break;
        case 1: {
            for(size_t w = 0; w < matrix->width; ++w) {
                if(matrix_get(matrix, w, 0, NULL) != 0) continue;
                if(matrix_get(matrix, w, 1, NULL) != 0) continue;
                *x = w; *y = 0; return true;
            }
        } break;
        case 2: {
            for(size_t w = 0; w < matrix->width - 1; ++w) {
                if(matrix_get(matrix, w, 0, NULL) != 0) continue;
                if(matrix_get(matrix, w, 1, NULL) != 0) continue;
                if(matrix_get(matrix, w + 1, 0, NULL) != 0) continue;
                if(matrix_get(matrix, w + 1, 1, NULL) != 0) continue;
                *x = w; *y = 0; return true;
            }
        } break;
    }
    return false;
}

bool verify(const list_t *list, const matrix_t *matrix) {
    for(size_t i = 0; i < list_size(list); ++i) {
        matrix_t *m; list_get(list, i, &m);
        if(matrix_compare(matrix, m)) return false;
        matrix_t *r = matrix_reverse(matrix);
        if(matrix_compare(r, m)) {
            matrix_deinit(r); return false;
        }
        matrix_deinit(r);
    }
    return true;
}

void paving_bricks(matrix_t *matrix, list_t *list) {
    bool found = false;
    for(size_t i = 0; i < 3; ++i) {
        size_t x, y;
        if(find_space(matrix, i, &x, &y)) {
            found = true;
            change_value(matrix, i, x, y, i + 1);
            paving_bricks(matrix, list);
            change_value(matrix, i, x, y, 0);
        }
    }
    if(!found && verify(list, matrix)) {
        list_append(list, matrix_clone(matrix));
    }
}

int main(void) {
    size_t width;
    scanf("%lu", &width);
    list_t *list = list_init();
    matrix_t *matrix = matrix_init(width, 2);
    paving_bricks(matrix, list);
    for(size_t i = 0; i < list_size(list); ++i) {
        matrix_t *matrix; list_get(list, i, &matrix);
        matrix_print(matrix); printf("\n");
    }
    printf("%lu\n", list_size(list));
    matrix_deinit(matrix);
    list_deinit(list);
    return 0;
}
回复

使用道具 举报

jxd12345
发表于 2021-7-18 10:38:22 | 显示全部楼层

回帖奖励 +5 鱼币

不要发一大堆代码上来，要发请用代码格式
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

超级玛尼哄
发表于 2021-7-18 10:51:15 | 显示全部楼层

回帖奖励 +5 鱼币

学习学习
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

匿名鱼油
匿名鱼油  发表于 2021-7-18 19:37:47
jxd12345 发表于 2021-7-18 10:38
不要发一大堆代码上来，要发请用代码格式

好的
回复 支持 反对

使用道具 举报

noah-py
发表于 2021-7-18 21:01:13 | 显示全部楼层
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复

使用道具 举报

hornwong
发表于 2021-7-19 11:17:09 | 显示全部楼层
感谢分享！
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

LIUBOLIUHAO
发表于 2021-7-19 12:33:05 | 显示全部楼层
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复

使用道具 举报

匿名鱼油
匿名鱼油  发表于 2021-7-19 14:48:49
Runtime error
应该不行
回复 支持 反对

使用道具 举报

名字只有七个字
发表于 2021-7-19 14:50:52 | 显示全部楼层
代码太乱了，加点缩进
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

匿名鱼油
匿名鱼油  发表于 2021-7-19 15:31:35
名字只有七个字 发表于 2021-7-19 14:50
代码太乱了，加点缩进

OK
回复 支持 反对

使用道具 举报

世伊酱
发表于 2021-7-19 17:37:12 | 显示全部楼层
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复

使用道具 举报

AdiosSpike
发表于 2021-7-19 22:05:32 | 显示全部楼层
感谢分享
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

人造人
发表于 2021-7-19 22:50:32 | 显示全部楼层    本楼为最佳答案   

回帖奖励 +5 鱼币

我也试着写了一个，同样是超时
我特别不喜欢这类题目，为了效率，要把代码写的非常没有可读性
我尝试着修改这个代码来通过测试，但是我放弃了，因为代码越改越差，我开始怀疑了，为了通过这个测试，把代码写成那样值得吗？
我放弃了写那样的代码，那样的代码看着难受



如果能做一个把输入的内容提取出来到文件/网页上的话
输入的内容？
输出的内容？
是把所有的可能输出出来？
我正是这样写代码的
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

// *************************************** matrix *************************************
typedef struct {
    int *data;
    size_t width;
    size_t height;
} matrix_t;

matrix_t *matrix_init(size_t width, size_t height) {
    matrix_t *matrix = malloc(sizeof(*matrix));
    if(!matrix) return NULL;
    matrix->width = width;
    matrix->height = height;
    matrix->data = malloc(sizeof(*matrix->data) * matrix->width * matrix->height);
    if(!matrix->data) {free(matrix); return NULL;}
    memset(matrix->data, 0, sizeof(*matrix->data) * matrix->width * matrix->height);
    return matrix;
}

void matrix_deinit(matrix_t *matrix) {
    if(matrix) free(matrix->data);
    free(matrix);
}

void matrix_print(const matrix_t *matrix) {
    if(!matrix) return;
    for(size_t h = 0; h < matrix->height; ++h) {
        for(size_t w = 0; w < matrix->width; ++w) {
            printf("%d ", matrix->data[h * matrix->width + w]);
        }
        printf("\n");
    }
}

void matrix_set(matrix_t *matrix, size_t x, size_t y, int value) {
    if(!matrix) return;
    if(x >= matrix->width) return;
    if(y >= matrix->height) return;
    matrix->data[y * matrix->width + x] = value;
}

int matrix_get(const matrix_t *matrix, size_t x, size_t y, bool *status) {
    if(!matrix || x >= matrix->width || y >= matrix->height) {
        if(status) *status = 0;
        return -1;
    }
    if(status) *status = 1;
    return matrix->data[y * matrix->width + x];
}

matrix_t *matrix_clone(const matrix_t *matrix) {
    if(!matrix) return NULL;
    matrix_t *dst = matrix_init(matrix->width, matrix->height);
    memcpy(dst->data, matrix->data, sizeof(*matrix->data) * matrix->width * matrix->height);
    return dst;
}

bool matrix_compare(const matrix_t *a, const matrix_t *b) {
    if(a == b) return true;
    if(!a || !b) return false;
    if(a->width != b->width) return false;
    if(a->height != b->height) return false;
    if(memcmp(a->data, b->data, sizeof(*a->data) * a->width * a->height)) return false;
    return true;
}

matrix_t *matrix_reverse(const matrix_t *matrix) {
    matrix_t *r = matrix_init(matrix->width, matrix->height);
    for(size_t h = 0; h < r->height; ++h) {
        for(size_t w = 0; w < r->width; ++w) {
            matrix_set(r, w, h, matrix_get(matrix, r->width - w - 1, h, NULL));
        }
    }
    return r;
}

// **************************************** list **************************************
typedef struct list_node_tag {
    matrix_t *matrix;
    struct list_node_tag *next;
} list_node_t;

typedef struct {
    list_node_t *node;
    size_t size;
} list_t;

list_t *list_init(void) {
    list_t *list = malloc(sizeof(*list));
    if(!list) return NULL;
    list->node = NULL;
    list->size = 0;
    return list;
}

size_t list_size(const list_t *list) {
    if(!list) return 0;
    return list->size;
}

bool list_empty(const list_t *list) {
    if(!list) return true;
    return list_size(list) == 0;
}

bool list_insert(list_t *list, size_t index, const matrix_t *matrix) {
    if(!list) return false;
    if(index > list_size(list)) return false;
    list_node_t *n = malloc(sizeof(*n));
    if(!n) return false;
    n->matrix = (matrix_t *)matrix;
    list_node_t **p = &list->node;
    while(index--) p = &(*p)->next;
    n->next = *p; *p = n;
    ++list->size; return true;
}

bool list_get(const list_t *list, size_t index, matrix_t **matrix) {
    if(!list) return false;
    if(index >= list_size(list)) return false;
    list_node_t *p = list->node;
    while(index--) p = p->next;
    *matrix = p->matrix; return true;
}

bool list_append(list_t *list, const matrix_t *matrix) {
    if(!list) return false;
    return list_insert(list, list_size(list), matrix);
}

bool list_delete(list_t *list, size_t index) {
    if(!list) return false;
    if(index >= list_size(list)) return false;
    list_node_t **p = &list->node;
    while(index--) p = &(*p)->next;
    list_node_t *temp = *p;
    *p = temp->next;
    matrix_deinit(temp->matrix); free(temp);
    --list->size; return true;
}

bool list_clear(list_t *list) {
    if(!list) return false;
    while(!list_empty(list)) list_delete(list, 0);
    return true;
}

void list_deinit(list_t *list) {
    if(!list) return;
    list_clear(list); free(list);
}
// ************************************************************************************

void change_value(matrix_t *matrix, size_t type, size_t x, size_t y, int value) {
    switch(type) {
        case 0: {
            matrix_set(matrix, x, y, value);
            matrix_set(matrix, x + 1, y, value);
        } break;
        case 1: {
            matrix_set(matrix, x, y, value);
            matrix_set(matrix, x, y + 1, value);
        } break;
        case 2: {
            matrix_set(matrix, x, y, value);
            matrix_set(matrix, x + 1, y, value);
            matrix_set(matrix, x, y + 1, value);
            matrix_set(matrix, x + 1, y + 1, value);
        } break;
    }
}

bool find_space(const matrix_t *matrix, size_t type, size_t *x, size_t *y) {
    switch(type) {
        case 0: {
            for(size_t h = 0; h < matrix->height; ++h) {
                for(size_t w = 0; w < matrix->width - 1; ++w) {
                    if(matrix_get(matrix, w, h, NULL) != 0) continue;
                    if(matrix_get(matrix, w + 1, h, NULL) != 0) continue;
                    *x = w; *y = h; return true;
                }
            }
        } break;
        case 1: {
            for(size_t w = 0; w < matrix->width; ++w) {
                if(matrix_get(matrix, w, 0, NULL) != 0) continue;
                if(matrix_get(matrix, w, 1, NULL) != 0) continue;
                *x = w; *y = 0; return true;
            }
        } break;
        case 2: {
            for(size_t w = 0; w < matrix->width - 1; ++w) {
                if(matrix_get(matrix, w, 0, NULL) != 0) continue;
                if(matrix_get(matrix, w, 1, NULL) != 0) continue;
                if(matrix_get(matrix, w + 1, 0, NULL) != 0) continue;
                if(matrix_get(matrix, w + 1, 1, NULL) != 0) continue;
                *x = w; *y = 0; return true;
            }
        } break;
    }
    return false;
}

bool verify(const list_t *list, const matrix_t *matrix) {
    for(size_t i = 0; i < list_size(list); ++i) {
        matrix_t *m; list_get(list, i, &m);
        if(matrix_compare(matrix, m)) return false;
        matrix_t *r = matrix_reverse(matrix);
        if(matrix_compare(r, m)) {
            matrix_deinit(r); return false;
        }
        matrix_deinit(r);
    }
    return true;
}

void paving_bricks(matrix_t *matrix, list_t *list) {
    bool found = false;
    for(size_t i = 0; i < 3; ++i) {
        size_t x, y;
        if(find_space(matrix, i, &x, &y)) {
            found = true;
            change_value(matrix, i, x, y, i + 1);
            paving_bricks(matrix, list);
            change_value(matrix, i, x, y, 0);
        }
    }
    if(!found && verify(list, matrix)) {
        list_append(list, matrix_clone(matrix));
    }
}

int main(void) {
    size_t width;
    scanf("%lu", &width);
    list_t *list = list_init();
    matrix_t *matrix = matrix_init(width, 2);
    paving_bricks(matrix, list);
    for(size_t i = 0; i < list_size(list); ++i) {
        matrix_t *matrix; list_get(list, i, &matrix);
        matrix_print(matrix); printf("\n");
    }
    printf("%lu\n", list_size(list));
    matrix_deinit(matrix);
    list_deinit(list);
    return 0;
}
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

人造人
发表于 2021-7-19 23:01:55 | 显示全部楼层
1.png
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

匿名鱼油
匿名鱼油  发表于 2021-7-20 08:27:35
人造人 发表于 2021-7-19 22:50
我也试着写了一个，同样是超时
我特别不喜欢这类题目，为了效率，要把代码写的非常没有可读性
我尝试着修 ...


感谢。
把精力耗费在这个问题上很不值得。
因为它可能是无解题。
所以我想尝试获取这个评测机的输入，然后写一些if语句，就有可能通过了。
非常感谢。
回复 支持 反对

使用道具 举报

匿名鱼油
匿名鱼油  发表于 2021-7-20 10:39:15
没法了，打表吧
回复 支持 反对

使用道具 举报

hornwong
发表于 2021-7-20 10:59:19 | 显示全部楼层

回帖奖励 +5 鱼币

感谢分享！
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

小超超超
发表于 2021-7-21 02:30:02 | 显示全部楼层
代码格式
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

burntlime
发表于 2021-7-22 13:59:30 | 显示全部楼层

回帖奖励 +5 鱼币

？
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复

使用道具 举报

临时号
发表于 2021-7-24 00:55:50 | 显示全部楼层

回帖奖励 +5 鱼币

感谢分享
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

下一页 »
12下一页
返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-11-15 14:24

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表