AtCoder Beginner Contest 430
|
10
|
0
|
ABC,Atcoder,题解

725 字
|
3 分钟

A Candy Cookie Law

判断一下即可，注意没有 $spj$ ，犯法输出 $Yes$ ，没犯法输出 $No$ 。

 void solve() {
     int a, b, c, d;
     cin >> a >> b >> c >> d;
     if (c >= a && d >= b || c < a) {
         cout << "No" << "\n";
     } else {
         cout << "Yes" << "\n";
     }
 }

B Count Subgrid

暴力枚举每个 $m\times m$ 的方格即可，转化成二进制或者字符串去重，注意转化成二进制时范围会到 $2^{100}$ ，需要用 $int128$ 。

 void solve() {
     int n, m;
     cin >> n >> m;
     vector<vector<int>> g(n, vector<int>(n));
     for (int i = 0; i < n; ++i) {
         string s;
         cin >> s;
         for (int j = 0; j < n; ++j) {
             g[i][j] = (s[j] == '.' ? 0 : 1);
         }
     }
     vector<i128> st;
     for (int i = 0; i + m <= n; ++i) {
         for (int j = 0; j + m <= n; ++j) {
             i128 cur = 0;
             for (int k = i; k < i + m; ++k) {
                 for (int l = j; l < j + m; ++l) {
                     cur = (cur << 1) + g[k][l];
                 }
             }
             st.pb(cur);
         }
     }
     sort(all(st));
     st.erase(unique(all(st)), st.end());
     cout << st.size() << "\n";
 }

C Truck Driver

求关于 $a$ 和 $b$ 的前缀，对于每个起点 $i$ ，二分对于 $a$ 的个数合法的 $r1$ 和对于 $b$ 的个数合法的 $r2$ ，二者相减就是合法的种数。

 void solve() {
     int n, a, b;
     cin >> n >> a >> b;
     string s;
     cin >> s;
     vector<int> sa(n + 1), sb(n + 1);
     for (int i = 1; i <= n; ++i) {
         sa[i] = sa[i - 1] + (s[i - 1] == 'a');
         sb[i] = sb[i - 1] + (s[i - 1] == 'b');
     }
     ll ans = 0;
     for (int i = 1; i <= n; ++i) {
         auto it1 = lower_bound(sa.begin() + i, sa.end(), sa[i - 1] + a);
         if (it1 == sa.end()) continue;
         int r1 = it1 - sa.begin();
 ​
         auto it2 = lower_bound(sb.begin() + i, sb.end(), sb[i - 1] + b);
         int r2;
         if (it2 == sb.end()) r2 = n + 1;
         else r2 = it2 - sb.begin();
 ​
         if (r1 <= r2 - 1) {
             ans += r2 - r1;
         }
     }
     cout << ans << "\n";
 }

D Neighbor Distance

每次插入一个新点 $x$ ，它只会影响自己和它相邻的两个点（前驱、后继）的最近距离。 因为别的点离它更远，不可能改变它们的最近邻。 所以我们用一个有序集合保存所有坐标，每次插入后只更新这三个点的 $d$​ 值，并维护全局和。

 void solve() {
     int n;
     cin >> n;
     vector<ll> a(n);
     for (int i = 0; i < n; ++i) cin >> a[i];
 ​
     set<ll> pos;
     unordered_map<ll, ll> d;
     pos.insert(0);
     d[0] = 0;
     ll S = 0;
 ​
     for (int i = 0; i < n; ++i) {
         ll x = a[i];
         auto it = pos.lower_bound(a[i]);
         bool f1 = (it != pos.end()), f2 = (it != pos.begin());
 ​
         auto pref = f2 ? prev(it) : pos.end();
 ​
         if (f2) {
             ll pred = *pref;
             ll old = d[pred];
             ll ppd = INF;
             if (pref != pos.begin()) {
                 auto pp = prev(pref);
                 ppd = pred - *pp;
             }
             ll npd = min(ppd, a[i] - pred);
             S += (npd - old);
             d[pred] = npd;
         }
 ​
         if (f1) {
             ll succ = *it;
             ll old = d[succ];
             ll nnd = INF;
             auto nit = next(it);
             if (nit != pos.end()) nnd = *nit - succ;
             ll nsd = min(nnd, succ - a[i]);
             S += (nsd - old);
             d[succ] = nsd;
         }
 ​
         ll l = f2 ? a[i] - *pref : INF;
         ll r = f1 ? *it - a[i] : INF;
         ll nxd = min(l, r);
         d[a[i]] = nxd;
         S += nxd;
         pos.insert(a[i]);
 ​
         cout << S << "\n";
     }
 }

