2023/11/28
vp了一场edu
Educational Codeforces Round 152 (Rated for Div. 2)
A。
签到
B.
我们可以发现一个性质，在有数字被减到0之前，所以数字必须小于等于k，否则我就去见那个大于k的数了。所以实际上就是a[i]%k，排序，特判一下余数为0时，a[i]=k;
C
非常的巧妙
给q次询问，那么我们如何快速的处理，发现一段区间可以等价的缩小，就是头部删0，尾部删1.那么我们维护两个数组pre，nxt。pre代表以i为右端点，能到的最左边，nxt同理。那么我们对于每段区间，把他等价转换之后，再推入set里面计数。特别注意，需要特判一个原字符串不会动的情况，这样会导致我们重复计数。
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define Acode ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define int long long
const int N = 2e5 + 10;
int pre[N], nxt[N];
set<pair<int, int>> alls;
void solve()
{
alls.clear();
int n, m;
cin >> n >> m;
string s;
cin >> s;
s = " " + s;
for (int i = 1; i <= n; i++)
{
if (s[i] == '1')
pre[i] = pre[i - 1];
else
pre[i] = i;
}
nxt[n + 1] = 1e15;
for (int i = n; i >= 1; i--)
{
if (s[i] == '0')
nxt[i] = nxt[i + 1];
else
nxt[i] = i;
}
while (m--)
{
int l, r;
cin >> l >> r;
l = nxt[l];
r = pre[r];
// cerr << l << " " << r << endl;
if (l > r)
alls.insert({-1, -1});
else
alls.insert({l, r});
}
cout << alls.size() << endl;
}
signed main()
{
Acode;
int T = 1;
cin >> T;
while (T--)
{
solve();
}
return 0;
}
D
其实挺简单的，感觉比C要简单。
双指针+贪心 ，我们先看2，覆盖左右，然后1。
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define Acode ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define int long long
const int N = 2e6 + 10;
int n, q;
int a[N];
int vis[N];
void solve()
{
int n;
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
int ans = 0;
for (int i = 1; i <= n; i++)
{
if (!a[i])
continue;
ans++;
int flag = 0;
int r = i;
for (int j = i; j <= n; j++)
{
if (a[j] == 2)
flag = 1;
if (!a[j])
break;
r = j;
}
if (flag)
{
if (a[i - 1] == 0 && vis[i - 1] == 0 && i - 1 >= 1)
{
vis[i - 1] = 1;
}
vis[r + 1] = 1;
}
else
{
if (a[i - 1] == 0 && vis[i - 1] == 0 && i - 1 >= 1)
{
vis[i - 1] = 1;
}
else
{
vis[r + 1] = 1;
}
}
i = r;
}
for (int i = 1; i <= n; i++)
{
if (!vis[i] && !a[i])
ans++;
}
cout << ans << endl;
}
signed main()
{
Acode;
int T = 1;
// cin >> T;
while (T--)
{
solve();
}
return 0;
}
然后学了点数据结构
扫描线-区间不同数和
我们关注每个区间的右端点r，那么r从1n扫描，同时用树状数组维护一个ans[l]数组，表示当前[lr]区间内的不同数的和，自然我们要关注a[r]这个数。看他上一次出现实在哪里pos=pre[a[r]],那么pos之前的区间不会因为a[r]而增加。而左端点[pos+1,r]会增加a[r].区间加，对于每个左端点单点查。
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define Acode ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define int long long
const int N = 1e6 + 10;
int a[N], pre[N];
vector<pair<int, int>> g[N];
int t[N];
int lowbit(int x)
{
return x & -x;
}
void add(int x, int val)
{
while (x <= 1e6)
{
t[x] += val;
x += lowbit(x);
}
}
int getsum(int x)
{
int sum = 0;
while (x)
{
sum += t[x];
x -= lowbit(x);
}
return sum;
}
int ans[N];
void solve()
{
int n, q;
cin >> n >> q;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i <= q; i++)
{
int l, r;
cin >> l >> r;
g[r].push_back({l, i});
}
for (int r = 1; r <= n; r++)
{
int pos = pre[a[r]];
add(pos + 1, a[r]);
add(r + 1, -a[r]);
for (auto it : g[r])
{
int l = it.first;
int id = it.second;
ans[id] = getsum(l);
}
pre[a[r]] = r; // 更新a[r]值上一次出现的位置
}
for (int i = 1; i <= q; i++)
{
cout << ans[i] << endl;
}
}
字典树应用-异或第k小
凡是碰到异或的题目，字典树都是不错的选择，我们把所有数都放进字典树里面，然后想找第k小，先看这一位为零有几个。然后在字典树上选择往那边走
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define Acode ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define int long long
const int N = 1e5;
struct node
{
int s[2];
int sz = 0;
} seg[N * 32];
int n, m, idx = 1; //idx从1开始
void insert(int x)
{
int p = 1; //注意这里p不能等于0，否则查询的时候，seg[p][id]为0时，会拿到根节点的值
for (int i = 30; i >= 0; i--)
{
seg[p].sz++;
int id = ((x >> i) & 1);
if (!seg[p].s[id])
seg[p].s[id] = ++idx;
p = seg[p].s[id];
}
seg[p].sz++;
}
int query(int x, int k)
{
int p = 1;
int ans = 0;
for (int i = 30; i >= 0; i--)
{
int id = ((x >> i) & 1);
if (seg[seg[p].s[id]].sz >= k)
{
p = seg[p].s[id];
}
else
{
k -= seg[seg[p].s[id]].sz;
ans ^= (1LL << i);
p = seg[p].s[1LL ^ id];
}
}
return ans;
}
void solve()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
int x;
cin >> x;
insert(x);
}
for (int i = 1; i <= m; i++)
{
int x, k;
cin >> x >> k;
cout << query(x, k) << endl;
}
}
signed main()
{
Acode;
int T = 1;
while (T--)
{
solve();
}
return 0;
}
扫描线-权值线段树（求mex）
权值线段树中,seg[id]的l,r代表这个节点 代表了l~r这个值域的信息。而不是数组中的下标
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define Acode ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define int long long
const int N = 2e5 + 10;
vector<pair<int, int>> qu[N];
int n, q;
int a[N];
int ans[N];
struct info
{
int minv;
};
struct node
{
info val;
} seg[N << 2];
info operator+(const info &a, const info &b)
{
info c;
c.minv = min(a.minv, b.minv);
return c;
}
void up(int id) // up的时候lazy标记不用管，因为合并的两个区间的信息info是正确的
{
seg[id].val = seg[id << 1].val + seg[id << 1 | 1].val;
}
void change(int id, int l, int r, int x, int w)
{
if (l == r)
{
seg[id].val.minv = w;
return;
}
int mid = l + r >> 1;
if (x <= mid)
change(id << 1, l, mid, x, w);
else
change(id << 1 | 1, mid + 1, r, x, w);
up(id);
}
int search1(int id, int l, int r, int d)
{
if (l == r)
return l;
int mid = l + r >> 1;
if (seg[id << 1].val.minv < d)
return search1(id << 1, l, mid, d);
else
return search1(id << 1 | 1, mid + 1, r, d);
}
void solve()
{
cin >> n >> q;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
a[i] = min(a[i], n + 1);
}
for (int i = 1; i <= q; i++)
{
int l, r;
cin >> l >> r;
qu[r].push_back({l, i});
}
for (int r = 1; r <= n; r++)
{
change(1, 0, n + 1, a[r], r);
for (auto it : qu[r])
{
int l = it.first;
int id = it.second;
ans[id] = search1(1, 0, n + 1, l);
}
}
for (int i = 1; i <= q; i++)
{
cout << ans[i] << endl;
}
}
signed main()
{
Acode;
int T = 1;
while (T--)
{
solve();
}
return 0;
}