P6971

Daben1 · 2022-08-15 22:29:08 · 题解

题意&思路简述

长宽高分别为 w，nw，1 的长方体，每层摆放 n 个形成 nw×nw×1 的底面为正方形的几何体。

每两层交替摆放，即呈“井”字形加高，共 h 层。

面对几何体的一个棱边，按从近到远令每次的 n 个长方体编号为 1，2，3…

现在依次给出 m 个 l k，表示第 idx 次，将第 l 层第 k 个长方体去除。

求在第几次操作时会使得几何体倒塌?

由此可见，本题操作并不复杂，且有顺序性。

直接开始大模拟。

解题思路

对每次操作判断最顶上 top 层的重心位置是否落在 h-top-1 层的可稳定范围内。

重心可简单的视作是前 top 层的剩余块的编号和 (等同于坐标和)除以前 top 层的剩余总块数。

其中，由于层次的摆放一次交替呈井字形 。故如果对奇数层移除一块长方体，偶数层应特殊处理。

AC代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int n, w, h, m;
bool flr[2][2501][10001];
int lft[2][2501], rgt[2][2501];
int cet[2][2501], num[2][2501];
int cmp(double x) {
    if(abs(x) < 1e-8)    return 0;
    return x > 0 ? 1 : -1;
}
bool jug(double center, double left, double right) {
    if(cmp(center - left) <= 0 || cmp(center - right) >= 0)
        return false;
    return true;
}
int main(){
    scanf("%d %d %d %d", &n, &w, &h, &m);
    memset(flr, true, sizeof(flr));
    long long lmt = (1+n) * n / 2;
    for(int i=1;i<=h;i++){
        cet[i%2][(i+1)/2] = lmt;
        num[i%2][(i+1)/2] = n;
        lft[i%2][(i+1)/2] = 1;
        rgt[i%2][(i+1)/2] = n;
    }
    for(int idx=1, l, k;idx<=m;idx++){
        scanf("%d %d", &l, &k);
        bool flg = l % 2;
        l = (l+1)/2;
        flr[flg][l][k] = 0;
        cet[flg][l] -= k;
        num[flg][l]--;
        for(int i=1;i<=n;i++)
            if(flr[flg][l][i] == true) {
                lft[flg][l] = i;
                break;
            }
        for(int i=n;i;i--)
            if(flr[flg][l][i] == true) {
                rgt[flg][l] = i;
                break;
            }
        double tCet = 0, tNum = 0;
        for(int i=h;i;i--){
            if(cmp(tNum) == 1 && flg == i%2) {
                double center = tCet * 1.0 / tNum;
                if(jug(center, lft[flg][(i+1)/2] - 0.5, rgt[flg][(i+1)/2] + 0.5) == false) {
                    printf("yes\n%d\n", idx);
                    return 0;
                }
            }
            if(i%2 == flg)
                tCet += cet[flg][(i+1)/2],
                tNum += num[flg][(i+1)/2];
            else
                tCet += num[!flg][(i+1)/2] * (1.0+n)/2.0,
                tNum += num[!flg][(i+1)/2];
        }
    }
    printf("no\n");
}