Posted 07/27/2015Updated 07/19/2023 Semprathlon / Simfae Dean ACM-ICPC / Programing16 minutes read (About 2397 words)

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:

一来一去的搜索……

Posted 07/26/2015Updated 07/19/2023 Semprathlon / Simfae Dean ACM-ICPC / Programing2 minutes read (About 239 words)

BestCoder 1st Anniversary T_T

1001 Souvenir

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)

/**
 * 2015年7月25日 下午7:07:41
 * PrjName:0725-01
 * @ Semprathlon
 */
public class Main {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        InputReader in=new InputReader(System.in);
        PrintWriter out=new PrintWriter(System.out);
        int T=in.nextInt();
        while(T-->0){
            int n=in.nextInt();
            int m=in.nextInt();
            int p=in.nextInt();
            int q=in.nextInt();
            int ans=0,has=0;
            if (m*p>q)
                ans+=n/m*q;
            else ans+=n/m*m*p;
            ans+=n%m*p;
            if ((n+m)/m*q<ans) ans=(n+m)/m*q;
            out.println(ans);
        }
        out.flush();
        out.close();
    }

}

1002 Hidden String

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
用Trie做查询时，往死胡同里钻而且根本停不下来，啊啊啊啊……

#include <cstdio>
#include <cstring>
char s[200], con[] = "anniversary";

int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%s", s);
        int len = strlen(s);
        bool flag = false;
        for(int i = 0; i <= 8; i++)
        {
            for(int j = i + 1; j <= 9; j++)
            {
                int k = 0;
                while(k < len && strncmp(con, s + k, i + 1) != 0)
                    k ++;
                if(k == len) 
                    continue;
                k += i + 1;
                while(k < len && strncmp(con + i + 1, s + k, j - i) != 0)
                    k ++;
                if(k == len) 
                    continue;
                k += j - i;
                while(k < len && strncmp(con + j + 1, s + k, 10 - j) != 0)
                    k ++;
                if(k != len)
                {
                    flag = true;
                    break;
                }
            }
        }
        if(flag) 
            puts("YES");
        else 
            puts("NO");
    }
}

这里的枚举倒是简洁得出奇。

1003 Sequence

Time Limit: 2000/2000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
下意识地做了贪心，果然被hack

Posted 07/24/2015Updated 07/19/2023 Semprathlon / Simfae Dean ACM-ICPC / Programinga minute read (About 160 words)

hdu 3853 LOOPS 递推求期望

hdu 3853 LOOPS

计算期望，往往是从末状态到初状态倒推的，相见恨晚

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
#include<math.h>
using namespace std;
const int MAXN=1010;
const double eps=1e-5;
double dp[MAXN][MAXN];
double p1[MAXN][MAXN];
double p2[MAXN][MAXN];
double p3[MAXN][MAXN];

int main()
{
    int R,C;
    while(scanf("%d%d",&R,&C)!=EOF)
    {
        for(int i=1;i<=R;i++)
          for(int j=1;j<=C;j++)
            scanf("%lf%lf%lf",&p1[i][j],&p2[i][j],&p3[i][j]);
        dp[R][C]=0;
        for(int i=R;i>=1;i--)
          for(int j=C;j>=1;j--)
          {
              if(i==R&&j==C)continue;
              if(fabs(1-p1[i][j])<eps)continue;
              dp[i][j]=p2[i][j]/(1-p1[i][j])*dp[i][j+1]+p3[i][j]/(1-p1[i][j])*dp[i+1][j]+2/(1-p1[i][j]);
          }
        printf("%.3lf\n",dp[1][1]);
    }
    return 0;
}

Posted 07/24/2015Updated 07/19/2023 Semprathlon / Simfae Dean ACM-ICPC / Programinga minute read (About 133 words)

2015 Multi-University Training Contest 2

1002 Buildings

特别拐弯抹角的平面几何模拟计算

#include<cctype>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<queue>
#include<stack>
#include<set>
#include<map>

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
const int maxn=210;
const int inf=0x7fffffff;
const double eps=1e-3;

int N,M;