E Shift String

先判断 $A$ 和 $B$ 的字符个数（0/1）是否相同，若不同直接输出 $-1$ 。

把 $A$ 拼成 $A+A$ ，在这个长度为 $2n$ 的字符串中查找模式 $B$ 。

找到的第一个匹配起始位置 $k$（且 $k < n$ ）就是最小左旋次数，若没有这样的匹配则输出 $-1$​ 。

 void solve() {
     string a, b;
     cin >> a >> b;
     int n = a.size();
     if (b.size() != n) {
         cout << -1 << "\n";
         return;
     }
 ​
     int ca[2] = {0, 0}, cb[2] = {0, 0};
     for (char c : a) ca[c - '0']++;
     for (char c : b) cb[c - '0']++;
     if (ca[0] != cb[0] || ca[1] != cb[1]) {
         cout << -1 << "\n";
         return;
     }
 ​
     string A = a + a;
     int m = n;
 ​
     vector<int> pi(m, 0);
     for (int i = 1; i < m; ++i) {
         int j = pi[i - 1];
         while (j > 0 && b[i] != b[j]) j = pi[j - 1];
         if (b[i] == b[j]) ++j;
         pi[i] = j;
     }
 ​
     int j = 0;
     int ans = -1;
 ​
     for (int i = 0; i < A.size(); ++i) {
         while (j > 0 && A[i] != b[j]) j = pi[j - 1];
         if (A[i] == b[j]) ++j;
         if (j == m) {
             int st = i - m + 1;
             if (st < n) {
                 ans = st;
                 break;
             }
             j = pi[j - 1];
         }
     }
 ​
     if (ans == -1) cout << -1 << "\n";
     else cout << ans << "\n";
 ​
 }

F Back and Forth Filling

对于每一个位置的数字，都可以求出它的最左位置 $mn$ 和最右位置 $mx$ ，使得它可以放在 $[mn,mx]$ 的任意一个位置。

  • $mn = 1+\text{左边连续的}l\text{的数量}+\text{右边连续的}r\text{的数量}$
  • $mn = n-\text{左边连续的}l\text{的数量}-\text{右边连续的}r\text{的数量}$

用差分数组统计统计每个位置被多少个区间覆盖即可。

 void solve() {
     int n;
     string s;
     cin >> n >> s;
 ​
     vector<int> lr(n + 1, 0), rl(n + 2, 0), ll(n + 1, 0), rr(n + 2, 0);
 ​
     for (int v = 2; v <= n; ++v) {
         if (s[v - 2] == 'R') lr[v] = lr[v - 1] + 1;
         else lr[v] = 0;
     }
 ​
     for (int v = n - 1; v >= 1; --v) {
         if (s[v - 1] == 'L') rl[v] = rl[v + 1] + 1;
         else rl[v] = 0;
     }
 ​
     for (int v = 2; v <= n; ++v) {
         if (s[v - 2] == 'L') ll[v] = ll[v - 1] + 1;
         else ll[v] = 0;
     }
 ​
     for (int v = n - 1; v >= 1; --v) {
         if (s[v - 1] == 'R') rr[v] = rr[v + 1] + 1;
         else rr[v] = 0;
     }
 ​
     vector<int> diff(n + 3, 0);
     for (int v = 1; v <= n; ++v) {
         int mn = 1 + lr[v] + rl[v];
         int mx = n - (rr[v] + ll[v]);
         diff[mn]++;
         diff[mx + 1] --;
     }
 ​
 ​
     vector<int> ans(n + 1, 0);
     int cur = 0;
     for (int i = 1; i <= n; ++i) {
         cur += diff[i];
         ans[i] = cur;
     }
 ​
     for (int i = 1; i <= n; ++i) {
         cout << ans[i] << " ";
     }
     cout << "\n";
 }

G Range Set Modifying Query

用线段树维护每个位置 $|S_i|$ ，节点保存区间最大值 $mx$ 和出现次数 $cnt$ ，支持区间加/减的懒标记。

对每个元素值 $x（1\cdots 60）$单独维护一个不相交的区间集合，表示哪些下标当前包含 $x$（区间合并/拆分，避免逐点操作）。

