Southeastern European Regional Programming Contest 2009 部分解题报告

貌似这次题目还是不错的，所以做了一下，不过还有几道难题没弄出来，一边思考，一边求救中。。。。
题目网址：
http://acm.hunnu.edu.cn/online/?action=problem&type=list&courseid=49

【Problem A】 

题目类型：数学 ，大数开方（用二分），大数四则运算。

思路分析：

已知 n = p * q  ,  p <= q  ,  | p - k * q| <= 10^5 

先消去p ,  然后解不等式得到 q 的取值范围为：

       ( -10^5 + sqrt( 10^10  + 4*k*n ) )/2  <= q <= (10 ^ 5 + sqrt(10 ^ 10  + 4 *k *n)) / 2 

本题巧妙之处，在于q 最多只有10^5 种选择 ， 所以依次枚举即可。

       For  ( q = low ;  q<=up ; ++ q ) 

                 If( n % q == 0 )   这就是答案；

涉及大数除大数 ， 所以用JAVA好点。 才学java , 写的比较烂 ， 被鄙视！

import java.io.*;
import java.util.*;
import java.math.*;

public class Main {
     
     public static BigInteger sqrt(BigInteger a){
            BigInteger  v0 = new BigInteger("0") ;
            BigInteger  v1 = new BigInteger("1");
            BigInteger  v2 = new BigInteger("2");
            BigInteger l = v1 , r = a.add(v1) , mid , x ;
            
            //System.out.println(a.toString());
            
            
            while((l.add(v1)).compareTo(r)<0){
                  mid = (l.add(r)).divide(v2) ;
                  x = mid.add(v1);
                  int tr1 = (mid.multiply(mid)).compareTo(a) ;
                  int tr2 = (x.multiply(x)).compareTo(a)     ; 
                  if(tr1 <=0 && tr2 > 0 )  return mid ;
                  if(tr1 < 0 )  
                        l = mid ; 
                  else  
                        r = mid.subtract(v1);
                  //System.out.println(l.toString() + "  and  " + r.toString());
            }
            if((r.multiply(r)).compareTo(a)<=0)  
                    return r ; 
            else    
                    return l ;
     }
    
     public static void main(String args[]){
            Scanner cin = new  Scanner(System.in);
            BigInteger P , Q , n ,k , low , up ,tp ; 
            BigInteger v10  = new BigInteger("100000");
            BigInteger v100 = new BigInteger("10000000000");
            BigInteger v4   = new BigInteger("4");
            BigInteger v2   = new BigInteger("2");
            BigInteger v1   = new BigInteger("1");
            BigInteger v0   = new BigInteger("0");
            
            while(cin.hasNext()){
                 n = cin.nextBigInteger() ; k = cin.nextBigInteger();
                 tp =sqrt(v100.add(v4.multiply(k.multiply(n)))) ;
                 low = (tp.subtract(v10)).divide(v2) ; 
                 if((low.compareTo(v2))<0)  
                            low = v2 ;
                 up  = (tp.add(v10)).divide(v2)      ; 
                 for(Q = low ; Q.compareTo(up)<=0 ; Q=Q.add(v1)) 
                       if( (n.mod(Q)).compareTo(v0) == 0 )  break ;
                 P = n.divide(Q); 
                 if(Q.compareTo(P)<0){
                     tp = Q ; Q = P ; P = tp ;
                 }
                 System.out.println(P.toString()+" * " + Q.toString());
            }
     }

}

【Problem B】

题目类型：简单模拟 

思路分析：

貌似没什么难点，就是题目描述有点晦涩。

#include<iostream>
using namespace std ;

char cmd[400000] ;
int  v[10009]   ;  

int main(){
    int index0 ,index1 , i , x , y , cn;
    memset(v , -1 ,sizeof(v));
    v[0] = 0 , v[1] = 1 ,v[2] = 2 ,v[3] = 3 ; 
    while(scanf("%d%s%d" ,&index0 , cmd ,&index1)!=EOF){
           x = v[index1] ;   cn = strlen(cmd);
           for(i = cn-1 ; i >=0 ; --i) 
              if(cmd[i]=='f')
                   x += (x%2 == 0 ? 3 : 1) ;
              else  if(cmd[i] == 'b')
                   x -= 2 ;
              else  if(cmd[i]== 'k')
                   printf("%d\n" , x);
              else  if(cmd[i]=='=')
                   printf("%c\n", v[index0] == x ? '=' : '#');
              else  
                   v[index0] = x ;
    }
    return 0 ;
}

【Problem C】

