Codeforces Global Round 19
A.已知序列中,你可以在1到n-1中选取一个len,使得前len个元素升序,后len个元素升序,有没有有一种方法使得最后整体不升序?
solution:整体不升序的充要条件就是原序列不升序
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T; cin >> T;
while (T --)
{
int n; cin >> n;
vector<int> a(n);
for (int &x : a) cin >> x;
cout << (is_sorted(a.begin(), a.end()) ? "NO\n" : "YES\n");
}
return 0;
}
B.已知序列中,你可以在1和n中任意划分,这样你产生的费用就是length(subarray) + Mex(subarray),求该序列所有子序列费用之和的最大值
solution:其实最大的分法是对每个元素分极小段,这样对每个0都有(1 + 1)的贡献,每个非0数都有(1 + 0)的贡献,显然没有方案会比这个好,因为你在计算大于1长度的子序列贡献会有费用重叠(不必要消耗),对所有子序列枚举即可(On^3),但是可以用On + 公式解决,推导过程略去
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T; cin >> T;
while (T --)
{
int n; cin >> n;
vector<int> a(n);
for (int &x : a) cin >> x;
int ans = 0;
for (int i = 0; i < n; i ++)
{
for (int j = i; j < n; j ++)
{
for (int k = i; k <= j; k ++)
{
ans += (a[k] ? 1 : 2);
}
}
}
cout << ans << "\n";
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T; cin >> T;
while (T --)
{
int n; cin >> n;
vector<int> a(n);
for (int &x : a) cin >> x;
int ans = 0;
for (int i = 0; i < n; i ++)
{
ans += (a[i] == 0 ? 2 : 1) * (i + 1) * (n - i);
}
cout << ans << "\n";
}
return 0;
}
C.给定一个序列为石头堆,每堆有对应石头数,首尾两端石堆无效,问你能否将中间石堆全部移走
solution:不可能移走只有两种情况:1.n = 3且a2为奇数 2.中间石堆全为1 而对于结果的移动次数,为中间石堆折半后上取整的和,可以通过题意推得
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T; cin >> T;
while (T --)
{
int n; cin >> n;
vector<int> a(n);
for (int &x : a) cin >> x;
if ((int)*max_element(a.begin() + 1, a.end() - 1) == 1 || (n == 3 && a[1] & 1)) cout << "-1\n";
else
{
int ans = 0;
for (int i = 1; i < n - 1; i ++) ans += (a[i] + 1) / 2;
cout << ans << "\n";
}
}
return 0;
}
D.给定等长的a b数组,你可以多次交换ai bi,最小化
$$\sum_{i=1}^{n} \sum_{j=i+1}^{n} \(a_i + a_j) + \sum_{i=1}^{n} \sum_{j=i+1}^{n} \(bi + bj)$$
而实际上稍加推理便可以得到一个项的变式
$$\sum_{i=1}^{n} \sum_{j=i+1}^{n} = (\sum_{i=1}^{n}a_i)^2 + (n - 2)\sum_{i=1}^{n}a_i^2$$
对于两项我们只考虑左边这一项时,对 $a_i$ 与 $b_i$ 进行合理交换,使得$((\sum_{i=1}^{n}a_i)^2 + (\sum_{i=1}^{n}b_i)^2)$最小,当成分组背包问题求解,对于{$a_i$}怎么取最小值,以及对应$x$
// code of JUYU ^ ^ never doubt youself !
#include <bits/stdc++.h>
typedef long long ll;
#define int ll
#define For(i,a,b) for (int i = a; i <= b; i ++)
#define Dow(i,a,b) for (int i = b; i >= a; -- i)
#define ms(a,b) memset(a, b, sizeof (a))
#define fir first
#define sec second
#define mk make_pair
#define pb push_back
#define eb emplace_back
using namespace std;
typedef pair<int,int> PII;
const int mod = 998244353;
const int MOD = 1000000007;
const int maxn = 1e5 + 5;
inline ll read()
{
ll t = 0, dp = 1; char c = getchar();
while(!isdigit(c)) {if (c == '-') dp = -1; c = getchar();}
while(isdigit(c)) t = t * 10 + c - 48, c = getchar();
return t * dp;
}
inline void write(ll x){if (x < 0){putchar('-'); x = -x;} if(x >= 10) write(x / 10); putchar(x % 10 + 48);}
inline void writeln(ll x){write(x); puts("");}
inline void write_p(ll x){write(x); putchar(' ');}
inline void write_b(ll x){putchar(' '); write(x);}
inline int qpow(int x, int y, int z){int ret = 1; for (; y; y /= 2, x = x * x % z) if (y & 1) ret = ret * x % z; return ret;}
inline int PrimeInv(int x, int y, int z){return qpow(x, y - 2, z);}
int a[maxn];
signed main()
{
int T; cin >> T;
while (T --)
{
int n = read();
vector<int> a(n + 1), b(n + 1);
For(i,1,n)
{
a[i] = read();
}
For(i,1,n)
{
b[i] = read();
}
int cnt = 0;
vector<int> sum(n + 1);
function<int(int)> count = [&](int x)
{
return x * (n - 1) * x;
};
int ans = 0;
For(i,1,n) sum[i] = sum[i - 1] + a[i] + b[i], ans += count(a[i]) + count(b[i]);
vector dp(n + 1, vector<int>(205 * 205, 1e18));
dp[0][0] = 0;
For(i,1,n) For(j,0,sum[i-1])
{
if (j + a[i] < 205 * 205) dp[i][j + a[i]] = min(dp[i][j + a[i]], dp[i - 1][j] + j * a[i] + (sum[i - 1] - j) * b[i]);
if (j + b[i] < 205 * 205) dp[i][j + b[i]] = min(dp[i][j + b[i]], dp[i - 1][j] + j * b[i] + (sum[i - 1] - j) * a[i]);
}
cout << ans + ((int)*min_element(dp[n].begin(), dp[n].end()) * 2) << "\n";
}
return 0;
}
/* stuff you should look for
* int overflow, array bounds
* special cases (n=1?)
* do smth instead of nothing and stay organized
* WRITE STUFF DOWN
* DON'T GET STUCK ON ONE APPROACH
-- Benq
*/
E.定义$f(x, y) = (cnt_x + cnt_y) * (x + y)$,在给定序列中找到$f(x, y)$的最大值,并且$x\not=y$,给定m个二元组,答案不能从中出现
solution:两种解法,一种是优先队列的bfs,一种是set等容器的二分,这里给出前者,tourist他们的写法是后者
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T; cin >> T;
while (T --)
{
int n, m; cin >> n >> m;
unordered_map<int, vector<int>> mp;
map<pair<int, int>, bool> bad;
map<int, int> cnt;
for (int i = 0; i < n; i ++)
{
int x; cin >> x; cnt[x] ++;
}
while (m --)
{
int u, v; cin >> u >> v;
bad[{u, v}] = true;
bad[{v, u}] = true;
}
for (auto [u, v] : cnt) mp[v].push_back(u);
for (auto &[u, v] : mp) sort(v.begin(), v.end());
int ans = 0;
for (auto [i, vi] : mp)
{
for (auto [j, vj] : mp)
{
if (i > j) continue;
auto bfs = [&]()
{
map<pair<int, int>, bool> vis;
priority_queue<array<int, 3>> pr;
pr.push(array<int, 3>{vi.back() + vj.back(), (int)(vi.size() - 1), (int)(vj.size() - 1)});
while (!pr.empty())
{
auto [w, u, v] = pr.top(); pr.pop();
if (vi[u] != vj[v] && !bad[{vi[u], vj[v]}]) return w;
if (u && !vis[{u - 1, v}])
{
pr.push(array<int, 3>{vi[u - 1] + vj[v], u - 1, v});
vis[{u - 1, v}] = true;
}
if (v && !vis[{u, v - 1}])
{
pr.push(array<int, 3>{vi[u] + vj[v - 1], u, v - 1});
vis[{u, v - 1}] = true;
}
}
return 0LL;
};
ans = max(ans, (i + j) * bfs());
}
}
cout << ans << "\n";
}
return 0;
}
F.给定一棵树的带权节点,为每个节点分配$w_i\geq0$,使得每个节点$i$都$u, v \rightarrow i \in Path(u, v) and min(w_u, w_v)\geq h_i$,求$min(\sum_{i=1}^{n}(w_i))$
solution:未完
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n; cin >> n;
vector<int> h(n + 1);
for (int i = 1; i <= n; i ++) cin >> h[i];
vector g(n + 1, vector<int>());
for (int i = 1; i < n; i ++)
{
int u, v; cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
int rt = max_element(h.begin() + 1, h.end()) - h.begin();
int ans = 0;
function<int(int, int)> dfs = [&](int u, int fa)
{
int max_w = 0;
if (u != rt)
{
for (int v : g[u])
{
if (v == fa) continue;
max_w = max(max_w, dfs(v, u));
}
if (max_w < h[u]) ans += h[u] - max_w;
return max(max_w, h[u]);
}
else
{
if (g[u].size() == 1)
{
for (int v : g[u])
{
max_w = max(max_w, dfs(v, u));
ans += h[u] * 2 - max_w;
}
}
else
{
multiset<int> ms;
for (int v : g[u]) ms.insert(dfs(v, u));
auto now = -- ms.end();
ans += h[u] - *now;
now --;
ans += h[u] - *now;
}
return 0LL;
}
};
dfs(rt, rt);
cout << ans << "\n";
return 0;
}
