2024.4.20 笔记
SP4354 Snowflakes
记录所有的雪花,判断是否存在两个雪花是相同的。由于数据量较大,需要 \(O(n)\) 的复杂度来查询雪花,考虑哈希表
定义一个哈希值的转换方式,让不同的雪花哈希值不相同,相同的雪花的六个角一定是相同的 \(6\) 个值且相同的顺序排列,只不过起点在不同的角上。因此可以将哈希值定义为每朵雪花的六个角的长度之和 \(+\) 六个角的长度乘积。
然后还需要判断两个雪花是否相同,不能使用哈希值比较的方法,因为可能会产生哈希冲突,因此可以使用雪花的特性,两个相同的雪花,各自从某一角开始顺时针或逆时针记录长度,能得到两个相同的六元组。我们可以基于这个特性直接暴力判断。
int n;
int snow[N][6];
int h[N], ne[N], idx;
int t[6];
int get_hash(int a[])
{
int res1 = 0, res2 = 0;
for (rint i = 0; i < 6; i++)
{
res1 = (res1 + a[i]) % P;
res2 = (res2 * a[i]) % P;
}
return (res1 + res2) % P;
}
bool check(int a[], int b[])
{
for (rint i = 0; i < 6; i++)
{
for (rint j = 0; j < 6; j++)
{
bool flag = 1;
for (rint k = 0; k < 6; k++)
if (a[(i + k) % 6] != b[(j + k) % 6])
flag = 0;
if (flag) return 1;
flag = 1;
for (rint k = 0; k < 6; k++)
if (a[(i + k) % 6] != b[(j - k) % 6])
flag = 0;
if (flag) return 1;
}
}
return 0;
}
bool insert(int a[])
{
int x = get_hash(a);
for (rint i = h[x]; i; i = ne[i])
{
if (check(snow[i], a)) return 1;
}
idx++;
for (rint i = 0; i < 6; i++) snow[idx][i] = a[i];
ne[idx] = h[x];
h[x] = idx;
return 0;
}
signed main()
{
cin >> n;
while (n--)
{
for (rint i = 0; i < 6; i++)
{
cin >> t[i];
}
if (insert(t))
{
puts("Twin snowflakes found.");
return 0;
}
}
puts("No two snowflakes are alike.");
return 0;
}
AcWing 138. 兔子与兔子
本题每次要比较的是字符串中的某两个区间是否相同,可以用字符串哈希来做,只需要使该区间内哈希值一样即可
int n, m;
char s[N];
//h[i] 表示原字符串中前 i 个字符组成的字符串的哈希值
//p[i] 表示 p 的 i 次方
uint h[N], p[N];
uint calc(int l, int r)
{
return h[r] - h[l - 1] * p[r - l + 1];
}
signed main()
{
scanf("%s", s + 1);
n = strlen(s + 1);
p[0] = 1;
for (rint i = 1; i <= n; i++)
{
p[i] = p[i - 1] * P;
h[i] = h[i - 1] * P + s[i];
}
cin >> m;
while (m--)
{
int l1, r1, l2, r2;
cin >> l1 >> r1 >> l2 >> r2;
if (calc(l1, r1) == calc(l2, r2)) puts("Yes");
else puts("No");
}
return 0;
}
AcWing 139. 回文子串的最大长度
由于 zty 讲的是哈希,就不用manacher了
本题要求的是一个字符串中最大回文串的长度,我们可以枚举中间点,然后每次求出当前中间点的最大回文串,对所有情况取一个最大值即可。
但是对于中间点有两种情况,如果字符串是奇数个,那么是存在中间点的,但是如果字符串是偶数个,那么是不存在中间点的。这里我们可以用一个常用技巧来简化判断,将字符串中每两个字符之间加上一个特殊字符,假设加上一个 '#'
,
对于奇数个的字符串,a#b#c#d#f
,添加后还是奇数个。对于偶数个的字符串,a#b#c#d
,添加后变成了奇数个。通过这样的处理,我们只需要考虑奇数情况的字符串就行了,奇数个的字符串一定是存在中间点的,因此直接枚举中间点即可。
然后就要对于每个中间点求最大回文串的长度,可以求当前中间点两边需要加上的边长,然后二分求这个边长的最大值。每次二分出最大值后统计一下回文串的长度,更新最大值即可。
int n;
char s[N];
//h[] 表示正序的字符串哈希值
//rh[] 表示倒序的字符串哈希值
//p[i] 表示p的i次方
uint h[N], rh[N], p[N];
uint calc(uint h[], int l, int r)
{
return h[r] - h[l - 1] * p[r - l + 1];
}
signed main()
{
int T = 1;
while (scanf("%s", s + 1), strcmp(s + 1, "END"))
{
n = strlen(s + 1);
for (rint i = n * 2; i >= 1; i -= 2)
//在字符串的每两个字符之间插入一个相同的数
{
s[i] = s[i / 2];
s[i - 1] = 'z' + 1;
}
n *= 2; //更新字符串的长度
p[0] = 1;
for (rint i = 1, j = n; i <= n; i++, j--)
{
p[i] = p[i - 1] * P;
h[i] = h[i - 1] * P + s[i];
rh[i] = rh[i - 1] * P + s[j];
}
int res = 0;
//记录最大回文串的长度
for (rint i = 1; i <= n; i++)
//枚举中间值
{
int l = 0, r = min(i - 1, n - i);
while (l < r)
{
int mid = (l + r + 1) >> 1;
//如果两边的字符串相等说明当前边长已经是回文串,那么可以继续扩大边长
if (calc(h, i - mid, i - 1) == calc(rh, n - (i + mid) + 1, n - (i + 1) + 1)) l = mid;
else r = mid - 1;
//否则说明不是回文串,那么更大的边长也不能组成回文串,因此需要缩小边长
}
if(s[i - l] <= 'z') res = max(res, l + 1);
//如果头和尾是字符串中的字符,那么整个回文串的长度是边长+1
else res = max(res, l);
//如果头和尾是额外添加的特殊字符,那么整个回文串的长度就是边长
}
printf("Case %lld: %lld\n", T++, res);
}
return 0;
}
P3435 OKR-Periods of Words
本题是一个字符串关于循环元的证明。
这里直接得出结论:对于字符串中每一位 i
,s[i - ne[i] + 1 ~ i]
和 s[1 ~ ne[i]]
都是相等的,并且不存在更大的 ne
值满足这个条件
还能得出推论:最小循环节是 1-ne[i]
,次小循环节是 1-ne[ne[i]]
,依次能得出一个字符串所有的循环节。
void get_next(char p[], int n)
{
for (rint i = 2, j = 0; i <= n; i++)
{
while (j > 0 && p[i] != p[j + 1]) j = ne[j];
if (p[i] == p[j + 1]) j++;
ne[i] = j;
}
}
signed main()
{
scanf("%lld%s", &n, s + 1);
get_next(s, n);
for (rint i = 2, j = 2; i <= n; i++, j = i)
{
while (ne[j]) j = ne[j];
if (ne[i]) ne[i] = j;//记忆化一下,不然会 TLE 30pts
ans += i - j;
}
cout << ans << endl;
return 0;
}
P5410 【模板】扩展 KMP
学的 George1123 佬的
这里只给出代码
int ans1, ans2;
int z[M];
char a[N], b[N];
char new_s[M];
void exKMP_getZ(char s[])
{
int n = strlen(s);
for (rint i = 1, j = 0; i < n; i++)
{
int k = i - j;
if (z[j] - k > 0) z[i] = min(z[k], z[j] - k);
while (z[i] + i < n && s[z[i]] == s[z[i] + i]) z[i]++;
if (z[j] - z[i] < k) j = i;
}
}
signed main()
{
scanf("%s%s", a, b);
int la = strlen(a);
int lb = strlen(b);
for (rint i = 0; i < lb; i++) new_s[i] = b[i];
for (rint i = lb, j = 0; i < la + lb; i++, j++) new_s[i] = a[j];
exKMP_getZ(new_s);
for (rint i = 0; i < lb; i++)
{
if (!i) ans1 ^= lb + 1;
else ans1 ^= (min(z[i], lb - i) + 1) * (i + 1);
}
for (rint i = 0; i < la; i++) ans2 ^= (min(z[i + lb], lb) + 1) * (i + 1);
cout << ans1 << endl << ans2 << endl;
return 0;
}
AcWing 142. 前缀统计
本题要求的是已知若干个字符串,然后查找出有多少个字符串是给定查询的字符串的前缀。
关于前缀的统计可以用 Trie 树来做,将已知的字符串全部加入 Trie 树中,在每个字符串的结尾节点做上标记。
然后在 Trie 树上查询给定的字符串,在查询这个字符串的路上到达的所有前缀都是字符串的前缀,每走到一个节点就将标记上累计的字符串个数累加到结果上。
int n, m;
int tr[N][27], tot = 1;
int cnt[N];
char s[N];
void insert(char s[])
{
int len = strlen(s), p = 1;
for (rint k = 0; k < len; k++)
{
int ch = s[k] - 'a';
if (!tr[p][ch]) tr[p][ch] = ++tot;
p = tr[p][ch];
}
cnt[p]++;
}
int search(char s[])
{
int len = strlen(s), p = 1;
int ans = 0;
for (rint k = 0; k < len; k++)
{
p = tr[p][s[k] - 'a'];
if (!p) return ans;
ans += cnt[p];
}
return ans;
}
signed main()
{
cin >> n >> m;
for (rint i = 1; i <= n; i++)
{
scanf("%s", s);
insert(s);
}
for (rint i = 1; i <= m; i++)
{
scanf("%s", s);
cout << search(s) << endl;
}
return 0;
}
AcWing 143. 最大异或对
字典树不单单可以高效存储和查找字符串集合,还可以存储二进制数字
将每个数以二进制方式存入字典树,找的时候从最高位去找有无该位的异
void insert(int val)
{
int p = 1;
for (rint k = 30; k >= 0; k--)
{
int ch = val >> k & 1;
if (!tr[p][ch]) tr[p][ch] = ++tot;
p = tr[p][ch];
}
}
int search(int val)
{
int p = 1;
int ans = 0;
for (rint k = 30; k >= 0; k--)
{
int ch = val >> k & 1;
if (tr[p][ch ^ 1])
{ // 走相反的位
p = tr[p][ch ^ 1];
ans |= 1 << k;
}
else
{ // 只能走相同的位
p = tr[p][ch];
}
}
return ans;
}
signed main()
{
cin >> n;
for (rint i = 1; i <= n; i++)
{
cin >> a[i];
insert(a[i]);
ans = max(ans, search(a[i]));
}
cout << ans << endl;
return 0;
}
AcWing 144. 最长异或值路径
首先可以用深搜求出所有点到根节点的异或距离,由于在二进制中异或运算相当于减法,
因此对于 x->y
之间的异或路径长度即可求解
我们现在需要枚举所有点,对于每个点x都求出和它的异或路径的异或值最大的一个点 \(y\),那么从 \(x\) 能走到的最长的异或路径也可求解
要从 \(n\) 个数中选出两个数,使得这两个数的异或值最大,可以使用 Trie 树快速求解
void add(int a, int b, int c)
{
e[++idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx;
}
void dfs(int x, int father, int sum)
{
a[x] = sum;
for (rint i = h[x]; i; i = ne[i])
{
int y = e[i];
if (y == father) continue;
dfs(y, x, sum ^ w[i]);
}
}
void insert(int val)
{
int p = 1;
for (rint k = 30; k >= 0; k--)
{
int ch = val >> k & 1;
if (!tr[p][ch]) tr[p][ch] = ++tot;
p = tr[p][ch];
}
}
int search(int val)
{
int p = 1;
int ans = 0;
for (rint k = 30; k >= 0; k--)
{
int ch = val >> k & 1;
if (tr[p][ch ^ 1])
{
p = tr[p][ch ^ 1];
ans |= 1 << k;
}
else
{
p = tr[p][ch];
}
}
return ans;
}
signed main()
{
cin >> n;
for (rint i = 1; i < n; i++)
{
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
add(b, a, c);
}
dfs(0, 0, 0);
for (rint i = 1; i <= n; i++) insert(a[i]);
int res = 0;
for (rint i = 1; i <= n; i++) res = max(res, search(a[i]));
cout << res << endl;
return 0;
}
AcWing 147. 数据备份
可以发现最优解中每两个配对的办公楼一定时相邻的,因此我们可以计算一下每两个相邻的办公楼之间的距离。
d[i]
表示第 \(i\) 个办公楼和第 \(i+1\) 个办公楼之间的距离。
那么问题就变成了从 d[]
数列中选 \(k\) 个数,使它们的和最小,并且相邻的两个数不能被同时选(任一办公楼都属于唯一的配对组)
如果 k = 1
,答案就是 d[]
数列中的最小值。
如果 k = 2
,答案则一定是以下两种情况:
-
- 选择最小值
d[i]
,以及除了d[i - 1], d[i], d[i + 1]
之外的其他数中的最小值
- 选择最小值
-
- 选择最小值两侧的两个数,
d[i - 1]
和d[i + 1]
- 选择最小值两侧的两个数,
很容易证明,如果不选 d[i - 1]
和 d[i + 1]
,那么最优解一定选了 d[i]
,选了 d[i]
后不能选 d[i - 1]
和 d[i + 1]
,因此还选了这三个数以外的最小值。如果选了d[i - 1]或d[i + 1]其中一个,由于d[i]的最小值,那么这时将 d[i - 1]
或 d[i + 1]
换成 d[i]
答案会更小,因此在最优解只有以上两种情况,且 d[i]
两则的数要么都选要么都不选。
因此,我们可以先选上最小值 d[i]
,然后把 d[i - 1], d[i], d[i + 1]
从数列中删去,再在原位置加入 d[i - 1] + d[i + 1] - d[i]
,这时就变成了"从新的数列中选出不超过 \(k-1\) 个数,使它们的和最小,且相邻两个数不能同时选"这个子问题。
对于子问题,如果选了 d[i - 1] + d[i + 1] + d[i]
,相当于去掉 d[i]
,换上 d[i - 1]
和 d[i + 1]
。如果没选,那么刚才选出的 d[i]
加上这次选出的最小值就是最优解。这样恰好涵盖了最优解的两种情况。
综上所述,得出了本题的算法:
建立一个链表,连接 \(n-1\) 个节点,分别表示 d[1], d[2], ..., d[n - 1]
,即每两个办公楼之间的距离。再建立一个最小堆,
与链表构成映射关系(即堆中也有 \(n-1\) 个节点,权值分别是 d[1], d[2], ..., d[n - 1]
,同时记录对应的在链表中的下标)。
每次取出堆顶,把权值累加到答案中,设堆顶对应链表节点的下标为 p
,数值为 w[p]
,在链表中删除 p, p->prev, p->next
,
在同样的位置插入一个新节点 q
,记录数值 w[q] = w[p->prev] + w[p->next] - w[p]
。在堆中同时删除对应的 p->prev
和 p->next
的节点,
插入对应链表节点 q
,权值为 w[q]
的新节点。
重复上述操作 \(K\) 次,就得到了最终答案。
int n, k;
int d[N];
int l[N], r[N];
//链表
int idx;
bool st[N];
//记录某个节点是否被删去
priority_queue<pii, vector<pii>, greater<pii> > h;
void remove(int x)
{ //删除链表中某个元素
st[x] = 1;
//记录当前节点在堆中也被删除
r[l[x]] = r[x];
l[r[x]] = l[x];
}
signed main()
{
cin >> n >> k;
for (rint i = 0; i < n; i++) cin >> d[i];
for (rint i = n - 1; i > 0; i--) d[i] -= d[i - 1];
d[0] = d[n] = inf; //设置两个边界哨兵
for (rint i = 1; i < n; i++)
{
l[i] = i - 1;
r[i] = i + 1;
h.push({d[i], i});
//加入堆中
}
int res = 0; //记录最小总和
for (rint i = 0; i < k; i++)
{
while (st[h.top().second]) h.pop();
//将所有应该删去的节点删去
pii t = h.top();
//取出堆顶
h.pop();
int v = t.first;
int p = t.second, left = l[p], right = r[p];
remove(left), remove(right); //删去两边的节点
res += v; //累加值
d[p] = d[left] + d[right] - d[p]; //修改值
h.push({d[p], p}); //将修改后的节点放回堆中
}
cout << res << endl;
return 0;
}
AcWing 241. 楼兰图腾
从左向右依次遍历每个数 \(a[i]\),使用树状数组统计在 \(i\) 位置之前所有比 \(a[i]\) 大的数的个数、以及比 \(a[i]\) 小的数的个数。统计完成后,将 \(a[i]\) 加入到树状数组。
从右向左依次遍历每个数 \(a[i]\),使用树状数组统计在 \(i\) 位置之后所有比 \(a[i]\) 大的数的个数、以及比 \(a[i]\) 小的数的个数。统计完成后,将 \(a[i]\) 加入到树状数组。
int n, a[N];
int l[N], r[N];
int c[N];
int A, V;
int lowbit(int x) {return x & -x;}
void add(int x, int k)
{
for (rint i = x; i <= n; i += lowbit(i)) c[i] += k;
}
int ask(int x)
{
int ans = 0;
for (rint i = x; i; i -= lowbit(i)) ans += c[i];
return ans;
}
signed main()
{
cin >> n;
for (rint i = 1; i <= n; i++) cin >> a[i];
for (rint i = 1; i <= n; i++)
{
//因为从左往右遍历并插值,所以在调用 ask 函数时 c 中存的都是第 i 个节点左边的值
int y = a[i]; //当前节点的高度
l[i] = ask(y - 1); //找到当前节点左边的比高度比 y 小的数的个数
r[i] = ask(n) - ask(y);//找到当前节点左边的比高度比 y 大的数的个数
add(y, 1);//把 y 插入到 c 数组中, 相当于建树
}
memset(c, 0, sizeof c);
//准备从右往左读,再建一遍树
for (rint i = n; i >= 1; i--)
{
int y = a[i];
l[i] *= ask(y - 1);
A += l[i];
//以 y 为最高点的总方案数为 (y 左边比 y 低的点数) * (y 右边比 y 低的点数)
r[i] *= ask(n) - ask(y);
V += r[i];
//以 y 为最低点的总方案数为 (y 左边比 y 高的点数) * (y 右边比 y 高的点数)
add(y, 1);
}
cout << V << " " << A << endl;
return 0;
}
P3605 Promotion Counting
求某节点子树内比该节点的点权大的点的个数
int n, p[N], b[N], ans[N];
vector<int> e[N];
int c[N];
int lowbit(int x){ return x & -x;}
void add(int x, int y)
{
for (; x <= n; x += lowbit(x)) c[x] += y;
}
int query(int x)
{
int ans = 0;
for (; x; x -= lowbit(x)) ans += c[x];
return ans;
}
void dfs(int x)
{
ans[x] = query(p[x]) - query(n);
for (auto y : e[x]) dfs(y);
ans[x] += (query(n) - query(p[x]));
add(p[x], 1);
}
signed main()
{
cin >> n;
for (rint i = 1; i <= n; i++)
{
cin >> p[i];
b[i] = p[i];
}
sort(b + 1, b + n + 1);
for (rint i = 1; i <= n; i++)
{
p[i] = lower_bound(b + 1, b + n + 1, p[i]) - b;
}
for (rint i = 2; i <= n; i++)
{
int x;
cin >> x;
e[x].push_back(i);
}
dfs(1);
for (rint i = 1; i <= n; i++) cout << ans[i] << endl;
return 0;
}
P4054 [JSOI2009] 计数问题
定义第一个维度为 \(x\),第二个维度为 \(y\),第三个维度为权值 \(c\)。
定义两个函数 \(add(x,y,c,d)\) 和 \(sum(x,y,c)\)。
- \(add(x,y,c,d)\):将左上角点坐标为 \((1,1)\),右下角点坐标为 \((x,y)\) 的矩形中中权值 \(c\) 的格子的个数增加 \(d\)
- \(sum(x,y,c)\) 统计左上角点坐标为 \((1,1)\),右下角点坐标为 \((x,y)\) 的矩形中权值为 \(c\) 的格子的个数。
因此当进行操作 1 时,将原先的权值出现次数 \(-1\),将修改后的权值的出现次数 \(+1\);
当进行操作 2 时,根据容斥原理,易得答案为 \(sum(x2, y2, c) - sum(x2, y1 - 1, c) - sum(x1 - 1, y2, c) + sum(x1 - 1, y1 - 1, c)\)。
int lowbit(int x) {return x & (-x);}
void add(int x, int y, int k, int color)
{
for (rint i = x; i <= n; i += lowbit(i))
for (rint j = y; j <= m; j += lowbit(j))
c[i][j][color] += k;
}
int query(int x, int y, int color)
{
int ans = 0;
for (rint i = x; i; i -= lowbit(i))
for (rint j = y; j; j -= lowbit(j))
ans += c[i][j][color];
return ans;
}
signed main()
{
cin >> n >> m;
for (rint i = 1; i <= n; i++)
{
for (rint j = 1; j <= m; j++)
{
cin >> color;
a[i][j] = color;
add(i, j, 1, color);
}
}
int T;
cin >> T;
while (T--)
{
int op;
cin >> op;
int x1, y1, x2, y2;
if (op == 1)
{
cin >> x1 >> y1 >> color;
add(x1, y1, -1, a[x1][y1]);
a[x1][y1] = color;
add(x1, y1, 1, color);
}
else
{
cin >> x1 >> x2 >> y1 >> y2 >> color;
cout << query(x2, y2, color) - query(x1 - 1, y2, color) - query(x2, y1 - 1, color) + query(x1 - 1, y1 - 1, color) << endl;
}
}
return 0;
}
标签:ch,2024.4,int,rint,笔记,return,++,字符串,20
From: https://www.cnblogs.com/spaceswalker/p/18148065