题解：P14557 [ROI 2013 Day2] 海战

wanganze · 2025-12-05 14:43:07 · 题解

背景

参考了官方题解。

题意

有一条 1\times n 的方格，要放 t 条长度为 k 的船，两条船至少间隔一格。

给定一些攻击，如果打到了一定有船的格子，那么结束程序，否则说明这里没有船。求每个时刻一定有船的格子个数。

保证数据合法。

分析

先看最开始的情况：我们知道这条格子最多装下 \lfloor\frac{len+1}{k+1}\rfloor 条船。如果 t<\lfloor\frac{len+1}{k+1}\rfloor，那么每一个格子都不能保证有船（有至少一整条船的空位，可以腾出来给每条船）；否则有 x=(len+1)\bmod(k+1) 个空位，船可以左右滑动，但每条船都能确定 k-x 个格子（其实可能是 0 个），所以总共有 t \times (k-x) 个格子一定有船。

最开始的问题是算区间 [1,n] 的能确定格子的个数。

每次攻击，我们找到攻击目标所在的区间，把它从攻击的位置裂成两段，更新答案。这个过程可以用 set 维护。

实现

#include<bits/stdc++.h>
using namespace std;
int n,t,k,ship,cnt;
struct Itv
{
    int l,r;
    int len()
    {
        return r - l + 1;
    }
    int s()
    {
        return (len() + 1) / (k + 1);
    }
    int c()
    {
        return max(0,s() * (k - (len() + 1) % (k + 1)));
    }
    bool operator < (const Itv &a) const
    {
        return l < a.l;
    }
};
set<Itv> s;
void add(Itv x)
{
    if(x.l <= x.r) s.insert(x),ship += x.s(),cnt += x.c();
} 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>t>>k;
    add({1,n});
    if(ship == t) cout<<cnt<<endl;
    else cout<<0<<endl;
    while(1)
    {
        int tar;
        cin>>tar;
        Itv x = *(-- s.upper_bound({tar,tar}));
        s.erase(x),ship -= x.s(),cnt -= x.c();
        add({x.l,tar - 1}),add({tar + 1,x.r});
        if(ship < t)
        {
            cout<<1<<endl;
            return 0;
        }
        cout<<"0 ";
        if(ship == t) cout<<cnt<<endl;
        else cout<<0<<endl;
    }
    return 0;
}