牛客网NOIP赛前集训营-提高组（第四场）游记

动态点分治

题目大意：

\(T(t\le10000)\)组询问，求\([l,r]\)中\(k(l,r,k<2^{63})\)的非负整数次幂的数的个数。

思路：

暴力，注意特判\(0\)和\(1\)的情况。

源代码：

#include<cstdio>
#include<cctype>
typedef unsigned long long uint64;
inline uint64 getint() {
    register char ch;
    while(!isdigit(ch=getchar()));
    register uint64 x=ch^'0';
    while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
    return x;
}
uint64 ans[64];
int main() {
    for(register int T=getint();T;T--) {
        const uint64 l=getint(),r=getint(),k=getint();
        if(k==0) {
            if(l>1) {
                puts("None.");
                continue;
            }
            if(l==0) printf("0 ");
            if(r!=0) printf("1 ");
            puts("");
            continue;
        }
        if(k==1) {
            puts(l<=1&&1<=r?"1":"None.");
            continue;
        }
        uint64 pwr=1;
        ans[0]=0;
        for(register int i=0;i<63;i++) {
            if(l<=pwr&&pwr<=r) {
                ans[++ans[0]]=pwr;
            }
            if(pwr>1.*r/k) break;
            pwr=pwr*k;
        }
        if(ans[0]==0) {
            puts("None.");
        } else {
            for(register uint64 i=1;i<=ans[0];i++) {
                printf("%llu%c",ans[i]," \n"[i==ans[0]]);
            }
        }
    }
    return 0;
}

区间：

题目大意：

给定一个长度为\(n(n\le4\times10^6)\)的数列\(A(A_i\le10^{18})\)，求一个最长的区间满足这个区间的\(\gcd\)本身也是这个区间的一个元素。

思路：

枚举每个数\(k\)作为区间\(\gcd\)，向左右扩展找到极大化区间\([l,r]\)，那么\([l,r]\)中其它元素都没有再枚举的必要。下一个\(k\)直接从\(r+1\)开始即可。

卡读入，直接getchar会被卡。使用mmap即可AC。

源代码：

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<cstdio>
#include<cctype>
#include<algorithm>
#include<sys/mman.h>
#include<sys/stat.h>
class MMapInput {
    private:
        char *buf,*p;
        int size;
    public:
        MMapInput() {
            register int fd=fileno(stdin);
            struct stat sb;
            fstat(fd,&sb);
            size=sb.st_size;
            buf=reinterpret_cast<char*>(mmap(0,size,PROT_READ,MAP_PRIVATE,fileno(stdin),0));
            p=buf;
        }
        char getchar() {
            return (p==buf+size||*p==EOF)?EOF:*p++;
        }
};
MMapInput mmi;
typedef long long int64;
inline int64 getint() {
    register char ch;
    while(!isdigit(ch=mmi.getchar()));
    register int64 x=ch^'0';
    while(isdigit(ch=mmi.getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
    return x;
}
const int N=4e6+1;
int64 a[N];
int main() {
    const int n=getint();
    for(register int i=1;i<=n;i++) a[i]=getint();
    int ans=0;
    for(int k=1;k<n;) {
        int l=k,r=k;
        for(;l>=1&&a[l]%a[k]==0;l--);
        for(;r<=n&&a[r]%a[k]==0;r++);
        ans=std::max(ans,r-l-1);
        k=r;
    }
    printf("%d\n",ans);
    return 0;
}

灭虫

同CF559E。

牛客网NOIP赛前集训营-提高组（第四场）游记

原文：https://www.cnblogs.com/skylee03/p/9750285.html