（出题人 $Brian Dean$ 题解  $yuan$译）

此问题是一种递归（深度优先）搜索以识别图形中的连接组件的练习。

第一项任务比第二项任务简单得多。我们建一个图，其中每个单元格是一个结点，如果它们包含相同的数字，则两个相邻的单元格连接一条边。

然后，我们从每个单元格开始递归 $Flood$ 填充（跳过已经访问过的单元格），扩展每个联通区域，并累加联通区域的大小。

对于第二项任务，我们为每对奶牛$（x，y）$创建一个图，结点是我们在第一个任务中计算的区域，用一条边连接相邻区域，

其中一个区域用 $x$ 标记，另一个区域用 $y$ 标记。

图中的每个结点被赋予一个“权”值，其权值与第一个任务的相应区域的大小相同,然后我们在每个图形上开始递归 $Flood$ 填充以找到具有最大面积的任何一个。

这里有两个重要的想法可以使我们的解决方案快速运行。

一是确保第一个任务中的每个区域在第二个任务中都被压缩为单个结点。

如果我们不这样做，那么在第二个任务中，我们可能会反复递归扫描同一大片区域，浪费大量时间。

另一个方法是，当我们进行递归搜索时，我们需要确保运行时间仅依赖于图中的边数而不是结点数，因为第二个任务图中涉及大量结点，但可能边数很少。

例如，我们不希望为每个结点保留一个“是否遍历过”的标记数组，并且在每个递归搜索时都被初始化为 $false$。

相反，在下面的解决方案中，我们为此使用了映射数据结构，它只在需要时创建标志，避免初始化不相关结点的初始化标志。

每个数字块是一个整体，用并查集维护大小 ；

给所有相邻数字块建边 ，并根据颜色排序 ；

处理每个数字块与哪些数字块相连，维护一个颜色连接着哪些数字块；

枚举处理所有相邻的数字块方案，已经根据数字值排在一起；

$Brian$ $Dean$ 的代码如下：

#include <iostream>
#include <fstream>
#include <map>
#include <set>
#include <algorithm>
using namespace std;

int N, B[1001][1001], cellid[1001][1001], global_regid;

struct Graph {
  map<int,set<int>> out_edges; 
  map<int,int> nodesize, regid;  // size of each node and region ID to which it belongs
  map<int,int> regsize;  // size of each region
};     

typedef pair<int,int> pii;
map<int, Graph> G1; // Graphs for all possible single IDs
map<pii, Graph> G2; // Graphs for all possible adjacent region pairs

// Return size of region reachable from nodeid
int visit(Graph &G, int nodeid, int regid)
{
  if (G.regid.count(nodeid) > 0) return 0;  // already visited?  bail out
  G.regid[nodeid] = regid;  // mark this node as visited
  int a = G.nodesize[nodeid];       // tally up region size
  for (int nbrid : G.out_edges[nodeid]) 
    a += visit(G, nbrid, regid);
  G.regsize[regid] = a;
  return a;
}

// Compute region sizes and return largest region size in graph.
// Running time only depends on # of edges, not # of nodes, so graph can be very sparse
int largest_region(Graph &G)
{
  int m = 0;
  for (auto &p : G.out_edges) m = max(m, visit(G, p.first, ++global_regid));
  return m;
}

void add_edge(Graph &G, int node1, int node2)
{
  G.out_edges[node1].insert(node2);
  G.out_edges[node2].insert(node1);
  G.nodesize[node1] = G.nodesize[node2] = 1;
}

// Add edge between two regions in a region pair graph
void add_G2_edge(int i1, int j1, int i2, int j2)
{
  int b1 = B[i1][j1], b2 = B[i2][j2], c1 = cellid[i1][j1], c2 = cellid[i2][j2];
  if (b1 > b2) { swap (b1,b2); swap(c1,c2); }
  int r1 = G1[b1].regid[c1], r2 = G1[b2].regid[c2];
  pii p = make_pair(b1, b2);
  add_edge(G2[p], r1, r2);
  G2[p].nodesize[r1] = G1[b1].regsize[r1];
  G2[p].nodesize[r2] = G1[b2].regsize[r2];
}