题目类型：稀疏图的二分图匹配

思路分析：

同上 ， 题目太晦涩 

这题点数比较多，有10000，所以不能直接开二维数组，套匈牙利算法。

推荐使用Dinic算法求最大流解决，速度MS比较快。

#include<iostream>
using namespace std ;
const  int  maxn = 20010  ;
const  int  maxe = 500000;
const  int  INF  = 1<<29  ;


struct node{
       int x ,y , c ,next ;
};
node e[maxe] ;
int  es , hd[maxn] , S , T , N;

void ins(int x , int y ,int c){
     e[es].x = x , e[es].y = y ,e[es].c = c ,e[es].next = hd[x] , hd[x] = es ++ ;
     e[es].x = y , e[es].y = x, e[es].c = 0 ,e[es].next = hd[y] , hd[y] = es ++ ;
}

int cur[maxn] , dep[maxn] , ps[maxn] ;
int dinic(){
    int i ,j ,k ,top , tr ,f ,r  ,u , v ,maxf = 0 ;
    while(1){
            memset(dep ,-1,sizeof(dep)); dep[S] = 0 ;  
            f = r = 0 ;  ps[r++] = S ;
            while(f!=r){
                    v = ps[f++] ;
                    for(i = hd[v] ; i!=-1 ; i=e[i].next)
                         if(e[i].c && dep[u = e[i].y] == -1 ) 
                         dep[u] = dep[v] + 1 , ps[r++] = u ;
                    if(dep[T]!=-1) break;
            }
            if(dep[T]==-1) break ;
            i = S , top = 0 ;  memcpy(cur ,hd,sizeof(hd));
            while(1){
                    if(i == T){
                          for(tr = INF , k = 0 ; k<top ; ++k)
                             if(tr > e[ps[k]].c ) tr = e[ps[f = k]].c ;
                          for(k = 0 ; k <top ; ++k)
                             e[ps[k]].c -= tr ,e[ps[k]^1].c += tr ;
                          maxf += tr , i = e[ps[top = f]].x ; 
                    }
                    for(j = cur[i] ;j!=-1 ; j=cur[i]=e[j].next)
                      if(e[j].c && dep[e[j].y]==dep[i]+1) break;
                    if(j!=-1){
                       ps[top++] = j ; i = e[j].y ;
                    }else{
                       if(0==top) break;
                       dep[i] = -1 ; i = e[ps[--top]].x ;
                    }
            }
    }
    return maxf ;
}

int main(){
    int n , job , cnt , k , i , j , v; 
    while(scanf("%d" ,&n)!=EOF){
           es = 0 ; memset(hd ,-1,sizeof(hd)); 
           S = 2*n ; T = 2*n+1 ; N = T ;
           for(k = 0 ; k < n ; ++k){
                 scanf("%d: (%d)" , &job , &cnt);
                 for(i = 0 ; i < cnt ;++i){
                          scanf("%d" ,&v); 
                          ins(job , v , 1 );
                 }
           }
           for(i = 0 ; i<n ; ++i)  ins(S ,i , 1),ins(n+i , T , 1);
           printf("%d\n" ,dinic());
    }
    return 0 ; 
}

【ProblemD】

题目类型：无向图连通性遍历  最大环

思路分析：

首先，既不能套用Tarjan算法，也不能套用求割点或求割边的算法。

注意到本题一个重要的信息：每条边最多属于一个环。

考虑用类似于求割点或割边的算法，一边用DFS遍历图的节点，一边记录部分信息。

首先考虑DFS遍历得到的生成树（如图），若DFS正好遍历到v这个节点，u是v的一个邻节点，显然，u既不属于红点集（否则，v应该在红点集），也不属于灰点集（否则，灰点集应该是v的子孙）。由此可得，若<v,u>边属于题目中的一个环，u只有可能是从根到v路径上的某一点。又由于每边只属于一个环，所以我们只要记录点v在DFS遍历得到的生成树的深度dep[ v ] 这个信息就可以完成要求，因为若<v , u>是回向边，必形成环，环的长度为

Dep[u] - dep[v] +１。

再深入一下思考，这个算法却不适用与求任意无向图的最大环，可以举出反例。

#include<iostream>
using namespace std ;
const int  maxn = 5000 ;
const int  maxe = 10 * maxn ;

struct node{
       int y ,next ;
};
node e[maxe] ;
int  es , hd[maxn] , N ,E ;
int  dep[maxn] , ans ;

