CVBB ACM Team

用户工具

站点工具

您在这里: front_page » 2020-2021 » teams » namespace » codeforces_round_638_div._2
2020-2021:teams:namespace:codeforces_round_638_div._2

差别

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

到此差别页面的链接

两侧同时换到之前的修订记录 前一修订版
后一修订版 		前一修订版
2020-2021:teams:namespace:codeforces_round_638_div._2 [2020/05/31 21:10]
great_designer [分析] 		2020-2021:teams:namespace:codeforces_round_638_div._2 [2020/07/10 16:29] (当前版本)
great_designer [分析]
行 34: 行 34:
  
 2 2
 +
 2 2
 +
 4 4
  
行 40: 行 42:
  
 2 2
 +
 6 6
  
行 110: 行 113:
  
 4 4
 +
 4 2 4 2
 +
 1 2 2 1 1 2 2 1
 +
 4 3 4 3
 +
 1 2 2 1 1 2 2 1
 +
 3 2 3 2
 +
 1 2 3 1 2 3
 +
 4 4 4 4
 +
 4 3 4 2 4 3 4 2
  
行 122: 行 133:
  
 5 5
 +
 1 2 1 2 1 1 2 1 2 1
 +
 4 4
 +
 1 2 2 1 1 2 2 1
 +
 -1 -1
 +
 7 7
 +
 4 3 2 1 4 3 2 4 3 2 1 4 3 2
  
行 274: 行 291:
  
 6 6
 +
 4 2 4 2
 +
 baba baba
 +
 5 2 5 2
 +
 baacb baacb
 +
 5 3 5 3
 +
 baacb baacb
 +
 5 3 5 3
 +
 aaaaa aaaaa
 +
 6 4 6 4
 +
 aaxxzz aaxxzz
 +
 7 1 7 1
 +
 phoenix phoenix
  
行 290: 行 319:
  
 ab ab
 +
 abbc abbc
 +
 b b
 +
 aa aa
 +
 x x
 +
 ehinopx ehinopx
  
行 402: 行 436:
  
 3 3
 +
 9 9
 +
 11 11
 +
 2 2
  
行 409: 行 446:
  
 3 3
 +
 1 0 2  1 0 2 
 +
 3 3
 +
 1 1 2 1 1 2
 +
 1 1
 +
 0  0 
  
行 474: 行 516:
  
 10010 1 1 1 4——从初始数列0 1 2 4到最终数列1 2 4 8过渡中，正在修改23两位。 10010 1 1 1 4——从初始数列0 1 2 4到最终数列1 2 4 8过渡中，正在修改23两位。
 +
 10011 1 2 0 4——从初始数列0 1 2 4到最终数列1 2 4 8过渡中，正在修改23两位。 10011 1 2 0 4——从初始数列0 1 2 4到最终数列1 2 4 8过渡中，正在修改23两位。
  
 10100 1 2 1 3——从初始数列0 1 2 4到最终数列1 2 4 8过渡中，正在修改34两位。 10100 1 2 1 3——从初始数列0 1 2 4到最终数列1 2 4 8过渡中，正在修改34两位。
 +
 10101 1 2 2 2——从初始数列0 1 2 4到最终数列1 2 4 8过渡中，正在修改34两位。 10101 1 2 2 2——从初始数列0 1 2 4到最终数列1 2 4 8过渡中，正在修改34两位。
 +
 10110 1 2 3 1——从初始数列0 1 2 4到最终数列1 2 4 8过渡中，正在修改34两位。 10110 1 2 3 1——从初始数列0 1 2 4到最终数列1 2 4 8过渡中，正在修改34两位。
 +
 10111 1 2 4 0——从初始数列0 1 2 4到最终数列1 2 4 8过渡中，正在修改34两位。 10111 1 2 4 0——从初始数列0 1 2 4到最终数列1 2 4 8过渡中，正在修改34两位。
  
行 550: 行 596:
 输入 输入
  
-第一行包含两个整数n和k（1\le n，k\le 500）-分别是灌木的数量和篮子容量。+第一行包含两个整数n和k（$1\le n，k\le 500$）-分别是灌木的数量和篮子容量。
  
-接下来的n行中的i-th包含两个整数a_i和b_i（$$$0\le a_i，b_i\le 10^9$$）-分别是i-th灌木中红色和蓝色浆果的数量。+接下来的n行中的i-th包含两个整数a_i和b_i（$0\le a_i，b_i\le 10^9$）-分别是i-th灌木中红色和蓝色浆果的数量。
  
 输出 输出
