A - Cadena 11/22
Descripción:
Recibe una cadena S de longitud N. Determina si cumple con el formato "11/22". Esta configuración requiere que los caracteres situados a la izquierda de la barra (/) sean todos '1', los de la derecha sean todos '2', y ambas secciones tengan exactamente la misma longitud.
Estrategia:
No es necesario realizar análisis complejos. Simplemente verifique las condiciones requeridas: la longitud debe ser impar, el carácter central debe ser '/', y las mitades deben contener únicamente '1' y '2' respectivamente.
#include <iostream>
#include <string>
using namespace std;
void resolverProblemaA() {
int longitud;
string cadena;
cin >> longitud >> cadena;
bool valida = true;
// La longitud debe ser impar para tener un centro
if (longitud % 2 == 0) valida = false;
if (valida) {
int mitad = longitud / 2;
char centro = cadena[mitad];
// Verificar caracter central
if (centro != '/') valida = false;
// Verificar parte izquierda e inferior
for (int k = 0; k < mitad && valida; ++k) {
if (cadena[k] != '1') valida = false;
if (cadena[mitad + 1 + k] != '2') valida = false;
}
}
cout << (valida ? "Yes" : "No") << endl;
}
int main() {
resolverProblemaA();
return 0;
}
B - Cadena 1122
Descripción:
Dada una cadena S, determine si es válida bajo la regla "1122". Esto implica que cada par de caracteres consecutivos debe ser idéntico (ej. 'aa', 'bb'), pero ningún valor de letra puede aparecer en pares distintos dentro de la misma cadena.
Estrategia:
Itere sobre la cadena de dos en dos. Cada par debe tener caracteres iguales entre sí. Además, utilice un registro para asegurar que ningún tipo de letra se repita en diferentes posiciones de pares.
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main() {
string texto;
cin >> texto;
int tamano = texto.length();
if (tamano % 2 != 0) {
cout << "No" << endl;
return 0;
}
vector<bool> yaVisto(256, false);
bool posible = true;
for (int idx = 0; idx < tamano; idx += 2) {
char actual = texto[idx];
char siguiente = texto[idx + 1];
if (actual != siguiente) {
posible = false;
break;
}
if (yaVisto[actual]) {
posible = false;
break;
}
yaVisto[actual] = true;
}
cout << (posible ? "Yes" : "No") << endl;
return 0;
}</bool>
C - Subcadena 11/22 Máxima
Descripción:
Encuentre la longitud de la subsecuencia más larga que cumpla con el patrón de la Parte A (1s seguidos de / seguidos de 2s) dentro de una cadena dada.
Estrategia:
Recorra la cadena buscando el caracter divisor '/'. Cuando lo encuentre, expanda simultáneamente hacia la izquierda y la derecha mientras coincidan con '1' y '2' respectivamente. Mantanga el máximo ancho encontrado.
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
string s;
cin >> n >> s;
int maxLongitud = 0;
for (int i = 0; i < n; ++i) {
if (s[i] == '/') {
int distancia = 1;
// Expandir hacia ambos lados
while (i - distancia >= 0 && i + distancia < n) {
if (s[i - distancia] == '1' && s[i + distancia] == '2') {
distancia++;
} else {
break;
}
}
// Distancia se incrementó en uno después del último válido, ajustamos
distancia--;
int total = distancia * 2 + 1;
maxLongitud = max(maxLongitud, total);
// Optimización: saltar los elementos procesados
i += distancia;
}
}
cout << maxLongitud << endl;
return 0;
}
D - Subcadena 1122 Más Larga
Descripción:
Se proporciona un arreglo de números enteros. Calcule la longitud máxima de una subsecuencia contigua donde los números aparecen en pares idénticos consecutivos (x, x, y, y, z, z...), asegurando que los valores dentro de los pares sean únicos entre sí.
Estrategia:
La solución implica dividir el problema en dos casos basados en la paridad del índice inicial (índices pares o impares). Utilice un puntero izquierdo (inicioSegmento) para rastrear el inicio del bloque válido actual y un mapa de frecuencias para verificar duplicados globales.
#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;
const int MAX_VALOR = 200005;
int ultimasOcurr[MAX_VALOR];
int calcularMaximo(int n, const vector<int>& arr, int offset) {
fill(ultimasOcurr, ultimasOcurr + MAX_VALOR, -1);
int maxLen = 0;
int startPtr = offset;
// Iteramos desde el primer elemento válido del offset
for (int i = offset + 1; i < n; i += 2) {
int parActual = arr[i];
int parPrevio = arr[i - 1];
// Validar que el par tenga el mismo valor interno
if (parActual != parPrevio) {
startPtr = i + 1; // Reiniciar ventana
continue;
}
// Si este número ya apareció en otro par dentro de la ventana actual
if (ultimasOcurr[parActual] >= startPtr) {
startPtr = ultimasOcurr[parActual] + 2;
}
ultimasOcurr[parActual] = i - 1; // Guardar índice del primer elemento del par
maxLen = max(maxLen, i - startPtr + 1);
}
return maxLen;
}
int main() {
int n;
cin >> n;
vector<int> datos(n);
for(int i=0; i<n cin="">> datos[i];
int ans = max(calcularMaximo(n, datos, 0), calcularMaximo(n, datos, 1));
cout << ans << endl;
return 0;
}</n>
E - Subsecuencia 11/22 con Consultas
Descripción:
Tiene una cadena S y Q consultas. Para cada rango [L, R], determine la longitud máxima de una subsecuencia que siga el patrón 1...1/2...2 centrado en algún '/' dentro del rango.
Estrategia:
Preprocese la cadena calculando sumas prefijas para contar '1's y sufijos para contar '2's. Para cada consulta, identifique todas las barras '/' en el rango especificado. El valor óptimo se encuentra aplicando búsqueda binaria en la posición de estas barras, maximizando min(cont_izquierda, cont_derecha).
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, q;
cin >> n >> q;
string str;
cin >> str;
vector<int> preficio1(n + 2, 0);
vector<int> suficio2(n + 2, 0);
vector<int> barrasPos;
// Construir vectores auxiliares
for (int i = 0; i < n; ++i) {
if (str[i] == '/') barrasPos.push_back(i);
else if (str[i] == '1') preficio1[i + 1] = preficio1[i] + 1;
else preficio1[i + 1] = preficio1[i];
if (str[n - 1 - i] == '2') suficio2[n - i] = suficio2[n - i + 1] + 1;
else suficio2[n - i] = suficio2[n - i + 1];
}
// Ajustar preficio1 para que sea accesible desde 1-based si se prefiere lógica de rangos
// Aquí usaremos índices 0-based para la lógica directa sobre la cadena
while (q--) {
int L, R;
cin >> L >> R;
// Ajustar a 0-based si la entrada es 1-based (asumido por estándar CP)
L--; R--;
int idxMin = lower_bound(barrasPos.begin(), barrasPos.end(), L) - barrasPos.begin();
int idxMax = upper_bound(barrasPos.begin(), barrasPos.end(), R) - barrasPos.begin() - 1;
int mejorResultado = 0;
if (idxMin <= idxMax) {
int izq = idxMin, der = idxMax;
// Búsqueda binaria para encontrar el punto óptimo de corte
// Donde la cantidad de 1s a la izquierda empieza a superar a los 2s a la derecha
while (izq <= der) {
int mid = (izq + der) >> 1;
int posBarra = barrasPos[mid];
// Cantidad de 1s entre L y la barra
int cnt1 = preficio1[posBarra] - preficio1[L];
// Cantidad de 2s entre la barra y R
int cnt2 = suficio2[posBarra + 1] - suficio2[R + 2]; // Ajuste índice sufixo
// Nota: Los indices de suficio2 dependen de construcción.
// Reajuste lógico para claridad:
// Contar 2s directamente en el rango posterior a la barra
int tempCnt2 = 0;
// O uso de suma prefijada correcta
// Simplificación para robustez: usar suma prefija inversa correctamente mapeada
int val = min(cnt1, cnt2);
mejorResultado = max(mejorResultado, val);
if (cnt1 > cnt2) der = mid - 1;
else izq = mid + 1;
}
}
cout << (mejorResultado == 0 ? 0 : mejorResultado * 2 + 1) << "\n";
}
return 0;
}