CERC2014训练日志

solve 5 (H C D I B)

rank 26/79

1.赛时ac的题在下面补充思路解法（思路较复杂可以贴代码）；

2.赛后补上的题在下面补充详细的思路，以及代码，要清晰；

3.补到银牌题。

https://vjudge.net/contest/216896#problem/A

A - Parades

<fzh>

注：题目中说的游行路径$(x, y)$，以下均成为节点$x$到节点$y$的着色路径；

一、思路

　　1、计算出每个节点的深度；

　　2、从树的叶子节点开始，枚举每一个节点$x$，做如下操作：

　　　　①统计当前节点$x$和儿子节点$s_i$之间的着色路径的条数；

　　　　②对于两个儿子节点$s_i$和$s_j$之间的着色路径，利用最大匹配的方式计算不相交的着色路径条数；

　　　　③对于如下情况：

　　　　显然，最大匹配为$1$，不妨假设选的匹配是$(S_1, S_2)$，如果$S_3$节点与$x$子树外的节点有着色路径(即，$\exists\ y, y \notin\ x$的子树，且$(S_3, y) = true$)，那么，把这些着色路径的$S_3$这一端转移到节点$x$上。

　　　　这并不影响最终结果，因为如果存在多个儿子节点与$x$子树外的节点有着色路径，从$x$开始一直往上走，必定会走公共边，而这样的情况只能选择其中一条路径。

　　　　还有就是，不要去想，如果$x$的儿子节点$S_i$和$S_i$的子孙节点之间有着色路径怎么办，这个算法是不是没有统计到。如果想到这，就要好好思考递推的奥秘，因为在对节点$x$做如上操作时，比$x$更深的节点都已经正确统计过了。而且他们与$S_i$子树外的着色路径的一端都已经转移到$S_i$上来了。

　　　　这是这道题中最难理解的地方。不明白就请在评论区留言。

　　3、逐层往上递推，即可求出树中无公共边的着色路径的条数。

二、源代码

#include<bits/stdc++.h>
using namespace std;
#define pb(x) push_back(x)
#define MAXN 1010
#define MAXD 11
typedef struct {
    int to, next;
} Edge;
typedef struct N1 {
    int deep, id;
    bool operator < (const N1& nd) const {
        return deep > nd.deep;
    }
} Node;
Edge tree[MAXN * 2];
Node nodes[MAXN];
int head[MAXN], ecnt;
int n, m, parent[MAXN], mat[1 << 11 | 1];
/*
L1数组，记录整棵树中的着色路径；
L2数组，记录节点x的所有儿子节点之间的着色路径；
所以，每次枚举节点x的时候，L2数组都会被清空。
*/
bool L1[MAXN][MAXN], L2[MAXD][MAXD];
vector<int> chs[MAXN];

void add(int from, int to) {
    tree[ecnt].to = to;
    tree[ecnt].next = head[from];
    head[from] = ecnt++;
}

void init() {
    memset(head, -1, sizeof(head));
    ecnt = 0;
    memset(L1, 0, sizeof(L1));
    for(int i = 0; i < MAXN; ++i)chs[i].clear();
}

void dfs(int root, int par, int d) {
    parent[root] = par;
    nodes[root].deep = d;
    nodes[root].id = root;
    for(int i = head[root], to = -1; i != -1; i = tree[i].next) {
        to = tree[i].to;
        if(to != par) {
            chs[root].pb(to);
            dfs(to, root, d + 1);
        }
    }
}

int match(int x) {
    mat[0] = 0;
    int top = (1 << chs[x].size()) - 1;
    for(int s = 1; s <= top; ++s) {
        mat[s] = 0;
        for(int i = 0, sz = chs[x].size(); i < sz; ++i) {
            for(int j = i + 1; j < sz; ++j) {
                if(L2[i][j] && (s & (1 << i)) && (s & (1 << j))) {
                    mat[s] = max(mat[s], mat[s - (1 << i) - (1 << j)] + 1);
                }
            }
        }
    }

    for(int i = 0; i < chs[x].size(); ++i) {//对应情况③
        if(mat[top - (1 << i)] == mat[top]) {
            int y = chs[x][i];
            if(!L1[x][y]) {
                for(int j = 1; j <= n; ++j) {//着色路径端点转移到节点x
                    if(j != x && j != y && parent[j] != x && L1[j][y])L1[x][j] = L1[j][x] = true;
                }
            }
        }
    }
    return mat[top];
}