void dfs(int x){
     int i , y ;
     for(i = hd[x] ; i!=-1 ; i=e[i].next){
          y = e[i].y ;
          if(dep[y]==-1){
             dep[y] = dep[x] + 1 ;  dfs(y);
          }else{
             ans = max(ans , dep[x]-dep[y]+1);
          }
     }
}

int main(){
    int tst , i , x, y ;
    scanf("%d",&tst);
    while(tst--){
           scanf("%d%d",&N,&E);
           es = 0 ;  memset(hd,-1,sizeof(hd));
           for(i = 0 ; i<E ; ++i){
                  scanf("%d%d",&x,&y); 
                  e[es].y = y , e[es].next = hd[x] , hd[x] = es ++ ;
                  e[es].y = x , e[es].next = hd[y] , hd[y] = es ++ ;
           }
           ans = 0 ;  memset(dep , -1 ,sizeof(dep));
           for(i = 1 ; i<=N ;++i) 
             if(dep[i]==-1){
                 dep[i] = 0 ; dfs(i);
             }
           printf("%d\n" , ans <= 2 ? 0 : ans);
    }
    return 0 ;
}

【ProblemF】

题目类型：BFS + 二分 （或者 最短路 + 二分）

思路分析：

该题的一个切入点在于题目规定了答案的范围[ 0 , 1000]之间，所以可以尝试去二分答案， 看看题目是否等价于具有单调性的可行性问题。很明显可以看出，拉长的棋盘最近距离肯定比压缩的棋盘最近距离大，所以满足单调性。

#include<iostream>
#include<queue>
using namespace std ;

const  int  maxn = 105 * 105 ;
const  int  maxe = 4 * maxn  ;
const  double INF = 1e100    ;
const  double EPS = 1e-8    ;
int dx[]={1,0,-1,0} ,dy[]={0,1,0,-1};

struct node{
       int y , next ;
       double c ;
};
node e[maxe] ;
int  es , hd[maxn] ,S ,T , N ; 
char bd[105][105] ;
int  row ,col ;

inline int sgn(double x){
       return (x>EPS)-(x<-EPS);
}


void ins(int x , int y , double c){
     e[es].y = y , e[es].c = c ,
     e[es].next = hd[x] , hd[x] = es ++ ;
}

double dist[maxn] ; 
int    vis[maxn]  ;

double SPFA(){
       queue<int> Q ; 
       int i , u , v ;
       for(i = 0 ; i <= N ; ++ i)  dist[i] = INF , vis[i] = 0 ;
       dist[S] = 0 , vis[S] = 1 , Q.push(S);
       while(!Q.empty()){
              v = Q.front() ; Q.pop() ;  vis[v] = 0 ;
              for(i = hd[v] ; i!=-1 ; i=e[i].next)
                 if(dist[u = e[i].y] > dist[v] + e[i].c ){
                     dist[u] = dist[v] + e[i].c ; 
                     if(!vis[u])  vis[u] = 1 , Q.push(u);
                 }
       }
       return dist[T] ;
}

double Try(double t ){
     int i , j , k ,nx ,ny; 
     es = 0 ; memset(hd , -1 ,sizeof(hd));  N = row * col + 1 ;
     for(i = 0 ; i <row ; ++ i)
         for(j = 0 ; j <col ; ++j)
           if(bd[i][j]!='#'){
                for(k = 0 ; k < 4 ;++ k){
                    nx = i + dx[k] , ny = j + dy[k]  ;
                    if((nx<0||ny<0||nx>=row||ny>=col)||bd[nx][ny]=='#') continue ;
                    if(k ==0 || k==2) 
                           ins(i*col+j , nx*col+ny ,t);
                    else   
                           ins(i*col+j , nx*col+ny ,1);
                }
               if(bd[i][j]=='S')  
                        S = i*col+j ;
               else  if(bd[i][j]=='E')  
                        T = i*col+j ;
           }
    return  SPFA();
}

int main(){
    int cs , i , tst = 0 ;
    char str[20] ;
    double  des , t1 ,t2 ,t3 , ty;
    scanf("%d" ,&cs);
    while(cs--){
              scanf("%lf%d" ,&des ,&row); gets(str);
              for(i = 0 ; i<row ;++i)  gets(bd[i]);
              col = strlen(bd[0]); 
              t1 = 0 , t3 = 1000 ;
              for(i = 0 ; i < 100 ; ++i){
                      t2 =(t1+t3)/2 ;
                      ty = Try(t2); 
                      if(!sgn(ty-des))  break ;
                      else  if(sgn(ty-des)==1) 
                              t3 = t2 ;
                      else   
                              t1 = t2 ;
              }  
              printf("Case #%d: %0.3lf%s\n" ,++tst , t2*100 ,"%");
    }
    return 0;
}
 

