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

题目: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;
}

评测记录:rid24052403 / 139ms / 2.75s / 3.45MB

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注