牛客周赛 Round 116
|
44
|
0
|
牛客,牛客周赛,题解

550 字
|
3 分钟

A 小红的区间

判断一下即可。

 void solve() {
     int a, b, c, d;
     cin >> a >> b >> c >> d;
     if (a > c && b < d) cout << "A" << "\n";
     else cout << "B" << "\n";
 }

B 小红的区间判断

同 A ，判断一下即可。

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

C 小红的区间查询

二分左端点，查询是否在这个区间内即可，注意边界。

 void solve() {
     int n, q;
     cin >> n >> q;
     vector<array<int, 3>> a(n);
     for (int i = 0; i < n; ++i) cin >> a[i][0] >> a[i][1], a[i][2] = i + 1;
     sort(all(a), [&](auto a, auto b) {
         if (a[0] != b[0]) return a[0] < b[0];
         return a[1] < b[1];
     });
  
     vector<ll> l(n);
     for (int i = 0; i < n; ++i) l[i] = a[i][0];
  
     while (q--) {
         ll x;
         cin >> x;
         int pos = upper_bound(all(l), x) - l.begin() - 1;
         if (pos >= 0) {
             auto [l, r, id] = a[pos];
             if (l <= x && x <= r) {
                 cout << id << "\n";
                 continue;
             }
         }
         cout << -1 << "\n";
     }
 }

D 小红的区间相交

考虑反做，只需要排除存在相离的一对或存在严格包含的一对即可。

  • 相离：等价于所有区间交集为空，判断一下 $min_R$ 和 $max_L$ 的大小关系即可。
  • 严格包含：
    • 按 $l$ 升序排序；对相同 $l$ 的区间一起处理（因为 $l_i$ = $l_j$ 不构成严格包含）。
    • 维护到当前为止（只考虑 $l$ 更小的区间）的 $max_r$ 。对于当前组中每个区间，如果 $max_r$ > $r_{cur}$（严格大），说明存在某个 $l$ 更小且 $r$ 更大的区间，发生严格包含 —— 输出 $No$ 。
    • 组内检查完毕后再把该组的 $r$ 更新到 $max_r$ 中。

如果两个检查都通过，则输出 $Yes$ 。

 void solve() {
     int n, mx = -inf, mn = inf;
     cin >> n;
     vector<PII> a(n);
     for (int i = 0; i < n; ++i) {
         cin >> a[i].fi >> a[i].se;
         mx = max(mx, a[i].fi);
         mn = min(mn, a[i].se);
     }
     if (mx > mn) {
         cout << "No" << "\n";
         return;
     }
     sort(all(a), [&](auto a, auto b) {
         if (a.fi != b.fi) return a.fi < b.fi;
         return a.se < b.se;
     });
     mx = -inf;
     bool ok = false;
     int i = 0;
     while (i < n && !ok) {
         int j = i;
         while (j < n && a[j].fi == a[i].fi) ++j;
         for (int k = i; k < j; ++k) {
             if (mx > a[k].se) {
                 ok = true;
                 break;
             }
         }
         for (int k = i; k < j; ++k) {
             mx = max(mx, a[k].se);
         }
         i = j;
     }
     if (ok) cout << "No" << "\n";
     else cout << "Yes" << "\n";
 }

E 小红的区间构造

设 $a_i$ 为点 $i$ 被覆盖次数。可发现相邻差分决定了每个位置需要多少区间开始或结束：

  • 结束数 $e_i = \max(0, a_i – a_{i+1})$ 。
  • 起始数 $s_i = (a_i – a_{i-1}) + e_{i-1}​$ 。

通过调节 $e_i$ 总和使其恰为 $m​$ ，再用栈模拟（区间开始入栈、区间结束出栈）即可构造出合法方案。

 void solve() {
     int n, m;
     ll sum = 0;
     cin >> n >> m;
     vector<ll> a(n + 2, 0);
     for (int i = 1; i <= n; i++) cin >> a[i], sum += a[i];
     a[n + 1] = 0;
  
     vector<ll> d(n + 1, 0);
     ll diff = 0;
     for (int i = 1; i <= n; i++) {
         d[i] = max(0LL, a[i] - a[i + 1]);
         diff += d[i];
     }
     if (m < diff || m > sum) {
         cout << -1 << "\n";
         return;
     }
     ll extra = m - diff;
     vector<ll> e(n + 1, 0);
     for (int i = 1; i <= n; i++) e[i] = d[i];
     for (int i = 1; i <= n && extra > 0; i++) {
         ll cap = a[i] - e[i];
         if (cap <= 0) continue;
         ll use = min(cap, extra);
         e[i] += use;
         extra -= use;
     }
     vector<ll> s(n + 1, 0);
     s[1] = a[1];
     for (int i = 2; i <= n; i++) {
         s[i] = (a[i] - a[i - 1]) + e[i - 1];
         if (s[i] < 0) {
             cout << -1 << "\n";
             return;
         }
     }
     ll S = 0;
     for (int i = 1; i <= n; i++) S += s[i];
     if (S != m) {
         cout << -1 << "\n";
         return;
     }
  
  
     vector<PII> ans;
     vector<int> stk;
     for (int i = 1; i <= n; i++) {
         for (ll t = 0; t < s[i]; ++t) stk.pb(i);
         for (ll t = 0; t < e[i]; ++t) {
             if (stk.empty()) {
                 cout << -1 << "\n";
                 return;
             }
             int l = stk.back(); stk.pop_back();
             ans.eb(l, i);
         }
     }
     if (ans.size() != m) {
         cout << -1 << "\n";
         return;
     }
     for (auto [u, v] : ans) cout << u << " " << v << "\n";
 }