int main() {
    int T, a, b;
    for(scanf("%d", &T); T--;) {
        init();
        scanf("%d", &n);
        for(int i = 1; i < n; ++i) {
            scanf("%d%d", &a, &b);
            add(a, b);
            add(b, a);
        }
        dfs(1, -1, 0);

        scanf("%d", &m);
        for(int i = 1; i <= m; ++i) {
            scanf("%d%d", &a, &b);
            L1[a][b] = L1[b][a] = true;
        }

        sort(nodes + 1, nodes + n + 1);
        int ans = 0;
        for(int i = 1; i <= n; ++i) {
            int x = nodes[i].id;
            for(int y : chs[x]) {
                if(L1[x][y])ans++;
            }

            memset(L2, 0, sizeof(L2));
            for(int j = 0, sz = chs[x].size(); j < sz; ++j) {
                for(int k = j + 1; k < sz; ++k) {
                    int s1 = chs[x][j], s2 = chs[x][k];
                    if(!L1[s1][x] && !L1[s2][x] && L1[s1][s2]) {
                        L2[j][k] = L2[k][j] = true;
                    }
                }
            }
            ans += match(x);
        }
        printf("%d\n", ans);
    }
    return 0;
}

https://vjudge.net/contest/216896#problem/B

B - Mountainous landscape （通过）

<fzh>

不解释，暴力能过。。。

https://vjudge.net/contest/216896#problem/C

C - Sums （通过）

<dzc>

水题不多说，给个N，要求表示成公差为一的等差数列且项数最小

1~sqrt(n)枚举项数，利用等差数列求和公式直接求出首项，需要判断合法性。

https://vjudge.net/contest/216896#problem/D

D - Wheels （通过）

<fzh>

思路

　　1、高中物理公式：$\omega_i\ =\ \frac{\omega_jr_j}{r_i}$，如果齿轮$i$和齿轮$j$相切；

　　2、因为题目中说了保证输入数据不会出现圆相交和卡机器的情况，所以，就不存在这种情况：

　　3、如果齿轮$i$和齿轮$j$相切，那么，建立从$i$到$j$的有向图。图建立完成之后，跑一遍dfs即可。

　　4、注意，计算两圆的圆心距的时候，不要开根号，而是直接返回圆心距的平方。再和半径和的平方比较。这样可避开浮点数精度问题。

https://vjudge.net/contest/216896#problem/E

E - Can't stop playing

<qj>

题意：一维2048。对于当前序列，只能把当前的数字放在最左边或者最右边，相邻两个数字如果相同会融合。问能否通过贪心操作使得最后序列只有一个元素。

思路：

首先，要构造的序列一定是一个' ^ '形的，因为一旦是' v '形，处于低谷的那个小数字永远不可能被消除。

那么可以把构造出来的序列拆分成左右两部分，使得左半部分呈上升趋势，右半部分呈下降趋势。

由于所有值都是二的倍数，左半部分可以用一个数字直接表示出来。

比如：左序列 1 2 4 8 可以直接用数字15表示，而数字15能且只能表示序列1 2 4 8 。

这里只讨论左半部分，右半部分其实是一样的，不再赘述。

那么，采取搜索的方式，假设选到第pos个数字时，左半序列和为lsum；

对于第pos个数字（假设为a[pos]），如果a[pos]想插在左边

（1）满足：a[pos]不大于左半序列的最小数字。

所以我们求出lsum的lowbit值，就可以知道a[pos]可不可以放在左半序列。（注意这里，如果lowbit为0，应该改为把0改为inf）

如果a[pos]可以放在左边，我们继续记忆化搜索:dfs(pos+1,lsum+a[pos]);

（2）满需：左半序列可以直接和右半序列合并，相当于把左半序列移到右边去；

如果能把左边的序列全都移到右边去，我们也能继续搜索。

至于highBit，意义和lowbit是相反的，用于记录lsum最大的那个数字是多少。

右边同理。