int main()
{
    int x,y;
    while(~scanf("%d%d%d%d",&N,&M,&x,&y))
    {
        if (M<N)
        {
            swap(N,M);
            swap(x,y);
        }
            int t0=(N+1)>>1;
            int up=x-1;
            int down=N-x;
            int left=y-1;
            int right=M-y;
            //cout<<t0<<endl;
            if ((N&1)&&N==M&&x==y&&x==(N+1)/2)
                printf("%d\n",t0-1);
            /*else if (min(up,down)>t0)
                printf("%d\n",min(max(left,right),min(up,down)));*/
            else
            {
                x=min(x,N-x+1);
                y=min(y,M-y+1);
                t0=max(t0,min(N-x,y));
                t0=min(t0,(M+1)/2);
                printf("%d\n",t0);
            }

    }
    return 0;
}

Posted 07/22/2015Updated 07/19/2023 Semprathlon / Simfae Dean ACM-ICPC / Programing9 minutes read (About 1292 words)

2015 Multi-University Training Contest 1

1002 Assignment RMQ

/**
 * 2015年7月21日 下午1:40:29
 * PrjName:0721-02
 * @ Semprathlon
 */
import java.io.*;
import java.util.*;
public class Main {
    final static int maxm=20,maxn=100010;
    static int[] a;
    static int[][] maxsum,minsum;
    static int n,k;
    
    static void RMQ(){ //预处理->O(nlogn){
        for(int i = 1; i != maxm; ++i)
            for(int j = 1; j <= n; ++j)
                if(j + (1 << i) - 1 <= n){
                    maxsum[i][j] = Math.max(maxsum[i - 1][j], maxsum[i - 1][j + (1 << i >> 1)]);
                    minsum[i][j] = Math.min(minsum[i - 1][j], minsum[i - 1][j + (1 << i >> 1)]);
                }
    }
    
    static int query(int src,int des){
        int k = (int)(Math.log(des - src + 1.0) / Math.log(2.0));
        int maxres = Math.max(maxsum[k][src], maxsum[k][des - (1 << k) + 1]);
        int minres = Math.min(minsum[k][src], minsum[k][des - (1 << k) + 1]);
        return maxres-minres;
    }
    
    static int bisearch(int p){
        int l=p,r=n;
        int res=p;
        while(l<=r){
            int mid=(l+r)>>1;
            int dif=query(p,mid);
            if (dif<k){
                res=mid;l=mid+1;
            }
            else
                r=mid-1;
        }
        return res-p+1;
    }
    
    public static void main(String[] args) throws IOException{
        // TODO Auto-generated method stub
        InputReader in=new InputReader(System.in);
        PrintWriter out=new PrintWriter(System.out);
        int T=in.nextInt();
        while(T-->0){
            n=in.nextInt();
            k=in.nextInt();
            a=new int[n+1];
            maxsum=new int[maxm][n+1];
            minsum=new int[maxm][n+1];
            for(int i=1;i<=n;i++){
                a[i]=in.nextInt();
                maxsum[0][i]=minsum[0][i]=a[i];
            }
            RMQ();
            long res=0L;
            for(int i=1;i<=n;i++)
                //out.print(bisearch(i)+" ");
                res+=bisearch(i);
            out.println(res);
        }
        out.flush();
        out.close();
    }

}

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());
    }
}

1007 Tricks Device

netflow,maxflow,Dinic

/**
 * 2015年7月22日 上午10:07:44
 * PrjName:0721-07
 * @ Semprathlon
 */
import java.io.*;
import java.util.*;

class Edge{
    int to,cap,rev,next;
    Edge(){}
    Edge(int t,int w,int r,int nt){
        to=t;cap=w;rev=r;next=nt;
    }
    Edge(Edge e){
        this.to=e.to;
        this.cap=e.cap;
        this.rev=e.rev;
        this.next=e.next;
    }
    void set(int t,int w,int r,int nt){
        to=t;cap=w;rev=r;next=nt;
    }
    void set(Edge e){
        this.to=e.to;
        this.cap=e.cap;
        this.rev=e.rev;
        this.next=e.next;
    }
}
class Queue<T>{
    T[] data;
    int size,h,r;
    /*Queue(Class<T> c,int sz){
        size=sz;
        @SuppressWarnings("unchecked")
        final T[] tmp=(T[])Array.newInstance(c, sz);
        data=tmp;
    }*/
    Queue(int sz){
        size=sz;
        data=(T[])new Object[sz];
    }
    void clear(){
        h=r=0;
    }
    boolean empty(){
        return h==r;
    }
    boolean full(){
        return (r+1)%size==h;
    }
    void push(T n){
        data[r]=n;
        r=(r+1)%size;
    }
    T pop(){
        T tmp=data[h];
        h=(h+1)%size;
        return tmp;
    }
}