加 $x$ 到 $[L,R]$ ：先对线段树 $+1$ ，然后对与 $[L,R]$ 重叠的已有区间只撤销它们的交集（对交集区间做 $-1$ ），最后将这些区间与 $[L,R]$ 合并插回集合。

删 $x$ 从 $[L,R]$ ：找到与 $[L,R]$ 重叠的区间，对交集区间做 $-1$ ，并把被截断的左右残段重新插回集合（区间拆分）。

查询直接用线段树 $ask(L,R)$ 返回 $(mx,cnt)$ 即可。

 void solve() {
     int n, q;
     cin >> n >> q;
 ​
     SegTree<int> seg(n);
     vector<int> init(n + 1, 0);
     seg.build(init);
 ​
     vector<set<PII>> ones(maxn + 1);
 ​
     for (int i = 0; i < q; ++i) {
         int op; cin >> op;
         if (op == 1) {
             int l, r, x;
             cin >> l >> r >> x;
             if (l > r) continue;
             seg.update(l, r, Tag<int> {1});
             auto &S = ones[x];
             auto it = S.lower_bound({l + 1, -inf});
             if (it != S.begin()) {
                 --it;
                 if (it->se < l) ++it;
             }
             int nl = l, nr = r;
             vector<PII> del;
             while (it != S.end() && it->fi <= r) {
                 int a = it->fi, b = it->se;
                 int ovl = max(a, l), ovr = min(b, r);
                 if (ovl <= ovr) seg.update(ovl, ovr, Tag<int> { -1});
                 nl = min(nl, a);
                 nr = max(nr, b);
                 del.pb(*it);
                 ++it;
             }
             for (auto &p : del) S.erase(p);
             S.insert({nl, nr});
         }
         else if (op == 2) {
             int l, r, x; cin >> l >> r >> x;
             if (l > r) continue;
             auto &S = ones[x];
             auto it = S.lower_bound({l + 1, -inf});
             if (it != S.begin()) {
                 --it;
                 if (it->se < l) ++it;
             }
             vector<PII> del;
             vector<PII> add;
             while (it != S.end() && it->fi <= r) {
                 int a = it->fi, b = it->se;
                 int ovl = max(a, l), ovr = min(b, r);
                 if (ovl <= ovr) seg.update(ovl, ovr, Tag<int> { -1});
                 del.pb(*it);
                 if (a < ovl) add.pb({a, ovl - 1});
                 if (ovr < b) add.pb({ovr + 1, b});
                 ++it;
             }
             for (auto &p : del) S.erase(p);
             for (auto &p : add) S.insert(p);
         }
         else if (op == 3) {
             int l, r;
             cin >> l >> r;
             auto res = seg.ask(l, r);
             cout << res.val << " " << res.cnt << "\n";
         }
     }
 }

头文件

 //Anoth3r
 #include<bits/stdc++.h>
 #include<bits/extc++.h>
 #define pb push_back
 #define eb emplace_back
 #define fi first
 #define se second
 #define all(a) a.begin(), a.end()
 #define rall(a) a.rbegin(), a.rend()
 using namespace std;
 ​
 typedef long long ll;
 typedef long double ld;
 typedef unsigned long long ull;
 typedef __int128 i128;
 typedef pair<int, int> PII;
 typedef pair<ll, ll> PLL;
 typedef tuple<ll, ll, ll> TLLL;
 typedef __gnu_pbds::tree<PLL, __gnu_pbds::null_type, less<PLL>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update> Tree;
 // typedef __gnu_pbds::tree<ll, __gnu_pbds::null_type, less<ll>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update> Tree;
 ​
 constexpr int inf = (ll)1e9 + 7;
 constexpr ll INF = (ll)2e18 + 9;
 // constexpr ll INF = (ll)4e18;
 // constexpr ll MOD = 1e9 + 7;
 constexpr ll MOD = 998244353;
 constexpr ld PI = acos(-1.0);
 constexpr ld eps = 1e-10;
 ​
 mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
 ull randint(ull l, ull r) {uniform_int_distribution<unsigned long long> dist(l, r); return dist(rng);}
 ​
 void init() {
 ​
 }
 ​
 void solve() {
 ​
 }
 ​
 int main() {
     ios::sync_with_stdio(0);
     cin.tie(0); cout.tie(0);
 ​
     init();
 ​
     int t = 1;
     // cin >> t;
     for (int _ = 1; _ <= t; ++_) {
         solve();
     }
     return 0;
 }

