关于九月第三次考试研究表明

阅读量：4665 次

发布时间：2019-06-09

本文共 10808 字，大约阅读时间需要 36 分钟。

考试开始于九月十五朦胧的晨光中

L·可怜·无助·又不会中序遍历·L打开了Ta面前的电脑

说时迟，那时快

只见得L·全电竞唯一一只蒟蒻·L刚好按下开机密码后的空格

一位不知名的陈姓人氏坐在教师机前

向下面颓废的LL以及所有大佬们双眉一挑

一时间蒟蒻震惊，大佬欢欣

：

中秋surprise之中秋考试大礼包

Candy

【问题描述】

糖糖有一个整数A,设A的十进制表示为

定义

糖糖利用这个方法生成了n个数字串,其中:

糖糖对于这些数字串在十进制下的和很感兴趣,现设

她想知道S的最小非1的因子是多少

【输入格式】

输入文件仅有一行，包含一个整数A

【输出格式】

输出文件仅一行表示答案所求的最小非1因子，保证答案不超过

【输入样例 1】

【输出样例 1】

【输入样例 2】

【输出样例 2】

样例2提示：233对应的b1..b3分别是:233,332,323，他们的和为888，最小非1因子为2

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

这道数论模板结合很容易想到统计出两个数字sum(数字和）*11111……1(位数1）

分别对两个数字求一遍最小质因子维护最小

#include
      
       #define re return#define ll long long#define inc(i,l,r) for(int i=l;i<=r;++i)using namespace std;template
       
        inline void rd(T&x){    char c;bool f=0;    while((c=getchar())<'0'||c>'9')if(c=='-')f=1;    x=c^48;    while((c=getchar())>='0'&&c<='9')x=x*10+(c^48);    if(f)x=-x;}const int maxn=5000000;int n,sum,prime[5000005],prime_cnt,ans1,ans2;char s[5000005];bool notprime[5000005];inline void Get_prime(){    notprime[1]=1;    inc(i,1,maxn)    {        if(!notprime[i])        prime[++prime_cnt]=i;                for(int j=1;j<=prime_cnt;++j)        {            if((ll)i*prime[j]>maxn)break;            notprime[i*prime[j]]=1;            if(i%prime[j]==0)break;        }    }}inline ll pow(ll a,ll x,ll mod){    ll res=1;    while(x)    {        if(x&1)res=(res*a)%mod;        a=(a*a)%mod;        x>>=1;    }    re res;}inline int Get_ans1(int sum){    inc(i,1,prime_cnt)    if(sum%prime[i]==0||(pow(10,n,9*prime[i])==1))re i;    re prime_cnt;}int main(){    scanf("%s",s+1);    n=strlen(s+1);    inc(i,1,n)        sum+=(s[i]^48);    Get_prime();    ans1=Get_ans1(sum);    printf("%d",prime[ans1]);    re 0;}

View Code

遗失的二叉树

【问题描述】

小T很喜欢研究树形数据结构，这一天，他的哥哥小Q丢给了小T一个问题：给定一序列，判断其是否为一颗二叉树的中序遍历，对于小T来说，这个问题太简单了，所以哥哥又添加了一个条件：树边连接的两个点的权值不能互质。现在小T对这个问题毫无对策，于是他请你帮他解决这个问题。

【输入格式】

输入文件名为 tree.in。每个输入文件包含多组数据。

输入文件仅有一行，第一行一个数字T，表示测试组数

对于每一组测试样例

第一行一个数字n，表示序列长度

第二行有n个数字ai，表示这个序列

【输出格式】

输出文件名为 tree.out。

输出文件输出T行，如果可以恢复出二叉树，则输出Yes，否则输出No。

【输入样例 1】

265 4 7 9 5 442 6 3 4

【输出样例 1】

NoYes

【数据规模与约定】

对于 40%的数据，

对于100%的数据，

#include
      
       #define re return#define inc(i,l,r) for(int i=l;i<=r;++i)using namespace std;template
       
        inline void rd(T&x){    char c;bool f=0;    while((c=getchar())<'0'||c>'9')if(c=='-')f=1;    x=c^48;    while((c=getchar())>='0'&&c<='9')x=x*10+(c^48);    if(f)x=-x;}int T,n,m,L[505][505],R[505][505],match[505][505],a[505],f[505][505];inline int gcd(int a,int b){    re b?gcd(b,a%b):a;}/*蒟蒻在线悲痛，中序遍历是什么*/int main(){        //freopen("in.txt","r",stdin);    rd(T);    while(T--)    {        rd(n);                memset(R,0,sizeof R);        memset(L,0,sizeof L);        inc(i,1,n)L[i][i]=R[i][i]=1;    /*                memset(f,0,sizeof f);        inc(i,1,n)f[i][i]=1;        */            inc(i,1,n)rd(a[i]);                inc(i,1,n)inc(j,i+1,n)        if(gcd(a[i],a[j])!=1)match[i][j]=match[j][i]=1;        else match[i][j]=match[j][i]=0;    /*    inc(k,1,n-1)        inc(i,1,n-k)        {            int j=i+k;            inc(kk,i+1,j-1)//强制有两子树            if(match[i][i+1]&&match[i][kk+1])f[i][j]|=(f[i+1][kk]&&f[kk+1][j]);                         if(match[i][i+1])f[i][j]|=f[i+1][j];        }    */                    inc(k,1,n-1)        inc(i,1,n-k)        {            int j=i+k;            inc(kk,i,j-1)//强制分成左块             if(match[kk][j])L[i][j]|=(L[i][kk]&&R[kk][j-1]);                        inc(kk,i+1,j)//强制分成右块             if(match[i][kk])R[i][j]|=(L[i+1][kk]&&R[kk][j]);        }                int f=0;        inc(i,1,n)        if(L[1][i]&&R[i][n])f=1;                //if(f[1][n])        if(f)printf("Yes\n");        else printf("No\n");    }    re 0;}

View Code

精灵

【问题描述】

wonderland的地图可以抽象成一个N个点的有根树，第i个点上生活着编号为i的精灵，根节点为1号节点。

一个点的深度定义为这个节点到根的距离+1，第i只精灵和第j只精灵的亲密度为他们在树上最近公共祖先的深度。

现在Jessica想询问你Q次，每次询问第z只精灵和第l~r只精灵的亲密度的和是多少。答案对201314（不是一个质数）取模。

【输入格式】

输入文件名为 elf.in。

第一行有2个整数，分别代表N,Q。

接下来N-1行，分别表示点2到点N的父亲节点编号。

接下来Q行，每行3个整数，分别代表一组询问的l r z。

【输出格式】

输出文件名为 elf.out。

输出共Q行，每行一个整数表示询问的答案，答案对201314（不是一个质数）取模。

【输入样例 1】

5 211222 5 42 5 3    8

【输出样例 1】

【数据规模与约定】

对于所有数据：N,Q≤10^5, 1≤l≤r≤N, 1≤z≤N。

Subtask1(5分):Q,N≤5

Subtask2(10分):Q≤100,N≤500

Subtask3(15分):Q≤1000,N≤1000

Subtask4(15分):树的形态为一条链，x(x≥2)节点的父亲为x-1。

Subtask5(30分):z为定值

Subtask6(25分):无特殊限

差分树链剖分/LCT

只有那么美好了

这是个人能想的出来的东西吗

作为一个人，LL写的暴力，非常暴力的暴力

由于longlong开炸了get_60pts

亲测可得75pts

#include
      
       #define re return#define ll long long#define dec(i,l,r) for(int i=l;i>=r;--i)#define inc(i,l,r) for(int i=l;i<=r;++i)using namespace std;template
       
        inline void rd(T&x){    char c;bool f=0;    while((c=getchar())<'0'||c>'9')if(c=='-')f=1;    x=c^48;    while((c=getchar())>='0'&&c<='9')x=x*10+(c^48);    if(f)x=-x;}const int maxn=100005;ll ans;int fz=-1,n,Q,fa[maxn][17],deep[maxn];ll L[maxn],R[maxn],Z[maxn];vector
        
         G[maxn];inline void dfs(int x){    deep[x]=deep[fa[x][0]]+1;    for(int i=0;fa[fa[x][i]][i];++i)    fa[x][i+1]=fa[fa[x][i]][i];        for(vector
         
          ::iterator it=G[x].begin();it!=G[x].end();++it)    {        int v=*it;        fa[v][0]=x;        dfs(v);    }}inline int Lca(int x,int y){    if(deep[x]
          
           =deep[y])    x=fa[x][i];        if(x==y)re deep[x];        dec(i,16,0)    if(fa[x][i]!=fa[y][i])    {        x=fa[x][i];        y=fa[y][i];    }    re deep[fa[x][0]];    }//-------------------------------------------inline void baoli1(){    int l,r,z;    dfs(1);    inc(i,1,Q)    {        ans=0;        rd(l),rd(r),rd(z);        inc(j,l,r)        ans=(ans+Lca(z,j))%201314;        printf("%lld\n",ans);    }}//----------------------------------------------#define ls rt<<1#define rs rt<<1|1ll sum[maxn<<2];inline void pushup(int rt){    sum[rt]=(sum[ls]+sum[rs])%201314;} inline void build(int rt,int l,int r){    if(l==r)    {        sum[rt]=Lca(l,fz);        re ;    }        int mid=(l+r)>>1;    build(ls,l,mid);    build(rs,mid+1,r);    pushup(rt);}inline void query(int rt,int l,int r,int x,int y){    if(x<=l&&r<=y)    {        ans=(ans+sum[rt])%201314;        re ;    }    int mid=(l+r)>>1;    if(x<=mid)query(ls,l,mid,x,y);    if(y>mid) query(rs,mid+1,r,x,y);}inline void baoliz()//线段树映射 {    dfs(1);    build(1,1,n);        inc(i,1,Q)    {        ans=0;        query(1,1,n,L[i],R[i]);        printf("%lld\n",ans);    }}//-----------------------------------------------inline void baolilian(){    inc(i,1,Q)    {        if(Z[i]<=L[i])        printf("%lld\n",(R[i]-L[i]+1)*Z[i]%201314);        else if(R[i]<=Z[i])        {            printf("%lld\n",((L[i]+R[i])*(R[i]-L[i]+1))/2%201314);         }        else        {            ans=((L[i]+Z[i]-1)*(Z[i]-L[i])/2%201314);            ans+=(R[i]-Z[i]+1)*Z[i]%201314;                        printf("%lld\n",ans%201314);        }    }}//-----------------------------------------------int main(){    int x,y;    rd(n),rd(Q);    inc(i,2,n)    {        rd(x);        G[x].push_back(i);     }         if(n<=1000&&Q<=1000)baoli1();    else    {        if(Q)rd(L[1]),rd(R[1]),rd(Z[1]);        fz=Z[1];            inc(i,2,Q)        {            rd(L[i]),rd(R[i]),rd(Z[i]);            if(fz!=Z[i])fz=-1;        }            if(fz==-1)baolilian();        else baoliz();        }    re 0;}

View Code

好好想想，与其用深度

不如累加到链上

#include
      
       #define re return#define ll long long#define inc(i,l,r) for(int i=l;i<=r;++i)using namespace std;template
       
        inline void rd(T&x){    char c;bool f=0;    while((c=getchar())<'0'||c>'9')if(c=='-')f=1;    x=c^48;    while((c=getchar())>='0'&&c<='9')x=x*10+(c^48);    if(f)x=-x;}const int maxn=100005;int n,Q,tot;int deep[maxn],top[maxn],size[maxn],son[maxn];ll ans[maxn];int  rev[maxn],seg[maxn],fa[maxn]; struct node{    int pos,id,z;    inline bool operator<(node a)const     {        re a.pos>pos;    }}qu[maxn<<1];vector
        
         G[maxn];inline void dfs1(int x){    deep[x]=deep[fa[x]]+(size[x]=1);    for(vector
         
          ::iterator it=G[x].begin();it!=G[x].end();++it)    {        int v=*it;        fa[v]=x;        dfs1(v);        size[x]+=size[v];        if(size[v]>size[son[x]])son[x]=v;    }}inline void dfs2(int x,int topf){    top[x]=topf;    seg[x]=++tot;    rev[tot]=x;    if(son[x])    {        dfs2(son[x],topf);    }        for(vector
          
           ::iterator it=G[x].begin();it!=G[x].end();++it)    {        int v=*it;        if(!top[v])        dfs2(v,v);    }}//-----------------------------------------------------------------------------------------------------#define ls rt<<1#define rs rt<<1|1const int mod=201314;long long lazy[maxn<<2],sum[maxn<<2];inline void pushup(int rt){    sum[rt]=sum[ls]+sum[rs];}inline void pushdown(int rt,int l,int r,int mid){    lazy[ls]+=lazy[rt];lazy[rs]+=lazy[rt];    sum[ls]+=lazy[rt]*(mid-l+1);    sum[rs]+=lazy[rt]*(r-mid);/*    sum[ls]+=lazy[rt];    sum[rs]+=lazy[rs];*/    lazy[rt]=0;}inline void add(int rt,int l,int r,int x,int y){    if(x<=l&&r<=y)    {        sum[rt]=(sum[rt]+r-l+1);        ++lazy[rt];        re ;    }    int mid=(l+r)>>1;    if(lazy[rt])pushdown(rt,l,r,mid);    if(x<=mid)add(ls,l,mid,x,y);    if(y>mid) add(rs,mid+1,r,x,y);        pushup(rt);}long long Ans;inline void query(int rt,int l,int r,int x,int y){    if(x<=l&&r<=y)    {        Ans=(Ans+sum[rt])%mod;        re ;    }    int mid=(l+r)>>1;    if(lazy[rt])pushdown(rt,l,r,mid);    if(x<=mid)query(ls,l,mid,x,y);    if(y>mid) query(rs,mid+1,r,x,y); }inline void update(int pos){    while(top[pos]!=1)    {        add(1,1,n,seg[top[pos]],seg[pos]);        pos=fa[top[pos]];    }    add(1,1,n,1,seg[pos]);}inline ll Get_ans(int pos){    Ans=0;    while(top[pos]!=1)    {        query(1,1,n,seg[top[pos]],seg[pos]);        pos=fa[top[pos]];    }    query(1,1,n,1,seg[pos]);        re Ans;}int main(){    freopen("in.txt","r",stdin);         rd(n),rd(Q);        int x,y;    inc(i,2,n)    {        rd(x);        G[x].push_back(i);    }    dfs1(1);dfs2(1,1);    //build;        int k=0;    inc(i,1,Q)    {        rd(qu[++k].pos);qu[k].id=-i;        --qu[k].pos;        rd(qu[++k].pos);qu[k].id=i;        rd(x);        qu[k-1].z=qu[k].z=x;    }        sort(qu+1,qu+k+1);        int now=0;    inc(i,1,k)    {        while(now