AOJ 834.买买买|OhYee 博客

这是一篇最后编辑于 8 年前的文章，其内容可能与目前实际情况差异较大，请注意甄别

题目

{% raw %}

{% endraw %} 一天Alice打开了她日常玩的游戏，发现她里面还有n个游戏币，她想把这些游戏币花光。现在可以买的一共三种道具，分别是房子（每一个价值1234567个游戏币），车子（每一个价值123456个游戏币），电脑（每一个价值1234个游戏币）。现在她想知道，通过买这三种道具是否可以把n个游戏币全部花光。

{% raw %}

{% endraw %}

第一行，一个数字t(1<=t<=100)。代表测试数据数量。
对于每一组测试数据，一个整数n（1<=n<=1000000000)，代表现在的游戏币。

{% raw %}

{% endraw %}

输出n行，每行输出"YES"或者"NO"，表示她可以或者不可以把游戏币全部花光。

{% raw %}

{% endraw %}

2
1359257
17851817

{% raw %}

{% endraw %}

YES
NO

{% raw %}

{% endraw %}

题解

由于最大的值非常大,如果直接 dfs 会非常慢
而且打表的文件会非常大

而看 1234567 和 1000000000 其实差别不是很大
除一下发现最多也就能买 800 多套房子
而即使全部买成汽车也就能买 8000 多辆
乘起来的数据量只有 10e6 完全是可以遍历的
也就是说,只需要枚举房子和车的数量,然后判断剩下的钱能不能整除电脑

这样做不超时的原因是房子和车的价格都非常大,可以将许多数据“跨越”掉
如果这数都很小的话,就没有办法了

代码

```cpp 买买买 https://github.com/OhYee/sourcecode/tree/master/ACM 代码备份 //*/ #define debug #include

//*/ #include #include #include #include #include using namespace std;

typedef long long LL;

int price[] = {1234567,123456,1234};

int main(){
#ifdef debug
freopen("in.txt", "r", stdin);
int START = clock();
#endif
cin.tie(0);
cin.sync_with_stdio(false);

int T;
cin >> T;
while(T--){
    LL n;
    cin >> n;
    bool flag = false;

    int max_fz = n / price[0];
    for(int i=0;i<=max_fz;i++){
        int max_cz = (n-i*price[0]) / price[1];
        for(int j=0;j<=max_cz;j++)
            if(!((n-i*price[0]-j*price[1]) % price[2])){
                flag = true;
                break;
            }
    }
    cout << (flag?"YES":"NO") << endl;
}

#ifdef debug
printf("Time:%.3fs.\n", double(clock() - START) / CLOCKS_PER_SEC);
#endif
return 0;

}

</div>

推荐订阅源

OhYee 博客

题目

题解

代码