2023/11/13
codeforces 906(div2) 补题
A. Sorting with Twos
题意：
给一个长度为n的数组，可以做任意次以下操作：选择一个整数m，将1-2^m 的数减1。若能使数组变为一个单调递增的数组则输出YES，否则输出NO
思路：一个区间的右边界和他 的右边是无所谓大小的，因为我们可以整段减来使其一定单增，但是整段和整段之间的数我们就无法改变他们的的相对大小，需要他们原本就单增。
B. Deja Vu
题意：
给一个长度为n的数组，做q次询问，若这个数能被2xi整除，则这个数加上2xi-1
思路：赛时想的是O（q+logn*n）的做法，看了题解发现有O（n *logq）的做法。
先说我的，考虑到a数据的值的范围最大1e9那么，最多有30个数能更新他们（每次更新之后），大于等于本次q的数不再有用。所以我维护一个最大可更新值，那个O（n）的扫一边q数组，遇到合法的就O（n）的扫一边a数组。
学到q是可以去重加变成一个单调递减的数组的，那么出现单调性，我们对于每一个a在q中二分他首次可以被更新的位置，那么之后的q他都可以吃到（预处理一个后缀和就能O（1）得到贡献）
C. Smilo and Monsters（贪心）
思路：双指针模拟即可，边界不是很会调，要仔细的模拟过，赛时wa一发过了
D. Suspicious logarithms（数学+分块）（补）
思路：因为我们要做两次幂次运算。那么我们必须确定一个底才能讨论。自然是第一个f(x),因为第二个g(x)是通过f(x)得出的。通过观察，发现f在2的幂次的区间内是一样的（显然）。随后可以打表知道同一个f，他最多只有两个值，那么就简单了。
做法：枚举x幂次的每一个区间，这样f固定。那么就来算g就行
这题有点卡常，放一份对的，但是极限数据被卡了的代码
#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 mod = 1e9 + 7;
int qpow(int a, int b)
{
int res = 1;
while (b)
{
if (b & 1)
res = res * a;
b >>= 1;
a = a * a;
}
return res;
}
int cal(int x)
{
int ans = 0;
for (int i = 2; (1LL << i) <= x; i++)
{
int l = (1LL << i);
int r = min((1LL << (i + 1)) - 1, x);
int cnt = 0, cnt1 = 0;
int xx = l;
while (xx >= i)
{
cnt++;
xx /= i;
}
xx = r;
while (xx >= i)
{
cnt1++;
xx /= i;
}
if (cnt == cnt1)
{
ans = (ans + (r - l + 1) % mod * cnt % mod) % mod;
}
else
{
int tt = qpow(i, cnt1);
ans = (ans + (tt - l) % mod * cnt % mod + (r - tt + 1) % mod * cnt1 % mod) % mod;
}
}
return ans;
}
void solve()
{
int l, r;
cin >> l >> r;
cout << (cal(r) - cal(l - 1) + mod) % mod << endl;
}
signed main()
{
Acode;
int T = 1;
cin >> T;
while (T--)
{
solve();
}
return 0;
}
AtCoder Beginner Contest 328
赛时写了5题，网上没找到好的F的题解，先放一放吧，果然打得好就补的少
D - Take ABC
思路：类似这种题可以用一个栈来模拟，时间复杂度为O（n）
上午 vpCodeforces Round 904 (Div. 2) solve(2/5)
C题想了个假的做法，然后也没什么好的方法，这个时候电脑也没电了，就录了一个多小时
https://www.bilibili.com/video/BV1E94y137PZ/?vd_source=7b3be65640481106bef731ef741a960f
Codeforces Round 904 (Div. 2) 补题
A. Simple Design
简单签到
B. Haunted House
如果一个数可以被2^i的整除的话，那么从第0位到第i-1位都要为零。那么问题就转化成将1都移到i-1位的左边的问题。因为会有阻隔和格子不够的问题，我们直接考虑0，这样会简单很多。，然后走一个零的后缀和就行了
C. Medium Design （补）
贪心思想只能感性的证明
思路：赛时只想到把起点1处理到0，然后去求最小值。这样被自己hack了，因为可能只有1有值，换言之，1点必须保留。遇到这种情况，我们就再让m为最小值。证明：如果覆盖1点也覆盖到了最大值，那么删除不影响，是要避免有地方就为0，这样覆盖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 l[N], r[N];
vector<int> alls;
int s[N];
int find(int x)
{
return lower_bound(alls.begin(), alls.end(), x) - alls.begin() + 1;
}
void solve()
{
alls.clear();
int n, m;
cin >> n >> m;
for (int i = 0; i <= 2 * n + 10; i++)
s[i] = 0;
for (int i = 1; i <= n; i++)
{
cin >> l[i] >> r[i];
alls.push_back(l[i]);
alls.push_back(r[i]);
}
alls.push_back(1);
alls.push_back(m);
sort(alls.begin(), alls.end());
alls.erase(unique(alls.begin(), alls.end()), alls.end());
for (int i = 1; i <= n; i++)
{
int x = find(l[i]);
int y = find(r[i]);
if (x == 1)
continue;
s[x]++;
s[y + 1]--;
}
for (int i = 1; i <= 2 * n; i++)
{
s[i] = s[i - 1] + s[i];
}
int ans = 0;
for (int i = 0; i <= 2 * n; i++)
{
ans = max(ans, s[i]);
s[i] = 0;
}
// cerr << ans << endl;
for (int i = 1; i <= n; i++)
{
int x = find(l[i]);
int y = find(r[i]);
// cerr << l[i] << " " << r[i] << " " << y << " " << alls.size() - 1 << endl;
if (y == alls.size())
continue;
s[x]++;
s[y + 1]--;
}
for (int i = 1; i <= 2 * n; i++)
{
s[i] = s[i - 1] + s[i];
}
for (int i = 0; i <= 2 * n; i++)
{
ans = max(ans, s[i]);
}
cout << ans << endl;
}
signed main()
{
Acode;
int T = 1;
cin >> T;
while (T--)
{
solve();
}
return 0;
}
第二种：优先队列+线段树的做法（补）
算是复习了线段树，好久没写了
思路：我们枚举左端点作为最大值，把区间按照左端点排序来选择，然后按照右端点升序来决定不选。
最后用线段树来维护区间内的最大值，最小值。 注意：需要离散化时的区间最值，需要把两个端点（1，m）也加入离散化数组，否则会导致区间缺失！ build建树的时候（1，1，alls.size()）;alls.size代表总的区间
#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 = 4e5 + 10;
int l[N], r[N];
vector<int> alls;
pair<int, int> s[N];
vector<int> lt;
int find(int x)
{
return lower_bound(alls.begin(), alls.end(), x) - alls.begin() + 1;
}
struct info
{
int maxx, minn;
int lazy = 0;
} seg[N << 2];
info operator+(const info &a, const info &b)
{
info c;
c.maxx = max(a.maxx, b.maxx);
c.minn = min(a.minn, b.minn);
return c;
}
void up(int id)
{
seg[id] = seg[id << 1] + seg[id << 1 | 1];
}
void build(int id, int l, int r)
{
seg[id].lazy = 0;
if (l == r)
{
seg[id].maxx = 0;
seg[id].minn = 0;
return;
}
int mid = l + r >> 1;
build(id << 1, l, mid);
build(id << 1 | 1, mid + 1, r);
up(id);
}
void settag(int id, int val)
{
seg[id].lazy += val;
seg[id].maxx += val;
seg[id].minn += val;
}
void down(int id)
{
if (!seg[id].lazy)
return;
settag(id << 1, seg[id].lazy);
settag(id << 1 | 1, seg[id].lazy);
seg[id].lazy = 0;
}
void modify(int id, int l, int r, int ql, int qr, int val)
{
if (ql > r || qr < l)
return;
if (ql <= l && r <= qr)
{
// cout << id << endl;
// cout << val << " REERERER" << endl;
settag(id, val);
return;
}
down(id);
int mid = l + r >> 1;
modify(id << 1, l, mid, ql, qr, val);
modify(id << 1 | 1, mid + 1, r, ql, qr, val);
up(id);
}
info query(int id, int l, int r, int ql, int qr)
{
if (ql <= l && r <= qr)
{
return seg[id];
}
int mid = l + r >> 1;
down(id);
if (qr <= mid)
return query(id << 1, l, mid, ql, qr);
else if (ql > mid)
return query(id << 1 | 1, mid + 1, r, ql, qr);
else
return query(id << 1, l, mid, ql, qr) + query(id << 1 | 1, mid + 1, r, ql, qr);
}
void solve()
{
alls.clear();
lt.clear();
int n, m;
cin >> n >> m;
alls.push_back(1);
alls.push_back(m);
for (int i = 1; i <= n; i++)
{
cin >> l[i] >> r[i];
lt.push_back(l[i]);
s[i] = {l[i], r[i]};
alls.push_back(l[i]);
alls.push_back(r[i]);
// cerr << l[i] << " " << r[i] << endl;
}
// cerr << seg[5].maxx << endl;
sort(alls.begin(), alls.end());
alls.erase(unique(alls.begin(), alls.end()), alls.end());
sort(s + 1, s + 1 + n);
build(1, 1, alls.size());
sort(lt.begin(), lt.end());
int ans = 0, pos = 1;
for (int i = 1; i <= n; i++)
{
s[i] = {find(s[i].first), find(s[i].second)};
// cerr << s[i].first << " " << s[i].second << endl;
}
for (int i = 0; i < lt.size(); i++)
{
lt[i] = find(lt[i]);
}
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
for (int i = 0; i < lt.size(); i++)
{
int x = lt[i];
while (s[pos].first <= x && s[pos].second >= x && pos <= n)
{
modify(1, 1, alls.size(), s[pos].first, s[pos].second, 1);
q.push({s[pos].second, s[pos].first});
pos++;
}
while (q.size() && q.top().first < x)
{
int a = q.top().second;
int b = q.top().first;
q.pop();
modify(1, 1, alls.size(), a, b, -1);
}
ans = max(ans, query(1, 1, alls.size(), 1, alls.size()).maxx - query(1, 1, alls.size(), 1, alls.size()).minn);
}
cout << ans << endl;
}
signed main()
{
Acode;
int T = 1;
cin >> T;
while (T--)
{
solve();
}
return 0;
}
bitset学习
bitset的申明要指明长度 ,通常可以除以32的复杂度。
bitset<length> bi
//bi[2]=1; 这样就能将第二位赋值为1
b1 = b2 & b3;//按位与
b1 = b2 | b3;//按位或
b1 = b2 ^ b3;//按位异或
b1 = ~b2;//按位补
b1 = b2 << 3;//移位
int one = b1.count();//统计1的个数
例题：AcWing 164. 可达性统计
原本对每一个点都要开n长度的数组，这样转移的复杂度是O(m*n);
开bitset可以变成O(n*m/32);
思路比较简单：反拓扑即可
#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;
const int M = 3e4 + 10;
vector<int> g[N];
bitset<M> f[N];
int du[N];
void solve()
{
int n, m;
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
int u, v;
cin >> u >> v;
g[v].push_back(u);
du[u]++;
}
queue<int> q;
for (int i = 1; i <= n; i++)
{
if (!du[i])
q.push(i);
}
while (q.size())
{
int u = q.front();
q.pop();
f[u][u] = 1;
for (auto v : g[u])
{
f[v] |= f[u];
du[v]--;
if (!du[v])
q.push(v);
}
}
for (int i = 1; i <= n; i++)
{
cout << f[i].count() << endl;
}
}
signed main()
{
Acode;
int T = 1;
// cin >> T;
while (T--)
{
solve();
}
return 0;
}