题解：P9788 [ROIR 2020 Day2] 区域规划

zeroflows · 2024-08-21 16:02:04 · 题解

题目传送门

思路

首先我们看下数据范围，n \le 3000，范围很小，所以暴力枚举。\ 于是第一份代码出来了。

#include<bits/stdc++.h>
using namespace std;
int s,a,b,c,d,n,m;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(),cout.tie();
    cin>>n>>m;
    for(a=1;a<=n;a++)
    {
        for(b=1;b<=n;b++)
        {
            for(c=1;c<a;c++)
            {
                for(d=1;d<b;d++)
                {
                    if(a==m||b==m)
                        continue;
                    if(a*b-c*d==n)
                        s++;
                }
            }
        }
    }
    cout<<s;
}

但只有 37 分。

然后考虑优化。\ 题目最主要的条件是 a \times b - c \times d = n 变下形可得 n + c \times d = a \times b，再考虑下范围。\ 于是第二份代码出来了。

#include<bits/stdc++.h>
using namespace std;
int s,a,b,c,d,n,m;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(),cout.tie();
    cin>>n>>m;
    for(c=n-2;c>=1;c--)
    {
        for(d=n-c;d>=1;d--)
        {
            for(a=n-1;a>c;a--)
            {
                if((n+d*c)%a||(n+d*c)/a<=d)
                    continue;
                b=(n+d*c)/a;
                if(a!=m&&b!=m&&a*b-c*d==n)
                    s++;
            }
        }
    }
    cout<<s;
}

但这样写也只有 51 分。

那我们换一种思路。\ 因为 a 与 b 不能等于 m 所以我们放在前面，减少循环次数。\ 我们考虑一下 a \times b 的大小。

• 首先 a \times b - c \times d = n，所以 a \times b 小于 n 的话直接往下走。\ 另外考虑一下 a 与 b 的大小关系。\ 我们枚举一下，可以发现 a 与 b 的值总是在 1 \sim n 之间。而且当 a \ne b 时，a b c d 与 b a c d 两个顺序都成立，同时 c 的最小值为 \max ( 1 , ( a \times b - n ) \div b)，于是我们可以这样。

for(a=1;a<=n;a++)
    {
        if(a==m)
            continue;
        for(b=a;b<=n;b++)
        {
            if(b==m||a*b<=n)
                continue;
            for(c=max(1,(a*b-n)/b);c<a;c++)
            {
            }
        }
    }

最后结合题目要求判断就行了。

代码

#include<bits/stdc++.h>
using namespace std;
int s,a,b,c,d,n,m;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(),cout.tie();
    cin>>n>>m;
    for(a=1;a<=n;a++)
    {
        if(a==m)
            continue;
        for(b=a;b<=n;b++)
        {
            if(b==m||a*b<=n)
                continue;
            for(c=max(1,(a*b-n)/b);c<a;c++)
            {
                d=a*b-n;
                if(d%c!=0||d/c>=b)
                    continue;
                s++;
                if(a!=b)
                    s++;
            }
        }
    }
    cout<<s;
}