public class Main {
    static int[] head,dis,cnt;
    static boolean[] vis;
    static Edge[] G;
    static int n,m;
    static Queue<Integer> que;
    static void bfs(int st){
        Arrays.fill(dis, -1);
        que.clear();
        dis[st]=0;
        vis[st]=true;
        que.push(st);
        while(!que.empty()){
            int u=que.pop();
            for(int i=head[u];i>-1;i=G[i].next){
                int v=G[i].to;
                if (G[i].cap>0&&!vis[v]){
                    dis[v]=dis[u]+1;
                    que.push(v);
                    vis[v]=true;
                }
            }
        }
    }
    static int dfs(int u,int d){
        if (u==n) return d;
        int res=0;
        for(int i=head[u];i>-1;i=G[i].next){
            int v=G[i].to;
            if (G[i].cap>0&&dis[v]==dis[u]+1){
                int tmp=dfs(v,Math.min(d,G[i].cap));
                G[i].cap-=tmp;
                G[G[i].rev].cap+=tmp;
                d-=tmp;
                res+=tmp;
            }
        }
        return res;
    }
    static int max_flow(int s,int t){
        int res=0;
        for(;;){
            Arrays.fill(vis, false);
            bfs(s);
            if (!vis[t]) return res;
            res+=dfs(s,Integer.MAX_VALUE);
        }
    }
    static void addedge(int from,int to,int cap){
        G[head[0]]=new Edge(to, cap, head[0]+1, head[from]);
        head[from]=head[0]++;
        G[head[0]]=new Edge(from,cap,head[0]-1,head[to]);
        head[to]=head[0]++;
    }
    static void spfa(int st){
        que.clear();
        que.push(st);
        dis[st]=0;
        vis[st]=true;
        while(!que.empty()){
            int u=que.pop();vis[u]=false;
            for(int i=head[u];i>-1;i=G[i].next){
                int v=G[i].to;
                if (dis[u]+G[i].cap<dis[v]){
                    dis[v]=dis[u]+G[i].cap;
                    if (!vis[v]){ 
                        que.push(v);
                        vis[v]=true;
                    }
                }
            }
        }
    }
    static int spfa2(int s,int t){
        Arrays.fill(cnt, Integer.MAX_VALUE);
        Arrays.fill(vis, false);
        que.clear();
        que.push(s);
        cnt[s]=0;
        vis[s]=true;
        while(!que.empty()){
            int u=que.pop();vis[u]=false;
            for(int i=head[u];i>-1;i=G[i].next){
                int v=G[i].to;
                if (dis[u]+G[i].cap!=dis[v]) continue;
                if (!vis[v]){ 
                    que.push(v);
                    vis[v]=true;
                }
                cnt[v]=Math.min(cnt[v], cnt[u]+1);
            }
            
        }
        return cnt[t];
    }
    static void init(){
        G=new Edge[(m<<1)+1];
        head=new int[(m<<1)+1];
        dis=new int[n+1];
        cnt=new int[n+1];
        vis=new boolean[n+1];
        Arrays.fill(head, -1);
        Arrays.fill(dis, Integer.MAX_VALUE);
        head[0]=1;
        //que=new Queue(Integer.class,(m<<1)+1);
        que=new Queue<Integer>((m<<1)+1);
    }
    public static void main(String[] args) throws IOException,InterruptedException {
        // TODO Auto-generated method stub
        StreamTokenizer cin = new StreamTokenizer(new BufferedInputStream(System.in)); 
        //InputReader in=new InputReader(System.in);
        PrintWriter out=new PrintWriter(System.out);
        while(cin.nextToken()!=StreamTokenizer.TT_EOF){
            n=(int)cin.nval;
            cin.nextToken();
            m=(int)cin.nval;
            init();
            for(int i=1;i<=m;i++){
                cin.nextToken();
                int u=(int)cin.nval;
                cin.nextToken();
                int v=(int)cin.nval;
                cin.nextToken();
                int w=(int)cin.nval;
                addedge(u, v, w);
                //addedge(v, u, w);
            }
            spfa(1);
            //out.println(dis[n]);
            //max_flow(1, n);
            //init2();
            Dinic dinic=new Dinic(1, n);
            for(int u=1;u<=n;u++)
                for(int i=head[u];i>-1;i=G[i].next){
                    int v=G[i].to;
                    if (dis[u]+G[i].cap==dis[v])
                        dinic.add(u, v, 1);
                }
            /*init();
            for(int i=1;i<=U[0];i++)
                addedge(U[i],V[i].to,1);*/
            out.println(dinic.maxflow()+" "+(m-spfa2(1,n)));
            /*for(int i=1;i<=n;i++)
                for(int j=head[i];j>-1;j=G[j].next)
                    out.println(j+"\t:"+i+" "+G[j].to+" "+G[j].cap+" "+G[j].rev+" "+G[j].next);*/
            
        }
        out.flush();
        out.close();
    }

}

