这道题是一道$dp$啊.. 思路都对了 但是我没有考虑到所有的转移情况都可以变成两堆进行处理
所以我的想法是$dp[i][j]$表示$i$个盘子在$j$个柱子里转移
然后我每次是枚举分成的堆数 然后取$min$ 如果只考虑变成两堆转移就会简单很多
然后要知道$n$个盘子在三个柱子里转移的步数是$2^{n} - 1$
方程
$dp[i][j] = min(2 * dp[k][j] + dp[i - k][j - 1])$
相当于先把上面一坨挪到一个柱子上 再把另外的用剩下的柱子转移 最后再把原先那一坨挪回去
代码
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 200; int n,m; ll p[N],dp[N][N]; void Init( ) { scanf("%d%d",& n,& m); p[0] = 1; for(int i = 1;i <= 63;i ++) p[i] = p[i - 1] * 2; } void Solve( ) { memset(dp,0x3f,sizeof(dp)); for(int i = 1;i <= n;i ++) dp[i][3] = p[i] - 1; for(int i = 1;i <= m;i ++) dp[0][i] = 0,dp[1][i] = 1,dp[2][i] = 3; for(int i = 1;i <= n;i ++) { for(int j = 4;j <= m;j ++) { for(int k = 1;k <= i;k ++) { dp[i][j] = min(dp[i][j], 2 * dp[k][j] + dp[i - k][j - 1]); } } } printf("%lld ",dp[n][m]); } int main( ) { freopen("hanoi.in","r",stdin); freopen("hanoi.out","w",stdout); Init( ); Solve( ); }
这道题我考试的时候竟然$A$了 qwqwqwqwqwq
当时考的时候乱搞搞出来的规律... 证明一下发现对了...
我们按照排名从前往后处理每个位置的值 然后因为是从前往后搞的 所以现在填的位置肯定比前一个要排名靠后
所以我们比较排名上一个的后面的位置排名$pre$和现在这个位置$now$的排名 如果$rank pre < rank now$
那么就说明我现在这个位置可以和上个位置填的字母一样 因为我后面的字母会帮助我把排名提起来
反之则必须自己帮自己 因为我后面的字符串没有前面的厉害 必须自己把排名搞上去
代码
#include <bits/stdc++.h> using namespace std; const int N = 2 * 1e5 + 5; int n,a[N],s[N],pos[N]; void Init( ) { scanf("%d",& n); for(int i = 1;i <= n;i ++) { scanf("%d",& a[i]); pos[a[i]] = i; } a[n + 1] = -1; } void Solve( ) { int ma = 0,now = 0; for(int i = 1;i <= n;i ++) { int p = pos[i]; if(i == 1) { s[p] = now; ma = max(ma,a[p + 1]); } else { if(a[p + 1] > ma) { s[p] = now; ma = max(a[p + 1],ma); } else { s[p] = ++ now; ma = a[p + 1]; } } } if(now > 25) { printf("-1"); return ; } for(int i = 1;i <= n;i ++) printf("%c",s[i] + 'a'); } int main( ) { freopen("rank.in","r",stdin); freopen("rank.out","w",stdout); Init( ); Solve( ); }
这道题是以前讲过的原题啊.. 而且还讲过两次
然后我每次都听懂了.. 遇到题仍然还是写不来... 题解写得蛮好的 我复制一波
化简一波发现
$f[u] = du + sum f[v]$ $v$是$u$的所有孩子,$du$是那个点的度数
$g[u] = du + g[fa] + sum f[v]$ $v$是$fa$不包括$u$的所有孩子
然后维护每条到根节点链的$f,g$之和 然后用$lca$作作差即可
代码
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int P = 20; const int N = 1e5 + 5; const int MOD = 1e9 + 7; int n,m,head[N],nex[2 * N],tov[2 * N],d[N]; int tot,anc[N][P + 1],fa[N],dep[N]; int disf[N],disg[N]; ll f[N],g[N]; void moc(ll & a,ll b) { a = (a + b) % MOD; } void add(int u,int v) { tot ++; nex[tot] = head[u]; tov[tot] = v; head[u] = tot; d[v] ++; d[u] ++; } void Dfs_f(int u, int fat) { anc[u][0] = fat; for(int i = 1;i <= P;i ++) anc[u][i] = anc[anc[u][i - 1]][i - 1]; fa[u] = fat; bool tag = false; for(int i = head[u];i;i = nex[i]) { int v = tov[i]; if(v == fat) continue; dep[v] = dep[u] + 1; Dfs_f(v, u); moc(f[u], f[v] + 1); } moc(f[u], 1); } void Dfs_g(int u, int fat) { ll s = 0; for(int i = head[u];i;i = nex[i]) { int v = tov[i]; if(v == fat) moc(s,g[u] + 1); else moc(s,f[v] + 1); } for(int i = head[u];i;i = nex[i]) { int v = tov[i]; if(v == fat) continue; g[v] = s - f[v]; Dfs_g(v, u); } } int find_lca(int u,int v) { if(dep[u] < dep[v]) swap(u, v); int del = dep[u] - dep[v]; for(int i = P;i >= 0;i --) if(del & (1 << i)) u = anc[u][i]; if(u == v) return u; for(int i = P;i >= 0;i --) if(anc[u][i] != anc[v][i]) v = anc[v][i], u = anc[u][i]; return fa[u]; } void Get(int u) { disf[u] = (disf[fa[u]] + f[u]) % MOD; disg[u] = (disg[fa[u]] + g[u]) % MOD; for(int i = head[u];i;i = nex[i]) { int v = tov[i]; if(v == fa[u]) continue; Get(v); } } void Init( ) { scanf("%d%d",& n,& m); for(int i = 1;i < n;i ++) { int u,v; scanf("%d%d",& u,& v); add(u, v); add(v, u); } Dfs_f(1, 0); Dfs_g(1, 0); f[1] = 0; Get(1); } void Solve( ) { while(m --) { int u,v; scanf("%d%d",& u,& v); int lca = find_lca(u, v); ll ans = ((disf[u] - disf[lca] + disg[v] - disg[lca]) % MOD + MOD) % MOD; printf("%lld ",ans); } } int main( ) { freopen("tree.in","r",stdin); freopen("tree.out","w",stdout); Init( ); Solve( ); }