专栏文章

题解：P12751 [POI 2017 R2] 集装箱 Shipping containers

GGW_tzym
P12751题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mindd7bt
此快照首次捕获于
2025/12/02 00:34
3 个月前
此快照最后确认于
2025/12/02 00:34
3 个月前
查看原文
闲话
在某场神秘的比赛的T2，我想到了类似于根号分治的解法，但由于没有见过根号分治，所以阈值选错了，想来练练这种题，结果由于数组开小了，被虐的死去活来。。。遂写题解纪念一下
题意很清楚，讲一下为什么是根号分治。初看此题，我们有种十分简单且暴力的做法：模拟一遍，但这样的话复杂度是 O(∑l)O(\sum l) 的当 dd 很小的时候，ll 可能很大，导致超时。反过来当 dd 很大的时候，ll 不可能很大，原因就是他给的限制：
满足 a+d×(l−1)≤na+d \times (l-1) \le n
那这个 dd 多大才算大呢？答案是 n\sqrt n ~要不然叫根号分治~。对于大于 n\sqrt n 的 dd，我们直接暴力修改就行，对于 dd 小的情况呢？我们可以按 dd 分类，把操作记在差分数组里，然后 O(n)O(n) 做前缀和，答案累加，输出即可。
然后再给个提示（就是这个）数组要开到 2×1052 \times 10^5。因为他保证 a+d×(l−1)≤na+d \times (l-1) \le n 但没保证 a+d×l≤na+d \times l \le n，所以在差分时会越界。
CPP
#include<iostream>
#include<cmath>
using namespace std;
unsigned int ans[200010];
unsigned int c[200010][320];
int main()
{
    int n,k;
    cin>>n>>k;
    int num=sqrt(n);
    //int num=316;开静态的动态的都行，自己设一个也行
    for(int i=1;i<=k;i++)
    {
        int a,d,l;
        cin>>a>>l>>d;
        if(d>num)
        {
            for(int j=0;j<l;j++)
            {
                ans[a+(j*d)]++;
            }
        }
        else
        {
            c[a][d]++;
            c[a+(d*l)][d]--;
        }
    }
    for(int i=1;i<=num;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(j>=i)c[j][i]+=c[j-i][i];
            ans[j]+=c[j][i];
        }
    }
    for(int i=1;i<=n;i++)
    {
        cout<<ans[i]<<" ";
    }
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...