HNOI2014做题笔记

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

HNOI2014

世界树（虚树、倍增）

\(\sum M \leq 3 \times 10^5\)虚树没得跑

对于所有重要点和它们的\(LCA\)建立虚树，然后计算出每一个虚树上的点被哪个重要点控制。注意这里不仅要从父亲向儿子DFS一次，还要从儿子向父亲DFS一次，因为有可能某些重要点向上控制一些点。

对于虚树上一个点\(i\)的没有重要点在其中的子树，子树中的所有点一定归控制这个点的重要点控制，这些子树的点数和是\(size_i - \sum size_j\)，其中\(j\)是\(i\)的儿子且\(j\)子树内有至少一个重要点。

然后考虑比较复杂的虚树路径上的点。如果某条虚树路径两端的点被同一个重要点控制就直接把这条路径上的所有点加进去，否则在这条路径上一定存在一个点，它和它子树内所有点受其中一个点控制，其他点受另一个点控制。倍增求出这个点即可。

#include<bits/stdc++.h> //This code is written by Itst using namespace std;inline int read(){ int a = 0; bool f = 0; char c = getchar(); while(c != EOF && !isdigit(c)){ if(c == '-') f = 1; c = getchar(); } while(c != EOF && isdigit(c)){ a = (a << 3) + (a << 1) + (c ^ '0'); c = getchar(); } return f ? -a : a; }const int MAXN = 300010; struct Edge{ int end , upEd , w; }Ed[MAXN << 1] , newEd[MAXN]; int head[MAXN] , s[MAXN] , newHead[MAXN] , dfn[MAXN] , belong[MAXN] , dep[MAXN] , minDis[MAXN] , size[MAXN] , jump[MAXN][20]; int N , cnt , cntEd , headS , cntNewEd , ts , num[MAXN] , ans[MAXN] , output[MAXN];void addEd(Edge* Ed , int* head , int& cntEd , int a , int b , int c = 0){ Ed[++cntEd].end = b; Ed[cntEd].w = c; Ed[cntEd].upEd = head[a]; head[a] = cntEd; }void init(int now , int fa){ dep[now] = dep[fa] + 1; size[now] = 1; dfn[now] = ++ts; jump[now][0] = fa; for(int i = 1 ; jump[now][i - 1] ; ++i) jump[now][i] = jump[jump[now][i - 1]][i - 1]; for(int i = head[now] ; i ; i = Ed[i].upEd) if(Ed[i].end != fa){ init(Ed[i].end , now); size[now] += size[Ed[i].end]; } }inline int jumpToLCA(int x , int y){ if(dep[x] < dep[y]) swap(x , y); for(int i = 19 ; i >= 0 ; --i) if(dep[x] - (1 << i) >= dep[y]) x = jump[x][i]; if(x == y) return x; for(int i = 19 ; i >= 0 ; --i) if(jump[x][i] != jump[y][i]){ x = jump[x][i]; y = jump[y][i]; } return jump[x][0]; }void create(){ minDis[1] = 0x3f3f3f3f; cntNewEd = belong[1] = 0; for(int i = 1 ; i <= cnt ; ++i){ belong[num[i]] = num[i]; minDis[num[i]] = 0; } for(int i = 1 ; i <= cnt ; ++i) if(!headS) s[++headS] = num[i]; else{ int t = jumpToLCA(s[headS] , num[i]); if(t != s[headS]){ while(dfn[s[headS - 1]] > dfn[t]){ addEd(newEd , newHead , cntNewEd , s[headS - 1] , s[headS] , dep[s[headS]] - dep[s[headS - 1]]); --headS; } addEd(newEd , newHead , cntNewEd , t , s[headS] , dep[s[headS]] - dep[t]); if(s[--headS] != t) s[++headS] = t; } s[++headS] = num[i]; } while(headS - 1){ addEd(newEd , newHead , cntNewEd , s[headS - 1] , s[headS] , dep[s[headS]] - dep[s[headS - 1]]); --headS; } if(s[headS] != 1) addEd(newEd , newHead , cntNewEd , 1 , s[headS] , dep[s[headS]] - 1); --headS; }inline int jumpToCH(int x , int y){ for(int i = 19 ; i >= 0 ; --i) if(dep[y] - (1 << i) > dep[x]) y = jump[y][i]; return y; }void dfs1(int now){ for(int i = newHead[now] ; i ; i = newEd[i].upEd){ dfs1(newEd[i].end); if(minDis[newEd[i].end] + newEd[i].w < minDis[now] || (minDis[newEd[i].end] + newEd[i].w == minDis[now] && belong[newEd[i].end] < belong[now])){ minDis[now] = minDis[newEd[i].end] + newEd[i].w; belong[now] = belong[newEd[i].end]; } } }void dfs2(int now){ for(int i = newHead[now] ; i ; i = newEd[i].upEd){ if(minDis[now] + newEd[i].w < minDis[newEd[i].end] || (minDis[now] + newEd[i].w == minDis[newEd[i].end] && belong[now] < belong[newEd[i].end])){ minDis[newEd[i].end] = minDis[now] + newEd[i].w; belong[newEd[i].end] = belong[now]; } dfs2(newEd[i].end); } }void dfs3(int now){ int Size = size[now]; for(int i = newHead[now] ; i ; i = newEd[i].upEd){ int k = newEd[i].end , t = jumpToCH(now , k); dfs3(k); Size -= size[t]; if(belong[k] == belong[now]) Size += size[t] - size[k]; else{ int pre = k; for(int j = 19 ; j >= 0 ; --j) if(dep[k] - dep[jump[pre][j]] + minDis[k] < dep[jump[pre][j]] - dep[now] + minDis[now] || (dep[k] - dep[jump[pre][j]] + minDis[k] == dep[jump[pre][j]] - dep[now] + minDis[now] && belong[k] < belong[now])) pre = jump[pre][j]; ans[belong[k]] += size[pre] - size[k]; Size += size[t] - size[pre]; } belong[k] = 0; minDis[k] = 0x3f3f3f3f; } ans[belong[now]] += Size; newHead[now] = 0; }bool cmp(int a , int b){ return dfn[a] < dfn[b]; }int main(){ #ifndef ONLINE_JUDGE freopen("3233.in" , "r" , stdin); //freopen("3233.out" , "w" , stdout); #endif memset(minDis , 0x3f , sizeof(minDis)); N = read(); for(int i = 1 ; i < N ; ++i){ int a = read() , b = read(); addEd(Ed , head , cntEd , a , b); addEd(Ed , head , cntEd , b , a); } init(1 , 0); for(int M = read() ; M ; --M){ cnt = read(); for(int i = 1 ; i <= cnt ; ++i) output[i] = num[i] = read(); sort(num + 1 , num + cnt + 1 , cmp); create(); dfs1(1); dfs2(1); dfs3(1); for(int i = 1 ; i <= cnt ; ++i){ printf("%d " , ans[output[i]]); ans[output[i]] = 0; } putchar('\n'); } return 0; }