【ProblemG】

题目类型：动态规划 （必须用滚动数组）

思路分析：

设子串S[1..n] ，被匹配串T[1..m]。

Opt[i , j]表示S[1...i] 与 T[1..j]进行匹配，且二者的尾部严格匹配的最小复杂值 。 

动态转移过程：

当S[i] = ' * ' 时 

       Opt[i , j ] = Min( Opt[i - 1, j ] , Opt[i , j - 1] + T[j] - 'a' + 1 ) ;

否则，当S[i] = '?'  时 ， 必须与T[j]匹配

       Opt[i , j]  = Opt[i -1 , j - 1]  + T[j] - 'a' + 1 ;

否则，当S[i] = T[j] 时 ， 也必须匹配

       Opt[i , j ]  = Opt[i - 1, j - 1 ]  + T[j] - 'a' + 1 ;

否则   Opt[i , j] = 无穷大；

【Problem I】

题目类型：多重背包 ， DFS + 贪心剪枝 

思路分析：

第k 个背包选择时有 0 , 1 , ... , k 这k + 1种选择 ， 所以状态可以用一颗排列树表示。

从DFS角度看 ， 复杂度为 15！， 明显复杂度太高，应该剪枝。

从贪心的角度思考，最好选择价格和重量比例比较大的物品比较占优势 ， 所以这个可以作为DFS的上界估计。然后，我们也可以按照这个顺序贪心出一个可能的解（不一定是最优值），这个值用于动态更新最优值，会大大提高搜索的效率。

#include<iostream>
#include<algorithm>
using namespace std ;

typedef __int64 lld ;
struct node{
       lld w , c , n ;
       double val ;
};
node x[20] ;

bool operator < (node a,node b){
     return a.val > b.val ;
}

lld N , M , maxc ,curc , curw ; 

lld comp1(lld st , lld up){
    lld nc , nw , i ;
    nc = nw = 0 ;
    for(i = st ; i <=N ; ++i) 
       if(nw + x[i].w <= up){
             if(nw + x[i].n * x[i].w <= up){
                   nc += x[i].n * x[i].c ;
                   nw += x[i].n * x[i].w ;
             }else{
                   lld cnt = (up - nw)/x[i].w ;
                   nc += cnt * x[i].c ; 
                   nw += cnt * x[i].w ;
             }
       }
    return nc ;
}

double comp2(lld st  , double up){
       double nc , nw ,cnt  ;
       lld i  ;
       nc = nw = 0 ;
       for(i = st ; i<=N ;++i)
           if(nw + (double)(x[i].n * x[i].w) <= up){
                  nc += (double)(x[i].n * x[i].c);
                  nw += (double)(x[i].n * x[i].w);
           }else{
                  cnt = (up - nw)/(double)x[i].w ;
                  nc += cnt * (double)x[i].c ;
                  nw += cnt * (double)x[i].w ; 
                  break ;
           }
     return nc ;
}

void dfs( int dep){
     if(dep > N){
          maxc = max( maxc , curc); return ;
     }
     for(lld i = 0 ; i<=x[dep].n && (curw + x[dep].w *i <= M) ; ++i){
               curw += i*x[dep].w ;
               curc += i*x[dep].c ;
               lld trc = comp1(dep+1 , M - curw );
               double mc =  comp2(dep+1 , (double)(M - curw));
               maxc = max(maxc , trc + curc);
               if(((double)curc) + mc > (double)maxc )   dfs(dep+1);
               curw -= i*x[dep].w  ;
               curc -= i*x[dep].c  ;  
     }
}

int main(){
    lld cs , i ;
    scanf("%I64d" ,&cs);
    while(cs--){
           scanf("%I64d%I64d" , &N ,&M);
           for(i = 1 ; i<=N ;++i)  scanf("%I64d" ,&x[i].w);
           for(i = 1 ; i<=N ;++i)  scanf("%I64d" ,&x[i].c);
           for(i = 1 ; i<=N ;++i){
               x[i].n = i ; 
               x[i].val = (double)x[i].c / (double)x[i].w ;
           }
           sort(x+1 , x+N+1);
           maxc = comp1(1 , M);
           curc = curw = 0 ;
           dfs(1);
           printf("%I64d\n" ,maxc);
    }
    return 0;
}

悲剧啊。。。。。。。。。。。。

还有好几道题目没弄出来。。。。。。。。