【高难思维题】Water Problem详解

2024-01-08 06:37:48

「RiOI-03」water problem - 洛谷

PS :看着要考虑的情况很多,实际代码15行......

题目大意

给定一个正整数?n,问一个正方形能否被分割为?n?个小正方形(不要求大小相等),输出?Yes?或?No。多组数据。

思路

题目很好理解吧?我们可以画个图:

上图就是n=4,n=9的情况了。

那看到这里,有人就要问了:那是不是只有完全平方数满足条件啊?

不是。看这里:

傻眼了吧?题目不要求正方形大小相等!

别急,我们一个个画:

这里分别是n=1,4,6,7,8时的图像。

再画下去,我们会惊奇地发现:

若n是3,5外的奇数,则它一定可以用上图两个图叠加的方式排出来;

若n是大于2的偶数,则它一定可以用类似n=6或n=8的方式排列出来。

所以......除了n=2,3,5,其它都有解!!!

(喝着我就是被出题人耍了一通呗)

?(洛谷原题题解截图)

焯!

代码

#include<iostream>
using namespace std;

int t, n;

int main()
{
    cin >> t;
    while(t--){
        cin >> n;
        if(n == 2 || n == 3 || n == 5) cout << "No\n";
        else cout << "Yes\n";
    }
    return 0;
}

总结?

不说了,先去问候作者十八代祖宗了(doge

思维难度超级高!!!

文章来源:https://blog.csdn.net/weixin_52398991/article/details/135437076
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。