class Dinic{
    public Dinic(int sourse , int meet){
                 this.sourse = sourse ; 
                 this.meet = meet ;
                 Arrays.fill(g,  0) ;
                 id = 1 ;
    }

    static final  int  maxn = 2008 , maxm = 500000 ;
    static class Edge{
           int v , f ,next ;
           Edge(){}
           Edge(int _v , int _f , int _next){
                 this.v = _v ;
                 this.f = _f ;
                 this.next = _next ;
           }
    };
    int  sourse , meet ;
    int  id ;
    static Edge[] e = new Edge[maxm*2 + 10] ;
    static int[] g = new int[maxn + 10] ;

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

    Queue<Integer> que  = new Queue<Integer>(maxm);
    static boolean[] vis = new boolean[maxn + 10] ;
    static int[]  dist = new int[maxn + 10] ;

    void bfs(){
             Arrays.fill(dist, 0) ;
             while(! que.empty()) que.pop() ;
             que.push(sourse) ;
             vis[sourse] = true ;
             while(! que.empty()){
                  int u = que.pop() ;
                  for(int i = g[u] ; i > 0 ; i = e[i].next){
                       int v = e[i].v ;
                       if(e[i].f  > 0 && !vis[v]){
                             que.push(v) ;
                             dist[v] = dist[u] + 1 ;
                             vis[v] = true ;
                       }
                  }
             }
    }

    int  dfs(int u , int delta){
             if(u == meet) return delta ;
             int ans = 0 ;
             for(int i = g[u] ; i > 0  && delta > 0  ; i = e[i].next){
                   int  v = e[i].v ;
                   if(e[i].f  > 0 && dist[v] == dist[u] + 1){
                        int d = dfs(v , Math.min(delta , e[i].f)) ;
                        e[i].f -= d ;
                        e[i^1].f += d ;
                        delta -= d ;
                        ans += d ;
                   }
             }
             return ans ;
    }

    public int  maxflow(){
                 int ans = 0 ;
                 while(true){
                     Arrays.fill(vis, false) ;
                     bfs() ;
                     if(! vis[meet]) return ans  ;
                     ans += dfs(sourse , Integer.MAX_VALUE) ;
                 }
    }

}

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());
    }

}

特别复杂的套模板

Posted 07/20/2015Updated 07/19/2023 Semprathlon / Simfae Dean ACM-ICPC / Programing3 minutes read (About 416 words)

Bestcoder

Protest一时爽，final test全爆零 QwQ

1001 wyh2000 and a string problem

1	out.println(str.matches(".w.y.h.")\|\|str.matches(".v{2,}.y.h.")?"Yes":"No");

偷懒着用正则表达式，华丽地TLE……
后来就醉了一样的胡乱的写了个匹配也不太行……

import java.io.*;
import java.util.*;
import java.math.*;
import java.util.regex.*;
import com.sun.org.apache.xalan.internal.xsltc.compiler.Pattern;
public class Main {
    static boolean check(String str){
        int res=0;
        int i,len=str.length();
        for(i=0;i<len-1;i++)
            if (str.charAt(i)=='w'||str.charAt(i)=='v'&&str.charAt(i+1)=='v'){
                res|=1;break;
            }
        for(;i<len;i++)
            if (str.charAt(i)=='y'){
                res|=2;break;
            }
        for(;i<len;i++)
            if (str.charAt(i)=='h'){
                res|=4;break;
            }
        return res==7;
    }
    public static void main(String[] args)  throws IOException{
        // TODO Auto-generated method stub
         InputReader in = new InputReader(System.in)  ;
         PrintWriter out = new PrintWriter(System.out) ;
         int T=in.nextInt();
         while(T-->0){
             String str=in.next();
             out.println(check(str)?"Yes":"No");
             out.flush();
         }
         out.close();
    }
}

