UESTC 1262 Memory 暴力法

Memory 暴力法

Source

第七届ACM趣味程序设计竞赛第三场（正式赛）E

My Solution

思路是已经有i-1个满足条件的数，再加第i个数进去依然满足，任意两个数的和不会和另外的两数和相等。

前面比赛的时候一直以为是斐波那契数列，结束了学长宣布不是Fib，确实当时笔者自己也感觉到数据很大的时候i-1个数和第i个数会相差很多，

可以相差好多亿（n<=52)，所以很可能存在j比Fib第i个数小，但也满足条件。

当时还一直以为是自己漏解，确实应当好好反思一下啊。

那么用暴力法还是比较好的选择了，呵呵，暴力法本来就挺好的。

sum[ i ][ j ]表示第i个数和第j个数的和。反正n<=52,这么整不要紧

先对ans[ i ]的i每一个i进行处理，从j开始递增并在子块 x=i 更新好sum[ x ][前面的数],且在每个里面放forfor对整个矩阵进行扫描，当然，要到x-1行的

时候停下，自己那行可不能扫啊。如果中间出现和相等了直接return，这也是函数相对直接嵌套在里面的好处了，一个return直接跳好几层for。

此外，对于sum[ i ][ j ]可能大部分sum[ i ]的后面部分都没有处理到，却常常会被扫到，但为了使算法写起来理解起来简洁一点，这里不用管它，

记得memset就好了，反正全是0，扫扫更健康。我们要找的是有没有相同和，后面的数的和怎么会和0相等呢☺，(毕竟n<=52,交一发，超时了再改，

虽然不快一般超时不了)，所以不用管它。

#include 
#include 
#include 
using namespace std;
int sum[56][56],ans[56],n;

inline bool judge(int x,int y)              //这个内联了也基本没有效果，谁叫它太大了啊。
{
    for(int i=1;i<x;i++){
        sum[x][i]=y+ans[i];
        for(int k=1;k<x;k++){              //k当然小于x，不然嘿嘿
            for(int l=1;l<x;l++){          //这里本来是n，也对，写博客的时候临时改为x了，这样相对n快了一点吧，用不到地方少扫几次了
                if(sum[x][i]==sum[k][l]) return false;
                //cout<<sum[k][l]<<" ";
            }
            //printf("n");
        }
    }
    return true;
}

int main()
{
    scanf("%d",&n);
    memset(sum,0,sizeof(sum));
    if(n==2) printf("1 1");
    else if(n==3) printf("1 2 3");
    else{
        ans[1]=1;ans[2]=2;ans[3]=3;
        sum[1][2]=3;sum[1][3]=4;sum[2][3]=5;

        printf("1 2 3");
        for(int i=4;i<=n;i++){
            for(int j=ans[i-1]+1;;j++){
                if(judge(i,j)){
                    ans[i]=j;
                    printf(" %d",j);
                    break;
                }
            }
        }
    }
    return 0;
}

非特殊说明，本站所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

------from ProLightsfx

UESTC 1262 Memory 暴力法

Memory 暴力法

Source

My Solution

相关推荐

UESTC 766 乐乐和球球博弈暴力(也可以不用暴力法)

Codeforces Round #444 (Div. 2) C. Solution for Cube 枚举、模拟、魔方