int main()
{
  ifstream fin ("multimoo.in");
  ofstream fout ("multimoo.out");
  
  fin >> N;
  for (int i=1; i<=N; i++)
    for (int j=1; j<=N; j++) {
      fin >> B[i][j];
      cellid[i][j] = i*N+j;    // unique ID for each cell
    }

  // Build primary graph
  for (int i=1; i<=N; i++)
    for (int j=1; j<=N; j++) {
      add_edge(G1[B[i][j]],cellid[i][j],cellid[i][j]); 
      if (i<N && B[i+1][j] == B[i][j]) add_edge(G1[B[i][j]], cellid[i][j], cellid[i+1][j]);
      if (j<N && B[i][j+1] == B[i][j]) add_edge(G1[B[i][j]], cellid[i][j], cellid[i][j+1]);
    }
 
  // Find largest region in primary graph
  int answer1 = 0;
  for (auto &p : G1) answer1 = max(answer1,largest_region(p.second));


  // Build secondary graphs based on regions of the primary graph that are adjacent
  for (int i=1; i<=N; i++)     
    for (int j=1; j<=N; j++) { 
      if (i<N && B[i+1][j] != B[i][j]) add_G2_edge(i,j,i+1,j); 
      if (j<N && B[i][j+1] != B[i][j]) add_G2_edge(i,j,i,j+1); 
    }

  // Find largest region in secondary graphs
  int answer2 = 0;
  for (auto &p : G2) answer2 = max(answer2, largest_region(p.second));
  
  fout << answer1 << "\n";
  fout << answer2 << "\n";
  
  return 0;
}

算法一

特殊样例：

1、长度小于 $5$ 的字符串不折叠, 因为压缩的话至少长度为 $4$;

例如：AAAA->4(A) 折叠前后相等  A->1(A) 不折叠更优

2、长度大于等于 $5$ 时，只包含一个字母;

例如：AAAAAAAAA->9(A)

算法二

区间DP

设 $dp[i][j]$ 表示把区间 $[l, r]$ 内的字符压缩之后的最短长度，考虑两种操作：

1、合并两个小区间后变为一个大区间；

这显然就是区间 $dp$ 的套路方法，即：

for (int k = l;k < r;++k)
    dp[l][r] = min (dp[l][r],dp[l][k] + dp[k + 1][r]);

2、将某个区间进行折叠；

对于 $[l,r]$ 字符串，若要被折叠成循环节长度为 $k$ 的字符串，需要满足 $1≤k≤r−l+1$ 且 $k ∣(r−l+1)$ 且 $∀i∈[l,r−k]$   $s[i]==s[i+k]$，若符合要求，则 $dp[l][r] = min (dp[l][r] , 2 + nums ((r - l + 1) / k) + dp[l][l + k - 1])$。其中的 $2$ 是两个括号的长度，$nums (x)$ 表示重复次数 $x$ 的位数，$dp[l][l + k - 1]$ 即循环节。

在得到最小长度后，由于需要输出合法的方案，所以我们在此基础上还要记录一些断点的信息，从而进行搜索。

用两个数组分别记录第一和第二种的操作的断点，第一种操作记录断点位置，第二种操作记录循环节的长度。

由于一个区间的处理只进行一种操作，所以在标记时要把另外一种操作的断点设为 0。

在递归时，对于一个区间若两种断点均不存在，则直接输出这段区间；

若是第一种操作的断点 k，则分别递归处理区间 [l,k] 和 [k+1,r]；

若是第二种，则先输出左括号和重复的次数，递归循环节的区间，再输出右括号即可。

//参考程序1：dp[][]记录最优长度，额外记录断点，递归输出方案
#include<bits/stdc++.h>
#define init(x,y) memset(x,y,sizeof(x))
#define INF 0x3f3f3f3f
using namespace std;
const int N = 105;
char str[N];
int n,dp[N][N],cut[N][N],fold[N][N];
int nums (int num)
{
	int cnt = 0;
	while (num) num /= 10,++cnt;
	return cnt;
}
void check (int l,int r,int k)
{//[l,r]字符串是否可以折叠为长度为k的字符串
	if ((r - l + 1) % k) return ;
	for (int i = l;i <= r - k;++i)
		if (str[i] != str[i + k]) return ;//不合法
	int s = 2 + nums((r - l + 1) / k) + dp[l][l + k - 1];
	if (s < dp[l][r])
	{
		dp[l][r] = s;
		cut[l][r] = 0;
		fold[l][r] = k;//区间可直接折叠
	}
}

