CC BY 4.0 （除特别声明或转载文章外）
如果这篇博客帮助到你，可以请我喝一杯咖啡~
An Easy Physics Problem
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 double lf;
typedef complex<lf> Coord;
#define X real()
#define Y imag()
const lf EPS = 1e-8;
int sgn(lf d) { return (d > EPS) - (d < -EPS); }
struct Line
{
Coord p, v;
Coord point(lf t) const { return p + v * t; }
};
struct Circle
{
Coord c;
lf r;
Coord point(lf t) const { return c + polar(r, t); } //t为参数，幅角
};
lf Dot(const Coord &A, const Coord &B) { return A.X * B.X + A.Y * B.Y; }
lf Cross(const Coord &A, const Coord &B) { return A.X * B.Y - B.X * A.Y; }
Coord getLineProjection(const Coord &P, const Line &L) { return L.point(Dot(L.v, P - L.p) / norm(L.v)); } //点在直线上的投影
Coord getSymmetry(const Coord &P, const Coord &O) { return O + O - P; } //P关于O的对称点
Coord getSymmetry(const Coord &P, const Line &L) { return getSymmetry(P, getLineProjection(P, L)); } //P关于L的对称点
bool onSegment(const Coord &P, const Coord &A1, const Coord &A2) { return sgn(Dot(A1 - P, A2 - P)) < 0 && !sgn(Cross(A1 - P, A2 - P)); } //判断点是否在线段上，不包含端点
int getLineCircleIntersection(const Line &L, const Circle &C, vector<Coord> &sol)
{
lf a = L.v.X,
b = L.p.X - C.c.X,
c = L.v.Y,
d = L.p.Y - C.c.Y,
e = a * a + c * c,
f = 2 * (a * b + c * d),
g = b * b + d * d - C.r * C.r,
delta = f * f - 4 * e * g;
if (sgn(delta) < 0)
return 0;
if (!sgn(delta))
return sol.push_back(L.point(-f / (2 * e))), 1;
if (sgn((-f - sqrt(delta)) / (2 * e)) > 0)
sol.push_back(L.point((-f - sqrt(delta)) / (2 * e)));
if (sgn((-f + sqrt(delta)) / (2 * e)) > 0)
sol.push_back(L.point((-f + sqrt(delta)) / (2 * e)));
return 2;
}
int ok(const Circle &C, Coord A, Coord V, const Coord &B)
{
vector<Coord> sol;
getLineCircleIntersection(Line{A, V}, C, sol);
if (sol.size() > 1)
{
if (onSegment(sol[1], A, sol[0]))
swap(sol[0], sol[1]);
if (onSegment(B, A, sol[0]))
return 1;
V = getSymmetry(A, Line{C.c, sol[0] - C.c}) - sol[0];
A = sol[0];
}
return !sgn(Cross(B - A, V)) && sgn((B - A).X) == sgn(V.X) && sgn((B - A).Y) == sgn(V.Y);
}
int t, kase, ox, oy, r, ax, ay, vx, vy, bx, by;
int main()
{
for (scanf("%d", &t); t--;)
{
scanf("%d%d%d%d%d%d%d%d%d", &ox, &oy, &r, &ax, &ay, &vx, &vy, &bx, &by);
printf("Case #%d: %s\n", ++kase, ok(Circle{Coord(ox, oy), r}, Coord(ax, ay), Coord(vx, vy), Coord(bx, by)) ? "Yes" : "No");
}
}
Binary Tree
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
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, k, t, ii;
vector<pair<int, char>> vec;
void output(int p)
{
printf("Case #%lld:\n", ii);
if (p == 1)
{
for (int i = 0; i < k - 1; i++)
printf("%lld %c\n", 1LL << i, '+');
printf("%lld %c\n", (1LL << k - 1) + 1, '+');
}
else
{
for (int i = 0; i < vec.size(); i++)
printf("%lld %c\n", vec[i].first, vec[i].second);
}
vec.clear();
}
signed main(void)
{
scanf("%lld", &t);
for (ii = 1; ii <= t; ii++)
{
scanf("%lld%lld", &n, &k);
if (n == (1LL << k))
output(1);
else
{
int t = (1LL << k) - 1 - n;
if (t % 2 == 0)
{
t /= 2;
for (int i = 0; i < k; i++)
{
//printf("%d %c",1LL<<i,t&1?'-':'+');
vec.push_back({1LL << i, t & 1 ? '-' : '+'});
t /= 2;
}
}
else
{
t /= 2;
t++;
for (int i = 0; i < k; i++)
{
//printf("%d %c",1LL<<i,t&1?'-':'+');
vec.push_back({1LL << i, t & 1 ? '-' : '+'});
t /= 2;
//t++;
}
vec[vec.size() - 1].first++;
}
output(2);
}
}
}
Friendship of Frog
蛤的友谊。
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
#include <bits/stdc++.h>
using namespace std;
char a[100000];
vector<int> vec[40];
int t, ans;
int main(void)
{
scanf("%d", &t);
for (int ii = 1; ii <= t; ii++)
{
scanf("%s", a);
for (int i = 0; i < 26; i++)
vec[i].clear();
for (int j = 0; a[j] != '\0'; j++)
{
vec[a[j] - 'a'].push_back(j);
}
ans = 1000000;
for (int i = 0; i < 26; i++)
{
for (int j = 1; j < vec[i].size(); j++)
ans = min(ans, vec[i][j] - vec[i][j - 1]);
}
if (ans == 1000000)
ans = -1;
printf("Case #%d: %d\n", ii, ans);
}
}
Kingdom of Black and White
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>
using namespace std;
typedef long long LL;
const int maxn = 1e5 + 10;
int T, tot;
LL a[maxn];
char ch[maxn];
int main()
{
scanf("%d", &T);
for (int t = 1; t <= T; t++)
{
scanf("%s", ch);
int L = strlen(ch);
memset(a, 0, sizeof(a));
tot = 1;
a[tot] = 1;
for (int i = 1; i < L; i++)
{
if (ch[i] != ch[i - 1])
tot++;
a[tot]++;
}
LL ans = 0, res = 0;
for (int i = 1; i <= tot; i++)
ans += a[i] * a[i];
LL Lans = ans;
for (int i = 1; i <= tot; i++)
{
if (i > 1)
{
if (a[i - 1] - 1ll != 0 || i - 2 <= 0)
{
res = ans - a[i] * a[i] + (a[i] + 1ll) * (a[i] + 1ll);
res = res - a[i - 1] * a[i - 1] + (a[i - 1] - 1ll) * (a[i - 1] - 1ll);
}
else
{
res = ans - a[i] * a[i] - a[i - 1] * a[i - 1] - a[i - 2] * a[i - 2];
res = res + (a[i] + a[i - 1] + a[i - 2]) * (a[i] + a[i - 1] + a[i - 2]);
}
Lans = max(res, Lans);
}
if (i < tot)
{
if (a[i + 1] - 1ll != 0 || i + 2 > tot)
{
res = ans - a[i] * a[i] + (a[i] + 1ll) * (a[i] + 1ll);
res = res - a[i + 1] * a[i + 1] + (a[i + 1] - 1ll) * (a[i + 1] - 1ll);
}
else
{
res = ans - a[i] * a[i] - a[i + 1] * a[i + 1] - a[i + 2] * a[i + 2];
res = res + (a[i] + a[i + 1] + a[i + 2]) * (a[i] + a[i + 1] + a[i + 2]);
}
Lans = max(res, Lans);
}
}
printf("Case #%d: %lld\n", t, Lans);
}
return 0;
}
LCM Walk
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
int deal(int x, int y)
{
int g = __gcd(x, y);
if (y % (g + x))
return 1;
int k = y / (g + x);
int t = y - k * x;
return 1 + deal(min(t, x), max(t, x));
}
int main()
{
int x, y, t;
scanf("%d", &t);
for (int i = 1; i <= t; i++)
{
scanf("%d%d", &x, &y);
printf("Case #%d: %d\n", i, deal(min(x, y), max(x, y)));
}
}