HNOI2016(BZOJ4542) 大数

时间:2022-10-01 00:16:53

HNOI2016 Day2 T3 大数

Description

  小 B 有一个很大的数 S,长度达到了 N 位;这个数可以看成是一个串,它可能有前导 0,例如00009312345
。小B还有一个素数P。现在,小 B 提出了 M 个询问,每个询问求 S 的一个子串中有多少子串是 P 的倍数(0 也
是P 的倍数)。例如 S为0077时,其子串 007有6个子串:0,0,7,00,07,007;显然0077的子串007有6个子串都是素
数7的倍数。

Input

  第一行一个整数:P。第二行一个串:S。第三行一个整数:M。接下来M行,每行两个整数 fr,to,表示对S 的
子串S[fr…to]的一次询问。注意:S的最左端的数字的位置序号为 1;例如S为213567,则S[1]为 2,S[1…3]为 2
13。N,M<=100000,P为素数

Output

  输出M行,每行一个整数,第 i行是第 i个询问的答案。

Sample Input

11
121121
3
1 6
1 5
1 4

Sample Output

5
3
2
//第一个询问问的是整个串,满足条件的子串分别有:121121,2112,11,121,121。

正解:莫队算法

解题报告:

  大概题意:给一串数和一个质数,然后每次询问一段区间,问对于这一个区间,有多少个子串组成的大数能够整除这个质数  

  今天为了做这道题先去学了莫队算法,然后A掉了莫队算法的入门题目——小Z的袜子。

  考场上面我傻逼的打了一个高精度,华丽丢掉暴力分。然而我发现只需要取个模就可以了,考场上傻了。

  学完莫队算法之后,发现这道题其实就是一个裸题。

  一开始依然是莫队算法的方式,按左端点所在块的编号为第一关键字,右端点编号为第二关键字排序,

  考虑先暴力处理每个块的第一组询问,之后可以发现我们只需要微调一下区间的左右端点就可以了。比如说:我上次处理了1 5,那么1 6就可以只把6加进去就可以了;如果这      一次是2 6,那么我还需要把1给去掉。

  考虑怎么转移:先离散化一下余数,记录[l, r]中这个数出现了几次,区间长度±1时显然答案改变值为这个点的余数的原出现次数(假设第一个数余数为2,用cnt[2]表示余数为2的数在当前区间的出现次数,那么去掉1之后答案改变值为cnt[2],自己yy一下应该想得通的)。

然后好像很有道理了,AC了?!好吧,其实是善良的出题人没有卡我们,其实p = 2 或 p = 5的情况是可以被卡掉的

  特判一下就好了,两个数组分别表示[1, i]中2或5的倍数时有多少种情况及有多少个数末尾是2或5的倍数,用前缀和维护。

  这样就可以完美AC了,可以过掉BZOJ上的新增数据了

  下面这份是没改过的,不要怪我懒QAQ

//It is made by ljh2000
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <ctime>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <string>
using namespace std;
typedef long long LL;
const int MAXN = 200011;
int MOD,m,len,l,r,block,L;
LL ans,A[MAXN],cnt[MAXN],a[MAXN],c[MAXN];
char ch[MAXN];
struct ask{int l,r,belong,id;}Q[MAXN];
inline bool cmp(ask q,ask qq){ if(q.belong==qq.belong) return q.r<qq.r; return q.belong<qq.belong; }
inline int getint(){
int w=0,q=0; char c=getchar(); while((c<'0'||c>'9') && c!='-') c=getchar();
if(c=='-') q=1,c=getchar(); while (c>='0'&&c<='9') w=w*10+c-'0',c=getchar(); return q?-w:w;
} inline void change(int val,int type){
ans-=cnt[val]*(cnt[val]-1)/2;
cnt[val]+=type;
ans+=cnt[val]*(cnt[val]-1)/2;
} inline void work(){
MOD=getint(); scanf("%s",ch+1); len=strlen(ch+1); LL/*!!!*/ now=0,ss=1; now=ch[len]-'0'; a[len]=now%MOD; c[len]=a[len];
block=sqrt(len); for(int i=len-1;i>=1;i--) { ss*=10; ss%=MOD; now+=ss*(ch[i]-'0'); now%=MOD; a[i]=now; c[i]=a[i]; }
sort(c+1,c+len+1); L=unique(c+1,c+len+1)-c-1; for(int i=1;i<=len;i++) a[i]=lower_bound(c+1,c+len+1,a[i])-c;
if(c[1]==0) a[len+1]=1; else a[len+1]=0;/*!!!*/
m=getint(); for(int i=1;i<=m;i++) Q[i].l=getint(),Q[i].r=getint(),Q[i].belong=(Q[i].l-1)/block+1,Q[i].id=i;
sort(Q+1,Q+m+1,cmp); l=1; r=0;
for(int i=1;i<=m;i++) {
while(r<=Q[i].r) r++,change(a[r],1);
while(r>Q[i].r+1) change(a[r],-1),r--;
while(l<Q[i].l) change(a[l],-1),l++;
while(l>Q[i].l) l--,change(a[l],1);
A[Q[i].id]=ans;
}
for(int i=1;i<=m;i++) printf("%lld\n",A[i]);
} int main()
{
work();
return 0;
}

  