行 563: 行 609:
  
 2 4 2 4
 +
 5 2 5 2
 +
 2 1 2 1
  
行 573: 行 621:
  
 1 5 1 5
 +
 2 3 2 3
  
行 607: 行 656:
 在第二个例子中，菲尼克斯可以用第一个（也是唯一一个）灌木的所有浆果填满一个篮子。 在第二个例子中，菲尼克斯可以用第一个（也是唯一一个）灌木的所有浆果填满一个篮子。
  
-在第三个示例中，Phoenix无法完全填充任何篮子，因为每个灌木中的浆果少于$$$5$$，总红色浆果少于$$$5$$，总蓝色浆果少于$$$5$$。+在第三个示例中，Phoenix无法完全填充任何篮子，因为每个灌木中的浆果少于5，总红色浆果少于5，总蓝色浆果少于5。
  
 在第四个例子中，菲尼克斯可以把所有的红色浆果放进篮子里，留下一个额外的蓝色浆果。 在第四个例子中，菲尼克斯可以把所有的红色浆果放进篮子里，留下一个额外的蓝色浆果。
  
 ====分析==== ====分析====
- 
-（暂无思路） 
  
 大致意思是只能从矩阵同行或同列取值，要求每次取值必须填满篮子（k个），问最多填多少个篮子。 大致意思是只能从矩阵同行或同列取值，要求每次取值必须填满篮子（k个），问最多填多少个篮子。
 +
 +$n$棵树每棵树上$a_i$个红果，$b_i$个蓝果，每个篮子容量为$k$，可以装同一棵树上的果实（条件一）或者颜色相同的果实（条件二），问最多使多少篮子恰好填满
 +
 +$1 \le n,k \le 500,1\le a_i,b_i\le 1e9$
 +
 +以下搬运自其他页面的本题题解：
 +
 +考虑暴力$dp$,​ $dp[i][j][k]$表示考虑到第$i$种物品，红色的篮子还可以放$j$个，蓝色的篮子还可以放$k$个的最大值。
 +
 +这样如果直接的转移是$n^5$的，显然不行。可以考虑一下$j$是否能推出$k$。
 +
 +发现有$果实总数-dp[i][j]*每框个数=k$
 +
 +转移就是枚举之前红色的框剩几个，现在红色的框剩几个。剩下的差就是本次与蓝色单独装框的即可。
 +
 +考虑到对于一棵树如果装在$t$个篮子中，一定可以使大于等于$t-1$个篮子满足条件一，因而所有最优解中存在一种方案使得每棵树最多提供一个满足条件二的篮子
 +
 +因而记$f(i,​j)$表示前$i$棵树装完剩余$j$个红果的最大篮子数,​$S_i$表示前$i$棵树果子总和,​可以推得剩余蓝果数量为$S_i-f(i,​j)*k-j$
 +
 +下面只简述存在条件二篮子的转移
 +
 +枚举该篮子中红果数量$num_1$，蓝果为$k-num_1$；令$t_1=j-num_1+a_i,​t_2=S_i-f(i,​j)*k-j-k+num_1+b_i$
 +
 +转移方程$f(i+1,​t_1\%k)=max(f(i+1,​t_1\%k),​f(i,​j)+1+t_1/​k+t_2/​k)$
  
 =====F===== =====F=====
行 642: 行 713:
  
 4 4
 +
 4 4 4 4
 +
 1 3 1 3
 +
 2 4 2 4
 +
 3 4 3 4
  
行 650: 行 725:
  
 YES YES
 +
 4 1 2 3 4 1 2 3
  
行 655: 行 731:
  
 4 4
 +
 1 3 1 3
 +
 2 4 2 4
 +
 3 4 3 4
 +
 2 3 2 3
  
行 663: 行 743:
  
 NO NO
 +
 1 3 4 2 1 3 4 2
 +
 1 2 4 3 1 2 4 3
  
2020-2021/teams/namespace/codeforces_round_638_div._2.1590930658.txt.gz · 最后更改: 2020/05/31 21:10 由 great_designer

页面工具

除额外注明的地方外，本维基上的内容按下列许可协议发布： CC Attribution-Share Alike 4.0 International
CC Attribution-Share Alike 4.0 International Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki
京ICP备20018844号-3