CC BY 4.0 （除特别声明或转载文章外）
如果这篇博客帮助到你，可以请我喝一杯咖啡~
四题签到 RK72 提前滚了…
Polynomial
洛必达定理搞一搞…
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
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t, n;
for (scanf("%d", &t); t--;)
{
scanf("%d", &n);
vector<int> f, g;
for (int i = 0, t; i < n; ++i)
scanf("%d", &t), f.push_back(t);
while (!f.back())
f.pop_back();
for (int i = 0, t; i < n; ++i)
scanf("%d", &t), g.push_back(t);
while (!g.back())
g.pop_back();
if (f.size() != g.size())
printf(f.size() < g.size() ? "0/1\n" : "1/0\n");
else
{
int gcd = __gcd(f.back(), g.back());
printf("%d/%d\n", f.back() / gcd, g.back() / gcd);
}
}
}
Game
一开始没有看到依次处理然后 WA 了两发…
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>
#define L first
#define R second
#define IN(x, p) (p.L <= x && x <= p.R)
#define INS(q, p) (IN(q.L, p) || IN(q.R, p) || IN(p.L, q) || IN(p.R, q))
using namespace std;
typedef pair<int, int> pii;
int main()
{
int t, n;
for (scanf("%d", &t); t--;)
{
scanf("%d", &n);
vector<pii> v;
for (int i = 0, a, b; i < n; ++i)
{
scanf("%d%d", &a, &b);
v.push_back(make_pair(a, b));
}
int ans = 0;
for (pii st(1, 1000000); !v.empty(); v.pop_back())
{
if (INS(st, v.back()))
{
st.L = max(st.L, v.back().L);
st.R = min(st.R, v.back().R);
}
else if (st.R < v.back().L)
{
if (v.back().L < v.back().R)
{
if ((v.back().L - st.R) % 2 == 0)
{
ans += (v.back().L + 1 - st.R) / 2;
st.L = st.R = v.back().L;
}
else
{
if (st.L < st.R)
{
ans += (v.back().L + 1 - st.R) / 2;
st.R = v.back().L + 1;
st.L = v.back().L;
}
else
{
ans += (v.back().L + 1 - st.R) / 2;
st.R = v.back().L + 1;
st.L = v.back().L;
}
}
}
else
{
ans += (v.back().L + 1 - st.R) / 2;
st.L = st.R = v.back().L;
}
}
else
{
swap(st.L, st.R), st.L = -st.L, st.R = -st.R;
swap(v.back().L, v.back().R), v.back().L *= -1, v.back().R *= -1;
if (v.back().L < v.back().R)
{
if ((v.back().L - st.R) % 2 == 0)
{
ans += (v.back().L + 1 - st.R) / 2;
st.L = st.R = v.back().L;
}
else
{
if (st.L < st.R)
{
ans += (v.back().L + 1 - st.R) / 2;
st.R = v.back().L + 1;
st.L = v.back().L;
}
else
{
ans += (v.back().L + 1 - st.R) / 2;
st.R = v.back().L + 1;
st.L = v.back().L;
}
}
}
else
{
ans += (v.back().L + 1 - st.R) / 2;
st.L = st.R = v.back().L;
}
swap(st.L, st.R), st.L = -st.L, st.R = -st.R;
}
}
printf("%d\n", ans);
}
}
Mindis
离散化成$4\times n^4$个点之后建图跑最短路即可。
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
#include <bits/stdc++.h>
using namespace std;
typedef double ll;
const ll INF = 1e18;
const int N = 255;
struct Ranker : vector<int>
{
void init() { sort(begin(), end()), resize(unique(begin(), end()) - begin()); }
int ask(int x) const { return lower_bound(begin(), end(), x) - begin(); }
};
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));
}
}
}
void add(Edge ed)
{
Graph::add(ed);
swap(ed.first, ed.second);
Graph::add(ed);
}
};
int main()
{
int t, n, x1[N], y1[N], x2[N], y2[N];
for (scanf("%d", &t); t--;)
{
Ranker rx, ry;
scanf("%d", &n);
for (int i = 0; i <= n; ++i)
{
scanf("%d%d%d%d", &x1[i], &y1[i], &x2[i], &y2[i]);
rx.push_back(x1[i]);
rx.push_back(x2[i]);
ry.push_back(y1[i]);
ry.push_back(y2[i]);
}
rx.init();
ry.init();
vector<vector<int>> v(rx.size(), vector<int>(ry.size()));
for (int i = 0; i <= n; ++i)
{
x1[i] = rx.ask(x1[i]);
x2[i] = rx.ask(x2[i]);
y1[i] = ry.ask(y1[i]);
y2[i] = ry.ask(y2[i]);
if (i < n)
for (int x = x1[i]; x < x2[i]; ++x)
for (int y = y1[i]; y < y2[i]; ++y)
++v[x][y];
}
Dijkstra g(rx.size() * ry.size());
#define P(i, j) ((i) * (int)ry.size() + j)
for (int i = 1; i < rx.size(); ++i)
for (int j = 1; j < ry.size(); ++j)
{
double lx = rx[i] - rx[i - 1], ly = ry[j] - ry[j - 1];
lx /= v[i - 1][j - 1] + 1, ly /= v[i - 1][j - 1] + 1;
g.add({P(i - 1, j - 1), P(i, j - 1), lx});
g.add({P(i - 1, j - 1), P(i - 1, j), ly});
g.add({P(i, j - 1), P(i, j), ly});
g.add({P(i - 1, j), P(i, j), lx});
}
g.ask(P(x1[n], y1[n]));
printf("%.5f\n", g.d[P(x2[n], y2[n])]);
}
}
Seq
六个一组愉快找规律…
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 31;
ll t, n, k, b;
int main()
{
for (scanf("%I64d", &t); t--;)
{
scanf("%I64d", &n);
k = n / 6, b = n % 6;
printf("%I64d\n", b == 1 ? k * 4 + 1 : b == 2 ? k * 3 + 1 : b == 3 ? k : b == 4 ? 6 * k + 3 : b == 5 ? k : k * 3);
}
}