void dfs (int l,int r)
{//递归输出折叠方案
	if (!cut[l][r] && !fold[l][r])//不能折叠，原样输出
		for (int i = l;i <= r;++i) printf ("%c",str[i]);
	else
		if (cut[l][r])//有断点，分别递归两个区间
			dfs (l,cut[l][r]),dfs (cut[l][r] + 1,r);
		else//区间可直接折叠
		{
			printf ("%d(",(r - l + 1) / fold[l][r]);
			dfs (l,l + fold[l][r] - 1);//继续递归循环节
			printf (")");
		}
}
int main ()
{
	freopen ("folding.in","r",stdin);
	freopen ("folding.out","w",stdout);
	while (scanf ("%s",str + 1) != EOF)
	{
		n = strlen (str + 1);//从下标1开始存储
		init (dp,INF);init (cut,0);init (fold,0);
		for (int i = 1;i <= n;++i) dp[1][i] = i,dp[i][i] = 1;//初始化
		for (int len = 1;len <= n;++len)
		{//枚举区间长度
			for (int l = 1;l <= n - len + 1;++l)
			{//枚举区间左边界
				int r = l + len-1;//右边界
				//情况2：区间可直接折叠
				for (int k = 1;k <= (r - l + 1) / 2;++k)
					check(l,r,k);
				//情况1：枚举断点，分别折叠左右区间后再合并
				for (int k = l;k < r;++k)
				{//枚举断点
					if (dp[l][k] + dp[k + 1][r] < dp[l][r])//区间合并
					{
						dp[l][r] = dp[l][k] + dp[k + 1][r];
						cut[l][r] = k;//记录断点
						fold[l][r] = 0;
					}
				}
			}
		}
		//printf ("%d\n",dp[1][n]);// 最小操作次数
		dfs (1,n);//递归输出最优方案
		puts ("\n");
	}
	return 0;
}

-----------------------------------------------------------------------------------------------------------------------------

//参考程序2：dp[l][r]直接存最优方案；
#include <bits/stdc++.h>
using namespace std;
string dp[110][110], s;
 
string _to_string(int num) {
	string ans;
	while(num) {
		ans += num % 10 + '0';
		num /= 10;
	}
	reverse(ans.begin(), ans.end());
	return ans;
}
int main() {
	freopen("folding.in","r",stdin);
	freopen("folding.out","w",stdout);
	int n;
	while(cin >> s) {
		n = s.length();
		for (int i = 0; i < n; i++) {
			dp[i][i] = s[i];//初始化
		}
		for (int len = 2; len <= n; len++)
		{//枚举区间长度
			for (int lt = 0; lt < n - len + 1; lt++)
			{//枚举区间左边界
				int rt = lt + len - 1;//枚举区间右边界
				dp[lt][rt] = s.substr(lt, rt - lt + 1);//初始化
				for (int loop = 1; loop <= len / 2; loop++)
				{//枚举循环节长度，检测区间是否可以直接折叠
					if(len % loop) continue;
					int l = lt, r = lt + loop;
					while(s[l] == s[r] && r <= rt) l++, r++;
					if(r > rt)
					{
						int num = len / loop;//循环次数
						dp[lt][rt] = _to_string(num);
						dp[lt][rt] += "(";
						dp[lt][rt] += dp[lt][lt + loop - 1];
						dp[lt][rt] += ")";
						//cout<< dp[lt][rt] <<endl;
						break;
					}
				}
				for (int k = lt; k < rt; k++)//区间DP
				{//枚举断点，分别折叠左右子区间后再合并
					if(dp[lt][rt].length() > dp[lt][k].length() + dp[k + 1][rt].length() || dp[lt][rt].length() == 0)
					{
						dp[lt][rt] = dp[lt][k] + dp[k + 1][rt];
					}
				}
			}
		}
		cout << dp[0][n - 1] <<endl;
	}
	return 0;
}

题解原作者：2017级吴昊钟 NOI2019铜牌

难度：普及+/提高

算法一：暴力枚举

在 $[ 0,n ]$ 的范围内暴力枚举 $m$ 的取值，直接统计 $[m,n]$ 之间的数中 $0$ 出现的次数为 $k$ 的最大 $m$ 的值。

时间复杂度：$O(N^2)$

期望得分：$30$分

算法二：前缀和+扫描法

在 $[0,n]$ 的范围内扫描，每一次进位使用类似高精度加法的方式维护 $0$ 出现的次数的变化情况，选取 $sum(n)-sum(m-1)$ 的值为 $k$ 的最大 $m$ 的值。

时间复杂度：$O(N)$

期望得分：$50$分

算法三：前缀和+组合计数

利用加法原理和乘法原理可以直接计算出 $f(n)$ 为 $[0,n]$ 之间的数中 $0$ 出现的次数，从 $n$ 开始倒序扫描选取第一个 $sum(n)-sum(m-1)$ 的值为 $k$ 的 $m$ 即可。也可以将算法二倒序维护解决。

时间复杂度：$O(N-M)$

期望得分：$70$分

算法四：二分法+前缀和+组合计数

在前一个算法的基础上利用二分法快速索引满足条件的 $m$ 的最大值即可。

时间复杂度：$O(log_{2}N)$

期望得分：$100$分