补一下之前的总结……
T1.restaurant
这道题还是很简单的嘛，子恒dalao非常良心。我们把招牌菜和所需要的菜品绑定在一起就成了完全背包，然后直接跑一遍完全背包即可。
#include<cstdio> #include<algorithm> #include<cstring> #include<iostream> #include<cmath> #include<queue> #include<set> #define rep(i,a,n) for(int i = a;i <= n;i++) #define per(i,n,a) for(int i = n;i >= a;i--) #define enter putchar(' ') using namespace std; typedef long long ll; const int M = 5005; ll read() { ll ans = 0,op = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') op = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { ans *= 10; ans += ch - '0'; ch = getchar(); } return ans * op; } ll T,n,m,t[M],tmax,w[M],x,dp[M]; int main() { freopen("restaurant.in","r",stdin); freopen("restaurant.out","w",stdout); T = read(); while(T--) { memset(dp,0,sizeof(dp)); n = read(),m = read(),tmax = read(); rep(i,1,n) t[i] = read(),w[i] = read(); rep(i,1,m) t[n+i] = read(),w[n+i] = read(); rep(i,1,m) rep(j,1,n) x = read(),t[n+i] += x * t[j]; rep(i,1,n+m) { rep(j,t[i],tmax) dp[j] = max(dp[j],dp[j-t[i]] + w[i]); } printf("%lld ",dp[tmax]); } return 0; }
T2.olefin
这道题当时想了60分暴力，反正就是直接从一个点开始向两边暴搜即可。
然后有20分是可以固输的，还有40分直接暴力，于是就得了60.
然后这道题的正解是换根DP，就是我们先求出一个点所在子树深度最大的点的深度，然后再记录fromroot表示从根来的最长链的长度，首先一遍dfs求出深度之后，我们对于每个点用fromroot更新其儿子的答案，然后更新它儿子的fromroot。
之后我们对于每一个点找出儿子之中深度最大的和次大的，用次大更新最大，最大更新其他即可。
60分暴力：
#include<cstdio> #include<algorithm> #include<cstring> #include<iostream> #include<cmath> #include<queue> #include<set> #define rep(i,a,n) for(int i = a;i <= n;i++) #define per(i,n,a) for(int i = n;i >= a;i--) #define enter putchar(' ') using namespace std; typedef long long ll; const int M = 100005; int read() { int ans = 0,op = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') op = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { ans *= 10; ans += ch - '0'; ch = getchar(); } return ans * op; } struct edge { int next,to,from; }e[M<<1]; int id,n,m,ecnt,head[M],t,sum,maxn,x,dis[M]; bool vis[M]; void add(int x,int y) { e[++ecnt].to = y; e[ecnt].next = head[x]; head[x] = ecnt; } void dfs(int x) { dis[x] = 0,vis[x] = 1; int maxm = 0; bool flag = 0; for(int i = head[x];i;i = e[i].next) { if(vis[e[i].to]) continue; if(e[i].to > n) continue; dfs(e[i].to); flag = 1; maxm = max(maxm,dis[e[i].to]); } if(flag) dis[x] += maxm,dis[x]++; } void naive(int x) { rep(i,1,n) vis[i] = 0; int k = ((x-1)<<1)-1; int r1 = e[k].to,r2 = x; //printf("#%d %d ",r1,r2); vis[r1] = vis[r2] = 1; dfs(r1); vis[r1] = vis[r2] = 1; dfs(r2); //printf("!%d %d ",dis[r1],dis[r2]); printf("%d ",dis[r1] + dis[r2] + 1); } int main() { freopen("olefin.in","r",stdin); freopen("olefin.out","w",stdout); id = read(); t = read(); while(t--) { n = read(),m = read(); ecnt = 0;rep(i,1,n) head[i] = 0; rep(i,1,n<<1) e[i].next = e[i].to = 0; rep(i,2,n) x = read(),add(i,x),add(x,i); rep(i,1,m) { x = read(); if(id == 5) printf("%d ",n-1); else if(id == 6) printf("2 "); else naive(x); } enter; } return 0; }
100分：
#include <bits/stdc++.h> #define enter putchar(' ') #define space putchar(' ') #define pii pair<int,int> #define fi first #define se second #define MAXN 100005 #define pb push_back #define ivorysi using namespace std; typedef long long int64; typedef double db; template<class T> void read(T &res) { res = 0;T f = 1;char c = getchar(); while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); } while(c >= '0' && c <= '9') { res = res * 10 + c - '0'; c = getchar(); } res *= f; } template<class T> void out(T x) { if(x < 0) {x = -x;putchar('-');} if(x >= 10) out(x / 10); putchar('0' + x % 10); } int N,M,fa[MAXN]; int dp[MAXN],ans[MAXN],fr[MAXN]; struct node { int to,next; }E[MAXN * 2]; int head[MAXN],sumE; void add(int u,int v) { E[++sumE].to = v; E[sumE].next = head[u]; head[u] = sumE; } void dfs1(int u) { for(int i = head[u] ; i ; i = E[i].next) { int v = E[i].to; dfs1(v); dp[u] = max(dp[v] + 1,dp[u]); } } void dfs2(int u) { pii p(0,0); for(int i = head[u] ; i ; i = E[i].next) { int v = E[i].to; ans[v] = max(dp[v] + 1 + fr[u],ans[v]); fr[v] = max(fr[v],fr[u] + 1); if(dp[v] >= dp[p.se]) p.se = v; if(dp[p.se] >= dp[p.fi]) swap(p.se,p.fi); } for(int i = head[u] ; i ; i = E[i].next) { int v = E[i].to; if(v != p.fi) { ans[v] = max(dp[v] + 2 + dp[p.fi],ans[v]); fr[v] = max(fr[v],dp[p.fi] + 2); } else if(p.se) { ans[p.fi] = max(ans[p.fi],dp[p.fi] + 2 + dp[p.se]); fr[p.fi] = max(fr[p.fi],dp[p.se] + 2); } dfs2(v); } } void Solve() { memset(head,0,sizeof(head));sumE = 0; memset(fr,0,sizeof(fr));memset(dp,0,sizeof(dp));memset(ans,0,sizeof(ans)); read(N);read(M); for(int i = 2 ; i <= N ; ++i) { read(fa[i]); add(fa[i],i); } dfs1(1);dfs2(1); int x; for(int i = 1 ; i <= M ; ++i) { read(x);out(ans[x]); if(i == M) enter; else space; } if(!M) enter; } int main() { freopen("olefin.in","r",stdin); freopen("olefin.out","w",stdout); int id,T; read(id);read(T); while(T--) { Solve(); } return 0; }
T3.tromino
这道题当时自己确实不知道该怎么做啊……
后来听了讲解竟然要分成那么多情况……我们考虑当左侧都填满的时候右侧有多少种填充情况。一共有九种，然后考虑在这个基础上把左边那一列填满，然后把这个3*2的窗口向右移动一列，看他们的变化情况……
然后你发现每步的移动都是一样的，你就能得到一个9*9的矩阵。
如果你使用OEIS网站或者高斯消元……可以把其简化为一个6*6矩阵，然后转移即可……
其实这道题的递推公式可以在OEIS上搜到的。
哦，然后因为这题的数据范围过大，即使是快速幂也满足不了需求，所以我们使用十进制快速幂，也就是每次把这个数一位一位的去进行快速幂即可，然后每次要乘上当前矩阵的10次幂。
看一下std，自己改过的代码找不到了……
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long ll; const int tb[6][6] = { {0, 1, 0, 0, 0, 0}, {0, 0, 1, 0, 0, 0}, {0, 0, 0, 1, 0, 0}, {0, 0, 0, 0, 1, 0}, {0, 0, 0, 0, 0, 1}, {-1, 0, 1, 6, 2, 1}, }; const int pre_ans[6] = {1, 1, 3, 10, 23, 62}; const int N = 1000005, P = 998244353; char s[N]; int n, a[N]; struct matrix { ll g[6][6]; matrix(){ memset(g, 0, sizeof(g)); } matrix operator * (const matrix &b) const { matrix c; for(int i = 0; i < 6; i++) for(int j = 0; j < 6; j++) for(int k = 0; k < 6; k++) c.g[i][j] = (c.g[i][j] + g[i][k] * b.g[k][j]) % P; return c; } } mtx, ans, tmp, pw[10]; int main(){ scanf("%s", s); n = strlen(s); if(n == 1 && s[0] < '6'){ printf("%d ", pre_ans[s[0] - '0']); return 0; } for(int i = 0; i < n; i++) a[i] = s[n - i - 1] - '0'; a[0] -= 5; for(int i = 0; a[i] < 0; i++) a[i] += 10, a[i + 1]--; while(n && a[n - 1] == 0) n--; for(int i = 0; i < 6; i++) for(int j = 0; j < 6; j++) mtx.g[i][j] = tb[i][j]; for(int i = 0; i < 6; i++) pw[0].g[i][i] = 1; for(int i = 1; i <= 9; i++) pw[i] = pw[i - 1] * mtx; ans = pw[0]; for(int i = n - 1; i >= 0; i--){ tmp = ans = ans * ans; ans = ans * ans; ans = ans * ans * tmp * pw[a[i]]; } for(int i = 0; i < 6; i++) mtx.g[i][0] = pre_ans[i]; ans = ans * mtx; printf("%lld ", ans.g[5][0]); return 0; }