T1 挑战
题意：有两行字符串，有 \(*\) 和 \(.\) 两种字符，你可以进行一种操作，将一个格子的 \(*\) 推到相邻的格子，如果推到一个有 \(*\) 的格子，那么将 \(*\) 合并，求最后把所有 \(*\) 合并成一个点的最小步数
考场上我竟然在想O(1)解法...
正解：直接 \(\text{DP}\)
设 \(f[i][0/1]\) 表示合并完前 \(i\) 列的 \(*\) ，当前再第 \(0/1\) 行，的最小步数
处理一下左右端点 \(l, r\) 然后转移即可，转移的时候大力分类讨论
代码
#include<bits/stdc++.h>
#define ll long long
#define re register
#define ull unsigned long long
using namespace std;
inline int read()
{
int x = 0, f = 0; char c = getchar();
while(c < '0') f |= (c == '-'), c = getchar();
while(c >= '0') x = (x << 1) + (x << 3) + (c & 15), c = getchar();
return f ? -x : x;
}
const int N = 2e5 + 10;
int T, n;
char s[2][N];
int f[N][2];
int main()
{
T = read();
while(T--)
{
n = read();
scanf("%s", s[0] + 1);
scanf("%s", s[1] + 1);
int l = n + 1, r = 0;
for(re int i = 1; i <= n; ++i)
{
if(s[0][i] == '*' || s[1][i] == '*')
{
l = i;
break;
}
}
for(re int i = n; i >= 1; --i)
{
if(s[0][i] == '*' || s[1][i] == '*')
{
r = i;
break;
}
}
if(l == n + 1)
{
printf("0\n");
continue;
}
for(re int i = l; i <= r; ++i) f[i][0] = f[i][1] = 0x7fffffff;
if(s[0][l] == '*' && s[1][l] == '.') f[l][0] = 0, f[l][1] = 1;
if(s[0][l] == '*' && s[1][l] == '*') f[l][0] = f[l][1] = 1;
if(s[0][l] == '.' && s[1][l] == '*') f[l][0] = 1, f[l][1] = 0;
for(re int i = l + 1; i <= r; ++i)
{
if(s[0][i] == '.' && s[1][i] == '.') f[i][0] = min(f[i - 1][0] + 1, f[i - 1][1] + 2), f[i][1] = min(f[i - 1][0] + 2, f[i - 1][1] + 1);
if(s[0][i] == '*' && s[1][i] == '.') f[i][0] = min(f[i - 1][0] + 1, f[i - 1][1] + 2), f[i][1] = min(f[i - 1][0] + 2, f[i - 1][1] + 2);
if(s[0][i] == '*' && s[1][i] == '*') f[i][0] = min(f[i - 1][0] + 2, f[i - 1][1] + 2), f[i][1] = min(f[i - 1][0] + 2, f[i - 1][1] + 2);
if(s[0][i] == '.' && s[1][i] == '*') f[i][0] = min(f[i - 1][0] + 2, f[i - 1][1] + 2), f[i][1] = min(f[i - 1][0] + 2, f[i - 1][1] + 1);
}
printf("%d\n", min(f[r][0], f[r][1]));
}
return 0;
}
T2 天☆堂
题意：找一个字符串的子串的最长上升子序列
子串的顺序的定义：若A串在B串前面，那么
\[(l_A < l_B) \lor (l_A = l_B \land r_A < r_B) \]子串上升的定义：按照字典序顺序
考场上打了一个 \(O(n^3 \times \log_2n)\) 的暴力，枚举子串 \(O(n^2)\) ，求上升子序列 \(O(\log_2n)\) ，判断两个子串大小 \(O(n)\)
后来chino告诉我可以先 \(Hash\) 一下，再二分找两个子串第一个不同的位置，也就是比大小了
后来又看到题解里的 \(O(n^2)\) 预处理， \(O(1)\) 比大小
照这样，我考场上的代码可以优化到 \(O(n^2 \times \log_2n)\) ，不过我懒，就不再尝试实现了，再说这题有更优的解法
介绍一下chino的做法，复杂度是 \(O(26 \times n^2)\)
其实 \(26\) 的上界实际上远远达不到，和正解 \(O(n^2)\) 几乎不相上下
建一颗 \(\text{trie}\) 树，然后按顺序插入串，每个节点记录这颗子树里的最大值（最长上升子序列的长度）设为 \(maxx\)
然后插入的时候更新新插入的串，怎么更新呢，就是自己到根节点这条链上，每一个节点的儿子字符小于自己字符的 \(maxx\) 的最大值再加 \(1\)
这个要递归实现，因为 \(maxx\) 是这个节点的子树的最大值，最后 \(maxx[root]\) 就是答案
chino的代码
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define ll long long
#define re register
#define ull unsigned long long
using namespace std;
inline int read()
{
int x = 0, f = 0; char c = getchar();
while(c < '0') f |= (c == '-'), c = getchar();
while(c >= '0') x = (x << 1) + (x << 3) + (c & 15), c = getchar();
return f ? -x : x;
}
const int N = 5e3 + 10;
int T, n;
char s[N];
int cnt, tot; // 边数，点数
int head[N * N], maxx[N * N];
char c[N * N];
struct Edge{ int v, next ; } xing[N * N];
void add(int u, int v)
{
++cnt;
xing[cnt].v = v;
xing[cnt].next = head[u];
head[u] = cnt;
}
// 当前节点是k，下一次要匹配的字符是s[pos]，前面的最大值是ans
void insert(int k, int pos, int ans)
{
maxx[k] = max(maxx[k], ans + 1);
++ans;
if(pos == n + 1) return ;
int v = 0;
for(re int i = head[k]; i; i = xing[i].next )
{
if(c[xing[i].v ] < s[pos]) ans = max(ans, maxx[xing[i].v ]);
else if(c[xing[i].v ] == s[pos]) v = xing[i].v ;
}
if(v == 0)
{
v = ++tot;
head[v] = 0;
maxx[v] = 0;
c[v] = s[pos];
add(k, v);
}
insert(v, pos + 1, ans);
maxx[k] = max(maxx[k], maxx[v]);
}
void work()
{
n = read();
scanf("%s", s + 1);
cnt = 0, tot = 1;
head[1] = 0;
maxx[1] = 0;
for(re int i = 1; i <= n; ++i) insert(1, i, -1);
printf("%d\n", maxx[1]);
}
int main()
{
T = read();
while(T--) work();
return 0;
}
正解： \(O(n^2)\) 预处理出任意两个子串的 \(LCP\) （最长公共前缀）的长度，这样就可以 \(O(1)\) 比较两个串的大小了，比较 \(\text{nb}\)
\[g[i][j] = g[i + 1][j + 1] + 1 \]然后还有一个贪心结论:如果把最终答案中的子串 \([l, r]\) 在原串中表示，那么每个 \(l\) 对应的 \(r\) 在答案中一定是连续的
若 \(A\) 串字典序小于 \(B\) 串，要么 \(A\) 是 \(B\) 的前缀，要么 \(A\) 和 \(B\) 的 \(LCP\) 后的第一个字符 \(A\) 的更小
我们直接比较两个串 \([l_1, n]\) 和 \([l_2, n]\) 的大小（ \(l_1 < l_2\) ），如果 \([l_1, n]\) 的字典序小于 \([l_2, n]\) ，就会有二者的 \(LCP[l_1, l_1 + d + 1]\) ，此时有且仅有 \([l_1, l_1 + d \sim n]\) 的所有串字典序都比 \([l_2, l_2 + d \sim n]\) 小，最优方案一定是贪心的选取 \([l_1, l_1 + d - 1]\) 作为左端点 \(l_2\) 的第一个串
\[f[i] = \max_{1 \le j \le i} \{ n - i + 1, f_j + n - i + 1 - g[i][j] \} \]于是就可以 \(O(n^2)\) 转移了
代码
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define ll long long
#define re register
#define ull unsigned long long
using namespace std;
inline int read()
{
int x = 0, f = 0; char c = getchar();
while(c < '0') f |= (c == '-'), c = getchar();
while(c >= '0') x = (x << 1) + (x << 3) + (c & 15), c = getchar();
return f ? -x : x;
}
const int N = 5e3 + 10;
int T, n;
char s[N];
int g[N][N], f[N];
int main()
{
T = read();
while(T--)
{
n = read();
scanf("%s", s + 1);
for(re int i = 1; i <= n + 1; ++i)
{
f[i] = 0;
for(re int j = 1; j <= n + 1; ++j)
{
g[i][j] = 0;
}
}
for(re int i = n - 1; i >= 1; --i)
{
for(re int j = n; j > i; --j)
{
if(s[i] == s[j])
{
g[i][j] = g[i + 1][j + 1] + 1;
}
else
{
g[i][j] = 0;
}
}
}
int ans = n;
for(re int i = 1; i <= n; ++i)
{
f[i] = n - i + 1;
for(re int j = 1; j < i; ++j)
{
if(i + g[j][i] <= n && s[i + g[j][i]] > s[j + g[j][i]])
{
f[i] = max(f[i], f[j] + n - i + 1 - g[j][i]);
}
}
ans = max(ans, f[i]);
}
printf("%d\n", ans);
}
return 0;
}
T3 药丸
题意：起点为 \(0\) ，每次可以向 \(+1，-1，0\) 方向走一步，不允许出现负数，求最后在 \([l, r]\) 区间的方案数
从 \(n\) 步里面任选 \(i\) 步走 \(+1，-1\) ，剩下的步数走 \(0\)， 那么答案就是
\[\sum_{i = 0}^{n} \binom{n}{i} \Bigg( {\sum_{j = l, 2 \mid (i + j)}^{r} \binom{i}{\frac {i + j} {2}} - \binom{i}{\frac {i + j + 2} {2}}} \Bigg) \]右边的求和式，相邻的两个 \(j\) 相差 \(2\) ，两个组合数的下方也相差 \(2\) ，展开后发现邻项刚好消掉
令 \(j_l = \lceil{\frac {i + l}{2}}\rceil, j_r = \lfloor{\frac {i + r}{2}}\rfloor\)
那么最后的答案就是
\[\sum_{i = 0}^{n} \binom{n}{i} \bigg({\binom{i}{j_l} - \binom{i}{j_r + 1}}\bigg) \]就可以预处理组合数然后 \(O(n)\) 求解了
但是模数不是素数！！！
我们可以把模数分解: $p = p_{1}^{w_1} p_{2}^{w_2} ... p_{k}^{w_k} $
然后把每个数字表示成 $x \cdot p_{1}^{w_1} p_{2}^{w_2} ... p_{k}^{w_k} $ 的形式
其中 \(x\) 与 \(p\) 互质，再预处理阶乘计算组合数，就可以了
因为我用了快速幂，所以复杂度是 \(O(n \log^2 p)\) 好像可以预处理做到 \(O(n \log p)\)
代码
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define ll long long
#define re register
#define ull unsigned long long
using namespace std;
inline int read()
{
int x = 0, f = 0; char c = getchar();
while(c < '0') f |= (c == '-'), c = getchar();
while(c >= '0') x = (x << 1) + (x << 3) + (c & 15), c = getchar();
return f ? -x : x;
}
const int N = 1e5 + 10;
int n, l, r;
ll mod;
ll prime[40], cnt;
// 快速幂
ll qpow(ll a, ll b, ll mod)
{
ll ans = 1;
while(b)
{
if(b & 1) ans = ans * a % mod;
b >>= 1;
a = a * a % mod;
}
return ans;
}
// 扩展欧拉定理求逆元
ll exgcd(ll a, ll b, ll &x, ll &y)
{
if(b == 0)
{
x = 1, y = 0;
return a;
}
ll ret = exgcd(b, a % b, y, x);
y -= a / b * x;
return ret;
}
// 扩展欧拉定理求逆元
ll getinv(ll a)
{
ll x, y;
exgcd(a, mod, x, y);
x = (x % mod + mod) % mod;
return x;
}
// 存一个数素数拆分形式
struct node
{
ll tot[35], x;
node(){ memset(tot, 0, sizeof(tot)); x = 1; }
// 初始化，把mod拆开
void into(ll mod)
{
ll now = mod;
for(re int i = 2; i * i <= mod; ++i)
{
if(now % i == 0)
{
prime[++cnt] = i;
while(now % i == 0) ++tot[cnt], now /= i;
}
}
if(now != 1) prime[++cnt] = now, tot[cnt] = 1;
}
// 将一个数变成素数拆分形式
void to(ll a)
{
ll now = a;
for(re int i = 1; i <= cnt; ++i)
{
if(now % prime[i] == 0)
{
while(now % prime[i] == 0) ++tot[i], now /= prime[i];
}
}
x = now % mod;
}
// 两个数相乘（素数拆分形式）
node friend operator * (const node &a, const node &b)
{
node c;
c.x = a.x * b.x % mod;
for(re int i = 1; i <= cnt; ++i) c.tot[i] = a.tot[i] + b.tot[i];
return c;
}
// 两个数相除（素数拆分形式）
node friend operator / (const node &a, const node &b)
{
node c;
c.x = a.x * getinv(b.x ) % mod;
for(re int i = 1; i <= cnt; ++i) c.tot[i] = a.tot[i] - b.tot[i];
return c;
}
// 讲一个数变回整型
ll back()
{
ll ans = x;
for(re int i = 1; i <= cnt; ++i) ans = ans * qpow(prime[i], tot[i], mod) % mod;
return ans;
}
}jc[N], M;
ll C(int n, int m)
{
if(n < m || n < 0 || m < 0) return 0;
node now = jc[n] / jc[m] / jc[n - m];
return now.back();
}
int main()
{
n = read(), mod = read(), l = read(), r = read();
M.into(mod);
for(re int i = 2; i <= n; ++i) jc[i].to(i);
for(re int i = 2; i <= n; ++i) jc[i] = jc[i - 1] * jc[i];
ll ans = 0;
for(re int i = 0; i <= n; ++i)
{
int jl = ceil((double)(i + l) / 2.0);
int jr = (i + r) / 2 + 1;
ans = (ans + C(n, i) * ((C(i, jl) - C(i, jr) + mod) % mod) % mod) % mod;
}
printf("%lld\n", ans);
return 0;
}