小美的字符串变换_

C/C++

_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号

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

#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)

牛客745468920号

#include <iostream>
#include <string>
#include <vector>
using namespace std;
vector<pair<int, int>> getTwoFactorizations(int n) {
    vector<pair<int, int>> result;

    for (int i = 2; i <= n / 2; i++) { // 只检查前半部分
        if (n % i == 0) { // i 是 n 的因子
            result.push_back({ i, n / i });
        }
    }

    return result;
}
int main() {
    int len;
    cin >> len;
    string str;
    cin >> str;
    auto ways = getTwoFactorizations(len);
    int ans = 1;
    char pre = str[0];
    for (int i = 1; i < len; i++) {
        if (str[i] != pre) {
            ans++;
            pre = str[i];
        }
    }
    vector<int>visited(len);
    int row_size = 0;
    int col_size = 0;
    int dirs[4][2] = { {0, 1}, {0, -1}, {-1, 0}, {1, 0} };
    auto dfs = [&](auto&& dfs, int row, int col, char cur) ->void {
        for (auto dir : dirs) {
            int new_row = row + dir[0];
            int new_col = col + dir[1];
            if (new_row >= 0 && new_row < row_size && new_col >= 0 && new_col < col_size &&
                !visited[new_row * col_size + new_col] && str[new_row * col_size + new_col] == cur) {
                visited[new_row * col_size + new_col] = 1;
                dfs(dfs, new_row, new_col, cur);
            }
        }
        return;
        };
    for (auto way : ways) {
        visited.assign(visited.size(), 0); // 重新填充整个 vector 为 0
        row_size = way.first;
        col_size = way.second;
        int temp = 0;
        for (int i = 0; i < row_size; i++) {
            for (int j = 0; j < col_size; j++) {
                if (!visited[i * col_size + j]) {
                    temp++;
                    visited[i * col_size + j] = 1;
                    dfs(dfs, i, j, str[i * col_size + j]);
                }
            }
        }
        ans = min(ans, temp);
    }
    cout << ans << endl;
}

发表于 2025-03-12 14:41:54 回复(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

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

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

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)

woshicainiao

写了好久，终于AK了。

发表于 2024-01-13 08:14:14 回复(0)

Java

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

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

#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号

使用并查集求解的，为什么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)

小美的字符串变换

输入描述:

输出描述:

输入

输出

说明

问题信息

热门推荐

相关试题