HDU 全国多校第四场题解

题解

A AND Minimum Spanning Tree

参考代码：

#include<bits/stdc++.h>

#define maxl 200010

using namespace std;

int n,ans1;

int mi[];

int ans[maxl];

inline void prework()

{

    scanf("%d",&n);

}

inline int find(int x)

{

    for(int j=;j<=;j++)

    if((x&mi[j])==)

        return mi[j];

}

inline void mainwork()

{

    ans1=;int x;

    for(int i=;i<=n;i++)

    {

        if(i&)

        {

            x=find(i);

            if(x<=n)

                ans[i]=x;

            else

                ans1++,ans[i]=;

        }

        else

            ans[i]=;

    }

}

inline void print()

{

    printf("%d\n",ans1);

    for(int i=;i<=n;i++)

        printf("%d%c",ans[i],(i==n)?'\n':' ');

}

int main()

{

    mi[]=;

    for(int i=;i<=;i++)

        mi[i]=mi[i-]*;

    int t;

    scanf("%d",&t);

    for(int i=;i<=t;i++)

    {

        prework();

        mainwork();

        print();

    }

    return ;

}

B Colored Tree

unsolved.

C Divide the Stones

题解：https://blog.csdn.net/liufengwei1/article/details/97970041

 #include<bits/stdc++.h>

 #define maxl 100010

 using namespace std;

 long long k,n,sum,t;

 long long dy[maxl];

 long long last[maxl],to[maxl];

 long long tmp[maxl];

 bool flag;

 vector <long long> ans[maxl];

 inline void prework()

 {

     scanf("%lld%lld",&n,&k);

     sum=1ll*n*(n+)/;

     for(long long i=;i<=k;i++)

         ans[i].clear();

 }

 inline void mainwork()

 {

     flag=false;

     if(sum%k!=)

         return;

     sum=sum/k;

     long long id;

     t=n/k;

     if(t%==)

     {

         long long id=;

         for(long long i=;i<=k;i++)

         {

             for(long long j=;j<=t/;j++)

             {

                 ans[i].push_back(id);

                 ans[i].push_back(n-id+);

                 id++;

             }

         }

         flag=true;

     }

     else

     {

         if(n/k==)

         {

             if(n==)

             {

                 ans[].push_back();

                 flag=true;

             }

             return;

         }

         for(long long i=;i<=k/+;i++)

         {

             dy[i]=k/+i;

             to[i]=(i-)*+;

         }

         for(long long i=k/+;i<=k;i++)

         {

             dy[i]=i-(k/)-;

             to[i]=(i-(k/)-)*;

         }

         for(long long i=;i<=k;i++)

             ans[i].push_back(i),last[i]=i,tmp[i]=i;

         long long num;

         for(long long i=;i<n/k;i++)

         {

             for(long long j=;j<=k;j++)

             {

                 num=dy[last[j]]+(i-)*k;

                 ans[j].push_back(num);

                 last[j]=to[last[j]];

                 tmp[j]+=num;

             }

         }

         for(long long i=;i<=k;i++)

             ans[i].push_back(sum-tmp[i]);

         flag=true;

     }

 }

 inline void print()

 {

     if(flag)

     {

         puts("yes");

         long long l;

         for(long long i=;i<=k;i++)

         {

             for(long long j=;j<n/k;j++)

                 printf("%lld%c",ans[i][j],(j==(n/k-))?'\n':' ');

         }

     }

     else

         puts("no");

 }

 int main()

 {

     long long t;

     scanf("%lld",&t);

     for(long long i=;i<=t;i++)

     {

         prework();

         mainwork();

         print();

     }

     return ;

 }

D Enveloping Convex

unsolved.

E Good Numbers

unsolved.

F Horse

unsolved.

G Just an Old Puzzle

题解：百度“15难题”

参考代码

#include<bits/stdc++.h>

using namespace std;

int ans;

int a[];

int x[];

inline void prework()

{

    for(int i=;i<=;i++)

    {

        scanf("%d",&a[i]);

        if(a[i]==)

        {

            a[i]=;

            ans=x[i];

        }

    }

}

inline void mainwork()

{

    for(int i=;i<=;i++)

    {

        for(int j=i+;j<=;j++)

        if(a[j]<a[i])

            ans++;

    }

}

inline void print()

{

    if(ans&)

        puts("No");

    else

        puts("Yes");

}

int main()

{

    x[]=;x[]=;x[]=;x[]=;

    x[]=;x[]=;x[]=;x[]=;

    int t;

    scanf("%d",&t);

    for(int cas=;cas<=t;cas++)

    {

        prework();

        mainwork();

        print();

    }

    return ;

}

H K-th Closest Distance

题解：主席树+二分 https://blog.csdn.net/liufengwei1/article/details/97948584

参考代码

#include<bits/stdc++.h>

#define maxl 100010

using namespace std;

