Este artículo recopila soluciones rápidas a problemas de dificultad baja (rojo y naranja) resueltos durante octubre en la plataforma Luogu. Se omiten problemas de nivel superior.
9 de noviembre
P1012 – Concatenar números para formar el mayor posible
Ordenar las cadenas directamente por orden lexicográfico falla; el criterio corrceto es: a + b > b + a.
#include <iostream>
#include <algorithm>
using namespace std;
const int MAX = 25;
string v[MAX];
bool mejor(const string& x, const string& y) {
return x + y > y + x;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n; cin >> n;
for (int i = 0; i < n; ++i) cin >> v[i];
sort(v, v + n, mejor);
for (int i = 0; i < n; ++i) cout << v[i];
return 0;
}
P1017 – Conversión entre bases arbitrarias
Al trabajar con bases negativas el residuo puede ser negativo; se ajusta sumanddo la base y corrigiendo el cociente.
#include <iostream>
using namespace std;
void imprimir(int resto) {
if (resto < 10) cout << resto;
else cout << char('A' + resto - 10);
}
void convertir(int n, int base) {
if (n == 0) return;
int r = n % base;
if (r < 0) { r -= base; n += base; }
convertir(n / base, base);
imprimir(r);
}
int main() {
int n, m; cin >> n >> m;
cout << n << "=";
if (n == 0) cout << 0;
else convertir(n, m);
cout << "(base" << m << ")\n";
return 0;
}
10 de noviembre
B3647 – Floyd-Warshall (plantilla)
Distancia mínima entre todo par de nodos en O(n³).
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 110, INF = 1e9;
int d[MAXN][MAXN];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m; cin >> n >> m;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
d[i][j] = (i == j ? 0 : INF);
for (int i = 0; i < m; ++i) {
int u, v, w; cin >> u >> v >> w;
d[u][v] = d[v][u] = w;
}
for (int k = 1; k <= n; ++k)
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) cout << d[i][j] << ' ';
cout << '\n';
}
return 0;
}
B3648 – "¿Cuántos años tienes?"
Lectura y salida literal.
#include <iostream>
int main() {
int x; std::cin >> x;
std::cout << "I am " << x << " years old.\n";
}
B3649 – Comparación simple
#include <iostream>
int main() {
int a, b; std::cin >> a >> b;
std::cout << (a <= b ? "YE5" : "N0") << '\n';
}
B3650 – Suma parcial 1..n
Imprimir la suma acumulada después de cada iteración.
#include <iostream>
int main() {
long long n, s = 0; std::cin >> n;
for (long long i = 1; i <= n; ++i) {
s += i;
std::cout << s << '\n';
}
}
11 de noviembre
B3821 – Casos de prueba para hackear
Para la subtarea 1 fuerza overflow: k = 1e9, n = 1e9-1.
Para la subtarea 2 basta con una cadena que cumpla solo las condiciones 2 y 3, por ejemplo aaaccc.
#include <iostream>
int main() {
int t; std::cin >> t;
if (t == 1) std::cout << "1000000000 999999999\n";
else std::cout << "aaaccc\n";
}
14 de octubre
B3632 – Operaciones con conjuntos
Usar arreglos booleanos para intersección y unión.
#include <iostream>
using namespace std;
const int MAX = 70;
bool A[MAX], B[MAX];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, x;
cin >> n;
for (int i = 0; i < n; ++i) { cin >> x; A[x] = true; }
cin >> m;
for (int i = 0; i < m; ++i) { cin >> x; B[x] = true; }
cout << n << '\n';
for (int i = 0; i < 64; ++i) if (A[i] && B[i]) cout << i << ' ';
cout << '\n';
for (int i = 0; i < 64; ++i) if (A[i] || B[i]) cout << i << ' ';
cout << '\n';
return 0;
}
B3637 – Subsecuencia creciente más larga
DP clásico O(n²).
#include <iostream>
using namespace std;
const int MAX = 5050;
int a[MAX], dp[MAX];
int main() {
int n; cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i];
int res = 0;
for (int i = 1; i <= n; ++i) {
dp[i] = 1;
for (int j = 1; j < i; ++j)
if (a[j] < a[i]) dp[i] = max(dp[i], dp[j] + 1);
res = max(res, dp[i]);
}
cout << res << '\n';
return 0;
}
B3636 – Mínimo de operaciones para reducir a 1
Greedy: si es par dividir entre 2, si no restar 1. Complejidad O(log n).
#include <iostream>
int main() {
long long n, pasos = 0;
std::cin >> n;
while (n != 1) {
if (n & 1) --n;
else n /= 2;
++pasos;
}
std::cout << pasos;
}
15 de octubre
CF1789A – Serval y Mocha
Basta con encontrar dos elementos cuyo gcd ≤ 2.
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t; cin >> t;
while (t--) {
int n; cin >> n;
int a[110];
for (int i = 0; i < n; ++i) cin >> a[i];
bool ok = false;
for (int i = 0; i < n && !ok; ++i)
for (int j = i + 1; j < n; ++j)
if (__gcd(a[i], a[j]) <= 2) ok = true;
cout << (ok ? "Yes" : "No") << '\n';
}
return 0;
}
CF1789B – Servall e Inversiones Mágicas
Comprobar que la cadena es casi palíndromo con a lo más un cambio.
#include <iostream>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t; cin >> t;
while (t--) {
int n; string s; cin >> n >> s;
int cambios = 0;
for (int i = 0, j = n - 1; i < j; ++i, --j)
if (s[i] != s[j]) ++cambios;
cout << (cambios <= 1 ? "YES" : "NO") << '\n';
}
return 0;
}
CF1883B – Chemistry
Sea odd la cantidad de letras con frecuencia impar. La respuesta es YES si odd-1 <= k.
#include <iostream>
#include <array>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t; cin >> t;
while (t--) {
int n, k; string s; cin >> n >> k >> s;
array<int, 26> freq{};
for (char c : s) ++freq[c - 'a'];
int odd = 0;
for (int v : freq) odd += v & 1;
cout << (max(0, odd - 1) <= k ? "Yes" : "No") << '\n';
}
return 0;
}