B. Mine Sweeper II
#include <bits/stdc++.h> using namespace std; const int N = 1e3 + 10; int n, m; char s1[N][N], s2[N][N], s3[N][N]; int solve(char sa[N][N], char sb[N][N]) { int cnt = n * m; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cnt -= sa[i][j] == sb[i][j]; return cnt; } int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) scanf("%s", s1[i] + 1); for (int i = 1; i <= n; i++) scanf("%s", s2[i] + 1); for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) s3[i][j] = (s1[i][j] == '.' ? 'X' : '.'); if (solve(s1, s2) <= n * m / 2) { for (int i = 1; i <= n; i++) puts(s1[i] + 1); return 0; } for (int i = 1; i <= n; i++) puts(s3[i] + 1); return 0; }
G. Fibonacci
若想让x * y为偶,只需其中一个为偶数。观察斐波那契数列,发现每3个数中就会有一个数是偶数。定义 odd 记录有几组这样的数,even 记录余下数(奇数)。 从第一组往后各组中的奇数能匹配的偶数成等差数列,求和即为 odd * (odd + 1) / 2。 每组中两个奇数匹配的偶数数量是相同的 * 2,所以奇数向后能匹配的偶数就有 odd * (odd + 1)。 同样偶数与其后的奇数匹配的情况就是 odd * even + (odd - 1) * 3 * odd / 2。#include <bits/stdc++.h> using namespace std; typedef long long ll; int main() { ll n; cin >> n; ll even = n % 3, odd = n / 3; ll ans = odd * (odd + 1) + odd * even + (odd - 1) * 3 * odd / 2; cout << ans; return 0; }
M. Gitignore
把不能忽略的文件路径记录一下,再从可以忽略的文件里遍历,遇到可以忽略的文件就删除,后面遇到相同路径的文件就不用操作了。
#include <bits/stdc++.h> using namespace std; typedef long long ll; map<string, ll> q, vis; string a[1001]; int main() { int cass; for (cin >> cass; cass; cass--) { ll m, n; cin >> n >> m; vis.clear(); q.clear(); for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = 1; i <= m; i++) { string x, y; cin >> x; for (int j = 0; j < x.size(); j++) { y += x[j]; if (x[j] == '/') vis[y] = 1; } } ll s = 0; for (int i = 1; i <= n; i++) { string x; int flag = 0; for (int j = 0; j < a[i].size(); j++) { x += a[i][j]; if (a[i][j] == '/') { if (q[x]) { flag = 1; break; } if (!vis[x]) { flag = q[x] = 1; s++; break; } } } s += !flag; } cout << s << "\n"; } return 0; }