1002 wyh2000 and pupil

#include<cctype>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<queue>
#include<stack>
#include<set>
#include<map>

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
const int maxn=200010;
const int inf=0x7fffffff;
const double eps=1e-3;

short col[maxn];
int s[2];

struct Edge
{
    int to,next;
    Edge(){}
    Edge(int v,int w):to(v),next(w){}
} edge[maxn];
int head[maxn];

void addedge(int u,int v)
{
    edge[head[0]]=Edge(v,head[u]);
    head[u]=head[0]++;
}

void init()
{
    fill(head,head+maxn,-1);
    head[0]=1;
}

int bfs(int u)
{
    queue<int> q;
    q.push(u);
    col[u]=0;
    while(!q.empty())
    {
        int p=q.front();
        s[col[p]]++;
        q.pop();
        for(int i=head[p];i!=-1;i=edge[i].next)
        {
            int v=edge[i].to;
            if (col[v]>=0)
            {
                if (col[v]==col[p]) return -1;
            }
            else
            {
                col[v]=1^col[p];
                q.push(v);
            }

        }
    }
    return 0;
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        init();
        int n,m;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            addedge(u,v);
            addedge(v,u);
        }

        int sum=0;
        fill(col+1,col+n+1,-1);
        for(int i=1;i<=n;i++)
            if (col[i]<0)
        {
            s[0]=s[1]=0;
            if (bfs(i)<0)
            {
                sum=-1;break;
            }
            else sum+=max(s[0],s[1]);
        }
        if (n==sum) sum--;
        if (sum<1||n-sum<1)
            puts("Poor wyh");
        else
            printf("%d %d\n",sum,n-sum);
    }
    return 0;
}

事实证明这并不是二分图匹配；并没有什么典型的算法让两个集合中的一个最大……
用DFS或BFS都可实现填色。

Posted 07/18/2015Updated 07/19/2023 Semprathlon / Simfae Dean ACM-ICPC / Programing2 minutes read (About 277 words)

hdu 5115 Dire Wolf 区间DP

2014ACM/ICPC亚洲区北京站
Dire Wolf

/**
 * 2015年7月18日 上午9:55:52
 * PrjName:hdu5115
 * @ Semprathlon
 */
import java.io.*;
public class Main {
    final static long inf=0x7FFFFFFFFFFFFFFFL;
    static long min(long a,long b){
        return Math.min(a, b);
    }
    public static void main(String[] args)  throws IOException{
        // TODO Auto-generated method stub
        StreamTokenizer in=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        PrintWriter out=new PrintWriter(new OutputStreamWriter(System.out));
        in.nextToken();
        int T=(int)in.nval,cas=0;
        int[] a,b;
        long[][] f;
        while(T-->0){
            in.nextToken();
            int n=(int)in.nval;
            a=new int[n+2];
            b=new int[n+2];
            f=new long[n+2][n+2];
            for(int i=1;i<=n;i++){
                in.nextToken();
                a[i]=(int)in.nval;
            }
            for(int i=1;i<=n;i++){
                in.nextToken();
                b[i]=(int)in.nval;
            }
            f[1][1]=a[1]+b[2];
            f[n][n]=a[n]+b[n-1];
            for(int i=2;i<n;i++)
                f[i][i]=a[i]+b[i-1]+b[i+1];
            for(int i=1;i<=n;i++)
                for(int j=i+1;j<=n;j++)
                    f[i][j]=inf;
            for(int j=0;j<=n;j++)
                for(int i=1;i+j<n+1;i++)
                    for(int k=i;k<=i+j;k++){
                        f[i][i+j]=min(f[i][i+j],f[i][k-1]+f[k+1][i+j]+a[k]+b[i-1]+b[i+j+1]);
                        //out.print(f[i][i+j]+" ");
                    }
            /*for(int i=0;i<=n+1;i++){out.println();
                for(int j=0;j<=n+1;j++)
                    out.print(f[i][j]+"\t");    
            }*/
                        
            
            /*for(int i=0;i<n;i++)
                for(int j=1;j<n-i;j++){
                    if (j==1)
                        min(f[j][j+i],f[j+1][j+i]+a[j]);
                    if (j>1)
                        min(f[j][j+i],f[j+1][j+i]+a[j]+b[j-1]);
                    if (i+j<n)
                        min(f[j][j+i],f[j][j+i-1]+a[j+i]+b[j+i+1]);
                    if (i+j==n)
                        min(f[j][j+i],f[j][j+i-1]+a[j+i]);
                    for(int k=j+1;k<j+i;k++)
                        min(f[j][j+i],f[j][k-1]+a[k]+f[k+1][j+i]);
                }*/
            out.println("Case #"+(++cas)+": "+f[1][n]);
            out.flush();
        }
        
        out.close();
    }
}

