Protein

OIer

2.8万

Protein
4小时前

代码

#include <algorithm>
#include <cstdio>
#include <cmath>
using namespace std;
const int N = 2000010;
const double eps = 1e-8;
int n, stk[N], top;
struct PDD { double x, y; } P[N];
bool PDD_cmp(PDD a, PDD b) { return (a.x != b.x) ? a.x < b.x : a.y < b.y; }
PDD operator+(PDD a, PDD b) { return (PDD) { a.x + b.x, a.y + b.y }; }
PDD operator-(PDD a, PDD b) { return (PDD) { a.x - b.x, a.y - b.y }; }
double cro(PDD a, PDD b) { return a.x * b.y - a.y * b.x; }
double dot(PDD a, PDD b) { return a.x * b.x + a.y * b.y; }
double area(PDD a, PDD b, PDD c) { return cro(b - a, c - a) / 2; }
// 求斜率, 注意特判斜率不存在的情况, 返回INF即可
double get_k(PDD a, PDD b) { return (a.x == b.x) ? 1e18 : (a.y - b.y) / (a.x - b.x); }
// 求函数 f, 注意特判, 如果 k <= 0, 不合法不要算, 防止更新错误答案
double f(PDD a, double k) { return k > 0 ? (a.x + a.y + a.x * k + a.y / k) : 1e18; }
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%lf%lf", &P[i].x, &P[i].y);
sort(P + 1, P + n + 1, PDD_cmp);
for (int i = 1; i <= n; stk[++top] = i, i++) // 求个凸包
while (top >= 2 && area(P[stk[top - 1]], P[stk[top]], P[i]) >= 0) top--;
double res = 1e18;
for (int i = 1; i <= top; i++) {
PDD A = P[stk[i]], B = P[stk[i - 1]], C = P[stk[i + 1]];
double k = sqrt(A.y / A.x), k1 = get_k(B, A), k2 = get_k(C, A);
// 以下不要忘记带负号
if ((i == 1 || -k <= k1) && // 要么 i = 1, 没有前驱节点, 要么比 k1 小
(i == top || -k >= k2)) // 要么 i = top, 没有后继节点, 要么比 k2 大
res = min(res, f(A, k)); // 这样满足 k 的条件, 更新答案
else if (i > 1) res = min(res, f(A, -k1));
else if (i < top) res = min(res, f(A, -k2));
}
printf("%.4lf", res);
return 0;
}


Protein
2天前

代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 200010;
int n, m, w[N], maxv = 0, idx;
int a[N], root[N];
struct NODE { int l, r, s[2], c; } tr[N * 20];
void pushup(int u) { tr[u].c = tr[tr[u].s[0]].c + tr[tr[u].s[1]].c; }
int build(int l, int r) {
int v = ++idx, mid = l + r >> 1;
tr[v].l = l, tr[v].r = r;
if (l == r) return v;
tr[v].s[0] = build(l, mid);
tr[v].s[1] = build(mid + 1, r);
return pushup(v), v;
}
int update(int u, int x) {
int v = ++idx, mid = tr[u].l + tr[u].r >> 1;
tr[v] = tr[u];
if (tr[u].l == tr[u].r) return tr[v].c++, v;
if (x <= mid) tr[v].s[0] = update(tr[u].s[0], x);
else tr[v].s[1] = update(tr[u].s[1], x);
return pushup(v), v;
}
int query(int u, int v, int l, int r) {
int k = tr[v].c - tr[u].c;
if (r < tr[u].l || l > tr[u].r || k == 0) return 0; // 判断一下, 防止越界
if (tr[u].l >= l && tr[u].r <= r) return k;
int cnt = 0, mid = tr[u].l + tr[u].r >> 1;
if (l <= mid) cnt += query(tr[u].s[0], tr[v].s[0], l, r);
if (r > mid) cnt += query(tr[u].s[1], tr[v].s[1], l, r);
return cnt;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> m;
for (register int i = 1; i <= n; i++)  // 找个最大值, 作为值域
cin >> a[i], maxv = max(maxv, a[i]);
root[0] = build(1, maxv); // 把空树建出来
for (register int i = 1; i <= n; i++)
root[i] = update(root[i - 1], a[i]); // 依次插入
for (register int b, x, l, r; m-- && cin >> b >> x >> l >> r; ) {
int ans = 0;
for (register int i = 18; i >= 0; i--) {
int p = query(root[l - 1], root[r], ans - x, ans - x + (1 << i) - 1);
int q = query(root[l - 1], root[r], ans - x + (1 << i), ans - x + (1 << (i + 1)) - 1);
if (!(b >> i & 1) && q) ans += (1 << i);
if (b >> i & 1 && !p) ans += (1 << i);
}
cout << (ans ^ b) << endl;
}
return 0;
}


