ABC-269解题报告

发表于 更新于 分类于

比赛传送门

D. Do use hexagon grid

题目传送门

n2n^2 枚举两个格点，判断是否能直接走，能则连边，最后用 dfs 计算连通块个数。

E. Last Rook

题目传送门

由于不需要考虑斜向的冲突，所以考虑行和列分开二分。以行为例：

如果有若干连续行的棋子数量小于行数，则答案一定在这些行中，以此作为二分的 check。

F. Numbered Checker

题目传送门

显然每一行剩下的数都是一个等差数列。

考虑奇偶行分开计算：对于奇数行，只有奇数列能产生贡献；对于偶数行，只有偶数列能产生贡献。以奇数行为例：

具体地，若输入的四界分别为 u,d,l,ru,d,l,r，则只考虑奇数行时，我们将四界缩紧为 u′,d′,l′,r′u',d',l',r'（为方便接下来处理），此时能产生贡献的列数为 lenrow=(r′−l′)/2+1len_{row}=(r'-l')/2+1，行数为 lencolumn=(d′−u′)/2+1len_{column}=(d'-u')/2+1。

显然贡献的左上角的值为 s1=(u′−1)×m+l′s_1=(u'-1)\times m+l'，右上角为 s2=(u′−1)×m+r′s_2=(u'-1)\times m+r'，则第一行的和 sumu′=(s1+s2)×lenrowsum_{u'}=(s_1+s_2)\times len_{row}。

第二个产生贡献的行（即 u′+2u'+2 行）的和为 sumu′+2=sumu′+lenrow×2msum_{u'+2}=sum_{u'}+len_{row}\times 2m，第三行为 sumu′+4=sumu′+lenrow×4msum_{u'+4}=sum_{u'}+len_{row}\times 4m 以此类推。可以发现每一行都含有一个 sumu′sum_{u'} 的项，单独提出来，得到 sumu′×lencolumnsum_{u'}\times len_{column}，而每一行新加的贡献为 lenrow×0m+lenrow×2m+lenrow×4m⋯len_{row}\times 0m+len_{row}\times 2m+len_{row}\times 4m\cdots，这也可以很容易得用等差数列求得。

偶数行偶数列的情况同理，由于操作完全相同，可以封装成函数调用两遍。

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=998244353;
int add(int a,int b) {return (a+b)%mod;}
int mul(int a,int b) {return a*b%mod;}
signed main() {
    int inv2=(mod+1)/2;
    int n,m,q;
    cin>>n>>m>>q;
    while(q--) {
        int l,r,u,d,ans=0;
        cin>>u>>d>>l>>r;
        auto solve=[&](bool flag) {
            int u1=u,d1=d,l1=l,r1=r;
            if(u1%2==flag) u1++;
            if(d1%2==flag) d1--;
            if(l1%2==flag) l1++;
            if(r1%2==flag) r1--;
            int lenrow=(r1-l1)/2+1,lencol=(d1-u1)/2+1;
            int res=mul(mul(add(add(mul(u1-1,m),l1),add(mul(u1-1,m),r1)),lenrow),inv2);
            (ans+=mul(res,lencol))%=mod;
            (ans+=mul(mul(mul(mul(2*(lencol-1),m),lencol),inv2),lenrow))%=mod;
        };
        solve(0),solve(1);
        cout<<ans<<endl;
    }
    return 0;
}