夜深人静写题解--杭电第四场

1001.AND Minimum Spanning Tree

题意：已知一个完全图，共有N个点，按1-N编号，点与点之间的边权为两点的编号相与，求权值和最小生成树，相同权值和输出最小的字典序方案

思路：为了保证可以得到权值和最小，对于每个点可以贪心的去找与其与值最小的点，为保证字典序最小，应找到第一个与其相与可以得到最小的点

方案：枚举每个点二进制位上最低0的位置，得到相遇的点，比如X的二进制位1110011110111，则与其相与的最小的点为1000，若用此方法找到的值比N值大，则将其与1相与

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6+7;
int b[maxn];
int main()
{
    int n;
    int t;
    cin>>t;
    while(t--)
    {
        cin>>n;
        long long int ans=0;
        for(int i=2; i<=n; i++)
        {
            if(i%2==0)
            {
                b[i]=1;
                ans+=((i&1)*1ll);
            }
            else
            {
                int t=i;
                for(int j=0;j<=30;j++)
                {
                    if((t&(1<<j))!=0)
                        continue;
                    else
                    {
                        if((1<<j)>n)
                        {
                            b[i]=1;
                        }
                        else
                        {
                            b[i]=1<<j;
                        }
                        ans+=((b[i]&i)*1ll);
                        break;
                    }
                }
            }
        }
        printf("%lld
",ans);
        for(int i=2; i<=n; i++)
        {
            printf("%d%c",b[i],i==n?'
':' ');
        }
    }

}

View Code

1007.Just an Old Puzzle

题意：类似于奇数码问题，问是否可以将一个图转化成另一个图

思路：裸题直接搞

代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int main()
 4 {
 5     int mp[25],ans=0;
 6     int t;
 7     cin>>t;
 8     while(t--)
 9     {
10         ans=0;
11         memset(mp,0,sizeof(mp));
12         for(int i=0; i<16; i++)
13         {
14             scanf("%d",&mp[i]);
15             if(!mp[i])
16                 ans+=6-i%4-i/4;
17             for(int j=0; j<i; j++)
18                 if(mp[j]>mp[i])
19                     ans++;
20         }
21         if(ans&1)
22             puts("Yes");
23         else
24             puts("No");
25     }
26 
27 }

View Code

1008. K-th Closest Distance

题意：给定一个数组，每次查询l-r区间之内与K距离第k近的元素，题目要求强制在线，每次输出答案为上一个的答案异或当前答案

思路：对于每个区间查询与K距离最近的元素，可以通过二分答案，查询当前区间处于[p-ans,p+ans]的数是否大于k个，check上述条件完成题目

1010.Minimal Power of Prime

题意：通过对于一个数，求解素因子权值的最小值，数的范围小于1e18，组数是t<50000

思路：对于一个数权值最小值得分析可以通过对于数据进行分析，由于是素因子，考虑到一个数有可能由一个两个较大的素因子相乘得到，我们可以直接对比较大的素因子直接进行判断，假设pq为素数，n=p*p

n=p*p*p,或n=p*p*p*p,或n=p*p*q*q，这几种情况我们可以直接O(1)判断，对于小于p需要乘至少5次方才能得到n直接暴力枚举，枚举sqrt(1e18)约等于4000以内的素数，总共只有552多个，总复杂度就是O(t*552)

代码：

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 int prim[4005];
  4 int vis[4005];
  5 int st=0;
  6 const double eps=1e-7;
  7 const int S=8;
  8 long long ans;
  9 int tol;
 10 long long int mult_mod(long long a,long long b,long long c)
 11 {
 12     a%=c;
 13     b%=c;
 14     long long ret=0;
 15     long long tmp=a;
 16     while(b)
 17     {
 18         if(b&1)
 19         {
 20             ret+=tmp;
 21             if(ret>c)ret-=c;
 22         }
 23         tmp<<=1;
 24         if(tmp>c)tmp-=c;
 25         b>>=1;
 26     }
 27     return ret;
 28 }
 29 long long int pow_mod(long long a,long long n,long long mod)
 30 {
 31     long long ret=1;
 32     long long temp=a%mod;
 33     while(n)
 34     {
 35         if(n&1)ret=mult_mod(ret,temp,mod);
 36         temp=mult_mod(temp,temp,mod);
 37         n>>=1;
 38     }
 39     return ret;
 40 }
 41 bool check(long long a,long long n,long long x,long long t)
 42 {
 43     long long ret=pow_mod(a,x,n);
 44     long long last=ret;
 45     for(int i=1; i<=t; i++)
 46     {
 47         ret=mult_mod(ret,ret,n);
 48         if(ret==1&&last!=1&&last!=n-1)return true;
 49         last=ret;
 50     }
 51     if(ret!=1)return true;
 52     else return false;
 53 }
 54 bool Miller_Rabin(long long n)
 55 {
 56     if(n<2)return false ;
 57     if(n==2)return true;
 58     if((n&1)==0)return false;
 59     long long x=n-1;
 60     long long t=0;
 61     while((x&1)==0)
 62     {
 63         x>>=1;
 64         t++;
 65     }
 66     srand(time(NULL));
 67     for(int i=1; i<S; i++)
 68     {
 69         long long a=rand()%(n-1)+1;
 70         if(check(a,n,x,t))
 71         {
 72             return false;
 73         }
 74     }
 75     return true;
 76 }
 77 void pre()
 78 {
 79     memset(vis,0,sizeof(vis));
 80     for(int i=2; i<4005; i++)
 81     {
 82         if(vis[i]==0)
 83         {
 84             prim[st++]=i;
 85             int j=1;
 86             while(j*i<4005)
 87             {
 88                 vis[j*i]=1;
 89                 j++;
 90             }
 91         }
 92     }
 93 }
 94 long long int ppow(long long a,long long int b)
 95 {
 96     long long int ans=1;
 97     while(b)
 98     {
 99         if(b&1)
100         {
101             ans=ans*a;
102         }
103         a=a*a;
104         b>>=1;
105     }
106     return ans;
107 }
108 bool checkn(long long int k,long long int n)
109 {
110     long long int tt=pow(n,1.0/k);
111     tt-=5;
112     if(tt<=0)tt=1;
113     while(ppow(tt+1,k)<=n)
114     {
115         tt++;
116     }
117     return (ppow(tt,k)==n);
118 }
119 int check1(long long int n)
120 {
121     int ans=100;
122     long long int qq=n;
123     if(n<=3)return 1;
124     for(int i=0; i<st; i++)
125     {
126         int jishu=0;
127         while(qq%prim[i]==0)qq/=prim[i],jishu++;
128         if(jishu!=0) ans=min(jishu,ans);
129     }
130     if(qq==1)return ans;
131     if(checkn(4ll,qq))
132     {
133         ans=min(4,ans);
134         return ans;
135     }
136     else if(checkn(3ll,qq))
137     {
138         ans=min(3,ans);
139         return ans;
140     }
141     else if(checkn(2ll,qq))
142     {
143         ans=min(2,ans);
144         return ans;
145     }
146     return 1;
147     //else return ans;
148 }
149 int main()
150 {
151     //printf("%d
",552*50000*4);
152     int t;
153     pre();
154     //printf("%d
",st);
155     scanf("%d",&t);
156     while(t--)
157     {
158         long long int n;
159         scanf("%lld",&n);
160         printf("%d
",check1(n));
161     }
162 }
163 /*
164 689596527711021121
165 */

View Code