2019牛客多校第四场-白红宇

2019牛客多校第四场

阅读量：231 次

发布时间：2019-03-01

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

A – meeting

题意：

给一棵n个点的图（保证是树）

给k个点表示k个点上有人，每次走一条边花费1分钟，问所有人走到同一个点最少要多少分钟

思路：

假设任意两个点间距离最大值为d,则d/2向上取整就是答案

最大距离求法类似求树的直径，第一次随便找一个点bfs找到距离当前点最远的点

然后从找到的点在bfs一次找到另外一个最远的点，两个最远点之间的距离就是最大距离

code：

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          #include
           
            typedef long long ll;const int inf=0x3f3f3f3f;const int inn=0x80808080;using namespace std;const int maxm=1e5+5;vector
            
             g[maxm];map
             
              have;int kk[maxm];int mark[maxm];int ans=0;//最远距离int id=1;//第一次bfs最远的点void bfs(int st){ memset(mark,0,sizeof mark); queue
              
               q; q.push(st); mark[st]=1; int timee=0;//距离 while(!q.empty()){ int len=q.size(); for(int i=0;i
               
                ans){ ans=timee; id=x; } } for(int j=0;j<(int)g[x].size();j++){ int v=g[x][j]; if(!mark[v]){ mark[v]=1; q.push(v); } } } timee++; }}int main(){ int n,k; cin>>n>>k; for(int i=1;i<=n-1;i++){ int a,b; cin>>a>>b; g[a].push_back(b); g[b].push_back(a); } for(int i=1;i<=k;i++){ cin>>kk[i]; have[kk[i]]=1;//标记 } bfs(kk[1]);//随便找一个点bfs就行 bfs(id);//bfs前面找到的最远的点 cout<<(ans+1)/2<

D – triples I

题意：

给一个数a，问a能否由多个3的倍数的数通过与运算(&)得来

例如7=3&6

要求数字个数尽量少

思路：

答案最多就两位。

一个二进制位mod 3只可能是1或者2。

若a是3的倍数，那么直接取a即可。

如果a的二进制位只有一位或两位，根本取不出0以外的3的倍数，所以无解。

官方题解：

只需考虑a的二进制位至少

若a mod 3=1：

如果a中的二进制位有至少两个mod 3=1的，设它们为p和q，取a-p,a-q即可。

如果a中的二进制位有恰好一个mod 3=1的，那么设mod 3=1的这个位为p，mod 3=2 的某个位为q，取a-p,p+q即可。

如果a中的二进制位没有mod 3=1的，假设有三个mod 3=2的位p,q,r，我们取ap-q,p+q+r即可。

若a mod 3=2只需把上面的讨论中1与2互换即可，是完全对称的。

code：

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          #include
           
            typedef long long ll;const int inf=0x3f3f3f3f;const int inn=0x80808080;using namespace std;ll n;void solve(){ vector
            
             a[3]; for(int i=0;i<=60;i++){ if(n>>i&1){ //%3=1的放到a[1]，%3=2的放到a[2] a[(i&1)+1].push_back(1LL<
             
              =2){ cout<<2<<' '<
              
               <<' '<
               
                <
                
                 =2){ cout<<2<<' '<
                 
                  <<' '<
                  
                   <
                   
                    >T; while(T--){ cin>>n; if(n%3==0){ cout<<1<<' '<
                    
                     <

J – free

题意：

给n,m,s,t,k

表示n个点，m条带权边，s起点，t终点，k表示k条边免费

每条边都要花费

求s到t最小需要花多少钱

思路：

有模板题：

正解：

自己做的时候跑一边最短路，跑的过程种记录最短路径的边，跑完取出权值排序，把除了k个最大的加起来，没想到直接a了，

想了想，感觉如果有两种总权值相同边不同的最短路好像就不行了。

分层最短路code：

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          #include
           
            typedef long long ll;const int inf=0x3f3f3f3f;const int inn=0x80808080;using namespace std;const int N=1e6+5;const int M=5e6+5;int head[N],nt[M],to[M],w[M];int cnt;int dis[N];int n,m,k,s,t;void init(){ memset(head,-1,sizeof head); cnt=0;}void add(int x,int y,int z){ cnt++;nt[cnt]=head[x];head[x]=cnt;to[cnt]=y;w[cnt]=z;}void dj(){ priority_queue
            
             
               ,vector
              
               
                 >,greater
                
                 
                   > >q; memset(dis,inf,sizeof dis); dis[s]=0; q.push(make_pair(dis[s],s)); while(!q.empty()){ int x=q.top().second; q.pop(); for(int i=head[x];i!=-1;i=nt[i]){ int v=to[i]; if(dis[v]>dis[x]+w[i]){ dis[v]=dis[x]+w[i]; q.push(make_pair(dis[v],v)); } } }}int main(){ while(scanf("%d%d%d",&n,&m,&k)==3){ scanf("%d%d",&s,&t); init(); while(m--){ int u,v,w; scanf("%d%d%d",&u,&v,&w); for(int i=0;i<=k;i++){ add(u+i*n,v+i*n,w);//当前层 add(v+i*n,u+i*n,w); if(i!=k){ //连到下一层 add(u+i*n,v+(i+1)*n,0);//到下一层的花费是0 add(v+i*n,u+(i+1)*n,0); } } } dj(); int ans=inf; for(int i=0;i<=k;i++){ ans=min(ans,dis[t+i*n]); } printf("%d\n",ans); } return 0;}

K – number

题意：

给一串数字问有多少子串是300的倍数

0和00和多个0也算

思路：

300的倍数即0前面是3的倍数后面至少两个0的数

官方题解修改：

记s[i]为前i的和mod3的值（前缀和），对于长度大于等于2的区间[l,r]，如果s[l-1]=s[r]（这样表明[l,r]里面的和mod3等于0，也就是3的倍数），如果此时s[r]和s[r-1]等于0，那么满足条件，累加答案

从小到大枚举r，同时记录有多少个0<=l<=r-2的l满足s[l]=0,1,2

复杂度O(n)

code：

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          #include
           
            typedef long long ll;const int inf=0x3f3f3f3f;const int inn=0x80808080;using namespace std;const int maxm=1e5+5;char s[maxm];int sum[maxm];int cnt[4];//[l,r-2]中0，1，2的个数，int main(){ scanf("%s",s+1); int len=strlen(s+1); for(int i=1;i<=len;i++){ sum[i]=(sum[i-1]+s[i]-'0')%3; } ll ans=0; for(int i=1;i<=len;i++){ if(s[i]=='0'){ ans++; if(s[i-1]=='0'){ ans+=cnt[sum[i]]; } } cnt[sum[i-1]]++; } cout<
            
             <

转载地址：http://zluv.baihongyu.com/

你可能感兴趣的文章