A - Two Subsequences(语言基础)
最小字符+剩余部分
B - Divine Array (暴力)
看题解操作次数上界是(O(log n))的，但是(O(n^2))能过。直接暴力。
C - Array Elimination(思维)
如果要把某一位全部减为0，那么就是把这一位为1的全部与起来。但是如果要把全部位都减掉，意味(k)很关键，每一位的1的个数必须是(k)的倍数。因此答案就是每一位1的个数的(gcd)的所有因子。
D - Frog Traveler(set，bfs)
如果(a)能跳到(b)并从(b)滑倒(c)，那么(a)向(c)连一条边，意味着(a)能一次跳到达(c)。可以发现每个(a)对应都是一段连续的区间。因此直接用set维护未访问的结点，然后从(n)开始bfs，访问过的点直接从set中删除。这个操作也能用并查集实现。时间复杂度(O(n log n))。
#include <bits/stdc++.h>
#define endl '
'
#define IOS std::ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define mp make_pair
#define seteps(N) fixed << setprecision(N)
typedef long long ll;
using namespace std;
/*-----------------------------------------------------------------*/
ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
#define INF 0x3f3f3f3f
const int N = 3e5 + 10;
const double eps = 1e-5;
int d[N];
set<int> id;
int a[N], b[N];
typedef pair<int, int> PII;
PII range[N];
int fa[N];
int main() {
IOS;
memset(fa, -1, sizeof fa);
memset(d, -1, sizeof d);
int n;
cin >> n;
d[n] = 0;
id.insert(0);
for(int i = 1; i<= n; i++) {
id.insert(i);
cin >> a[i];
}
for(int i = 1; i <= n; i++) {
cin >> b[i];
}
for(int i = 1; i <= n; i++) {
int tar = i + b[i];
range[i] = {tar - a[tar], tar};
}
d[n] = 0;
queue<int> q;
q.push(n);
id.erase(n);
while(!q.empty()) {
int cur = q.front();
q.pop();
int l = range[cur].first, r = range[cur].second;
auto tar = id.lower_bound(l);
while(tar != id.end() && *tar <= r) {
d[*tar] = d[cur] + 1;
fa[*tar] = cur;
q.push(*tar);
int nt = *tar + 1;
id.erase(tar);
tar = id.lower_bound(nt);
// cout << *tar << " ";
}
// cout << endl;
}
if(d[0] == -1) cout << -1 << endl;
else {
int cur = 0;
vector<int> ans;
while(cur != -1) {
ans.push_back(cur);
cur = fa[cur];
}
ans.pop_back();
reverse(ans.begin(), ans.end());
cout << d[0] << endl;
for(int i = 0; i < ans.size(); i++) cout << ans[i] << " ";
cout << endl;
}
}
E - Optimal Insertion (贪心，线段树)
首先对(b)排序，这样肯定是最优的。然后(b)插入(a)还是(a)插入(b)其实没区别，于是假设是(b)插入(a)，(p_i)代表(b_i)放在了(a_i)到(a_{i+1})之间；对于放在(a)结尾的(b_i)，令(p_i=n+1)。
答案除了(a)本身之外，还有(b)插入带来的。(a)的很好求，主要是求(b)的贡献。贪心地考虑一下，就是从左往右找到第一个产生逆序对最少的位置，插入(b_i)，要保证(p_i le p_{i+1})，直到插完为止。
因此可以用线段树维护对于(b_i)放在每个位置((p))产生的逆序对，整个区间中值最小的位置就是所要放(b_i)的位置。维护的方法见代码，同时可以发现，由于(b_i)是递增的，这个最小的位置也是递增的，同时保证了(b_i)产生逆序对最少以及(p_i le p_{i+1})(这样(b_i)之间也不会产生逆序对)。
#include <bits/stdc++.h>
#define endl '
'
#define IOS std::ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define mp make_pair
#define seteps(N) fixed << setprecision(N)
typedef long long ll;
using namespace std;
/*-----------------------------------------------------------------*/
ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
#define INF 0x3f3f3f3f
const int N = 1e6 + 10;
const double eps = 1e-5;
int mi[N << 2], lazy[N << 2];
void pushdown(int rt) {
if(lazy[rt]) {
lazy[rt << 1] += lazy[rt];
lazy[rt << 1 | 1] += lazy[rt];
mi[rt << 1] += lazy[rt];
mi[rt << 1 | 1] += lazy[rt];
lazy[rt] = 0;
}
}
void build(int l, int r, int rt) {
if(l == r) {
mi[rt] = lazy[rt] = 0;
return ;
}
int mid = (l + r) / 2;
build(l, mid, rt << 1);
build(mid + 1, r, rt << 1 | 1);
mi[rt] = lazy[rt] = 0;
}
void upd(int l, int r, int L, int R, int val, int rt) {
if(l >= L && r <= R) {
mi[rt] += val;
lazy[rt] += val;
return ;
}
int mid = (l + r) / 2;
pushdown(rt);
if(L <= mid) upd(l, mid, L, R, val, rt << 1);
if(R > mid) upd(mid + 1, r, L, R, val, rt << 1 | 1);
mi[rt] = min(mi[rt << 1], mi[rt << 1 | 1]);
}
int a[N], b[N];
vector<int> pos[N << 1];
int cnt[N << 1];
int tarr[N << 1];
int n, m, mx;
int lowbit(int x) {
return x&-x;
}
void add(int p, int val) {
while(p <= mx) {
tarr[p] += val;
p += lowbit(p);
}
}
int sum(int p) {
int res = 0 ;
while(p) {
res += tarr[p];
p -= lowbit(p);
}
return res;
}
int main() {
IOS;
int t;
cin >> t;
while(t--) {
vector<int> num;
cin >> n >> m;
build(1, n + 1, 1);
for(int i = 1; i <= n; i++) cin >> a[i], num.push_back(a[i]);
for(int i = 1; i <= m; i++) cin >> b[i], num.push_back(b[i]);
sort(num.begin(), num.end());
num.erase(unique(num.begin(), num.end()), num.end());
mx = num.size();
for(int i = 1; i <= mx; i++) pos[i].clear(), tarr[i] = 0, cnt[i] = 0;
// 离散化
for(int i = 1; i <= n; i++) a[i] = lower_bound(num.begin(), num.end(), a[i]) - num.begin() + 1;
for(int i = 1; i <= m; i++) b[i] = lower_bound(num.begin(), num.end(), b[i]) - num.begin() + 1;
ll ans = 0;
for(int i = 1; i <= n; i++) pos[a[i]].push_back(i), add(a[i], 1), ans += sum(mx) - sum(a[i]), upd(1, n + 1, i + 1, n + 1, 1, 1); // pos是a的值对应的位置，用于优化
for(int i = 1; i <= m; i++) cnt[b[i]]++; // 统计b值的个数，由于有相同的值，所以用这种方法。
for(int i = 1; i <= mx; i++) { // 枚举b
for(int p : pos[i]) upd(1, n + 1, p + 1, n + 1, -1, 1);
for(int p : pos[i - 1]) upd(1, n + 1, 1, p, 1, 1);
ans += 1ll * cnt[i] * mi[1];
}
cout << ans << endl;
}
}
F - Difficult Mountain(dp，优化)
分析一下，有一下几种情况：
- (s <p)，不统计
- (a le p)且(s ge p)，直接统计，不影响结果
- (a>p)且(sge p)，单独讨论。
因此只需计算怎么排列情况3的人，使得答案最大。
假设最优情况是选择了集合(S_i={a_i,s_i})，其中最大的(a)是(a_i)。那么对于集合中所有(s ge a_i)的人，它们排在(i)之后是最优的，而(s < a_i)的人必须排在(i)之前。排在(i)前面存在某个(j)，有(a_jle a_i)，而(j)是排在(i)前面元素的集合(S_j={a_j,s_j}sub S_i)，中(a)最大的。(S_i-S_j)中剩下这些人都是满足(s ge a_i)且(age a_j)，排在(i)的后面。显然这个满足最优子结构。
因此先对(a)排序，(f(i))代表(S_i)的大小，即(f(i)=|S_i|)。有如下转移方程
[f(i)=max_{j=0}^{i-1}(f(j)+cal(j+1,i-1,i))[s_ige a_j]
]
其中
[cal(l,r,p)=sumlimits_{i=l}^{r}[s_ige a_p]
]
最后答案就是(max(f(i)))加上情况2。
令(sum(l,p)=sumlimits_{i=0}^{l}[s_ige a_p])，可得
[f(i)-sum(i-1,i)=max_{j=0}^{a_jle s_i}(f(j)-sum(j,i))
]
用线段树维护更新(maxlimits_{j=0}^{a_jle s_i}(f(j)-sum(j,i)))，使用和E题类似的方法优化即可。
#include <bits/stdc++.h>
#define endl '
'
#define IOS std::ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define mp make_pair
#define seteps(N) fixed << setprecision(N)
typedef long long ll;
using namespace std;
/*-----------------------------------------------------------------*/
ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
#define INF 0x3f3f3f3f
const int N = 1e6 + 10;
const double eps = 1e-5;
typedef pair<int, int> PII;
int s[N], a[N];
PII arr[N];
bool ok[N];
vector<int> pos[N];
int mx[N << 2], lazy[N << 2];
void pushdown(int rt) {
if(lazy[rt]) {
lazy[rt << 1] += lazy[rt];
lazy[rt << 1 | 1] += lazy[rt];
mx[rt << 1] += lazy[rt];
mx[rt << 1 | 1] += lazy[rt];
lazy[rt] = 0;
}
}
void upd(int l, int r, int L, int R, int val, int rt) {
if(l >= L && r <= R) {
mx[rt] += val;
lazy[rt] += val;
return ;
}
pushdown(rt);
int mid = (l + r) / 2;
if(mid >= L) upd(l, mid, L, R, val, rt << 1);
if(mid < R) upd(mid + 1, r, L, R, val, rt << 1 | 1);
mx[rt] = max(mx[rt << 1], mx[rt << 1 | 1]);
}
int que(int l, int r, int L, int R, int rt) {
if(l >= L && r <= R) {
return mx[rt];
}
pushdown(rt);
int res = -INF;
int mid = (l + r) / 2;
if(mid >= L) res = max(res, que(l, mid, L, R, rt << 1));
if(mid < R) res = max(res, que(mid + 1, r, L, R, rt << 1 | 1));
mx[rt] = max(mx[rt << 1], mx[rt << 1 | 1]);
return res;
}
int dp[N];
bool cmp(const PII& a, const PII &b) {
return a.first < b.first;
}
int main() {
IOS;
vector<int> num;
int n, d;
cin >> n >> d;
num.push_back(d);
for(int i = 1; i <= n; i++) {
cin >> s[i] >> a[i];
num.push_back(s[i]);
num.push_back(a[i]);
}
sort(num.begin(), num.end());
num.erase(unique(num.begin(), num.end()), num.end());
d = lower_bound(num.begin(), num.end(), d) - num.begin() + 1;
for(int i = 1; i <= n; i++) {
s[i] = lower_bound(num.begin(), num.end(), s[i]) - num.begin() + 1;
a[i] = lower_bound(num.begin(), num.end(), a[i]) - num.begin() + 1;
}
int ans = 0;
for(int i = 1; i <= n; i++) {
if(a[i] <= d && s[i] >= d) ans++;
if(a[i] > d && s[i] >= d) ok[i] = true;
}
int m = 0;
for(int i = 1; i <= n; i++) {
if(ok[i]) {
arr[++m] = {a[i], s[i]};
}
}
arr[0].first = d;
sort(arr + 1, arr + 1 + m, cmp);
for(int i = 1; i <= m; i++) {
pos[arr[i].second].push_back(i);
upd(0, m, i, m, -1, 1);
}
int cur = 1, mxa = 0;
for(int i = 1; i <= m; i++) {
while(cur < arr[i].first) {
for(int p : pos[cur]) {
upd(0, m, p, m, 1, 1);
}
cur++;
}
int tarp = upper_bound(arr + 1, arr + 1 + i, PII{arr[i].second, INF}, cmp) - arr - 1;
dp[i] = que(0, m, 0, tarp, 1) - que(0, m, i - 1, i - 1, 1) + dp[i - 1] + 1;
upd(0, m, i, i, dp[i], 1);
mxa = max(mxa, dp[i]);
}
ans += mxa;
cout << ans << endl;
}