Modulo Query ZOJ - 3940 (区间取模)-程序员宅基地

技术标签: 数论  

题目

https://cn.vjudge.net/problem/ZOJ-3940

题意

给你n个模数,和一个0-m范围,Q次询问,每次问范围内有多少数结果是给定的数

思路

区间取模,对x个区间取模,最多会产生x+1个区间,即x个0-(x-1)的区间合并为一个,和0-(<x)的区间

所有最后最多会有2*n个区间,

对于所有的查询x,查找有多少区间又端点大于等于x,即答案

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod = 1e9+7;
struct node
{
    int r,cnt;
    bool operator < (const node &a) const
    {
        return r < a.r;
    }
}a[500005];
int sum[500005];
int qw[500005];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        node u;
        u.r = m,u.cnt = 1;
        priority_queue<node> q;
        q.push(u);
        for(int i = 1;i <= n;i++)
        {
            int x;
            scanf("%d",&x);
            while(q.top().r >= x)
            {
                u = q.top();
                q.pop();
                int cnt = u.cnt;
                while(!q.empty()&&q.top().r == u.r)
                {
                    cnt+=q.top().cnt;
                    q.pop();
                }
                node v;
                v.r = x - 1;
                int num = cnt*(u.r/x);
                v.cnt = num;
                q.push(v);
                v.r = u.r % x;
                v.cnt = cnt;
                q.push(v);
            }
        }
        int p = 0;
        while(!q.empty())
        {
            a[p].r = q.top().r;
            a[p++].cnt = q.top().cnt;
            q.pop();
        }
        sort(a,a+p);
        memset(sum,0,sizeof(sum));
        for(int i =p-1;i >= 0;i--)
        {
            sum[i] = sum[i+1] + a[i].cnt;
            qw[i] = a[i].r;
        }
        int Q;
        scanf("%d",&Q);
        ll ans = 0;
        for(int k = 1;k <= Q;k++)
        {
            int x;
            scanf("%d",&x);
            int id = lower_bound(qw,qw+p,x) - qw;
            ans += (ll)k*sum[id];
            ans %= mod;
        }
        printf("%lld\n",ans);
    }
    return 0;
}

 

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/sdut_jk17_zhangming/article/details/89192309

智能推荐

android的binder机制研究(C++部分) 分享-程序员宅基地

文章浏览阅读300次。转自:http://ytydyd.blog.sohu.com/139026338.html (一) 概述 android的binder机制提供一种进程间通信的方法,使一个进程可以以类似远程过程调用的形式调用另一个进程所提供的功能。binder机制在Java环境和C/C++环境都有提供。 android的代码中,与C/C++的binder包括一些类型和接口的定义和实现,相关的代码在下面这几个文件中: framew

DLL中调用约定和名称修饰(二)_dll __thiscall-程序员宅基地

文章浏览阅读573次。4、thiscallthiscall调用约定是C++中的非静态类成员函数的默认调用约定。thiscall只能被编译器使用,没有相应的关键字,因此不能被程序员指定。采用thiscall约定时,函数参数按照从右到左的顺序入栈,被调用的函数在返回前清理传送参数的栈,只是另外通过ECX寄存器传送一个额外的参数:this指针。 这次的例子中将定义一个类,并在类中定义一个成员函数,代码如下: _dll __thiscall

关键字final的含义及用法_final关键字-程序员宅基地

文章浏览阅读1.2w次,点赞8次,收藏24次。1.关键字final表示最终的,不可变的。2.关键字final可以修饰变量、方法,还有类3.final修饰的类无法被继承4.final修饰的方法无法被覆盖,无法被重写5.final控制不了能不能调用的问题,表示的是最后的,不能变的,不能改的。6.final修饰的变量只能赋一次值7.final修饰的引用:该引用只能指向1个对象,并且它只能永远指向该对象,并且无法指向其他对象。并且在该方法执行过程中,该引用指向对象之后,该对象不会被垃圾回收期回收直到当前方法结束,才会释放空间_final关键字

Php5.6.15-fpm的运行机制源码剖析-程序员宅基地

