美文网首页
分段打表

分段打表

作者: 云中翻月 | 来源:发表于2020-11-25 07:37 被阅读0次

适用题目特征

当打表范围过大,但表之间可以递推。

原理

借助分块的思想,答案来自若干子表的组合。即,整块的答案用预处理的值计算,非整块的答案暴力计算。
关于分块大小,通常\sqrt{n}会取得最好的效果,但受限于提交代码长度限制,实际分块大小通常大于\sqrt{n}
PS:2020年CCPC网络赛中,计算[1,n]的素数和的题目,似乎可以用这种方法水过去。

例题

Luogu P1822
代码如下

/*
Luogu P1822
*/
#define method_1
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
#define rep(i,s,t) for(int i=(s);i<=(t);i++)
#define rep0(i,s,t) for(int i=(s);i<(t);i++)
#define rrep(i,t,s) for(int i=(t);i>=(s);i--)
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=1000+5;
const int Len=1000000; //sqrt(1e9)
const int INF=0x3f3f3f3f;
const int cnt[]={0,2045,1044,750,357,316,316,358,749,1044,1474,866,1044,303,220,154,115,84,125,346,927,378,558,750,221,204,154,118,134,146,382,110,270,303,357,176,204,168,128,89,75,85,126,298,221,316,176,220,168,88,69,69,88,168,220,176,316,221,298,126,85,75,89,128,168,204,176,357,303,270,111,382,145,134,118,154,204,222,749,558,378,927,347,124,84,115,154,220,303,1044,866,2022,754,224,71,86,115,168,298,558,1474,626,558,118,81,51,33,19,30,316,1461,866,1044,303,220,154,115,84,125,346,927,110,558,94,221,96,77,48,32,26,60,74,270,116,66,95,204,118,83,55,29,50,126,118,77,50,76,113,168,57,43,44,88,108,79,40,41,44,91,98,85,41,89,69,81,34,23,30,21,80,67,136,145,74,64,51,21,22,24,35,53,489,347,75,61,51,24,13,28,172,79,1143,754,47,45,51,36,15,20,229,924,240,240,298,118,69,51,28,43,63,585,866,328,303,113,77,51,35,25,62,375,378,558,750,221,204,154,118,134,146,382,67,194,303,84,176,96,81,49,32,25,47,98,298,126,69,95,220,108,52,38,43,57,168,113,76,50,77,118,126,50,48,69,128,118,60,40,34,29,96,74,156,97,134,76,77,34,27,23,26,55,162,193,124,54,69,51,23,23,35,37,311,315,224,35,58,51,22,28,72,277,25,78,118,168,65,58,35,27,14,14,382,92,116,220,101,69,53,33,39,32,110,558,94,221,96,77,48,32,26,60,110,270,303,357,176,204,168,128,89,75,34,83,118,221,64,176,113,109,42,27,38,52,108,220,95,69,126,298,98,47,35,54,69,168,96,76,59,65,194,110,51,66,74,118,101,60,44,30,47,138,32,60,75,84,65,77,52,21,25,33,24,41,47,71,52,69,56,34,35,16,23,47,91,118,115,52,45,35,16,15,170,64,65,113,154,65,61,32,32,20,378,240,79,126,204,101,64,46,27,54,67,194,303,84,176,96,81,49,32,25,85,126,298,221,316,176,220,168,88,69,27,42,109,113,176,64,221,118,83,34,29,55,83,118,204,95,66,116,270,74,41,49,78,76,154,96,77,33,78,110,23,46,49,54,115,101,79,29,23,52,15,22,53,35,86,65,81,52,26,12,12,26,52,81,65,86,35,53,22,15,52,23,29,79,101,115,54,49,46,23,110,78,33,77,96,154,76,78,49,41,74,270,116,66,95,204,118,83,55,29,34,83,118,221,64,176,113,109,42,27,69,88,168,220,176,316,221,298,126,85,25,32,49,81,96,176,84,303,194,67,54,27,46,64,101,204,126,79,240,378,20,32,32,61,65,154,113,65,64,170,15,16,35,45,52,115,118,91,47,23,16,35,34,56,69,52,71,47,41,24,33,25,21,52,77,65,84,75,60,32,138,47,30,44,60,101,118,74,66,51,110,194,65,59,76,96,168,69,54,35,47,98,298,126,69,95,220,108,52,38,27,42,109,113,176,64,221,118,83,34,75,89,128,168,204,176,357,303,270,110,60,26,32,48,77,96,221,94,558,110,32,39,33,53,69,101,220,116,92,382,14,14,27,35,58,65,168,118,78,26,276,72,28,22,51,58,36,224,315,310,37,35,23,23,51,69,54,125,193,161,55,26,23,27,34,77,76,134,98,155,74,96,29,34,40,60,118,128,69,48,50,126,118,77,50,76,113,168,57,43,38,52,108,220,95,69,126,298,98,47,25,32,49,81,96,176,84,303,194,68,382,145,134,118,154,204,222,749,558,379,374,62,25,35,51,77,113,304,327,867,584,63,43,28,51,69,118,298,241,239,924,229,20,15,36,51,45,47,754,1143,79,172,28,13,24,51,61,76,346,489,53,35,24,22,21,51,64,74,145,136,67,80,21,30,23,34,81,69,89,41,85,98,91,44,41,40,79,108,88,44,43,57,168,113,76,50,77,118,126,50,29,55,83,118,204,95,66,116,270,74,60,26,32,48,77,96,221,94,558,110,927,347,124,84,115,154,220,303,1044,866,1461,316,30,19,33,51,81,118,558,626,3567,2257,88,6,20,33,35,54,314,2022,371,1006,134,9,9,36,53,50,192,927,57,72,84,14,11,24,48,78,98,382,46,41,23,18,9,21,56,83,69,75,50,83,52,27,21,23,52,109,57,69,44,88,108,79,40,41,44,91,98,85,35,54,69,168,96,76,59,65,194,110,54,27,46,64,101,204,126,79,240,379,374,62,25,35,51,77,113,304,327,866,2022,754,224,71,86,115,168,298,558,1474};
int A,B;
int ID(int x){
    return (x+Len-1)/Len;
}
int L(int x){
    return (ID(x)-1)*Len+1;
}
int R(int x){
    return ID(x)*Len;
}
inline int qpow(int a,int b) {
    int res=1;
    while(b){
        if(b&1) res=res*a;
        a=a*a;
        b>>=1;
    }
    return res;
}
int magic(int x) {
    int y=0,num[10],i=-1;
    while(x) num[++i]=x%10,x/=10;
    for(int j=0;j<i;j++)
        y+=abs(num[j]-num[j+1])*qpow(10,j);
    if(y<10) return y;
    else return magic(y);
}
void solve() {
    int res=0;
    if(A<=7&&B>=7) res=1;
    if(ID(A)==ID(B)) rep(i,A,B) res+=magic(i)==7;
    else{
        rep(i,A,R(A)) res+=magic(i)==7;
        rep(i,L(B),B) res+=magic(i)==7;
        rep0(i,ID(A)+1,ID(B)) res+=cnt[i];
    }
    cout<<res;
}
int main() {
//  ios::sync_with_stdio(false);
//  freopen("魔法指纹.in","r",stdin);
    cin>>A>>B;
    solve();
    return 0;
}
#endif
#ifdef method_2
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
#define rep(i,s,t) for(int i=(s);i<=(t);i++)
#define rep0(i,s,t) for(int i=(s);i<(t);i++)
#define rrep(i,t,s) for(int i=(t);i>=(s);i--)
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=+5;
const int INF=0x3f3f3f3f;
inline int qpow(int a,int b) {
    int res=1;
    while(b){
        if(b&1) res=res*a;
        a=a*a;
        b>>=1;
    }
    return res;
}
int magic(int x) {
    int y=0,num[10],i=-1;
    while(x) num[++i]=x%10,x/=10;
    for(int j=0;j<i;j++)
        y+=abs(num[j]-num[j+1])*qpow(10,j);
    if(y<10) return y;
    else return magic(y);
}
void solve() {
    int Len=1000000,res=1,L,R;
    for(int i=1;i<=1000;i++){
        L=(i-1)*Len+1;
        R=min(1000000000,Len*i);
        for(int j=L;j<=R;j++)
            if(magic(j)==7) res++;
        printf("%d,", res);res=0;
    }
}
int main() {
//  ios::sync_with_stdio(false);
    freopen("table.out", "w", stdout);
    solve();
    return 0;
}
#endif
#ifdef method_3
/*

*/