F 小红的区间创建

每个已有区间把区间轴划分为若干相交与非相交段。 对每个位置 x ：

  • 设 $minR[x]$ 为覆盖到 $x$ 的区间最小右端点；新区间若包含 $x$ ，其右端点需 $\leq minR[x]-1$ 。
  • 设 $maxL[x]$ 为覆盖到 $x$ 的区间最大左端点；若包含 $x$ ，其左端点需 $\geq maxL[x]+1$ 。

再排除已有区间端点，统计所有满足左右限制的不相交区间对数即可。

 void solve() {
     int n, m;
     cin >> n >> m;
     vector<PII> a(n);
     for (int i = 0; i < n; ++i) cin >> a[i].fi >> a[i].se;
 ​
     vector<vector<int>> mna(m + 3), mnr(m + 3);
     for (auto [l, r] : a) {
         if (l + 1 <= m) mna[l + 1].pb(r);
         if (r + 1 <= m) mnr[r + 1].pb(r);
     }
     multiset<int> ms;
     vector<int> mr(m + 1, m + 1);
     for (int x = 1; x <= m; x++) {
         for (int v : mna[x]) ms.insert(v);
         for (int v : mnr[x]) {
             auto it = ms.find(v);
             if (it != ms.end()) ms.erase(it);
         }
         if (ms.empty()) mr[x] = m + 1;
         else mr[x] = *ms.begin();
     }
 ​
 ​
     vector<vector<int>> mxa(m + 2), mxr(m + 2);
     for (auto [l, r] : a) {
         mxa[l].pb(l);
         if (r <= m) mxr[r].pb(l);
     }
     multiset<int> ms2;
     vector<int> ml(m + 1, 0);
     for (int x = 1; x <= m; x++) {
         for (int v : mxa[x]) ms2.insert(v);
         for (int v : mxr[x]) {
             auto it = ms2.find(v);
             if (it != ms2.end()) ms2.erase(it);
         }
         if (ms2.empty()) ml[x] = 0;
         else ml[x] = *ms2.rbegin();
     }
 ​
     vector<bool> vis(m + 2, 0);
     for (auto [l, r] : a) {
         vis[l] = 1;
         vis[r] = 1;
     }
 ​
     vector<vector<int>> bucket(m + 3);
     for (int i = 1; i <= m; i++) {
         int T = ml[i] + 1;
         if (T < 1) T = 1;
         if (T > m + 1) T = m + 1;
         if (i >= 1 && i <= m) bucket[T <= m + 1 ? T : m + 1].pb(i);
     }
 ​
     BIT<int> bit(m);
     ll ans = 0;
     for (int i = 1; i <= m; ++i) {
         for (int j : bucket[i]) {
             if (!vis[j]) bit.add(j, 1);
         }
         if (vis[i]) continue;
         int mx = (mr[i] == m + 1 ? m : mr[i] - 1);
         if (mx < i) continue;
         ans += bit.ask(i, mx);
     }
     cout << ans << "\n";
 }

头文件

 //Another
 #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 BIT {
     vector<Int> a;
     int n;
 ​
     BIT() {}
     BIT(int n) {
         init(n);
     }
 ​
     void init(int n) {
         this->n = n;
         a.resize(n + 1);
     }
 ​
     void add(int x, int k) {
         for (; x <= n; x += x & -x) {
             a[x] += k;
         }
     }
 ​
     void add(int x, int y, Int k) {
         add(x, k), add(y + 1, -k);
     }
 ​
     Int ask(int x) {
         Int ans = 0;
         for (; x; x -= x & -x) {
             ans += a[x];
         }
         return ans;
     }
 ​
     Int ask(int x, int y) {
         return ask(y) - ask(x - 1);
     }
 ​
     Int kth(int k) {
         Int ans = 0;
         for (int i = __lg(n); i >= 0; i--) {
             Int val = ans + (1 << i);
             if (val < n && a[val] < k) {
                 k -= a[val];
                 ans = val;
             }
         }
         return ans + 1;
     }
 };
暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																				
					
											
						

	

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

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