ZOJ Monthly, July 2015

B.Help Bob

Time Limit: 2 Seconds Memory Limit: 65536 KB

• Problem Description
  There is a game very popular in ZJU at present, Bob didn’t meant to participate in it. But he decided to join it after discovering a lot of pretty girls playing it.
  There are n stones on the ground and they are marked as 1 to n respectively. There will be 2 players in each competition. And the game rules are simple, A and B take turns to move. Each round, one of them can only take 1 number away, and then pick out all the divisors of the choosed number. When anyone who can not take away 1 number any longer, he will fail the whole game.

• Input
  There are multiple cases. Each case include an integer number n (0 ≤ n ≤ 100).

• Output
  For each case, A win, output “win”. If not, output”fail”.

• Sample Input
  3
  4

• Sample Output
  win
  win

乍一看是博弈，其实啥都没！问题中的决策不一定最优，只要求获胜的可能……

import java.io.*;
import java.util.*;
public class Main {
	public static void main(String[] args) throws IOException {
		StreamTokenizer in=new StreamTokenizer(new BufferedInputStream(System.in));
		PrintWriter out=new PrintWriter(System.out);
		while(in.nextToken()!=StreamTokenizer.TT_EOF){
			int n=(int)in.nval;
			if (n==0) out.println("fail");
			else out.println("win");
		}
		out.flush();
		out.close();
	}
}

E.The Exchange of Items

Time Limit: 2 Seconds Memory Limit: 65536 KB

• Problem Description
  Bob lives in an ancient village, where transactions are done by one item exchange with another. Bob is very clever and he knows what items will become more valuable later on. So, Bob has decided to do some business with villagers.
  At first, Bob has N kinds of items indexed from 1 to N, and each item has Ai. There are M ways to exchanges items. For the ith way (Xi, Yi), Bob can exchange one Xith item to one Yith item, vice versa. Now Bob wants that his ith item has exactly Bi, and he wonders what the minimal times of transactions is.

• Input
  There are multiple test cases.
  For each test case: the first line contains two integers: N and M (1 < = N, M <= 100).
  The next N lines contains two integers: Ai and Bi (1 < = Ai, Bi <= 10,000).
  Following M lines contains two integers: Xi and Yi (1 < = Xi, Yi <= N).
  There is one empty line between test cases.

• Output
  For each test case output the minimal times of transactions. If Bob could not reach his goal, output -1 instead.

• Sample Input
  2 1
  1 2
  2 1
  1 2

4 2
1 3
2 1
3 2
2 3
1 2
3 4

• Sample Output
  1

-1

被这题的思维折腾哭了啊，从不可行的二分图，到搜索以及最短路径，再到乱七八糟的区间DP，不知多晚才拾起网络流……
伪最短路，RE

import java.io.*;
import java.util.*;
public class Main {
	static int[] a,f;
	static int[][] E;
	static int maxstep=10000;
	static int n,m;
	final static int pri=17;
	static int hashCode(int[] a){
		int s1=0,s2=0;
		int len=a.length;
		/*for(int i=0;i<len;i++){
			s1*=19;
			s1+=a[i]%19;
		}*/
		for(int i=0;i<len;i++){
			s2*=pri;
			s2+=Math.abs(a[i])%pri;
		}
		return s2;
	}
	static int spfa(int[] st){
		HashMap<Integer, Integer> mp=new HashMap<Integer, Integer>();
		BitSet vis=new BitSet();
		Queue<int[]> que=new LinkedList<int[]>();
		que.add(st);
		mp.put(hashCode(st), 0);
		vis.set(hashCode(st));
		while(!que.isEmpty()){
			int[] u=que.poll();
			int p=mp.get(hashCode(u));
			if (p>=maxstep) return -1;
			for(int i=1;i<=m;i++){
				int[] v=u.clone();
				v[E[0][i]]--;
				v[E[1][i]]++;
				int hv=hashCode(v);
				if (hv==0) return p+1;
				if (que.contains(v)){
					int q=mp.get(hv);
					if (p+1<q){
						//vis.replace(hv, p+1);
						mp.remove(hv);
						mp.put(hv, p+1);
						if (!vis.get(hv)){
							que.add(v);
							vis.set(hv);
						}
					}
				}
				else{
					mp.put(hv, p+1);
					if (!vis.get(hv)){
						que.add(v);
						vis.set(hv);
					}
				}
			}
		}
		return -1;
	}
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		StreamTokenizer in=new StreamTokenizer(new BufferedInputStream(System.in));
		PrintWriter out=new PrintWriter(System.out);
		while(in.nextToken()!=StreamTokenizer.TT_EOF){
			n=(int)in.nval;
			in.nextToken();
			m=(int)in.nval;
			a=new int[n+1];
			for(int i=1;i<=n;i++){
				in.nextToken();
				int x=(int)in.nval;
				in.nextToken();
				int y=(int)in.nval;
				a[i]=y-x;
			}
			E=new int[2][m+1];
			for(int i=1;i<=m;i++){
				in.nextToken();
				int u=(int)in.nval;
				in.nextToken();
				int v=(int)in.nval;
				E[0][i]=u;E[1][i]=v;
				//a[u]--;a[v]++;out.println(hashCode(a));
			}
			int res=spfa(a);
			out.println(res);
			out.flush();
		}
		out.close();
	}
}

