无题6

题解：

第一题：类比只有三根，四根的柱子的汉诺塔，柱子越多越好，柱子盘子固定，步数一定，如果我有K个盘子，J个柱子，把P个盘子移到1个柱子的步数为F【P】【J】，那么剩余K-P个盘子移到1个柱子就是F【K-P】【J-1】，放P的柱子不能再放了，然后我们又有J个可以自由移动的柱子，

所以f[ i ][ j ] = min(f[ k ][ j ] * 2 + f[ i - k ][ j -1 ]), 枚举k即可；

#include<bits/stdc++.h>
using namespace std;
long long dp[70][70];



int main(){
    freopen("hanoi.in","r",stdin);
    freopen("hanoi.out","w",stdout);
    int n, m;
    scanf("%d%d", &n, &m);
    
    memset(dp, 0x3f, sizeof(dp));
    
    dp[1][3] = 1;
    for(int i = 2; i <= n; i++) dp[i][3] = ((dp[i - 1][3] + 1) << 1) - 1;
    for(int i = 1; i <= 65; i++) dp[0][i] = 0, dp[1][i] = 1, dp[2][i] = 3;
    
    
    for(int i = 4; i <= m; i++)
        for(int j = 3; j <= n; j++){
            for(int k = 1; k <= j; k++)
                dp[j][i] = min(2 * dp[j - k][i] + dp[k][i - 1], dp[j][i]);
        }
    printf("%lld
", dp[n][m]);
}

View Code

第二题：

我只想说cyj太聪明了

#include<bits/stdc++.h>
using namespace std;
const int M = 200005;
char s[M]; int b[M];
struct node{
    int val, id;
    bool operator < (const node &rhs) const{
        return val < rhs.val;
    }
}a[M];

int q[M], h, t;
int main(){
    freopen("rank.in","r",stdin);
    freopen("rank.out","w",stdout);
    int n, fg = 0;
    scanf("%d", &n);
    char now = 'a';
    for(int i = 1; i <= n; i++){
        scanf("%d", &a[i].val), a[i].id = i; b[i] = a[i].val;
    }
    sort(a + 1, a + 1 + n);
    int lst = 0; a[n+1].id = -1;
    for(int i = 1; i <= n; i++){
        node p; p.val = i;
        int pos = lower_bound(a + 1, a + 1 + n, p) - a;
        if(b[a[pos].id + 1] > lst) s[a[pos].id] = now;
        else s[a[pos].id] = ++now;
        lst = b[a[pos].id + 1];
        if(now > 'z'){fg = -1;break;}
    }
    if(fg)puts("-1");
    else for(int i = 1; i <= n; i++)printf("%c", s[i]);
}

View Code

第三题：期望DP，以前讲过，终于还是写了这道题

F化简：f(u) = sum ( f(v) ) + deg(u) , v is u's child

G化简：g(u) = g(fa(u)) + f(fa(u)) - f(u);

注意求完f,然后用f更新g, 修改f[ 1 ] = 0, 因为1不会再往上走，但更新g之前不能改F1，是有实际有意的；

#include<bits/stdc++.h>
using namespace std;
#define ex(i, u) for(int i = h[u]; i; i = G[i].nxt)
const int mod = 1e9 + 7, M = 1e5 + 5;
int P = 20, f[M], g[M], F[M], GV[M], dep[M], deg[M], anc[M][25], h[M], tot;
struct edge{int nxt, v;}G[M<<1];
void add(int u, int v){G[++tot].v = v, G[tot].nxt = h[u], h[u] = tot;}
inline int moc(int a){return a >= mod ? a - mod : a;}
void dfs1(int u, int fa){
    anc[u][0] = fa;
    for(int p = 1; p <= P; p++)
        anc[u][p] = anc[anc[u][p - 1]][p - 1];
    ex(i, u){
        int v = G[i].v;
        if(v == fa)continue;
        dfs1(v, u);
        f[u] = moc(f[u] + f[v]);
    }
    f[u] = moc(f[u] + deg[u]);
}

void dfs2(int u, int fa){
    dep[u] = dep[fa] + 1;    
     F[u] = moc(F[fa] + f[u]);
     GV[u] = moc(GV[fa] + g[u]);
    ex(i, u){
        int v = G[i].v;
        if(v == fa)continue;
        g[v] = (g[u] + f[u] - f[v] + mod) % mod;
        dfs2(v, u);
    }
}

int get(int u, int v){
    if(dep[u] < dep[v])swap(u, v);
    int t = dep[u] - dep[v];
    for(int p = 0; t; t >>= 1, p++)
        if(t & 1) u = anc[u][p];
    if(u == v) return u;
    
    for(int p = P; p >= 0; p--)
        if(anc[u][p] != anc[v][p])
            u = anc[u][p], v = anc[v][p];
    return anc[u][0];
}


int main(){
    freopen("tree.in","r",stdin);
    freopen("tree.out","w",stdout);
    int n, q, u, v;
    scanf("%d%d", &n, &q);
    for(int i = 1; i < n; i++){
        scanf("%d%d", &u, &v);
        add(u, v); add(v, u);
        deg[u]++; deg[v]++;
    }
    dfs1(1, 0);
    F[0] = -f[1];
    dfs2(1, 0);
    //for(int i = 1; i <= n; i++)printf("%d %d %d %d %d
", i, f[i], g[i], F[i], GV[i]);
    f[1] = 0;
    while(q--){
        scanf("%d%d", &u, &v);
        int lca = get(u, v), flca = anc[lca][0];
        int ans = ( (F[u] - F[lca] + GV[v] - GV[lca]) % mod + mod ) % mod;
        printf("%d
", ans);
    }
}

View Code