牛客周赛 Round 82（思维、差分、树状数组、大根堆、前后缀、递归）

牛客周赛 Round 82（思维、差分、树状数组、大根堆、前后缀、递归）

A. 夹心饼干

语法基础题

#include<bits/stdc++.h>
using namespace std;int main(){string s;cin >> s;cout << (s[0] == s[2] ? "YES" : "NO") << endl;return 0;
}

B. C. 食堂大作战（思维）

显然，只要没有两个窗口同时关门，即合法方案。

对于方案，按照关门时间排序，依次输出即可。

#include<bits/stdc++.h>
using namespace std;const int maxn = 1e5 + 5;pair<int, int> a[maxn];int main(){int n;cin >> n;for(int i = 1; i <= n; i++){cin >> a[i].first;a[i].second = i;} sort(a+1, a+1+n);int flag = 1;for(int i = 1; i <= n; i++){if(a[i].first == a[i-1].first){flag = 0;break;}}if(flag){cout << "YES" << endl;}else cout << "NO" << endl;return 0;
}

D. 小苯的排列计数(差分、树状数组)

对于样例：

10

7 7 7 5 5 1 1 1 1 1 1

首先，标黄色的元素的值是确定的。

其次，我们依次来看：

1. 7₂，在此处，可以选择 8，9，10。即，有三种选择。（这里表示第二个 7，其他相同形式同理）
2. 7₃，在此处，可以选择 8，9，10。但是，这时已经在 7₂处使用过一个元素，还有两种选择可用。
3. 5₂，在此处，可以选择 6，8，9，10。但是，这时已经在 7₂ 和 7₃ 处使用过两个元素，还有两种选择可用。
4. 依次类推…

对于一个方案，在某元素 x：

1. 如果第一次出现时，该元素在只能在此处，在此处贡献一种组合的可能。
2. 如果元素 x 不是第一次出现时：
   • 如有大于该元素的选择，可选择元素的个数等于此处贡献的组合。
   • 如没有大于该元素的选择，则方案不合法。

---

使用差分和树状数组配合，即可实现，求[x, n] 中的可用元素个数。

---

#include<bits/stdc++.h>
#define ll long long
using namespace std;const int maxn = 1e6 + 5;
const ll mod = 998244353;ll a[maxn], tree[maxn];int lowbit(int x){return x & (-x);
}void add(int i, int value){while(i < maxn){tree[i] += value;i += lowbit(i);}
}int sum(int i){int res = 0;while(i > 0){res += tree[i];i -= lowbit(i);}return res;
}int main(){int ncase;cin >> ncase;while(ncase--){int n;cin >> n;for(int i = 1; i <= n; i++) cin >> a[i];for(int i = 1; i <= n; i++) tree[i] = 0;for(int i = 1; i <= n; i++) add(i, 1);ll res = 1;for(int i = 1; i <= n; i++){if(a[i] != a[i-1]){if(a[i] > a[i-1]  && i != 1){res = 0;break;}add(a[i], -1);}else{int cnt = sum(n) - sum(a[i]);	// 差分if(cnt == 0){res = 0;break;}else{res = res * cnt % mod;add(a[i]+1, -1);}}}cout << res << endl;}return 0;
}

E. 和+和（大根堆，前缀和）

题意等价于：选一个 x，在 a[1，x] 中选 m 个最小的数，在 b[x+1, n] 中选 m 个最小的数，使得选出的数sum最小。

枚举所有可能的 x，只要能 O(1) 或者 O(log(n)) 求出 a[1，x] 中 m 个最小的数的和，即可。

---

对于a数组，维护一个大小为 m 的大根堆，即前 i 个元素中最小的 m 个元素。

依次遍历a数组，插入新值a[i]，删除最大的元素，维护sum，维护前缀min即可。

---

对于 b 数组，逆序遍历，操作同上。

---

#include<bits/stdc++.h>
#define ll long long
using namespace std;const int maxn = 2e5 + 5;ll a[maxn], b[maxn];
ll pre[maxn], suf[maxn];priority_queue<int> qu;int main(){int n, m;cin >> n >> m;for(int i = 1; i <= n; i++) cin >> a[i];for(int i = 1; i <= n; i++) cin >> b[i];ll sum = 0;for(int i = 1; i <= n; i++){sum += a[i];qu.push(a[i]);if(i > m){sum -= qu.top();qu.pop();			}pre[i] = sum;} sum = 0;while(!qu.empty()) qu.pop();for(int i = 1; i <= n; i++){sum += b[n-i+1];qu.push(b[n-i+1]);if(i > m){sum -= qu.top();qu.pop();			}suf[n-i+1] = sum;}ll res = 2e9;for(int i = m; i+m-1 < n; i++){res = min(res, pre[i] + suf[i+1]);}cout << res << endl;return 0;
}

F. 怎么写线性SPJ （思维、递归）

手搓几个样例后，容易想到一个事实：

令 mid = ( l + r ) / 2，如果 a[mid] 是一个 “唯一元素”，接下来，只需要考虑 (l, mid-1) 和 (mid+1, r) 即可。

用相同的思路处理(l, mid-1) 和 (mid+1, r)，直到区间大小为 1。（递归）

#include<bits/stdc++.h>
#define ll long long
using namespace std;const int maxn = 2e5 + 5;int a[maxn];void dfs(int l, int r, int num){if(l > r) return; int mid = l + r >> 1;a[mid] = num;dfs(l, mid-1, num+1);dfs(mid+1, r, num+1);
}int main(){int n;cin >> n;dfs(1, n, 1); set<int> s;for(int i = 1; i <= n; i++) s.insert(a[i]);cout << s.size() << endl;for(int i = 1; i <= n; i++) cout << a[i] << " ";return 0;
}