代码：

 1 #pragma comment(linker, "/STACK:102400000,102400000")
 2 #include<bits/stdc++.h>
 3 using namespace std;
 4 
 5 #define maxn 1024
 6 char ans[maxn];
 7 int n;
 8 int sum[maxn];
 9 bool vis[maxn][(1<<13)+5];
10 int highbit[1<<14];
11 int a[1024];
12 
13 int getlowbit(int val){
14     for(int i=0;i<14;i++){
15         if(val&(1<<i))
16             return (1<<i);
17     }return (1<<14);
18 }
19 
20 bool dfs(int pos,int lsum){
21     bool ret=0;
22     int rsum = sum[pos-1]-lsum;
23     if(pos>n){
24         if(lsum==highbit[lsum]&&rsum==highbit[rsum]&&lsum+rsum==highbit[lsum+rsum]){
25             return true;
26         }return false;
27     }
28     if(vis[pos][lsum]||vis[pos][rsum])return false;
29     vis[pos][lsum]=vis[pos][rsum]=true;
30 
31     int lowbitL = getlowbit(lsum);
32     int lowbitR = getlowbit(rsum);
33 
34     if(a[pos]<=lowbitL){
35         int L=lsum + a[pos], R=rsum;
36         if(highbit[L]==highbit[R]){
37             L+=highbit[L];
38             R-=highbit[R];
39         }
40         if(dfs(pos+1,L)){
41             ans[pos-1]='l';ret=1;
42         }
43     }
44     else if(rsum==highbit[rsum]&&rsum>=highbit[lsum]){
45         int L=lsum+rsum, R=a[pos];
46         if(highbit[L]==highbit[R]){
47             L+=highbit[L];
48             R-=highbit[R];
49         }
50         if(dfs(pos+1,L)){
51             ans[pos-1]='r';ret=1;
52         }
53     }
54     if(a[pos]<=lowbitR){
55         int L=lsum, R=rsum + a[pos];
56         if(highbit[L]==highbit[R]){
57             L+=highbit[L];
58             R-=highbit[R];
59         }
60         if(dfs(pos+1,L)){
61             ans[pos-1]='r';ret=1;
62         }
63     }
64     else if(lsum==highbit[lsum]&&lsum>=highbit[rsum]){
65         int L=a[pos], R=lsum+rsum;
66         if(highbit[L]==highbit[R]){
67             L+=highbit[L];
68             R-=highbit[R];
69         }
70         if(dfs(pos+1,L)){
71             ans[pos-1]='l';ret=1;
72         }
73     }
74     return ret;
75 }
76 
77 int main(){
78     for(int i=1;i<(1<<14);i++){
79         if((i&-i)==i)highbit[i]=i;
80         else highbit[i]=highbit[i-1];
81     }
82     int t;cin>>t;
83     while(t--){
84         scanf("%d",&n);
85         for(int i=1;i<=n;i++){
86             scanf("%d",a+i);
87             sum[i]=sum[i-1]+a[i];
88             memset(vis[i],0,sizeof(vis[i]));
89         }
90         if(dfs(1,0)){
91             ans[n]='\0';
92             printf("%s\n",ans);
93         }
94         else{
95             puts("no");
96         }
97     }
98     return 0;
99 }

https://vjudge.net/contest/216896#problem/F

F - Vocabulary

<dzc>

题意：给你三个字符串，这三个字符串有些字符以？代替了，询问有多少种合理的？替换方式使得三个字符串的字典序递增。字符串长度1000000,结果对1e9+9取余。

大半天心血都花在这上了。。看了半天网络上仅有的几个题解没有看懂。

官方题解很有意思，说是先两个两个的预处理，最后放到一起推，想了许久还是不知道怎么利用每两个字符串之间的关系处理出三个字符串的。

于是只能强行三个一起dp找状态转移。感觉我没有找到最佳的状态表示方法，但是没办法咯。

思路：设三个字符串为Sa,Sb,Sc,开dp[1000000][4],其中

dp[i][0] 代表到i位置时，使得字典序Sa=Sb=Sc的方案数

dp[i][1] 代表到i位置时，使得字典序Sa<Sb=Sc的方案数

dp[i][2] 代表到i位置时，使得字典序Sa=Sb<Sc的方案数

dp[i][3] 代表到i位置时，使得字典序Sa<Sb<Sc的方案数

