首页 > 其他分享 >Solution - Atcoder ARC157D YY Garden

Solution - Atcoder ARC157D YY Garden

时间:2024-10-02 16:33:46浏览次数:6  
标签:Atcoder 横轴 sum texttt YY int 划分 maxn ARC157D

考虑到因为有横轴数轴两部分的限制,不妨先固定下来一部分的限制再处理另一部分。
对于这题来说横轴竖轴本质是相同的,于是不妨考虑固定横轴。

如果知道了横轴的分割,那么对于竖轴上就可以根据分割情况知道合法的分割了。
即考虑记 \(f_i\) 为考虑了竖轴的前 \(i\) 列,第 \(i\) 列为最后一个划分的最后一列的方案数。
考虑转移的 \(f_j\to f_i\),那么 \(j\) 就要满足对于横轴的每一个划分,\((j, i]\) 内都只有 \(2\) 个 \(\texttt{Y}\)。

能够发现,转移时 \(i\) 对应的 \(j\) 应当是一个区间范围内的,于是可以前缀和优化 DP,复杂度就是 \(\mathcal{O}(km)\),其中 \(k\) 是横轴划分的段数。

于是接下来的问题就来到了横轴,由上述的讨论可知现在的问题就是尽量小化横轴划分的 \(\sum k\)(因为复杂度为 \(m\sum k\))。
那么接下来的想法就是找一些合法的横轴划分的必要条件,缩小这个 \(\sum k\) 了。

考虑到因为竖轴的划分对于所有横轴是相同的,这说明对于每个横轴划分出的部分内部的块数是相同的,进一步说明了每个横轴划分出的部分的 \(\texttt{Y}\) 的个数是相同的。

所以说可以枚举 \(\sum\limits_{i = 1}^n \sum\limits_{j = 1}^m [s_{i, j} = \texttt{Y}]\) 的因数 \(d\),然后按照横轴划分的每部分内的 \(\texttt{Y}\) 的个数都为 \(d\) 去尝试划分。

如果能够成功划分,那么就可以 DP,并且用乘法原理乘上横轴划分的方案数。
对于横轴划分的方案数,其实就是因为两个划分的块中可能有全 \(\texttt{X}\) 的行,这一行给任意一边都是不影响划分的,统计比较简单不在此阐述,可以参考实现。

分析一下 \(\sum k\),本人暂时只会感性理解,考虑到其实还是当每一行的 \(\texttt{Y}\) 的个数都相同最劣,因为这个时候能够尽量满足足够多的划分(?)。
于是可以知道 \(\sum k\) 应当是 \(\mathcal{O}(n\ln n)\) 级别的。

时间复杂度 \(\mathcal{O}(d(S)n + nm\ln n)\),其中 \(S = \sum\limits_{i = 1}^n \sum\limits_{j = 1}^m [s_{i, j} = \texttt{Y}]\),\(d(x)\) 表示 \(x\) 的因数个数。

#include<bits/stdc++.h>
using ll = long long;
constexpr ll mod = 998244353;
const int maxn = 2e3 + 10;
char s[maxn][maxn];
int sum[maxn][maxn];
int val[maxn];
int L[maxn], R[maxn];
ll g[maxn];
int main() {
   int n, m; 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++)
         sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + (s[i][j] == 'Y');
   if (! sum[n][m])
      return puts("0"), 0;
   int nst = 1, ned = n;
   while (sum[nst][m] == 0) nst++;
   while (sum[ned - 1][m] == sum[n][m]) ned--;
   ll ans = 0;
   for (int d = 2; d <= sum[n][m]; d += 2)
      if (sum[n][m] % d == 0) {
         ll f = 1;
         std::vector<std::pair<int, int> > seg;
         for (int i = nst, j = nst; i <= ned; i = j) {
            while (j <= ned && sum[j][m] - sum[i - 1][m] < d) j++;
            if (j > ned || sum[j][m] - sum[i - 1][m] > d) {f = 0; break;}
            seg.emplace_back(i, j);
            int c = 1; j++;
            while (j <= ned && sum[j][m] == sum[j - 1][m]) j++, c++;
            (f *= c) %= mod;
         }
         if (! f)
            continue;
         for (int i = 1; i <= m; i++)
            L[i] = 0, R[i] = i - 1;
         for (int id = 0; id < seg.size(); id++) {
            auto [x, y] = seg[id];
            for (int i = 0; i <= m; i++)
               val[i] = sum[y][i] - sum[x - 1][i];
            std::unordered_map<int, int> mx, mn;
            for (int i = 0; i <= m; i++)
               mx[val[i]] = i;
            for (int i = m; ~ i; i--)
               mn[val[i]] = i;
            for (int i = 1; i <= m; i++)
               if (mx.count(val[i] - 2)) {
                  R[i] = std::min(R[i], mx[val[i] - 2]);
                  L[i] = std::max(L[i], mn[val[i] - 2]);
               } else
                  R[i] = -1;
         }
         g[0] = 1ll;
         for (int i = 1; i <= m; i++) {
            if (L[i] <= R[i])
               g[i] = (g[R[i]] - (L[i] ? g[L[i] - 1] : 0ll) + mod) % mod;
            else  
               g[i] = 0;
            (g[i] += g[i - 1]) %= mod;
         }
         (ans += f * (g[m] - g[m - 1] + mod)) %= mod;
      }
   printf("%lld\n", ans);
   return 0;
}

