牛客周赛 Round 82（思维、差分、树状数组、大根堆、前后缀、递归）
文章目录
- 牛客周赛 Round 82（思维、差分、树状数组、大根堆、前后缀、递归）
- A. 夹心饼干
- B. C. 食堂大作战（思维）
- D. 小苯的排列计数(差分、树状数组)
- E. 和+和（大根堆，前缀和）
- F. 怎么写线性SPJ （思维、递归）
牛客周赛 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
首先，标黄色的元素的值是确定的。
其次，我们依次来看：
- 72，在此处，可以选择 8，9，10。即，有三种选择。（这里表示第二个 7，其他相同形式同理）
- 73，在此处，可以选择 8，9，10。但是，这时已经在 72处使用过一个元素，还有两种选择可用。
- 52，在此处，可以选择 6，8，9，10。但是，这时已经在 72 和 73 处使用过两个元素，还有两种选择可用。
- 依次类推…
对于一个方案，在某元素 x：
- 如果第一次出现时，该元素在只能在此处，在此处贡献一种组合的可能。
- 如果元素 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;
}