最小费用流，AC

import java.io.BufferedInputStream;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;
import java.util.StringTokenizer;

import com.sun.org.apache.regexp.internal.recompile;


public class Main {
    
        public static void main(String[] args) throws IOException{
                StreamTokenizer cin = new StreamTokenizer(new BufferedInputStream(System.in)); 
                InputReader in = new InputReader(System.in)  ;
                PrintWriter out = new PrintWriter(System.out) ;
               
                while(cin.nextToken() != cin.TT_EOF){
                	     new Task().solve(cin, out)  ;   //out.flush() ;
                }
                
               out.flush() ;
                
                /*
                int t = in.nextInt() ;
                while(t-- > 0){
                	      new Task().solve(in , out)  ;
                }
                out.flush() ; 
                */
        }
     
}

class Task{
         
	     static  int[] a = new int[108] ;
	     static  int[] b = new int[108] ;
	     
	     static  ArrayList<Integer>[] adj = new ArrayList[108] ;
	     
	     static  ArrayList<Integer>[] colorg = new ArrayList[108]  ;
	     static  int[] color = new int[108] ;
	     
	     void dfs(int u , int c){
	    	      color[u] = c ;
	    	      colorg[c].add(u) ;
	    	      for(int v : adj[u]){
	    	    	     if(color[v] == -1) dfs(v , c) ; 
	    	      }
	     }
	     
	     
	     int[]  dist = new int[108] ;
	     boolean[] in = new boolean[108] ;
	     
	     void  spfa(int s){
	    	       Arrays.fill(dist, Integer.MAX_VALUE) ;
	    	       dist[s] = 0 ;
	    	       Arrays.fill(in, false) ;
	    	       in[s] = true ;
	    	       Queue<Integer> q = new LinkedList<Integer>() ;
	    	       q.add(s) ;
	    	       while(! q.isEmpty()){
	    	    	       int u = q.poll()  ;   in[u] = false ;
	    	    	       for(int v : adj[u]){
	    	    	    	         if(dist[u] + 1 < dist[v]){
	    	    	    	        	    dist[v] = dist[u] + 1 ;
	    	    	    	        	    if(! in[v]){
	    	    	    	        	    	    in[v] = true ; q.add(v) ;
	    	    	    	        	    }
	    	    	    	         }
	    	    	       }
	    	       }
	     }
          
