胡思乱想 #0
配合音乐食ī …
May all the beauty be blessed.
题目地址:洛谷:【P2827】蚯蚓 – 洛谷
本题中,我们将用符号 $\lfloor c \rfloor$ 表示对 c 向下取整,例如: $\lfloor 3.0 \rfloor = \lfloor 3.1 \rfloor = \lfloor 3.9 \rfloor = 3$。
蛐蛐国最近蚯蚓成灾了!隔壁跳蚤国的跳蚤也拿蚯蚓们没办法,蛐蛐国王只好去请神刀手来帮他们消灭蚯蚓。
蛐蛐国里现在共有 n 只蚯蚓( n 为正整数)。每只蚯蚓拥有长度,我们设第 i 只蚯蚓的长度为 ai ( i = 1, 2, … , n ),并保证所有的长度都是非负整数(即:可能存在长度为0的蚯蚓)。
每一秒,神刀手会在所有的蚯蚓中,准确地找到最长的那一只(如有多个则任选一个)将其切成两半。神刀手切开蚯蚓的位置由常数 p (是满足 0 < p < 1 的有理数)决定,设这只蚯蚓长度为 x ,神刀手会将其切成两只长度分别为 $\lfloor px \rfloor$ 和 $\lfloor x – px \rfloor$ 的蚯蚓。特殊地,如果这两个数的其中一个等于 0 ,则这个长度为 0 的蚯蚓也会被保留。此 外,除了刚刚产生的两只新蚯蚓,其余蚯蚓的长度都会增加 q(是一个非负整常数)。
蛐蛐国王知道这样不是长久之计,因为蚯蚓不仅会越来越多,还会越来越长。蛐 蛐国王决定求助于一位有着洪荒之力的神秘人物,但是救兵还需要 m 秒才能到来……(m 为非负整数)蛐蛐国王希望知道这 m 秒内的战况。
具体来说,他希望知道:
蛐蛐国王当然知道怎么做啦! 但是他想考考你……
输入格式:
第一行包含六个整数 n, m, q, u, v, t ,其中: n, m, q 的意义见【问题描述】; u, v, t 均 为正整数;你需要自己计算 p = u/v (保证 0 < u < v );t 是输出参数,其含义将会在【输出格式】中解释。
第二行包含 n 个非负整数,为 a1, a2, … , an ,即初始时 n 只蚯蚓的长度。
同一行中相邻的两个数之间,恰好用一个空格隔开。
保证 1 ≤ n ≤ 10^5 , 0 ≤ m ≤ 7 × 10^6 , 0 < u < v ≤ 10^9 , 0 ≤ q ≤ 200 , 1 ≤ t ≤ 71 ,
0 ≤ ai ≤ 10^8 。
输出格式:
第一行输出$\left\lfloor \frac{m}{t} \right\rfloor$个整数,按时间顺序,依次输出第 t秒,第 2t 秒,第 3t 秒,……被切 断蚯蚓(在被切断前)的长度。
第二行输出$\left\lfloor \frac{n+m}{t} \right\rfloor$个整数,输出 m 秒后蚯蚓的长度:需要按从大到小的顺序,依次输出排名第 t ,第 2t ,第 3t ,……的长度。
同一行中相邻的两个数之间,恰好用一个空格隔开。即使某一行没有任何数需要输出,你也应输出一个空行。
请阅读样例来更好地理解这个格式。
输入样例#1:
3 7 1 1 3 1 3 3 2
输出样例#1:
3 4 4 4 5 5 6 6 6 6 5 5 4 4 3 2 2
输入样例#2:
3 7 1 1 3 2 3 3 2
输出样例#2:
4 4 5 6 5 4 3 2
输入样例#3:
3 7 1 1 3 9 3 3 2
输出样例#3:
2
很容易想到用三个堆来维护原来的蚯蚓、切后的两段蚯蚓,通过一定的修正将堆内的各个元素统一至某一时间点(如,最开始的长度),便于堆内元素值的比较。可以用当前值-当前秒数作为修正值。
在这种做法的基础上,我们观察到,由于每次都是取最大的来切,切后的两段蚯蚓分别对应的两个序列内部实际上有随时间递增而不减的单调性。我们直接将堆换为队列即可得到本题的正解。
正解复杂度$O(m)$。
// Code by KSkun, 2018/11
#include <cstdio>
#include <cctype>
#include <cmath>
#include <algorithm>
#include <functional>
#include <vector>
typedef long long LL;
inline char fgc() {
static char buf[100000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
? EOF : *p1++;
}
inline LL readint() {
register LL res = 0, neg = 1; register char c = fgc();
for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
for(; isdigit(c); c = fgc()) res = res * 10 + c - '0';
return res * neg;
}
inline char readsingle() {
register char c;
while(!isgraph(c = fgc())) {}
return c;
}
const int MAXN = 100005, MAXM = 7000005;
int n, m, q, u, v, t, a[MAXN];
double p;
std::vector<int> vec;
struct Queue {
int l, r, a[MAXM];
Queue(): l(1), r(1) {}
inline void push(int x) {
a[r++] = x;
}
inline void pop() {
if(l >= r) return; l++;
}
inline int query(int p, int t) {
if(l >= r) return -1;
return a[l] + (p - 1) * q * (1 - t) + (p - l - 1) * q * t;
}
inline bool empty() {
return l >= r;
}
} que[3];
inline void query(int x, int &res, int &t) {
int r1 = que[0].empty() ? -1 : que[0].query(x, 0),
r2 = que[1].empty() ? -1 : que[1].query(x, 1),
r3 = que[2].empty() ? -1 : que[2].query(x, 1);
if(r1 > res) {
res = r1; t = 0;
}
if(r2 > res) {
res = r2; t = 1;
}
if(r3 > res) {
res = r3; t = 2;
}
}
int main() {
n = readint(); m = readint(); q = readint();
u = readint(); v = readint(); t = readint();
p = double(u) / v;
for(int i = 1; i <= n; i++) a[i] = readint();
std::sort(a + 1, a + n + 1, std::greater<int>());
for(int i = 1; i <= n; i++) que[0].push(a[i]);
for(int i = 1; i <= m; i++) {
int res = -1, t = -1;
query(i, res, t);
if(i % ::t == 0) printf("%d ", res);
que[t].pop();
que[1].push(floor(p * res));
que[2].push(res - floor(p * res));
}
puts("");
while(!que[0].empty()) {
vec.push_back(que[0].query(m + 1, 0));
que[0].pop();
}
while(!que[1].empty()) {
vec.push_back(que[1].query(m + 1, 1));
que[1].pop();
}
while(!que[2].empty()) {
vec.push_back(que[2].query(m + 1, 1));
que[2].pop();
}
std::sort(vec.begin(), vec.end(), std::greater<int>());
for(int i = 0; i < vec.size(); i++) {
if((i + 1) % t == 0) printf("%d ", vec[i]);
}
return 0;
}
由于博主高考完了,本文不再更新。
我们在做运动学图像题的时候总是会面临一些非传统的运动学图像,在这篇文章中,我将归总我遇到过的有趣的创新图像题以及分析方法。
(多选)放在水平面上的物体,在水平力$F$作用下开始运动,以物体静止时的位置为坐标原点,力$F$的方向为正方向建立$x$轴,物体的加速度随位移的变化图像如图所示。下列说法中错误的是
A. 位移为$x_1$时,物体的速度大小为$\sqrt{2a_0x_1}$
B. 位移为$x_2$时,物体的速度达到最大
C. 物体的最大速度为$\sqrt{a_0(x_2+x_3)}$
D. $0 \sim x_2$过程中物体做匀加速直线运动,$x_2 \sim x_3$过程中物体做匀减速直线运动
题目来源:放在水平面上的物体,在水平力F作用下开始运动,以物体静止时的位置为坐标原点,力F的方向为正方向建立x轴,物体的加速度随位移的变化图像如图所示… 满分5满分网
【解析】
本题给了一个$a-x$图像。我们注意到,在$x_2 \sim x_3$段的图像是一条直线,这是随时间增大均匀减小的加速度吗?显然不是。
在与计算无关的情况下,我们可以认为$x$轴就是原来$a-t$图像的$t$轴,只是这根轴上的数值分布不均匀。用这种方法可以定性分析运动的相关情况。我们发现,在整个运动中物体都在加速。
在需要计算的情况下,我们显然无法使用观察图像的方法获得速度的变化量。对于这个图像,我们能使用的公式只有$v_t^2 – v_0^2 = 2ax$这一个了。然而用好它也能解决很多问题。
接下来我们逐选项地分析题目。
A项,在$x_1$处使用公式$v_1^2 – 0 = 2a_0x_1$,即可求出$v_1=\sqrt{2a_0x_1}$,本项是正确的。
B项,由于全段都在加速,$x_3$才是速度达到最大的时候的位移值。
C项,最大速度显然要计算$x_3$处的速度$v_3$,但是问题来了,这是一个变加速直线运动,我们无法利用传统方法求解了,还有什么其他的办法呢?观察公式$v^2=2ax$,$ax$不就是图形的面积吗?我们可以求出图形的面积为$S=\frac12(x_2+x_3)a_0$,代入上面的公式,得到了我们要求的速度$v_3^2=(x_2+x_3)a_0$,即$v_3=\sqrt{(x_2+x_3)a_0}$。
D项,$x_2 \sim x_3$段加速度恒为正,物体在做匀加速运动。
最后还有一个坑,题目要求选出错误的,因此应该选择BD两项。
本题解决非传统问题的方法是,通过公式得到非传统图像的面积意义,从而解决非传统问题。看来,对于图像与公式的意义把握是解决问题的重要手段。
(多选)甲、乙两质点在同一时刻、同一地点沿同一方向做直线运动。质点甲做初速度为零,加速度大小为$a_1$的匀加速直线运动。质点乙做初速度为$v_0$,加速度大小为$a_2$的匀减速直线运动至速度减为零保持静止。甲、乙两质点在运动过程中的$x-v$(位置速度)图象如图所示(虚线与对应的坐标轴垂直)。则
A. 在$x-v$图象中,图线$a$表示质点甲的运动,质点乙的初速度$v_0=6 \ \mathrm{m/s}$
B. 质点乙的加速度大小$a_2=2 \ \mathrm{m/s^2}$
C. 质点甲的加速度大小$a_1=2 \ \mathrm{m/s^2}$
D. 图线$a$、$b$的交点表示两质点同时到达同一位置
题目来源:【甲、乙两质点在同一时刻、同一地点沿同一方向做直线运动.质点甲做初速度为零,加速度大小为a1的匀加速直线运动.质点乙做初速度为v0,加速度大小为a2的匀减速直线运动至速度减为零】作业帮
【解析】
这又是一个不按套路来的题目,我们习惯了看$x-t$图像以后看这个怎么看怎么不舒服,于是就容易做错。不过由于可以通过图像推导出一些常规结论,相比需要利用图形面积意义的题目还是要简单些。
A项,容易知两物体都是从$x=0$位置开始运动,由于乙有初速度,因此乙对应图线$b$,甲对应$a$。查起始位置处速度得知$v_{0}=6 \ \mathrm{m/s}$。
B项与C项,这样的图线应当如何计算加速度成为了一个问题。计算的困难来自于图形的关键点都只给了半边信息,有横坐标信息的关键点没给纵坐标,有纵坐标的没给横坐标,不过不要虚,要相信题是能做出来的,我们按部就班地来准备方程:
不妨关注共速的位置,假设二者共同速度为$v$:
对甲:
$$ v^2 = 2a_1x \tag{1}$$
对乙:
$$ v_0^2 – v^2 = 2a_2x \tag{2} $$
联立(1)式和(2)式,得到$a_1+a_2=3 \ \mathrm{m/s^2} \tag{*1}$
我们再取一个共位移的位置,此时$v_1=8 \ \mathrm{m/s}$,$v_2=2 \ \mathrm{m/s}$,假设二者位移都是$x$:
对甲:
$$ v_1^2 = 2a_1x \tag{3} $$
对乙:
$$ v_0^2 – v_2^2 = 2a_2x \tag{4} $$
联立(3)和(4),得到$a_1=2a_2 \tag{*2}$
到此为止,我们已经可以通过(*1)和(*2)得到答案为$a_1=2 \ \mathrm{m/s^2}, a_2=1 \ \mathrm{m/s^2}$。从而判断C正确,B错误。
对于D项,交点表示两物体的速度相同且位移相同的一个状态,但是不一定要同时达到,基于数据的分析也可以证明确实不是同时达到的。
我们可以发现,给半边条件也是有用的,因为有两个物体,每个物体列出一个式子,设一个未知数,就可以在两个式子间消元获得足够的信息了。
研究人员测得飞机着陆后若不制动在平直跑道上滑行的总距离为$x$,所用的时间为$t$。考虑到飞机的滑行速度越小,所受的阻力越小,则飞机着陆时的速度应为
A. $v < \frac{x}{t}$
B. $\frac{x}{t} < v < \frac{2x}{t}$
C. $v = \frac{2x}{t}$
D. $v > \frac{2x}{t}$
题目来源:《高考小题练透 物理》(67高考,外研社)、【某同学欲估算飞机着陆时的速度,他假设飞机在平直跑道上做匀减速运动,飞机在跑道上滑行的距离为x,从着陆到停下来所用的时间为t,实际上,飞机的速度越大,所受的阻力越大,即加】作业帮
【解析】
由于阻力随滑行速度减小而减小,减速的加速度大小是在减小的,因此$v-t$图像看上去应该是下凸的,这就给我们估计$t=0$时的速度带来了麻烦,毕竟我们并不知道它和平均速度的关系。
为了解决这个问题,我们不妨假设一个在$t$时间内的匀减速运动,并把图像和题目中这个运动的图像做到一起,观察我们将得到什么。
这个匀减速运动的平均速度显然是$\frac{v}{2}$,而题目中这个运动的位移是小于匀减速运动的,因此平均速度也要小于匀减速的,即$\frac{x}{t} < \frac{v}{2}$,便推知了$v > \frac{2x}{t}$这一结论。
有的运动我们并不熟悉,也不好用已有的运动学手段甚至是数学手段来处理它的(图像)问题,我们可以利用与上面类似的“假设”思想发现新的突破口。