HNOI2016(BZOJ4542) 大数的更多相关文章

  1. 【HNOI2016】大数

    [HNOI2016]大数 题目链接 题目描述 小 B 有一个很大的数 $ S $,长度达到了 $ N $ 位:这个数可以看成是一个串,它可能有前导 $ 0 $,例如 00009312345 .小 B ...

  2. 「HNOI2016」大数

    题目描述 给定一个质数\(p\)和一个数字序列,每次询问一段区间\([l,r]\), 求出该序列区间\([l,r]\)内的所有子串,满足该子串所形成的数是\(p\)的倍数(样例的解释也挺直观的) 基本 ...

  3. bzoj4542 大数

    Description 小 B 有一个很大的数 S,长度达到了 N 位:这个数可以看成是一个串,它可能有前导 0,例如00009312345.小B还有一个素数P.现在,小 B 提出了 M 个询问,每个 ...

  4. loj2053 「HNOI2016」大数

    ref #include <algorithm> #include <iostream> #include <cstring> #include <cstdi ...

  5. HNOI做题记录

    算是--咕完了? 2013.2014的就咕了吧,年代太久远了,并且要做的题还有那么多-- LOJ #2112. 「HNOI2015」亚瑟王 发现打出的概率只和被经过几次有关. 于是\(dp_{i,j} ...

  6. 【BZOJ4542】&lbrack;Hnoi2016&rsqb;大数 莫队

    [BZOJ4542][Hnoi2016]大数 Description 小 B 有一个很大的数 S,长度达到了 N 位:这个数可以看成是一个串,它可能有前导 0,例如00009312345.小B还有一个 ...

  7. 【bzoj4542】 Hnoi2016—大数

    http://www.lydsy.com/JudgeOnline/problem.php?id=4542 (题目链接) 题意 给出一个素数$P$,一个数串$S$,$m$个询问,每次询问区间$[l,r] ...

  8. BZOJ4542&colon; &lbrack;Hnoi2016&rsqb;大数

    Description 小 B 有一个很大的数 S,长度达到了 N 位:这个数可以看成是一个串,它可能有前导 0,例如00009312345.小B还有一个素数P.现在,小 B 提出了 M 个询问,每个 ...

  9. &lbrack;BZOJ4542&rsqb; &lbrack;Hnoi2016&rsqb; 大数 &lpar;莫队&rpar;

    Description 小 B 有一个很大的数 S,长度达到了 N 位:这个数可以看成是一个串,它可能有前导 0,例如00009312345.小B还有一个素数P.现在,小 B 提出了 M 个询问,每个 ...

随机推荐

  1. 脏检查and刷新机构

    ---恢复内容开始--- 脏检查:当食物提交时,Hiberante会对Session中持久状态的对象进行加测,判断对象的数据是否发生了变化 为什么要进行脏检查?, 解析:如果对象发生了改变,就需要将改 ...

  2. Java总结篇系列:Java多线程(一)

    多线程作为Java中很重要的一个知识点,在此还是有必要总结一下的. 一.线程的生命周期及五种基本状态 关于Java中线程的生命周期,首先看一下下面这张较为经典的图: 上图中基本上囊括了Java中多线程 ...

  3. WINCE&plus;6410 拨号上网

    我们现在的模块用的是USB接口,然后模拟成一个COM6进行通信,在CE的: 控制面板->网络连接 里要新建一个连接,选择"拨号连接"然后设置好区域代码,还有附加解调器命令+C ...

  4. 基于ant的jmeter自动化性能测试

    准备工作: 1.java的运行环境正常,及运行java -version.javac -version能正常输出java版本: 2.ant的运行环境正常,使用ant需要配置环境变量,编辑/etc/pr ...

  5. state与status的区别

    status 指人时暗指相对的地位,指物时相当于 situation.situation 较狭义地指由环境综合决定的特定时间上的状态或情形. state 人或物存在或所处的状态,和 condition ...

  6. How Indexes Are Stored

    reference:  http://docs.oracle.com/cd/B28359_01/server.111/b28318/schema.htm#CHDJGADJ 当创建索引的时候,Oracl ...

  7. Knockoutjs官网翻译系列(二) Observable 数组

    承接前文,前文书说道了KO框架中如何使用observable的视图模型属性来与UI元素进行绑定并自动进行双向更新的事儿.observable属性除了服务基础数据类型之外,还定义了专门为服务数组类型的o ...

  8. Cracking the coding interview--Q1&period;6

    原文: Given an image represented by an NxN matrix, where each pixel in the image is 4 bytes, write a m ...

  9. 优秀的VeriSign和混蛋的GlobalSign

    由于领导不懂行,直接购买了GlobalSign的证书,结果引起了我这个开发人员痛苦的2星期之旅,说说大体情况: 目的:对买来的一个驱动程序进行签名,使之能够在Win x64情况下安装和使用 下载Win ...

  10. angular directive知识

    一般来讲 directive名字遵循一下规则: 1.忽略以x-和data-为元素/属性的前缀 2.转化“:”,“-”,“_”命名为驼峰命名 如下所示 <div ng-controller=&qu ...