#include <bits/stdc++.h> using namespace std; map<string, bool> tab; map<string, int> score; bool IsGood(string s){ int c = (int) s.size(); string s1; for(int i = 1; i < c; i++){ if(s[i] == s[i-1]){ s1 = ""; for(int j = 0; j < i-1; j++) s1 += s[j]; if(s[i] == 'C') s1 += 'Z'; else s1 += 'C'; for(int j = i+1; j < c; j++) s1 += s[j]; if(tab.count(s1)) return 1; } } return 0; } void Dobre(int n){ tab["C"] = 1; tab["Z"] = 1; string s; int ilosc; for(int i = 2; i <= n; i++){ ilosc = (1 << i); for(int j = 0; j < ilosc; j++){ s = ""; for(int k = 0; k < i; k++){ if(j&(1 << k)) s += 'C'; else s += 'Z'; } if(IsGood(s)) tab[s] = 1; } } } int Opcje(string s, int n){ string s1; int ilosc = (1 << n), c = (int) s.size(), k, wynik = 0; for(int i = 0; i < ilosc; i++){ s1 = s; k = 0; for(int j = 0; j < c; j++){ if(s[j] == 'N'){ if(i&(1 << k)) s1[j] = 'C'; else s1[j] = 'Z'; k++; } } if(tab.count(s1)) wynik++; } score[s] = wynik; return wynik; } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n, q; cin >> n >> q; string termion; cin >> termion; int amountN = 0; Dobre(n); for(int i = 0; i < n; i++){ if(termion[i] == 'N') amountN++; } cout << Opcje(termion, amountN) << '\n'; char z; int a; for(int i = 0; i < q; i++){ cin >> a >> z; a--; if(termion[a] == 'N' && z != 'N') amountN--; else if(z == 'N' && termion[a] != 'N') amountN++; termion[a] = z; if(score.count(termion)) cout << score[termion] << '\n'; else cout << Opcje(termion, amountN) << '\n'; } return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 | #include <bits/stdc++.h> using namespace std; map<string, bool> tab; map<string, int> score; bool IsGood(string s){ int c = (int) s.size(); string s1; for(int i = 1; i < c; i++){ if(s[i] == s[i-1]){ s1 = ""; for(int j = 0; j < i-1; j++) s1 += s[j]; if(s[i] == 'C') s1 += 'Z'; else s1 += 'C'; for(int j = i+1; j < c; j++) s1 += s[j]; if(tab.count(s1)) return 1; } } return 0; } void Dobre(int n){ tab["C"] = 1; tab["Z"] = 1; string s; int ilosc; for(int i = 2; i <= n; i++){ ilosc = (1 << i); for(int j = 0; j < ilosc; j++){ s = ""; for(int k = 0; k < i; k++){ if(j&(1 << k)) s += 'C'; else s += 'Z'; } if(IsGood(s)) tab[s] = 1; } } } int Opcje(string s, int n){ string s1; int ilosc = (1 << n), c = (int) s.size(), k, wynik = 0; for(int i = 0; i < ilosc; i++){ s1 = s; k = 0; for(int j = 0; j < c; j++){ if(s[j] == 'N'){ if(i&(1 << k)) s1[j] = 'C'; else s1[j] = 'Z'; k++; } } if(tab.count(s1)) wynik++; } score[s] = wynik; return wynik; } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n, q; cin >> n >> q; string termion; cin >> termion; int amountN = 0; Dobre(n); for(int i = 0; i < n; i++){ if(termion[i] == 'N') amountN++; } cout << Opcje(termion, amountN) << '\n'; char z; int a; for(int i = 0; i < q; i++){ cin >> a >> z; a--; if(termion[a] == 'N' && z != 'N') amountN--; else if(z == 'N' && termion[a] != 'N') amountN++; termion[a] = z; if(score.count(termion)) cout << score[termion] << '\n'; else cout << Opcje(termion, amountN) << '\n'; } return 0; } |