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:07]
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
  
行 307: 行 341:
 ====分析==== ====分析====
  
-错误的算法： +先排序，然后分这几种情况：
- +
-逆向考虑。+
  
-首先，把所有的字母全部拆掉，即对于长为n的串，先拆成n个单独的字母，然后不断拼接，直到拼成剩下k个串为止。+比较s[0]和s[k-1]，如果不同直接输出s[k-1]，因为这时在首字母中s[k-1]已经是最大的了，后面什么都不加就是最小的，其他的加到别的地方。
  
-由于字母顺序可以打乱，那么先将n个字母按照字典序排序。（字母可重复） +如果s[0]和s[k-1]相同，说明首字母相同，注意样例中的aaaaa，这就是一种特殊情况，这个情况a要均分，才是最小，比较s[k]和s[n-1]，相同就是尽量均分。
- +
-每次合并的时候，把字典序最大的合并到字典序最小，并将新串串内排序，再插入原串的排列。这是二分查找加插入的操作。 +
- +
-用STL里面的multiset（元素可重复），本质还是树，每次取最大元和最小元维护就行了。 +
- +
-正确的算法： +
- +
-先排序，然后分这几种情况：+
  
-1. 比较s[0]和s[k-1]，如果不同直接输出s[k-1]，因为这时在首字母中s[k-1]已经是最大的了，后面什么都不加就是最小的，其他的加到别的地方。 +s[k]和s[n-1]不同的话，只能把s[k]到s[n-1]全都放在一个的后面，因为如果分给了其他的，一定会导致字典序增大。如abbc变成abc。
-2. 如果s[0]和s[k-1]相同，说明首字母相同，注意样例中的aaaaa，这就是一种特殊情况，这个情况a要均分，才是最小，比较s[k]和s[n-1]，相同就是尽量均分。 +
-3. s[k]和s[n-1]不同的话，只能把s[k]到s[n-1]全都放在一个的后面，因为如果分给了其他的，一定会导致字典序增大。如abbc变成abc+
  
 ====代码==== ====代码====
行 414: 行 436:
  
 3 3
 +
 9 9
 +
 11 11
 +
 2 2
  
行 421: 行 446:
  
 3 3
 +
 1 0 2  1 0 2 
 +
 3 3
 +
 1 1 2 1 1 2
 +
 1 1
 +
 0  0 
  
行 486: 行 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两位。
  
行 499: 行 533:
 100000 0 1 2 4 8——以此类推 100000 0 1 2 4 8——以此类推
  
-被修改的两位，和始终保持不变，为2的{位数减一}次幂，前一个数是标红的1后面部分减1。+被修改的两位，和始终保持不变，为2的{位数减一}次幂，前一个数是从左往右数第一个1后面部分减1。
  
 ====代码==== ====代码====
行 562: 行 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灌木中红色和蓝色浆果的数量。
  
 输出 输出
行 575: 行 609:
  
 2 4 2 4
 +
 5 2 5 2
 +
 2 1 2 1
  
行 585: 行 621:
  
 1 5 1 5
 +
 2 3 2 3
  
行 619: 行 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=====
行 654: 行 713:
  
 4 4
 +
 4 4 4 4
 +
 1 3 1 3
 +
 2 4 2 4
 +
 3 4 3 4
  
行 662: 行 725:
  
 YES YES
 +
 4 1 2 3 4 1 2 3
  
行 667: 行 731:
  
 4 4
 +
 1 3 1 3
 +
 2 4 2 4
 +
 3 4 3 4
 +
 2 3 2 3
  
行 675: 行 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.1590930457.txt.gz · 最后更改: 2020/05/31 21:07 由 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