首页 > 试题广场 >

小美的字符串变换

[编程题]小美的字符串变换
  • 热度指数：1271 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
小美拿到了一个长度为n的字符串，她希望将字符串从左到右平铺成一个矩阵（先平铺第一行，然后是第二行，以此类推，矩阵有x行y列，必须保证x*y=n，即每y个字符换行，共x行）。

该矩阵的权值定义为这个矩阵的连通块数量。小美希望最终矩阵的权值尽可能小，你能帮小美求出这个最小权值吗？

注：我们定义，上下左右四个方向相邻的相同字符是连通的。

输入描述:
第一行输入一个正整数n，代表字符串的长度。
第二行输入一个长度为n的、仅由小写字母组成的字符串。
1\leq n \leq 10^4


输出描述:
输出一个整数表示最小权值。
示例1

输入

9
aababbabb

输出

2

说明

平铺为3*3的矩阵：
aab
abb
abb
共有2个连通块，4个a和5个b。
算法知识视频讲解
添加回答
C/C++
_Atlantis_头像 _Atlantis_
主要还是字符串和矩阵之间坐标转换，转过了这个弯之后就是针对每一个没有访问的点进行回溯遍历周围与它相同的字符 
#include <bits/stdc++.h>

using namespace std;

void backtrace(const string &str, bool *const flags, int x, int y, int row, int col, char c)
{
    int idx = row * y + col;
    if (row < 0 || row >= x || col < 0 || col >= y || flags[idx] || str[idx] != c)
        return;

    flags[idx] = true;
    backtrace(str, flags, x, y, row + 1, col, c);
    backtrace(str, flags, x, y, row - 1, col, c);
    backtrace(str, flags, x, y, row, col + 1, c);
    backtrace(str, flags, x, y, row, col - 1, c);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    string str;
    cin >> str;

    bool flags[n];

    long long ret = LONG_LONG_MAX;
    for (int x = 1; x < n; ++x)
    {
        if (n % x)
            continue;
        int y = n / x;

        fill(flags, flags + n, false);
        long long cnt = 0;
        for (int row = 0; row < x; ++row)
        {
            for (int col = 0; col < y; ++col)
            {
                int idx = row * y + col;
                if(!flags[idx])
                {
                    ++cnt;
                    backtrace(str, flags, x, y, row, col, str[idx]);
                }
            }
        }

        ret = min(ret, cnt);
    }

    cout << ret;
}


发表于 2023-08-17 10:48:01 回复(2)
牛客768475367号头像 牛客768475367号 
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            in.nextLine();
            char[] cs = in.nextLine().toCharArray();
            int res = n;
            for(int i=1;i<n;i++){
                if(n%i==0){
                    int row = i;
                    int col = n/i;
                    char[][] board = new char[row][col];
                    int[][] used = new int[row][col];
                    for(int j=0,count=0;j<row;j++){
                        for(int k=0;k<col;k++){
                            board[j][k] = cs[count++];
                        }
                    }
                    int num = 0;
                    for(int j=0;j<row;j++){
                        for(int k=0;k<col;k++){
                            if(used[j][k]==0){
                                dfs(board,used,j,k,++num);
                            }
                        }
                    }
                    res = Math.min(res,num);
                }
            }
            System.out.println(res);
        }
    } 
    public static void dfs(char[][] board,int[][]  used,int i,int j,int count){
        if(i<0||j<0||i>=board.length||j>=board[0].length||used[i][j]!=0){
            return;
        }
        used[i][j]=count;
        if(i>0&&board[i-1][j]==board[i][j]){
            dfs(board, used,i-1,j,count);
        }
        if(i<board.length-1&&board[i+1][j]==board[i][j]){
            dfs(board, used,i+1,j,count);
        }
        if(j>0&&board[i][j-1]==board[i][j]){
            dfs(board, used,i,j-1,count);
        }
        if(j<board[0].length-1&&board[i][j+1]==board[i][j]){
            dfs(board, used,i,j+1,count);
        }
    }
}
dfs
发表于 2023-11-18 12:03:17 回复(0)
Angelqs头像 Angelqs
#include <iostream>
#include <string>
#include <climits>
using namespace std;

int helper(string& s, int part){
    int result = 0;
    for(int i = 0; i < s.size(); i++){
        if((i >= part && s[i - part] == s[i]) && (i % part != 0 && s[i] == s[i - 1])){
            if(s[i - part - 1] != s[i]){
                result--;
            }
            continue;
        }
        if((i >= part && s[i - part] == s[i]) || (i % part != 0 && s[i] == s[i - 1])){
            continue;
        }
        result++;
    }
    return result;
}