	      public void solve(StreamTokenizer  cin , PrintWriter out) throws IOException{
		    	    int n =  (int) cin.nval ;
	                cin.nextToken() ; int m = (int) cin.nval ;
	 	      
	                for(int i = 1 ; i <= n ; i++){
	                   	    cin.nextToken() ; a[i] = (int) cin.nval ;
	                        cin.nextToken() ; b[i] = (int) cin.nval ;
	                }
	                
	                
	                for(int i = 1 ; i <= n ; i++) adj[i] = new ArrayList<Integer>() ;
	         
	                
	                while(m-- > 0){
	             	      cin.nextToken() ;  int u = (int) cin.nval ;
	             	      cin.nextToken() ;  int v = (int) cin.nval ;
	             	      adj[u].add(v) ;
	             	      adj[v].add(u) ;
	                }
	                
	                Arrays.fill(color, -1) ;
	                for(int i = 0 ; i <= n ; i++) colorg[i] = new ArrayList<Integer>() ;
	                
	                int k = 0 ; 
	                for(int i = 1 ; i <= n ; i++){
	             	      if(color[i] == -1){
	             	    	    dfs(i , k++) ;
	             	      }
	                }
	                
	                int sum = 0 ;
	                for(int i = 0 ; i < k ; i++){
	             	        int sa = 0 , sb = 0 ;
	             	        for(int u : colorg[i]){
	             	        	     sa += a[u] ;
	             	        	     sb += b[u] ;
	             	        	     sum += Math.abs(a[u] - b[u]) ;
	             	        }
	             	        if(sa != sb){
	             	        	    out.println(-1) ;
	             	             	return  ;
	             	        } 
	                }
	                
	                   ArrayList<Integer> adx = new ArrayList<Integer>() ; 
	                   ArrayList<Integer> ady = new ArrayList<Integer>() ; 
	                   for(int i = 1 ; i <= n ; i++){
	                           if(a[i] > b[i]) 
	                        	       adx.add(i) ;
	                           else if(a[i] < b[i])
	                        	       ady.add(i) ;       
	                   }
	                   
	                   
	                   int N= adx.size() ;
	                   int M= ady.size() ;
	                   Mincostflow mcf = new Mincostflow(0 , 2*N+2*M+1)  ;
	                   
	                   for(int i = 1 ; i <= N ; i++){
	                	      int u = adx.get(i-1) ; 
	                	      mcf.add(i, N + i, a[u] - b[u] , 0)  ;
	                	      mcf.add(0, i, Integer.MAX_VALUE , 0) ;
	                   }
	                   
	                   for(int i = 1 ; i <= M ; i++){
	                	      int u = ady.get(i-1) ; 
	                	      mcf.add(2*N + i, 2*N +  M +  i, b[u] - a[u] , 0 )  ;
	                	      mcf.add(2*N+M+i , 2*N+2*M+1, Integer.MAX_VALUE , 0) ;
	                   }
	                   
	                   for(int i = 1 ; i <= adx.size() ; i++){
	                	       int u = adx.get(i-1) ;
	                	       spfa(u) ;
	                	       
	                	       for(int j = 1 ; j <= ady.size() ; j++){
	                	    	       int v = ady.get(j-1) ;
	                	    	       if(dist[v] == Integer.MAX_VALUE) continue ;		   
	                	    	       mcf.add(N+i, 2*N+j, Integer.MAX_VALUE, dist[v] )  ;
	                	       }
	                	       
	                   }
	                
	                
	                
	                   out.println(mcf.mincostflow()) ;
		                   
	            
	      }
      
}


class Mincostflow{
	
	public Mincostflow(int sourse , int meet){
		         this.source = sourse ;
		         this.meet = meet ;
		         Arrays.fill(g, 0) ;
			     id = 1 ;
	}
	
	static final int maxn = 5000 , maxm = 50000 ;
	static class Edge{
	       int v , f , w , next ;
	       Edge(){}
	       Edge(int _v , int _f , int _w , int _next){
	    	        this.v = _v ;
	    	        this.f = _f ;
	    	        this.w = _w ;
	    	        this.next = _next ;
	       }
	}
	
	static int[]  g = new int[maxn + 10] ;
	static Edge[] e = new Edge[maxm + 10] ;
	int  source , meet ;
	int  id ;

	void  add(int u , int v  , int f , int w){
	      e[++id] = new Edge(v , f , w , g[u]) ;
	      g[u] = id ;
	      e[++id] = new Edge(u , 0 , -w , g[v]) ;
	      g[v] = id ;
	}

	Queue<Integer> que  = new LinkedList<Integer>() ;
	static boolean[] in = new boolean[maxn + 10] ;
	static int[]  dist = new int[maxn + 10] ;
	static int[]  pv = new int[maxn + 10] ;
	static int[]  pe = new int[maxn + 10] ;

	boolean bfs(){
	     while(! que.isEmpty()) que.poll() ;
	     que.add(source) ;
	     Arrays.fill(dist, Integer.MAX_VALUE) ;
	     dist[source] = 0  ;
	     in[source] = true ;
	     while(! que.isEmpty()){
	           int u = que.poll() ;
	           in[u] = false ;
	           for(int i = g[u] ; i > 0; i = e[i].next){
	                int  v = e[i].v ;
	                if(e[i].f > 0 && dist[u] + e[i].w < dist[v]){
	                      dist[v] = dist[u] + e[i].w ;
	                      pv[v] = u ;
	                      pe[v] = i ;
	                      if(! in[v]){
	                            in[v] = true ;  que.add(v) ;
	                      }
	                }
	           }
	     }
	     return  dist[meet] < Integer.MAX_VALUE  ;
	}

