[HZOI] CSP-S模拟37 赛后总结
我就是大 DP fw！
今天是 dp 专场。
爆炸心路历程
直接开 T1。
据说是签到题。。。但是我没签上到（心态炸了qwq）
题面描述很简单，就是拼好串，求最大回文串长度。
赛时开题一看回文串！
坏了，忘了马拉车怎么打了，有点心慌。
然后直接去考虑怎么贪心去了。
想了一万个贪心策略，全被自己 hack 了，然后就这样，2 hours 过去了。
开始慌到爆炸！
要保龄了要保龄了，怎么办怎么办！？
我不想保龄啊啊啊
然后发现貌似可以dp。
然后设了个特别离谱的四维dp。
开始狂推不止，推不出来。。。
大脑根本无法思考，什么！？已经过去 3 hours了。
不行，先开后边的题吧，至少拿个暴力分。
欸？T2怎么这么简单？切了切了
欸？T3暴力能有 70 tps！？打了打了
欸？T4我会打 30 tps!做了做了
然后在半个小时的时间内拿了所有的分。。。
之后最后半小时继续凹 T1，要不先打个暴力吧，能有 20 tps先。
最后 T1 暴力打假了。。。
T4 调试语句忘删了，挂了 30。。。
最后得分：[0 + 100 + 70 + 0] --> [170];
rk16。
打的真垃圾。。。
快考试了打模拟赛能不能上点心。。。
模拟赛能不能再爱我一次♪♪♪
T1：回文
直接考虑区间 dp。
设 dp 状态为: \(dp_{la,ra,lb,rb}\) 代表 \(a\) 串中 \([la,ra]\) 与 \(b\) 串中 \([lb,rb]\) 是否可以拼成回文串。
然后大力分讨出转移方程。
注意初始化 \(len\) 为 \(1\) 和 \(len\) 为 \(2\) 都要赋初值（因为回文串分奇偶）。
最后放代码
点击查看代码
#include<bits/stdc++.h>
#define Blue_Archive return 0
using namespace std;
constexpr int N = 53;int T;
int n;
int m;
int ans;bool dp[N][N][N][N];string a,b;inline int read()
{int x = 0,op = 1;char c = getchar_unlocked();while(c < '0' || c > '9'){if(c == '-') op = -1;c = getchar_unlocked();}while(c <= '9' && c >= '0') x = (x << 1) + (x << 3) + (c ^ 48),c = getchar_unlocked();return op * x;
}inline void write(int x)
{if(x < 0) x = -x,putchar_unlocked('-');if(x > 9) write(x / 10);putchar_unlocked(x % 10 + '0');
}inline void work()
{ans = 1;memset(dp,0,sizeof(dp));cin >> a >> b;n = a.length();m = b.length();a = ' ' + a;b = ' ' + b;a[0] = '$';b[0] = '%';a[n + 1] = '&';b[m + 1] = '^';for(int i = 1;i <= n + 1;i ++){for(int j = 1;j <= m + 1;j ++){dp[i][i][j][j] = (a[i] == b[j]); dp[i][i - 1][j][j - 1] = 1; dp[i][i - 1][j][j] = 1; dp[i][i][j][j - 1] = 1;if(a[i] == a[i - 1]) dp[i - 1][i][j][j - 1] = 1;if(b[j] == b[j - 1]) dp[i][i - 1][j - 1][j] = 1;}}for(int la = 1;la <= n + 1;la ++){for(int ra = la - 1;ra <= n;ra ++){for(int lb = 1;lb <= m + 1;lb ++){for(int rb = lb - 1;rb <= m;rb ++){dp[la][ra][lb][rb] |= (dp[la + 1][ra - 1][lb][rb] & (a[la] == a[ra])) | (dp[la][ra][lb + 1][rb - 1] & (b[lb] == b[rb])) | (dp[la + 1][ra][lb][rb - 1] & (a[la] == b[rb])) | (dp[la][ra - 1][lb + 1][rb] & (a[ra] == b[lb])) | (dp[la + 1][ra - 1][lb + 1][rb - 1] & (a[la] == a[ra]) & (b[lb] == b[rb]));if(dp[la][ra][lb][rb]) ans = max(ans,ra - la + rb - lb + 2);}}}}for(int la = n + 1;la >= 1;la --){for(int ra = la - 1;ra <= n;ra ++){for(int lb = m + 1;lb >= 1;lb --){for(int rb = lb - 1;rb <= m;rb ++){dp[la][ra][lb][rb] |= (dp[la + 1][ra - 1][lb][rb] & (a[la] == a[ra])) | (dp[la][ra][lb + 1][rb - 1] & (b[lb] == b[rb])) | (dp[la + 1][ra][lb][rb - 1] & (a[la] == b[rb])) | (dp[la][ra - 1][lb + 1][rb] & (a[ra] == b[lb])) | (dp[la + 1][ra - 1][lb + 1][rb - 1] & (a[la] == a[ra]) & (b[lb] == b[rb]));if(dp[la][ra][lb][rb]) ans = max(ans,ra - la + rb - lb + 2);}}}}cout << ans << '\n';
}signed main()
{freopen("string.in","r",stdin);freopen("string.out","w",stdout);// freopen("data.in","r",stdin);freopen("data.out","w",stdout);ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> T;while(T --) work();Blue_Archive;
}
T2：数排列
大简单题，直接考虑 dp 即可。
dp 状态为： \(dp_{i,j}\) 第 \(i\) 个数放在第 \(i\) 个序列中的第 \(j\) 位的方案数。
朴素转移有 \(O(n^3)\)。
前缀和优化即可做到 \(O(n^2)\)。
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define Blue_Archive return 0
using namespace std;
constexpr int N = 2e3 + 3;
constexpr int mod = 1e9 + 7;int n;
int ans;
int dp[N][N];
int sum[N][N];char a[N];signed main()
{// freopen("data.in","r",stdin);freopen("data.out","w",stdout);freopen("perm.in","r",stdin);freopen("perm.out","w",stdout);ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> n;for(int i = 1;i < n;i ++) cin >> a[i];dp[1][1] = 1;sum[1][1] = 1;for(int i = 2;i <= n;i ++){for(int j = 1;j <= i;j ++){if(a[i - 1] == '1') dp[i][j] = sum[i - 1][j - 1];else dp[i][j] = ((sum[i - 1][i - 1] - sum[i - 1][j - 1]) % mod + mod) % mod;sum[i][j] = (sum[i][j - 1] + dp[i][j]) % mod;}}cout << sum[n][n] << '\n';Blue_Archive;
}
T3：树上的背包
神秘折半搜。
考虑01背包的定义：是否选择每一个物品。
考虑是棵完全二叉树，每个点最多可以选 \(log_2n\) 个物品。
直接折半搜索，时间复杂度是 \(O(q2^\frac{log_2n}{2})\) 也就是 \(O(q \sqrt{n})\) 可以通过此题。
什么暴力比正解难打。。。
点击查看代码
#include<bits/stdc++.h>
#define con putchar_unlocked(' ')
#define ent putchar_unlocked('\n')
#define lowbit(x) (x & (-x))
#define Blue_Archive return 0
using namespace std;
constexpr int N = 1e5 + 3;
constexpr int INF = 1e9 + 3;int n;
int q;
int V;
int ans;
int top;
int tr[N];
int stk[301];struct miku
{int w,val;
}a[N];inline int read()
{int x = 0,op = 1;char c = getchar_unlocked();while(c < '0' || c > '9'){if(c == '-') op = -1;c = getchar_unlocked();}while(c <= '9' && c >= '0') x = (x << 1) + (x << 3) + (c ^ 48),c = getchar_unlocked();return op * x;
}inline void write(int x)
{if(x < 0) x = -x,putchar_unlocked('-');if(x > 9) write(x / 10);putchar_unlocked(x % 10 + '0');
}inline void update(int pos,int val){for(int i = pos;i <= V + 1;i += lowbit(i)) tr[i] = max(tr[i],val);}inline int query(int pos){int res = -INF;for(int i = pos;i;i -= lowbit(i)) res = max(res,tr[i]);return res;}inline void dfs1(int x,int up,int sum,int res)
{if(sum > V) return;if(x == up + 1){update(sum + 1,res);return;}dfs1(x + 1,up,sum,res);dfs1(x + 1,up,sum + a[stk[x]].w,res + a[stk[x]].val);
}inline void dfs2(int x,int up,int sum,int res)
{if(sum > V) return;if(x == up + 1){ans = max(ans,query(V - sum + 1) + res);return;}dfs2(x + 1,up,sum,res);dfs2(x + 1,up,sum + a[stk[x]].w,res + a[stk[x]].val);
}signed main()
{freopen("knapsack.in","r",stdin);freopen("knapsack.out","w",stdout);// freopen("data.in","r",stdin);freopen("data.out","w",stdout);n = read();for(int i = 1;i <= n;i ++){a[i].val = read();a[i].w = read();}q = read();for(int i = 1,x;i <= q;i ++){for(int j = 1;j <= V + 1;j ++) tr[j] = 0;ans = 0;x = read();V = read();top = 0;while(x) stk[++ top] = x,x /= 2;dfs1(1,top / 2,0,0);dfs2(top / 2 + 1,top,0,0);write(ans),ent;}Blue_Archive;
}
T4：树上的背包
不会，咕咕咕。