Problème T1 : F
Raisonnement
Comme les tableaux a et b sont liés par une relation biunivoque, le nombre de candidats possibles est au plus n. Pour chaque valeur candidate, on vérifie en un seul parcours si elle réalise une correspondance parfaite entre a et b. On peut utiliser une tible de hachage, un map ou un multiset pour stocker les éléments de b et les retirer au fur et à mesure.
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 2000 + 5;
int n, top, pile[MAXN * MAXN], a[MAXN], b[MAXN];
unordered_multiset<int> bag;
bool verifie(int x) {
bag.clear();
for (int i = 0; i < n; ++i) bag.insert(b[i]);
for (int i = 0; i < n; ++i) {
int besoin = x ^ a[i];
auto it = bag.find(besoin);
if (it == bag.end()) return false;
bag.erase(it);
}
return true;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for (int i = 0; i < n; ++i) cin >> a[i];
for (int i = 0; i < n; ++i) cin >> b[i];
for (int i = 0; i < n; ++i) {
int cand = a[0] ^ b[i];
if (verifie(cand)) pile[top++] = cand;
}
sort(pile, pile + top);
top = unique(pile, pile + top) - pile;
cout << top << "\n";
for (int i = 0; i < top; ++i) cout << pile[i] << "\n";
return 0;
}
Problème T2 : S
Raisonnement
Une approche naïve (parcours direct) ne donne que 10 points, le parcours inverse 50, et la combinaison des deux 60 – malheureusement je n’ai obtenu que 10. La solution optimale utilise la programmation dynamique. À l’intérieur d’une couleur, l’ordre relatif ne change jamais. Si la dernière position de la couleur i est j, le nombre d’échanges est j − i − (nombre de cette couleur déjà placés). La DP construit la séquence finale. On définit dp[i][j][k][last] : après i éléments, j R, k G, et la dernière couleur est last (0=R,1=G,2=Y). On peut réduire une dimension car le nombre de Y se déduit.
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1LL << 60;
const int MAXN = 405;
int n, cnt[3][MAXN], pos[3][MAXN];
ll dp[2][MAXN][MAXN][3];
char s[MAXN];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> (s + 1);
// Initialisation des positions et des compteurs
for (int i = 0; i < 3; ++i) pos[i][0] = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 0; j < 3; ++j) cnt[j][i] = cnt[j][i - 1];
int c;
if (s[i] == 'G') c = 1;
else if (s[i] == 'Y') c = 2;
else c = 0;
++cnt[c][i];
pos[c][cnt[c][i]] = i;
}
// Vérification de faisabilité
for (int i = 0; i < 3; ++i)
if (cnt[i][n] > (n + 1) / 2) { cout << -1; return 0; }
// Initialisation DP
memset(dp, 0x3f, sizeof(dp));
if (cnt[0][n]) dp[1][1][0][0] = 0;
if (cnt[1][n]) dp[1][0][1][1] = 0;
if (cnt[2][n]) dp[1][0][0][2] = 0;
for (int i = 1; i < n; ++i) {
int cur = i & 1, nxt = cur ^ 1;
for (int j = 0; j <= cnt[0][n]; ++j)
for (int k = 0; k <= cnt[1][n]; ++k)
fill(dp[nxt][j][k], dp[nxt][j][k] + 3, INF);
int maxR = min(i, cnt[0][n]);
for (int j = 0; j <= maxR; ++j) {
int maxG = min(i - j, cnt[1][n]);
for (int k = 0; k <= maxG; ++k) {
int y = i - j - k;
if (y < 0) continue;
for (int last = 0; last < 3; ++last) {
ll val = dp[cur][j][k][last];
if (val == INF) continue;
// Ajout d'un R
if (last && j < cnt[0][n]) {
int p = pos[0][j + 1];
ll add = max(0LL, k - cnt[1][p]) + max(0LL, y - cnt[2][p]);
dp[nxt][j + 1][k][0] = min(dp[nxt][j + 1][k][0], val + add);
}
// Ajout d'un G
if (last != 1 && k < cnt[1][n]) {
int p = pos[1][k + 1];
ll add = max(0LL, j - cnt[0][p]) + max(0LL, y - cnt[2][p]);
dp[nxt][j][k + 1][1] = min(dp[nxt][j][k + 1][1], val + add);
}
// Ajout d'un Y
if (last != 2 && y < cnt[2][n]) {
int p = pos[2][y + 1];
ll add = max(0LL, j - cnt[0][p]) + max(0LL, k - cnt[1][p]);
dp[nxt][j][k][2] = min(dp[nxt][j][k][2], val + add);
}
}
}
}
}
ll ans = INF;
for (int i = 0; i < 3; ++i)
ans = min(ans, dp[n & 1][cnt[0][n]][cnt[1][n]][i]);
cout << ans << "\n";
return 0;
}
Problème T3 : Y
Raisonnement
La solution utilise une DP sur les éléments du tableau s. On calcule deux séries de valeurs : une avec base = 1 et une avec base = 0. On combine ensuite les résultats via le principe d’inclsuion-exclusion. Les fonctions g1 et g2 sont des sommes partielles utiles pour la mise à jour linéaire. Les constantes modulaires sont précalculées.
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;
const int MAXN = 1e6 + 5;
int n, s[MAXN];
ll dp[MAXN][2], inv2, inv6;
ll power(ll x, ll y) {
ll res = 1;
while (y) {
if (y & 1) res = res * x % MOD;
x = x * x % MOD;
y >>= 1;
}
return res;
}
inline ll sum1(ll x) { x %= MOD; return x * (x + 1) % MOD * inv2 % MOD; }
inline ll sum2(ll x) { x %= MOD; return x * (x + 1) % MOD * (2 * x + 1) % MOD * inv6 % MOD; }
ll solve(int base, int lim) {
memset(dp, 0, sizeof(dp));
dp[1][0] = base;
dp[1][1] = base ^ 1;
for (int i = 1; i <= n; ++i) {
int x = s[i] - lim;
dp[i + 1][0] = (dp[i + 1][0] + dp[i][0] * sum1(x) % MOD + dp[i][1] * (x + 1) % MOD) % MOD;
x += lim;
dp[i + 1][1] = (dp[i + 1][1] + dp[i][0] * (x * sum1(x) % MOD - sum2(x) + MOD) % MOD + dp[i][1] * sum1(x) % MOD) % MOD;
}
return dp[n + 1][base ^ 1];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for (int i = 1; i <= n; ++i) cin >> s[i];
inv2 = power(2, MOD - 2);
inv6 = power(6, MOD - 2);
ll ans = (solve(1, 0) + solve(0, 0) - solve(1, 1) - solve(0, 1) + 2LL * MOD) % MOD;
cout << ans << "\n";
return 0;
}
Problème T4 : O
Raisonnement
Solution heuristique inspirée de zxb (les données de test sont particulièrement peu exigeantes : presque monotones). On maintient une pile décroissante (du bas vers le haut). On balaie la pile à chaque pas pour déterminer quand une flamme changera. Ensuite, à chaque instant, on applique les modifications directement. Un arbre de Fenwick permet de maintenir la somme courante.
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 2e5 + 5;
int n, m, pos = 1, top;
int pile[MAXN], s[MAXN];
ll ans[MAXN];
vector<pair<int,int>> modifs[MAXN];
struct Query {
int id, t, l, r;
} q[MAXN];
struct BIT {
ll tree[MAXN];
inline int lowbit(int x) { return x & -x; }
inline void add(int x, ll val) {
for (; x <= n; x += lowbit(x)) tree[x] += val;
}
inline ll sum(int x) {
ll res = 0;
for (; x; x -= lowbit(x)) res += tree[x];
return res;
}
inline ll query(int l, int r) { return sum(r) - sum(l - 1); }
} bit;
bool cmp(const Query &a, const Query &b) { return a.t < b.t; }
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
// Initialisation et construction des modifications
for (int i = 1; i <= n; ++i) {
cin >> s[i];
bit.add(i, s[i]);
while (top && s[pile[top]] <= s[i]) --top;
for (int j = 1; j <= top; ++j)
modifs[i - pile[j]].push_back({i, s[pile[j]]});
pile[++top] = i;
}
// Lecture des requêtes
for (int i = 1; i <= m; ++i) {
int t, l, r;
cin >> t >> l >> r;
q[i] = {i, min(t, n), l, r};
}
sort(q + 1, q + m + 1, cmp);
// Traitement des instants et réponse aux questions
for (int t = 1; t <= n && pos <= m; ++t) {
for (auto &p : modifs[t]) {
int idx = p.first;
ll newVal = p.second;
bit.add(idx, newVal - s[idx]);
s[idx] = newVal;
}
while (pos <= m && q[pos].t == t) {
ans[q[pos].id] = bit.query(q[pos].l, q[pos].r);
++pos;
}
}
for (int i = 1; i <= m; ++i) cout << ans[i] << "\n";
return 0;
}