AC自动机
2021杭电多校第八场1009
题意：在文本串中查询每个模式串出现的次数，但是不可重叠。例：aba在abababa中出现了两次。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 |
#include <bits/stdc++.h> using namespace std; typedef long long LL; const int N = 600009; class AC { public: void init() { for(int i = 0; i < N; i++) { for(int j = 0; j < 26; j++) trie[i][j] = 0; fail[i] = ans[i] = count[i] = len[i] = id[i] = 0; p[i] = -1; } cnt = 0; } int insert(char c[]) { int n = strlen(c), root = 0; for(int i = 0; i < n; i++) { int k = c[i] - 'a'; if(!trie[root][k]) trie[root][k] = ++cnt; root = trie[root][k]; len[root] = i + 1; } count[root]++; return root; } void getId(int i, char c[]) { id[i] = insert(c); } void getFail() { queue<int> q; for(int i = 0; i < 26; i++) { if(!trie[0][i]) continue; fail[trie[0][i]] = 0; q.push(trie[0][i]); } while(!q.empty()) { int now = q.front(); q.pop(); for(int i = 0; i < 26; i++) { if(!trie[now][i]) continue; int u = fail[now], v = trie[now][i]; while(u && !trie[u][i]) u = fail[u]; fail[v] = trie[u][i]; q.push(v); } } } void Query(char c[]) { int n = strlen(c); for(int i = 0, j = 0; i < n; i++) { int k = c[i] - 'a'; while(j && !trie[j][k]) j = fail[j]; j = trie[j][k]; for(int now = j; now; now = fail[now]) { if(p[now]==-1 || i-p[now]>=len[now]) ans[now]++, p[now] = i; } } } int getAns(int x) { return ans[id[x]]; } private: int trie[N][26], fail[N], cnt, ans[N]; int len[N], count[N], p[N], id[N]; }; AC ans; int T, n; char text[N], mode[N]; int main(int argc, char const *argv[]) { #ifndef ONLINE_JUDGE freopen("input.in", "r", stdin); freopen("output.out", "w", stdout); #endif scanf("%d", &T); while(T--) { ans.init(); scanf("%s", text); scanf("%d", &n); for(int i = 1; i <= n; i++) scanf("%s", mode), ans.getId(i, mode); ans.getFail(); ans.Query(text); for(int i = 1; i <= n; i++) printf("%d\n", ans.getAns(i)); } return 0; } |
KMP
双Hash
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 |
#include <bits/stdc++.h> #define MP(a, b) make_pair(a, b) using namespace std; typedef long long LL; typedef long long ULL; typedef pair<ULL, ULL> Pair; const int N = 400009; const ULL P = 233; const ULL Mod1 = 1e9 + 7; const ULL Mod2 = 1e9 + 9; int n, m; char c[N]; ULL p[N], _p[N]; Pair _hash[N]; map<Pair, ULL> f; vector<Pair> g; template<typename T> T read() { T num = 0; char c; bool flag = 0; while((c=getchar())==' ' || c=='\n' || c=='\r'); if(c=='-') flag = 1; else num = c - '0'; while(isdigit(c=getchar())) num = num * 10 + c - '0'; return flag ? -num : num; } Pair getHash(int l, int r) { ULL tmp1 = (_hash[r].first - _hash[l - 1].first * p[r - l + 1] % Mod1 + Mod1) % Mod1; ULL tmp2 = (_hash[r].second - _hash[l - 1].second * _p[r - l + 1] % Mod2 + Mod2) % Mod2; return MP(tmp1, tmp2); } int main() { #ifndef ONLINE_JUDGE freopen("input.in", "r", stdin); freopen("output.out", "w", stdout); #endif cin >> n; p[0] = 1; _p[0] = 1; for (int i = 1; i <= 400000; i++) p[i] = (p[i - 1] * P) % Mod1, _p[i] = (_p[i - 1] * P) % Mod2; for (int i = 1; i <= n; i++) { cin >> c+1; m = strlen(c + 1); for (int j = 1; j <= m; j++) _hash[j].first = (_hash[j - 1].first * P % Mod1 + c[j]) % Mod1, _hash[j].second = (_hash[j - 1].second * P % Mod2 + c[j]) % Mod2; f[_hash[m]]++; for (int j = 1; j + j < m; j++) if(getHash(1, j) == getHash(m - j + 1, m)) g.push_back(getHash(j + 1, m - j)); } ULL ans = 0; for (auto i : g) ans += f[i]; for (auto i : f) ans += i.second * (i.second - 1) / 2; cout << ans << '\n'; return 0; } |
Manacher
求最长回文串的长度
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 |
#include <bits/stdc++.h> using namespace std; typedef long long LL; const int N = 300009; int T, n, m, p[N], len1, len2; char s[N], str[N]; template<typename T> T read() { T num = 0; char c; bool flag = 0; while((c=getchar())==' ' || c=='\n' || c=='\r'); if(c=='-') flag = 1; else num = c - '0'; while(isdigit(c=getchar())) num = num * 10 + c - '0'; return flag ? -num : num; } void init() { str[0] = '$'; str[1] = '#'; int id = 0, mx = 0; for (int i = 0; i < len1; i++) { str[2 * i + 2] = s[i]; str[2 * i + 3] = '#'; } len2 = 2 * len1 + 2; str[len2] = '*'; } void manacher() { int id = 0, mx = 0; for (int i = 1; i < len2; i++) { if(mx>i) p[i] = min(p[2 * id - i], mx - i); else p[i] = 1; for (; str[i + p[i]] == str[i - p[i]]; p[i]++); if(i+p[i]>mx) mx = i + p[i], id = i; } } int main(int argc, char const *argv[]) { #ifndef ONLINE_JUDGE freopen("input.in", "r", stdin); freopen("output.out", "w", stdout); #endif while((scanf("%s", s))!=EOF) { len1 = strlen(s); init(); manacher(); int ans = 0; for (int i = 0; i < len2; i++) ans = max(ans, p[i]); printf("%d\n", ans - 1); } return 0; } |
求二维坐标点的最短距离
POJ3714 Raid
题意：有n个核电站和n个特工，位置为二维坐标，问距离核电站最近的特工距核电站多远。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 |
#include <bits/stdc++.h> using namespace std; typedef long long LL; typedef double DB; const int N = 100009; const DB INF = 2e18; struct Node { Node(){} Node(DB x, DB y, int mark):x(x), y(y), mark(mark){} DB x, y; int mark; bool operator < (const Node&a) const { if(x==a.x) return y < a.y; return x < a.x; } }; Node g[2*N], tmp[2*N]; int T, n, m; bool cmp(const Node&a, const Node&b) { return a.y < b.y; } DB dist(Node a, Node b) { if(a.mark==b.mark) return INF; DB dx = a.x - b.x; DB dy = a.y - b.y; return sqrt(dx*dx+dy*dy); } DB dfs(int l, int r) { if(l>=r) return INF; if(r-l==1) return dist(g[l], g[r]); int mid = l + r >> 1; DB lval = dfs(l, mid); DB rval = dfs(mid, r); DB ans = min(lval, rval); int cnt = 0; for(int i = l; i <= r; i++) if(fabs(g[i].x-g[mid].x)<ans) tmp[++cnt] = g[i]; sort(tmp+1, tmp+cnt+1, cmp); for(int i = 1; i < cnt; i++) for(int j = i+1; (j<=cnt) && (tmp[j].y-tmp[i].y<ans); j++) ans = min(ans, dist(tmp[i], tmp[j])); return ans; } int main() { scanf("%d", &T); while(T--) { scanf("%d", &n); for(int i = 1; i <= n; i++) { DB x, y; scanf("%lf%lf", &x, &y); g[i] = Node(x, y, 0); } for(int i = 1; i <= n; i++) { DB x, y; scanf("%lf%lf", &x, &y); g[i+n] = Node(x, y, 1); } sort(g+1, g+2*n+1); DB ans = dfs(1, 2*n); printf("%.3lf\n", ans); } return 0; } |
向量
向量四则运算，点积，叉积，夹角等
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 |
#include <bits/stdc++.h> using namespace std; typedef long long LL; typedef double DB; const int N = 1009; const DB PI = acos(-1); struct Vector { Vector(){} Vector(DB x, DB y):x(x), y(y){} DB x, y; Vector operator+(Vector a) { return Vector(x + a.x, y + a.y); } Vector operator-(Vector a) { return Vector(x - a.x, y - a.y); } Vector operator*(DB a) { return Vector(x * a, y * a); } Vector operator/(DB a) { return Vector(x / a, y / a); } DB Dot(Vector a) { return x * a.x + y * a.y; } DB Length() { return sqrt(this->Dot(*this)); } DB Cross(Vector a) { return x * a.y - y * a.x; } // 向量旋转，rad为逆时针旋转的角，弧度制 void Rotate(DB rad) { *this = Vector(x * cos(rad) - y * sin(rad), x * sin(rad) + y * cos(rad)); } // 单位法线 Vector Normal() { return Vector(-y / this->Length(), x / this->Length()); } }; DB Angle(Vector a, Vector b) { return acos(a.Dot(b) / a.Length() / b.Length()); } Vector toVector(DB x_1, DB y_1, DB x_2, DB y_2) { return Vector(x_2 - x_1, y_2 - y_1); } // 叉积求三角形面积 Area2为三角形面积2倍，按照逆时针顺序给出三个点 DB Area2(DB x_1, DB y_1, DB x_2, DB y_2, DB x_3, DB y_3) { return toVector(x_1, y_1, x_2, y_2).Cross(toVector(x_1, y_1, x_3, y_3)); } // 逆时针顺序给出三个点 DB Area(DB x_1, DB y_1, DB x_2, DB y_2, DB x_3, DB y_3) { return sqrt(Area2(x_1, y_1, x_2, y_2, x_3, y_3)); } // 判断向量b,c是否在a的两侧 int notSameSide(Vector a, Vector b, Vector c) { return a.Cross(b) * a.Cross(c) <= 0; } // 判断平行 bool Parallel(Vector a, Vector b) { return a.Cross(b) == 0; } typedef Vector Point; int n, m; Point g[N][2], p[N][2]; bool f[N]; int main() { #ifndef ONLINE_JUDGE freopen("input.in", "r", stdin); freopen("output.out", "w", stdout); #endif DB x, y; scanf("%d%d", &n, &m); scanf("%lf%lf", &x, &y); for (int i = 1; i <= n; i++) scanf("%lf%lf%lf%lf", &g[i][0].x, &g[i][0].y, &g[i][1].x, &g[i][1].y); for (int i = 1; i <= m; i++) scanf("%lf%lf%lf%lf", &p[i][0].x, &p[i][0].y, &p[i][1].x, &p[i][1].y); for (int i = 1; i <= m; i++) { Vector vec1 = toVector(p[i][0].x, p[i][0].y, p[i][1].x, p[i][1].y); Vector vec2 = toVector(p[i][0].x, p[i][0].y, x, y); if(vec2.Length() > vec1.Length() || vec1.Dot(vec2) < 0) continue; bool flag = 0; for (int j = 1; j <= n; j++) { Vector a = toVector(p[i][0].x, p[i][0].y, g[i][0].x, g[i][0].y); Vector b = toVector(p[i][0].x, p[i][0].y, g[i][1].x, g[i][1].y); Vector c = toVector(g[i][0].x, g[i][0].y, p[i][0].x, p[i][0].y); Vector d = toVector(g[i][0].x, g[i][0].y, p[i][1].x, p[i][1].y); Vector _p = toVector(p[i][0].x, p[i][0].y, p[i][1].x, p[i][1].y); Vector _q = toVector(g[i][0].x, g[i][0].y, g[i][1].x, g[i][1].y); if(notSameSide(_p, a, b) && notSameSide(_q, c, d)) { flag = 1; break; } } if(flag) continue; for (int j = 1; j <= m; j++) { if(i==j) continue; Vector a = toVector(p[j][0].x, p[j][0].y, p[i][0].x, p[i][0].y); Vector b = toVector(p[j][0].x, p[j][0].y, p[i][1].x, p[i][1].y); Vector c = Vector(0, 0) - a; Vector d = Vector(0, 0) - b; if(a.Cross(b) == 0 && c.Dot(d) < 0) { flag = 1; break; } } if(flag) continue; f[i] = 1; } for (int i = 1; i <= m; i++) { if(f[i]) puts("visible"); else puts("not visible"); } return 0; } |
求圆并
题意：求圆并起来的面积与圆的面积和的比值
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 |
#include <bits/stdc++.h> using namespace std; typedef long long LL; const double PI = acos(-1); const double EPS = 1e-8; const int N = 2009; int sgn(double x) { return (x > EPS) - (x < -EPS); } struct Point { Point() {} Point(double x, double y) : x(x), y(y) {} double x, y; double angle() { return atan2(y, x); } Point operator + (const Point&rhs) const { return Point(x + rhs.x, y + rhs.y); } Point operator - (const Point&rhs) const { return Point(x - rhs.x, y - rhs.y); } Point operator * (double t) const { return Point(x * t, y * t); } Point operator / (double t) const { return Point(x / t, y / t); } double length() const { return sqrt(x * x + y * y); } Point unit() const { double l = length(); return Point(x / l, y / l); } }; double cross(const Point &a, const Point &b) { return a.x * b.y - a.y * b.x; } double dist(const Point &p1, const Point &p2) { return (p1 - p2).length(); } // 弧度制 Point rotate(const Point &p, double angle, const Point &o = Point(0, 0)) { Point t = p - o; double x = t.x * cos(angle) - t.y * sin(angle); double y = t.y * cos(angle) + t.x * sin(angle); return Point(x, y) + o; } struct Region { Region() {} Region(double st, double ed) : st(st), ed(ed) {} double st, ed; bool operator < (const Region &rhs) const { if(sgn(st - rhs.st)) return st < rhs.st; return ed < rhs.ed; } }; struct Circle { Circle() {} Circle(Point c, double r) : c(c), r(r) {} Circle(double x, double y, double r) : c(Point(x, y)), r(r) {} Point c; double r; vector<Region> reg; void add(const Region &r) { reg.push_back(r); } bool contain(const Circle &cir) const { return sgn(dist(cir.c, c) + cir.r - r) <= 0; } bool intersect(const Circle &cir) const { return sgn(dist(cir.c, c) - cir.r - r) < 0; } }; double sqr(double x) { return x * x; } void intersection(const Circle &cir1, const Circle &cir2, Point &p1, Point &p2) { double l = dist(cir1.c, cir2.c); double d = (sqr(l) - sqr(cir2.r) + sqr(cir1.r)) / (2 * l); double d2 = sqrt(sqr(cir1.r) - sqr(d)); Point mid = cir1.c + (cir2.c - cir1.c).unit() * d; Point v = rotate(cir2.c - cir1.c, PI / 2).unit() * d2; p1 = mid + v, p2 = mid - v; } Point calc(const Circle &cir, double angle) { Point p = Point(cir.c.x + cir.r, cir.c.y); return rotate(p, angle, cir.c); } Circle cir[N]; bool del[N]; int n; double solve() { double ans = 0; memset(del, 0, sizeof(del)); for (int i = 0; i < n; i++) cir[i].reg.clear(); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) if(!del[j]) { if(i == j) continue; if(cir[j].contain(cir[i])) { del[i] = true; break; } } } for (int i = 0; i < n; i++) if(!del[i]) { Circle &mc = cir[i]; Point p1, p2; bool flag = false; for (int j = 0; j < n; j++) if(!del[j]) { if(i == j) continue; if(!mc.intersect(cir[j])) continue; flag = true; intersection(mc, cir[j], p1, p2); double rs = (p2 - mc.c).angle(), rt = (p1 - mc.c).angle(); if(sgn(rs) < 0) rs += 2.0 * PI; if(sgn(rt) < 0) rt += 2.0 * PI; if(sgn(rs - rt) > 0) mc.add(Region(rs, PI * 2.0)), mc.add(Region(0, rt)); else mc.add(Region(rs, rt)); } if(!flag) { ans += PI * sqr(mc.r); continue; } sort(mc.reg.begin(), mc.reg.end()); int cnt = 1; for (int j = 1; j < int(mc.reg.size()); j++) { if(sgn(mc.reg[cnt - 1].ed - mc.reg[j].st) >= 0) { mc.reg[cnt - 1].ed = max(mc.reg[cnt - 1].ed, mc.reg[j].ed); } else mc.reg[cnt++] = mc.reg[j]; } mc.add(Region()); mc.reg[cnt] = mc.reg[0]; for (int j = 0; j < cnt; j++) { p1 = calc(mc, mc.reg[j].ed); p2 = calc(mc, mc.reg[j + 1].st); ans += cross(p1, p2) / 2; double angle = mc.reg[j + 1].st - mc.reg[j].ed; if(sgn(angle) < 0) angle += 2.0 * PI; ans += 0.5 * sqr(mc.r) * (angle - sin(angle)); } } return ans; } Point p[N]; int main() { #ifndef ONLINE_JUDGE freopen("input.in", "r", stdin); freopen("output.out", "w", stdout); #endif scanf("%d", &n); for (int i = 0; i < n; i++) { double x, y; scanf("%lf%lf", &x, &y); p[i] = Point(x, y); } int q; scanf("%d", &q); for (int i = 0; i < q; i++) { double r, S = 0; scanf("%lf", &r); S = 1.0 * n * PI * r * r; for (int j = 0; j < n; j++) cir[j] = Circle(p[j], r); printf("%.15lf\n", solve() / S); } return 0; } |
FFT
多项式乘法
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 |
#include <bits/stdc++.h> using namespace std; typedef long long LL; const int N = 4000009; const double PI = acos(-1.0); struct Complex { Complex() {} Complex(double r, double i) : r(r), i(i) {} double r, i; Complex operator + (const Complex &a) const { return Complex(r + a.r, i + a.i); } Complex operator - (const Complex &a) const { return Complex(r - a.r, i - a.i); } Complex operator * (const Complex &a) const { return Complex(r * a.r - i * a.i, r * a.i + i * a.r); } double real() { return r; } double image() { return i; } }; int T, n, m, len, rev[N]; Complex a[N], b[N]; template<typename T> T read() { T num = 0; char c; bool flag = 0; while((c=getchar())==' ' || c=='\n' || c=='\r'); if(c=='-') flag = 1; else num = c - '0'; while(isdigit(c=getchar())) num = num * 10 + c - '0'; return flag ? -num : num; } void init(int length) { int tmp = 0; len = 1; while(len <= length) len <<= 1, tmp++; for (int i = 0; i < len; i++) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (tmp - 1)); } void FFT(Complex *A, int inv) { for (int i = 0; i < len; i++) if(i < rev[i]) swap(A[i], A[rev[i]]); for (int i = 1; i < len; i <<= 1) { Complex tmp = Complex(cos(PI / i), inv * sin(PI / i)); for (int j = 0; j < len; j += (i << 1)) { Complex omega = Complex(1, 0); for (int k = 0; k < i; k++, omega = omega * tmp) { Complex x = A[j + k], y = omega * A[j + k + i]; A[j + k] = x + y, A[j + k + i] = x - y; } } } } int main(int argc, char const *argv[]) { #ifndef ONLINE_JUDGE freopen("input.in", "r", stdin); freopen("output.out", "w", stdout); #endif n = read<int>(); m = read<int>(); for (int i = 0; i <= n; i++) { int r = read<int>(); a[i] = Complex(1.0 * r, 0); } for (int i = 0; i <= m; i++) { int r = read<int>(); b[i] = Complex(1.0 * r, 0); } init(n + m); FFT(a, 1), FFT(b, 1); for (int i = 0; i < len; i++) a[i] = a[i] * b[i]; FFT(a, -1); for (int i = 0; i <= n + m; i++) printf("%d%c", int(a[i].r / len + 0.5), i == n + m ? '\n' : ' '); return 0; } |
组合数学
Meisell-Lehmer（小于等于n的素数个数）
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 |
#include<cmath> #include<cstdio> #include<iostream> #define IL inline #define RG register using namespace std; typedef long long LL; const int N=5000005; const int M=7; const int PM=2*3*5*7*11*13*17; int p[N],pi[N]; int phi[PM+1][M+1],sz[M+1]; LL n; bool f[N]; IL void getprime() { for(RG int i=2;i<N;i++) { if(!f[i]) p[++p[0]]=i; pi[i]=p[0]; for(RG int j=1;p[j]*i<N;j++) { f[p[j]*i]=1; if(i%p[j]==0) break; } } } IL void init() { getprime(); sz[0]=1; for(RG int i=0;i<=PM;i++) phi[i][0]=i; for(RG int i=1;i<=M;i++) { sz[i]=p[i]*sz[i-1]; for(RG int j=1;j<=PM;j++) phi[j][i]=phi[j][i-1]-phi[j/p[i]][i-1]; } } IL int sqrt2(LL x) { LL r=(LL)sqrt(x-0.1); while(r*r<=x) r++; return (int)(r-1); } IL int sqrt3(LL x) { LL r=(LL)cbrt(x-0.1); while(r*r*r<=x) r++; return (int)(r-1); } IL LL getphi(LL x,int s) { if(s==0) return x; if(s<=M) return phi[x%sz[s]][s]+(x/sz[s])*phi[sz[s]][s]; if(x<=p[s]*p[s]*p[s]&&x<N) { int s2x=pi[sqrt2(x)]; LL ans=pi[x]-(s2x+s-2)*(s2x-s+1)/2; for(RG int i=s+1;i<=s2x;i++) ans+=pi[x/p[i]]; return ans; } return getphi(x,s-1)-getphi(x/p[s],s-1); } IL LL getpi(LL x) { if(x<N) return pi[x]; LL ans=getphi(x,pi[sqrt3(3)])+pi[sqrt3(x)]-1; for(RG int i=pi[sqrt3(x)]+1,ed=pi[sqrt2(x)];i<=ed;i++) ans-=getpi(x/p[i])-i+1; return ans; } LL MeiLeh(LL x) { if(x<N) return pi[x]; int a=(int)MeiLeh(sqrt2(sqrt2(x))); int b=(int)MeiLeh(sqrt2(x)); int c=(int)MeiLeh(sqrt3(x)); LL sum=getphi(x,a)+(LL)(b+a-2)*(b-a+1)/2; for(int i=a+1;i<=b;i++) { LL w=x/p[i]; sum-=MeiLeh(w); if(i>c) continue; LL lim=MeiLeh(sqrt2(w)); for(int j=i;j<=lim;j++) sum-=MeiLeh(w/p[j])-(j-1); } return sum; } int main() { init(); while((scanf("%lld",&n))!=EOF) printf("%lld\n",MeiLeh(n)); return 0; } |
Tarjan
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 |
#include <bits/stdc++.h> using namespace std; typedef long long LL; const int N = 100009; struct Edge { Edge() {} Edge(int x, int y) : x(x), y(y) {} int x, y; } edge[N]; int T, n, m, q, cnt, scc_cnt, max_scc; int dfn[N], low[N], scc_id[N]; vector<int> g[N]; bool vis[N]; stack<int> t; void init() { memset(dfn, 0, sizeof(dfn)); memset(low, 0, sizeof(low)); memset(scc_id, 0, sizeof(scc_id)); memset(vis, 0, sizeof(vis)); cnt = 0; scc_cnt = 0; max_scc = 0; } void tarjan(int x) { dfn[x] = low[x] = ++cnt; vis[x] = 1; t.push(x); for(auto i:g[x]) { if(!dfn[i]) { tarjan(i); low[x] = min(low[x], low[i]); } else if(vis[i]) low[x] = min(low[x], dfn[i]); } if(dfn[x] == low[x]) { int now, count = 0; ++scc_cnt; do { now = t.top(); t.pop(); scc_id[now] = scc_cnt; vis[now] = 0; ++count; } while (now != x); max_scc = max(max_scc, count); } } int main(int argc, char const *argv[]) { #ifndef ONLINE_JUDGE freopen("input.in", "r", stdin); freopen("output.out", "w", stdout); #endif scanf("%d", &T); while(T--) { init(); scanf("%d%d%d", &n, &m, &q); for (int i = 1; i <= n; i++) g[i].clear(); for (int i = 1; i <= m; i++) { scanf("%d%d", &edge[i].x, &edge[i].y); g[edge[i].x].push_back(edge[i].y); } for (int i = 1; i <= n; i++) if(!dfn[i]) tarjan(i); int tmp = max_scc; while(q--) { int k; scanf("%d", &k); if(scc_id[edge[k].x] == scc_id[edge[k].y]) { printf("%d\n", tmp); continue; } g[edge[k].y].push_back(edge[k].x); init(); for (int i = 1; i <= n; i++) { if(!dfn[i]) tarjan(i); } printf("%d\n", max(tmp, max_scc)); g[edge[k].y].pop_back(); init(); for (int i = 1; i <= n; i++) { if(!dfn[i]) tarjan(i); } } } return 0; } |
树链剖分
HDU 3966 Aragorn's Story
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 |
#include <bits/stdc++.h> using namespace std; typedef long long LL; const int N = 50009; class SegmentTree { #define lc rt << 1 #define rc rt << 1 | 1 #define mid ((l + r) >> 1) public: void build(int l, int r, int rt) { t[rt].val = t[rt].lzy = 0; if(l >= r) return; build(l, mid, lc); build(mid + 1, r, rc); } void push_down(int rt, int l, int r) { t[lc].lzy += t[rt].lzy; t[rc].lzy += t[rt].lzy; t[lc].val += (mid - l + 1) * t[rt].lzy; t[rc].val += (r - mid) * t[rt].lzy; t[rt].lzy = 0; } void push_up(int rt) { t[rt].val = t[lc].val + t[rc].val; } void update(int l, int r, int rt, int L, int R, int v) { if(r < L || l > R || l > r || L > R) return; if(L <= l && r <= R) { t[rt].lzy += v; t[rt].val += v * (r - l + 1); return; } push_down(rt, l, r); update(l, mid, lc, L, R, v); update(mid + 1, r, rc, L, R, v); push_up(rt); } int query(int l, int r, int rt, int L, int R) { if(r < L || l > R || l > r || L > R) return 0; if(L <= l && r <= R) return t[rt].val; push_down(rt, l, r); int lval = query(l, mid, lc, L, R); int rval = query(mid + 1, r, rc, L, R); push_up(rt); return lval + rval; } private: struct Node { Node() {} Node(int val, int lzy) : val(val), lzy(lzy) {} int val, lzy; }; Node t[4 * N]; } t; int T, n, m, k, a[N]; vector<int> g[N]; int deep[N], son[N], size[N], fa[N]; int top[N], id[N], cnt, sub_t[N]; void init() { cnt = 0; for (int i = 1; i <= n; i++) g[i].clear(), fa[i] = 0, top[i] = 0, id[i] = 0, sub_t[i] = 0; } void dfs1(int x, int dep) { deep[x] = dep; size[x] = 1; son[x] = 0; for (auto i : g[x]) { if(i == fa[x]) continue; fa[i] = x; dfs1(i, dep + 1); size[x] += size[i]; if(size[i] > size[son[x]]) son[x] = i; } sub_t[x] = cnt; return; } void dfs2(int x, int tp) { id[x] = ++cnt; top[x] = tp; if(son[x]) dfs2(son[x], tp); for (auto i : g[x]) { if(i == fa[x] || i == son[x]) continue; dfs2(i, i); } } void update(int x, int y, int z) { while (top[x] != top[y]) { if(deep[top[x]] > deep[top[y]]) swap(x, y); t.update(1, cnt, 1, id[top[y]], id[y], z); y = fa[top[y]]; } if(deep[x] > deep[y]) swap(x, y); t.update(1, cnt, 1, id[x], id[y], z); return; } int query(int x, int y) { int ans = 0; while (top[x] != top[y]) { if(deep[top[x]] > deep[top[y]]) swap(x, y); ans += t.query(1, cnt, 1, id[top[y]], id[y]); y = fa[top[y]]; } if(deep[x] > deep[y]) swap(x, y); ans += t.query(1, cnt, 1, id[x], id[y]); return ans; } int main(int argc, char const *argv[]) { #ifndef ONLINE_JUDGE freopen("input.in", "r", stdin); freopen("output.out", "w", stdout); #endif while ((scanf("%d%d%d", &n, &m, &k)) != EOF) { init(); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); for (int i = 1; i <= m; i++) { int u, v, w; scanf("%d%d", &u, &v); g[u].push_back(v); g[v].push_back(u); } dfs1(1, 1); dfs2(1, 1); t.build(1, cnt, 1); for (int i = 1; i <= n; i++) t.update(1, cnt, 1, id[i], id[i], a[i]); for (int i = 1; i <= k; i++) { char op[10]; scanf("%s", op); if(op[0] == 'I') { int x, y, z; scanf("%d%d%d", &x, &y, &z); update(x, y, z); } else if(op[0] == 'D') { int x, y, z; scanf("%d%d%d", &x, &y, &z); update(x, y, -z); } else { int x; scanf("%d", &x); printf("%d\n", query(x, x)); } } } return 0; } |
高斯消元
异或矩阵：2020ICPC济南-A
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 |
#include <bits/stdc++.h> using namespace std; typedef long long LL; const int N = 209; const LL Mod(998244353LL); int T, n, m, A[N][N], B[N][N]; bitset<N> a[N]; template<typename T> T read() { T num = 0; char c; bool flag = 0; while((c=getchar())==' ' || c=='\n' || c=='\r'); if(c=='-') flag = 1; else num = c - '0'; while(isdigit(c=getchar())) num = num * 10 + c - '0'; return flag ? -num : num; } LL ksm(LL x, LL y) { LL ans = 1; while(y) { if(y&1) ans = (ans * x) % Mod; y >>= 1LL; x = (x * x) % Mod; } return ans % Mod; } LL gauss() { int tmp = 0; for (int r = 1, c = 1; r <= n && c <= n; r++, c++) { int i = r; for (; i <= n; i++) if(a[i][c]) break; if(i > n) { --r; ++tmp; continue; } swap(a[r], a[i]); for (i = r + 1; i <= n; i++) if(a[i][c]) a[i] ^= a[r]; } return ksm(2, tmp) % Mod; } int main(int argc, char const *argv[]) { #ifndef ONLINE_JUDGE freopen("input.in", "r", stdin); freopen("output.out", "w", stdout); #endif n = read<int>(); for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) A[i][j] = read<int>(); for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) B[i][j] = read<int>(); LL ans = 1; for (int j = 1; j <= n; j++) { for (int i = 1; i <= n; i++) for (int k = 1; k <= n; k++) a[i][k] = A[i][k]; for (int i = 1; i <= n; i++) a[i][i] = a[i][i] ^ B[i][j]; (ans *= gauss()) %= Mod; } printf("%lld\n", ans); return 0; } |
二分图
网络流
朱刘算法
k短路
三分
数位DP
主席树
求区间中小于等于k的数的个数
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 |
#include <bits/stdc++.h> using namespace std; typedef long long LL; const int N = 100009; int T, n, m, a[N], b[N]; class HJT { #define mid ((l + r) >> 1) #define left_tree l, mid #define right_tree mid + 1, r public: void clear() { tot = 0; memset(t, 0, sizeof(t)); } void update(int l, int r, int &rt, int p) { t[++tot] = t[rt]; rt = tot; ++t[rt].sum; if(l>=r) return; if(mid>=p) update(left_tree, t[rt].lc, p); else update(right_tree, t[rt].rc, p); } int query(int l, int r, int l_rt, int r_rt, int v) { if(b[r] <= v) return t[r_rt].sum - t[l_rt].sum; else if(b[l] > v) return 0; int x = b[mid]; if(b[mid] >= v) return query(left_tree, t[l_rt].lc, t[r_rt].lc, v); else return t[t[r_rt].lc].sum - t[t[l_rt].lc].sum + query(right_tree, t[l_rt].rc, t[r_rt].rc, v); } private: struct Node { int sum, lc, rc; } t[8 * N]; int tot; }; HJT t; int rt[N]; template<typename T> T read() { T num = 0; char c; bool flag = 0; while((c=getchar())==' ' || c=='\n' || c=='\r'); if(c=='-') flag = 1; else num = c - '0'; while(isdigit(c=getchar())) num = num * 10 + c - '0'; return flag ? -num : num; } void solve() { t.clear(); n = read<int>(); m = read<int>(); for (int i = 1; i <= n; i++) b[i] = a[i] = read<int>(); sort(b + 1, b + n + 1); int Size = unique(b + 1, b + n + 1) - b - 1; for (int i = 1; i <= n; i++) { int k = lower_bound(b + 1, b + Size + 1, a[i]) - b; rt[i] = rt[i - 1]; t.update(1, Size, rt[i], k); } for (int i = 1; i <= m; i++) { int l = read<int>(); int r = read<int>(); int x = read<int>(); int y = read<int>(); int sum1 = t.query(1, Size, rt[l - 1], rt[r], x - 1); int sum2 = t.query(1, Size, rt[l - 1], rt[r], y); printf("%d\n", sum2 - sum1); } } int main(int argc, char const *argv[]) { #ifndef ONLINE_JUDGE freopen("input.in", "r", stdin); freopen("output.out", "w", stdout); #endif T = read<int>(); for (int i = 1; i <= T; i++) { printf("Case #%d:\n", i); solve(); } return 0; } |
叨叨几句... NOTHING