论坛 › C\C++交流 › 关于openjudge的无解题

Anonymous 发表于 2021-7-18 10:14:54

关于openjudge的无解题

本帖最后由 匿名 于 2021-7-19 15:31 编辑

#include<bits/stdc++.h>
#define N 4000
char a;
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;
        int n,b;
        scanf("%d",&b);
        memset(a,0,sizeof(a));
        a = 1;
        a = 3;
        a = 3;
        a = 8;
        a = 2;
        a = 7;
        a = 1;
        a = 2;
        for(n = 7;n <= b;n++)
        {
                memset(antemp,0,N);
                add(a,a);
                add(antemp,a);
                mul(antemp,3);
                add(a,antemp);
                sub(a,a);
                memset(antemp,0,n);
                add(antemp,a);
                mul(antemp,2);
                sub(a,antemp);
                memset(antemp,0,n);
                add(antemp,a);
                mul(antemp,4);
                sub(a,antemp);
        }
        pri(a);
        return 0;
}
这是一个有可能过的（至少思路没问题）
https://oj.nbdp.net/status.php?problem_id=3249&jresult=4
这是另一个网站上的同一个题，但对时间比较宽松

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

可能吗？

jxd12345 发表于 2021-7-18 10:38:22

不要发一大堆代码上来，要发请用代码格式

超级玛尼哄 发表于 2021-7-18 10:51:15

学习学习

Anonymous 发表于 2021-7-18 19:37:47

jxd12345 发表于 2021-7-18 10:38
不要发一大堆代码上来，要发请用代码格式

好的

noah-py 发表于 2021-7-18 21:01:13

{:10_263:}

hornwong 发表于 2021-7-19 11:17:09

感谢分享！

LIUBOLIUHAO 发表于 2021-7-19 12:33:05

{:10_257:}

Anonymous 发表于 2021-7-19 14:48:49

Runtime error
应该不行

名字只有七个字 发表于 2021-7-19 14:50:52

代码太乱了，加点缩进

Anonymous 发表于 2021-7-19 15:31:35

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

OK

世伊酱 发表于 2021-7-19 17:37:12

{:5_109:}

AdiosSpike 发表于 2021-7-19 22:05:32

感谢分享

人造人 发表于 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);
      }
      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 = 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;
}

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;
}

人造人 发表于 2021-7-19 23:01:55

Anonymous 发表于 2021-7-20 08:27:35

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

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

Anonymous 发表于 2021-7-20 10:39:15

没法了，打表吧

hornwong 发表于 2021-7-20 10:59:19

感谢分享！

小超超超 发表于 2021-7-21 02:30:02

代码格式

burntlime 发表于 2021-7-22 13:59:30

？

临时号 发表于 2021-7-24 00:55:50

感谢分享

查看完整版本: 关于openjudge的无解题