	int  augment(){
	     int u = meet  ;
	     int delta = Integer.MAX_VALUE ;
	     while(u != source){
	           delta = Math.min(delta , e[pe[u]].f) ;
	           u = pv[u] ;
	     }
	     u = meet ;
	     while(u != source){
	           e[pe[u]].f -= delta ;
	           e[pe[u] ^ 1].f += delta ;
	           u = pv[u] ;
	     }
	     return dist[meet] * delta ;
	}

	int  mincostflow(){
	     int ans = 0 ;
	     while(bfs())  ans += augment() ;
	     return ans ;
	}
}


class InputReader{
    public BufferedReader reader;
    public StringTokenizer tokenizer;

    public InputReader(InputStream stream){
           reader = new BufferedReader(new InputStreamReader(stream), 32768);
           tokenizer = null;
    }

    public String next(){
        while(tokenizer == null || !tokenizer.hasMoreTokens()){
            try{
                tokenizer = new StringTokenizer(reader.readLine());
            }catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return tokenizer.nextToken();
    }

    public int nextInt() {
        return Integer.parseInt(next());
    }
    
    public long nextLong() {
        return Long.parseLong(next());
    }

}

H.Twelves Monkeys

Time Limit: 5 Seconds Memory Limit: 32768 KB

• Problem Description
  James Cole is a convicted criminal living beneath a post-apocalyptic Philadelphia. Many years ago, the Earth’s surface had been contaminated by a virus so deadly that it forced the survivors to move underground. In the years that followed, scientists had engineered an imprecise form of time travel. To earn a pardon, Cole allows scientists to send him on dangerous missions to the past to collect information on the virus, thought to have been released by a terrorist organization known as the Army of the Twelve Monkeys.
  The time travel is powerful so that sicentists can send Cole from year x[i] back to year y[i]. Eventually, Cole finds that Goines is the founder of the Army of the Twelve Monkeys, and set out in search of him. When they find and confront him, however, Goines denies any involvement with the viruscan. After that, Cole goes back and tells scientists what he knew. He wants to quit the mission to enjoy life. He wants to go back to the any year before current year, but scientists only allow him to use time travel once. In case of failure, Cole will find at least one route for backup. Please help him to calculate how many years he can go with at least two routes.

• Input
  The input file contains multiple test cases.
  The first line contains three integers n,m,q(1≤ n ≤ 50000, 1≤ m ≤ 50000, 1≤ q ≤ 50000), indicating the maximum year, the number of time travel path and the number of queries.
  The following m lines contains two integers x,y(1≤ y ≤ x ≤ 50000) indicating Cole can travel from year x to year y.
  The following q lines contains one integers p(1≤ p ≤ n) indicating the year Cole is at now

• Output
  For each test case, you should output one line, contain a number which is the total number of the year Cole can go.

• Sample Input
  9 3 3
  9 1
  6 1
  4 1
  6
  7
  2

• Sample Output
  5
  0
  1

• Hint
  6 can go back to 1 for two route. One is 6-1, the other is 6-7-8-9-1. 6 can go back to 2 for two route. One is 6-1-2, the other is 6-7-8-9-1-2.

多好的静态区间查询啊，可是不好好写O(n)，写O(n^2)的就TLE。

vector<pair<int,int> > vec;
int n,m,q;

int bisearch(int key){
		int l=1,r=m+1,mid=1,a;
		while(l<r-1){
			mid=(l+r)>>1;
			a=vec[mid-1].first;
			if (a<=key)
				l=mid;
			else
				r=mid;
		}
		if (vec[l-1].first<key) return l;
		return l-1;
	}

int main()
{
    while(~scanf("%d%d%d",&n,&m,&q)){
			vec.clear();
			for(int i=1;i<=m;i++){
				int u,v;
				scanf("%d%d",&u,&v);
				vec.push_back(make_pair(u,v));
			}
			sort(vec.begin(),vec.end());
			//for(int i=0;i<m;i++) printf("%d:%d %d\n",i+1,vec[i].first,vec[i].second);
			for(int i=1;i<=q;i++){
				int p;
				scanf("%d",&p);
				int h=bisearch(p);
				if (m-h<2){
					puts("0");
					continue;
				}
				int min1,min2;
				min1=min2=p;
				for(int j=h;j<m;j++){
					int k=vec[j].second;
					if (k<min1)
                    {
                        min2=min1;min1=k;
                    }
                    else
                        min2=min(min2,k);
				}

				//sort(v.begin(),v.end());
				printf("%d\n",p-min2);
			}
		}
    return 0;
}

用线段树查询区间次小值也可行，但是从后往前处理跟方便，而且一次性完成。

/**
 * 2015年7月30日 上午10:02:07
 * PrjName:zoj3888
 * @ Semprathlon
 */
import java.io.*;
import java.util.*;
public class Main {
	static int[][] f;
	final static int maxn=50010;
	static Vector<Vector<Integer>> a=new Vector<Vector<Integer>>();
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		StreamTokenizer in=new StreamTokenizer(new BufferedInputStream(System.in));
		PrintWriter out=new PrintWriter(System.out);
		for(int i=1;i<maxn;i++)
			a.add(new Vector<Integer>());
		while(in.nextToken()!=StreamTokenizer.TT_EOF){
			int n=(int)in.nval;
			in.nextToken();
			int m=(int)in.nval;
			in.nextToken();
			int q=(int)in.nval;
			for(int i=1;i<=n;i++)
				a.get(i-1).clear();
			for(int i=1;i<=m;i++){
				in.nextToken();
				int u=(int)in.nval;
				in.nextToken();
				int v=(int)in.nval;
				a.get(u-1).add(v);
			}
			f=new int[n+2][2];
			f[n+1][0]=f[n+1][1]=n+1;
			for(int i=n;i>0;i--){
				f[i][0]=Math.min(i, f[i+1][0]);
				f[i][1]=Math.min(i, f[i+1][1]);
				Vector<Integer> v=a.get(i-1);
				for(int j=0;j<v.size();j++)
					if (v.get(j)<=f[i][0]){
						f[i][1]=f[i][0];f[i][0]=v.get(j);
					}
					else
						f[i][1]=Math.min(f[i][1], v.get(j));
			}
			while(q-->0){
				in.nextToken();
				int p=(int)in.nval;
				out.println(p-f[p][1]);
			}
		}
		out.flush();
		out.close();
	}

}