Protein
2天前

代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 200010;
int n, m, w[N], maxv = 0, idx;
int a[N], root[N];
struct NODE { int l, r, s[2], c; } tr[N * 20];
void pushup(int u) { tr[u].c = tr[tr[u].s[0]].c + tr[tr[u].s[1]].c; }
int build(int l, int r) {
int v = ++idx, mid = l + r >> 1;
tr[v].l = l, tr[v].r = r;
if (l == r) return v;
tr[v].s[0] = build(l, mid);
tr[v].s[1] = build(mid + 1, r);
return pushup(v), v;
}
int update(int u, int x) {
int v = ++idx, mid = tr[u].l + tr[u].r >> 1;
tr[v] = tr[u];
if (tr[u].l == tr[u].r) return tr[v].c++, v;
if (x <= mid) tr[v].s[0] = update(tr[u].s[0], x);
else tr[v].s[1] = update(tr[u].s[1], x);
return pushup(v), v;
}
int query(int u, int v, int l, int r) {
int k = tr[v].c - tr[u].c;
if (r < tr[u].l || l > tr[u].r || k == 0) return 0;
if (tr[u].l >= l && tr[u].r <= r) return k;
int cnt = 0, mid = tr[u].l + tr[u].r >> 1;
if (l <= mid) cnt += query(tr[u].s[0], tr[v].s[0], l, r);
if (r > mid) cnt += query(tr[u].s[1], tr[v].s[1], l, r);
return cnt;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> m;
for (register int i = 1; i <= n; i++)
cin >> a[i], maxv = max(maxv, a[i]);
root[0] = build(1, maxv);
for (register int i = 1; i <= n; i++)
root[i] = update(root[i - 1], a[i]);
for (register int b, x, l, r; m-- && cin >> b >> x >> l >> r; ) {
int ans = 0;
for (register int i = 18; i >= 0; i--) {
int p = query(root[l - 1], root[r], ans - x, ans - x + (1 << i) - 1);
int q = query(root[l - 1], root[r], ans - x + (1 << i), ans - x + (1 << (i + 1)) - 1);
if (b >> i & 1 && !p) ans += (1 << i);
if (!(b >> i & 1) && q) ans += (1 << i);
}
cout << (ans ^ b) << endl;
}
return 0;
}


Protein
2天前

代码

#include <iostream>
#include <cstring>
using namespace std;
const int N = 110, M = 2e7 + 10, mod = 20170408;
int n, m, p, P[M], V[M], idx, cnt[N];
struct MATRIX { int a[N][N]; };
MATRIX operator*(MATRIX A, MATRIX B) {
static MATRIX C;
memset(C.a, 0, sizeof C.a);
for (int i = 0; i < p; i++)
for (int j = 0; j < p; j++)
for (int k = 0; k < p; k++)
C.a[i][j] = (C.a[i][j] + 1ll * A.a[i][k] * B.a[k][j]) % mod;
return C;
}
void init(int n) {
V[1] = true;
for (int i = 2; i <= n; i++) {
if (!V[i]) P[++idx] = i;
for (int j = 1; P[j] <= n / i; j++) {
V[P[j] * i] = true;
if (i % P[j] == 0) break;
}
}
}
MATRIX qmi(MATRIX A, int b) {
static MATRIX C;
memset(C.a, 0, sizeof C.a);
for (int i = 0; i < p; i++) C.a[i][i] = 1;
for (; b; b >>= 1, A = A * A)
if (b & 1) C = C * A;
return C;
}
MATRIX work(int inv) {
static MATRIX A, F;
memset(cnt, 0, sizeof cnt);
memset(F.a, 0, sizeof F.a);
for (int i = 1; i <= m; i++)
if (inv == 1) cnt[i % p]++;
else if (inv == 2 && V[i]) cnt[i % p]++;
for (int i = 0; i < p; i++)
for (int j = 0; j < p; j++)
A.a[i][j] = cnt[(j - i + p) % p];
F.a[0][0] = 1;
return F * qmi(A, n);
}
int main() {
init(M - 10);
cin >> n >> m >> p;
cout << ((work(1).a[0][0] - work(2).a[0][0]) % mod + mod) % mod << endl;
return 0;
}


Protein
3天前

