首页 > 其他分享 >P2468 [SDOI2010] 粟粟的书架

P2468 [SDOI2010] 粟粟的书架

时间:2024-12-06 12:09:56浏览次数:4  
标签:粟粟 cnt le return val int SDOI2010 P2468

P2468 [SDOI2010] 粟粟的书架

题意简述:

给你一个矩阵,每次给定一个矩形和一个值 \(h\) ,让你在这个矩形中选 $ k$ 个数使得这 \(k\) 个数的和 \(\ge h\) 且最小化这个 \(k\)

对于 \(50\%\) 的数据,满足 \(R, C\le 200\),\(M\le 2\times 10^5\)。

另有 \(50\%\) 的数据,满足 \(R=1\),\(C\le 5\times 10^5\),\(M\le 2\times 10^4\)。

对于 \(100\%\) 的数据,满足 \(1\le P_{i,j}\le 1000\),\(1\le H_i\le 2\times 10^9\)。

Solution:

看到这个猎奇的数据范围我们就知道这题肯定不简单,首先我们来看一下后50分怎么拿:

不难想到我们可以建一颗可持久化权值线段树,然后在主席树上查询在 \([-rt_{l-1}+rt[r]]\) 的答案,具体实现就是权值线段树上尽量往右子树跳,\(k \ge t[x].val\) 就全部取。

然后再来说一下前50分怎么拿,注意到:  

满足 \(1\le P_{i,j}\le 1000\),\(R, C\le 200\)

我们可以开一个$ sum[R][C][inf] $ 一个二维前缀和\(sum{i,j,k}\)来存
\((1,1)(i,j)\) 这个矩形内权值等于 \(k\) 的数量

然后对于每个查询,直接暴力从 \(1000 -> 1\) 扫一遍然后统计答案就好了

Code

#include<bits/stdc++.h>
using namespace std;
int n,m,q;
struct Solve1
{
    #define N 500005
    #define inf 2000000000
    //Segment_Tree
    struct Segment_Tree{
    int rt[N],cnt=0;
    struct Tree{
        int ls,rs,val,cnt;
    }t[N*40];
    void insert(int &x,int y,int l,int r,int k)
    {
        t[x=++cnt] = t[y];
        t[x].val+=k;t[x].cnt++;
        if(l==r)return;
        int mid=l+r>>1;
        if(k<=mid)insert(t[x].ls,t[y].ls,l,mid,k);
        if(mid<k)insert(t[x].rs,t[y].rs,mid+1,r,k);
    }
    void query(int x,int y,int l,int r,int L,int R,int &k,int &cnt)
    {
        if(k<=0)return ;
        int Val=-t[x].val+t[y].val,Cnt=-t[x].cnt+t[y].cnt;
        if(L<=l&&r<=R&&k>=Val)
        {
            k-=Val;
            cnt+=Cnt;
            return;
        }
        if(l==r)
        {
            int val=Val/Cnt;
            cnt+=(k/val);
            k-=(k/val)*val;
            if(k){cnt++;k-=val;}
            return;
        }
        int mid=l+r>>1;
        if(mid<R)query(t[x].rs,t[y].rs,mid+1,r,L,R,k,cnt);
        if(L<=mid) query(t[x].ls,t[y].ls,l,mid,L,R,k,cnt);
    }
    }T;
    void work()
    {
        for(int i=1,x;i<=m;i++)
        {
            scanf("%d",&x);
            T.insert(T.rt[i],T.rt[i-1],1,inf,x);
        }
        for(int i=1;i<=q;i++)
        {
            int l,r,x,y,k;
            scanf("%d%d%d%d%d",&x,&l,&y,&r,&k);
            int ans=0;
            if(-T.t[T.rt[l-1]].val+T.t[T.rt[r]].val<k){printf("Poor QLW\n");continue;}
            T.query(T.rt[l-1],T.rt[r],1,inf,1,inf,k,ans);
            printf("%d\n",ans);
        }
    }
    #undef N
    #undef inf

}S_1;
struct Solve_2{
    #define N 205
    #define inf 1005
    int sum[N][N][inf],a[N][N];
    void work()
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                scanf("%d",&a[i][j]);
                sum[i][j][a[i][j]]++;
            }
        }
        for(int i=2;i<=n;i++)for(int k=1;k<=1000;k++)sum[i][1][k]+=sum[i-1][1][k];
        for(int j=2;j<=m;j++)for(int k=1;k<=1000;k++)sum[1][j][k]+=sum[1][j-1][k];
        for(int i=2;i<=n;i++)for(int j=2;j<=m;j++)for(int k=1;k<=1000;k++)
        {
            sum[i][j][k]=sum[i-1][j][k]+sum[i][j-1][k]-sum[i-1][j-1][k]+sum[i][j][k];
        }
        for(int i=1;i<=q;i++)
        {
            int x_0,y_0,x_1,y_1,h,ans=0;
            scanf("%d%d%d%d%d",&x_0,&y_0,&x_1,&y_1,&h);
            for(int k=1000;k;k--)
            {
                int cnt=sum[x_1][y_1][k]-sum[x_1][y_0-1][k]-sum[x_0-1][y_1][k]+sum[x_0-1][y_0-1][k];
                if(h>(k*cnt))
                {
                    ans+=cnt;
                    h-=(k*cnt);
                }
                else
                {
                    ans+=(h/k);
                    h-=((h/k)*k);
                    while(h>0)
                    {
                        ans++;
                        h-=k;
                        
                    }
                    break;
                }
            }
            if(h>0)printf("Poor QLW\n");
            else printf("%d\n",ans);
        }

    }

    #undef N
    #undef inf
}S_2;
int main()
{
    //freopen("P2468.in","r",stdin);freopen("P2468.out","w",stdout);
    cin>>n>>m>>q;
    if(n==1)S_1.work();
    else S_2.work();
    return 0;
}

