[洛谷题解] CF567D One-Dimensional Battle Ships

发布于 2019-09-20  462 次阅读

题目：CF567D One-Dimensional Battle Ships

题意翻译的修正

接下来，Bob会用m颗炮弹尝试打中Alice的战舰，每颗炮弹会选择一个格子打击。但由于Alice喜欢作弊，所以她不会告诉Bob什么时候击中了战舰。请你帮助Bob判断，在第几次发射炮弹后，Alice一定会有一艘战舰被击中。

应该理解成

接下来，Bob会用m颗炮弹尝试打中Alice的战舰，每颗炮弹会选择一个格子打击。但由于Alice喜欢作弊，所以她不会告诉Bob什么时候击中了战舰。请你帮助Bob判断，在第几次发射炮弹后，他就能判定Alice一定在作弊（并拆穿她）。

并且，此题中Alice实际上是一直在用“未击中”回应Bob发射炮弹的操作。

解题思路

一开始，我们可以将地图看做一个连续区间。我们认为这个区间被染成了颜色1。利用小学数学功底， 很容易发现，对于一个长度为sz的区间，最多可以放置floor(\frac{sz+1}{len+1})个战舰（题目要求战舰不能互相连接，也不能重叠）。

显然，Bob每扔出一颗炮弹，都会将炮弹打中的区间分成两块（此处我们允许其中一块或者两块长度是0）。

按照朴素的思路，我们可以在每次打击之后对于每个区间计算出能放置的战舰数量，最后相加。如果发现，这些区间已经不能容纳题目中的k艘战舰，那么显然Alice就作弊了。（显然也没有别的情况了）

实现细节

我们用一个树状数组2（区间修改，单点查询）维护每个点所属的区间（后称颜色），并维护每种颜色的左右端点。

一开始，我们将树状数组的值全部赋值为1，并将1的范围设定为[1,n]
，代表整个连续的区间。

随后，如果一颗子弹落在pos位置，范围为[l,r]的区间上，那么区间被拆成两个，分别是[l,pos-1]和[pos+1,r]（此处无需考虑边界，因为如果某区间的大小变成了0，这个区间在以后就没有存在感了，因为她不会再被打中）。我们将区间[l,pos-1]保持原有的颜色，然后将区间[pos,pos]颜色变成-1，最后将[pos+1,r]变成一个新的颜色（由于这个区间原本就是清一色的，再染成一种颜色可以通过树状数组2完成）。

至于统计，将变量cnt初始化为原来整个区间的容纳量。每次区间拆分时，先减去原有区间的容量，在加上得到的两个区间的容量，就可以了。

代码与评测记录

// status: [Accepted]
// oj:     [luogu]

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 300001;
int n,m,len;
int ct = 0;
int lcolor[MAXN];
int rcolor[MAXN];
int cnt = 0;

//树状数组（区间修改，单点查询）
template<class T,int len>
struct CycOkIai{
    //数据表（无必要时请勿从外部访问）
    int data[len+1];

    //清空树状数组（初始化时无需调用）
    void clear() {
        for(int i=1;i<=len;i++) {
            data[i]=0;
        }
    }

    //返回正整数删除所有非最后一个1的结果
    int lowbit(int x) {return x&(-x);}

    //更新数据，将idx-n加上一个数
    void delta(int idx,int val=0) {
        while(idx<=n) {
            data[idx]+=val;
            idx+=lowbit(idx);
        }
    }

    //更新数据，将l-r加上一个数
    void update(int l,int r,int val=0) {
        delta(l,val);
        delta(r+1,-val);
    }

    //查询位于idx的数据
    int at(int idx) {
        int ret=0;
        while(idx) {
            ret+=data[idx];
            idx-=lowbit(idx);
        }
        return ret;
    }
};

CycOkIai<int,MAXN> col;

inline int capacity(int id) {
    int sz = rcolor[id] - lcolor[id] + 1;
    return (sz+1)/(len+1);
}

int main() {
    ios::sync_with_stdio(false);
    cin>>n>>m>>len;
    ++ct;
    col.update(1,n,ct);
    lcolor[ct] = 1;
    rcolor[ct] = n;

    cnt = capacity(1);

    if(cnt < m) {cout<<"0"<<endl;return 0;}

    int T;
    cin>>T;
    for(int t=1;t<=T;t++) {
        int pos;
        cin>>pos;
        if(col.at(pos)==-1) continue;
        int cc = col.at(pos);
        cnt -= capacity(cc);
        ++ct;
        rcolor[ct] = rcolor[cc];
        rcolor[cc] = pos - 1;
        lcolor[ct] = pos + 1;
        col.update(lcolor[ct],rcolor[ct],ct-cc);
        col.update(pos,pos,-1-cc);
        cnt += capacity(cc) + capacity(ct);
        if(cnt < m) {cout<<t<<endl;return 0;}
    }

    cout<<-1<<endl;
}

评测记录：R24052403

赏

undefined