1005.md (3526B)
1 Source: https://codeforces.com/blog/entry/60511 2 3 Tutorial is loading... 4 5 **Code in C++ for details** 6 7 ``` 8 int n; 9 cin >> n; 10 vector<int> a; 11 int p = -1; 12 forn(i, n) { 13 int x; 14 cin >> x; 15 if (x == 1 && p != -1) 16 a.push_back(p); 17 p = x; 18 } 19 a.push_back(p); 20 cout << a.size() << endl; 21 for (int i: a) 22 cout << i << " "; 23 ``` 24 25 Tutorial is loading... 26 27 **Code in C++ for details** 28 29 ``` 30 string s, t; 31 cin >> s >> t; 32 int w = 0; 33 while (true) { 34 int i = s.length() - w - 1; 35 int j = t.length() - w - 1; 36 if (i >= 0 && j >= 0 && s[i] == t[j]) 37 w++; 38 else 39 break; 40 } 41 cout << s.length() + t.length() - 2 * w << endl; 42 ``` 43 44 Tutorial is loading... 45 46 **Code in C++ for details** 47 48 ``` 49 int n; 50 cin >> n; 51 vector<int> a(n); 52 map<int,int> c; 53 forn(i, n) { 54 cin >> a[i]; 55 c[a[i]]++; 56 } 57 int ans = 0; 58 forn(i, n) { 59 bool ok = false; 60 forn(j, 31) { 61 int x = (1 << j) - a[i]; 62 if (c.count(x) && (c[x] > 1 || (c[x] == 1 && x != a[i]))) 63 ok = true; 64 } 65 if (!ok) 66 ans++; 67 } 68 cout << ans << endl; 69 ``` 70 71 Tutorial is loading... 72 73 **Code in C++ for details** 74 75 ``` 76 string s; 77 cin >> s; 78 int n = s.length(); 79 80 int r = 0; 81 vector<int> fin(3, -1); 82 fin[0] = 0; 83 84 vector<int> z(n + 1); 85 for (int i = 1; i <= n; i++) { 86 r = (r + s[i - 1] - '0') % 3; 87 z[i] = z[i - 1]; 88 if (fin[r] != -1) 89 z[i] = max(z[i], z[fin[r]] + 1); 90 fin[r] = i; 91 } 92 93 cout << z[n] << endl; 94 ``` 95 96 Tutorial is loading... 97 98 **Code in C++ for details** 99 100 ``` 101 int n, m; 102 cin >> n >> m; 103 vector<int> p(n); 104 forn(i, n) 105 cin >> p[i]; 106 map<int,int> c; 107 c[0] = 1; 108 bool has = false; 109 int sum = 0; 110 long long ans = 0; 111 for (int r = 0; r < n; r++) { 112 if (p[r] < m) 113 sum--; 114 else if (p[r] > m) 115 sum++; 116 117 if (p[r] == m) 118 has = true; 119 if (has) 120 ans += c[sum] + c[sum - 1]; 121 else 122 c[sum]++; 123 } 124 cout << ans << endl; 125 ``` 126 127 Tutorial is loading... 128 129 **Code in C++ for details** 130 131 ``` 132 long long greaterCount(int m) { 133 vector<int> s(2 * n + 1); 134 int sum = n; 135 long long result = 0; 136 s[sum] = 1; 137 long long add = 0; 138 forn(i, n) { 139 if (a[i] < m) 140 sum--, add -= s[sum]; 141 else 142 add += s[sum], sum++; 143 result += add; 144 s[sum]++; 145 } 146 return result; 147 } 148 149 cin >> n >> m; 150 a = vector<int>(n); 151 forn(i, n) 152 cin >> a[i]; 153 cout << greaterCount(m) - greaterCount(m + 1) << endl; 154 ``` 155 156 Tutorial is loading... 157 158 **Code in C++ for details** 159 160 ``` 161 int n, m, k; 162 cin >> n >> m >> k; 163 vector<vector<int>> g(n); 164 vector<int> a(m), b(m); 165 forn(i, m) { 166 cin >> a[i] >> b[i]; 167 a[i]--, b[i]--; 168 g[a[i]].push_back(b[i]); 169 g[b[i]].push_back(a[i]); 170 } 171 172 queue<int> q; 173 q.push(0); 174 vector<int> d(n, INT_MAX); 175 d[0] = 0; 176 177 while (!q.empty()) { 178 int u = q.front(); 179 q.pop(); 180 for (int v: g[u]) 181 if (d[v] == INT_MAX) { 182 d[v] = d[u] + 1; 183 q.push(v); 184 } 185 } 186 187 vector<vector<int>> inc(n); 188 forn(i, m) { 189 if (d[a[i]] + 1 == d[b[i]]) 190 inc[b[i]].push_back(i); 191 if (d[b[i]] + 1 == d[a[i]]) 192 inc[a[i]].push_back(i); 193 } 194 195 vector<int> f(n); 196 vector<string> result; 197 198 forn(i, k) { 199 string s(m, '0'); 200 for (int j = 1; j < n; j++) 201 s[inc[j][f[j]]] = '1'; 202 result.push_back(s); 203 204 bool ok = false; 205 for (int j = 1; j < n; j++) 206 if (f[j] + 1 < inc[j].size()) { 207 ok = true; 208 f[j]++; 209 break; 210 } else 211 f[j] = 0; 212 if (!ok) 213 break; 214 } 215 216 cout << result.size() << endl; 217 forn(i, result.size()) 218 cout << result[i] << endl; 219 ```