代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010, mod = 1e9 + 7;
int n, m, f[N][20];
// k 是倍增自带的, 忽略 k 就和普通并查集一模一样了
int find(int x, int k) { return f[x][k] != x ? (f[x][k] = find(f[x][k], k)) : f[x][k]; }
void merge(int x, int y, int k) { f[find(x, k)][k] = f[find(y, k)][k]; }
int main() {
cin >> n >> m;
for (int j = 0; j <= 19; j++)
for (int i = 1; i <= n; i++)
f[i][j] = i;
for (int a, b, c, d; m-- && cin >> a >> b >> c >> d; )
for (int i = 19; i >= 0; i--)
if (a + (1 << i) - 1 > b) continue; // 比右边区间大的就跳过
else merge(a, c, i), a += 1 << i, c += 1 << i; // 倍增跳
for (int j = 20; j >= 1; j--) // 注意 >= 1
for (int i = 1; i + (1 << j) - 1 <= n; i++)
merge(i, find(i, j), j - 1),  // 推到两个子区间
merge(i + (1 << (j - 1)), find(i, j) + (1 << (j - 1)), j - 1);
int cnt = 0, res = 9;
for (int i = 1; i <= n; i++) cnt += (f[i][0] == i); // 判断几个集合
for (int i = 1; i <= cnt - 1; i++) res = 1ll * res * 10 % mod; // 暴力算就行
cout << res << endl;
return 0;
}


Protein
3天前

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#define int long long
using namespace std;
const int N = 20010;
int n, m, B[N][61], P[N][61];
int h[N], ptr[N << 1], val[N << 1], idx;
int base[N], f[N][21], dep[N], w[N];
void add(int a, int b) { val[idx] = b, ptr[idx] = h[a], h[a] = idx++; }
void insert(int u, int B[], int P[]) {
int x = w[u];
for (int i = 60; i >= 0; i--) {
if (!(x >> i & 1)) continue;
if (!B[i]) { B[i] = x, P[i] = u; break; } // 不存在线性基
if (dep[u] > dep[P[i]]) swap(P[i], u), swap(x, B[i]); // 比较一下深度
x ^= B[i];
}
}
void DFS(int u, int fa) {
f[u][0] = fa, dep[u] = dep[fa] + 1;
for (int i = 1; i <= 20; i++) // LCA 预处理父亲
f[u][i] = f[f[u][i - 1]][i - 1];
for (int i = 0; i <= 60; i++) // 复制父亲信息
P[u][i] = P[fa][i], B[u][i] = B[fa][i];
insert(u, B[u], P[u]);        // 用自己更新一下
for (int i = h[u]; i != -1; i = ptr[i])
if (val[i] != fa) DFS(val[i], u);
}
int LCA(int a, int b) { // 倍增LCA
if (dep[a] < dep[b]) swap(a, b);
for (int i = 20; i >= 0; i--)
if (dep[f[a][i]] >= dep[b]) a = f[a][i];
if (a == b) return a;
for (int i = 20; i >= 0; i--)
if (f[a][i] != f[b][i])
a = f[a][i], b = f[b][i];
return f[a][0];
}
int query(int a, int b) {
int t = LCA(a, b);
for (int i = 60; i >= 0; i--) // 首先把 a 到 LCA 的线性基全复制过来
(dep[P[a][i]] >= dep[t]) ? base[i] = B[a][i] : base[i] = 0;
for (int i = 60; i >= 0; i--) {
if (dep[P[b][i]] < dep[t]) continue;
int x = B[b][i]; // 暴力插入 b 到 LCA 的线性基
for (int j = 60; j >= 0; j--)
if (!(x >> j & 1)) continue;
else if (!base[j]) { base[j] = x; break; }
else x ^= base[j];
}
int res = 0; // 最大值
for (int i = 60; i >= 0; i--)
res = max(res, base[i] ^ res);
return res;
}
signed main() {
cin >> n >> m;
memset(h, -1, sizeof h);
for (int i = 1; i <= n; i++) cin >> w[i];
for (int i = 1, a, b; i < n; i++)
cin >> a >> b, add(a, b), add(b, a);
DFS(1, 0);
for (int a, b; m-- && cin >> a >> b; )
cout << query(a, b) << endl;
return 0;
}


Protein
4天前