贪心真的是要贪婪死了。。。
已消除区段。。。其实对后续操作没有影响，符合无后效性。

Posted 07/18/2015Updated 07/19/2023 Semprathlon / Simfae Dean ACM-ICPC / Programing2 minutes read (About 229 words)

ACM-ICPC 2014 Beijing Regional / hdu 5115 区间DP

贪心？走进死胡同了吧

/**
 * 2015年7月18日 上午9:55:52
 * PrjName:hdu5115
 * @ Semprathlon
 */
import java.io.*;
public class Main {
	final static long inf=0x7FFFFFFFFFFFFFFFL;
	static long min(long a,long b){
		return Math.min(a, b);
	}
	public static void main(String[] args)  throws IOException{
		// TODO Auto-generated method stub
		StreamTokenizer in=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
		PrintWriter out=new PrintWriter(new OutputStreamWriter(System.out));
		in.nextToken();
		int T=(int)in.nval,cas=0;
		int[] a,b;
		long[][] f;
		while(T-->0){
			in.nextToken();
			int n=(int)in.nval;
			a=new int[n+2];
			b=new int[n+2];
			f=new long[n+2][n+2];
			for(int i=1;i<=n;i++){
				in.nextToken();
				a[i]=(int)in.nval;
			}
			for(int i=1;i<=n;i++){
				in.nextToken();
				b[i]=(int)in.nval;
			}
			f[1][1]=a[1]+b[2];
			f[n][n]=a[n]+b[n-1];
			for(int i=2;i<n;i++)
				f[i][i]=a[i]+b[i-1]+b[i+1];
			for(int i=1;i<=n;i++)
				for(int j=i+1;j<=n;j++)
					f[i][j]=inf;
			for(int j=0;j<=n;j++)
				for(int i=1;i+j<n+1;i++)
					for(int k=i;k<=i+j;k++){
						f[i][i+j]=min(f[i][i+j],f[i][k-1]+f[k+1][i+j]+a[k]+b[i-1]+b[i+j+1]);
						//out.print(f[i][i+j]+" ");
					}
			/*for(int i=0;i<=n+1;i++){out.println();
				for(int j=0;j<=n+1;j++)
					out.print(f[i][j]+"\t");	
			}*/
						
			
			/*for(int i=0;i<n;i++)
				for(int j=1;j<n-i;j++){
					if (j==1)
						min(f[j][j+i],f[j+1][j+i]+a[j]);
					if (j>1)
						min(f[j][j+i],f[j+1][j+i]+a[j]+b[j-1]);
					if (i+j<n)
						min(f[j][j+i],f[j][j+i-1]+a[j+i]+b[j+i+1]);
					if (i+j==n)
						min(f[j][j+i],f[j][j+i-1]+a[j+i]);
					for(int k=j+1;k<j+i;k++)
						min(f[j][j+i],f[j][k-1]+a[k]+f[k+1][j+i]);
				}*/
			out.println("Case #"+(++cas)+": "+f[1][n]);
			out.flush();
		}
		
		out.close();
	}

}

Posted 07/18/2015Updated 07/19/2023 Semprathlon / Simfae Dean ACM-ICPC / Programing2 minutes read (About 225 words)

ACdreamOJ 1726 hash 二进制表示下的枚举

http://acdream.info/problem?pid=1726
Problem Description

Recently, Losanto find an interesting Math game. The rule is simple: Tell you a number H, and you can choose some numbers from a set {a[1],a[2],……,a[n]}.If the sum of the number you choose is H, then you win. Losanto just want to know whether he can win the game.

