2024 牛客多校第三场（倍增，贪心）
J - Rigged Games
题面：给出一个 \(01\) 字符串 \(s\) , 代表小局比赛的输赢。求大局 Bo( \(2b - 1\) )，小局 Bo( \(2a - 1\) ) 的结果。
求出 \(s\) 的每一个位置出发的输赢结果。
数据范围： \(n, a, b \; (1≤n,a,b≤1e5)\)
我和正解的思考相同的部分只有，我知道它会循环，并且找出了一定的循环规律。
考虑定义
-
\(f_{i, j}\) 为从 \(i\) 位置出发，经历 \(2^j\) 场局后小局赢得的个数
-
\(g_{i, j}\) 为从 \(i\) 位置出发，经历 \(2^j\) 场局后对局从哪里开始
好完美又自然的定义，但是依然没想到。然后维护这两个数组，并且求出当前位置赢下 \(2b - 1\) 场时谁赢下了该场比赛。
还有一点，既然是倍增，当然要先求出 \(j = 0\) 时的情况。记录前缀和，二分求出当前位置后多少局刚好赢下一小局。前缀和后二分，真是太优美了。
参考代码如下：
// Created by qyy on 2024/9/10.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<int, int>
#define endl "\n"
const long long inf = 0x3f3f3f3f3f3f3f3f;
const int N = 3e5 + 10;
const int mod = 7;
int f[N][22], g[N][22], pre[N], nxt[N], flag[N], ans[N];
int n, m, a, b;
string s;
int query(int pos, int x){
int ans = 0;
for(int i = 0; i <= 20; i++){
if((1 << i) & x){
ans += f[pos][i];
pos = g[pos][i];
}
}
return ans;
}
void solve() {
cin >> n >> a >> b;
cin >> s;
for(int i = 0; i <= 300000; i++){
int pos = i % n;
if(s[pos] == '0'){
if(i == 0){
continue;
}
pre[i] = pre[i - 1];
}else{
if(i == 0){
pre[i] = 1;
continue;
}
pre[i] = pre[i - 1] + 1;
}
}
for(int i = 0; i < n; i++){
// calculate the nxt[i], flag[i];
int l = i, r = 3e5;
int cnt1, cnt0;
while(l < r){
int mid = (l + r) >> 1;
if(i == 0){
cnt1 = pre[mid];
}else{
cnt1 = pre[mid] - pre[i - 1];
}
cnt0 = mid - i + 1 - cnt1;
if(max(cnt1, cnt0) < a){
l = mid + 1;
}else{
r = mid;
}
}
nxt[i] = (r + 1) % n;
if(r == 0){
cnt1 = pre[r];
}else{
cnt1 = pre[r] - pre[i - 1];
}
cnt0 = r - i + 1 - cnt1;
if(cnt1 > cnt0){
flag[i] = 1;
}else{
flag[i] = 0;
}
}
for(int i = 0; i < n; i++){
f[i][0] = flag[i];
g[i][0] = nxt[i];
}
for(int j = 1; j <= 20; j++){
for(int i = 0; i < n; i++){
f[i][j] = f[i][j - 1] + f[g[i][j - 1]][j - 1];
g[i][j] = g[g[i][j - 1]][j - 1];
}
}
for(int i = 0; i < n; i++){
int cnt1 = query(i, 2*b - 1);
if(cnt1 >= b){
ans[i] = 1;
}else{
ans[i] = 0;
}
cout << ans[i];
}
cout << endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t = 1;
//cin >> t;
while (t--) {
solve();
}
return 0;
}
A - Bridging the Gap 2
题意：\(n\) 个人过河，一条船，任何时刻船上人数起码 \([L, R]\) 个人，且从一岸边到另一岸边，船上每个人都会损失一点体力，给出所有人的体力值，问能否全部人都安全过河。
数据范围：$n,L,R ; (1≤L<R≤n≤5e5) $
考虑民权出的：
有 \(n\) 个人，第\(i\)个人有 \(a_i\left(1\leq i\leq n\right)\) 点能量，现在有无穷只小卡拉米，小卡拉米一只一只出现 (即开始出现一只，打死后出现下一只),每只小卡拉米都需要至少\(m\)个人一起消耗一点能量才能将它击败，能量不能恢复，最终求这\(n\)个人最多能消灭多少只卡拉米。
例：有 4 个人，能量分别为 \(\{5,3,2,1\}\) , \(m\) 为 2,那么第一只小卡拉米需要第 1 个人和第 2 个人，同时消耗一点能量才能将其消灭，以此类推最终最多能消灭5只怪物，组合为(1,2) , (1,2) , (1,2) , (1,3) , (1,3,4)
最多能消灭多少只小卡拉米？
考虑二分答案，在check函数中，有一个显然成立的结论，所有能量大于当前怪兽的数量的全部是没用的能量。而剩下的全部能量加起来与怪兽的血量做比较即可出答案，好神奇的，好巧妙的结论，仿佛从眼皮子底下溜走的简单结论。
于是此题就是算出当前 \(n\) 个人过河最少需要多少次，与他们体力求出来最多可以划多少次，两者做比较。
参考代码如下：
// Created by qyy on 2024/9/10.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<int, int>
#define endl "\n"
const long long inf = 0x3f3f3f3f3f3f3f3f;
const int N = 5e5 + 10;
const int mod = 7;
ll n, L, R, a[N];
int check(ll x){
ll res = n - x*(R - L);
if(res > L && res <= R){
return 7;
}
if(res > R){
return 0;
// 说明 k 小了
}
if(res <= L){
return 1;
}
return false;
}
void solve() {
cin >> n >> L >> R;
for(int i = 1; i <= n; i++){
cin >> a[i];
}
ll kl = 0, kr = 1e6;
while(kl <= kr){
ll mid = (kl + kr) >> 1;
if(check(mid) == 7){
kl = kr = mid;
break;
}
if(check(mid) == 1){
kr = mid - 1;
}else if(check(mid) == 0){
kl = mid + 1;
}
}
// cout << kl << endl;
// ll res2 = (n - L + R - L - 1)/(R - L) - 1;
ll sum = L*kl;
for(int i = 1; i <= n; i++){
if(a[i] % 2 == 0){
a[i]--;
}
a[i] = (a[i] - 1)/2;
}
for(int i = 1; i <= n; i++){
sum -= min(a[i], kl);
}
if(sum <= 0){
cout << "YES\n";
}else{
cout << "NO\n";
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t = 1;
//cin >> t;
while (t--) {
solve();
}
return 0;
}
D - Dominoes!
好一个贪心模拟，硬控我两个钟。
题意：给出 \(n\) 个有左右两个数字的骨牌，要求排列骨牌成一排，使得任意两个相邻骨牌的相邻的两个数字不得相同，输出方案。
一个重要观察是：问题出在两个数字相同的骨牌上，如果数字不相同的话，总有办法排好。
于是慢慢分类讨论吧，是个锻炼码力的题目......
参考代码如下：
// Created by qyy on 2024/9/11.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<int, int>
#define endl "\n"
const long long inf = 0x3f3f3f3f3f3f3f3f;
const int N = 4e5 + 10;
const int mod = 7;
int n;
struct Domino{
int l, r;
}d[N], ans[N];
bool flag[N];
int to[N];
map<int, int> mp;
set<int> st;
int cnt1[N], cnt2[N];
vector<int> e[N];
bool cmp2(int x, int y){
return cnt1[x] < cnt1[y];
}
void solve() {
cin >> n;
for(int i = 1; i <= n; i++){
cin >> d[i].l >> d[i].r;
st.insert(d[i].l);
st.insert(d[i].r);
}
// ------- 离散化 ---------
int cnt = 0;
for(auto i:st){
mp[i] = ++cnt;
to[cnt] = i;
}
int sum2 = 0;
for(int i = 1; i <= n; i++){
d[i].l = mp[d[i].l];
d[i].r = mp[d[i].r];
if(d[i].l != d[i].r){
sum2++;
}
}
if(sum2 == n){
int last = 0;
int opos = 1;
// 特殊情况，没有重复的多米诺
for(int i = 1; i <= n; i++){
int l = d[i].l, r = d[i].r;
if(l == r) continue;
if(l == last){
swap(d[i].l, d[i].r);
swap(l, r);
}
ans[opos].l = l;
ans[opos].r = r;
last = r;
opos++;
}
cout << "YES\n";
for(int i = 1; i <= n; i++){
cout << to[ans[i].l] << " " << to[ans[i].r] << endl;
}
return ;
}
for(int i = 1; i <= n; i++){
int l = d[i].l, r = d[i].r;
if(l == r){
cnt1[l]++;
}else{
cnt2[l]++;
cnt2[r]++;
}
}
int pos = 0;
for(int i = 1; i <= 2*n; i++){
if(cnt1[pos] < cnt1[i]){
pos = i;
}
}
for(int i = 1; i <= 2*n; i++){
if(cnt1[i] == cnt1[pos]){
if(n - cnt2[i] < 2*cnt1[i] - 1){
cout << "NO\n";
return ;
}
}
}
priority_queue<PII> q;
// 相同的都无法填满最大的 "boss"
if(n - sum2 < 2*cnt1[pos] - 1){
// 贪心放置相同的多米诺
for(int i = 1; i <= cnt1[pos]*2 - 1; i+=2){
ans[i].l = ans[i].r = pos;
}
int cur = 2;
for(int i = 1; i <= 2*n; i++){
if(i == pos){
continue;
}
for(int j = 1; j <= cnt1[i]; j++){
ans[cur].l = ans[cur].r = i;
cur += 2;
}
}
// 贪心放置不同的多米诺
int last = pos;
for(int i = 1; i <= n; i++){
int l = d[i].l, r = d[i].r;
if(l == r) continue;
if(l == last){
swap(d[i].l, d[i].r);
swap(l, r);
}
if(cur < cnt1[pos]*2 - 1){
if(l == pos || r == pos){
continue;
}
}
ans[cur].l = l;
ans[cur].r = r;
flag[i] = true;
if(cur >= cnt1[pos]*2 - 1){
last = r;
cur++;
}else{
cur+=2;
}
}
for(int i = 1; i <= n; i++){
int l = d[i].l, r = d[i].r;
if(l == r) continue;
if(flag[i]) continue;
if(l == last){
swap(d[i].l, d[i].r);
swap(l, r);
}
ans[cur].l = l;
ans[cur].r = r;
flag[i] = true;
if(cur >= cnt1[pos]*2 - 1){
last = r;
cur++;
}else{
cur+=2;
}
}
}else{
// --------- 这一部分真的有点难写诶 -------------
vector<int> tmp;
for(int i = 1; i <= 2*n; i++){
if(cnt1[i] > 0){
tmp.push_back(i);
}
}
sort(tmp.begin(), tmp.end(), cmp2);
int len = tmp.size();
for(int i = 0; i < len; i++){
for(int j = 1; j <= cnt1[tmp[i]]; j++){
e[j].push_back(tmp[i]);
}
}
int fpos = cnt1[tmp[len - 1]]*2 - 1, opos = 2;
for(int i = 1; i <= fpos; i += 2){
ans[i].l = ans[i].r = tmp[len - 1];
}
int last = 0;
for(int i = 4e5; i >= 1; i--){
if(e[i].size() <= 1){
continue;
}
int lenj = e[i].size();
for(int j = 0; j < lenj - 1; j++){
ans[opos].l = ans[opos].r = e[i][j];
last = ans[opos].l;
if(opos <= fpos){
opos += 2; // 说明还在 boss 的掌握之中
}else{
opos++;
}
}
}
for(int i = 1; i <= n; i++){
int l = d[i].l, r = d[i].r;
if(l == r) continue;
if(l == last){
swap(d[i].l, d[i].r);
swap(l, r);
}
ans[opos].l = l;
ans[opos].r = r;
last = r;
opos++;
}
}
cout << "YES\n";
for(int i = 1; i <= n; i++){
cout << to[ans[i].l] << " " << to[ans[i].r] << endl;
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t = 1;
//cin >> t;
while (t--) {
solve();
}
return 0;
}
这样的时间还不错
标签：const,int,多校,long,mid,2024,cnt1,else,第三场 From： https://www.cnblogs.com/9102qyy/p/18408701