CF1484A题解

Keep_RAD · 2021-04-14 21:28:42 · 题解

这一题其实根本就不要数组模拟，只需推出公式。

首先我们审视一下这一题，为了直接了当的体现，我还是画个图：（初始状态）

未开   未开
未开   未开

我们开一扇：

对右开 未开
未开  未开

此时右上角与左上角联通，再开：

对右开 对下开
未开  未开

此时只剩左下角未对上开，再开：

对右开 对下开
未开  对左开

此时右上角与左上角联通，右上角与右下角联通，再开：

对右开 对下开
对上开 对左开

至此，我们就完成了。

敲黑板：

规律：令行为a,令列为b,则方案数未ab,复杂度O(T)。

代码:

#include<bits/stdc++.h>
using namespace std;
inline int read()//快读板子
{
    register int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9')
    {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=(x<<3)+(x<<1)+(c^48); 
        c=getchar();
    }
    return x*f;
}
int main()
{
    int t;
    t=read();
    while(t--)
    {
        int a=read(),b=read();
        cout<<a*b<<endl;//别忘记换行
    }
    return 0;//完结撒花~~~
}

Goodbye~~