Input

There are several cases.
In each case, there are two numbers in the first line n (the size of the set) and H. The second line has n numbers {a[1],a[2],……,a[n]}.0<n<=40, 0<=H<10^9, 0<=a[i]<10^9,All the numbers are integers.

Output

If Losanto could win the game, output “Yes” in a line. Else output “No” in a line.

Sample Input

10 87
2 3 4 5 7 9 10 11 12 13
10 38
2 3 4 5 7 9 10 11 12 13

Sample Output

No
Yes

最大的n值为40，需枚举的状态略多；于是折成两半枚举。前后两段合拼时，不是正向地求和，而是逆向查询，节约了时间

/**
 * 2015年7月17日 下午5:41:50
 * PrjName:acd1726
 * @ Semprathlon
**/
import java.io.*;
import java.util.*;
public class Main {
	public static void main(String[] args) throws IOException {
		StreamTokenizer cin = new StreamTokenizer(new InputStreamReader(System.in));
		PrintWriter out = new PrintWriter(System.out);
		HashSet<Long> map = new HashSet<Long>();
		while (cin.nextToken() != StreamTokenizer.TT_EOF) {
			int n = (int) cin.nval;
			cin.nextToken();
			int m = (int) cin.nval;
			map.clear();
			int[] num = new int[n];
			for (int i = 0; i < n; i++) {
				cin.nextToken();
				num[i] = (int) cin.nval;
			}
			int t = (n + 1) / 2;
			for (int i = 0; i < (1 << t); i++) {
				long sum = 0;
				for (int j = 0; j < t; j++) {
					if ((i & (1 << j)) > 0)
						sum += num[j];
				}
				if (sum > m)
					continue;
				map.add(sum);
			}
			int tt = n - t;
			boolean flag = map.contains(m);
			for (int i = 0; i < (1 << tt); i++) {
				long sum = 0;
				for (int j = 0; j < tt; j++) {
					if ((i & (1 << j)) > 0)
						sum += num[t + j];
				}
				if (sum > m)
					continue;
				if (map.contains(m - sum)) {
					flag = true;
					break;
				}
			}
			if (flag)
				out.println("Yes");
			else
				out.println("No");
			// out.flush();
		}
		out.flush();
	}
}

Posted 07/17/2015Updated 07/19/2023 Semprathlon / Simfae Dean ACM-ICPC / Programing2 minutes read (About 232 words)

hdu 4810 Wall Painting 位操作

本题题意甚是费解。
找到合适的位操作，再运用组合数，是关键。

/**
 * 2015年7月15日 上午11:21:15
 * PrjName:hdu4825
 * @ Semprathlon
 */

import java.io.*;

class Trie {
    private final int maxd = 33;
    private long data;
    private Trie ch0, ch1;

    void insert(long n) {
        Trie rt = this;
        for (int i = maxd - 1; i >= 0; i--) {
            if ((n & (1L << i)) == 0L) {// 0
                if (rt.ch0 == null)
                    rt.ch0 = new Trie();
                rt = rt.ch0;
            } else {// 1
                if (rt.ch1 == null)
                    rt.ch1 = new Trie();
                rt = rt.ch1;
            }
            if (i == 0)
                rt.data = n;
        }
    }

    long query(long n) {
        Trie rt = this;
        for (int i = maxd - 1; i >= 0; i--) {
            if ((n & (1L << i)) > 0L && rt.ch0 != null || rt.ch1 == null)// 0
                rt = rt.ch0;
            else if (rt.ch1 != null)// 1
                rt = rt.ch1;
        }
        return rt.data;
    }
}

public class Main {
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(
                new InputStreamReader(System.in)));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        int cas = 0;
        in.nextToken();
        int T = (int) in.nval;
        while (T-- > 0) {
            Trie tr = new Trie();
            in.nextToken();
            int n = (int) in.nval;
            in.nextToken();
            int m = (int) in.nval;
            for (int i = 1; i <= n; i++) {
                in.nextToken();
                tr.insert((long) in.nval);
            }
            out.println("Case #" + (++cas) + ":");
            for (int i = 1; i <= m; i++) {
                in.nextToken();
                out.println(tr.query((long) in.nval));
            }
        }
        out.flush();
        out.close();
    }

}