|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
总结与反思
C - 如果一个数可以确定整个状态, 考虑设未知数然后给所有的数减掉偏移量 E - 要删除一个东西, 我们更常见的做法是伪删除 F - DP 首先考虑阶段, 即以什么样的顺序完成这个任务, 状态要符合转移 G - 发现一个非常长, 或者有循环的东西要想到倍增, 知 1 就知道所有 H - 字符串的公共前后缀/回文 之类的都有相等的关系, 这类结构相似的问题可以由小的给大的问题提供上下界或者答案
E - POI2008 Trains
关键在于如何更新每个种类的值, 可以用动态开点或者平衡树
这里用并查集的写法, 因为时间的先后, 为了强制让后来的字符串没法用以前的答案更新, 可以把后来的点当作根
伪删除很重要的思想#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
const int N = 1005;
const int M = 1e5 + 5;
const int P = 131;
struct Node {
int pa, val;
Node(int a = 0, int b = 0) {
pa = a;
val = b;
}
};
// 最多有 N + M 个 hash 值, dsu 给每个 hash 值存点
vector<Node> dsu[N + M];
// pos 给哈希值的编号, 对应 dsu 的位置, siz 是对应 vec 的实际大小
// 值只和当前的大小有关, 可以只改变 siz 实现伪删除
unordered_map<ll, int> pos;
int cnt, l[N], siz[N + M];
int ans[N], n, m, q;
// hash 用
ll H[N], p[N];
char s[N][105];
// h 是哈希的哈希
int Findpa(int u, int h) {
if (dsu[h][u].pa == u)
return dsu[h][u].val;
dsu[h][u].val = max(dsu[h][u].val, Findpa(dsu[h][u].pa, h));
dsu[h][u].pa = dsu[h][dsu[h][u].pa].pa;
return dsu[h][u].val;
}
// u 字符串编号, h 新的哈希值
// l[u] 相当于 u 在 vec 中的位置
void Insert(int u) {
int& id = pos[H[u]];
if (!id)
id = ++cnt;
siz[id]++;
l[u] = dsu[id].size();
// 如果有就把原来的树并到 u 上
if (l[u])
dsu[id][l[u] - 1].pa = l[u];
dsu[id].emplace_back(l[u], siz[id]);
}
void Del(int u) {
siz[pos[H[u]]]--;
ans[u] = max(ans[u], Findpa(l[u], pos[H[u]]));
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m >> q;
p[0] = 1;
for (int i = 1; i <= m; i++) {
p[i] = p[i - 1] * P;
}
for (int i = 1; i <= n; i++) {
cin >> (s[i] + 1);
for (int j = 1; j <= m; j++) {
H[i] = H[i] * P + s[i][j];
}
Insert(i);
ans[i] = 1;
}
while (q--) {
int x, xp, y, yp;
cin >> x >> xp >> y >> yp;
Del(x);
if (x != y)
Del(y);
H[x] += (s[y][yp] - s[x][xp]) * p[m - xp];
H[y] += (s[x][xp] - s[y][yp]) * p[m - yp];
swap(s[x][xp], s[y][yp]);
Insert(x);
if (x != y)
Insert(y);
}
for (int i = 1; i <= n; i++) {
cout << max(ans[i], Findpa(l[i], pos[H[i]])) << '\n';
}
return 0;
}
F - P2593 [ZJOI2006] 超级麻将
想 DP 不要盲目看整个问题, 想想以什么样子的顺序完成, 把四周的状态放进状态里可以参考 P2157 [SDOI2009] 学校食堂#include <bits/stdc++.h>
using namespace std;
const int N = 102;
const int M = 100;
bool f[N][N][N][2];
int n, cnt[N];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
while(n--){
memset(f, 0, sizeof(f));
f[0][0][0][0] = 1;
for(int i = 1; i <= M; i++){
cin >> cnt[i];
for(int j = 0; j <= cnt[i - 1]; j++){
for(int k = 0; k <= cnt[i]; k++){
// 阶段: 前 i 个已经拿完了, 现在考虑 i
// 对于现有的状态我们可以选择不同拿法
// 出对子
if(k > 1){
f[i][j][k][1] |= f[i][j][k - 2][0];
}
// 出刻子
if(k > 2){
f[i][j][k][0] |= f[i][j][k - 3][0];
f[i][j][k][1] |= f[i][j][k - 3][1];
}
if(k > 3){
f[i][j][k][0] |= f[i][j][k - 4][0];
f[i][j][k][1] |= f[i][j][k - 4][1];
}
// 出 k 个顺子
if(i == 1 && k == 0){
f[i][j][k][0] = 1;
f[i][j][k][1] = 1;
continue;
}
if(k <= j && k <= cnt[i - 2]){
f[i][j][k][0] |= f[i - 1][cnt[i - 2] - k][j - k][0];
f[i][j][k][1] |= f[i - 1][cnt[i - 2] - k][j - k][1];
}
}
}
}
if(f[M][cnt[M - 1]][cnt[M]][1]) cout << "Yes\n";
else cout << "No\n";
}
return 0;
}
G - BZOJ2062 素颜2
基环树森林上一个点一定跳到最后是在环上, 如何比较生成的字符串? 字符串很长, 倍增就行#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
const int N = 1e5 + 5;
const int P = 131;
int n;
ll h[N][18], p[18];
int t[N][18];
int ans[N];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
p[0] = P;
for (int i = 1; i <= 17; i++) {
p[i] = p[i - 1] * p[i - 1];
}
for (int i = 1; i <= n; i++) {
char ch;
cin >> ch;
h[i][0] = ch;
}
for (int i = 1; i <= n; i++) {
cin >> t[i][0];
}
// 研究非常长的东西的时候可以想想倍增口牙
// 知道 1 也就知道所有
// 比如从一个点一直往后跳 / 超级长的序列之类的
for (int j = 1; j < 18; j++) {
for (int i = 1; i <= n; i++) {
t[i][j] = t[t[i][j - 1]][j - 1];
h[i][j] = h[i][j - 1] * p[j - 1] + h[t[i][j - 1]][j - 1];
}
}
for (int i = 1; i <= n; i++) ans[i] = i;
sort(ans + 1, ans + n + 1, [](int x, int y) {
// 如果 两个相同, 就返回编号小的
if (h[x][17] == h[y][17])
return x < y;
for (int i = 16; i >= 0; i--) {
// 如果前缀相等就跳
if (h[x][i] == h[y][i]) {
x = t[x][i], y = t[y][i];
}
}
// 跳到最远的地方, 下一个就是不相等位置
return h[x][0] < h[y][0];
});
for (int i = 1; i <= n; i++) {
cout << ans[i] << '\n';
}
return 0;
}
H - P3546 [POI2012] PRE-Prefixuffix
利用前后缀相等性质, 可以找出 i 的上界, 这种一递推关系, 答案规模慢慢扩大一定要想到, 字符串的 next 数组也是同样理念
找出 i 和 i + 1 的关系#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 5;
const ll P = 131;
const ll M = 1e9 + 7;
int n, b[N / 2];
ll p[N], h[N];
string s;
void Init() {
s = '-' + s;
p[0] = 1;
for (int i = 1; i <= n; i++) {
p[i] = p[i - 1] * P % M;
h[i] = (h[i - 1] * P % M + s[i]) % M;
}
}
ll Get(int l, int r) { return (h[r] + M - (h[l - 1] * p[r - l + 1] % M)) % M; }
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> s;
Init();
int ans = 0;
for (int i = n / 2; i >= 1; i--) {
// 求出 [i + 1, n - i] 的 最长公共前后缀
// 考虑知道 b[i] 求 b[i + 1], 推出 b[i + 1] >= b[i] - 2 (还有可以拓展的空间)
// 那么 b[i] <= b[i + 1] + 2, 这就是上界
for (int j = b[i + 1] + 2; j >= 1; j--) {
if (i + j <= n / 2 && Get(i + 1, i + j) == Get(n - i - j + 1, n - i)) {
b[i] = j;
break;
}
}
if (Get(1, i) == Get(n - i + 1, n)) {
ans = max(ans, i + b[i]);
}
}
cout << ans;
return 0;
}
|
|