双哈希
为了避免哈希把两个不同的字符串映射到同一个数上面去。
于是用两组哈希值都存一下，然后判断相等的时候就是当且仅当两个哈希值都相等的时候这两个字符串才相等
哈希是这样的吗，我感觉我之前学的哈希不是这样的，心碎了。
T1 5043 [模板] 树同构
这一题就是先把每一棵树对应的哈希值给求出来，然后再遍历一遍找一下有没有和这棵树哈希值相等的树，如果有的话就选择第一个输出来。
然后树的哈希值求法是看的题解，记住了，以后就这么求。然后这个模数还挺玄学的，上网找了两个但是都是九十分，题解的那个 \(2333\) 就是一百分，这个就只能看运气了吧。
int n,m;
int ans[N][N];
vector<int> e[N];
lwl Hash(int u,int fa) {
lwl q[N];
int idx = 0;
lwl ans = N;
for (auto v : e[u]) {
if (v == fa) continue;
q[++ idx] = Hash(v,u);
}
sort(q + 1,q + 1 + idx);
for (int i = 1; i <= idx; i ++) {
ans = ans * p + q[i];
}
return ans * p + N + 1;
}
int main(){
m = fr();
for (int i = 1; i <= m; i ++) {
n = fr();
for (int j = 1; j <= n; j ++) e[j].clear();
for (int j = 1; j <= n; j ++) {
int a = fr();
if (!a) continue;
e[j].push_back(a);
e[a].push_back(j);
}
for (int j = 1; j <= n; j ++) {
ans[i][j] = Hash(j,0);
}
sort(ans[i] + 1,ans[i] + 1 + n);
for (int j = 1,k = 0; j <= i; j ++) {
while (k <= n) {
if (ans[i][++ k] != ans[j][k]) break;
}
if (k > n) {
fw(j);
ch;
break;
}
}
}
return 0;
}
拓扑排序
T1 1954 航空管制
因为这个航班同时有两种依赖关系，所以我们先根据第二种依赖关系将所有点的 \(k\) 值更新一下，更新的方式就是把所有依赖遍历一遍，把每个 \(k[i]\) 更新为 \(\min(k[i],k[v] - 1)\)，然后这个就是这个点真实的 \(k\) 值。
处理出来这个 \(k\) 值之后，就可以根据这个 \(k\) 值加上优先队列和拓扑排序求出来第一问了。
第二问的话需要一开始存边的时候存一个反向边。因为第一问的做法其实实际上是让每一架航班都尽量晚飞。然后在处理第二问的时候，其实就是要让 \(i\) 点和 \(i\) 点依赖的点尽量早飞，这就等价于让其他航班尽量晚飞。
所以我们就通过反向边 \(dfs\) 标记一下 \(i\) 点及其祖先，然后根据 \(k\) 值从大到小，从后往前安排其它航班。
由于其他航班是从后往前安排的，即这些航班占据了可能的、最晚的起飞时间。那么空出来的起飞时间一定是可能情况下最早的。而 \(i\) 最早的起飞时间，就是这些空出来的起飞时间中最后一个（其余空出来的时间必须安排 \(i\) 的祖先）。我们在从后往前安排其他航班的过程中即可顺便求解。
int n,m;
int k[N],d[N],temp[N];
vector<int> e[N];
vector<int> fe[N];
bool flag[N];
int num[N][N],cnt[N];
void Top() {
memcpy(temp,d,sizeof temp);
priority_queue<pii,vector<pii>,greater<pii> > q;
for (int i = 1; i <= n; i ++) {
if (!d[i]) {
q.push({k[i],i});
}
}
while (q.size()) {
auto t = q.top();
q.pop();
fw(t.se),kg;
for (auto v : e[t.se]) {
d[v] --;
if (!d[v]) q.push({k[v],v});
}
}
ch;
memcpy(d,temp,sizeof temp);
}
void dfs(int u) {
if (flag[u]) return ;
flag[u] = true;
for (auto v : e[u]) {
dfs(v);
k[u] = min(k[u],k[v] - 1);
}
num[k[u]][++ cnt[k[u]]] = u;
}
void fdfs(int u) {
flag[u] = true;
for (auto v : fe[u]) {
if (!flag[v]) fdfs(v);
}
}
int main(){
n = fr(),m = fr();
for (int i = 1; i <= n; i ++) {
k[i] = fr();
}
int a,b;
while (m --) {
a = fr(),b = fr();
e[a].push_back(b);
fe[b].push_back(a);
d[b] ++;
}
for (int i = 1; i <= n; i ++) {
dfs(i);
}
Top();
for (int i = 1; i <= n; i ++) {
for (int j = 1; j <= n; j ++) {
flag[j] = false;
}
fdfs(i);
int ans = n;
for (int j = n; j; j --) {
if (ans > j) break;
for (int t = 1; t <= cnt[j]; t ++) {
if (!flag[num[j][t]])
ans --;
}
}
fw(ans);
kg;
}
ch;
return 0;
}
1054 等价表达式
模拟就不写太多了，就是模拟。
然后这里的数组维度是指的是 \(a\) 的次数
struct node{
lwl w[N];
void clear() {
memset(w,0,sizeof w);
}
node operator = (const node &t) {
this->clear();
for (int i = 0; i <= n; i ++)
w[i] = t.w[i];
return *this;
}
node operator = (const lwl &t) {
this->clear();
w[0] = t;
return *this;
}
node operator + (const node &t) const {
node ww;
for (int i = 0; i <= n; i ++) {
ww.w[i] = w[i] + t.w[i];
}
return ww;
}
node operator - (const node &t) const {
node ww;
for (int i = 0; i <= n; i ++) {
ww.w[i] = w[i] - t.w[i];
}
return ww;
}
node operator * (const node &t) const {
node ww;
ww.clear();
for (int i = 0; i <= n; i ++) {
for (int j = 0; j <= n; j ++) {
if (i + j > n) continue;
int p = i + j;
ww.w[p] += w[i] * t.w[j];
}
}
return ww;
}
node pow(const node &t) const {
int h = t.w[0];
node ans;ans = 1;
node a = *this;
while (h) {
if (h & 1) ans = ans * a;
a = a * a;
h >>= 1;
}
return ans;
}
void print() {
for(int i = n; i >= 0; i --) {
if (w[i] == 0) continue;
if (i != n) cout << '+';
cout << w[i] << 'a' << i;
}
cout << endl;
}
bool operator == (const node &t) const {
for (int i = 0; i <= n; i ++) {
if (w[i] != t.w[i]) return false;
}
return true;
}
};
stack<node> num;
stack<char> op;
bool check(char t) {
if (t >= '0' && t <= '9') return true;
if (t == '+' || t == '-' || t == '*' || t == '^')
return true;
if (t == '(' || t == ')' || t == 'a') return true;
return false;
}
int level(char t) {
if (t == '^') return 3;
if (t == '*') return 2;
if (t == '-' || t == '+') return 1;
return 0;
}
void suan() {
node b = num.top();num.pop();
node a = num.top();num.pop();
char c = op.top();op.pop();
node ans;
if (c == '+') ans = a + b;
else if (c == '-') ans = a - b;
else if (c == '*') ans = a * b;
else ans = a.pow(b);
num.push(ans);
}
void get(string &s){
s.clear();
char ch;
while(((ch=cin.get())==' ')||ch=='\n'||ch=='\r');
do{
if(ch==' ') continue;
s.push_back(ch);
}while((ch=cin.get())!='\n'&&ch!=EOF&&ch!='\r');
}
node frr() {
string s; s.reserve(60); get(s);
int len = s.length();
int cnt = 0;
bool flag = true;
if (!len) flag = false;
for (int i = 0; i < len; i ++) {
if (s[i] == '(') cnt ++;
if (s[i] == ')') cnt --;
if (cnt < 0) flag = false;
}
if (cnt) flag = false;
if (!flag) {
node WA;
WA.clear();
WA.w[n + 1] = 114514;
return WA;
}
flag = false;
lwl t = 0;
node u,h;
u.clear(),h.clear();
u.w[1] = 1;
for (int i = 0; i < len; i ++) {
if (!check(s[i])) continue;
if (s[i] == 'a') {
num.push(u);
continue;
}
if (s[i] >= '0' && s[i] <= '9') {
t = t * 10 + s[i] - '0';
flag = true;
continue;
}
if (flag) {
h = t;
t = 0,flag = false;
num.push(h);
}
if (s[i] == '(') {
op.push(s[i]);
continue;
}
if (s[i] == ')') {
while (op.top() != '(')
suan();
op.pop();
continue;
}
while (op.size() && level(op.top()) >= level(s[i]))
suan();
op.push(s[i]);
}
if (flag) {
h = t;
num.push(h);
}
while (op.size())
suan();
u = num.top();
num.pop();
return u;
}
int main(){
//freopen("qwq.in","r",stdin);
node ans; ans = frr();
int T = fr();
for (int i = 0; i < T; i ++) {
node t = frr();
if (t == ans) {
putchar('A' + i);
}
}
return 0;
}
练习
一开始搞第一题搞了好久，所以后面的题都没怎么看，都是后面补得。
A.电子表格计算器
算什么拓扑排序，明明就是大模拟，模拟写的我想死真的是，写这题写了快三个小时，结果八十分卡了半天是因为老师的数据出的有问题，所以过不去。
不知道老师标程怎么过去的。中间有一点代码是特判那个错误数据用的。
#include<bits/stdc++.h>
#include<ext/rope>
using namespace std;
using namespace __gnu_cxx;
typedef long long lol;
typedef pair<int, int> pii;
typedef pair<lol, lol> pll;
typedef pair<double, double> pdd;
typedef unsigned int uin;
typedef unsigned long long ull;
const int N = 305;
int n, m, d[N][N], c[N][N];
char s[N];
vector<pair<pii, int>> lnk[N][N];
queue<pii> q;
int main ()
{
scanf ("%d%d", &n, &m);
getchar();
for (int i = 1; i <= n; ++ i )
for (int j = 1; j <= m; ++ j )
{
scanf ("%s", s);
int p = 0, len = strlen (s), flg;
while (s[p] != '\0')
{
flg = 1;
while (s[p] == '-' || s[p] == '+')
{
if (s[p] == '-')
flg *= -1, ++ p;
else if (s[p] == '+')
++ p;
}
if (isdigit(s[p]))
{
int x = 0;
while (p < len && isdigit(s[p])) x = x * 10 + s[p] - '0', ++ p;
d[i][j] += flg * x;
}
else
{
int sy = s[p] - 'A' + 1, sx = 0;
++ p;
while (p < len && isdigit(s[p])) sx = sx * 10 + s[p] - '0', ++ p;
if (sx > n) continue;
lnk[sx][sy].push_back({{i, j}, flg}), ++ c[i][j];
}
}
if (!c[i][j]) q.push({i, j});
}
while (!q.empty())
{
pii u = q.front();
int x = u.first, y = u.second;
q.pop();
for (auto &item : lnk[x][y])
{
d[item.first.first][item.first.second] += d[x][y] * item.second;
--c[item.first.first][item.first.second];
if (!c[item.first.first][item.first.second])
q.push(item.first);
}
}
printf ("%d %d\n", n, m);
for (int i = 1; i <= n; ++ i )
{
for (int j = 1; j <= m; ++ j )
if (c[i][j]) printf ("ERROR ");
else printf ("%d ", d[i][j]);
printf ("\n");
}
return 0;
}
B.杂务
洛谷上做过原题
int n;
int w[N],h[N];
vector<int> e[N];
int d[N];
int main(){
n=fr();
for(int i=1;i<=n;i++){
int id=fr();
w[i]=fr();
int a;
while(1){
a=fr();
if(!a) break;
e[a].push_back(id);
d[id]++;
}
}
int ans=0;
queue<int> q;
for(int i=1;i<=n;i++)
if(!d[i]){
q.push(i);
h[i]=w[i];
}
while(q.size()){
auto t=q.front();
q.pop();
for(auto v:e[t]){
d[v]--;
if(!d[v]) q.push(v);
h[v]=max(h[v],h[t]+w[v]);
}
}
for(int i=1;i<=n;i++)
ans=max(ans,h[i]);
cout<<ans<<endl;
return 0;
}
C.第二饭堂
哈希，但不完全哈希。就让他自然溢出就可以了。因为要求回文串，而回文串的性质其中有一条就是从前往后的哈希值和从后往前的哈希值是一样的，所以我们就判断一下前面的是不是回文串就可以了。
而且显而易见的是，如果回文串的前面一半是回文串，那么回文串的后面一半也是回文串，就可以这样求了。
代码极短
int dp[N];
int main(){
string s;
cin >> s;
lwl p = 1,ans = 0,l = 0,r = 0;
for (int i = 0; i < s.length(); i ++) {
l = l * 929 + s[i] - '0' + 1; // 从后往前的哈希值
r = r + (s[i] - '0' + 1) * p; // 从后往前的哈希值
p *= 929;
if (l == r) dp[i + 1] = dp[(i + 1) / 2] + 1;
// 如果相等的话，就加一下
ans += dp[i + 1];
}
fw(ans);
return 0;
}
D.图的逆变换
大致思路：如果在 \(D\) 图中有 \(u -> v -> w\) ，又有 \(x -> v -> w\)，那么在新建的图 \(E\) 中 \(uv,xv\) ，都应该向 \(vw\) 连边，此时如果存在另一个 \(y\) 使得 \(v -> y\) 之间有边，那么在 \(E\) 中也应该有 \(uv -> vy\),\(xv -> vy\)
也就是说，如果两个点指向一个公共的点，那么他们所有出边指向的点集必然相同，事实上这就是存在 \(D\) 的充要条件。
然后这个可以用 \(bitsets\) 记录邻接矩阵，算一下两行的与和异或，如果与不是 \(0\) ，那么就说明指向公共点，此时看异或，如果异或不是 \(0\) ，那么就说明出边不重合，那么就说明不存在 \(D\)
int n,m;
bitset<N> w[N];
bitset<N> y,h;
int main(){
int T = fr();
while (T --) {
n = fr();
m = fr();
for (int i = 1; i <= n; i ++) {
w[i].reset();
}
for (int i = 1; i <= m; i ++) {
int a = fr() + 1,b = fr() + 1;
w[a].set(b);
}
bool flag = true;
for (int i = 1; i <= n; i ++) {
for (int j = 1; j <= n; j ++) {
y = w[i] & w[j],h = w[i] ^ w[j];
if (y.count() && h.count()) {
flag = false;
break;
}
}
}
if (flag) yj;
else wj;
}
return 0;
}