うーん
A. Sonya and Queries
問題概要
空の多重集合に対し, 個のクエリが与えられるので処理せよ.
- を 個集合に加える.
- を 個集合から消す.
- 集合の中で, パターン に一致する値の個数を数えて出力する. パターンは値を 進表記したときの各桁の偶奇を指定している.
解法
のパターンは 通りしかない. また, が定まれば が一意に定まるのは明らか.
クエリ と のときに, どの にマッチするかを見て, 対応するところに加えると良い.
ビットで各桁の偶奇を保存すると楽.
ソース
#include <bits/stdc++.h> using namespace std; typedef long long int64; int sz[1 << 20]; int main() { int T; cin >> T; while(T--) { char t; int64 S; cin >> t >> S; int bit = 0; for(int i = 0; i < 20; i++) { bit |= (S % 2) << i; S /= 10; } if(t == '+') ++sz[bit]; else if(t == '-') --sz[bit]; else cout << sz[bit] << endl; } }
B. Searching Rectangles
問題概要
のセルからなる 次元グリッドがある.
枚の長方形のシートがグリッド上のどこかに置かれている. シートはセルの縁にそっていて, 枚のシートが重なり合うことはない.
長方形領域を指定して, 領域が何枚のシートを内包するかを質問することができる. 回以下の質問で, このシートの位置を特定せよ.
解法
二分探索というのはすぐ分かるけどデバッグ難しい.
まず, シートが 枚含まれていると大変なので, どのあたりに 枚あるかを見つける. 枚のシートの位置関係を考えると, グリッドをある列か行で直線で分断することが可能. この位置を適当に二分探索して見つける.
分断したら, それぞれのシートを二分探索で見つけるだけ.
ソース
#include <bits/stdc++.h> using namespace std; struct Rect { int x1, y1, x2, y2; }; int N; map< tuple< int, int, int, int >, int > dp; int check(int x1, int y1, int x2, int y2) { if(dp.count(tie(x1, y1, x2, y2))) return (dp[tie(x1, y1, x2, y2)]); cout << "?" << " " << x1 << " " << y1 << " " << x2 << " " << y2 << endl; int k; cin >> k; return (dp[tie(x1, y1, x2, y2)] = k); } Rect getRect(int x1, int y1, int x2, int y2) { Rect rect; int left = x1, right = x2; while(right - left > 0) { int mid = (left + right) / 2; if(check(x1, y1, mid, y2) == 0) left = mid + 1; else right = mid; } rect.x2 = left; left = y1, right = y2; while(right - left > 0) { int mid = (left + right) / 2; if(check(x1, y1, x2, mid) == 0) left = mid + 1; else right = mid; } rect.y2 = left; left = x1, right = x2; while(right - left > 0) { int mid = (left + right + 1) / 2; if(check(mid, y1, x2, y2) == 0) right = mid - 1; else left = mid; } rect.x1 = left; left = y1, right = y2; while(right - left > 0) { int mid = (left + right + 1) / 2; if(check(x1, mid, x2, y2) == 0) right = mid - 1; else left = mid; } rect.y1 = left; return (rect); } int main() { Rect r1, r2; cin >> N; int left = 1, right = N; while(right - left > 0) { int mid = (left + right) / 2; if(check(1, 1, mid, N) == 0) left = mid + 1; else right = mid; } if(check(1, 1, left, N) == 1 && check(left + 1, 1, N, N) == 1) { r1 = getRect(1, 1, left, N); r2 = getRect(left + 1, 1, N, N); } else { left = 1, right = N; while(right - left > 0) { int mid = (left + right) / 2; if(check(1, 1, N, mid) == 0) left = mid + 1; else right = mid; } r1 = getRect(1, 1, N, left); r2 = getRect(1, left + 1, N, N); } cout << "! " << r1.x1 << " " << r1.y1 << " " << r1.x2 << " " << r1.y2 << " " << r2.x1 << " " << r2.y1 << " " << r2.x2 << " " << r2.y2 << endl; }
C. Sonya and Problem Wihtout a Legend
問題概要
長さ の数列 がある. 各要素を増減して狭義増加部分列にしたい. 要素を するごとにコストが かかる. 最小コストを求めよ.
解法
典型っぽい. じょうしょうツリーなのでそれを貼るだけ(乱暴.
まず, 狭義増加(より大きい) だと大変なので 広義増加(以上) として考える. これは, とすればよい.
あとは動的計画法でこの問題を解く.
番目の要素を値 にするときの最小コスト
とすれば, この更新は, . は座標圧縮すれば高々 個しかないので, .
ソース
#include <bits/stdc++.h> using namespace std; typedef long long int64; const int64 INF = 1LL << 60; int main() { int N, A[3000]; vector< int > nums; int64 dp[2][3000]; cin >> N; for(int i = 0; i < N; i++) { cin >> A[i]; A[i] -= i; nums.push_back(A[i]); } sort(begin(nums), end(nums)); nums.erase(unique(begin(nums), end(nums)), end(nums)); fill_n(*dp, 2 * 3000, INF); auto& now = dp[0], & nxt = dp[1]; now[0] = 0; for(int i = 0; i < N; i++) { int64 small = INF; for(int j = 0; j < nums.size(); j++) { small = min(small, now[j]); nxt[j] = small + abs(A[i] - nums[j]); } swap(now, nxt); } cout << *min_element(now, now + nums.size()) << endl; }