J.Wumpus

Time Limit: 2 Seconds Memory Limit: 65536 KB

• Problem Description
  One day Leon finds a very classic game called Wumpus.The game is as follow.
  Once an agent fell into a cave. The legend said that in this cave lived a kind of monster called Wumpus, and there were horrible pits which could lead to death everywhere. However, there were also a huge amount of gold in the cave. The agent must be careful and sensitive so that he could grab all of the gold and climb out of the cave safely.
  The cave can be regarded as a n*n board. In each square there could be a Wumpus, a pit, a brick of gold, or nothing. The agent would be at position (0,0) at first and headed right.(As the picture below) For each step, there are six possible movements including going forward, turning left, turning right, shooting, grabbing the gold, and climbing out of the cave. If the agent steps into a square containing a pit or Wumpus, he will die. When the agent shoots, the Wumpus in front of him will die. The goal of the agent is to grab all of the gold and return to the starting position and climb out(it's OK if any Wumpus is still living).When a brick of gold is grabbed successfully, you will gain 1000 points. For each step you take, you will lose 10 points. Your job is to help him compute the highest point he can possibly get. For the purpose of simplification, we suppose that there is only one brick of gold and the agent cannot shoot the Wumpus. If there is a pit at (0, 0), the agent dies immediately. There will not be a Wumpus at (0, 0).

Input
There are multiple cases. The first line will contain one integer k that indicates the number of cases.
For each case:
The first line will contain one integer n (n < = 20).
The following lines will contain three integers, each line shows a position of an object. The first one indicates the type of the object. 1 for Wumpus, 2 for pit and 3 for gold. Then the next two integers show the x and y coordinates of the object.
The input end with -1 -1 -1. (It is guaranteed that no two things appear in one position.)

Output
The output contains one line with one integer, which is the highest point Leon could possibly get. If he cannot finish the game with a non-negative score, print “-1”.

Sample Input
2
3
1 1 1
2 2 0
3 2 2
-1 -1 -1
3
1 1 1
3 2 2
-1 -1 -1

Sample Output
850
870

Hint
For the sample 1, the following steps are taken:
turn left, forward, forward, turn right, forward, forward, grab, turn left, turn left, forward, forward, turn left, forward, forward, climb.
There are in all 15 steps, so the final score is 840. For the sample 2 , the path is as follow:

一来一去的搜索……