pts: 100
T1: 100
T2: 0
T3: 0
吐槽:xj 中学的神仙题目,T1 贪心跑过了正解的 dp /se
T1
Strategy
游戏中有 \(n\) 个敌人,面对第 \(i\) 个敌人,三种解决方案
- 花 \(attack_i\) 的代价主动进攻,此技能最多用 \(k\) 次
- 花 \(define_i\) 的代价防御,此技能可以用无数次
- 和该敌人结盟,此技能只能用一次
给定每个敌人的 \(attack_i\) 和 \(define_i\) 以及最多的攻击次数 \(k\) ,求出和第 \(i\) 个盟友结盟的情况下,在这一轮的最小花费
\(n \leq 4000\)
solution
贪心
常用策略:考虑敌人的性价比 \((define_i - attack_i)\)
如果一个敌人的 \(D - A\) 比较大的话,会优先考虑进攻 (在次数限制范围之内)
所以对每个敌人的 \(D - A\) 排序
然后枚举盟友,如果是盟友啥也不动就好
排完序的前 \(n - k\) 个敌人一定选择防守,对它们没机会进攻
对后 \(k\) 个选择进攻或防守
时间复杂度:\(O(n^2)\)
std 复杂度 \(O(n^2log~n)\) ? ?
code
namespace Ariel_{
struct node{int id, num;}E[N];
bool cmp(node a, node b) {return a.num < b.num;}
int n, k, a[N], d[N], sum, Ans, p, o;
void main(){
n = read(), k = read();
for (int i = 1; i <= n; i++) a[i] = read(), d[i] = read(), sum += a[i];
for (int i = 1; i <= n; i++) E[i].num = d[i] - a[i], E[i].id = i;
sort (E + 1, E + n + 1, cmp);
for (int i = 1; i <= n; i++) {
Ans = sum - a[i], p = 1, o = 1;
while (o < n - k) {
if (E[p].id != i) Ans += E[p].num, o++;
p++;
}
while (p <= n) {
if (E[p].id != i)
if (E[p].num < 0) Ans += E[p].num;
else break;
p++;
}
printf("%lld ", Ans);
}
}
}
T2
easy LCA
一棵节点为 \(n\) 的树,给定一个长度为 \(n\) 的排列 \(p\)
定义连续子段的 \(p_{l,r}\) 的权值为 \(val[l,r] = depth[lca(p_l, p_{l + 1}…p_r)]\) (这段序列所有点的 \(lca\) 的深度)
求出所有 \(n * (n + 1)/2\) 的连续字段的权值之和 \((\sum_{i = 1}^{i = n}\sum_{j = i}^nval[i, j])\)
根节点的深度为 \(1\)
\(n\leq 6*10^5\)
\(solution\)
首先 \(LCA\) 满足单调性,也就是连续一段区间的 \(LCA\) 为两两 \(LCA\) 中深度最小的一个
所以把所有相邻节点的 \(LCA\) 都求出来,也就是序列 \(l\)
\(l_i\) 表示 \(nxtLCA_{a_i, a_{i + 1}}\)
对于任意连续 \(k\) 个节点,我们枚举一个 \(l_i\) ,算出它左边第一个深度小于它的节点 \((l_j)\) 和右边深度第一个小于它的节点 \(l_k\) 那么这段区间内的 \(LCA\) 就都是 \(l_i\) 了
这个可以用单调栈维护
namespace STACK{
stack<int> s;
//计算左边界
void calc_L(){
for (int i = 1; i < n; i++){
while(!s.empty() && l[s.top()] >= l[i]) R[s.top()] = i - 1, s.pop();
s.push(i);
}
while(!s.empty()) R[s.top()] = n - 1, s.pop();
}
//计算右边界
void calc_R(){
for (int i = n - 1; i >= 1; i--){
while(!s.empty() && l[i] < l[s.top()]) L[s.top()] = i + 1, s.pop();//左边界
s.push(i);
}
while(!s.empty()) L[s.top()] = 1, s.pop();//多余的情况
}
}
所以这段区间的答案就为 \(((l_i-l_j+1)*(l_k-l_i+1)*dep[l_i])\)
时间复杂度为 \(O(n logn)\) (求相邻 \(LCA\) )
code
\(LCA\) 用树剖写滴,可能有点长 emm
/*
work by:Ariel_
*/
#include <iostream>
#include <cstring>
#include <cstdio>
#include <stack>
#include <algorithm>
#define int long long
using namespace std;
const int N = 1200010;
int read(){
int x = 0,f = 1; char c = getchar();
while(c < '0'||c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') {x = x*10 + c - '0'; c = getchar();}
return x*f;
}
int n, l[N], a[N], dep[N];
int L[N], R[N];
struct edge {int v, nxt;}e[N];
int head[N], cnt;
void add_edge(int u, int v) {
e[++cnt] = (edge){v, head[u]};
head[u] = cnt;
}
namespace LCA{
int fa[N], top[N], siz[N], son[N];
void dfs(int x, int f) {
fa[x] = f, siz[x] = 1, dep[x] = dep[f] + 1;
for (int i = head[x]; i; i = e[i].nxt) {
int v = e[i].v;
if(v == f) continue;
dfs(v, x);siz[x] += siz[v];
if(siz[v] > siz[son[x]]) son[x] = v;
}
}
void dfs2(int x, int tp) {
top[x] = tp;
if(son[x]) dfs2(son[x], tp);
for (int i = head[x]; i; i = e[i].nxt) {
int v = e[i].v;
if (v == fa[x] || v == son[x]) continue;
dfs2(v, v);
}
}
int lca(int x, int y){
while(top[x] != top[y]) {
if(dep[top[x]] < dep[top[y]]) swap(x, y);
x = fa[top[x]];
}
if(dep[x] > dep[y]) swap(x, y);
return x;
}
}
namespace STACK{
stack<int> s;
void calc_L(){
for (int i = 1; i < n; i++){
while(!s.empty() && l[s.top()] >= l[i]) R[s.top()] = i - 1, s.pop();
s.push(i);
}
while(!s.empty()) R[s.top()] = n - 1, s.pop();
}
void calc_R(){
for (int i = n - 1; i >= 1; i--){
while(!s.empty() && l[i] < l[s.top()]) L[s.top()] = i + 1, s.pop();//左边界
s.push(i);
}
while(!s.empty()) L[s.top()] = 1, s.pop();//多余的情况
}
}
namespace Ariel_{
int ans = 0;
void main() {
n = read();
for (int i = 1, u, v; i < n; i++){
u = read(),v = read();
add_edge(u, v), add_edge(v, u);
}
for (int i = 1; i <= n; i++) a[i] = read();
LCA::dfs(1, 0), LCA::dfs2(1, 1);
for (int i = 1; i < n; i++) l[i] = dep[LCA::lca(a[i], a[i + 1])];
STACK::calc_L(), STACK::calc_R();
for(int i = 1; i < n; i++) ans += (i - L[i] + 1) * (R[i] - i + 1) * l[i];
for(int i = 1; i <= n; i++) ans += dep[a[i]];
printf("%lld", ans);
}
}
signed main(){
Ariel_::main();
return 0;
}
T3
Scarborough Fair
由 \(n\) 个点和 \(m\) 条无向边组成的图 (由于集市中存在桥,故不保证是平面图),其中第 \(i\) 条道路连接 \(u_i\) ,\(v_i\) 两点,有 \(w_i\) 的概率是不能通行的。
小 \(W\) 定义一张图的不方便程度为图中的联通块个数,现在给定集市的地图,小 \(W\) 希望你能帮他求出这张图的期望不方便程度
答案对 \(998244353\) 取模
\(n\leq 17\)
solution
状压期望 \(dp\) 部分分都不会写 @ @