这里会显示出您选择的修订版和当前版本之间的差别。
后一修订版 | 前一修订版 | ||
2020-2021:teams:legal_string:组队训练比赛记录:contest21 [2021/10/02 19:27] jxm2001 创建 |
2020-2021:teams:legal_string:组队训练比赛记录:contest21 [2021/10/04 17:04] (当前版本) jxm2001 [题解] |
||
---|---|---|---|
行 4: | 行 4: | ||
^ 题目 ^ 蒋贤蒙 ^ 王赵安 ^ 王智彪 ^ | ^ 题目 ^ 蒋贤蒙 ^ 王赵安 ^ 王智彪 ^ | ||
- | | B | 0 | 0 | 0 | | + | | B | 2 | 0 | 0 | |
| E | 0 | 0 | 0 | | | E | 0 | 0 | 0 | | ||
| F | 0 | 0 | 0 | | | F | 0 | 0 | 0 | | ||
| G | 2 | 0 | 0 | | | G | 2 | 0 | 0 | | ||
- | | H | 0 | 0 | 0 | | + | | H | 2 | 0 | 0 | |
| K | 0 | 0 | 0 | | | K | 0 | 0 | 0 | | ||
====== 题解 ===== | ====== 题解 ===== | ||
+ | |||
+ | ===== B. discount ===== | ||
+ | |||
+ | ==== 题意 ==== | ||
+ | |||
+ | 给定 $n$ 种商品,对于每个商品 $i$,有两种策略,一种是花费 $a_i$ 购买同时赠送商品 $j$,一种是花费 $b_i$ 购买。$(b_i\le a_i)$ | ||
+ | |||
+ | 问至少获得所有商品各一种的最小费用。 | ||
+ | |||
+ | ==== 题解 ==== | ||
+ | |||
+ | 假定花费 $a_i$ 购买商品 $i$ 可以赠送商品 $j$,则连边 $j\to i$,其中 $i$ 是 $j$ 的儿子结点。 | ||
+ | |||
+ | 于是可以得到基环树森林,定义每个结点的状态 $0/1/2$ 表示不购买该结点/以 $b_i$ 购买该结点/以 $a_i$ 购买该结点。 | ||
+ | |||
+ | 于是原问题等价于使得每个结点的状态如果为 $0$ 则至少有一个儿子状态为 $2$ 的最小费用。 | ||
+ | |||
+ | 先考虑树的解法,设 $\text{dp}(u,0/1/2)$ 为只考虑子树 $u$ 的情况下的最小费用,不难得到状态转移方程。 | ||
+ | |||
+ | 接下来考虑每个基环树上的环,任取一个点,枚举该点在环上的子节点状态是否为 $2$,然后进行线性 $\text{dp}$。 | ||
+ | |||
+ | <hidden 查看代码> | ||
+ | <code cpp> | ||
+ | const int MAXN=1e5+5; | ||
+ | const LL inf=1e18; | ||
+ | struct Edge{ | ||
+ | int to,next; | ||
+ | }edge[MAXN]; | ||
+ | int head[MAXN],edge_cnt; | ||
+ | void Insert(int u,int v){ | ||
+ | edge[++edge_cnt]=Edge{v,head[u]}; | ||
+ | head[u]=edge_cnt; | ||
+ | } | ||
+ | int fa[MAXN],a[MAXN],b[MAXN]; | ||
+ | bool inque[MAXN],node_vis[MAXN],node_cyc[MAXN]; | ||
+ | LL dp[MAXN][3]; | ||
+ | vector<int> cyc; | ||
+ | void dfs(int u){ | ||
+ | LL s1=0,s2=inf; | ||
+ | node_vis[u]=true; | ||
+ | for(int i=head[u];i;i=edge[i].next){ | ||
+ | int v=edge[i].to; | ||
+ | if(node_cyc[v])continue; | ||
+ | dfs(v); | ||
+ | LL w=min({dp[v][0],dp[v][1],dp[v][2]}); | ||
+ | s1+=w; | ||
+ | s2=min(s2,dp[v][2]-w); | ||
+ | } | ||
+ | dp[u][0]=s1+s2; | ||
+ | dp[u][1]=b[u]+s1; | ||
+ | dp[u][2]=a[u]+s1; | ||
+ | } | ||
+ | LL dp2[MAXN][3]; | ||
+ | LL cal1(){ | ||
+ | int u=cyc[0]; | ||
+ | dp2[u][0]=min({dp[u][0],dp[u][1]-b[u],dp[u][2]-a[u]}); | ||
+ | dp2[u][1]=dp[u][1]; | ||
+ | dp2[u][2]=dp[u][2]; | ||
+ | _for(i,1,cyc.size()){ | ||
+ | int u=cyc[i],p=cyc[i-1]; | ||
+ | dp2[u][0]=dp2[p][2]+min({dp[u][0],dp[u][1]-b[u],dp[u][2]-a[u]}); | ||
+ | dp2[u][0]=min(dp2[u][0],dp[u][0]+min(dp2[p][0],dp2[p][1])); | ||
+ | dp2[u][1]=dp[u][1]+min({dp2[p][0],dp2[p][1],dp2[p][2]}); | ||
+ | dp2[u][2]=dp[u][2]+min({dp2[p][0],dp2[p][1],dp2[p][2]}); | ||
+ | } | ||
+ | return dp2[*cyc.rbegin()][2]; | ||
+ | } | ||
+ | LL cal2(){ | ||
+ | int u=cyc[0]; | ||
+ | dp2[u][0]=dp[u][0]; | ||
+ | dp2[u][1]=dp[u][1]; | ||
+ | dp2[u][2]=dp[u][2]; | ||
+ | _for(i,1,cyc.size()){ | ||
+ | int u=cyc[i],p=cyc[i-1]; | ||
+ | dp2[u][0]=dp2[p][2]+min({dp[u][0],dp[u][1]-b[u],dp[u][2]-a[u]}); | ||
+ | dp2[u][0]=min(dp2[u][0],dp[u][0]+min(dp2[p][0],dp2[p][1])); | ||
+ | dp2[u][1]=dp[u][1]+min({dp2[p][0],dp2[p][1],dp2[p][2]}); | ||
+ | dp2[u][2]=dp[u][2]+min({dp2[p][0],dp2[p][1],dp2[p][2]}); | ||
+ | } | ||
+ | return min({dp2[*cyc.rbegin()][0],dp2[*cyc.rbegin()][1],dp2[*cyc.rbegin()][2]}); | ||
+ | } | ||
+ | LL solve(int u){ | ||
+ | cyc.clear(); | ||
+ | stack<int> st; | ||
+ | int pos=u; | ||
+ | while(!inque[pos]){ | ||
+ | inque[pos]=true; | ||
+ | st.push(pos); | ||
+ | pos=fa[pos]; | ||
+ | } | ||
+ | node_cyc[pos]=true; | ||
+ | cyc.push_back(pos); | ||
+ | while(st.top()!=pos){ | ||
+ | int tmp=st.top(); | ||
+ | node_cyc[tmp]=true; | ||
+ | cyc.push_back(tmp); | ||
+ | st.pop(); | ||
+ | } | ||
+ | reverse(cyc.begin(),cyc.end()); | ||
+ | for(int u:cyc) | ||
+ | dfs(u); | ||
+ | return min(cal1(),cal2()); | ||
+ | } | ||
+ | int main() | ||
+ | { | ||
+ | int n=read_int(); | ||
+ | _rep(i,1,n) | ||
+ | a[i]=read_int(); | ||
+ | _rep(i,1,n) | ||
+ | b[i]=a[i]-read_int(); | ||
+ | _rep(i,1,n){ | ||
+ | fa[i]=read_int(); | ||
+ | Insert(fa[i],i); | ||
+ | } | ||
+ | LL ans=0; | ||
+ | _rep(u,1,n){ | ||
+ | if(!node_vis[u]) | ||
+ | ans+=solve(u); | ||
+ | } | ||
+ | enter(ans); | ||
+ | return 0; | ||
+ | } | ||
+ | </code> | ||
+ | </hidden> | ||
===== G. transform ===== | ===== G. transform ===== | ||
- | 赛后一分钟过样例 $\to$ 过题,乐。 | + | 二分答案 $+$ 滑动窗口,赛后一分钟过样例 $\to$ 过题,乐。 |
+ | |||
+ | ===== H. travel ===== | ||
+ | |||
+ | ==== 题意 ==== | ||
+ | |||
+ | 给定一棵点权树,从树上选三条不相交的路径,每条路径的权值定义为路径上的点权和,要求最大化三条路径权值和。 | ||
+ | |||
+ | ==== 题解 ==== | ||
+ | |||
+ | 设 $\text{dp}(u,0/1/2,i)$ 表示只考虑 $u$ 的子树,结点 $u$ 的状态为 $0/1/2$ 时,已经选中了 $i$ 条链此时的最大路径权值和。 | ||
+ | |||
+ | 我们需要维护一条正在生成的链,这条链不包含在已经选中的 $i$ 条链当中,如果 $u$ 状态为 $0$ 表示 $u$ 不在生成链中。 | ||
+ | |||
+ | 如果 $u$ 状态为 $1$ 表示 $u$ 在生成链中且 $u$ 只有一个儿子在生成链中, $u$ 状态为 $2$ 表示 $u$ 在生成链中且 $u$ 有两个儿子在生成链中。 | ||
+ | |||
+ | 考虑状态转移,利用生成链的合并,不难有 | ||
+ | |||
+ | $$ | ||
+ | \text{dp}(u,0,i+j)\gets \text{dp}(u,0,i)+\text{dp}(v,0,j)\\ | ||
+ | \text{dp}(u,1,i+j)\gets \text{dp}(u,0,i)+\text{dp}(v,1,j)+a_u\\ | ||
+ | \text{dp}(u,1,i+j)\gets \text{dp}(u,1,i)+\text{dp}(v,0,j)\\ | ||
+ | \text{dp}(u,2,i+j)\gets \text{dp}(u,1,i)+\text{dp}(v,1,j)\\ | ||
+ | \text{dp}(u,2,i+j)\gets \text{dp}(u,2,i)+\text{dp}(v,0,j) | ||
+ | $$ | ||
+ | |||
+ | 注意上式的 $\gets$ 表示取最大值,另外为了防止选中复数条从 $v$ 生成的链,需要开一个临时数组存储中间量。 | ||
+ | |||
+ | 初始状态为 $\text{dp}(u,1,0)=a_u$,最后转移完要考虑将正在生成的链转化为已经选中的链,于是有 | ||
+ | |||
+ | $$ | ||
+ | \text{dp}(u,0,i)\gets \max(\text{dp}(u,1,i-1),\text{dp}(u,2,i-1)) | ||
+ | $$ | ||
+ | |||
+ | 最终答案为 $\text{dp}(1,0,k)$,时间复杂度 $O(nk^2)$,其中 $k$ 表示最多能选中的链的个数。本题 $k=3$。 | ||
+ | |||
+ | [[http://tokitsukaze.live/2018/07/24/2018niuke2.H/|参考资料]] | ||
+ | |||
+ | <hidden 查看代码> | ||
+ | <code cpp> | ||
+ | const int MAXN=4e5+5,MAXK=4; | ||
+ | struct Edge{ | ||
+ | int to,next; | ||
+ | }edge[MAXN<<1]; | ||
+ | int a[MAXN],head[MAXN],edge_cnt; | ||
+ | LL dp[MAXN][3][MAXK],tmp[3][MAXK]; | ||
+ | void Insert(int u,int v){ | ||
+ | edge[++edge_cnt]=Edge{v,head[u]}; | ||
+ | head[u]=edge_cnt; | ||
+ | } | ||
+ | void Max(LL &a,LL b){ | ||
+ | if(b>a) | ||
+ | a=b; | ||
+ | } | ||
+ | void dfs(int u,int fa){ | ||
+ | dp[u][1][0]=a[u]; | ||
+ | for(int i=head[u];i;i=edge[i].next){ | ||
+ | int v=edge[i].to; | ||
+ | if(v==fa)continue; | ||
+ | dfs(v,u); | ||
+ | _for(i,0,3)_for(j,0,MAXK) | ||
+ | tmp[i][j]=dp[u][i][j]; | ||
+ | _for(i,0,MAXK)_for(j,0,MAXK-i){ | ||
+ | Max(tmp[0][i+j],dp[u][0][i]+dp[v][0][j]); | ||
+ | Max(tmp[1][i+j],dp[u][0][i]+dp[v][1][j]+a[u]); | ||
+ | Max(tmp[1][i+j],dp[u][1][i]+dp[v][0][j]); | ||
+ | Max(tmp[2][i+j],dp[u][1][i]+dp[v][1][j]); | ||
+ | Max(tmp[2][i+j],dp[u][2][i]+dp[v][0][j]); | ||
+ | } | ||
+ | _for(i,0,3)_for(j,0,MAXK) | ||
+ | dp[u][i][j]=tmp[i][j]; | ||
+ | } | ||
+ | _for(i,1,MAXK) | ||
+ | Max(dp[u][0][i],max(dp[u][1][i-1],dp[u][2][i-1])); | ||
+ | } | ||
+ | int main() | ||
+ | { | ||
+ | int n=read_int(); | ||
+ | _rep(i,1,n) | ||
+ | a[i]=read_int(); | ||
+ | _for(i,1,n){ | ||
+ | int u=read_int(),v=read_int(); | ||
+ | Insert(u,v); | ||
+ | Insert(v,u); | ||
+ | } | ||
+ | dfs(1,0); | ||
+ | enter(dp[1][0][3]); | ||
+ | return 0; | ||
+ | } | ||
+ | </code> | ||
+ | </hidden> | ||
+ | |||
+ | ===== J. farm ==== | ||
+ | |||
+ | ==== 题意 ==== | ||
+ | |||
+ | 给定 $n\times m$ 的矩阵,每个位置一个植物,种类为 $a(i,j)$。接下来 $q$ 个操作,每次选定一个矩形区域施加种类为 $k$ 的药水。 | ||
+ | |||
+ | 当植物的种类与被施加的药水种类不同时植物死亡。问最后死亡的植物数。 | ||
+ | |||
+ | ==== 题解 1 ==== | ||
+ | |||
+ | 二维线段树维护区间赋值,最后查询时将所有操作下放到子节点暴力修改,时间复杂度 $O(nm\log n\log m)$。 | ||
+ | |||
+ | ==== 题解 2 ==== | ||
+ | |||
+ | 二维树状数组维护矩形区间加,先将所有操作加入矩阵,最后枚举种类,枚举种类 $k$ 的植物时先消除 $k$ 类药水的影响查询完成后再加回去。 | ||
+ | |||
+ | 时间复杂度同为 $O(nm\log n\log m)$,但常数小。 | ||
+ | |||
+ | ==== 题解 3 ==== | ||
+ | 随机给每个种类 $k$ 赋一个值 $f(k)$,然后哈希处理矩阵加,当种类 $k$ 的植物的所在位置的权值恰好为 $f(k)$ 的倍数时该植物存活。 | ||
+ | 如果不放心可以二重哈希,时间复杂度 $O(nm)$。 |