显然我们想画出矩形只需获得该矩形横轴上的区间 及纵轴上的区间 即可。所以遍历每个 # ,获得行列坐标的最值，得到原矩形，再遍历一遍原矩形，寻找字符 . 即可。
// 获取 x_min, x_max, y_min, y_max
for (LL i = 1; i <= H; i ++){
for (LL j = 1; j <= W; j ++){
cin >> G[i][j];
if (G[i][j] == '#')
x1 = min(x1, i), x2 = max(x2, i), yy1 = min(yy1, j), y2 = max(y2, j);
}
}
// 寻找'.'
for (LL i = x1; i <= x2; i ++){
for (LL j = yy1; j <= y2; j ++){
if (G[i][j] == '.')
cout << i << " " << j << "\n";
}
}
首先， 为无用数据，直接不要。接下来每两个数据都是一个区间 ，表示一次睡眠，一共有 个，输入时即进行前缀和统计， 表示在第 次睡眠结束时一共睡的时刻数。
询问 内睡了多久可用类差分思想，转化为 。 表示 从时刻 至时刻 一共的睡眠时间。
对于 ，可以二分查找在时刻 之前最后一次完整的睡眠，设此睡眠为第 次， 如果 ，即在时刻 时下一次睡眠开始了但未结束，则 ，否则 。
主要的计算 代码如下：
// T[i](1 <= i <= n) 表示第 i 个睡眠区间。
// T[i].L, T[i].R, 表示 第 i 个睡眠区间的开始时刻与结束时刻。
// T[i].sum 表示第 i 个睡眠区间结束时一共的睡眠时间(前缀和)。
// 此处的 n 为 (原来的 N + 1) / 2, 也就是睡眠次数。
LL calc(LL x){
LL L = 0, R = n;
while (L + 1 < R){
LL Mid = (L + R) >> 1;
if (T[Mid].R > x){
R = Mid;
}
// 若 x 正好为第 Mid 个睡眠区间的结尾，直接可以返回 T[Mid].sum。
else if (T[Mid].R == x)
return T[Mid].sum;
else
L = Mid;
}
LL tmp = L;
if (T[R].R <= x)
tmp = R;
// 以上代码用二分找到时刻 x 前最后一个完整的睡眠区间
// 以下代码计算时间
if (x >= T[tmp + 1].L)
return T[tmp].sum + (x - T[tmp + 1].L);
return T[tmp].sum;
}
没什么好说的，比较水。
使用类广搜思想。
且处理时显然先处理耐力 值最高的最优。使用 priority_queue 或手写堆。
// 注意 Priority_queue 要以 h (y) 为关键字，这样才能保证先取到耐力值 h 最高的。
// 此处 x 表示 p 值，y 表示 h 值。
for (LL i = 1; i <= K; i ++){
cin >> x >> y;
pq.push(make_pair(y, x));
}
// Len 表示遍历到了几个结点，也就是能被守卫到的结点数。
LL Len = 0;
// 类广搜。
while (!pq.empty()){
LL x = pq.top().second, y = pq.top().first; pq.pop();
// 如果已经被遍历过，肯定不如上一次优，因为上一次 h 值一定大于这一次，所以跳过
if (vis[x])
continue;
vis[x] = 1;
++ Len;
if (y == 0)
continue;
for (auto v : G[x]){
if (!vis[v])
pq.push(make_pair(y - 1, v));
}
}
// 输出
cout << Len << "\n";
for (LL i = 1; i <= n; i ++)
if (vis[i])
cout << i << " ";