CC BY 4.0 （除特别声明或转载文章外）
如果这篇博客帮助到你，可以请我喝一杯咖啡~
Bazinga
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
#include <bits/stdc++.h>
using namespace std;
const int maxn=500+10,maxL=2000+10;
int T,n,ans;
char ch[maxn][maxL];
struct KMP
{
const string s;
vector<int> next;
KMP(const string &s) : s(s), next(s.size() + 1, 0)
{
for (int i = 1, j; i < s.size(); ++i)
{
for (j = next[i]; j && s[i] != s[j];)
j = next[j];
next[i + 1] = s[i] == s[j] ? j + 1 : 0;
}
}
bool find_in(const string &t)const
{
for (int i = 0, j = 0; i < t.size(); ++i)
{
while (j && s[j] != t[i])
j = next[j];
if (s[j] == t[i])
++j;
if (j == s.size())
return 1; //²»return¿ÉµÃµ½tÖÐsµÄËùÓÐÆ¥ÅäµØÖ·i+1-s.size()
}
return 0;
}
};
int main()
{
scanf("%d",&T);
for (int t=1;t<=T;t++)
{
scanf("%d",&n);
for (int i=1;i<=n;i++) scanf("%s",ch[i]);
int L=0,R=0;
for (int i=n;i>=2;i--) if (!KMP(ch[i-1]).find_in(ch[i])) {R=i;break;}
if (R==0) {printf("Case #%d: -1\n",t);continue;}
ans=R;
L=R;R++;
while (R<=n)
{
while (L>0 && KMP(ch[L]).find_in(ch[R])) L--;
if (L<=0) break;
R++;
}
ans=max(ans,R-1);
printf("Case #%d: %d\n",t,ans);
}
return 0;
}
Pagodas
1
2
3
4
5
6
7
8
9
10
11
12
#include <bits/stdc++.h>
using namespace std;
int t, n, a, b;
int main()
{
scanf("%d", &t);
for (int i = 1; i <= t; i++)
{
scanf("%d%d%d", &n, &a, &b);
cout << "Case #" << i << ": " << (n / (__gcd(a, b)) % 2 ? "Yuwgna" : "Iaka") << endl;
}
}
Triple
三维偏序，使用二维树状数组维护。
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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Fenwick
{
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;
}
};
pair<BaseFenwick, BaseFenwick> p;
Fenwick(int n) : p(n, n) {}
void add(int x, ll w) { p.first.add(x, w), p.second.add(x, x * w); }
void add(int l, int r, ll w) { add(l, w), add(r + 1, -w); }
ll ask(int x) { return (x + 1) * p.first.ask(x) - p.second.ask(x); }
ll ask(int l, int r) { return ask(r) - ask(l - 1); }
};
struct Fenwick2
{
struct BaseFenwick2
{
vector<Fenwick> v;
BaseFenwick2(int r, int c) : v(r, c) {}
void add(int x, int b, int t, ll w)
{
for (; x < v.size(); x += x & -x)
v[x].add(b, t, w);
}
ll ask(int x, int b, int t)
{
ll ans = 0;
for (; x; x -= x & -x)
ans += v[x].ask(b, t);
return ans;
}
};
pair<BaseFenwick2, BaseFenwick2> p;
Fenwick2(int r, int c) : p(BaseFenwick2(r, c), BaseFenwick2(r, c)) {}
void add(int x, int b, int t, ll w) { p.first.add(x, b, t, w), p.second.add(x, b, t, x * w); }
void add(int l, int b, int r, int t, ll w) { add(l, b, t, w), add(r + 1, b, t, -w); } //(l,b)~(r,t)
ll ask(int x, int b, int t) { return (x + 1) * p.first.ask(x, b, t) - p.second.ask(x, b, t); }
ll ask(int l, int b, int r, int t) { return ask(r, b, t) - ask(l - 1, b, t); }
};
const int M = 1e5 + 9;
int t, n, m, kase;
int main()
{
for (scanf("%d", &t); t--;)
{
vector<tuple<int, int>> a(M);
vector<tuple<int, int, int, int>> p;
scanf("%d%d", &n, &m);
for (int i = 0, x, y; i < n; ++i)
{
scanf("%d%d", &x, &y);
if (get<0>(a[y]) < x)
a[y] = make_tuple(x, 0);
if (get<0>(a[y]) == x)
++get<1>(a[y]);
}
for (int i = 0, c, d, e; i < m; ++i)
{
scanf("%d%d%d", &c, &d, &e);
p.emplace_back(get<0>(a[e]), c, d, get<1>(a[e]));
}
sort(p.rbegin(), p.rend());
for (int i = 1; i < p.size(); ++i)
if (get<0>(p[i - 1]) == get<0>(p[i]) && get<1>(p[i - 1]) == get<1>(p[i]) && get<2>(p[i - 1]) == get<2>(p[i]))
{
get<3>(p[i]) += get<3>(p[i - 1]);
get<3>(p[i - 1]) = 0;
}
Fenwick2 f(1023, 1023);
ll ans = 0;
for (auto it : p)
if (get<3>(it))
{
if (!f.ask(get<1>(it) + 5, get<2>(it) + 5, 1009, 1009))
ans += get<3>(it);
f.add(get<1>(it) + 5, get<2>(it) + 5, get<1>(it) + 5, get<2>(it) + 5, get<3>(it));
}
printf("Case #%d: %lld\n", ++kase, ans);
}
}
Kykneion asma
还是要学习一个，任意模数的 FFT，不是费马素数的模数要用特殊的姿势去膜，不能无脑 NTT。
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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double lf;
#define X real()
#define Y imag()
#ifndef M_PI
const double M_PI = acos(-1);
#endif
struct Mod
{
const ll M, SM;
Mod(ll M) : M(M), SM(sqrt(M) + 0.5) {}
ll qadd(ll &a, ll b) const { return a += b, a >= M ? a -= M : a; } //假如a+b<2*M，就不必取模了，取模运算耗时很高
ll add(ll a, ll b) const { return qadd(a = (a + b) % M, M); } //考虑a和b不在同余系内甚至为负数的情况
ll mul(ll a, ll b) const { return add(a * b, M); }
};
struct Factorial : Mod
{
vector<ll> fac, ifac;
Factorial(int N, ll M) : fac(N, 1), ifac(N, 1), Mod(M)
{
for (int i = 2; i < N; ++i)
fac[i] = mul(fac[i - 1], i), ifac[i] = mul(M - M / i, ifac[M % i]);
for (int i = 2; i < N; ++i)
ifac[i] = mul(ifac[i], ifac[i - 1]);
}
} M(32767, 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;
}
};
struct FFT : Rader
{
vector<complex<lf>> w;
FFT(int n) : Rader(n), w(size())
{
for (int i = 0; i < size(); ++i)
w[i] = polar(1.0, 2 * M_PI * i / size());
}
void fft(vector<complex<lf>> &x) const
{
for (int i = 0; i < x.size(); ++i)
if (i < at(i))
std::swap(x[i], x[at(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> t = w[size() / (i << 1) * j] * x[k + i];
x[k + i] = x[k] - t, x[k] += t;
}
}
vector<ll> ask(const vector<ll> &a, const vector<ll> &b) const
{
vector<complex<lf>> xa(a.begin(), a.end()), xb(b.begin(), b.end());
xa.resize(size()), xb.resize(size()), fft(xa), fft(xb);
for (int i = 0; i < size(); ++i)
xa[i] *= xb[i];
fft(xa);
vector<ll> ans(size());
for (int i = 0; i < size(); ++i)
ans[i] = xa[(size() - i) & (size() - 1)].real() / size() + 0.5;
return ans;
}
vector<ll> askMod(const vector<ll> &a, const vector<ll> &b, ll M) const //任意模数
{
vector<complex<lf>> e(size()), c(size());
for (int i = 0; i < a.size(); ++i)
e[i].real(a[i] & 0x7fff), e[i].imag(a[i] >> 15);
for (int i = 0; i < b.size(); ++i)
c[i].real(b[i] & 0x7fff), c[i].imag(b[i] >> 15);
fft(e), fft(c);
vector<complex<lf>> d(c);
for (int i = 0; i < size(); ++i)
{
int fr = (size() - i) & (size() - 1);
c[i] *= 0.5 * complex<lf>(e[i].X + e[fr].X, e[i].Y - e[fr].Y);
d[i] *= 0.5 * complex<lf>(e[i].Y + e[fr].Y, e[fr].X - e[i].X);
}
fft(c), fft(d);
vector<ll> ans(size());
for (int i = 0; i < size(); ++i)
{
ll fr = (size() - i) & (size() - 1),
p = c[fr].X / size() + 0.5,
o = c[fr].Y / size() + 0.5,
x = d[fr].X / size() + 0.5,
u = d[fr].Y / size() + 0.5;
ans[i] = (p % M + ((o + x) % M << 15) + (u % M << 30)) % M;
}
return ans;
}
};
int t, n, m, kase;
int main()
{
for (scanf("%d", &t); t--;)
{
scanf("%d", &n);
vector<ll> f(n + 1);
f[0] = 1;
for (int a = 0; a < 5; ++a)
{
scanf("%d", &m);
for (int i = 0; i <= n; ++i)
if (n - i - (a == 0) >= 0)
f[i] = M.mul(f[i], M.fac[n - i - (a == 0)]);
auto g = FFT(n + m + 2).askMod(f, vector<ll>(M.ifac.begin(), M.ifac.begin() + m + 1), M.M);
for (int i = 0; i <= n; ++i)
if (n - i - (a == 0) >= 0)
f[i] = M.mul(g[i], M.ifac[n - i - (a == 0)]);
}
printf("Case #%d: %lld\n", ++kase, f[n]);
}
}
Meeting
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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
struct Graph
{
struct Vertex
{
vector<int> o;
};
struct Edge
{
int first, second;
ll len; //?????,??????
};
vector<Vertex> v; //??
vector<Edge> e; //??
Graph(int n) : v(n) {}
void add(const Edge &ed)
{
v[ed.first].o.push_back(e.size());
e.push_back(ed);
}
};
struct Dijkstra : Graph
{
vector<ll> d;
vector<int> p;
Dijkstra(int n) : Graph(n) {}
void ask(int s)
{
d.assign(v.size(), INF);
//p.assign(v.size(), e.size());
priority_queue<pair<ll, int>> q;
for (q.push(make_pair(d[s] = 0, s)); !q.empty();)
{
ll dis = -q.top().first;
int u = q.top().second;
if (q.pop(), d[u] < dis)
continue;
for (int i = 0, k, to; i != v[u].o.size(); ++i)
if (k = v[u].o[i], to = e[k].second,
d[to] > d[u] + e[k].len)
{
d[to] = d[u] + e[k].len; //, p[to] = k;
q.push(make_pair(-d[to], to));
}
}
}
};
int t, n, m, kase;
int main()
{
for (scanf("%d", &t); t--;)
{
scanf("%d%d", &n, &m);
Dijkstra g(n + m + 1);
for (int i = 1, t, s; i <= m; ++i)
{
scanf("%d%d", &t, &s);
for (int j = 0, x; j < s; ++j)
{
scanf("%d", &x);
g.add({x, n + i, t});
g.add({n + i, x, t});
}
}
g.ask(1);
vector<ll> d;
swap(d, g.d);
g.ask(n);
pair<ll, vector<int>> ans(INF, {});
for (int i = 1; i <= n; ++i)
{
ll tmp = max(d[i], g.d[i]);
if (ans.first > tmp)
ans.first = tmp, ans.second.clear();
if (ans.first == tmp)
ans.second.push_back(i);
}
if (ans.first < INF)
{
printf("Case #%d: %lld\n", ++kase, ans.first >> 1);
for (int i = 0; i < ans.second.size(); ++i)
printf("%d%c", ans.second[i], "\n "[i + 1 < ans.second.size()]);
}
else
printf("Case #%d: Evil John\n", ++kase);
}
}