int main() {
    int n = 0;
    cin >> n;
    string s;
    cin >> s;
    int result = INT_MAX;
    for(int i = 1; i <= n; i++){
        if(n % i != 0){
            continue;
        }
        else{
            result = min(result, helper(s, i));
        }
    }
    cout << result << endl;
}
// 64 位输出请用 printf("%lld")
发表于 2023-08-19 12:29:20 回复(0)
Python
开心的修勾在划水头像 开心的修勾在划水 
nn = int(input())
s = list(input())

# 行列可能的情况
mn=[]
for i in range(1,nn):
    if nn%i==0:
        mn.append((i,nn//i))
#回溯
def dfs(row,col,m,n,c):
    ##用行列来计算在一维数组中的角标
    i = row*n+col
    if row< 0&nbs***bsp;row>=m&nbs***bsp;col<0&nbs***bsp;col>=n&nbs***bsp;used[i]==1&nbs***bsp;s[i]!=c:
        return
    used[i] = 1
    dfs(row+1,col,m,n,c)
    dfs(row-1,col,m,n,c)
    dfs(row,col+1,m,n,c)
    dfs(row,col-1,m,n,c)

#计算
min_res=float('inf')
for m,n in mn:
    used = [0 for _ in range(nn)]
    res=0
    for i in range(m):
        for j in range(n):
            idx = i*n+j
            if used[idx]==0:
                ##如果某个元素未被检索到，则这次会检索到并且res+=1
                res+=1
                dfs(i,j,m,n,s[idx])
    min_res=min(min_res,res)
print(min_res)


        
编辑于 2023-08-17 15:44:34 回复(0)
Java
小牛马来咯头像 小牛马来咯
DFS连通图
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        String string =in.next();
        if(n==1){
            System.out.print(1);
            return;
        }
        
        int res=10000;
        for(int x=1;x<=n/2;x++){
            if(n%x==0){
                int count=0;
                int y=n/x;
                char[][] m=new char[x][y];
                for(int i=0;i<x;i++){
                    for(int j=0;j<y;j++){
                        m[i][j]=string.charAt(i*y+j);
                    }
                }
                boolean[][] visited=new boolean[x][y];
                for(int i=0;i<x;i++){
                    for(int j=0;j<y;j++){
                        if(!visited[i][j]){
                            char s=m[i][j];
                            dfs(m,i,j,visited,s);
                            count++;
                        }
                    }
                }
                res=Math.min(res,count);
            }
        }
        System.out.print(res);
    }
    public static void dfs(char[][] m,int r,int c,boolean[][] visited,char s){
        //char s=m[r][c];
        if(!isin(m,r,c) || m[r][c]!=s || visited[r][c]){
            return ;
        }

        visited[r][c]=true;

        dfs(m,r-1,c,visited,s);
        dfs(m,r+1,c,visited,s);
        dfs(m,r,c-1,visited,s);
        dfs(m,r,c+1,visited,s);
    }

    public static boolean isin(char[][] m,int r,int c){
        return (r>=0 && r<m.length && c>=0 && c<m[0].length);
    }
}

编辑于 2024-04-24 21:57:35 回复(0)
VaskaJ头像 VaskaJ
n = int(input())
s = input()

direct = [[0,1,0,-1],
        [-1,0,1,0]]

def dfs(matrix, i, j, visited, ch):
    global direct
    row = len(matrix)
    col = len(matrix[0])

    for t in range(4):
        new_i = i + direct[0][t]
        new_j = j + direct[1][t]
        if 0 <= new_i < row and 0 <= new_j < col and visited[new_i][new_j] == False and matrix[new_i][new_j] == ch:
            visited[new_i][new_j] = True
            dfs(matrix, new_i, new_j, visited, ch)



def get_val(matrix):
    res = 0
    row = len(matrix)
    col = len(matrix[0])
    visited = [[False] * col for _ in range(row)]
    for i in range(row):
        for j in range(col):
            if visited[i][j] == False:
                res += 1
                visited[i][j] = True
                dfs(matrix, i, j, visited, matrix[i][j])
    return res

min_val = float('inf')
for x in range(1, n):
    if n % x != 0:
        continue
    y = n // x
    matrix = []
    i = 0
    while i < n:
        matrix.append(s[i:i+y])
        i += y

    cur_val = get_val(matrix)
    min_val = min(min_val, cur_val)
print(min_val)


