待补：C.Community Service/D.Largest Remainder
A. Ice Cream直接 O ( 1 ) O(1) O(1)计算即可。
#include #define int long long using namespace std; inline void solve(){ int n, x, y; cin >> x >> y >> n; int by = (n / (x + y)) * x * 3 + (min(n % (x + y), x) * 3); cout << by << endl; } signed main(){ int t = 0; cin >> t; while(t--) solve(); return 0; }
B.Maximum Sub-Reverse Matching
发现 n ≤ 1000 n \leq 1000 n≤1000，那么考虑 O ( n 2 ) O(n^2) O(n2)枚举所有区间，对每个区间计算匹配数目并更新即可。
#include #define int long long #define endl '\n' using namespace std; inline void solve(){ int n = 0; cin >> n; string s1, s2; cin >> s1 >> s2; int ans1 = 0, ans2 = 0, ansl = 0, ansr = 0; for(int i = 0; i < n; i++) ans1 += (s1[i] == s2[i] ? 1 : 0); for(int l = 0; l < n; l++){ for(int r = l; r < n; r++){ int cnt = 0; for(int i = 0; i < l; i++) cnt += (s1[i] == s2[i] ? 1 : 0); for(int i = r + 1; i < n; i++) cnt += (s1[i] == s2[i] ? 1 : 0); for(int ll = l, rr = r; rr >= l; ll++, rr--){ if(s1[ll] == s2[rr]) cnt++; } if(cnt > ans2) ans2 = cnt, ansl = l, ansr = r; else if(cnt == ans2){ if(r - l < ansr - ansl) ansl = l, ansr = r; } } } cout << ans1 << ' ' << ans2 << ' ' << ansl + 1 << ' ' << ansr + 1 << endl; } signed main(){ ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0); int t = 0; cin >> t; while(t--) solve(); return 0; }
F. What a Colorful Wall
考虑倒序染色，发现是二维染色，于是考虑扫描线+倒序染色，对于染色的维护可以用并查集维护。
对于每行初始化一个并查集，然后倒序染色，染色时对该行的列进行合并即可。
#include #define int long long using namespace std; const int N = 1e7 + 10; vector<int> ax, ay; struct node{ int x1, y1, x2, y2, col; }a[N]; struct UnionFind { vector<int> fa; UnionFind(int n) : fa(n) { std::iota(fa.begin(), fa.end(), 0); } int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); } bool merge(int x, int y){ int px = find(x), py = find(y); if (px == py) return false; else fa[px] = py; return true; } }; const int M = 4010; bool book[N]; inline void solve(){ int n = 0; cin >> n; for(int i = 1; i <= n; i++){ int x1, y1, x2, y2, color; scanf("%lld %lld %lld %lld %lld", &x1, &y1, &x2, &y2, &color); ax.emplace_back(x1), ax.emplace_back(x2); ay.emplace_back(y1), ay.emplace_back(y2); a[i] = node{x1, y2, x2, y1, color}; } std::function<int(vector<int> &, int)> find = [&](vector<int> v, int x){ return lower_bound(v.begin(), v.end(), x) - v.begin(); }; sort(ax.begin(), ax.end()); sort(ay.begin(), ay.end()); ax.erase(unique(ax.begin(), ax.end()), ax.end()); ay.erase(unique(ay.begin(), ay.end()), ay.end()); for(int i = 1; i <= n; i++){ int x1 = find(ax, a[i].x1), y1 = find(ay, a[i].y1); int x2 = find(ax, a[i].x2), y2 = find(ay, a[i].y2); a[i] = node{x1, y1, x2, y2, a[i].col}; //cout << a[i].x1 << ' ' << a[i].y1 << ' ' << a[i].x2 << ' ' << a[i].y2 << endl; } int maxc = ax.size(); for(int i = 0; i <= maxc; i++){ UnionFind uf(maxc * 2 + 1); for(int j = n; j >= 1; j--){ if(a[j].x1 <= i && i < a[j].x2){ int k = uf.find(a[j].y1); while(k < a[j].y2){ uf.merge(k, k + 1); book[a[j].col] = 1; k = uf.find(k); } } } } int ans = 0; for(int i = 0; i < M - 5; i++) if(book[i] == 1) ans++; printf("%lld\n", ans); } signed main(){ solve(); return 0; }
J.Transportation Network
一道阅读理解题。不难发现构造方式
那么按照以上方式计算即可。
#include #define int long long #define ull unsigned long long using namespace std; inline void solve(){ int n, s, p; cin >> n >> s >> p; for(int i = 1, k; i <= s; i++) cin >> k; int ans = ((n - p) * p + (n - 1) * (s - 1) + (n - 1) * (p - s) * 2 + (n - 1) * (n - p - 1)) * 2; cout << ans << endl; } signed main(){ ios_base::sync_with_stdio(false); int t = 1; cin >> t; while(t--) solve(); return 0; }
M.Escaping the Foggy Forest
模拟+签到，直接枚举方向即可，注意边界算0
#include #define int long long #define endl '\n' using namespace std; const int N = 110; int g[N][N]; struct node{ int x, y; const bool operator< (const node &a) const { return x < a.x || x == a.x && y < a.y; } }ans[100010]; const int dx[] = {0, 1, 0, -1}; const int dy[] = {1, 0, -1, 0}; inline void solve(){ int m, n; cin >> m >> n; for(int i = 1; i <= m; i++){ for(int j = 1; j <= n; j++) cin >> g[i][j]; } int s, f, r; cin >> s >> f >> r; int cnt = 0; for(int i = 1; i <= m; i++){ for(int j = 1; j <= n; j++){ if(g[i][j] != s) continue; for(int id = 0; id < 4; id++){ int fx = i + dx[id], fy = j + dy[id]; int rx = i + dx[(id + 1) % 4], ry = j + dy[(id + 1) % 4]; if(g[fx][fy] == f && g[rx][ry] == r){ ans[++cnt] = node{i, j}; break; } } } } sort(ans + 1, ans + 1 + cnt); for(int i = 1; i <= cnt; i++) cout << ans[i].x - 1 << ' ' << ans[i].y - 1 << '\n'; } signed main(){ solve(); return 0; }
