T1
使用 \(bfs\) 记录走到 \(tx,ty\) 的路径的横边和竖边的数量，然后取 \(\max\)。这里取 \(\max\) 的原因是，找到的路径必须是最短路，当 \(k\) 取的小的时候竖边就会变多，所以这条路径就不一定是最短路了。
#include<bits/stdc++.h>
using namespace std;
#define p pair<int, int>
int n, m, sx, sy, tx, ty;
int dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
bitset<105> mp[105], vis[105];
double s;
struct node{ int x, y, w, h; };
queue<node> q;
vector<p> vec;
int main(){
freopen("msg.in", "r", stdin); freopen("msg.out", "w", stdout);
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin>>n>>m>>sx>>sy>>tx>>ty;
for(int i=1, x; i<=n; ++i) for(int j=1; j<=m; ++j)
cin>>x, mp[i][j] = x;
cin>>s;
q.emplace(node{sx, sy, 0, 0});
while(!q.empty()){
auto t = q.front(); q.pop();
int ux = t.x, uy = t.y;
vis[ux][uy] = 1;
for(int i=0; i<4; ++i){
int vx = ux + dir[i][0], vy = uy + dir[i][1];
if(vx < 1 || vy < 1 || vx > n || vy > m || mp[vx][vy] || vis[vx][vy]) continue;
int tmpw = t.w, tmph = t.h;
dir[i][0] ? ++tmph : ++tmpw;
if(vx == tx && vy == ty){
vec.emplace_back(p{tmpw, tmph});
continue;
} vis[vx][vy] = 1;
q.emplace(node{vx, vy, tmpw, tmph});
}
} double ans = 0.0;
for(auto it : vec){
int w = it.first, h = it.second;
if(w * 1.0 > s) continue;
ans = max(ans, 1.0 * (s - 1.0 * w) / h);
} return cout<<fixed<<setprecision(3)<<ans, 0;
}
T3 摸鱼军训
考虑每一次冒泡都会把一个大数提到序列最后面，那么相应地就会有较小的数向前移动。那么就可以大致描述某一个数的移动过程：先向前走一段，再向后走一段。显然有每个数向前走的距离为这个数前面比它大的数的数量，称为 \(lm_i\)，如果查询的 \(k\) 要小于等于 \(lm_i\)，那么答案即为 \(pos_i-k\)。
对于向后走的一段，考虑使用一个队列来更直观的维护这个东西。每一次冒泡之前都将向前走走完的数加到队列中去，这个队列一定是单调递增的。对于如下队列：(中间加点是为了凸显在原数列中的位置)
\[4 \dots5\dots6\dots7 \]那么下一次冒泡，序列变化如下：
\[\begin{split} 4 \dots5\dots6\dots7\\\ \dots4\dots5\dots67\\ \dots4\dots567 \end{split} \]可以发现的是每一次冒泡，队列里的每一个数，都会移动到它的下一个数的屁股后面。又因为队列里的数的顺序是按照向前移动完的时间加进去的，那么比 \(x\) 大的数一定会先加入队列中。那么对于第一次移动，\(x\)会移动到 第一个大于它的数 \(y\) 的屁股后面，也就是 \(pos_y-1\)，第二次移动时，\(y\) 会移动到 \(z\) 的屁股后面，所以 \(pos_y=pos_z-1\)，然后 \(x\) 移动到 \(y\) 的后面 \(pos_x=pos_y-1=pos_z-2\)。规律显然。对于第 \(k\) 次移动，在队列里第 \(k\) 个的数的位置为 \(pos_k\)，那么答案即为 \(pos_k-k\)。又因为在队列里比他靠前的数只能是比它大的数，那么就在原序列里找从左往右数第 \(k\) 个大于它的数的 \(pos\) 即可。
#include<bits/stdc++.h>
using namespace std;
constexpr int B = 1<<20;
char buf[B], *p1 = buf, *p2 = buf, obuf[B], *O = obuf;
#define gt() (p1==p2 && (p2=(p1=buf)+fread(buf, 1, B, stdin), p1==p2) ? EOF : *p1++)
template <typename T> inline void rd(T &x){
x = 0; int f = 0; char ch = gt();
for(; !isdigit(ch); ch = gt()) f ^= ch == '-';
for(; isdigit(ch); ch = gt()) x = (x<<1) + (x<<3) + (ch^48);
x = f ? -x : x;
}
template <typename T, typename ...TT> inline void rd(T &x, TT &...xx){ rd(x), rd(xx...); }
#define pt(ch) (O-obuf==B && (fwrite(obuf, 1, B, stdout), O=obuf), *O++ = (ch))
template <typename T> inline void wt(T x){
if(x > 9) wt(x / 10); pt(x % 10 ^ 48);
}
#define fw fwrite(obuf, 1, O - obuf, stdout)
#define p pair<int, int>
constexpr int N = 5e5 + 5;
int n, q, a[N], ans[N], pos[N], lm[N];
vector<p> Q[N];
namespace BIT{
#define lb(x) ((x) & (-x))
int t[N];
inline void add(int pos, int val){
for(; pos<=n; pos+=lb(pos)) t[pos] += val;
}
inline int query(int pos){
int res = 0;
for(; pos>0; pos-=lb(pos)) res += t[pos];
return res;
}
}
namespace ST{
#define ls (id << 1)
#define rs (id << 1 | 1)
struct node{ int l, r, sum; }t[N<<2];
inline void build(int id, int l, int r){
t[id] = node{l, r, 0};
if(l == r) return;
int mid = (l + r) >> 1;
build(ls, l, mid), build(rs, mid+1, r);
}
inline void modify(int id, int pos){
if(t[id].l == t[id].r) return t[id].sum = 1, void();
int mid = (t[id].l + t[id].r) >> 1;
modify((pos <= mid) ? ls : rs, pos);
t[id].sum = t[ls].sum + t[rs].sum;
}
inline int query(int id, int val){
if(t[id].l == t[id].r) return t[id].l;
int mid = (t[id].l + t[id].r) >> 1;
if(t[ls].sum >= val) return query(ls, val);
return query(rs, val-t[ls].sum);
}
}
int main(){
freopen("bubble.in", "r", stdin); freopen("bubble.out", "w", stdout);
rd(n); for(int i=1; i<=n; ++i){
rd(a[i]), BIT::add(a[i], 1);
lm[a[i]] = i - BIT::query(a[i]);
pos[a[i]] = i;
}
rd(q); for(int i=1, k, x; i<=q; ++i){
rd(k, x);
if(lm[x] >= k) ans[i] = pos[x] - k;
else if(n - x < k) ans[i] = x;
else Q[x].emplace_back(p{k, i});
}
ST::build(1, 1, n);
for(int i=n; i>=1; --i){
for(auto it : Q[i]){
int ps = ST::query(1, it.first);
ans[it.second] = ps - it.first;
} ST::modify(1, pos[i]);
}
for(int i=1; i<=q; ++i) wt(ans[i]), pt(10);
return fw, 0;
}