编辑于 2024-03-22 14:22:03 回复(0)
university201806281737696头像 university201806281737696 
import java.util.Scanner;

public class Main {

    //四个方向
    private static final int[][] DIRECT = {
            {0, 1},
            {0, -1},
            {1, 0},
            {-1, 0}
    };

    //检查是否越界
    private static boolean check(int x, int y, int m, int n) {
        return x >= 0 && x < m && y >= 0 && y < n;
    }

    private static int getMax(char[] chars, int length) {
        int ans = Integer.MAX_VALUE;
        for (int m = 1; m * m <= length; m++) {
            if (length % m == 0) {
                int n = length / m;
                //m*n的矩阵
                ans = Math.min(ans, getCount(chars, m, n, length));
                //n*m的矩阵
                ans = Math.min(ans, getCount(chars, n, m, length));
            }
        }
        return ans;
    }

    private static int getCount(char[] chars, int row, int column, int length) {
        UnionFind unionFind = new UnionFind(length);
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < column; j++) {
                //沿着四个方向，看能否合并
                for (int[] d : DIRECT) {
                    int nextI = i + d[0], nextJ = j + d[1];
                    //(i, j)在原来的位置：i * column + j
                    if (check(nextI, nextJ, row, column) && chars[i * column + j] == chars[nextI * column + nextJ]) {
                        unionFind.union(i * column + j, nextI * column + nextJ);
                    }
                }
            }
        }
        return unionFind.getCount();
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int length = in.nextInt();
        String s = in.next();
        System.out.println(getMax(s.toCharArray(), length));
    }

}

class UnionFind {
    private int[] parent;
    private int[] rank;
    //连通分量的大小
    private int count;

    public UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
        count = n;
    }

    public int find(int x) {
        while (x != parent[x]) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }

    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX == rootY) {
            return;
        }

        if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
            count--;
            return;
        }

        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
            count--;
            return;
        }

        parent[rootX] = rootY;
        rank[rootY]++;
        count--;
    }

    public int getCount() {
        return count;
    }
}
简单的因式分解+并集查
发表于 2024-03-09 17:55:59 回复(0)
小刀只会cv头像 小刀只会cv
golang实现 100% 过测试用例 
package main

import (
	"fmt"
	"math"
)

// 计算给定矩阵维度下的连通块数量
func calcBlocks(s string, rows, cols int) int {
	matrix := make([][]byte, rows)
	for i := range matrix {
		matrix[i] = make([]byte, cols)
	}

	// 填充矩阵
	for i, c := range s {
		matrix[i/cols][i%cols] = byte(c)
	}

	// 计算连通块
	blocks := 0
	visited := make([][]bool, rows)
	for i := range visited {
		visited[i] = make([]bool, cols)
	}
	for i := 0; i < rows; i++ {
		for j := 0; j < cols; j++ {
			if !visited[i][j] {
				dfs(matrix, visited, i, j, matrix[i][j])
				blocks++
			}
		}
	}
	return blocks
}

// 深搜
func dfs(matrix [][]byte, visited [][]bool, i, j int, char byte) {
	if i < 0 || j < 0 || i >= len(matrix) || j >= len(matrix[0]) || visited[i][j] || matrix[i][j] != char {
		return
	}
	visited[i][j] = true
	dfs(matrix, visited, i+1, j, char)
	dfs(matrix, visited, i-1, j, char)
	dfs(matrix, visited, i, j+1, char)
	dfs(matrix, visited, i, j-1, char)
}

func main() {
	var n int
	var s string
	fmt.Scan(&n)
	fmt.Scan(&s)

	minBlocks := math.MaxInt32
	// 尝试所有可能的行数x，因为x*y=n
	for x := 1; x <= n; x++ {
		if n%x == 0 {
			y := n / x
			blocks := calcBlocks(s, x, y)
			if blocks < minBlocks {
				minBlocks = blocks
			}
		}
	}
	fmt.Println(minBlocks)
}


