ABC334 参赛记录

· · 个人记录

md，G 题会做但是没调出来。

B

我认为解释不如直接看代码 

 cin>>a>>m>>l>>r;
 if(a<l)
 {
    printf("%lld\n",calc(r)-calc(l-1));
 }
 else if(a>=l&&a<=r)
 {
     printf("%lld\n",(a-l)/m+1+(r-a)/m);
 }
 else
 {
     printf("%lld\n",calc2(l)-calc2(r+1));
 }

C

以下结论我认为很显然，不做解释。

如果 n 是偶数，那么排序，然后贪心地 (1,2) 一对，(3,4) 一对 \cdots \cdots

如果 n 是奇数，那么枚举要删的点，经过预处理可以 O(1) 计算得出删除每个点之后的答案。

D

纯纯前缀和二分板子。

E

先预处理连通块，然后枚举每个点，看把他涂成绿色的连通块个数，思想简单就是写起来麻烦。

F

暂时不会。

G

稍微修改一下求割点的算法，使其标记上它所连接的连通块数量，这个稍微思考一下就能想出来。 

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5;
const int maxm = 8e6 + 5;
int n, m;
int id(int i, int j)
{
    return (i - 1) * m + j;
}
int head[maxn];
struct EDGE
{
    int to, nxt;
} edge[maxm << 1];
int cnt = 1;
typedef long long ll;
const ll mod = 998244353;
ll qpow(ll a, ll b)
{
    ll ret = 1;
    while (b)
    {
        if (b & 1)
            ret = ret * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ret;
}
ll inv(ll a)
{
    return qpow(a, mod - 2);
}
void add(int u, int to)
{
    edge[++cnt].to = to;
    edge[cnt].nxt = head[u];
    head[u] = cnt;
}
int dfn[maxn];
int low[maxn];
int cut[maxn];
int ids; // 时间戳
void print(int x)
{
    int lie=x%m;
    if(lie==0)lie=m;
    printf("%d %d\n",(x-1)/m+1,lie);
}
void tarjan(int u, int fa)
{
    dfn[u] = low[u] = ++ids;
    register int child = 0; // 子树
    for (int i = head[u]; i; i = edge[i].nxt)
    {
        register int to = edge[i].to;
        if (!dfn[to])
        { // 尚未访问过
            tarjan(to, fa);
            low[u] = min(low[u], low[to]);
            if (low[to] >= dfn[u] && u != fa) // 需要经过u访问更早的祖先
            {
                cut[u]++;
            }
            if (u == fa) // 如果是根节点
            {
                child++; // 子树++
            }
        }
        low[u] = min(low[u], dfn[to]); // 没有父子关系的话，那么按普通边计算，更新u
    }
    if (child >= 2 && u == fa) // 这样根节点也是割点，因为删除它就会有两棵蒲通的树不连通
    {
        cut[u] = child-1;
    }
   // printf("u = ",u);
   // print(u);
   // printf("cut = %d\n",cut[u]);
}
char s[1005][1005];
bool chk(int i, int j)
{
    if (s[i][j] != '#')
        return 0;
    if (i < 1 || i > n)
        return 0;
    if (j < 1 || j > m)
        return 0;
    return 1;
}
bool td[1000005];
void dfs(int u)
{
    td[u] = 1;
    for (int i = head[u]; i; i = edge[i].nxt)
    {
        int to = edge[i].to;
        if (!td[to])
            dfs(to);
    }
}
int ltkcnt;
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        scanf("%s", s[i] + 1);
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (chk(i, j))
            {
                if (chk(i - 1, j))
                {
                    add(id(i - 1, j), id(i, j));
                    add(id(i, j), id(i - 1, j));
                }
                if (chk(i + 1, j))
                {
                    add(id(i + 1, j), id(i, j));
                    add(id(i, j), id(i + 1, j));
                }
                if (chk(i, j - 1))
                {
                    add(id(i, j - 1), id(i, j));
                    add(id(i, j), id(i, j - 1));
                }
                if (chk(i, j + 1))
                {
                    add(id(i, j + 1), id(i, j));
                    add(id(i, j), id(i, j + 1));
                }
            }
        }
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (s[i][j] == '#' && !dfn[id(i, j)])
            {
                tarjan(id(i, j), id(i, j));
            }
            if (s[i][j] == '#' && !td[id(i, j)])
            {
                dfs(id(i, j));
                ltkcnt++;
            }
        }
    }
  //  printf("ltkcnt = %d\n", ltkcnt);
    ll ans = 0;
    ll ansct = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (s[i][j] != '.')
            {
                ansct++;
                bool ok=0;
                ok|=(s[i-1][j]=='#');
                ok|=(s[i][j-1]=='#');
                ok|=(s[i+1][j]=='#');
                ok|=(s[i][j+1]=='#');
                if(!ok)ans+=ltkcnt-1;
                else ans += (ltkcnt + max(0, cut[id(i, j)]));
            //    printf("%d %d %d\n", i, j, (ltkcnt + cut[id(i, j)]));
                ans %= mod;
            }
        }
    }
    ans *= inv(ansct);
    printf("%lld", ans % mod);
    return 0;
}