#endif

相关文章

  • 分段打表

    适用题目特征 当打表范围过大,但表之间可以递推。 原理 借助分块的思想,答案来自若干子表的组合。即,整块的答案用预...

  • 分段打不上去了

    从网吧路过,不禁想到了曾经的那段岁月。 只不过是一个小目标,就是为了在自己面前证明自己可以达到什么样的分段。 或许...

  • 打表

    打表 给定一个十进制的正整数(1<=n<=10000),写下从1到n的所有整数,然后数一下其中出现的数字“1”的个...

  • (打表)E - Recursive Queries CodeFo

    题意:忘了,反正就是打表题解:打表(前缀和) 代码:

  • 素数打表

  • TableView全表截图以及分段分享

    TableView 全表截图 APP中有一个类似于分析报告的页面,需要全部分享,包括超出屏幕之外的cell。直接截...

  • 什么是虚拟内存,分页、分段又是什么?

    操作系统——内存管理之内存分配(分页,分段,段页)多级页表与快表 共享内存可以用虚拟内存来实现。 共享内存的方式原...

  • 《计算机组成与体系结构》——7.2虚拟存储器

    本节重点: 虚拟存储器技术 页表 块表 分段 分页技术使多道程序设计变得真正有效,而且进程分页这一简单策略导致了另...

  • 辽宁本科低分段考生如何"保本‘’

    一般而言,高于本科线40分之内的考生应属于本科低分段考生,根据2018年辽宁省高考一分一段表统计,理工类本科低分段...

  • 世界你好分段计费is分

    世界你好分段计费is分 世界你好分段计费is分世界你好分段计费is分世界你好分段计费is分世界你好分段计费is分世...

网友评论

      本文标题:分段打表

      本文链接:https://www.haomeiwen.com/subject/teowiktx.html