Protein
4天前

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdio>
#define x first
#define y second
using namespace std;
typedef pair<double, double> PDD;
const int N = 1000010;
const double eps = 1e-7;
int n, cnt = 0;
PDD P[N], ans[N];
struct LINE { PDD st, ed; } L[N];
inline PDD operator-(PDD a, PDD b) { return make_pair(a.x - b.x, a.y - b.y); }
inline PDD operator+(PDD a, PDD b) { return make_pair(a.x + b.x, a.y + b.y); }
inline PDD operator*(PDD a, double c) { return make_pair(a.x * c, a.y * c); }
inline int cmp(double a, double b) { return (fabs(a - b) < eps) ? 0 : ((a < b) ? -1 : 1); }
inline double cro(PDD a, PDD b) { return a.x * b.y - a.y * b.x; }
inline double area(PDD a, PDD b, PDD c) { return cro(b - a, c - a); }
inline double get_angle(LINE a) { return atan2(a.ed.y - a.st.y, a.ed.x - a.st.x); }
// get_line_intersection 得到直线交点
inline PDD GLI(PDD p, PDD v, PDD q, PDD w) { return p + v * (cro(w, (p - q)) / cro(v, w));}
inline PDD GLI(LINE a, LINE b) { return GLI(a.st, a.ed - a.st, b.st, b.ed - b.st); }
inline bool on_right(LINE a, LINE b, LINE c) {  return cmp(area(a.st, a.ed, GLI(b, c)), 0) < 0; }
inline double get_area(PDD P[], int n) {
double res = 0;
for (int i = 2; i + 1 <= n; i++)
res += cro(P[i] - P[1], P[i + 1] - P[i]);
return res / 2;
}
inline bool LINE_cmp(LINE a, LINE b) {
double A = get_angle(a), B = get_angle(b);
if (cmp(A, B) == 0) return area(a.st, a.ed, b.ed) < 0;
else return A < B;
}
int q[N];
inline double HPI() {
sort(L + 1, L + cnt + 1, LINE_cmp);
int hh = 0, tt = -1, k = 0;
for (int i = 1; i <= cnt; i++) {
if (i != 1 && !cmp(get_angle(L[i]), get_angle(L[i - 1]))) continue;
while (hh + 1 <= tt && on_right(L[i], L[q[tt - 1]], L[q[tt]])) tt--;
while (hh + 1 <= tt && on_right(L[i], L[q[hh + 1]], L[q[hh]])) hh++;
q[++tt] = i;
}
while (hh + 1 <= tt && on_right(L[q[hh]], L[q[tt - 1]], L[q[tt]])) tt--;
while (hh + 1 <= tt && on_right(L[q[tt]], L[q[hh + 1]], L[q[hh]])) hh++;
q[++tt] = q[hh];
for (int i = hh; i < tt; i++) ans[++k] = GLI(L[q[i]], L[q[i + 1]]);
return get_area(ans, k);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) cin >> P[i].x >> P[i].y;
P[n + 1] = P[1]; // 处理一下, 方便后面
for (int i = 1; i <= n; i++) L[++cnt] = (LINE) { P[i], P[i + 1] };
for (int i = 2; i <= n; i++) {
double A = P[1].y - P[2].y + P[i + 1].y - P[i].y;
double B = P[2].x - P[1].x + P[i].x - P[i + 1].x;
double C = -P[2].x * P[1].y + P[1].x * P[2].y + P[i + 1].x * P[i].y - P[i].x * P[i + 1].y;
if (cmp(B, 0) == 0) L[++cnt] = (LINE) { (PDD){ -C / A, 0 }, (PDD) { -C / A - B, A } };
else L[++cnt] = (LINE) { (PDD) { 0, -C / B }, (PDD) { -B, -C / B + A }};
}
// 概率就是合法面积除以总面积
printf("%.4Lf", HPI() / get_area(P, n));
return 0;
}


Protein
5天前