线段树

 template<class Int>
 struct Tag {
     Int v = 0;
     void operator+=(const Tag<Int> &o) {
         v += o.v;
     }
     bool check() {
         return v != 0;
     }
 };
 ​
 template<class Int>
 struct Info {
     Int val = 0;
     int cnt = 1;
     int l = 0, r = 0;
 ​
     Info() { val = 0; cnt = 1; l = r = 0; }
 ​
     Info(int) { val = -inf; cnt = 0; l = r = 0; }
 ​
     Info operator+(const Info<Int> &o) const {
         Info res;
         res.l = l;
         res.r = o.r;
         if (val > o.val) {
             res.val = val;
             res.cnt = cnt;
         } else if (val < o.val) {
             res.val = o.val;
             res.cnt = o.cnt;
         } else {
             res.val = val;
             res.cnt = cnt + o.cnt;
         }
         return res;
     }
     void operator+=(const Tag<Int> &o) {
         val += o.v;
     }
     bool check() {
         return l != r;
     }
 };
 ​
 template<class Int>
 class SegTree {
 private:
     vector<Info<Int>> info;
     vector<Tag<Int>> tag;
     int n;
 ​
     int ls(int x) {return x << 1;}
     int rs(int x) {return x << 1 | 1;}
 ​
     void print(int x, int l, int r) {
         cout << x << ":[" << l << "," << r << "],val:" << info[x].val << ",cnt:" << info[x].cnt << ",tag:" << tag[x].v << "\n";
         if (l == r) return;
         int mid = l + r >> 1;
         print(ls(x), l, mid);
         print(rs(x), mid + 1, r);
     }
 ​
     template<class Array>
     void build(int x, int l, int r, Array &data) {
         info[x].l = l;
         info[x].r = r;
         if (l == r) {
             info[x].val = data[l];
             return;
         }
         int mid = (l + r) >> 1;
         build(ls(x), l, mid, data);
         build(rs(x), mid + 1, r, data);
         info[x] = info[ls(x)] + info[rs(x)];
     }
 ​
     void push_down(int x) {
         if (tag[x].check() && info[x].check()) {
             info[ls(x)] += tag[x];
             info[rs(x)] += tag[x];
             tag[ls(x)] += tag[x];
             tag[rs(x)] += tag[x];
             tag[x] = {0};
         }
     }
 ​
     void update(int x, int l, int r, int lq, int rq, Tag<Int> v) {
         if (rq < l || lq > r) return;
         if (lq <= l && r <= rq) {
             info[x] += v;
             tag[x] += v;
             return;
         }
         push_down(x);
         int mid = (l + r) >> 1;
         update(ls(x), l, mid, lq, rq, v);
         update(rs(x), mid + 1, r, lq, rq, v);
         info[x] = info[ls(x)] + info[rs(x)];
     }
 ​
     void modify(int x, int l, int r, int pos, Int v) {
         if (r < pos || l > pos) return;
         if (l == r && l == pos) {
             info[x].val = v;
             return;
         }
         int mid = (l + r) >> 1;
         push_down(x);
         modify(ls(x), l, mid, pos, v);
         modify(rs(x), mid + 1, r, pos, v);
         info[x] = info[ls(x)] + info[rs(x)];
     }
 ​
     Info<Int> ask(int x, int l, int r, int lq, int rq) {
         if (rq < l || lq > r) return {0};
         if (lq <= l && r <= rq) return info[x];
         push_down(x);
         int mid = (l + r) >> 1;
         auto left = ask(ls(x), l, mid, lq, rq);
         auto right = ask(rs(x), mid + 1, r, lq, rq);
         if (left.cnt == 0) return right;
         if (right.cnt == 0) return left;
         return left + right;
     }
 public:
     SegTree(int n_): n(n_), info(4 * n_ + 1), tag(4 * n_ + 1) {}
 ​
     void printTree() {
         print(1, 1, n);
     }
 ​
     template<class Array>
     void build(Array &data) {
         build(1, 1, n, data);
     }
 ​
     void update(int l, int r, Tag<Int> v) {
         if (l > r) return;
         update(1, 1, n, l, r, v);
     }
 ​
     void modify(int pos, Int v) {
         modify(1, 1, n, pos, v);
     }
 ​
     Info<Int> ask(int l, int r) {
         return ask(1, 1, n, l, r);
     }
 };
暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																				
					
											
						

	

		
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
	

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇
下一篇