编辑于 2024-03-09 01:54:05 回复(0)
jxy2012头像 jxy2012
写了好久，终于AK了。
发表于 2024-01-13 08:14:14 回复(0)
Java
lyongwolf头像 lyongwolf
此题是经典的并查集模板题。首先生成行列乘积为n的二阶矩阵，再根据矩阵中元素上下左右值是否与之相等选择是否union，最后得到并查集中集合数量。取所有二阶矩阵并查集中集合数量最小值即为解。 
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        char[] str = sc.next().toCharArray();
        int q = n;
        for (int i = 1; i <= n; i++) {
            if (n % i == 0) {
                int N = i;
                int M = n / i;
                int[][] board = new int[N][M];
                int index = 0;
                for (int j = 0; j < N; j++) {
                    for (int k = 0; k < M; k++) {
                        board[j][k] = str[index++];
                    }
                }
                q = Math.min(q, q(board));
            }
        }
        System.out.println(q);
    }

    public static int q(int[][] board) {
        int N = board.length;
        int M = board[0].length;
        UnionFind uf = new UnionFind(N * M);
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                int cur = i * M + j;
                if (i - 1 >= 0 && board[i - 1][j] == board[i][j]) {
                    uf.union(cur - M, cur);
                }
                if (i + 1 < N && board[i + 1][j] == board[i][j]) {
                    uf.union(cur + M, cur);
                }
                if (j - 1 >= 0 && board[i][j - 1] == board[i][j]) {
                    uf.union(cur - 1, cur);
                }
                if (j + 1 < M && board[i][j + 1] == board[i][j]) {
                    uf.union(cur + 1, cur);
                }
            }
        }
        return uf.size();
    }

    public static class UnionFind {
        private int[] parent;
        private int[] sizeMap;
        private int size;

        public UnionFind(int N) {
            size = N;
            parent = new int[N];
            sizeMap = new int[N];
            for (int i = 0; i < N; i++) {
                parent[i] = i;
                sizeMap[i] = 1;
            }
        }

        public int size() {
            return size;
        }

        private int find(int v) {
            if (v != parent[v]) {
                parent[v] = find(parent[v]);
            }
            return parent[v];
        }

        public void union(int v1, int v2) {
            int f1 = find(v1);
            int f2 = find(v2);
            if (f1 != f2) {
                size--;
                int s1 = sizeMap[f1];
                int s2 = sizeMap[f2];
                if (s1 > s2) {
                    parent[f2] = f1;
                    sizeMap[f1] += s2;
                } else {
                    parent[f1] = f2;
                    sizeMap[f2] += s1;
                }
            }
        }
    }
}



发表于 2023-11-03 22:17:00 回复(0)
C/C++
一点飞鸿影下头像 一点飞鸿影下
简单的并查集 

	
	

		#include <iostream>
	


	

		#include <vector>
	


	

		#include <cstring>
	


	

		using namespace std;
	


	

		class UFD
	


	

		{
	


	

		private:
	


	

		    vector<int> father;
	


	

		public:
	


	

		    UFD(int n)
	


	

		    {
	


	

		        for(int i = 0; i < n; i++)
	


	

		            father.push_back(i);
	


	

		    }
	


	

		    int find(int num)
	


	

		    {
	


	

		        if(father[num] != num)
	


	

		            father[num] = find(father[num]);
	


	

		        return father[num];
	


	

		    }
	


	

		    void connect(int start, int end)
	


	

		    {
	


	

		        start = find(start);
	


	

		        end = find(end);
	


	

		        if(start != end)
	


	

		            father[end] = start;
	


	

		    }
	


	

		};
	


	

		int sumConnectedBlock(string& str, int n, int m)
	


	

		{
	


	

		    UFD ufd = UFD(str.length());    
	


	

		    for(int i = 0; i < n; i++)
	


	

		    {
	


	

		        for(int j = 0; j < m; j++)
	


	

		        {
	


	

		            if(i > 0 && str[(i - 1)*m + j] == str[i*m + j])
	


	

		                ufd.connect((i - 1)*m + j, i*m + j);
	


	

		            if(j > 0 && str[i*m + j - 1] == str[i*m + j])
	


	

		                ufd.connect(i*m + j - 1, i*m + j);
	


	

		        }
	


	

		    }
	


	

		    int cnt = 0;
	


	

		    for(int i = 0; i < str.length(); i++)
	


	

		    {
	


	

		        cnt += ufd.find(i) == i;
	


	

		    }
	


	

		    return cnt;  
	


	

		}
	


	

		int main() {
	


	

		    int n;
	


	

		    cin >> n;
	


	

		    string str;
	


	

		    cin >> str;
	


	

		    int min_cnt = 10000;
	


	

		    for(int i = 1; i <= n; i++)
	


	

		    {
	


	

		        if(n % i == 0)
	


	

		        {
	


	

		            int cnt = sumConnectedBlock(str, i, n / i);
	


	

		            min_cnt = min(min_cnt, cnt);
	


	

		        }
	


	

		    }
	


	

		    cout << min_cnt << endl;
	


	

		    return 0;
	


	

		}

