【2024.9.30】NOIP2024 赛前集训-刷题训练（4）
Problem - 2000D - Codeforces
给一串数和一串LR字符，L 可以向右连接 R， 覆盖部分的LR不能再使用，但覆盖部分可以有被禁用的LR。每次覆盖部分的数字之和计入答案，求最大答案。
手玩一下发现可以贪心。从最左边的 L 和最右边的 R 开始贪心。操作顺序和实际是倒着的，但不影响。
#include<bits/stdc++.h>
#define F(i,l,r) for(int i(l);i<=(r);++i)
#define G(i,r,l) for(int i(r);i>=(l);--i)
using namespace std;
using ll = long long;
const int N = 2e5 + 105;
ll sum[N], ans = 0;
int posl[N],posr[N],a[N];
char s[N];
int n,T,cntl=0,cntr=0;
signed main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> T;
while(T--){
ans = 0;
cntl = 0;
cntr = 0;
cin >> n;
F(i, 1, n) cin >> a[i],sum[i] = sum[i - 1] + a[i];
cin >> (s + 1);
F(i, 1, n){
if(s[i] == 'L') posl[++cntl] = i;
else posr[++cntr] = i;
}
int l = 1, r = cntr;
while(l <= cntl && r >=1 && posl[l] < posr[r]){
ans += sum[posr[r]] - sum[posl[l] - 1];
++l, --r;
}
cout << ans << '\n';
}
return 0;
}
Problem - 33D - Codeforces
给一堆点和一堆没有交集的圆，保证点不在圆上。每次询问两个特定点 \(A，B\)， 问 \(A\) 到 \(B\) 至少要穿过多少个圆。
对于一个圆 \(S\)，
\(A \in S, B \in S\)， 不穿过。
\(A \in S, B \notin S\)， 要穿过。
\(A \notin S, B \in S\)， 要穿过。
\(A \notin S, B \notin S\)， 不穿过。
根据 点和圆位置的判定原理 预处理好 所有点圆关系 即可。
#include<bits/stdc++.h>
#define F(i,l,r) for(int i(l);i<=(r);++i)
#define G(i,r,l) for(int i(r);i>=(l);--i)
using namespace std;
using ll = long long;
const int N = 1005;
bool f[N][N];
int n, m, k;
ll kx[N], ky[N], cx[N], cy[N], r[N];
signed main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> m >> k;
F(i, 1, n) cin >> kx[i] >> ky[i];
F(i, 1, m) cin >> r[i] >> cx[i] >> cy[i];
F(i, 1, n){
F(j, 1, m){
if((kx[i] - cx[j]) * (kx[i] - cx[j]) + (ky[i] - cy[j]) * (ky[i] - cy[j]) < r[j] * r[j])
f[i][j] = 1;
}
}
while(k--){
int a, b, ans = 0;
cin >> a >> b;
F(i, 1, m){
int sum = f[a][i] + f[b][i];
if(sum == 1) ++ans;
}
cout << ans << '\n';
}
return 0;
}
Problem - 2001D - Codeforces
求最长子序列，要求元素互不相同，奇数位尽量大，偶数位尽量小。
手玩几个样例发现，能不能先跳过某个元素 \(x\)，把后面更符合要求的先放，取决于这是不是最后一个 \(x\)。
自然想到从右往左扫出后缀中每个元素出现的次数。标记一下在后缀中每个元素首次出现的位置 \(pos\)。
把序列信息整齐地写在草稿纸上后，容易发现在相邻两个 \(pos\) 之间，不用考虑是不是最后一个，那么就可以直接贪心地按照 “奇大偶小” 来选，其中 \(a[pos]\) 必选。
所以我们需要用线段树实现 单点复制 和 区间求max和min。
具体的实现过程为，从左往右一个一个 \(pos\)区间 地处理，每次跳转到极值的下一位就能保证一定最优。
！！！有一个细节：\(a[pos]\) 必选，但是 不一定选的是这个位置。所以如果这个值被提前选到了，那么这个 \(pos\)区间 要和后面的 \(pos\) 区间进行合并，直到 \(a[pos]\) 没有被选过。
时间复杂度：\(O(nlogn)\)， 其实可以用单调队列做到严格 \(O(n)\)。
(小小3k， 轻松拿捏~)
#include<bits/stdc++.h>
#define F(i,l,r) for(int i(l);i<=(r);++i)
#define G(i,r,l) for(int i(r);i>=(l);--i)
using namespace std;
using ll = long long;
const int N = 3e5 + 5;
const int inf = 0x3f3f3f3f;
int a[N], ne[N], t[N], mx[N << 2], mn[N << 2];
int T, n;
vector<int> v[N], tback;
void pushup(int u){
mx[u] = max(mx[u * 2], mx[u * 2 + 1]);
mn[u] = min(mn[u * 2], mn[u * 2 + 1]);
}
void update(int u, int l, int r, int x, int y){
if(l == r) {
if(y == inf) mx[u] = -y, mn[u] = y;
else mx[u] = mn[u] = y;
return ;
}
int mid = (l + r) >> 1;
if(x <= mid) update(u * 2, l, mid, x, y);
else update(u * 2 + 1, mid + 1, r, x, y);
pushup(u);
}
int query_max(int u, int l,int r, int x, int y){
if(x <= l && r <= y) return mx[u];
int mid = (l + r) >> 1, ret = -inf;
if(x <= mid) ret = max(ret, query_max(u * 2, l, mid, x, y));
if(y > mid) ret = max(ret, query_max(u * 2 + 1, mid + 1, r, x, y));
return ret;
}
int query_min(int u, int l,int r, int x, int y){
if(x <= l && r <= y) return mn[u];
int mid = (l + r) >> 1, ret = inf;
if(x <= mid) ret = min(ret, query_min(u * 2, l, mid, x, y));
if(y > mid) ret = min(ret, query_min(u * 2 + 1, mid + 1, r, x, y));
return ret;
}
signed main(){
// freopen("test.in","r",stdin);
// freopen("LMMS2.in","r",stdin);
// freopen("LMMS.out","w",stdout);
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> T;
while(T --){
cin >> n;
int len = 0;
F(i, 1, n) cin >> a[i], v[a[i]].emplace_back(i), update(1, 1, n, i, a[i]);
G(i, n, 1){
if(!t[a[i]]) ne[i] = i, ++len, tback.emplace_back(a[i]);
else ne[i] = ne[i + 1];
++t[a[i]];
}
int i = 1, cnt = 0;
cout << len << '\n';
while(i <= n){
int l = i, r = ne[i];
while(l < r){
while(a[r] == inf && r + 1 <= n) r = ne[r + 1];
int val;
if((++cnt) & 1){
val = query_max(1, 1, n, l, r);
}
else{
val = query_min(1, 1, n, l, r);
}
if(val !=inf && val != -inf){
if(val == a[r] && r + 1 <= n) r = ne[r + 1];
int pos = -1;
for(auto x : v[val]){
if(x >= l && x <= r && pos == -1) pos = x;
if(x >= l) update(1, 1, n, x, inf), a[x] = inf;
}
cout << val << ' ';
l = pos + 1;
}
else l = r + 1;
}
if(l == r && a[r] != inf) {
++cnt;
cout << a[r] << ' ';
for(auto x: v[a[r]]) if(x >= l) update(1, 1, n, x, inf), a[x] = inf;
} i = r + 1;
}
cout << '\n';
for(auto pos : tback) {
t[pos] = 0;
v[pos].clear();
}tback.clear();
}
return 0;
}
Problem - 2001E1 - Codeforces
#include<bits/stdc++.h>
#define F(i,l,r) for(int i(l);i<=(r);++i)
#define G(i,r,l) for(int i(r);i>=(l);--i)
using namespace std;
using ll = long long;
const int N = 505;
int n, k, mod, T;
ll f[N][N], g[N][N], sum[N][N];
signed main(){
// freopen("DH.in","r",stdin);
// freopen("DH.out","w",stdout);
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> T;
while(T --){
cin >> n >> k >> mod;
F(i, 1, n) f[i][0] = 1, g[i][0] = 1, sum[i][0] = 1;
F(i, 0, k) f[1][i] = g[1][i] = 1, sum[1][i] = i + 1;
F(i, 2, n) F(j, 1, k){
G(p, j, 0){
int q = min(p, j - p);
if(p != q){ // p >= q
(g[i][j] += g[i - 1][p] * sum[i - 1][q] * 2 % mod) %= mod;
(f[i][j] += f[i - 1][p] * sum[i - 1][q] * 2 % mod) %= mod;
}
else {
(g[i][j] += g[i - 1][p] * sum[i - 1][p - 1] * 2 % mod + g[i - 1][p] * g[i - 1][p] % mod) %= mod;
(f[i][j] += f[i - 1][p] * sum[i - 1][p - 1] * 2 % mod) %= mod;
}
}
sum[i][j] = (sum[i][j - 1] + g[i][j]) % mod;
}
cout << f[n][k] << '\n';
F(i, 0, n) F(j, 0, k) f[i][j] = g[i][j] = sum[i][j] = 0;
}
return 0;
}