2022牛客多校9

A Car Show(赛时已过)

签到题
直接双指针模拟即可，使用权值数组来记录不同种类的数量，然后维护种类数即可
赛时题意理解错了，原来是m种都要，怒wa一发

B Two Frogs(赛时已过)

赛时罕见的过了dp
800大小$n^2$过
如果直接维护的话是$n^3$，所以使用差分数组优化一个n
同时进行滚动数组优化节省空间

E Longest Increasing Subsequence(赛时已过)

自己写的其实还是比题解麻烦的，但本质上都是二进制拆分
查分所需要的基本个数为60，所以对每一位的分配最多为1，优化一下即可
其实之前区域赛写过原题，赛时居然还码这么久

G Magic Spells

emmmm,其实思路很好想，就是马拉车+hash+map
但头一次遇到卡单hash的，学了下标程的双hash就过了

using pull = pair<ull, ull>;
const int P = 131;
ull h[N], h2[N], p[N], p2[N];
map<pull, int>mp;
namespace MLC
{
const int N = 3e5 + 5;
int cnt, len;
char s[N], ss[N * 2];//s从1开始
int r[N * 2];
pull get(int l, int r)
{
l /= 2, r /= 2;
ull hash1 = (h[r] - h[l - 1] * p[r - l + 1] % mod + mod) % mod;
ull hash2 = (h2[r] - h2[l - 1] * p2[r - l + 1] % mod2 + mod2) % mod2;
return { hash1,hash2 };
}
void init(int n = 0)//将每两个字符中插入一个字符
{
if (n)len = n;
else len = strlen(s + 1);
cnt = 1;
ss[0] = '!'; ss[cnt] = '#';
rep(i, 1, len)ss[++cnt] = s[i], ss[++cnt] = '#';
ss[cnt + 1] = '$';
h[0] = h2[0] = 0;
for (int i = 1; i <= len; i++)
{
h[i] = (h[i - 1] * P % mod + s[i]) % mod;
h2[i] = (h2[i - 1] * P % mod2 + s[i]) % mod2;
}
}
set<pull>sss;
void manacher()
{
int pos = 0, mx = 0;
static int num = 0;
num++;
sss.clear();
rep(i, 2, cnt)
{
if (i < mx) r[i] = min(r[pos * 2 - i], mx - i);
else
{
r[i] = 1;
if (ss[i] != '#')sss.insert(get(i, i));
}
while (ss[i + r[i]] == ss[i - r[i]])
{
if (ss[i + r[i]] != '#')sss.insert(get(i - r[i], i + r[i]));
r[i]++;
}
if (mx < i + r[i])mx = i + r[i], pos = i;
}
for (auto x : sss)
{
if (num > 1 && mp.find(x) == mp.end())continue;
if (mp[x] != num - 1)mp.erase(x);
else mp[x]++;
}
}
}
int n;
void solve()
{
p[0] = p2[0] = 1;
for (int i = 1; i <= 300'000; i++)
{
p[i] = p[i - 1] * P % mod;
p2[i] = p2[i - 1] * P % mod2;
}
cin >> n;
rep(i, 1, n)
{
cin >> MLC::s + 1;
MLC::init();
MLC::manacher();
}
ll ans = 0;
for (auto x : mp)if (x.se == n)ans++;
cout << ans << endl;
}

先写到这，后面还有两题还没怎么懂，之后再补

最后

以上就是跳跃香水为你收集整理的2022牛客多校9的全部内容，希望文章能够帮你解决2022牛客多校9所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。