搜索结果
查询Tags标签: NOI2014,共有 5条记录-
P2114 [NOI2014] 起床困难综合症
https://www.luogu.com.cn/problem/P2114 位运算的题都考虑从高到低。那么可以确定最高位。那么就看看转移到最高位需不需要这一位为 1,然后将这一位置 1,继续下一位。 \(f[i][j],g[i][j]\) 分别表示到第 i 个操作,第 j 位能否为 1,以及能否不为 1。 \(pre[i][j]\) 表…
2022/7/22 23:26:34 人评论 次浏览 -
NOI2014购票
题意: 给出根节点为 \(1\) 的一颗树,\(d_i\) 表示 \(1\) 到 \(i\) 的距离, 每个点 \(i\) 可以跳到距离 \(\leq l_i\) 的点 \(j\) 上,花费是 \((d_i - d_j) \times p_i + q_i\),求每个点到根节点的最小花费。 dp 方程转移: \[f_i = \min \{f_j + (d_i - d_j) \times p…
2022/2/15 23:13:12 人评论 次浏览 -
P2354 [NOI2014] 随机数生成器
前半段模拟。 后面贪心:从小到大依次选。判断能不能选: 每行维护 \(L,R\)。红色位置不能走。然后暴力。 卡空间,以下 \(70pts\)。 #include<bits/stdc++.h> using namespace std; const int maxn=5001*5001; long long x0,a,b,c,d,n,m,q,u,v; struct l{int x;int…
2021/10/4 6:13:21 人评论 次浏览 -
P2354 [NOI2014] 随机数生成器
前半段模拟。 后面贪心:从小到大依次选。判断能不能选: 每行维护 \(L,R\)。红色位置不能走。然后暴力。 卡空间,以下 \(70pts\)。 #include<bits/stdc++.h> using namespace std; const int maxn=5001*5001; long long x0,a,b,c,d,n,m,q,u,v; struct l{int x;int…
2021/10/4 6:13:21 人评论 次浏览 -
[NOI2014] 购票
这题怎么大家都做过了/kk 感谢 Fz 的题解! 首先这题有一个 DP 式子, \[f_i = d_i \times p_i + q_i +\min(-d_j\times p_i+f_j) \]明显是斜率优化的形式。 但对于 \(u\) 有贡献的只有离他较近的若干个祖先。 这里就有几个做法;点分 树剖,u 到某个祖先可以剖为 若干条重…
2021/5/23 10:28:56 人评论 次浏览