CC BY 4.0 （除特别声明或转载文章外）
如果这篇博客帮助到你，可以请我喝一杯咖啡~
Best Subsequence
贪心。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 9;
set<pair<int, int>> q;
int n, k, a[N], pre[N], nxt[N];
int main()
{
scanf("%d%d", &n, &k);
for (int i = 0; i < n; ++i)
{
scanf("%d", &a[i]);
pre[i] = (i - 1 + n) % n;
nxt[i] = (i + 1) % n;
}
for (int i = 0; i < n; ++i)
q.emplace(a[i] + a[nxt[i]], i);
while (q.size() > k)
{
int x = q.rbegin()->second;
if (a[x] < a[nxt[x]])
x = nxt[x];
q.erase({a[x] + a[nxt[x]], x});
q.erase({a[pre[x]] + a[x], pre[x]});
q.emplace(a[pre[x]] + a[nxt[x]], pre[x]);
nxt[pre[x]] = nxt[x];
pre[nxt[x]] = pre[x];
}
printf("%d", q.rbegin()->first);
}
现场打了个二分+DP+离散化+树状数组前缀最小值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
const int N = 2e5 + 9, INF = 2e9 + 9;
int n, k, a[N];
struct Ranker : vector<ll>
{
void init() { sort(begin(), end()), resize(unique(begin(), end()) - begin()); }
int ask(ll x) const { return lower_bound(begin(), end(), x) - begin(); }
} rk;
struct Fenwick : vector<ll>
{
Fenwick(int n) : vector<ll>(n, 0) {}
ll ask(int x)
{
ll r = 0;
for (; x; x -= x & -x)
r = max(r, at(x));
return r;
}
void upd(int x, ll val)
{
for (; x < size(); x += x & -x)
at(x) = max(at(x), val);
}
};
int ok(int m)
{
Fenwick t(rk.size() + 9);
t.upd(rk.ask(a[1]) + 2, 1);
for (int i = 2; i <= n; ++i)
if (m - a[i] > 0)
{
ll now = t.ask(rk.ask(m - a[i] + 1) - 1 + 2);
if (now > 0)
{
if (m - a[i] >= a[1] && now + 1 >= k)
return 1;
t.upd(rk.ask(a[i]) + 2, now + 1);
}
}
return 0;
}
int bs(int b, int e)
{
if (e - b < 2)
return e;
int m = b + (e - b >> 1);
return ok(m) ? bs(b, m) : bs(m, e);
}
int main()
{
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; ++i)
scanf("%d", &a[i]), rk.push_back(a[i]);
rk.push_back(INF);
rk.push_back(-INF);
rk.init();
rotate(a + 1, min_element(a + 1, a + n + 1), a + n + 1);
printf("%d", bs(0, INF));
}
Cool Pairs
构造。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 3e5 + 9;
ll n, k, a[N], b[N], c[N];
int main()
{
scanf("%lld%lld", &n, &k);
for (ll i = 0, x; i < n; ++i)
{
scanf("%lld", &x), --x;
a[x] = i - n;
b[x] = n;
}
for (ll i = 0, x; k && i < n; ++i)
{
scanf("%lld", &x), --x;
if (k >= x)
{
k -= x;
b[x] = -n;
}
else
{
copy(a, a + x, c);
nth_element(c, c + k - 1, c + x);
b[x] = -c[k - 1] - 1;
k = 0;
}
}
printf("Yes\n");
for (ll i = 0; i < n; ++i)
printf("%lld ", a[i]);
printf("\n");
for (ll i = 0; i < n; ++i)
printf("%lld ", b[i]);
}
Free Edges
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9;
vector<int> g[N];
int n, m, vis[N];
void dfs(int u)
{
vis[u] = 1;
for (int to : g[u])
if (!vis[to])
dfs(to);
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 0, x, y; i < m; ++i)
{
scanf("%d%d", &x, &y);
g[x].push_back(y);
g[y].push_back(x);
}
for (int i = 1; i <= n; ++i)
if (!vis[i])
dfs(i), ++m;
printf("%d", m - n);
}