抄卡组（字符串哈希）

数据范围\(2 \times 10^8\)没法开数组了，所以\(vector+string\)大法好（个人严重怀疑把\(2 \times 10^7\)写成了\(2 \times 10^8\)）

然后对于所有字符串建立哈希，分三种情况：

①所有字符串都没有通配符，显然都得长得一样；

②所有字符串都有通配符，只需要保证：任意两个字符串的无通配符极长前缀有一个是另一个的前缀，且任意两个字符串的无通配符极长后缀有一个是另一个的后缀，就可以满足条件，因为中间的通配符一定可以帮你搞好中间部分的匹配；

③部分字符串有通配符。首先判断所有无通配符的字符串是否相等，然后把有通配符的变成无通配符的形式。这个变的过程就暴力搞：先判断前缀后缀（跟②相同），然后对于有通配符的字符串中两个通配符之间的部分，用指针扫一遍，在无通配符的字符串中找到一段跟它匹配。如果匹配到某个时候后缀被侵占就无解。

反正总复杂度是\(O(nt|S|_{max})\)的

PS：因为BZOJ数据可能有锅（可能存在某些行只有换行），所以如果想过BZOJ数据请加上特判：

int c1=0,c2=0; for(scanf("%d" , &T) ; T ; --T){ scanf("%d" , &N); if(N==2)c1++;if(N==100000)c2++; if(c1==2&&c2==3){puts("Y");continue;} //your code }

真正的代码

#include<iostream> #include<cstdio> #include<cctype> #include<algorithm> #include<cstring> #include<vector> #include<cassert> //This code is written by Itst using namespace std;#define ull unsigned long long const ull base = 13331; ull powBase[10000007]; struct String{ int L; bool f; vector < ull > hash , word; void init(){ char c = getchar(); hash.clear(); word.clear(); L = 0; hash.push_back(0); while(c == '\r' || c == '\n') c = getchar(); while(c != '\r' && c != '\n'){ ++L; hash.push_back(hash[L - 1] * base + c); if(c == '*') word.push_back(L); c = getchar(); } f = word.size(); } ull getHash() {return hash[L];} int getPre() {return f ? word[0] : -1;} int getSuf() {return f ? L - (*--word.end()) : -1;} ull calc(int i , int j) {return i <= 0 || j > L ? -1 : hash[j] - hash[i - 1] * powBase[j - i + 1];} }now[100007]; #define PII pair < int , int > #define st first #define nd second vector < PII > clc;void init(){ powBase[0] = 1; for(int i = 1 ; i <= 1e7 + 3 ; ++i) powBase[i] = powBase[i - 1] * base; }bool match(int a , int b){ int L = now[a].getPre(); if(now[a].calc(1 , L - 1) != now[b].calc(1 , L - 1)) return 0; int R = now[a].getSuf() - 1; if(now[a].calc(now[a].L - R , now[a].L) != now[b].calc(now[b].L - R , now[b].L)) return 0; int p1 = 0 , p2 = L; while(p1 + 1 < now[a].word.size() && p2 + R < now[b].L){ int len = now[a].word[p1 + 1] - now[a].word[p1] - 1; ull num = now[a].calc(now[a].word[p1] + 1 , now[a].word[p1 + 1] - 1); while(1){ if(p2 + len - 1 + R >= now[b].L) return 0; if(now[b].calc(p2 , p2 + len - 1) == num){ ++p1; p2 += len; break; } ++p2; } } return p1 + 1 == now[a].word.size(); }int main(){ #ifndef ONLINE_JUDGE freopen("in","r",stdin); //freopen("out","w",stdout); #endif init(); int T , N; for(scanf("%d" , &T) ; T ; --T){ scanf("%d" , &N); int pre = 0; bool ans = 1; for(int i = 1 ; i <= N ; ++i){ now[i].init(); if(!now[i].f){ if(pre && now[pre].getHash() != now[i].getHash()) ans = 0; pre = i; } } if(ans) if(!pre){ clc.clear(); for(int i = 1 ; i <= N ; ++i) clc.push_back(PII(now[i].getPre() - 1 , i)); sort(clc.begin() , clc.end()); for(int i = 0 ; ans && i < N - 1 ; ++i) if(now[clc[i].nd].calc(1 , clc[i].st) != now[clc[i + 1].nd].calc(1 , clc[i].st)) ans = 0; clc.clear(); for(int i = 1 ; i <= N ; ++i) clc.push_back(PII(now[i].getSuf() , i)); sort(clc.begin() , clc.end()); for(int i = 0 ; ans && i < N - 1 ; ++i){ int a = clc[i].nd , b = clc[i + 1].nd; if(now[a].calc(now[a].L - clc[i].st + 1 , now[a].L) != now[b].calc(now[b].L - clc[i].st + 1 , now[b].L)) ans = 0; } } else for(int i = 1 ; ans && i <= N ; ++i) if(now[i].f) ans = match(i , pre); cout << (ans ? "Y" : "N") << endl; } return 0; }

江南乐（Multi-SG、数论分块）

游戏中每一堆石子都是独立的，所以可以算出石子数量为\(x\)时的SG函数然后求异或。

求SG函数自然要考虑后继状态。如果\(x < F\)显然\(SG_x=0\)，否则它可以有若干个后继。假设我们把这一堆石子分作\(i\)堆，那么就会有\(x \mod i\)堆石子数量为\(\lfloor \frac{x}{i} \rfloor + 1\)的堆，还会有\(i - (x \mod i)\)堆石子数量为\(\lfloor \frac{x}{i} \rfloor\)的堆，它们的\(SG\)函数的异或值就是这个后继的\(SG\)。

可以发现一个重要性质：根据数论分块\(\lfloor \frac{x}{i} \rfloor\)最多只有\(2 \sqrt{x}\)个取值，所以在很多情况下石子数量是一致的。

还可以发现很多堆石子数量相同，\(SG\)值异或会抵消，所以我们只关注\(x \mod i\)和\(i - (x \mod i)\)的奇偶性。而\(x \mod i = x - \lfloor \frac{x}{i} \rfloor i\)，所以在\(\lfloor \frac{x}{i} \rfloor\)不变的情况下这两个数的奇偶性只会有\(2\)种情况。分别取\(i\)和\(i+1\)带入得到两种情况，最后求出所有情况取mex就可以求出\(SG_x\)。

推荐使用下面的求mex方式以避免memset

#include<iostream> #include<cstdio> #include<cctype> #include<algorithm> #include<cstring> #include<cassert> //This code is written by Itst using namespace std;inline int read(){ int a = 0; char c = getchar(); while(!isdigit(c)) c = getchar(); while(isdigit(c)){ a = a * 10 + c - 48; c = getchar(); } return a; }int SG[100007] , mex[100007] , F; bool vis[100007];void solve(int x){ if(vis[x]) return; vis[x] = 1; if(x == 1 || x < F) return; for(int i = 2 ; i <= x ; i = x / (x / i) + 1){ solve(x / i); solve(x / i + 1); } for(int i = 2 ; i <= x ; i = x / (x / i) + 1) for(int j = 0 ; i + j <= x && j <= 1 ; ++j) mex[((x % (i + j)) & 1) * SG[x / (i + j) + 1] ^ (((i + j) - x % (i + j)) & 1) * SG[x / (i + j)]] = x; while(mex[SG[x]] == x) ++SG[x]; }int main(){ #ifndef ONLINE_JUDGE freopen("in","r",stdin); //freopen("out","w",stdout); #endif int T = read(); F = read(); while(T--){ int N = read() , sum = 0; for(int i = 1 ; i <= N ; ++i){ int a = read(); solve(a); sum ^= SG[a]; } printf("%d " , (bool)sum); } return 0; }

画框（分治、KM）

最小乘积最大匹配裸题

对于一个匹配得到的\(\sum A\)和\(\sum B\)将它看做平面上的一个点\((X , Y)\)，那么\(X \times Y\)能够取到最小值的点一定会在所有点构成的下凸包上

先找到\(\sum A\)最小和\(\sum B\)最小的匹配\(L = (x_L , y_L) , R = (x_R , y_R)\)，然后找到与这两个点构成的直线距离最远且在其下方的点\(C\)，如果存在就分治找直线\(LC\)和\(RC\)，直到找到所有点。

找点\(C\)使用叉积，就是要让\(\overrightarrow {LC} \times \overrightarrow {LR}\)要最大。化简一下也就是要让\(x_C(y_R - y_L) - y_C(x_R - x_L)+y_Lx_R-x_Ly_R\)最大。最后两项跟\(C\)无关就不管，而\(x_C = \sum A , y_C = \sum B\)，所以将原匹配中一条边的权值变成\(A \times (y_R - y_L) - B \times (x_R - x_L)\)，再做KM即可。

不排除卡\(O(n^4)\)KM的可能性

#include<iostream> #include<cstdio> #include<cstdlib> #include<ctime> #include<cctype> #include<algorithm> #include<cstring> #include<iomanip> #include<queue> #include<map> #include<set> #include<bitset> #include<stack> #include<vector> #include<cmath> #include<cassert> //This code is written by Itst using namespace std;inline int read(){ int a = 0; char c = getchar(); while(!isdigit(c)) c = getchar(); while(isdigit(c)){ a = a * 10 + c - 48; c = getchar(); } return a; }struct comp{ int x , y; comp(int _x = 0 , int _y = 0) : x(_x) , y(_y){} comp operator -(comp a){return comp(x - a.x , y - a.y);} }; int from[141] , match[141] , pre[141] , ex[141] , need[141]; int A[141][141] , B[141][141] , Edge[141][141] , N , ans; bool vis[141]; queue < int > q;inline bool push(int t , int x){ vis[x] = 1; if(!match[x]){ int u = t , v = x; while(u){ t = match[u]; match[u] = v; match[v] = u; u = pre[u]; v = t; } return 1; } q.push(match[x]); pre[match[x]] = t; return 0; }comp KM(){ int ansA = 0 , ansB = 0; memset(match , 0 , sizeof(match)); memset(ex , 0 , sizeof(ex)); for(int i = 1 ; i <= N ; ++i) for(int j = N + 1 ; j <= N * 2 ; ++j) ex[i] = max(ex[i] , Edge[i][j]); for(int i = 1 ; i <= N ; ++i){ pre[i] = 0; memset(vis , 0 , sizeof(vis)); memset(need , 0x7f , sizeof(need)); while(!q.empty()) q.pop(); q.push(i); bool f = 0; while(!f){ while(!f && !q.empty()){ int t = q.front(); q.pop(); vis[t] = 1; for(int j = N + 1 ; !f && j <= 2 * N ; ++j) if(!vis[j]){ int nd = ex[t] + ex[j] - Edge[t][j]; if(!nd) f = push(t , j); else if(need[j] > nd){ need[j] = nd; from[j] = t; } } } if(f) break; int minN = 2e9; for(int j = N + 1 ; j <= 2 * N ; ++j) if(!vis[j]) minN = min(minN , need[j]); for(int j = 1 ; j <= N ; ++j) if(vis[j]) ex[j] -= minN; for(int j = N + 1 ; j <= 2 * N ; ++j) if(vis[j]) ex[j] += minN; for(int j = N + 1 ; !f && j <= 2 * N ; ++j) if(!vis[j] && !(need[j] -= minN)) f = push(from[j] , j); } } for(int i = 1 ; i <= N ; ++i){ ansA += A[i][match[i]]; ansB += B[i][match[i]]; } return comp(ansA , ansB); }int dot(comp a , comp b){ return a.x * b.y - a.y * b.x; }void solve(comp L , comp R){ for(int i = 1 ; i <= N ; ++i) for(int j = N + 1 ; j <= 2 * N ; ++j) Edge[i][j] = A[i][j] * (R.y - L.y) - B[i][j] * (R.x - L.x) + 20000; comp cur = KM(); if(dot(R - L , cur - L) < 0){ ans = min(ans , cur.x * cur.y); solve(L , cur); solve(cur , R); } }int main(){ #ifndef ONLINE_JUDGE freopen("in","r",stdin); //freopen("out","w",stdout); #endif for(int T = read() ; T ; --T){ N = read(); for(int i = 1 ; i <= N ; ++i) for(int j = N + 1 ; j <= N * 2 ; ++j) A[i][j] = read(); for(int i = 1 ; i <= N ; ++i) for(int j = N + 1 ; j <= N * 2 ; ++j) B[i][j] = read(); for(int i = 1 ; i <= N ; ++i) for(int j = N + 1 ; j <= N * 2 ; ++j) Edge[i][j] = 200 - A[i][j]; comp L = KM(); for(int i = 1 ; i <= N ; ++i) for(int j = N + 1 ; j <= N * 2 ; ++j) Edge[i][j] = 200 - B[i][j]; comp R = KM(); ans = min(L.x * L.y , R.x * R.y); solve(L , R); cout << ans << endl; } return 0; }

米特运输（树形DP、哈希）

既然树的形态是一定的，那么对于每一个点\(x\)，\(val_1\)会是\(val_x\)的\(bon_x\)倍，\(bon_x\)是一个定值且可以树形DP出来

对于\(val_x \times bon_x\)相同的点，把\(val_1\)改成\(val_x \times bon_x\)之后这一些点都不需要重建

所以需要求的就是\(val_x \times bon_x\)相同的点中点数最多的一组。\(val_x \times bon_x\)会比较大，Hash存一下就可以了。

道路堵塞（SPFA、乱搞）

正解真是信仰算法（或许还有更正确的算法吧，但是我肯定是不会的了）

首先一个结论：如果某一条\(1\)到\(N\)的最短路上被截断了一条边，那么剩余图中的最短路一定是\(1 \rightarrow x \rightarrow y \rightarrow N\)，其中\(1 \rightarrow x\)、\(y \rightarrow N\)是原最短路的子路径，而\(x \rightarrow y\)与原最短路无交。

暴力就是每一次删一条边然后暴力\(SPFA\)一遍，但这样显然是过不了的。考虑优化这个暴力算法。

首先把所有重要边全部ban掉跑一边\(SPFA\)，然后从起点到终点一条一条地恢复边，每恢复一条边也跑一边\(SPFA\)。每一次\(SPFA\)如果跑出了一条\(x \rightarrow y\)的路，其中\(x\)是即将被恢复的边的起点，\(y\)是最短路上的另一个点，就将\(1 \rightarrow x \rightarrow y \rightarrow N\)的边加入到一个堆中。

注意到对于\(1 \rightarrow x \rightarrow y \rightarrow N\)的边，ban掉最短路上\(x \rightarrow a_1 \rightarrow a_2 ... a_k \rightarrow y\)的任意一条边，这一条路径都有可能成为最短路。所以这个堆中的路径可以重复使用，直到被ban的边在\(y\)之后，这条边就没有用了，直接pop掉。当堆中没有边的时候就是\(-1\)，否则当前被ban的边的答案就是堆顶的路径长度。

值得注意的是\(SPFA\)的从起点开始的最短路数组\(dis[]\)不需要清空，因为在不断恢复边的过程中\(dis[]\)一定是递减的。

#include<iostream> #include<cstdio> #include<cctype> #include<algorithm> #include<cstring> #include<queue> #include<vector> #include<cassert> //This code is written by Itst using namespace std;inline int read(){ int a = 0; char c = getchar(); while(!isdigit(c)) c = getchar(); while(isdigit(c)){ a = a * 10 + c - 48; c = getchar(); } return a; }#define PII pair < int , int > #define st first #define nd second const int MAXN = 1e5 + 7; struct Edge{ int end , upEd , w; }Ed[MAXN << 1]; priority_queue < PII > q1; queue < int > q; int head[MAXN] , dis[MAXN] , pre[MAXN] , suf[MAXN] , sp[MAXN] , nd[MAXN] , ind[MAXN] , N , M , L , cntEd; bool vis[MAXN] , ban[MAXN << 1];inline void addEd(int a , int b , int c){ Ed[++cntEd].end = b; Ed[cntEd].upEd = head[a]; Ed[cntEd].w = c; head[a] = cntEd; }void SPFA(int id){ dis[nd[id]] = pre[id]; q.push(nd[id]); while(!q.empty()){ int t = q.front(); q.pop(); vis[t] = 0; for(int i = head[t] ; i ; i = Ed[i].upEd) if(!ban[i] && dis[Ed[i].end] > dis[t] + Ed[i].w){ dis[Ed[i].end] = dis[t] + Ed[i].w; if(ind[Ed[i].end]) q1.push(PII(-(suf[ind[Ed[i].end]] + dis[Ed[i].end]) , ind[Ed[i].end])); if(!vis[Ed[i].end]){ vis[Ed[i].end] = 1; q.push(Ed[i].end); } } } ban[sp[id]] = 0; }int main(){ #ifndef ONLINE_JUDGE freopen("in","r",stdin); //freopen("out","w",stdout); #endif memset(dis , 0x7f , sizeof(dis)); N = read(); M = read(); L = read(); for(int i = 1 ; i <= M ; ++i){ int a = read() , b = read() , c = read(); addEd(a , b , c); } ind[1] = nd[1] = 1; for(int i = 1 ; i <= L ; ++i){ sp[i] = read(); ban[sp[i]] = 1; nd[i + 1] = Ed[sp[i]].end; } for(int i = 2 ; i <= L + 1 ; ++i){ ind[nd[i]] = i; pre[i] = pre[i - 1] + Ed[sp[i - 1]].w; } for(int i = L ; i ; --i) suf[i] = suf[i + 1] + Ed[sp[i]].w; for(int i = 1 ; i <= L ; ++i){ SPFA(i); while(!q1.empty() && q1.top().nd <= i) q1.pop(); printf("%d\n" , q1.empty() ? -1 : -q1.top().st); } return 0; }