题解 P5635 【【CSGRound1】天下第一】

Eleven谦 · 2019-11-15 11:39:57 · 题解

分析题目：

• 题目中说明，有T组数据，但是mod只有一个。很显然，这道题可以用记忆化搜索嘛！（当然，当你打开算法标签时，你也能很快发现）

AC历程：

• 得知算法，加上题意十分好懂，二话不说开始敲板子。第一次测样例，发现error情况会卡死程序。怎么办？我就又开了一个二维数组a保存结果，再测，对了。

• 交上去，爆0！先是RE，再是MLE...难道记忆化不是这么编的？？

• 再读题：1<=X,Y,MOD<=10000。这种范围，开两个二维肯定会爆呀！那减少一个吧。用tot记录循环的次数（代替a数组的作用），如果tot>1000，直接输出error即可。就像这样：

#include <bits/stdc++.h>
using namespace std;
int t,mod,x,y；
long long f[1001][1001];
// 此处f开[1001][1001]，是RE；
// 开[10001][10001],很明显的MLE了
inline int solve(int x,int y,int tot) {
    if(tot>10000) return 3;

    if(f[x][y]!=0) return f[x][y];
    if(x==0) return f[x][y]=1;
    if(y==0) return f[x][y]=2;

    int xx=(x+y)%mod;
    int yy=(xx+y)%mod;
    return f[x][y]=solve(xx,yy,tot+1);

}

int main() {
    scanf("%d%d",&t,&mod);
    while(t--) {
        scanf("%d%d",&x,&y);
        if(solve(x,y,0)==1) puts("1");
        else if(solve(x,y,0)==2) puts("2");
        else puts("error");
    }
    return 0;
}

• 还是不行？上网搜索了一下关于c++ 数据类型的知识，发现了还有一个叫 short 的东西，占用内存比 int 和 longlong 都要小很多，于是，将f数组的类型改为 short，再交，AC...

代码如下：

#include <bits/stdc++.h>
using namespace std;
int t,mod,x,y;
short f[10001][10001];

inline int solve(int x,int y,int tot) {
    if(tot>10000) return 3;

    if(f[x][y]!=0) return f[x][y];
    if(x==0) return f[x][y]=1;
    if(y==0) return f[x][y]=2;

    int xx=(x+y)%mod;
    int yy=(xx+y)%mod;
    return f[x][y]=solve(xx,yy,tot+1);

}

int main() {
    scanf("%d%d",&t,&mod);
    while(t--) {
        scanf("%d%d",&x,&y);
        if(solve(x,y,0)==1) puts("1");
        else if(solve(x,y,0)==2) puts("2");
        else puts("error");
    }
    return 0;
}

再下关于C++里的数据类型的基础知识叭（dalao请忽略qwq)

在32 位的系统上

short 占据的内存大小是2 个byte；
int占据的内存大小是4 个byte；
long占据的内存大小是4 个byte；
float占据的内存大小是4 个byte；
double占据的内存大小是8 个byte；
char占据的内存大小是1 个byte。

int 的范围为-2147483648~ 2147483647；
short的范围为 -32768~ 32767。

PS：当然，这道题的算法标签是骗人的。不用记忆化也能过，代码和记忆化的都差不多，f数组都不用开。

将solve改成如下即可：

inline int solve(int x,int y,int tot) {
    if(tot>10000) return 3;
    if(x==0) return 1;
    if(y==0) return 2;
    else {
        int xx=(x+y)%mod;
        int yy=(xx+y)%mod;
        solve(xx,yy,tot+1);
    }
}

这题很水，对不对QAQ