11.23
LG14362 [CSP-S2025] Route
Un ajout important : pour un graphe donné, après avoir calculé son arbre couvrant minimum (MST), si l'on ajoute d'autres arêtes pour former un nouveau graphe, le MST du nouveau graphe n'utilisera jamais les arêtes non-arbres de l'ancien graphe.
LG14394/LOJ2729 [JOISC 2016] Poupée gigogne
Analyse
Le problème semble pouvoir être résolu en précalculant le nombre total de poupées emboîtées pour chaque configuration donnée, puis en utilisant une recherche binaire pour chaque requête. Cependant, la complexité résultante, potentiellement O(Qn log n), pourrait être trop élevée. De plus, la partie sur l'emboîtement ressemble à un problème d'optimisation glouton ou de programmation dynamique (DP). La présence du tag "théorème de Dilworth" suggère une approche plus profonde.
Plus tard dans la journée, l'idée est d'utiliser une approche hors ligne. Les dimensions (diamètre de base et hauteur) des poupées peuvent être représentées comme des points sur un plan cartésien. Le problème se transforme alors en la recherche de la plus longue sous-séquence croissante dans un arrangement de points dans le premier quadrant. Une optimisation avec un arbre de données (BIT) est appliquée à la DP. La discrétisation est nécessaire car les valeurs R_i, H_i, A_j, B_j peuvent atteindre 10^9.
Solution
#include <bits>
using namespace std;
const int N = 200005;
int n, q;
struct node {
int r, h, id;
} inp[N << 1];
int b[N << 1], c[N << 1];
int ans[N];
void add(int x, int v) {
for (int i = x; i < (N << 1); i += i & (-i))
c[i] = max(c[i], v);
}
int query(int x) {
int res = 0;
for (int i = x; i; i -= i & (-i))
res = max(res, c[i]);
return res;
}
bool cmp(node x, node y) {
if (x.r != y.r)
return x.r > y.r;
if (x.h != y.h)
return x.h < y.h;
return x.id < y.id;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> q;
int m = 0;
for (int i = 1; i <= n + q; i++) {
int R, H;
cin >> R >> H;
b[++m] = H;
if (i > n) {
inp[i] = (node) { R, H, i - n };
} else {
inp[i] = (node) { R, H, 0 };
}
}
sort(inp + 1, inp + n + q + 1, cmp);
sort(b + 1, b + m + 1);
m = unique(b + 1, b + m + 1) - b - 1;
for (int i = 1; i <= n + q; i++)
inp[i].h = lower_bound(b + 1, b + m + 1, inp[i].h) - b;
for (int i = 1; i <= n + q; i++) {
if (inp[i].id) {
ans[inp[i].id] = query(inp[i].h);
} else {
add(inp[i].h, query(inp[i].h) + 1);
}
}
for (int i = 1; i <= q; i++)
cout << ans[i] << '\n';
}
</bits>
LG14396/LOJ2731 [JOISC 2016] Solitaire
Analyse
Le problème semble être de type comptage. Une première tentative consiste à déterminer les cas impossibles. Les configurations impossibles sont celles où une ligne de longueur supérieure à 2 contient des 'x' consécutifs, ou lorsque les quatre coins sont des 'x'.
Une approche par programmation dynamique (DP) est envisagée. L'état de la DP pourrait considérer les trois lignes et la colonne courante. Un état plus détaillé pourrait inclure l'index de la colonne et le mode de placement (par ligne ou par colonne). Les transitions dépendent des configurations possibles des cellules adjacentes. L'optimisation par sommes préfixées et la gestion des lignes 1 et 3 séparément sont considérées. La solution implémente une logique complexe de DP avec des optimisations.
Solution
#include <bits>
#define int long long
#define mod 1000000007
using namespace std;
const int N = 2005;
void calc(int &x, int y){
x += y;
if (x >= mod)
x -= mod;
}
int n;
string s[3];
int f[N][N * 3][2];
int C[N * 3][N * 3], fac[N * 3];
int p[6010][3];
int cnt;
int work(int l, int r){
int cnt_col;
cnt_col = (s[0][l] == 'x') + (s[1][l] == 'x') + (s[2][l] == 'x');
f[l][cnt_col][1] = fac[cnt_col - 1];
if (l != 1){
if (cnt_col == 2)
f[l][1][0] = 1;
if (cnt_col == 3)
f[l][1][0] = f[l][2][0] = 2;
}
memset(p, 0, sizeof(p));
for (int j = 1; j <= cnt_col + 5; j++)
p[j][1] = (p[j - 1][1] + f[l][j][1]) % mod;
for (int j = 1; j <= cnt_col + 5; j++)
p[j][2] = (p[j - 1][2] + j * f[l][j][1]) % mod;
for (int j = cnt_col; j; j--)
p[j][0] = (p[j + 1][0] + f[l][j][0]) % mod;
for (int i = l + 1; i <= r; i++){
int tmp = (s[0][i] == 'x') + (s[2][i] == 'x');
cnt_col += tmp + 1;
for (int j = 1; j <= cnt_col; j++){
int coe = fac[tmp] * C[j - 1][tmp] % mod;
calc(f[i][j][1], p[cnt_col - tmp - 1][1] * coe % mod);
calc(f[i][j][1], p[j - tmp][0] * coe % mod);
if (tmp){
calc(f[i][j][0], p[j - 1][1] * C[cnt_col - j][tmp] % mod * fac[tmp] % mod);
if (tmp != 1){
coe = (cnt_col - j) * fac[tmp] % mod;
calc(f[i][j][0], (p[j - 1][1] * (j - 1) % mod - p[j - 1][2] + mod) % mod * coe % mod);
if (j >= 2)
calc(f[i][j][0], p[j - 2][2] * coe % mod);
}
}
}
for (int j = 1; j <= cnt_col + 5; j++)
p[j][1] = (p[j - 1][1] + f[i][j][1]) % mod;
for (int j = 1; j <= cnt_col + 5; j++)
p[j][2] = (p[j - 1][2] + j * f[i][j][1]) % mod;
for (int j = cnt_col; j; j--)
p[j][0] = (p[j + 1][0] + f[i][j][0]) % mod;
}
::cnt += cnt_col;
int ret = 0;
for (int i = 1; i <= cnt_col; i++)
calc(ret, (f[r][i][1] + (r != n) * f[r][i][0]) % mod);
return ret % mod;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int i = C[0][0] = fac[0] = 1; i <= n * 3; i++){
fac[i] = fac[i - 1] * i % mod;
for (int j = C[i][0] = 1; j <= i; j++)
C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
}
cin >> s[0] >> s[1] >> s[2];
s[0] = " " + s[0];
s[1] = " " + s[1];
s[2] = " " + s[2];
if (s[0][1] == 'x' || s[0][n] == 'x' || s[2][1] == 'x' || s[2][n] == 'x'){
cout << 0;
return 0;
}
int c = 0, maxn = 0;
for (int i = 1; i <= n; i++){
if (s[0][i] == 'x'){
maxn = max(maxn, ++c);
}
else{
c = 0;
}
}
if (maxn > 1){
cout << 0;
return 0;
}
c = 0;
for (int i = 1; i <= n; i++){
if (s[2][i] == 'x'){
maxn = max(maxn, ++c);
}
else{
c = 0;
}
}
if (maxn > 1){
cout << 0;
return 0;
}
int tmp = 0, ans = 1;
for (int i = 1; i <= n; i++){
if (s[1][i] == 'o')
tmp += (s[0][i] == 'x') + (s[2][i] == 'x');
else{
int k = cnt;
int j = i;
while (j <= n && s[1][j] == 'x')
j++;
ans = ans * work(i, j - 1) % mod * C[cnt][k] % mod;
i = j - 1;
}
}
cout << ans * C[cnt + tmp][tmp] % mod * fac[tmp] % mod;
}
</bits>
LG8321 『JROI-4』 Avene de Bucarest 2
Analyse
La condition est que A soit monotone non croissante, et que la valeur maximale de A soit supérieure ou égale à la valeur minimale de B. Ces conditions semblent inhabituelles. Après avoir consulté une explication, l'approche consiste à fusionner et trier les tableaux A et B pour simplifier la condition sur le minimum de B. Le problème se ramène alors à un problème d'apparimeent résolu par DP. L'état DP, noté f[i][j], représente le nombre de façons d'apparier j éléments parmi les i premiers éléments de la séquence combinée C. La transition considère si l'élément courant est apparié ou non.
Solution
#include <bits>
#define int long long
#define mod 998244353
using namespace std;
const int N = 5005;
void calc(int &x, int y){
x += y;
if (x >= mod)
x -= mod;
}
int n;
string s[3];
int f[N][N * 3][2];
int C[N * 3][N * 3], fac[N * 3];
int p[6010][3];
int cnt;
int work(int l, int r){
int cnt_col;
cnt_col = (s[0][l] == 'x') + (s[1][l] == 'x') + (s[2][l] == 'x');
f[l][cnt_col][1] = fac[cnt_col - 1];
if (l != 1){
if (cnt_col == 2)
f[l][1][0] = 1;
if (cnt_col == 3)
f[l][1][0] = f[l][2][0] = 2;
}
memset(p, 0, sizeof(p));
for (int j = 1; j <= cnt_col + 5; j++)
p[j][1] = (p[j - 1][1] + f[l][j][1]) % mod;
for (int j = 1; j <= cnt_col + 5; j++)
p[j][2] = (p[j - 1][2] + j * f[l][j][1]) % mod;
for (int j = cnt_col; j; j--)
p[j][0] = (p[j + 1][0] + f[l][j][0]) % mod;
for (int i = l + 1; i <= r; i++){
int tmp = (s[0][i] == 'x') + (s[2][i] == 'x');
cnt_col += tmp + 1;
for (int j = 1; j <= cnt_col; j++){
int coe = fac[tmp] * C[j - 1][tmp] % mod;
calc(f[i][j][1], p[cnt_col - tmp - 1][1] * coe % mod);
calc(f[i][j][1], p[j - tmp][0] * coe % mod);
if (tmp){
calc(f[i][j][0], p[j - 1][1] * C[cnt_col - j][tmp] % mod * fac[tmp] % mod);
if (tmp != 1){
coe = (cnt_col - j) * fac[tmp] % mod;
calc(f[i][j][0], (p[j - 1][1] * (j - 1) % mod - p[j - 1][2] + mod) % mod * coe % mod);
if (j >= 2)
calc(f[i][j][0], p[j - 2][2] * coe % mod);
}
}
}
for (int j = 1; j <= cnt_col + 5; j++)
p[j][1] = (p[j - 1][1] + f[i][j][1]) % mod;
for (int j = 1; j <= cnt_col + 5; j++)
p[j][2] = (p[j - 1][2] + j * f[i][j][1]) % mod;
for (int j = cnt_col; j; j--)
p[j][0] = (p[j + 1][0] + f[i][j][0]) % mod;
}
::cnt += cnt_col;
int ret = 0;
for (int i = 1; i <= cnt_col; i++)
calc(ret, (f[r][i][1] + (r != n) * f[r][i][0]) % mod);
return ret % mod;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int i = C[0][0] = fac[0] = 1; i <= n * 3; i++){
fac[i] = fac[i - 1] * i % mod;
for (int j = C[i][0] = 1; j <= i; j++)
C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
}
cin >> s[0] >> s[1] >> s[2];
s[0] = " " + s[0];
s[1] = " " + s[1];
s[2] = " " + s[2];
if (s[0][1] == 'x' || s[0][n] == 'x' || s[2][1] == 'x' || s[2][n] == 'x'){
cout << 0;
return 0;
}
int c = 0, maxn = 0;
for (int i = 1; i <= n; i++){
if (s[0][i] == 'x'){
maxn = max(maxn, ++c);
}
else{
c = 0;
}
}
if (maxn > 1){
cout << 0;
return 0;
}
c = 0;
for (int i = 1; i <= n; i++){
if (s[2][i] == 'x'){
maxn = max(maxn, ++c);
}
else{
c = 0;
}
}
if (maxn > 1){
cout << 0;
return 0;
}
int tmp = 0, ans = 1;
for (int i = 1; i <= n; i++){
if (s[1][i] == 'o')
tmp += (s[0][i] == 'x') + (s[2][i] == 'x');
else{
int k = cnt;
int j = i;
while (j <= n && s[1][j] == 'x')
j++;
ans = ans * work(i, j - 1) % mod * C[cnt][k] % mod;
i = j - 1;
}
}
cout << ans * C[cnt + tmp][tmp] % mod * fac[tmp] % mod;
}
</bits>
LG8594 「KDOI-02」 Un仇的复
Analyse
Ce problème semble être une variante de problèmes de pavage ou de décomposition. L'idée est de considérer des sous-problèmes et de les combiner. Une approche par DP est envisagée, où f[i][j] pourrait représenter le nombre de façons de couvrir un rectangle de taille i x j. La solution utilise des formules combinatoires, notamment le principe d'inclusion-exclusion et des coefficients binomiaux pour gérer les contraintes. La formule finale ressemble à une somme complexe de termes impliquant des combinaisons.
Solution
#include <bits>
#define mod 998244353
using namespace std;
const int N = 40000005;
int qpow(int a, int b){
int res = 1;
while (b){
if (b & 1)
res = 1ll * res * a % mod;
a = 1ll * a * a % mod;
b >>= 1;
}
return res;
}
int fac[N], inv[N];
long long C(int x, int y){
if (y < 0 || y > x) return 0;
return 1ll * inv[y] * inv[x - y] % mod * fac[x] % mod;
}
int n, k;
int main(){
int tmp = 40000000;
fac[0] = 1;
for (int i = 1; i <= tmp; i++){
fac[i] = 1ll * fac[i - 1] * i % mod;
}
inv[tmp] = qpow(fac[tmp],mod - 2);
for (int i = tmp - 1; i >= 0; i--){
inv[i] = 1ll * inv[i + 1] * (i + 1) % mod;
}
cin >> n >> k;
int ans = 0;
for (int i = 1; i <= k; i++){
for (int j = 0; j <= k && k - j - 2 * i >= 0; j++){
if (2 * (n - i - j) < 0 || k - j - 2 * i < 0 || n - j - 1 < 0 || 2 * (n - i - j) < k - j - 2 * i || j + 1 < i || n - j - 1 < i - 1)
continue;
ans = (ans + C(2 * n - 2 * i - 2 * j, k - j - 2 * i) * C(j + 1, i) % mod * C(n - j - 1, i - 1) % mod) % mod;
}
}
cout << (ans + (n == k)) % mod;
}
</bits>
LG4141 L'objet disparu
Analyse
Ce problème est inversé : trouver l'état initial à partir du résultat. La DP est utilisée pour modéliser le processus. f[i][0] représente le nombre de configurations pour une capacité i sans l'objet disparu. f[i][1] représente le nombre de configurations pour une capacité i avec un objet supprimé. La transition pour f[j][1] est f[j][0] - f[j - w_i][1] pour j >= w_i. Pour j < w_i, f[j][1] = f[j][0] mod 10. Le modulo 10 est utilisé pour ne considérer que le dernier chiffre. Une étape de précalcul est également nécessaire.
Solution
#include <bits>
#define int long long
using namespace std;
const int N = 2005;
int n, m, w[N], f[N][2];
signed main(){
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> w[i];
f[0][0] = 1;
for (int i = 1; i <= n; i++){
for (int j = m; j >= w[i]; j--){
f[j][0] = (f[j][0] + f[j - w[i]][0]) % 10;
}
}
for (int i = 1; i <= n; i++){
for (int j = 0; j <= m; j++){
f[j][1] = f[j][0];
}
for (int j = w[i]; j <= m; j++){
f[j][1] = (f[j][1] - f[j - w[i]][1] + 10) % 10;
}
for (int j = 1; j <= m; j++){
cout << f[j][1] % 10;
}
cout << '\n';
}
}
</bits>
LG13349 「ZYZ 2025」 Séquence de nombres naturels
Analyse
Le problème demande de trouver le nombre de séquences naturelles satisfaisant certaines conditions, notamment b_x = y. Cette condition peut être transformée en l'exigence que b_x = 0 en soustrayant y * a_x des bornes de l'intervalle. Pour le cas simplifié où l=r=V, le problème sans la contrainte b_x=0 ressemble à un problème de sac à dos complet. Pour gérer la contrainte b_x=0, le principe d'inclusion-exclusion généralisé est utilisé. En combinant ces approches, une relation de récurrence pour le DP est dérivée. Pour le cas général l=r, des sommes préfixées sont utilisées.
Solution
#include <bits>
#define mod 998244353
using namespace std;
const int N = 3005;
int n, q, l, r, k, op, x, y, a[N << 1], f[N << 1];
void add(int &x, int y){
x += y;
if (x >= mod)
x -= mod;
}
void reduce(int &x, int y){
x -= y;
if (x < 0)
x += mod;
}
int calc(int l, int r){
if (r < 0) return 0;
if (l < 0) l = 0;
return (f[r] - (l > 0 ? f[l - 1] : 0) + mod) % mod;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> q;
f[0] = 1;
for (int i = 1; i <= n; i++){
cin >> a[i];
for (int j = a[i]; j <= 5000; j++)
add(f[j], f[j - a[i]]);
}
for (int i = 1; i <= 5000; i++)
add(f[i], f[i - 1]);
while (q--){
vector<int> tmp;
cin >> l >> r >> k;
for (int i = 1; i <= k; i++){
cin >> x >> y;
tmp.push_back(a[x]);
l -= a[x] * y;
r -= a[x] * y;
}
if (r < 0){
cout << 0 << '\n';
continue;
}
if (l < 0)
l = 0;
int m = tmp.size(), ans = 0;
for (int i = 0; i < (1 << m); i++){
int tot = 0;
for (int j = 0; j < m; j++){
if ((i >> j) & 1){
add(tot, tmp[j]);
}
}
if (__builtin_popcount(i) % 2 == 0)
add(ans, calc(l - tot, r - tot));
else
reduce(ans, calc(l - tot, r - tot));
}
cout << ans << '\n';
}
}
</int></bits>
La session de résolution d'exercices est terminée. Aucune nouvelle compétence significative n'a été acquise, mais la pratique a été effectuée.