标签:Atcoder,横轴,sum,texttt,YY,int,划分,maxn,ARC157D
From: https://www.cnblogs.com/rizynvu/p/18444835

相关文章

  • AtCoder Beginner Contest 365
    A-LeapYear思路模拟即可;AC代码#include<bits/stdc++.h>#defineendl'\n'#defineintintlonglong#definepbpush_back#definebsbitsetusingnamespacestd;typedefpair<char,int>PCI;typedefpair<......
  • 题解:AtCoder Beginner Contest AT_abc373_d ABC373D Hidden Weights(格式美化版)
    题目传送门题目翻译给你一个NNN个点,MMM条边的有向图,其中边有边......
  • AtCoder Beginner Contest 365题解
    A-LeapYear按照题意模拟即可。codeB-SecondBest按照题意模拟即可。codeC-TransportationExpenses考虑当\(x\)增大时,\(\min(x,a_i)=x\)的项会越来越少。换言之,当\(x\)足够大时,\(ans=\suma_i\),若此时\(ans>M\)则说明无论补贴多少,这时答案都是一定的......
  • AtCoder Beginner Contest 371(ABCDE)
    A个人直接硬解,讨论情况也并不复杂代码:#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;constintN=1e6+10;voidsolve(){chara,b,c;cin>>a>>b>>c;if(a=='<'){if(c=='<......
  • 题解:AtCoder Beginner Contest AT_abc373_d ABC373D Hidden Weights
    题目传送门题目翻译给你一个NNN个点,MMM条边的有向图,其中边有边......
  • yy语音找不到qjpeg4.dll怎么办?YY语音qjpeg4.dll修复大全:多种方法总有一款适合你
    当YY语音找不到qjpeg4.dll文件时,这通常意味着系统或YY语音的安装目录中缺少了必要的动态链接库文件。以下是一些修复方法,你可以根据自己的情况选择适合的一种或多种方法尝试解决:1.重新安装YY语音步骤:卸载当前版本的YY语音。清除可能残留的旧文件或注册表项(可选步骤,如果卸......
  • 「比赛记录」AtCoder abc373 (9.28)
    CTH想看F题解,于是先发出来F.KnapsackwithDiminishingValues属于是翻译官方题解了首先我们设\(dp_{w,j}\)表示从权重为\(w\)或更小的物品中选总重为\(j\)的物品可以得到的最大幸福度。考虑\(dp\)的转移。我们把所有物品按照权重\(w\)分为多组,(每一组中所有物品......
  • AtCoder Beginner Contest 373
    这场咋这么简单A.September\(\text{diff11}\)给你\(12\)个字符串\(S_1\)到\(S_{12}\),问你有多少字符串满足\(|S_i|=i\)点击查看代码usingnamespacereader;strings[13];intmain(){ for(inti=1;i<=12;++i){ cin>>s[i]; } intans=0; for(inti=1;i<=12......
  • AtCoder Beginner Contest 373
    A-September题意给\(12\)个字符串,问长度等于标号的字符串个数。思路模拟。代码点击查看代码#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintmxn=1e6+5;voidsolve(){ intans=0; for(inti=0;i<12;i++) { ......
  • 【Atcoder训练记录】AtCoder Beginner Contest 373
    https://atcoder.jp/contests/abc373/tasks赛后反思B题第一次读错题意,浪费了几分钟,需加强审题能力对于图论有些生疏,D题为简单图论,在76min的时候才AC,需加强训练图论A题给定12个字符串,求字符串长度\(=i\)的个数,直接模拟#include<bits/stdc++.h>#defineintlonglongu......