const int nn=1e6;

int n,m,tot,ans;

int rt[maxl],a[maxl];

struct node

{

    int ls,rs,sum;

}tree[maxl**];

inline void insert(int num,int &x,int l,int r)

{

    tree[++tot]=tree[x];x=tot;

    ++tree[x].sum;

    if(l==r) return;

    int mid=(l+r)>>;

    if(num<=mid)

        insert(num,tree[x].ls,l,mid);

    else

        insert(num,tree[x].rs,mid+,r);

}

inline void prework()

{

    scanf("%d%d",&n,&m);

    for(int i=;i<=n;i++)

        scanf("%d",&a[i]);

    tree[].ls=tree[].rs=tree[].sum=;

    rt[]=;

    tot=;

    for(int i=;i<=n;i++)

    {

        rt[i]=rt[i-];

        insert(a[i],rt[i],,nn);

    }

}

inline int query(int i,int j,int l,int r,int i1,int j1)

{

    if(i1==l && j1==r)

        return tree[j].sum-tree[i].sum;

    int mid=(i1+j1)>>,ret;

    if(r<=mid)

        ret=query(tree[i].ls,tree[j].ls,l,r,i1,mid);

    else if(l>mid)

        ret=query(tree[i].rs,tree[j].rs,l,r,mid+,j1);

    else

    {

        ret=query(tree[i].ls,tree[j].ls,l,mid,i1,mid);

        ret+=query(tree[i].rs,tree[j].rs,mid+,r,mid+,j1);

    }

    return ret;

}

inline bool jug(int l,int r,int mid,int p,int k)

{

    int up=min(p+mid,nn),lo=max(,p-mid);

    int sum=query(rt[l-],rt[r],lo,up,,nn);

    if(sum<k)

        return false;

    else

        return true;

}

inline void mainwork()

{

    ans=;int up,lo,p,k,l,r,mid;

    for(int i=;i<=m;i++)

    {

        scanf("%d%d%d%d",&lo,&up,&p,&k);

        lo^=ans;up^=ans;p^=ans;k^=ans;

        l=;r=nn;

        while(l+<r)

        {

            mid=(l+r)>>;

            if(!jug(lo,up,mid,p,k))// <k

                l=mid;

            else

                r=mid;

        }

        if(jug(lo,up,l,p,k))

            ans=l;

        else

            ans=l+;

        printf("%d\n",ans);

    }

}

inline void print(){}

int main()

{

    int t;

    scanf("%d",&t);

    for(int i=;i<=t;i++)

    {

        prework();

        mainwork();

        print();

    }

    return ;

}

I Linear Functions

unsolved.

J Minimal Power of Prime

参考代码

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int size=1e6+;

double eps=1e-;

int p[size];bool prime[size];

int mpri[size];

int tot=;

void init()

{

    for(int i=;i<size;i++) prime[i]=true;

    for(int i=;i<size;i++)

    {

        if(prime[i])

        {

            p[++tot]=i;

            mpri[i]=i;

        }

        for(int j=;j<=tot&&p[j]*i<size;j++)

        {

            prime[i*p[j]]=false;mpri[i*p[j]]=p[j];

            if(i%p[j]==) break;

        }

    }

}

int main()

{

    init();

    int t;

    long long x;

    scanf("%d",&t);

    while(t--)

    {

        scanf("%lld",&x);

        int cnt=;

        int ans=;

        if(x<size){

            int ps=mpri[x];

            while(x!=)

            {

                do x/=ps,cnt++;

                while(mpri[x]==ps);

                ps=mpri[x];

                ans=min(ans,cnt);

            }

            printf("%d\n",ans);

            continue;

        }

        bool flag=false;

        for(int i=;i<=tot;i++)

        {

            cnt=;

            if(x%p[i]==)

            {

                do x/=p[i],cnt++;

                while(x%p[i]==);

            }

            if(cnt==)

            {

                puts("");

                flag=true;

                break;

            }

        }

        if(flag) continue;

        LL sq=sqrt(x)+eps;

        if(sq*sq==x)

        {

            printf("2\n");

        }

        else

        {

            puts("");

        }

    }

}

巴特西

HDU 全国多校第四场题解

题解

A AND Minimum Spanning Tree

B Colored Tree

C Divide the Stones

D Enveloping Convex

E Good Numbers

F Horse

G Just an Old Puzzle

H K-th Closest Distance

I Linear Functions

unsolved.

J Minimal Power of Prime

最新文章

热门文章

巴特西

HDU 全国多校第四场 题解

题解

A AND Minimum Spanning Tree

B Colored Tree

C Divide the Stones

D Enveloping Convex

E Good Numbers

F Horse

G Just an Old Puzzle

H K-th Closest Distance

I Linear Functions

unsolved.

J Minimal Power of Prime

最新文章

热门文章

HDU 全国多校第四场题解