C.Draw Grids
标签：博弈论
解法：容易得出能画的线的数量必定为nm - 1，根据nm奇偶性判断即可。
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
if (n * m % 2 == 0)
cout << "YES" << endl;
else
cout << "NO" << endl;
return 0;
}D.Er Ba Game
标签：模拟
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while (t--) {
int a, b, c, d;
cin >> a >> b >> c >> d;
if (a > b)
swap(a, b);
if (c > d)
swap(c, d);
if (a == 2 && b == 8 && c == 2 && d == 8)
cout << "tie" << endl;
else if (a == 2 && b == 8)
cout << "first" << endl;
else if (c == 2 && d == 8)
cout << "second" << endl;
else if (a == b) {
if (c == d) {
if (a > c)
cout << "first" << endl;
else if (a < c)
cout << "second" << endl;
else
cout << "tie" << endl;
} else {
cout << "first" << endl;
}
} else if (c == d)
cout << "second" << endl;
else if ((a + b) % 10 == (c + d) % 10) {
if (b > d)
cout << "first" << endl;
else if (b < d)
cout << "second" << endl;
else
cout << "tie" << endl;
} else if ((a + b) % 10 > (c + d) % 10)
cout << "first" << endl;
else
cout << "second" << endl;
}
return 0;
}F.Girlfriend
标签：计算几何，积分
解法：考虑二维情况，推出函数曲线为圆形，因此三维情况为两球相交。分为相离、包含、相交（过圆心和不过圆心）分类讨论。
#include <cmath>
#include <iostream>
using namespace std;
using LD = long double;
const LD PI = M_PI;
struct P {
LD x, y, z;
explicit P(LD x = 0, LD y = 0, LD z = 0) : x(x), y(y), z(z) {}
};
struct B {
P p;
LD r;
} b0, b1;
LD dis(P a, P b) {
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y) +
(a.z - b.z) * (a.z - b.z));
}
LD fun(B a, LD y) {
LD t1 = a.r * cos(asin(y / a.r));
LD t = (a.r - t1) / 5000;
LD ans = 0;
for (LD i = t1; i <= a.r; i += t) {
ans += (a.r * a.r - i * i) * PI * t;
}
return ans;
}
LD fun1(B a, LD y) { return 4 * PI * a.r * a.r * a.r / 3 - fun(a, y); }
int main() {
int T;
cin >> T;
for (; T; --T) {
LD ax, ay, az, bx, by, bz;
cin >> ax >> ay >> az;
cin >> bx >> by >> bz;
LD cx, cy, cz, dx, dy, dz;
cin >> cx >> cy >> cz;
cin >> dx >> dy >> dz;
LD k0, k1;
cin >> k0 >> k1;
b0.p = P((k0 * k0 * bx - ax) / (k0 * k0 - 1),
(k0 * k0 * by - ay) / (k0 * k0 - 1),
(k0 * k0 * bz - az) / (k0 * k0 - 1));
b0.r = sqrt(b0.p.x * b0.p.x + b0.p.y * b0.p.y + b0.p.z * b0.p.z +
(ax * ax + ay * ay + az * az -
k0 * k0 * (bx * bx + by * by + bz * bz)) /
(k0 * k0 - 1));
b1.p = P((k1 * k1 * dx - cx) / (k1 * k1 - 1),
(k1 * k1 * dy - cy) / (k1 * k1 - 1),
(k1 * k1 * dz - cz) / (k1 * k1 - 1));
b1.r = sqrt(b1.p.x * b1.p.x + b1.p.y * b1.p.y + b1.p.z * b1.p.z +
(cx * cx + cy * cy + cz * cz -
k1 * k1 * (dx * dx + dy * dy + dz * dz)) /
(k1 * k1 - 1));
LD d = dis(b0.p, b1.p);
if (d >= b0.r + b1.r) {
cout << "0\n";
} else if (d <= abs(b0.r - b1.r)) {
LD t = min(b0.r, b1.r);
cout << 4 * PI * t * t * t / 3 << '\n';
} else {
LD a = dis(b0.p, b1.p);
LD y = sqrt(2 * (b0.r * b0.r * a * a + b1.r * b1.r * a * a +
b0.r * b0.r * b1.r * b1.r) -
b0.r * b0.r * b0.r * b0.r - b1.r * b1.r * b1.r * b1.r -
a * a * a * a) /
2 / a;
LD rmin = min(b0.r, b1.r), rmax = max(b0.r, b1.r);
if (d * d + rmin * rmin >= rmax * rmax)
cout << fun(b0, y) + fun(b1, y) << "\n";
else {
if (b0.r < b1.r)
swap(b0, b1);
cout << fun(b0, y) + fun1(b1, y) << "\n";
}
}
}
return 0;
}I.Penguins
标签：BFS
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int dyA[4] = {-1, 1, 0, 0};
int dxA[4] = {0, 0, -1, 1};
int dyB[4] = {1, -1, 0, 0};
int dxB[4] = {0, 0, -1, 1};
string opt[4] = {"L", "R", "U", "D"};
struct state {
int a, b, c, d;
} st, en;
queue<state> q;
string k[20][20][20][20];
int step[20][20][20][20];
string as[20][2];
bool judge(int x, int y, int z) {
if (x < 0 || x >= 20)
return false;
if (y < 0 || y >= 20)
return false;
if (as[x][z][y] == '#')
return false;
return true;
}
bool operator==(state x, state y) {
return (x.a == y.a) && (x.b == y.b) && (x.c == y.c) && (x.d == y.d);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
memset(step, 0x3f, sizeof(step));
for (int i = 0; i < 20; i++)
cin >> as[i][0] >> as[i][1];
st.a = 19;
st.b = 19;
st.c = 19;
st.d = 0;
en.a = 0;
en.b = 19;
en.c = 0;
en.d = 0;
q.push(st);
step[st.a][st.b][st.c][st.d] = 0;
while (!q.empty()) {
state tmp = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
state nmp = tmp;
if (judge(tmp.a + dxA[i], tmp.b + dyA[i], 0))
nmp.a += dxA[i], nmp.b += dyA[i];
if (judge(tmp.c + dxB[i], tmp.d + dyB[i], 1))
nmp.c += dxB[i], nmp.d += dyB[i];
if (nmp == tmp)
continue;
int stepnmp = step[nmp.a][nmp.b][nmp.c][nmp.d];
int steptmp = step[tmp.a][tmp.b][tmp.c][tmp.d] + 1;
string knmp = k[nmp.a][nmp.b][nmp.c][nmp.d];
string ktmp = k[tmp.a][tmp.b][tmp.c][tmp.d] + opt[i];
if (stepnmp > steptmp || (stepnmp == steptmp && knmp > ktmp)) {
step[nmp.a][nmp.b][nmp.c][nmp.d] = steptmp;
k[nmp.a][nmp.b][nmp.c][nmp.d] = ktmp;
q.push(nmp);
}
}
}
cout << step[en.a][en.b][en.c][en.d] << '\n';
cout << k[en.a][en.b][en.c][en.d] << '\n';
state tmp = st;
as[tmp.a][0][tmp.b] = 'A';
as[tmp.c][1][tmp.d] = 'A';
string option = k[en.a][en.b][en.c][en.d];
int len = option.length();
for (int i = 0; i < len; i++) {
state nmp = tmp;
int x;
if (option[i] == 'L')
x = 0;
else if (option[i] == 'R')
x = 1;
else if (option[i] == 'U')
x = 2;
else
x = 3;
if (judge(tmp.a + dxA[x], tmp.b + dyA[x], 0))
nmp.a += dxA[x], nmp.b += dyA[x];
if (judge(tmp.c + dxB[x], tmp.d + dyB[x], 1))
nmp.c += dxB[x], nmp.d += dyB[x];
tmp = nmp;
as[tmp.a][0][tmp.b] = 'A';
as[tmp.c][1][tmp.d] = 'A';
}
for (int i = 0; i < 20; i++)
cout << as[i][0] << ' ' << as[i][1] << '\n';
return 0;
}K.Stack
标签：构造，平衡树
解法：场上解法较麻烦，后续补上正常解法。
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using LL = long long;
using Tree = __gnu_pbds::tree<int, __gnu_pbds::null_type, less<int>,
__gnu_pbds::splay_tree_tag,
__gnu_pbds::tree_order_statistics_node_update>;
Tree t;
int b[1000001], ans[1000001];
void init(int n) {
for (int i = 1; i <= n; ++i)
t.insert(i);
}
int fun(int k) {
if (k <= 0) {
return 0;
}
auto tmp = t.find_by_order(k - 1);
int tmp1 = *tmp;
t.erase(tmp);
return tmp1;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int n = 0, k = 0;
cin >> n >> k;
int nn = n;
for (int i = 1; i <= k; ++i) {
int p, x;
cin >> p >> x;
b[p] = x;
}
for (n; n; --n) {
if (b[n]) {
break;
} else {
ans[n] = n;
}
}
init(n);
int now = 0;
for (int i = n; i; --i) {
--now;
if (b[i] && b[i] < now) {
cout << "-1\n";
return 0;
}
now = max(now, b[i]);
if (now > i) {
cout << "-1\n";
return 0;
}
ans[i] = fun(now);
}
for (int i = 1; i <= nn; ++i) {
if (!ans[i]) {
ans[i] = fun(1);
}
cout << ans[i] << ' ';
}
cout << '\n';
return 0;
}
Comments NOTHING