发表于 2023-09-29 10:23:07 回复(0)
言笑723头像 言笑723 
import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    static int c ;
    static ArrayList<Integer[]> set =  new ArrayList<>(Arrays.asList(new Integer[] {0, 1},
            new
            Integer[] {0, -1}, new Integer[] {1, 0}, new Integer[] {-1, 0}));
    static int h;
    static int l;
    static boolean[][] isvisit;
    static char[][] graph;
    static int fin=Integer.MAX_VALUE;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int a = in.nextInt();
            in.nextLine();
            String   s = in.nextLine();
            int slen  = s.length();
            for (int i1 = 1; i1 <= (int)(Math.sqrt(slen)); i1++) {
                if ((slen / i1)*i1==slen) {
                    
                    for (int m=0;m<2;m++){
                        if (m==0){
                            h = i1;
                         l  = slen / i1;
                        }
                        else {
                            l = i1;
                             h  = slen / i1;
                        }
                    graph = new char[h][l];
                    c=0;
                    for (int i = 0; i < h; i++) {
                        for (int j = 0; j < l; j++) {
                            graph[i][j] = s.charAt(i * l + j);
                            //System.out.println(s.charAt(i*l+j));
                        }
                    }
                    //System.out.println(h+"  t "+l);
                    isvisit  = new boolean[h][l];
                    for (int i = 0; i < h; i++) {
                        for (int j = 0; j < l; j++) {
                            if (!isvisit[i][j]) {
                                //  for (int i1=0;i1<h;i1++){

                                //     for (int j1=0;j1<l;j1++){
                                //         //System.out.println(isvisit[i1][j1]);
                                //     }}
                                c++;
                                dfs(i, j);

                            }

                        }
                    }
                   //System.out.println(h+" "+l+" "+c);
                    fin  =Math.min(fin,c);
                    }


                }
            }

            System.out.println(fin);
        }
    }
    static void dfs(int a, int b) {

        isvisit[a][b] = true;
        for (Integer[] tr : set) {
            int ta = a + tr[0];
            int tb = b + tr[1];
            if (ta >= 0 & ta < h && tb >= 0 && tb < l && !isvisit[ta][tb] &&
                    graph[a][b] == graph[ta][tb]) {
                dfs(ta, tb);
            }

        }

    }
}

发表于 2023-09-20 15:39:33 回复(0)
一个人生下来就是来工作得头像 一个人生下来就是来工作得 
#include <iostream>
#include <bits/stdc++.h>
using namespace std;


int res = INT_MAX;
int cnt;
int rowCnt;
int colCnt;

bool isValid(int i,int j){
    return i<rowCnt && j<colCnt && i>=0 && j>=0;
}

void dfs(vector<string>&mat,vector<vector<bool>>& isVisited,int i,int j){
    isVisited[i][j]=1;
    if(isValid(i+1,j) && mat[i][j]==mat[i+1][j] &&!isVisited[i+1][j]) dfs(mat,isVisited,i+1,j);
    if(isValid(i,j+1) && mat[i][j]==mat[i][j+1] &&!isVisited[i][j+1]) dfs(mat,isVisited,i,j+1);
    if(isValid(i-1,j) && mat[i][j]==mat[i-1][j] &&!isVisited[i-1][j]) dfs(mat,isVisited,i-1,j);
    if(isValid(i,j-1) && mat[i][j]==mat[i][j-1] &&!isVisited[i][j-1]) dfs(mat,isVisited,i,j-1);
}


int getWeight(string& s,int m,int n){
    cnt = 0;
    vector<vector<bool>> isVisited(m,vector<bool>(n,0));
    vector<string> mat(m,"");
    colCnt = n;
    rowCnt = m;
    int k=0;
    for(const auto& c:s){
        if((int)(mat[k].length())==n) k+=1; 
        mat[k] += c;
    }
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            if(!isVisited[i][j]){
                cnt++;
                dfs(mat,isVisited,i,j);
            }
        }
    }
    return cnt;
}



int main(){
    ios::sync_with_stdio(false);
    string s;
    int x;
    cin>>x>>s;
    for(int i=1;i<x;++i){
        if(x%i==0){
            int m = x/i;
            int n = i;
            res = min(res,getWeight(s,m,n));
        }
    }
    cout<< res;
    return 0;
}

