2012-C08-team1
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
{{{
卖队友了。。。
我看了几题给你们发了想法到A题，都没注意看啊。。。
看了你们AC代码发现我考虑到的DP转移是对的，附录一个
——prowindy
}}}
{{{
附录：场外支援（已证明被无视了。。）
赛后敲了B交 发现一开始发你们的做法有问题，需要注意
1. 乘法会爆long long 注意判inf 不影响答案 2. 每次要把字符串0位置也标为check候选集
加上这两点，就是对的了。
/*
* E题题意是：给一个树，每个节点有2个儿子（**二叉树？），这个节点的儿子或者是另一个节点（有2儿子），或者是结局（无儿子）
* 可以有个记录游戏存档的操作，
* 但是只能记录最后一次存档，问至多走多少步，可以走完所有结局。
*
*
* 也就是打游戏时想玩到所有结局，没必要从头开始玩，可以在某个地方存档，玩完一个结局，跳到这个存档继续往下玩。
*
* 树形DP之：
* f[i][0] 表示只在i点存档，每次跳回i点继续玩，需要走多少步，走完i子树所有结局
* f[i][1] 表示在i这棵子树随意存档，需要多少步
* f[i][2] 表示i这棵子树下需要完成的结局有多少个
*
* dfs( i ){
* if (i==N) //是结局
* {
* f[i][0] = f[i][1] = 0,f[i][2] = 1;
* return ;
* }
* f[i][2] = f[L][2]+f[R][2];
* f[i][0] = f[L][0]+f[R][0]+f[i][2];//走完L子树，走完R子树，需要f[i][2]次走到子树
* f[i][1] = min(
* f[L][2]+f[L][0] + 1+f[R][1]; //每次回到i点继续走暴力走完L子树，需要f[L][2]次走到L子树， R子树随意用存档
* f[R][2]+f[R][0] + 1+f[L][1];// 同上，先暴力走R子树，再智能走L子树
* 1+f[L][1] + dep[i]+ 1+f[R][1];//不在i保存，智能走L子树，从头游戏走到i,智能走R子树
* );
* }
*
* ans = min(f[i][0],f[i][1]);
*
* 方程肯定没问题，50W的DFS可能有点大，RE的话可以写非递归的版本。
*
*
*
*
*
* B题就是：给N个字符串，要求字典序第K小的长度为M的由它们拼接成的串是什么。
* 首先定义几个值：
* 1. cnt[i]表示凑成长度为i的串，任意使用这些字符串，有多少种方法。
* 2. check[i][j]表示输入的第i号串的第j个字符当前是否可取用。
* 3. pre[i]表示答案串的前i个字符，可以有多少种整个串的凑法，要求凑法都是字典序<=答案串的substr(0,i)
* 4. calc[c]表示当前选择时，如果选取了c字符，那之前有多少种串是会字典序<=这个选择的
*
* 那么，输入后，先预处理for (i 0-> M) for (each str) cnt[i] +=cnt[i-len(str)];
* 初始化 for (each str[i]) check[i][0] = len(str[i])<=M;
*
* 然后枚举答案串的第i个字符
* for (i 0->M){
* 计算calc[c]：
* for (j 0->N)
* for (k 0->len(str[j]))
* if (check[j][k]){ //第k个可用于连接
* c = str[j][k];
* calc[c] += pre[除去这个串前面有多长] * cnt[除去这个串后面有多长];
* }
*
* for (c 0->26)
* {
* finalans[i] = c;
* if (calc[c]<=K){
* 维护每个串的check[][]，顺便更新pre[]——这样枚举到的串肯定组成字典序<=finalans，所以可以更新pre[]
* if (check[j][k]==c){
* check[j][k+1] = true;
* if (k+1==length)
* pre[i] += pre[i-length];
* }
* K-=calc[c];
* }
* }
* }
*
* 输出答案finalans[]；
* GL!!
*/
}}}卖队友了。。。
我看了几题给你们发了想法到A题，都没注意看啊。。。
看了你们AC代码发现我考虑到的DP转移是对的，附录一个
——prowindy
附录：场外支援（已证明被无视了。。）
赛后敲了B交 发现一开始发你们的做法有问题，需要注意
1. 乘法会爆long long 注意判inf 不影响答案 2. 每次要把字符串0位置也标为check候选集
加上这两点，就是对的了。
/*
* E题题意是：给一个树，每个节点有2个儿子（**二叉树？），这个节点的儿子或者是另一个节点（有2儿子），或者是结局（无儿子）
* 可以有个记录游戏存档的操作，
* 但是只能记录最后一次存档，问至多走多少步，可以走完所有结局。
*
*
* 也就是打游戏时想玩到所有结局，没必要从头开始玩，可以在某个地方存档，玩完一个结局，跳到这个存档继续往下玩。
*
* 树形DP之：
* f[i][0] 表示只在i点存档，每次跳回i点继续玩，需要走多少步，走完i子树所有结局
* f[i][1] 表示在i这棵子树随意存档，需要多少步
* f[i][2] 表示i这棵子树下需要完成的结局有多少个
*
* dfs( i ){
* if (i==N) //是结局
* {
* f[i][0] = f[i][1] = 0,f[i][2] = 1;
* return ;
* }
* f[i][2] = f[L][2]+f[R][2];
* f[i][0] = f[L][0]+f[R][0]+f[i][2];//走完L子树，走完R子树，需要f[i][2]次走到子树
* f[i][1] = min(
* f[L][2]+f[L][0] + 1+f[R][1]; //每次回到i点继续走暴力走完L子树，需要f[L][2]次走到L子树， R子树随意用存档
* f[R][2]+f[R][0] + 1+f[L][1];// 同上，先暴力走R子树，再智能走L子树
* 1+f[L][1] + dep[i]+ 1+f[R][1];//不在i保存，智能走L子树，从头游戏走到i,智能走R子树
* );
* }
*
* ans = min(f[i][0],f[i][1]);
*
* 方程肯定没问题，50W的DFS可能有点大，RE的话可以写非递归的版本。
*
*
*
*
*
* B题就是：给N个字符串，要求字典序第K小的长度为M的由它们拼接成的串是什么。
* 首先定义几个值：
* 1. cnt[i]表示凑成长度为i的串，任意使用这些字符串，有多少种方法。
* 2. check[i][j]表示输入的第i号串的第j个字符当前是否可取用。
* 3. pre[i]表示答案串的前i个字符，可以有多少种整个串的凑法，要求凑法都是字典序<=答案串的substr(0,i)
* 4. calc[c]表示当前选择时，如果选取了c字符，那之前有多少种串是会字典序<=这个选择的
*
* 那么，输入后，先预处理for (i 0-> M) for (each str) cnt[i] +=cnt[i-len(str)];
* 初始化 for (each str[i]) check[i][0] = len(str[i])<=M;
*
* 然后枚举答案串的第i个字符
* for (i 0->M){
* 计算calc[c]：
* for (j 0->N)
* for (k 0->len(str[j]))
* if (check[j][k]){ //第k个可用于连接
* c = str[j][k];
* calc[c] += pre[除去这个串前面有多长] * cnt[除去这个串后面有多长];
* }
*
* for (c 0->26)
* {
* finalans[i] = c;
* if (calc[c]<=K){
* 维护每个串的check[][]，顺便更新pre[]——这样枚举到的串肯定组成字典序<=finalans，所以可以更新pre[]
* if (check[j][k]==c){
* check[j][k+1] = true;
* if (k+1==length)
* pre[i] += pre[i-length];
* }
* K-=calc[c];
* }
* }
* }
*
* 输出答案finalans[]；
* GL!!
*/