topcoder srm 699 div1 -3-白红宇

topcoder srm 699 div1 -3

阅读量：5961 次

发布时间：2019-06-19

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

1、两个长度为$n$的数组$a,b$，$0 \leq a_{i} <2^{30}$。$b_{i}=-1$或者$b_{i}$为除$a_{i}$外其他数字的抑或值。现在给定$b$，如果不存在$a$，返回-1.否则输出$a$数组所有数字和的最小值。

思路：一位一位考虑。当前考虑第$k$位。对于所有不知道的数字将它们看做一个数字0或者1。现在就是一个全是01的数组$c$，那么$c_{i}$^$c_{j}$=$A_{i}$^$A_{j}$。其中$A_{i}=(a_{i}$>>$k)$&1.然后假定$A_{0}=$0或者1进行判断即可。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           #include 
            
             #include 
             
              #include 
              
               #include 
               
                using namespace std;const int N=44;int n;vector
                
                 
                   > g[N];int a[N],m;int b[N];int c[N];int dfs(int t){ for(int i=0;i<(int)g[t].size();++i) { int v=g[t][i].first; int w=g[t][i].second; if(b[v]==-1) { b[v]=w^b[t]; if(!dfs(v)) return 0; } else if(b[v]!=(w^b[t])) return 0; } return 1;}int get(){ for(int i=0;i
                  
                   tmp) ans=tmp; } if(ans==m+1) ans=-1; return ans;}int cal(){ m=0; int k=0; for(int i=0;i

x) { n=(int)x.size(); long long sum=0; for(int i=0;i<30;++i) { for(int j=0;j

>i)&1; } int p=cal(); if(p==-1) return -1; sum+=(1ll<

2、一个$N$个节点的有向图。给出$m$个数对$(a_{0},b_{0}),(a_{1},b_{1})...(a_{m-1},b_{m-1})$。两个节点$X,Y$有边当且仅当存在一个数对$(a_{i},b_{i})$使得$a_{i}$可整除$X$且$b_{i}$可整除$Y$。给定起点$s$终点$t$，求最短路。

思路：将数对看做节点。第$i$个节点可以向第$j$个节点连边当且仅当$lcm(b_{i},a_{j})\leq N$。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           #include 
            
             #include 
             
              #include 
              
               #include 
               
                using namespace std;vector
                
                  g[1005];int n;int s,t;queue
                 
                   Q;int f[1005];int bfs(){ memset(f,-1,sizeof(f)); f[0]=0; Q.push(0); while(!Q.empty()) { int u=Q.front(); Q.pop(); for(int i=0;i<(int)g[u].size();++i) { int v=g[u][i]; if(f[v]==-1) { f[v]=f[u]+1; Q.push(v); } } } if(f[t]!=-1) return f[t]-1; return f[t];}int gcd(int a,int b){ return !b?a:gcd(b,a%b);}class FromToDivisible{public: int shortest(int N,int S,int T,vector
                  
                    a,vector
                   
                     b) { n=(int)a.size(); s=0; t=n+1; for(int i=0;i

转载于:https://www.cnblogs.com/jianglangcaijin/p/6860812.html

你可能感兴趣的文章