CC BY 4.0 （除特别声明或转载文章外）
如果这篇博客帮助到你，可以请我喝一杯咖啡~
Forcefield
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9 + 7;
set<int> s[2]{{0, INF}, {0, INF}};
int n, now, ans;
int main()
{
scanf("%d%d", &n, &now);
for (int i = 0, x, p; i < n; ++i)
scanf("%d%d", &x, &p), s[p & 1].insert(x);
for (int rev = 0;; rev ^= 1)
{
if (rev)
{
int pos = *s[1].upper_bound(now);
if (pos == INF)
{
if (s[0].size() != 2 || s[1].size() != 2)
ans = -1;
break;
}
s[1].erase(now = pos);
}
else
{
int pos = *--s[0].lower_bound(now);
if (pos)
s[0].erase(pos);
else
++ans;
now = pos;
}
}
printf("%d", ans);
}
Missing Part
给你一个串 S，这个 S 是环状的，给你另外一个字符串 S1，然后你需要定义一种大写的 ABCDE 到小写的 abcde 对应关系，使得失配数最小。
假设只有两种字符，那么 1 个卷积就行了。5 个字符，最莽的做法是 120 个卷积，那得超时，预处理一下就是 25 个卷积。卷积当然要 FFT 啦。
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
typedef double lf;
const int N = 65535;
const lf PI = acos(-1);
struct Rader : vector<int>
{
Rader(int n) : vector<int>(1 << int(ceil(log2(n))))
{
for (int i = at(0) = 0; i < size(); ++i)
if (at(i) = at(i >> 1) >> 1, i & 1)
at(i) += size() >> 1;
}
};
struct FFT : Rader
{
vector<complex<lf>> w;
FFT(int n) : Rader(n), w(size(), polar(1.0, 2 * PI / size()))
{
w[0] = 1;
for (int i = 1; i < size(); ++i)
w[i] *= w[i - 1];
}
vector<complex<lf>> fft(const vector<complex<lf>> &a)
{
vector<complex<lf>> x(size());
for (int i = 0; i < a.size(); ++i)
x[at(i)] = a[i];
for (int i = 1; i < size(); i <<= 1)
for (int j = 0; j < i; ++j)
for (int k = j; k < size(); k += i << 1)
{
complex<lf> &l = x[k], &r = x[k + i], t = w[size() / (i << 1) * j] * r;
r = l - t, l += t;
}
return x;
}
vector<ll> mul(vector<complex<lf>> xa, const vector<complex<lf>> &xb)
{
for (int i = 0; i < size(); ++i)
xa[i] *= xb[i];
vector<ll> ans(size());
xa = fft(xa), ans[0] = xa[0].real() / size() + 0.5;
for (int i = 1; i < size(); ++i)
ans[i] = xa[size() - i].real() / size() + 0.5;
return ans;
}
};
char a[N], b[N];
int main()
{
scanf("%s%s", a, b);
int n = strlen(a), ans = 0, p[5];
FFT f(n * 2);
vector<ll> sum[5][5];
vector<vector<complex<lf>>> xa(5, vector<complex<lf>>(n * 2)), xb(5, vector<complex<lf>>(n * 2));
for (int i = 0; i < 5; ++i)
{
for (int j = 0; j < n; ++j)
{
if (a[j] == 'A' + i)
xa[i][j] = xa[i][j + n] = 1;
if (b[j] == 'a' + i)
xb[i][n - j - 1] = 1;
}
xa[i] = f.fft(xa[i]), xb[i] = f.fft(xb[i]), p[i] = i;
}
for (int i = 0; i < 5; ++i)
for (int j = 0; j < 5; ++j)
sum[i][j] = f.mul(xa[i], xb[j]);
do
for (int j = 0, tmp; j < n * 2; ++j)
{
for (int i = tmp = 0; i < 5; ++i)
tmp += sum[i][p[i]][j];
ans = max(ans, tmp);
}
while (next_permutation(p, p + 5));
printf("%d", n - ans);
}
Cryptographic Argument
折纸的过程就是蝴蝶变换。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll M = 1e9 + 7;
struct Rader : vector<int>
{
Rader(int n) : vector<int>(1 << int(ceil(log2(n))))
{
for (int i = at(0) = 0; i < size(); ++i)
if (at(i) = at(i >> 1) >> 1, i & 1)
at(i) += size() >> 1;
}
} rev0(1), rev1(1);
ll h, k, m, l, r, a, b, c;
ll ask(ll u)
{
ll p = u >> (k >> 1) + 1, q = p << (k >> 1) ^ u >> 1;
p = rev1[p], q = rev0[q];
if (u & 1)
p ^= rev1.size() - 1, q ^= rev0.size() - 1;
return (q * rev1.size() | p) << 1 | u & 1;
}
int main()
{
scanf("%lld%lld%lld%lld%lld%lld%lld", &k, &m, &l, &r, &a, &b, &c);
rev0 = Rader(1 << (k >> 1)), rev1 = Rader(1 << k - (k >> 1) - 1);
for (ll i = 0, n = 1LL << k; i < m; ++i)
{
if (l & 1)
{
if (r & 1)
h ^= (r - l >> 1) * (n - 1) + ask(l);
else
h ^= (r - l - 1 >> 1) * (n - 1) + ask(l) + ask(r);
}
else
{
if (r & 1)
h ^= (r - l + 1 >> 1 & 1) * (n - 1);
else
h ^= (r - l >> 1 & 1) * (n - 1) ^ ask(r);
}
h = ((l ^ r ^ h) + c) % M;
l = (l ^ a ^ h) % (n + 1) % n;
r = (r ^ b ^ h) % (n - l) + l;
}
printf("%lld", h);
}
The Jedi Killer
28、29 行的EPS不能用sgn去掉，暂时不知道为啥…改了之后 WA4（猜测是浮点数做减法的时候的对齐操作丢了精度）。
启示是浮点数比较大小的时候不能作差判sgn…
#include <bits/stdc++.h>
#define X real()
#define Y imag()
using namespace std;
typedef double lf;
typedef complex<lf> Coord;
const lf EPS = 1e-9;
int sgn(lf d) { return (d > EPS) - (d < -EPS); }
lf Cross(const Coord &A, const Coord &B) { return A.X * B.Y - B.X * A.Y; }
int main()
{
int t, lm, lg, ans;
for (scanf("%d", &t); t--; printf(ans ? "YES\n" : "NO\n"))
{
scanf("%d%d", &lm, &lg);
vector<Coord> p;
for (int i = 0, x, y; i < 3; ++i)
scanf("%d%d", &x, &y), p.emplace_back(x, y);
if (!sgn(Cross(p[0] - p[1], p[1] - p[2])))
ans = sgn(max(max(abs(p[0] - p[1]), abs(p[1] - p[2])), abs(p[2] - p[0])) - max(lm, lg * 2)) <= 0;
else
for (int i = ans = 0; !ans && i < 3; ++i)
{
lf d0 = abs(p[(i + 1) % 3] - p[(i + 2) % 3]),
h = fabs(Cross(p[(i + 1) % 3] - p[i], p[(i + 2) % 3] - p[i]) / d0),
d1 = sqrt(norm(p[i] - p[(i + 1) % 3]) - h * h),
d2 = sqrt(norm(p[i] - p[(i + 2) % 3]) - h * h);
ans = sgn(h - lm) <= 0 && max(d1, d2) <= lg + EPS ||
sgn(h - lg) <= 0 && max(d1, d2) <= lm + EPS &&
sgn(h * h + d0 * d0 - max(norm(p[i] - p[(i + 1) % 3]), norm(p[i] - p[(i + 2) % 3]))) <= 0;
}
}
}
Youngling Tournament
给你 n 个数，然后从大到小排序，如果这个数不小于他后面的数的和，那么这个数就是胜利者。
单点修改，问你每次胜利者有多少个。
树状数组+multiset瞎几把做即可。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 7;
struct BaseFenwick
{
vector<ll> v;
BaseFenwick(int n) : v(n, 0) {}
void add(int x, ll w)
{
for (; x < v.size(); x += x & -x)
v[x] += w;
}
ll ask(int x)
{
ll ans = 0;
for (; x; x -= x & -x)
ans += v[x];
return ans;
}
};
struct Ranker : vector<ll>
{
void init() { sort(begin(), end()), resize(unique(begin(), end()) - begin()); }
int ask(ll x) const { return lower_bound(begin(), end(), x) - begin(); }
} rk;
ll n, m, a[N], b[N], c[N];
int main()
{
scanf("%lld", &n);
for (int i = 1; i <= n; ++i)
scanf("%lld", &a[i]), rk.push_back(a[i]);
scanf("%lld", &m);
for (int i = 0; i < m; ++i)
scanf("%lld%lld", &b[i], &c[i]), rk.push_back(c[i]);
rk.init();
multiset<ll> s;
BaseFenwick t(rk.size() + 1);
for (int i = 1; i <= n; ++i)
s.insert(a[i]), t.add(rk.ask(a[i]) + 1, a[i]);
for (int i = 0;; ++i)
{
int res = 1;
multiset<ll>::iterator p = s.begin(), q = p++;
if (*p == *q)
++res;
while (1)
{
p = s.lower_bound(t.ask(rk.ask(*q) + 1));
if (p == s.begin())
++p;
if (p == s.end())
break;
q = p--;
if (*q >= t.ask(rk.ask(*p) + 1))
++res;
}
printf("%d\n", res);
if (i == m)
break;
s.erase(s.find(a[b[i]]));
t.add(rk.ask(a[b[i]]) + 1, -a[b[i]]);
s.insert(a[b[i]] = c[i]);
t.add(rk.ask(a[b[i]]) + 1, a[b[i]]);
}
}
Garland Checking
不做路径压缩的并查集，增加一个 splay 操作，用于把某个点旋转到并查集的顶点。
正解是 LCT…待学习。
#include <bits/stdc++.h>
using namespace std;
struct UnionFindSet
{
vector<int> fa;
UnionFindSet(int n) : fa(n)
{
for (int i = 0; i < n; ++i)
fa[i] = i;
}
void splay(int u, int f)
{
if (fa[u] != u)
splay(fa[u], u);
fa[u] = f;
}
int ask(int u) { return fa[u] != u ? ask(fa[u]) : u; }
};
char s[9];
int n, a, b;
int main()
{
scanf("%d", &n);
for (UnionFindSet ufs(n + 1); ~scanf("%s", s) && s[0] != 'E';)
{
scanf("%d%d", &a, &b), ufs.splay(a, a), ufs.splay(b, b);
if (s[0] == 'T')
printf(ufs.ask(a) == b ? "YES\n" : "NO\n"), fflush(stdout);
else
ufs.fa[a] = s[0] == 'D' ? a : b;
}
}