[已解决]关于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

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

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

学习学习

匿名鱼油 *发表于 2021-7-18 19:37:47* · 发表于 2021-7-18 19:37:47

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

好的

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

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

感谢分享！

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

匿名鱼油 *发表于 2021-7-19 14:48:49* · 发表于 2021-7-19 14:48:49

Runtime error
应该不行

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

代码太乱了，加点缩进

匿名鱼油 *发表于 2021-7-19 15:31:35* · 发表于 2021-7-19 15:31:35

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

OK

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

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

复制代码

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

匿名鱼油 *发表于 2021-7-20 08:27:35* · 发表于 2021-7-20 08:27:35

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

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

匿名鱼油 *发表于 2021-7-20 10:39:15* · 发表于 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的无解题

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

回帖奖励 +5 鱼币

回帖奖励 +5 鱼币

回帖奖励 +5 鱼币

回帖奖励 +5 鱼币

回帖奖励 +5 鱼币

回帖奖励 +5 鱼币