对于每个位置i，三个字符串的当前字符情况有8种，如下：(X代表已知的某字符,?代表需要替换的问号)

1 2 3 4 5 6 7 8

X ? X X ? ? X ?

X X ? X ? X ? ?

X X X ? X ? ? ?

这8种情况对应着8种状态转移(转移实在是太多，所以我认为这应该不是个好方法)

在推导转移式的时候注意Sa=Sb=Sc可以衍生出其他三种状态

Sa<Sb=Sc和Sa=Sb<Sc都只能衍生出自己和Sa<Sb<Sc

而Sa<Sb<Sc只能衍生出自己。

说简单点，就是只能等号变小于号，小于号不能变等号。

计算出每种情况下上一个位置i-1的每一个状态能够衍生出当前位置的状态的数量(有点绕)

就能得到状态转移，一直递推，dp[N][3]即是结果.

注：N是三个字符串长度的最大值，注意当字符串长度不等时短的字符串不够长的部分要补 -1 ('a'-1)

式子太多就不罗列了。直接上代码。

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 const int mod=1e9+9;
  4 int sa[1000100],sb[1000100],sc[1000100],len,n;//-1代表字符不存在 <-1代表是？ 0-25代表a-z
  5 char s[1000100];
  6 long long dp[1000100][4];
  7 int main()
  8 {
  9     int t;
 10     cin>>t;
 11     while(t--)
 12     {
 13         n=0;
 14         memset(sa,-1,sizeof(sa));
 15         memset(sb,-1,sizeof(sb));
 16         memset(sc,-1,sizeof(sc));
 17         scanf("%s",s);
 18         len=strlen(s);
 19         n=max(n,len);
 20         for(int i=1;i<=len;i++)
 21         {
 22             sa[i]=s[i-1]-'a';
 23         }
 24         scanf("%s",s);
 25         len=strlen(s);
 26         n=max(n,len);
 27         for(int i=1;i<=len;i++)
 28         {
 29             sb[i]=s[i-1]-'a';
 30         }
 31         scanf("%s",s);
 32         len=strlen(s);
 33         n=max(n,len);
 34         dp[0][0]=1;
 35         for(int i=1;i<=len;i++)
 36         {
 37             sc[i]=s[i-1]-'a';
 38         }
 39         for(int i=1;i<=n;i++)
 40         {
 41             if(sa[i]<-1&&sb[i]<-1&&sc[i]<-1)
 42             {
 43                 dp[i][0]=26*dp[i-1][0];
 44                 dp[i][1]=325*dp[i-1][0]+676*dp[i-1][1];
 45                 dp[i][2]=325*dp[i-1][0]+676*dp[i-1][2];
 46                 dp[i][3]=2600*dp[i-1][0]+325*26*dp[i-1][1]+325*26*dp[i-1][2]+26*26*26*dp[i-1][3];
 47             }
 48             else if(sa[i]<-1&&sb[i]<-1)
 49             {
 50                 dp[i][0]=dp[i-1][0];
 51                 dp[i][1]=sc[i]*dp[i-1][0]+26*dp[i-1][1];
 52                 dp[i][2]=sc[i]*dp[i-1][0]+26*dp[i-1][2];
 53                 dp[i][3]=sc[i]*(sc[i]-1)/2*dp[i-1][0]+26*sc[i]*dp[i-1][1]+325*dp[i-1][2]+26*26*dp[i-1][3];
 54             }
 55             else if(sa[i]<-1&&sc[i]<-1)
 56             {
 57                 dp[i][0]=dp[i-1][0];
 58                 dp[i][1]=sb[i]*dp[i-1][0]+26*dp[i-1][1];
 59                 dp[i][2]=(25-sb[i])*dp[i-1][0]+26*dp[i-1][2];
 60                 dp[i][3]=sb[i]*(25-sb[i])*dp[i-1][0]+26*(25-sb[i])*dp[i-1][1]+26*sb[i]*dp[i-1][2]+26*26*dp[i-1][3];
 61             }
 62             else if(sb[i]<-1&&sc[i]<-1)
 63             {
 64                 dp[i][0]=dp[i-1][0];
 65                 dp[i][1]=(25-sa[i])*dp[i-1][0]+26*dp[i-1][1];
 66                 dp[i][2]=(25-sa[i])*dp[i-1][0]+26*dp[i-1][2];
 67                 dp[i][3]=(25-sa[i])*(24-sa[i])/2*dp[i-1][0]+325*dp[i-1][1]+26*(25-sa[i])*dp[i-1][2]+26*26*dp[i-1][3];
 68             }
 69             else if(sc[i]<-1)
 70             {
 71                 if(sa[i]==sb[i]) dp[i][0]=dp[i-1][0]; else dp[i][0]=0;
 72                 if(sa[i]<sb[i]) dp[i][1]=dp[i-1][0]+dp[i-1][1]; else dp[i][1]=dp[i-1][1];
 73                 if(sa[i]==sb[i]) dp[i][2]=(25-sb[i])*dp[i-1][0]+26*dp[i-1][2]; else dp[i][2]=0;
 74                 if(sa[i]<sb[i]) dp[i][3]=(25-sb[i])*dp[i-1][0]+(25-sb[i])*dp[i-1][1]+26*dp[i-1][2]+26*dp[i-1][3]; else dp[i][3]=(25-sb[i])*dp[i-1][1]+26*dp[i-1][3];
 75             }
 76             else if(sb[i]<-1)
 77             {
 78                 if(sa[i]==sc[i]) dp[i][0]=dp[i-1][0]; else dp[i][0]=0;
 79                 if(sa[i]<sc[i]) dp[i][1]=dp[i-1][0]+dp[i-1][1]; else dp[i][1]=dp[i-1][1];
 80                 if(sa[i]<sc[i]) dp[i][2]=dp[i-1][0]+dp[i-1][2]; else dp[i][2]=dp[i-1][2];
 81                 if(sc[i]-sa[i]>1) dp[i][3]=(sc[i]-sa[i]-1)*dp[i-1][0]+sc[i]*dp[i-1][1]+(25-sa[i])*dp[i-1][2]+26*dp[i-1][3]; else dp[i][3]=sc[i]*dp[i-1][1]+(25-sa[i])*dp[i-1][2]+26*dp[i-1][3];
 82             }
 83             else if(sa[i]<-1)
 84             {
 85                 if(sb[i]==sc[i]) dp[i][0]=dp[i-1][0]; else dp[i][0]=0;
 86                 if(sb[i]==sc[i]) dp[i][1]=sb[i]*dp[i-1][0]+26*dp[i-1][1]; else dp[i][1]=0;
 87                 if(sb[i]<sc[i]) dp[i][2]=dp[i-1][0]+dp[i-1][2]; else dp[i][2]=dp[i-1][2];
 88                 if(sb[i]<sc[i]) dp[i][3]=sb[i]*dp[i-1][0]+26*dp[i-1][1]+sb[i]*dp[i-1][2]+26*dp[i-1][3]; else dp[i][3]=sb[i]*dp[i-1][2]+26*dp[i-1][3];
 89             }
 90             else
 91             {
 92                 if(sa[i]==sb[i]&&sa[i]==sc[i]) dp[i][0]=dp[i-1][0]; else dp[i][0]=0;
 93                 if(sb[i]!=sc[i]) dp[i][1]=0; else if(sa[i]<sb[i]) dp[i][1]=dp[i-1][0]+dp[i-1][1]; else dp[i][1]=dp[i-1][1];
 94                 if(sa[i]!=sb[i]) dp[i][2]=0; else if(sb[i]<sc[i]) dp[i][2]=dp[i-1][0]+dp[i-1][2]; else dp[i][2]=dp[i-1][2];
 95                 if(sa[i]<sb[i]&&sb[i]<sc[i]) dp[i][3]=dp[i-1][0]+dp[i-1][1]+dp[i-1][2]+dp[i-1][3];
 96                 else if(sa[i]<sb[i]) dp[i][3]=dp[i-1][2]+dp[i-1][3];
 97                 else if(sb[i]<sc[i]) dp[i][3]=dp[i-1][1]+dp[i-1][3];
 98                 else dp[i][3]=dp[i-1][3];
 99             }
100             dp[i][0]%=mod;
101             dp[i][1]%=mod;
102             dp[i][2]%=mod;
103             dp[i][3]%=mod;
104         }
105         cout<<dp[n][3]<<endl;
106     }
107 }