用户工具

站点工具


2020-2021:teams:legal_string:组队训练比赛记录:contest21

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

后一修订版
前一修订版
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  | +|  B  |  ​ ​| ​ 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  |  ​+|  H  |  ​ ​| ​ 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)$。
2020-2021/teams/legal_string/组队训练比赛记录/contest21.1633174039.txt.gz · 最后更改: 2021/10/02 19:27 由 jxm2001