代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 200010;
int n, m, A[N], B[N];
char C[N];
struct NODE { int l, r, a, b, s, c; } tr[N << 2];
inline void init(int u, int c) {
if (c == 0) tr[u].a = tr[u].b = tr[u].c = tr[u].s = 0;
else tr[u].a = tr[u].b = tr[u].c = 1, tr[u].s = 0;
}
inline NODE operator+(const NODE &l, const NODE &r) { // 运算符重载
NODE u = (NODE) { l.l, r.r };
u.c = l.c + r.c, u.s = l.s + r.s;
u.a = l.a, u.b = r.b;
if (l.c && r.c && (!l.b || !r.a)) u.s++;
return u;
}
void build(int u, int l, int r) {
tr[u].l = l, tr[u].r = r;
if (l == r) return init(u, B[l]), void(0);
int mid = (l + r) >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
tr[u] = tr[u << 1] + tr[u << 1 | 1];
}
void modify(int u, int x, int c) {
if (tr[u].l == tr[u].r) return init(u, c), void(0);
int mid = (tr[u].l + tr[u].r) >> 1;
if (x <= mid) modify(u << 1, x, c);
else modify(u << 1 | 1, x, c);
tr[u] = tr[u << 1] + tr[u << 1 | 1];
}
NODE query(int u, int l, int r) {
if (l <= tr[u].l && tr[u].r <= r) return tr[u];
int md = (tr[u].l + tr[u].r) >> 1;
if (r <= md) return query(u << 1, l, r);
else if (l > md) return query(u << 1 | 1, l, r);
else return query(u << 1, l, r) + query(u << 1 | 1, l, r); // 注意讨论
}
int calc(int x) { return ((C[x] == '+') ? (A[x] + A[x - 1]) : (A[x] * A[x - 1])) % 10; }
inline void modify(int pos, int num, char opt) {
A[pos] = A[pos + n] = num, C[pos] = C[pos + n] = opt;
if (pos > 1) modify(1, pos, calc(pos)); // 如果是开头, 不用计算
modify(1, pos + n, calc(pos + n));
modify(1, pos + 1, calc(pos + 1));
if (pos < n) modify(1, pos + n + 1, calc(pos + n + 1)); // n + pos + 1 超出长度, 不用算
}
bool check(int mid, int pos) { return query(1, pos + mid, n + pos - mid).s; }
inline int query(int pos) {
// 这两行注释了也能过, 样例都过不了......
if (A[pos] == 0 && query(1, pos + 1, pos + n - 1).s == 0) return 0; // 特判 0
if (query(1, pos, pos + n).s == 0) return -1; // 特判 -1
modify(1, pos, A[pos]), modify(1, pos + n, A[pos]);
int l = 0, r = n >> 1;
while (l < r) {
int mid = (l + r + 1) >> 1;
if (query(1, pos + mid, n + pos - mid).s) l = mid;
else r = mid - 1;
}
if (pos > 1) modify(1, pos, calc(pos));
modify(1, pos + n, calc(pos + n));
return l + 1; // 注意加 1
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> A[i] >> C[i];
for (int i = 1; i <= n; i++) A[i + n] = A[i], C[i + n] = C[i];
for (int i = 2; i <= n << 1; i++) B[i] = calc(i);
build(1, 1, n << 1);
char opt;
for (int op, pos, num; m-- && cin >> op >> pos; ) // 由于从 1 开始, 下标需要加 1
if (op == 2) cout << query(pos + 1) << endl;
else cin >> num >> opt, modify(pos + 1, num, opt);
return 0;
}


Protein
6天前

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
const int N = 100010, M = 600010;
int n, tr[M][26], flag[M], idx_t;       // trie
string str[N];
int h[M], ptr[N], val[N], sz[M], idx_g; // 链式前向星
void insert(string str) {
int p = 0, c = str[0] - 'a';
for (int i = 0; i < (int)str.size(); i++, c = str[i] - 'a')
p = ((tr[p][c]) ? tr[p][c] : (tr[p][c] = ++idx_t));
flag[p] = true; // 标记结尾
}
// 加边函数
void add(int a, int b) { val[idx_g] = b, ptr[idx_g] = h[a], h[a] = idx_g++; }
void update(int p, int top) {
// 如果 v 是结尾，加边
for (int i = 0; i < 26; i++)
if (flag[tr[p][i]]) add(top, tr[p][i]);
for (int i = 0; i < 26; i++)
if (flag[tr[p][i]]) update(tr[p][i], tr[p][i]);
else if (tr[p][i]) update(tr[p][i], top);
}
long long res = 0;
void DFS(int u) {
// 计算子树大小
sz[u] = 1;
for (int i = h[u]; i != -1; i = ptr[i])
DFS(val[i]), sz[u] += sz[val[i]];
// 贪心计算答案
vector<int> temp;
for (int i = h[u]; i != -1; i = ptr[i])
temp.push_back(sz[val[i]]);
sort(temp.begin(), temp.end());
int delta = 1; // 偏移量
for (int i = 0; i < (int)temp.size(); i++)
res += delta, delta += temp[i];
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> str[i];
for (int i = 1; i <= n; i++) reverse(str[i].begin(), str[i].end()); // 翻转
for (int i = 1; i <= n; i++) insert(str[i]);                        // 插入
memset(h, -1, sizeof h);
update(0, 0), DFS(0);
cout << res << endl;
return 0;
}