传送门
Codeforces Round #772 (Div. 2)
A
按位考虑，若存在第 k k k 位为 1 1 1 的元素，则可以用这个元素将其余元素的第 k k k 位变为 0 0 0；为满足操作的约束，存在 1 1 1 的每个数位至少需要保留一个元素。故最小和为所有元素的按位或。总时间复杂度 O ( n ) O(n) O(n)。
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
typedef long long ll;
const int MAXN = 1E2 + 5;
int T, N, A[MAXN];
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> T;
while (T--)
{
cin >> N;
for (int i = 0; i < N; ++i)
cin >> A[i];
int res = 0;
for (int i = 0; i < N; ++i)
res |= A[i];
cout << res << '\n';
}
return 0;
}
B
改变任一元素至多影响其左右元素。当某个元素 a i a_i ai 相邻元素都是局部最大时，取 a i ′ = max ( a i − 1 , a i + 1 ) a^{\prime}_i=\max(a_{i-1},a_{i+1}) ai′=max(ai−1,ai+1) 即可消去两个局部最大元素；其余情况，取局部最大元素为左右元素的最大值即可。总时间复杂度 O ( n ) O(n) O(n)。
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
typedef long long ll;
const int MAXN = 2E5 + 5;
int T, N, A[MAXN];
bool conf[MAXN];
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> T;
while (T--)
{
cin >> N;
for (int i = 0; i < N; ++i)
cin >> A[i], conf[i] = 0;
for (int i = 1; i < N - 1; ++i)
conf[i] = A[i] > A[i - 1] && A[i] > A[i + 1];
int res = 0;
for (int i = 0; i < N; ++i)
{
if (!conf[i])
continue;
if (i + 2 < N && conf[i + 2])
++res, conf[i + 2] = 0, A[i + 1] = max(A[i], A[i + 2]);
else
++res, A[i] = max(A[i - 1], A[i + 1]);
}
cout << res << '\n';
for (int i = 0; i < N; ++i)
cout << A[i] << (i + 1 == N ? '\n' : ' ');
}
return 0;
}
C
由于操作涉及的三个元素满足索引值的单调递增性，那么索引值最大的两个元素不能被修改。若 a n − 1 > a n a_{n-1}>a_n an−1>an 则不可能使数组单调非降； 反之，若 a n > = 0 a_n>=0 an>=0，取所有可以被修改的元素为 a n − 1 − a n a_{n-1}-a_n an−1−an 即可；若 a n < 0 a_n<0 an<0，则涉及它的操作不可能使数组满足单调非降性，那么将其删除后递归地处理即可。总时间复杂度 O ( n ) O(n) O(n)。
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
typedef long long ll;
const int MAXN = 2E5 + 5;
int T, N, A[MAXN];
void solve()
{
for (int i = N - 2; i >= 0; --i)
{
if (A[i] > A[i + 1])
{
cout << "-1\n";
return;
}
if (A[i + 1] >= 0)
{
cout << i << '\n';
for (int j = 0; j < i; ++j)
cout << j + 1 << ' ' << i + 1 << ' ' << i + 2 << '\n';
return;
}
}
cout << "0\n";
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> T;
while (T--)
{
cin >> N;
for (int i = 0; i < N; ++i)
cin >> A[i];
solve();
}
return 0;
}
D
元素 x x x 所生成的元素可以表示为 x x x 的二进制表示后添加数个 1 1 1 或 00 00 00。为了避免重复计数，将可以被数组中其他元素生成的元素删除；具体而言，不断删除元素二进制表示下，末尾的 1 1 1 或 00 00 00，判断余下的位构成的元素是否在数组中即可。时间复杂度 O ( n log n log max ( a i ) ) O\big(n\log n\log\max(a_i)\big) O(nlognlogmax(ai))
求严格小于
2
p
2^p
2p 的元素个数，则元素为长度至多位
p
p
p 的任意数字。考虑元素
x
x
x 及其生成的严格小于
2
p
2^p
2p 的元素个数，设
x
x
x 二进制表示下长度为
l
e
n
len
len，则末尾需要至多长度为
n
=
p
−
l
e
n
n=p-len
n=p−len 的
1
1
1 或
00
00
00 来补。那么元素的个数为
∑
0
≤
j
≤
n
,
0
≤
2
k
≤
j
(
j
−
k
k
)
=
∑
0
≤
2
k
≤
n
∑
2
k
≤
j
≤
n
(
j
−
k
k
)
\sum\limits_{0\leq j\leq n,0\leq 2k\leq j}\binom{j-k}{k}=\sum\limits_{0\leq 2k\leq n}\sum\limits_{2k\leq j\leq n}\binom{j-k}{k}
0≤j≤n,0≤2k≤j∑(kj−k)=0≤2k≤n∑2k≤j≤n∑(kj−k) 代入
i
=
j
−
k
i=j-k
i=j−k 得到
∑
0
≤
2
k
≤
n
∑
k
≤
i
≤
n
−
k
(
i
k
)
=
∑
0
≤
2
k
≤
n
[
∑
0
≤
i
≤
n
−
k
(
i
k
)
−
∑
0
≤
i
≤
k
−
1
(
i
k
)
]
=
∑
0
≤
2
k
≤
n
(
n
−
k
+
1
k
+
1
)
\sum\limits_{0\leq 2k\leq n}\sum\limits_{k\leq i\leq n-k}\binom{i}{k}=\sum\limits_{0\leq 2k\leq n}\left[\sum\limits_{0\leq i\leq n-k}\binom{i}{k}-\sum\limits_{0\leq i\leq k-1}\binom{i}{k}\right]=\sum\limits_{0\leq 2k\leq n}\binom{n-k+1}{k+1}
0≤2k≤n∑k≤i≤n−k∑(ki)=0≤2k≤n∑[0≤i≤n−k∑(ki)−0≤i≤k−1∑(ki)]=0≤2k≤n∑(k+1n−k+1)
不同的
l
e
n
len
len 仅有
log
max
(
a
i
)
\log\max(a_i)
logmax(ai) 种，统计每一种的元素数量，预处理逆元，就可以
O
(
p
)
O(p)
O(p) 统计答案。
官方题解提供了一种简洁的 D P DP DP 做法。二进制表示末尾添加 1 1 1 或 00 00 00，则数位增加 1 1 1 或 2 2 2，得到形如斐波那契数列的递推式 d p i = d p i − 1 + d p i − 2 dp_i=dp_{i-1}+dp_{i-2} dpi=dpi−1+dpi−2。这样的递推式可以通过矩阵快速幂等方法进行优化，故当 p p p 的数量级增大，也可以高效地解决问题。
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
typedef long long ll;
const int MAXN = 2E5 + 5, MOD = 1E9 + 7;
int N, P, A[MAXN], len_num[32];
bool del[MAXN];
ll fac[MAXN], invf[MAXN];
ll qpow(ll x, int n)
{
ll res = 1;
x %= MOD;
while (n)
{
if (n & 1)
res = res * x % MOD;
x = x * x % MOD, n >>= 1;
}
return res;
}
ll C(ll n, ll m)
{
if (m == 0)
return 1;
if (n < m || m < 0)
return 0;
return fac[n] * invf[m] % MOD * invf[n - m] % MOD;
}
int get(int x)
{
int len = 0;
while (x)
++len, x >>= 1;
return len;
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> N >> P;
for (int i = 0; i < N; ++i)
cin >> A[i];
sort(A, A + N);
for (int i = 0; i < N; ++i)
{
int a = A[i];
while (a)
{
bool upd = 0;
if (a & 1)
a >>= 1, upd = 1;
else if (!(a & 1) && !(a >> 1 & 1))
a >>= 2, upd = 1;
if (!upd)
break;
if (*lower_bound(A, A + N, a) == a)
{
del[i] = 1;
break;
}
}
}
for (int i = 0; i < N; ++i)
if (!del[i])
++len_num[get(A[i])];
fac[0] = invf[0] = 1;
for (int i = 1; i <= P; ++i)
fac[i] = fac[i - 1] * i % MOD, invf[i] = qpow(fac[i], MOD - 2);
ll res = 0;
for (int len = 1; len < 32; ++len)
{
ll t = 0;
int n = P - len;
for (int k = 0; 2 * k <= n; ++k)
t += C(n - k + 1, k + 1);
t %= MOD;
res += t * len_num[len] % MOD;
}
cout << res % MOD << '\n';
return 0;
}
E 补题
题中的两类关系，需要注意的是，无论速度如何，双方都能相遇或不相遇。则关系 1 1 1 只可能为一方在左侧方向为左，一方在右侧方向为右；关系 2 2 2 只可能为一方在左侧方向为右，一方在右侧方向为左。
此时两类关系涉及相对位置关系与各自方向的关系，难以同时处理。不妨先处理方向关系，即判断是否存在合法的赋值，使车辆向左或向右。可以通过并查集或二分图染色进行判断。
赋予车辆一组合法的方向，此时相相对位置关系就容易处理了。对于左侧的车辆，向右侧的车辆连一条有向边，判断是否满足拓扑序即可。总时间复杂度 ( n + m ) (n+m) (n+m)。
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
typedef long long ll;
const int MAXN = 2E5 + 5;
int N, M, col[MAXN], deg[MAXN], pos[MAXN];
vector<int> G[MAXN];
struct node
{
int u, v, type;
} ns[MAXN];
void dfs(int u, int c)
{
col[u] = c;
for (auto v : G[u])
if (col[v] == -1)
dfs(v, c ^ 1);
}
bool color()
{
memset(col, -1, sizeof(col));
for (int u = 0; u < N; ++u)
if (col[u] == -1)
dfs(u, 0);
for (int u = 0; u < N; ++u)
for (auto v : G[u])
if (col[u] == col[v])
return 0;
return 1;
}
bool topsort()
{
memset(deg, 0, sizeof(deg));
for (int u = 0; u < N; ++u)
for (auto v : G[u])
++deg[v];
queue<int> q;
vector<int> ps;
for (int u = 0; u < N; ++u)
if (!deg[u])
q.push(u), ps.pb(u);
while (q.size())
{
int u = q.front();
q.pop();
for (auto v : G[u])
if (!--deg[v])
q.push(v), ps.pb(v);
}
if ((int)ps.size() < N)
return 0;
for (int i = 0; i < N; ++i)
pos[ps[i]] = i;
return 1;
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> N >> M;
for (int i = 0; i < M; ++i)
{
auto &t = ns[i];
cin >> t.type >> t.u >> t.v;
--t.u, --t.v;
G[t.u].pb(t.v), G[t.v].pb(t.u);
}
if (!color())
{
cout << "NO\n";
return 0;
}
for (int u = 0; u < N; ++u)
G[u].clear();
for (int i = 0; i < M; ++i)
{
int u = ns[i].u, v = ns[i].v;
if (col[u])
swap(u, v);
if (ns[i].type == 1)
G[u].pb(v);
else
G[v].pb(u);
}
if (!topsort())
{
cout << "NO\n";
return 0;
}
cout << "YES\n";
for (int i = 0; i < N; ++i)
cout << (col[i] ? 'R' : 'L') << ' ' << pos[i] << '\n';
return 0;
}
F 补题
对任意位置 i i i 的元素，使 ∣ x i − x j ∣ ⋅ ( w i + w j ) \lvert x_i-x_j\rvert\cdot (w_i+w_j) ∣xi−xj∣⋅(wi+wj) 最大的 j j j 可能位置，对于同一侧而言，满足随着 ∣ i − j ∣ \lvert i-j\rvert ∣i−j∣ 增大而减小；但对单个 i i i 求解这样的最大值，时间复杂度仍为 O ( n ) O(n) O(n)。
根据对称性，假设 w j ≤ w i w_j\leq w_i wj≤wi，则可以排除 w j > w i w_j>w_i wj>wi 的位置；由于目标是求区间最优，若某一些决策元素可以导出更优决策，则可以排除这样的决策，于是可以排除 w j ≤ w i w_j\leq w_i wj≤wi 且 ∣ i − j ∣ \lvert i-j\rvert ∣i−j∣ 并非最小的位置 k k k，因为同一侧满足 w j ≤ w i w_j\leq w_i wj≤wi 且 ∣ i − j ∣ \lvert i-j\rvert ∣i−j∣ 最小的 j j j 与 k k k 构成的点对可以得到更小的值。那么只用考虑 O ( n ) O(n) O(n) 个点对即可，这样的点对可以通过单调栈求解。
问题转化为已知一些带权值的线段，求区间内被完全覆盖的线段权值的最小值。这样的问题可以通过依次处理左右边界约束求解，具体而言，将查询离线，逆序处理，将满足左边界约束的区间，用能够维护前缀信息的数据结构进行维护，然后在这样的数据结构上查询满足右边界约束的信息即可。总时间复杂度 O ( n log n ) O(n\log n) O(nlogn)。
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
typedef long long ll;
const int MAXN = 3E5 + 5;
const ll INF = 0x3f3f3f3f3f3f3f3f;
int N, Q;
int X[MAXN], W[MAXN];
vector<int> rs[MAXN];
vector<pair<int, int>> qs[MAXN];
ll bit[MAXN], res[MAXN];
int stk[MAXN], top;
void _min(ll &x, ll y) { x = min(x, y); }
void add(int i, ll x)
{
while (i <= N)
_min(bit[i], x), i += i & -i;
}
ll ask(int i)
{
ll s = INF;
while (i)
_min(s, bit[i]), i -= i & -i;
return s;
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> N >> Q;
for (int i = 0; i < N; ++i)
cin >> X[i] >> W[i];
for (int i = 0; i < Q; ++i)
{
int l, r;
cin >> l >> r;
--l, --r;
qs[l].pb({r, i});
}
for (int i = 0; i < N; ++i)
{
while (top && W[stk[top - 1]] > W[i])
--top;
if (top)
rs[stk[top - 1]].pb(i);
stk[top++] = i;
}
top = 0;
for (int i = N - 1; i >= 0; --i)
{
while (top && W[stk[top - 1]] > W[i])
--top;
if (top)
rs[i].pb(stk[top - 1]);
stk[top++] = i;
}
memset(bit, 0x3f, sizeof(bit));
for (int l = N - 1; l >= 0; --l)
{
for (auto r : rs[l])
{
ll t = (ll)(W[l] + W[r]) * (X[r] - X[l]);
add(r + 1, t);
}
for (auto &p : qs[l])
{
int r = p.first, k = p.second;
res[k] = ask(r + 1);
}
}
for (int i = 0; i < Q; ++i)
cout << res[i] << '\n';
return 0;
}