看到说不按题目难度排序, 先读下题
初看
\(\rm{T1}\) 没什么思路
\(\rm{T2}\) 感觉像是 \(\rm{dp}\) , 可能能多骗点?
\(\rm{T3}\) 又是计数
\(\rm{T4}\) 没思路
感觉要寄, \(\rm{lhs}\) 多半又要 \(\rm{AK}\)
\(\rm{T2}\)
观察到这个类型的题比较熟, 先开 \(\rm{T2}\)
简化题意
给定一长为 \(n\) 的字符串 \(S\) , 由前 \(m\) 个小写字母构成, 现在要求将这个字符串变换成一个由至少连续 \(k\) 个相同字符构成的字符串组成的字符串( 下称为 合法字符串 ), 其中, 字符 \(a \to b\) 的花费为 \(W_{a, b}\)
显然的, \(W_{a, b}\) 的计算可以用 \(\rm{Floyd}\) 进行 \(O(m^3)\) 的计算
考虑状态转移方程的设计
令 \(dp_{i, p}\) 表示字符串到 \(i\) 结尾时, 当前的结尾字符为 \(p\) , 令其为合法字符串的最小花费
则有
- 跟上之前的染色, 不需要考虑长度
- 自己单独拉出来进行染色, 长度至少为 \(k\)
时间复杂度 \(O(n m^2)\) , 需要预处理 \(\rm{Cost}\) , 前缀和做一下就可以了, 转移 \(O(1)\), 预处理 \(O(nm)\)
现在问题转化成了如何高效的找
\[\min\left[ dp_{j, q} + \rm{Cost} ( { S_{j + 1 \sim i} \to p } ) \right] \text{ }, \text{ } j \leq i - k \]观察到 \(Cost\) 的可拆性
维护 \(g_{x, p} = \min_{i = 1}^{x} (dp_{i, p} + \rm{Cost}(S_{i + 1 \sim x} \to p))\)
那么转移就显然了, 每次计算的仅仅是 \(g_{i - k, p} + \rm{Cost}(S_{i - k + 1, i} \to p)\)
对于 \(g\) 的转移, 有
\[g_{i, p} = \min (g_{i - 1, p} + \rm{Cost}(S_{i, i} \to p), dp_{i, p}) \]最外层显然需要先枚举 \(p\) , 里面枚举 \(i, q\)
这个时候已经过去 \(50 \rm{min}\) 了, 完蛋, 希望别假
先不打代码去看看 \(\rm{T1}\) , 防止一会脑子糊了做不出, 代码什么的艹过去就行了
确实多练 \(\rm{dp}\) 是好的
\(\rm{T1}\)
观察到康凌睿说这题是个 \(\rm{dp}\) , 往这个方向想
\(\rm{lhs}\) 说他没思路? 多半又要 \(\rm{AK}\)
往好的方向想, 至少对于 \(30\%\) 的数据, 我们可以状态压缩艹过去, 对于 \(60\%\) 的数据, 我们可以剪枝艹过去, 剩下 \(40 \rm{pts}\) 大不了不要了
我是删除线仙人
\(1 \rm{h} 20 \rm{min}\) 之后就放掉这道题去做后面的了, 有时间再看
\(\rm{T3}\)
简化题意,
每次让 \(i\) 位置的人位移到 \(A_i\) , 求能够使 \(k\) 次口令后回到原位的 \(A\) 排列
这个题好像之前的一道题
手玩样例找下性质, 然而并没有
直接观察大样例, 包没有性质的啊
再次跳题, 多半也没时间回来想了
\(\rm{T4}\)
从好的角度来想, 这个题至少题意清楚
显然的, 我们可以 \(O(n^2)\) 的计算出两两飞船之间唯一一次可以跳跃的机会时间, 这是简单的
对于 \(n^2\) 个时刻 (必须是排好序的), 每一次都可以更新最优解
这个复杂度大概是 \(O(n^2 \log n)\) 的, 可能可以通过 \(50\%\) 的数据
代码
现在还有 \(1 \rm{h} 45 \rm{min}\) , 最高可以拿到 \(60 + 100 + 0 + 50 = 210 \rm{pts}\), 但是最低只有 \(30 + 0 + 0 + 0 = 30 \rm{pts}\) 就看算法正确性和接下来的安排了
\(\rm{T1}\)
先打最为暴力和保险的 \(\rm{T1}\)
#include <bits/stdc++.h>
#include <bits/stdc++.h>
const int MAXN = 1020;
#define InMap(a, b) a >= 1 && a <= n && b >= 1 && b <= n
int n;
int W[MAXN][MAXN];
class Subtask_AB_Class
{
private:
int Now[MAXN][MAXN]; //0 A; 1 B
int Ans = 0;
/*检查以 (x, y) 为右下角的 2 * 2 正方形的合法性*/
bool Check(int x, int y)
{
if (InMap(x - 1, y - 1)) {
int CntA = 0, CntB = 0;
for (int i = x - 1; i <= x; i++)
for (int j = y - 1; j <= y; j++)
CntA += int(Now[i][j] == 0), CntB += int(Now[i][j] == 1);
if (CntA == CntB) return true;
else return false;
}else {
return true;
}
return true;
}
int CalcAns()
{
int NowAns = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (Now[i][j] == 0) NowAns += W[i][j];
return NowAns;
}
void dfs(int x, int y)
{
if (x == n && y == n) {
if(Check(n, n))
Ans = std::max(Ans, CalcAns());
return;
}
if (!Check(x, y)) return;
if (y != n) {
Now[x][y + 1] = 0;
dfs(x, y + 1);
Now[x][y + 1] = 1;
dfs(x, y + 1);
}else {
Now[x + 1][1] = 0;
dfs(x + 1, 1);
Now[x + 1][1] = 1;
dfs(x + 1, 1);
}
}
public:
void solve()
{
dfs(1, 0);
printf("%d", Ans);
}
} Subtask_AB;
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
scanf("%d", &W[i][j]);
Subtask_AB.solve();
return 0;
}
花了 \(25 \rm{min}\) 打, 一遍过并且惊人的快
\(\rm{T2}\)
这个题是正解, 但是实现稍微复杂, 尽可能快但是要保证正确
大不了放弃 \(\rm{T4}\)
神经, 写一半发现复杂度算错了, 极限优化
现在还剩下 \(40 \rm{min}\) 左右, 看看能不能拼出来这 \(100 \rm{pts}\)
大结局
最后死磕 \(\rm{T2}\) 转移和优化应该是对的, 没打出来, 遗憾趋势
预计 : $ 60 + 0 + 0 + 0 = 60 \rm{pts}$
实际 :
标签：min,text,11.15,Cost,模拟,字符串,rm,CW,dp From： https://www.cnblogs.com/YzaCsp/p/18547637