文章浏览阅读189次。源码版本:Php5.6.15源码目录:sapi/fpm/fpm说明:源码的主要功能在上面直接注解=============>>start<<================================主进程信号初始化,依据收到的信号类型,进行处理int fpm_signals_init_main() /* {{{ */{struct sigactio...

Flash 平台技术的优化(二) 节省内存_单片机优化程序减少flash占用-程序员宅基地

文章浏览阅读975次。 节省内存 对于应用程序(尤其桌面应用程序)开发一直非常重要。然而,内存的使用量对移动设备来说非常重要,因此有必要限制应用程序占用的内存量。显示对象选择适当的显示对象。ActionScript 3.0 包含很多显示对象。要限制内存用量,最简单的优化技巧之一是使用合适类型的显示对象。对于非交互式简单形状,请使用 Shape 对象。对于不需要时间轴的交互式对象,请使用 Sprite 对象。对于使用时间轴的动画,请使用MovieClip 对象。应始终为应用程序选择最有效的对象类型。以下_单片机优化程序减少flash占用

Bayer彩色滤波器-程序员宅基地

文章浏览阅读6.7k次。Bayer滤波器是一个将RGB三种彩色安排在单片CCD像元阵列上的彩色滤波器排列方式,如下图所示。Bayer滤波器又常被称作彩色滤波马赛克。每一个像元都用一微小的红、绿、蓝滤色片覆盖,其中绿色像元的数量是红和蓝像元的数量的二倍。这是因为人眼对绿色图像细节的分辨能力比红和蓝的高。从图上图中的(b)部分可以看出,每四个像元组成的方块内,都含有二个绿色像元,而红和蓝色像元

随便推点

[Android]应用语言切换的三种方法_安卓 更改应用语言-程序员宅基地

文章浏览阅读584次。[Android]应用语言切换的三种方法 分类: Android2011-07-11 00:27273人阅读评论(0)收藏举报 Android对国际化与多语言切换已经做得不错了,一个应用只要命名相应语系的values-[l_安卓 更改应用语言

Python3 HTMLTestRunner自动化测试报告美化-程序员宅基地

文章浏览阅读431次。1 # FileName : MyHTMLTestRunner.py 2 # Author : wangyinghao 3 # DateTime : 2019/1/9 21:04 4 # SoftWare : PyCharm 5 """ 6 A TestRunner for use with the Python unit testing framewor...

java GC、新生代、老年代-程序员宅基地

文章浏览阅读957次。1.Java GC、新生代、老年代 堆是虚拟机管理的最大一块内存空间,主要用于存放各种类的实例对象。 Java中,为了更好的的管理内存中的对象,包括内存的分配和回收。 堆(60M)=新生代(18M)+老年代(42M). 新生代(18M)=Eden(16M)+from Survivor+to Survivor. 老年代耗时是新生代的22倍。 堆的大小可以通过参数指定,虚拟机每次使用的时

Spring Boot项目配置阿里云ssl证书_postprocesscontext-程序员宅基地

文章浏览阅读2.4k次,点赞4次,收藏14次。最近参与了一个微信小程序的项目,API要求服务器域名是Https的,所以研究了一下ssl证书在Spring Boot中的配置首先,到云服务提供商申请一套SSL证书,这里就不提供具体的申请流程了申请到证书之后下载证书现在Tomcat的进行下载,下载解压后有两个文件分别是.pfx后缀和.txt后缀的打开我们的项目(这里就不演示如何构建自己的基于Spring Boot的项目了)将.pfx..._postprocesscontext

python socket编程中端口被占用的解决方法(转载)-程序员宅基地

文章浏览阅读689次。python socket编程中端口被占用的解决方法(转载)

layui后台系统--子页面修改父页面Tab(新增,删除)_layui.router()-程序员宅基地

文章浏览阅读1w次。使用layui后台模板时发现原生的新增,关闭tab选项卡功能有问题。以下是可实现的代码: 1.新增$('#aaa').on('click', function () { var e = $(this), i = '../Departments/Index', t = 222; layui.router(); ..._layui.router()