Skip to Content
CTRL K

Diluc and Kaeya

Editorial oficial (C++, Java) 

Explicación

Consideremos un string con una razón no reducida 2D:2K2D:2K y una subcadena con razón D:KD:K. Si sacamos la subcadena con razón D:KD:K, nos queda otra subcadena con razón D:KD:K (2D−D:2K−K2D-D:2K-K), por lo que el string original se puede partir. Así, para “cortar” una subcadena del string original, la razón reducida de la subcadena debe ser la misma que la razón reducida del string original.

Nótese que las subcadenas deben empezar en el índice 00. Si sacamos una subcadena del medio del string, es más difícil calcular la razón de los elementos anteriores.

Llevamos el número total de ‘D’ y el número total de ‘K’. Para cada prefijo, la razón D:KD:K en términos más bajos es Dgcd⁡(D,K):Kgcd⁡(D,K)\frac{D}{\gcd(D,K)}:\frac{K}{\gcd(D,K)}. La solución para cada prefijo es cuántas veces apareció esta razón reducida hasta ahora más uno. Sumamos uno porque la cantidad de veces que apareció esta razón reducida es la cantidad de cortes, y la cantidad de piezas resultantes de los cortes es los cortes más uno.

Implementación

Complejidad temporal: O(N)\mathcal{O}(N)

#include <algorithm>
#include <iostream>
#include <unordered_map>
#include <vector>
 
using std::cout;
using std::endl;
using std::vector;
 
int main() {
	int test_num;
	std::cin >> test_num;
	for (int t = 0; t < test_num; t++) {
		int len;
		std::cin >> len;
		vector<char> str(len);
		for (char &c : str) { std::cin >> c; }
 
		int d_num = 0;
		int k_num = 0;
		vector<int> max_pref_chunks;
		std::unordered_map<int, std::unordered_map<int, int>> prev_ratios;
		for (char c : str) {
			if (c == 'D') {
				d_num++;
			} else if (c == 'K') {
				k_num++;
			}
			// get the simplified ratio by dividing both quantities by the gcd
			int gcd = std::__gcd(d_num, k_num);
			int d_ratio = d_num / gcd;
			int k_ratio = k_num / gcd;
			// add the ratio to the records and record the max prefix chunk
			// amount
			max_pref_chunks.push_back(++prev_ratios[d_ratio][k_ratio]);
		}
 
		for (int i = 0; i < len - 1; i++) { cout << max_pref_chunks[i] << ' '; }
		cout << max_pref_chunks.back() << endl;
	}
}
import java.io.*;
import java.util.*;
 
public class DilucKaeya {
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
		int testNum = Integer.parseInt(read.readLine());
 
		StringBuilder ans = new StringBuilder();
		for (int t = 0; t < testNum; t++) {
			read.readLine();
			String str = read.readLine();
 
			int dNum = 0;
			int kNum = 0;
			HashMap<Integer, HashMap<Integer, Integer>> prevRatios = new HashMap<>();
			int[] maxPrefChunks = new int[str.length()];
			for (int i = 0; i < str.length(); i++) {
				if (str.charAt(i) == 'D') {
					dNum++;
				} else if (str.charAt(i) == 'K') {
					kNum++;
				}
				// get the simplified ratio by dividing both quantities by the
				// gcd
				int gcd = gcd(dNum, kNum);
				int dRatio = dNum / gcd;
				int kRatio = kNum / gcd;
 
				// add the ratio to the records and record the max prefix chunk
				// amount
				if (!prevRatios.containsKey(dRatio)) {
					prevRatios.put(dRatio, new HashMap<>());
				}
				prevRatios.get(dRatio).put(
				    kRatio, prevRatios.get(dRatio).getOrDefault(kRatio, 0) + 1);
				maxPrefChunks[i] = prevRatios.get(dRatio).get(kRatio);
			}
 
			for (int i = 0; i < str.length() - 1; i++) {
				ans.append(maxPrefChunks[i]).append(' ');
			}
			ans.append(maxPrefChunks[str.length() - 1]).append('\n');
		}
		System.out.print(ans);
	}
 
	private static int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
}
from math import gcd
 
for _ in range(int(input())):
	input()
	k_num = 0
	d_num = 0
	max_pref_chunks = []
	pref_ratios = {}
	for c in input():
		if c == "D":
			d_num += 1
		elif c == "K":
			k_num += 1
 
		# get the simplified ratio by dividing both quantities by the gcd
		common = gcd(d_num, k_num)
		d_ratio = d_num // common
		k_ratio = k_num // common
 
		# add the ratio to the records and record the max prefix chunk amount
		if d_ratio not in pref_ratios:
			pref_ratios[d_ratio] = {}
		if k_ratio not in pref_ratios[d_ratio]:
			pref_ratios[d_ratio][k_ratio] = 0
		pref_ratios[d_ratio][k_ratio] += 1
		max_pref_chunks.append(pref_ratios[d_ratio][k_ratio])
 
	print(" ".join(str(m) for m in max_pref_chunks))
Fundamentos