「csp校内训练 2019-10-25」解题报告
T1、高中物理题
\(Description\)：
在《物理 必修1》书中，我们学习了匀变速直线运动这种运动方式，相信大家对它的相关性质已经很了解了。（尚不了解的同学可以参考题面最后的说明）。
现在，在理想的光滑平面上放置着一个小物块。给定了 \(n\) 个加速阶段，每种方式包含两个属性，分别为 \(a_i\) 加速度 (单位为 \(\mathrm{m/s^2}\)) 与 \(t_i\) 能够维持这个加速度的时间 (单位为 \(\mathrm{s}\))。只有当一个阶段结束后才能切换到下一个阶段，切换的过程并不会消耗时间。数据保证加速度和时间都是正数。
众所周知，物理老师一定不会轻易放过我们。他想知道，假定能任意安排阶段之间的顺序，这个物块的可能最大位移与按输入顺序进行加速的位移之差值是多少。也就是说，你需要先找到一种加速的顺序使得物块位移最大，再用这个最大值减去输入顺序加速的位移，并输出这个差值。
\(1 \leq n \leq 10^5, 0 < a_i, t_i \leq 10^5\)。
\(Solution\)：
位移为：\(x = v_0 t + \frac{1}{2} a t ^ 2\)
\(\frac{1}{2} a t ^ 2\) 是不变的，所以让 \(v_0\) 最快达到最大值就是最大位移。
时间复杂度 \(O(n \log_2 n + kn)\)，其中 \(k\) 为高精度复杂度。
\(Source\)：
#include <cstdio>
#include <cstring>
#include <algorithm>
int in() {
int x = 0; char c = getchar(); bool f = 0;
while (c < '0' || c > '9')
f |= c == '-', c = getchar();
while (c >= '0' && c <= '9')
x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
return f ? -x : x;
}
template<typename T>inline void chk_min(T &_, T __) { _ = _ < __ ? _ : __;}
template<typename T>inline void chk_max(T &_, T __) { _ = _ > __ ? _ : __;}
const int N = 1e5 + 5, M = 1e6;
struct info {
int a, t;
inline bool operator < (const info &b) const {
return this->a > b.a;
}
} p[N];
int n;
struct INT {
long long a[10];
INT() {
memset(a, 0, sizeof(a));
}
inline long long& operator [] (const int x) {
return a[x];
}
inline INT operator + (long long b) {
INT ret;
for (int i = 9; i >= 0; --i)
ret[i] = a[i];
ret[0] += b;
for (int i = 0; i < 9; ++i)
if (ret[i] >= M)
ret[i + 1] += ret[i] / M , ret[i] %= M;
return ret;
}
inline INT operator + (INT b) {
INT ret;
for (int i = 9; i >= 0; --i)
ret[i] = a[i] + b[i];
for (int i = 0; i < 9; ++i)
if (ret[i] >= M)
ret[i + 1] += ret[i] / M , ret[i] %= M;
return ret;
}
inline INT operator * (long long b) {
INT ret;
for (int i = 9; i >= 0; --i)
ret[i] = a[i] * b;
for (int i = 0; i < 9; ++i)
if (ret[i] >= M)
ret[i + 1] += ret[i] / M , ret[i] %= M;
return ret;
}
inline INT operator - (INT b) {
INT ret;
for (int i = 9; i >= 0; --i)
ret[i] = a[i] - b[i];
for (int i = 0; i < 9; ++i)
if (ret[i] < 0)
ret[i + 1] += (ret[i] / M - 1) , ret[i] = (ret[i] % M + M) % M;
return ret;
}
inline void operator += (long long b) {
*this = *this + b;
}
inline void operator += (INT b) {
*this = *this + b;
}
inline void operator -= (INT b) {
*this = *this - b;
}
void out() {
int i;
for (i = 9; i >= 0; --i)
if (a[i] > 0)
break;
if (!~i)
return (void)(puts("0.0"));
printf("%lld", a[i]);
for (--i; i >= 0; --i)
printf("%06lld", a[i]);
puts(".0");
}
} ;
int main() {
//freopen("in", "r", stdin);
freopen("physics.in", "r", stdin);
freopen("physics.out", "w", stdout);
n = in();
for (int i = 1; i <= n; ++i)
p[i] = (info){in(), in()};
INT t1, t2, v_1, v_2;
for (int i = 1; i <= n; ++i) {
t1 += v_1 * p[i].t;
v_1 += 1ll * p[i].a * p[i].t;
}
std::sort(p + 1, p + 1 + n);
for (int i = 1; i <= n; ++i) {
t2 += v_2 * p[i].t;
v_2 += 1ll * p[i].a * p[i].t;
}
//t2.out(), t1.out();
(t2 - t1).out();
return 0;
}T2、买咖啡
\(Description\)：
KSkun 自从上了带学以来上课就没有不困的时候，尤其是微积分课，大脑基本全程处于离线状态。然而面对 \(11\) 学分的微积分课， KSkun 必须不挂科才能够顺利毕业。这时，咖啡就成了救命药。
由于咖啡在带学中是抢手货，它的价格每小时都会发生变化。现在，考虑长为 \(n\) 小时的一段时间，在第 \(i\) 小时中，咖啡的价格为 \(c_i\)。由于秋冬季容易感冒，KSkun 不会喝冷了的咖啡，一杯咖啡在经过 \(h\) 小时后会冷，这之后 KSkun 不会再喝它了。一杯咖啡可以让 KSkun 保持清醒 \(1\) 小时，他想知道在每个小时中分别买几杯咖啡，才能让自己在花费最少的情况下在每个小时中都能够通过喝 \(1\) 杯热的咖啡保持清醒。
在本题中，你只需要输出第 \([b, e]\) 这些小时中的答案即可。
\(1 \leq n \leq 10^5, 1 \leq h, b, e \leq n, 1 \leq c_i \leq 10^4\)。保证多组数据n之和不超过 \(5*10^5\)。
\(Solution\)：
单调队列维护即可。
时间复杂度 \(O(\sum n_i)\)。
\(Source\)：
#include <cstdio>
#include <cstring>
#include <algorithm>
int in() {
int x = 0; char c = getchar(); bool f = 0;
while (c < '0' || c > '9')
f |= c == '-', c = getchar();
while (c >= '0' && c <= '9')
x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
return f ? -x : x;
}
template<typename T>inline void chk_min(T &_, T __) { _ = _ < __ ? _ : __;}
template<typename T>inline void chk_max(T &_, T __) { _ = _ > __ ? _ : __;}
const int N = 1e5 + 5;
int n, h, b, e;
int main() {
//freopen("in", "r", stdin);
freopen("coffee.in", "r", stdin);
freopen("coffee.out", "w", stdout);
while (~scanf("%d %d %d %d", &n, &h, &b, &e)) {
static int c[N], cnt[N], q[N];
for (int i = 1; i <= n; ++i)
c[i] = in();
int l = 0, r = 0;
for (int i = 1; i <= n; ++i) {
cnt[i] = 0;
while (l < r && i - q[l] >= h)
++l;
while (l < r && c[i] <= c[q[r - 1]])
--r;
q[r++] = i;
++cnt[q[l]];
}
for (int i = b; i <= e; ++i)
printf("%d ", cnt[i]);
puts("");
}
return 0;
}T3、我的世界
\(Description\)：
《我的世界》（Minecraft，以下简称 MC ）是一款在 OI 界很知名的游戏。KSkun 也对它起了兴趣。
众所周知，由于性能限制，在 MC 中，你只能看到距离自己一定距离之内的物体，我们把可视距离限制记为 \(D\) 。MC 的世界中的任何一个位置都能用一个坐标 \((x, y, z)\) 表示，计算两个位置 \((x_1, y_1, z_1), (x_2, y_2, z_2)\) 之间的距离的公式为 \(d = |x_1 - x_2| + |y_1 - y_2| + |z_1 - z_2|\)。当两个位置之间的距离 \(d\) 满足 \(d \leq D\) 时这两个位置的玩家可以看到彼此。
现在，已知某个 MC 服务器中一共有 \(n\) 个玩家，坐标的范围为 \(1\) 到 \(m\) 之间的整数，为了简化问题，我们讨论不同维度的空间，空间的维度记为 \(B\) ，可能的取值为 \(\{1, 2, 3\}\) 。对于其他未讨论的维度，其坐标参数为维度数，且距离计算方法也是各坐标参数之差的绝对值之和。求服务器中有多少对玩家互相可以看见彼此。
特别地，一个玩家不能看见自己。
数据按照 \(B\) 的取值分组，其中，\(B=1\) 和 \(B=2\) 两种情况各 \(30\) 分，\(B=3\) 共 \(40\) 分。
对于 \(B=1\) 的数据：
\(1 \leq m \leq 75,000,000\)对于 \(B=2\) 的数据：
\(1 \leq m \leq 75,000\)对于 \(B=3\) 的数据：
\(1 \leq m \leq 75\)对于所有数据：
\(1 \leq B \leq 3, 1 \leq n \leq 10^5, 1 \leq D \leq 10^8, 1 \leq x_i, y_i, z_i \leq m\)。
\(Solution\)：
\(B = 1\)：
排序。
时间复杂度 \(O(n \log_2 n)\)。
\(B = 2\)：
转切比雪夫距离后扫描线。
时间复杂度 \(O(n \log_2 n)\)。
\(B = 3\)：
由于 \(M \leq 75\) 把两维转切比雪夫距离，对于每一个第三维坐标维护其他两维的前缀和。
时间复杂度 \(O(mn)\)。
\(Source\)：
#include <cstdio>
#include <cstring>
#include <algorithm>
int in() {
int x = 0; char c = getchar(); bool f = 0;
while (c < '0' || c > '9')
f |= c == '-', c = getchar();
while (c >= '0' && c <= '9')#include <cstdio>
#include <cstring>
#include <algorithm>
int in() {
int x = 0; char c = getchar(); bool f = 0;
while (c < '0' || c > '9')
f |= c == '-', c = getchar();
while (c >= '0' && c <= '9')
x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
return f ? -x : x;
}
template<typename T>inline void chk_min(T &_, T __) { _ = _ < __ ? _ : __;}
template<typename T>inline void chk_max(T &_, T __) { _ = _ > __ ? _ : __;}
const int N = 1e5 + 5;
struct node {
int x, y, z;
inline bool operator < (const node &b) const {
return this->x < b.x;
}
} a[N];
int n, B, d, m;
long long res;
namespace _1D {
void work() {
std::sort(a + 1, a + 1 + n);
for (int i = 1, pos = 1; i <= n; ++i) {
while (pos < i && a[i].x - a[pos].x > d)
++pos;
res += i - pos;
}
}
}
namespace _2D {
struct binary_index_tree {
int t[N + N];
void modify(int p, int k) { for (; p <= m + m; p += (p & -p)) t[p] += k; }
int ask(int p, int ret = 0) { for (; p; p -= (p & -p)) ret += t[p]; return ret; }
} bit;
void work() {
for (int i = 1; i <= n; ++i)
a[i] = (node){a[i].x - a[i].y, a[i].x + a[i].y};
std::sort(a + 1, a + 1 + n);
for (int i = 1, pos = 1; i <= n; ++i) {
for (; pos < i && a[i].x - a[pos].x > d; ++pos)
bit.modify(a[pos].y, -1);
res += bit.ask(std::min(m + m, a[i].y + d)) - bit.ask(std::max(0, a[i].y - d - 1));
bit.modify(a[i].y, 1);
}
}
}
namespace _3D {
const int M = 77;
int s[M][M << 1 | 1][M << 1 | 1];
void work() {
for (int i = 1; i <= n; ++i) {
a[i] = (node){a[i].x + a[i].y, a[i].x - a[i].y + m, a[i].z};
++s[a[i].z][a[i].x][a[i].y];
}
for (int i = 1; i <= m; ++i)
for (int j = 1; j <= m + m; ++j)
for (int k = 1; k <= m + m; ++k)
s[i][j][k] += s[i][j - 1][k] + s[i][j][k - 1] - s[i][j - 1][k - 1];
for (int i = 1; i <= n; ++i) {
int z = a[i].z, x = a[i].x, y = a[i].y, tmp, ux, uy, vx, vy;
for (int j = std::min(m, z + d); j >= std::max(1, z - d); --j) {
tmp = d - std::abs(j - z);
ux = x + tmp, chk_min(ux, m + m);
uy = y + tmp, chk_min(uy, m + m);
vx = x - tmp, chk_max(vx, 1);
vy = y - tmp, chk_max(vy, 1);
res += s[j][ux][uy] - s[j][vx - 1][uy] - s[j][ux][vy - 1] + s[j][vx - 1][vy - 1];
}
--res;
}
res >>= 1;
}
}
int main() {
//freopen("in", "r", stdin);
freopen("minecraft.in", "r", stdin);
freopen("minecraft.out", "w", stdout);
B = in(), n = in(), d = in(), m = in();
for (int i = 1; i <= n; ++i) {
a[i].x = in();
if (B > 1)
a[i].y = in();
if (B > 2)
a[i].z = in();
}
if (B == 1) {
_1D::work();
} else if (B == 2) {
_2D::work();
} else {
_3D::work();
}
printf("%lld\n", res);
return 0;
}
x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
return f ? -x : x;
}
template<typename T>inline void chk_min(T &_, T __) { _ = _ < __ ? _ : __;}
template<typename T>inline void chk_max(T &_, T __) { _ = _ > __ ? _ : __;}
const int N = 1e5 + 5;
struct node {
int x, y, z;
inline bool operator < (const node &b) const {
return this->x < b.x;
}
} a[N];
int n, B, d, m;
long long res;
namespace _1D {
void work() {
std::sort(a + 1, a + 1 + n);
for (int i = 1, pos = 1; i <= n; ++i) {
while (pos < i && a[i].x - a[pos].x > d)
++pos;
res += i - pos;
}
}
}
namespace _2D {
struct binary_index_tree {
int t[N + N];
void modify(int p, int k) { for (; p <= m + m; p += (p & -p)) t[p] += k; }
int ask(int p, int ret = 0) { for (; p; p -= (p & -p)) ret += t[p]; return ret; }
} bit;
void work() {
for (int i = 1; i <= n; ++i)
a[i] = (node){a[i].x - a[i].y, a[i].x + a[i].y};
std::sort(a + 1, a + 1 + n);
for (int i = 1, pos = 1; i <= n; ++i) {
for (; pos < i && a[i].x - a[pos].x > d; ++pos)
bit.modify(a[pos].y, -1);
res += bit.ask(std::min(m + m, a[i].y + d)) - bit.ask(std::max(0, a[i].y - d - 1));
bit.modify(a[i].y, 1);
}
}
}
namespace _3D {
const int M = 77;
int s[M][M << 1 | 1][M << 1 | 1];
void work() {
for (int i = 1; i <= n; ++i) {
a[i] = (node){a[i].x + a[i].y, a[i].x - a[i].y + m, a[i].z};
++s[a[i].z][a[i].x][a[i].y];
}
for (int i = 1; i <= m; ++i)
for (int j = 1; j <= m + m; ++j)
for (int k = 1; k <= m + m; ++k)
s[i][j][k] += s[i][j - 1][k] + s[i][j][k - 1] - s[i][j - 1][k - 1];
for (int i = 1; i <= n; ++i) {
int z = a[i].z, x = a[i].x, y = a[i].y, tmp, ux, uy, vx, vy;
for (int j = std::min(m, z + d); j >= std::max(1, z - d); --j) {
tmp = d - std::abs(j - z);
ux = x + tmp, chk_min(ux, m + m);
uy = y + tmp, chk_min(uy, m + m);
vx = x - tmp, chk_max(vx, 1);
vy = y - tmp, chk_max(vy, 1);
res += s[j][ux][uy] - s[j][vx - 1][uy] - s[j][ux][vy - 1] + s[j][vx - 1][vy - 1];
}
--res;
}
res >>= 1;
}
}
int main() {
//freopen("in", "r", stdin);
freopen("minecraft.in", "r", stdin);
freopen("minecraft.out", "w", stdout);
B = in(), n = in(), d = in(), m = in();
for (int i = 1; i <= n; ++i) {
a[i].x = in();
if (B > 1)
a[i].y = in();
if (B > 2)
a[i].z = in();
}
if (B == 1) {
_1D::work();
} else if (B == 2) {
_2D::work();
} else {
_3D::work();
}
printf("%lld\n", res);
return 0;
}