P9753 [CSP-S 2023] 消消乐
一道公式推理题,我们知道一般删除操作我们肯定是用栈来维护,假设我们的字符串是 \(abbddcc\),那么我们的栈的每次操作因该是长这样:
次数 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
---|---|---|---|---|---|---|---|---|
内容 | 空 | a | ab | a | ac | a | ad | a |
观察表格,我们发现, \(a\) 频繁出现,每次出现都代表着删除次数的增加。那么 \(a\) 的次数与答案有什么联络吗?有的有的包有的。
我们发现,这个时候的答案因该是 \(6\),次数是 \(4\),当我们将后面的 \(cc\) 删除后,答案因该是 \(3\),次数是 \(3\).你可以在写几组,然后通过次数的答案发现公式因该是 \(x * (x - 1) / 2\)
那么,根据这个规律,我们先用普通写法找出每次的栈的状态后,将他存储起来。然后统计每个的状态出些的次数通过公式求出答案。
code
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
string s;
stack<int>q,pos;
map<int,int>op;
int cnt;
int hs[2000005];
set<int>S;
signed main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin >> n >> s;s = " " + s;S.insert(0);op[0] = 1;for(int i = 1 ; i <= n ; i ++){if(!q.empty() && q.top() == s[i] - 'a'){op[hs[pos.top() - 1]] ++;hs[i] = hs[pos.top() - 1];q.pop();pos.pop();}else{q.push(s[i] - 'a');pos.push(i);hs[i] = hs[i - 1] * 131 + s[i];S.insert(hs[i]);op[hs[i]] ++;}}int ans = 0;for(int v : S){ans += op[v] * (op[v] - 1) / 2;}cout << ans;return 0;
}
P4398 [JSOI2008] Blue Mary的战役地图
小小板子,直接拿捏,我们发现 \(n\) 的范围可以支持到 \(n ^ 5\) 然后,问的是一个正方形,那么我们直接暴力正方形的边长,然后跑两边哈希。
两张图片都要跑一遍。记住不要写成 \(pw_a * pw_b\) 这不等于 \(pw_{a * b}\) ,然后,我们就直接暴力两张图的右下角,判断两个矩阵的哈希值是否一致。
这个地方有一个小小的优化,当我们发现一致的时候说明边长是 \(h\) 的时候有答案了,那么就不用再判断边长是 \(h\) 的正方形了。
code
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,maxn;
int a[1005][1005],b[1005][1005];
int hs1[1005][1005],hs2[1005][1005];
int pw[1000005];
int dp1[1005][1005],dp2[1005][1005];
int check1(int x,int l,int r){return hs1[x][r] - hs1[x][l - 1] * pw[r - l + 1];
}
int check2(int x,int l,int r){return hs2[x][r] - hs2[x][l - 1] * pw[r - l + 1];
}
signed main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin >> n;for(int i = 1 ; i <= n ; i ++){for(int j = 1 ; j <= n ; j ++){cin >> a[i][j];}}for(int i = 1 ; i <= n ; i ++){for(int j = 1 ; j <= n ; j ++){cin >> b[i][j];}}for(int A = 1 ; A <= n ; A ++){int B = A;pw[0] = 1;for(int i = 1 ; i <= n * n ; i ++){pw[i] = pw[i - 1] * 131;}for(int i = 1 ; i <= n ; i ++){for(int j = 1 ; j <= n ; j ++){hs1[i][j] = hs1[i][j - 1] * 131 + a[i][j];}}for(int i = 1 ; i <= n ; i ++){for(int j = 1 ; j <= n ; j ++){hs2[i][j] = hs2[i][j - 1] * 131 + b[i][j];}}int cf = pow(131 , B);for(int j = B ; j <= n ; j ++){for(int i = 1 ; i <= n ; i ++){dp1[i][j] = dp1[i - 1][j] * pw[B] + check1(i , j - B + 1 , j);if(i > A){dp1[i][j] = dp1[i][j] - check1(i - A , j - B + 1 , j) * pw[A * B];}}}for(int j = B ; j <= n ; j ++){for(int i = 1 ; i <= n ; i ++){dp2[i][j] = dp2[i - 1][j] * pw[B] + check2(i , j - B + 1 , j);if(i > A){dp2[i][j] = dp2[i][j] - check2(i - A , j - B + 1 , j) * pw[A * B];}}}bool f = 1;for(int i = A ; i <= n ; i ++){for(int j = A ; j <= n ; j ++){for(int x = A ; x <= n ; x ++){for(int y = A ; y <= n ; y ++){if(dp1[i][j] == dp2[x][y]){maxn = max(maxn , A);f = 0;break;}}}if(!f)break;}if(!f)break;}}cout << maxn;return 0;
}
P2580 于是他错误的点名开始了
首先,我们先来了解一下字典树,这是一个求前缀最快的算法不知道有没有之一。它是怎么建立的呢?既然是求前缀的算法,那么肯定与前缀有关。
首先,当有一个字符串的前缀和一个字符串的前缀相同的时候,我们就是在两个字符串相同的位置后面进行分叉,显示出两个字符串。
补充:1、我们可以在当前字符串的字典树上经过的每个点都进行标记,表示走到当前位置就是走到了当前字符串的前缀位置,也可以用来表示有一个字符串的前缀是这个。
2、在字符串的字典树上的结束位置标记,代表着这是一个完整的字符串了。
这样,我们搜一个字符串是一个字符串的前缀的时候,就可以直接从根开始,然后根据当前的字符想不同的路去走,如果走着走着就没有相同的字符了,说明这不是前缀,否则就是有一个字符的前缀。
但是,我们发现,这道题目还要求是几个字符串的前缀。那么,我们就可以在每次建树的时候直接统计当前前缀有几个字符串变成。
但是,当我们找当前的树的下一个节点的时候知道字符但是不知道是哪一个啊,所以这个时候我们就要标记字符但是又不能直接看字符,因为如果还有一条边的字符相同呢?,
所以,我们就给每一次的每个点的字符给一个新的编号然后通过编号找下一个字符。那么,这道板子题目和这道板子我就不讲了。
code
#include<bits/stdc++.h>
using namespace std;
int n,m;
int node[500005][26];
int mp[500005];
int tot;
void insert(string s){int len = s.size();int u = 0;for(int i = 0 ; i < len ; i ++){int c = s[i] - 'a';if(node[u][c] == 0){node[u][c] = ++tot;}u = node[u][c];}mp[u] ++;
}
int search(string s){int len = s.size();int u = 0;for(int i = 0 ; i < len ; i ++){int c = s[i] - 'a';if(node[u][c] == 0){return 0;}u = node[u][c];}return mp[u];
}
int main(){cin >> n;for(int i = 1 ; i <= n ; i ++){string s;cin >> s;insert(s);}cin >> m;while(m --){string s;cin >> s;int x = search(s);if(x == 1){cout << "OK\n";insert(s);}else if(x > 1){cout << "REPEAT\n";}else{cout << "WRONG\n";}}return 0;
}
P1470 [USACO2.3] 最长前缀 Longest Prefix
对于本题,我们知道每一次我们都是在上面的答案中间选择一个字符串。记住要选完哦,所以建树的时候我们将结尾字符标记了。
然后,我们就可以从另一个字符串中搜索,我们知道每次到达底部了当然要回到根节点,但是,有些时候在前面到达其中的结尾的时候我们既可以回到根节点也可以继续搜索。
这个时候我们应该怎么抉择呢?不知道,但是,我们可以直接暴力搜索两次的答案。注意还有一种情况,因为题目作者的操作,我们选择的不一定连续哦。所以还有一种情况要搜。
code
#include<bits/stdc++.h>
using namespace std;
int n,m;
int node[1000005][65];
int mp[1000005];
int tot,ans;
string s;
bool vis[1000005];
void insert(string s){int len = s.size();int u = 0;for(int i = 0 ; i < len ; i ++){int c = s[i] - 'A';if(node[u][c] == 0){node[u][c] = ++tot;}u = node[u][c];}mp[u] = 1;
}
void dfs(int pos,int k){int u = s[pos] - 'A';k = node[k][u];if(mp[k]){ans = max(ans , pos + 1);if(!vis[pos]){dfs(pos + 1 , 0);}vis[pos] = true;}if(k != 0){dfs(pos + 1 , k);}
}
int main(){string x;while(cin >> x){if(x == ".")break;insert(x);}string y = "";while(cin >> y){s += y;}dfs(0 , 0);cout << ans;return 0;
}
P10471 最大异或对 The XOR Largest Pair
首先,我们知道异或就是在二进制中两个数的数位上的数不同则当前答案数位是 \(1\)。那么,我们就可以先将所有的数字转换成二进制。
答案要最大,那么首先就是确保高位是 \(1\) 这样我们才能去报答案最大。因为,当高位是 \(0\) 哪怕剩下的低位全是 \(1\) 也没有高位是 \(1\) 的时候大。
然后,我们还知道二进制中每个位数总是前面所有位是 \(1\) 后再加 \(1\)。因此我们优先选择高位异或值是 \(1\) 的情况。但是,我们仍然发现一件事。
对于每个位置,每次在字典树中一边走 \(1\) 另一边走 \(0\) 每次都是相反的走。这当然没错,但是高位是 \(1\) 且相同后还要比较低位啊,我们却不知道怎么走才能让确保高位是 \(1\) 之后低位更大。
也就是不知道该走 \(1/0\) 还是 \(0/1\) ,也就是我们需要提前得到其中的一个数值的信息,然后找与当前信息相反的分支。那么,我们就可以搜索解决。
code
#include<bits/stdc++.h>
#define int long long
using namespace std;
int T;
int n;
int top;
int maxn;
int node[3200005][10];
void insert(int x){int u = 0;for(int i = 30 ; i >= 0 ; i --){int c = (x >> i) & 1;if(node[u][c] == 0){node[u][c] = ++top;}u = node[u][c];}return;
}
int search(int x){int u = 0,ans = 0;for(int i = 30 ; i >= 0 ; i --){int c = (x >> i) & 1;if(node[u][c ^ 1]){u = node[u][c ^ 1];ans += (1 << i);}else{u = node[u][c];}}return ans;
}
signed main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin >> n;for(int i = 1 ; i <= n ; i ++){int x;cin >> x;insert(x);maxn = max(maxn , search(x));}cout << maxn;return 0;
}
P4551 最长异或路径
问个简单的问题:什么是爱情,我们知道两点的距离因该是从根节点到那两个点的答案减去双倍的 \(lca\)。就是:dis[x] + dis[y] - 2 * dis[lca(x,y)]
图长这样:
那么,我们转换到本题这个是所有边权的异或值,观察图片,两个答案的异或值不就是从根节点到 \(x,y\) 的异或值吗?因为,根节点到 \(LCA\) 的异或答案是 \(0\),然后剩下的部分也就是从 \(LCA\) 到 \(x,y\) 的异或答案异或根据可拆分性也就是从 \(x\) 到 \(y\) 的异或答案了。
那么,这道题目就演变成了上一题了。根节点到其余点的答案就是 \(a_i\) 求的不变。
code
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
struct pi{int v,w;
};
vector<pi>E[100005];
int top;
int maxn;
int dp[100005];
int node[3200005][10];
void insert(int x){int u = 0;for(int i = 30 ; i >= 0 ; i --){int c = (x >> i) & 1;if(node[u][c] == 0){node[u][c] = ++top;}u = node[u][c];}return;
}
int search(int x){int u = 0,ans = 0;for(int i = 30 ; i >= 0 ; i --){int c = (x >> i) & 1;if(node[u][c ^ 1]){u = node[u][c ^ 1];ans += (1 << i);}else{u = node[u][c];}}return ans;
}
void dfs(int u,int fa){for(int i = 0 ; i < E[u].size() ; i ++){int v = E[u][i].v;if(v != fa){dp[v] = dp[u] ^ E[u][i].w;dfs(v , u);} }
}
signed main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin >> n;for(int i = 1 ; i < n ; i ++){int u,v,w;cin >> u >> v >> w;E[u].push_back({v , w});E[v].push_back({u , w});}dfs(1 , 0);for(int i = 1 ; i <= n ; i ++){insert(dp[i]);}for(int i = 1 ; i <= n ; i ++){maxn = max(maxn , search(dp[i]));}cout << maxn;return 0;
}
P3065 [USACO12DEC] First! G
我们可以发现,有两种情况是不可以的,首先就是当前字符串的前缀是另一个字符串,那么无论如何也不可能通过改变顺序使得当前字符串最小。因为比较规则中如果没有不同的字符串小的字符串更小。
第二种情况就是出现了冲突,比如我们一开始发现 \(a > b,b > c\) 然后突然发现 \(b > a\) 这个时候就是出现了冲突,也可以看作有了一个环。那么,这种情况我们怎么找出来呢?
我们发现,如果当前字符串要最小,也就是当前字符串与其他字符比较的第一个不同的位置的字符的顺序更靠前。这个时候我们观察到“第一个不同的位置”,联想到字典树。
这不就是当前字符串的字典树中每次出现分叉的时候当前字符比其他字符小吗?那么,我们就根据这个性质,我们就可以推理出每两个字符的关系了,然后就要判断是否有环了。我们可以并查集或者拓扑判环。
code
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
vector<string>E;
vector<int>G[100005];
int top;
map<int,int>mp;
int maxn;
int dp[100005];
int node[30001 * 26][52];
string s[100005];
int in[100005];
void insert(string s){int len = s.size();int u = 0;for(int i = 0 ; i < len ; i ++){int c = s[i] - 'a';if(node[u][c] == 0){node[u][c] = ++top;}u = node[u][c];}mp[u] = 1;
}
int search(string s){int len = s.size();int u = 0,ans = 0;for(int i = 0 ; i < len - 1 ; i ++){int c = s[i] - 'a';u = node[u][c];ans += mp[u];}return ans;
}
bool tuopu(){for(int i = 0 ; i < 26 ; i ++){in[i] = 0;}for(int i = 0 ; i < 26 ; i ++){for(int j = 0 ; j < G[i].size() ; j ++){int v = G[i][j];in[v] ++;}}queue<int>q;for(int i = 0 ; i < 26 ; i ++){if(!in[i])q.push(i);}while(!q.empty()){int u = q.front();q.pop();for(int i = 0 ; i < G[u].size() ; i ++){int v = G[u][i];if(v == u)continue; in[v] --;if(in[v] == 0){q.push(v);}}}for(int i = 0 ; i < 26 ; i ++){if(in[i]){return false;}}return true;
}
bool check(string s){int u = 0,len = s.size();for(int i = 0 ; i < 26 ; i ++){G[i].clear();}for(int i = 0 ; i < len ; i ++){int c = s[i] - 'a';for(int j = 0 ; j < 26 ; j ++){if(node[u][j] && j != c){G[j].push_back(c);}}u = node[u][c];}return tuopu();
}
signed main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin >> n;for(int i = 1 ; i <= n ; i ++){cin >> s[i];insert(s[i]); }for(int i = 1 ; i <= n ; i ++){if(search(s[i]) == 0 && check(s[i])){E.push_back(s[i]);}}cout << E.size() << "\n";for(int i = 0 ; i < E.size() ; i ++){cout << E[i] << "\n";}return 0;
}