发表于 2023-08-19 08:07:10 回复(0)
C/C++
zzq&cr头像 zzq&cr 
#include <climits>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
struct Pos {
    int x;
    int y;
    Pos(int a, int b) {
        x = a;
        y = b;
    }
};
 
 
int lianTong(vector<vector<char>>& v) {
 
    int ret = 0;
    vector<vector< int>> dp(v.size(), vector<int>(v[0].size(), 0));
 
    for (int i = 0; i < dp.size(); i++) {
        for (int j = 0; j < dp[i].size(); j++) {
            if (dp[i][j] == 0) {
                queue<Pos> q;
                int sum = 1;
 
 
                char base = v[i][j];
                q.push(Pos(i, j));
                dp[i][j] = 1;
                while (!q.empty()) {
                    // 向上找
                    int x = q.front().x;
                    int y = q.front().y;
                    if ( x - 1 >= 0 && dp[x - 1][y] == 0 && v[x - 1][y] == base) {
                        sum++;
                        q.push(Pos(x - 1, y));
                        dp[x-1][y] =1;
                    }
                    // 向下找
                    if ( x + 1 < dp.size() && dp[x + 1][y] == 0 && v[x + 1][y] == base) {
                        sum++;
                        q.push(Pos(x + 1, y));
                        dp[x+1][y] =1;
                    }
                    // 向左找
                    if ( y - 1 >= 0 && dp[x][y - 1] == 0 && v[x][y - 1] == base) {
                        sum++;
                        q.push(Pos(x, y - 1));
                        dp[x][y -1] =1;
                    }
                    // 向又找
                    if ( y + 1 < dp[x].size() && dp[x ][y + 1] == 0 && v[x ][y + 1] == base) {
                        sum++;
                        q.push(Pos(x, y + 1));
                        dp[x][y +1] =1;
                    }
                    q.pop();
 
                }
                if (sum > 0) ret++;
 
            }
        }
    }
    return ret;
 
}
 
int main() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    int min = INT_MAX;
    for(int row=1;row<n+1;row++){
        int col = n/row;
        if(col *row ==n){
             
            vector<vector<char>> v(row,vector<char>(col,'0'));
            for(int i=0;i<row;i++){
                for(int j=0;j<col;j++){
                    v[i][j] = s[i*col+j];
                }
            }
 
            int ret = lianTong(v);
            if (min > ret) min = ret;
 
 
        }
    }
    cout << min << endl;
}
// 64 位输出请用 printf("%lld")


发表于 2023-08-16 11:18:47 回复(0)
牛客346064503号头像 牛客346064503号
使用并查集求解的，为什么for( int x = 1 ; x * x <= n; ++x)通过不了第10个用例，而for(int x =1 ; x <= n; ++x)就可以了 
#include <bits/stdc++.h>

using namespace std;

class DSU{
public:
    vector<int> nums;
    DSU(int n ){
        nums.resize(n);
        for(int i = 0; i < n; ++i)
            nums[i] = i;
    }
    int findParent(int x){
        int y = x;
        while(y != nums[y])
            y = nums[y];
        while(x != nums[x]){
            int temp = x;
            x = nums[x];
            nums[temp] = y;
        }
        return y;
    }
    void merge(int x, int y){
        int parx = findParent(x);
        int pary = findParent(y);
        nums[parx] = pary;
    }
    int getUnion(){
        int ans = 0;
        for(int i = 0; i < nums.size(); ++i)
            if(nums[i] == i)
                ++ans;
        return ans;
    }
};

int dfs(const string& str, int m, int n){
    DSU dsu(m*n);
    for(int i = 0; i < m; ++i)
        for(int j = 0; j < n; ++j){
            if(i >= 1 && str[(i-1)*n+j] == str[i*n+j])
                dsu.merge((i-1)*n+j, i*n+j);
            if(j >= 1 && str[i*n+j-1] == str[i*n+j])
                dsu.merge(i*n+j-1, i*n+j);
        }
    return dsu.getUnion();
}


int main(){
    int n;
    int ans = INT_MAX;
    cin >> n;
    
    string str;
    cin >> str;
    for(int x = 1; x*x <= n; ++x){
        if(n%x)
            continue;
        int y = n/x;
        ans = min(ans,dfs(str,x,y));
    }
    cout << ans << endl;

    return 0;

}

// 64 kmnplvqksghziolcfczxpygfiahpgqdaezyjmbwvwgotojprgoqjyeajlqjzrcxd


发表于 2023-08-15 22:47:59 回复(2)
提交观点

问题信息

来自：美团2023年秋招笔试...
难度：
15条回答 1844浏览

热门推荐

相关试题

小美的字符串变换

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号