标签:粟粟,cnt,le,return,val,int,SDOI2010,P2468
From: https://www.cnblogs.com/LG017/p/18590477

相关文章

  • LOJ#2885. 「SDOI2010」猪国杀
    对拍器在此。https://www.luogu.com/discuss/81283献忠!AC代码modoiread{usestd::{io::{stdin,Read},ops::{Add,Mul,Neg},};pubfnnext()->u8{letmuta=stdin().lock();letmutc=[0u8];matcha......
  • [SDOI2010] 猪国杀
    猪国杀前言这道题是一道大模拟,个人认为还是挺锻炼码力的,所以本蒟蒻花一天的时间,爆肝一周的时间终于写完了。。。题意题目传送门游戏目的主猪/MP\texttt{MP}MP:自己......
  • 洛谷 P2478 [SDOI2010] 城市规划 题解
    题意简述仙人掌上求至少间隔两个位置的最大独立集。(仙人掌指,没有一条边在两个或以上的环里的无向图。)题目分析仙人掌就是树套环,即树上每个结点都是一个结点或环。那么将题目拆解成树上DP和环上DP即可。用tarjan缩点即可。树上DP先来看看树上DP。显然每个点有三个状......
  • P2482 [SDOI2010] 猪国杀 代码(暂未完成)
    #include<bits/stdc++.h>usingnamespacestd;namespacework{constintmaxPlayerNumber=11;intn,m,top=1;//玩家数,牌堆中的牌数,目前的牌堆顶unordered_map<string,int>transCard;//牌型编号unordered_map<string,int>transRole;//角色编号vector<int>c......
  • [SDOI2010] 大陆争霸
    [SDOI2010]大陆争霸屁话真多。第一眼看上去好像是最短路加了个强制拓扑。也就是说当结界还没被破坏的时候,已经到达的机器人只能干等着。在dijkstra中,机器人所在的点可以更新最短路。但拓扑图上该点的入度不为\(0\),即结界产生器没有被全部破坏时,不能入队。当炸掉一个结界......
  • [SDOI2010] 大陆争霸 题解
    [题目传送门](https://www.luogu.com.cn/problem/P2446)#解法由题可知,一个城市$u$保护城市$v$,所以建一条边$u\tov$表示城市$u$保护城市$v$,因为题目说保证有解,所以建的图一定是一个**有向无环图$DAG$**。再在此基础上求出最短路径。具体过程为设$dis_u$表示实际到达(攻破)$u$的最......
  • 【题解】Luogu-P2482 SDOI2010 猪国杀
    写了\(358\)行,\(11.94\mathrm{KB}\),有这么几个地方写挂了:反猪决斗一定选主猪。游戏结束判定是主猪死亡或全部反猪死亡。决斗可能被反杀,之后不能再出牌。点击查看代码#include<bits/stdc++.h>usingnamespacestd;intn,m;charCh[3];queue<char>Deck;in......
  • [SDOI2010] 代码拍卖会 题解
    [SDOI2010]代码拍卖会题解题目描述一个\(n,n\le10^{18}\)位数,仅由\(1\sim9\)组成,后一位数字一定大于等于前一位数字。求这些数中可以被\(m,m\le500\)整除的有多少,对\(999911659\)取模。解析这个数一定形如\(112334455677788999\)可以把它拆成\[\begin{aligned}......
  • [SDOI2010] 外星千足虫
    题意现在你面前摆有\(1\ldotsN\)编号的\(N\)只千足虫,你的任务是鉴定每只虫子所属的星球,但不允许亲自去数它们的足。Charles每次会在这\(N\)只千足虫中选定若干只放入“昆虫点足机”(theInsectFeetCounter,IFC)中,“点足机”会自动统计出其内所有昆虫足数之和。Charles......
  • [SDOI2010] 古代猪文
    题意求下列表达式的值\(\large{g^{\sum_{d|n}{\binom{n}{d}}}\pmod{999911659}}\)其中,\(n,d\leqslant10^9.\)Solution由欧拉定理可知,\(\large{原式=g^{\sum_{d|n}{\binom{n}{d}}\pmod{999911658}}}\)显然只需要考虑分子,考虑到\(999911658\)范围下的组合数无法......