Posted Updated  Semprathlon / Simfae Dean ACM-ICPC / Programing4 minutes read (About 633 words)

2015 Multi-University Training Contest 3

1001 Magician

具有肉眼可见的可用线段树解决的统计操作要求。
但是区间更新异常繁杂。
不要拘泥于区间内具体的数据选取，而应该采用状态转移。
除了向上传递操作以外，注意查询操作时不要把区段查询结果直接更新到左右子树上（覆盖区域并不一致） 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
/**
 * 2015年7月29日 上午10:35:39
 * PrjName:hdu5316-2
 * @ Semprathlon
 */
import java.io.*;
import java.util.*;

public class Main {
    final static long inf=0x4000000000000000L;
    final static int maxn=100010;
    static int[] a=new int[maxn+1];
    static SegTree tr=new SegTree(1, maxn);
    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();
            for(int i=1;i<=n;i++) 
                a[i]=in.nextInt();
            tr.reset(1,1, n, a);
            for(int i=1;i<=m;i++){
                int k=in.nextInt();
                int x=in.nextInt();   
                if (k==0){
                    //out.println(tr.query(x, y));
                    int y=in.nextInt();
                    long ans=-inf;
                    long[] res=tr.query(1,x, y);
                    for(int j=0;j<4;j++)
                        ans=Math.max(ans, res[j]);
                    out.println(ans);
                }
                else{
                    long y=in.nextLong();
                    tr.update(1,x, y);
                }
                    
            }
        }
        out.flush();
        out.close();
    }

}

class SegTree{
    final static long inf=0x4000000000000000L;
    int[] l,r,mid;
    long[][] s;
    SegTree(int x,int y){
        l=new int[(y-x+2)<<2];
        r=new int[(y-x+2)<<2];
        mid=new int[(y-x+2)<<2];
        s=new long[(y-x+2)<<2][4];
        build(1,x,y);
    }
    void build(int k,int x,int y){
        /*l=x;r=y;*/mid[k]=(x+y)>>1;
        if (x<y){
            build(k<<1,x, mid[k]);
            build(k<<1|1,mid[k]+1, y);
        }
        //s0=s1=s2=s3=-inf;
    }
    void reset(int k,int x,int y,int[] a){
        l[k]=x;r[k]=y;mid[k]=(x+y)>>1;
        if (x<y){
            reset(k<<1,x, mid[k], a);
            reset(k<<1|1,mid[k]+1, y, a);
            up(s[k],s[k<<1],s[k<<1|1]);
        }
        else{
            if ((mid[k]&1)>0){//odd
                s[k][0]=a[mid[k]];
                s[k][1]=s[k][2]=s[k][3]=-inf;
            }
            else{//even
                s[k][3]=a[mid[k]];
                s[k][0]=s[k][1]=s[k][2]=-inf;
            }
        }
            
    }
    void up(long[] k,long[] l,long[] r){
        k[0]=k[1]=k[2]=k[3]=-inf;
        k[0]=Math.max(k[0], l[0]+r[2]);//odd-odd
        k[0]=Math.max(k[0], l[1]+r[0]);
        
        k[1]=Math.max(k[1], l[1]+r[1]);//odd-even
        k[1]=Math.max(k[1], l[0]+r[3]);
        
        k[2]=Math.max(k[2], l[2]+r[2]);//even-odd
        k[2]=Math.max(k[2], l[3]+r[0]);
        
        k[3]=Math.max(k[3], l[3]+r[1]);//even-even
        k[3]=Math.max(k[3], l[2]+r[3]);
        
        k[0]=Math.max(k[0], l[0]);
        k[0]=Math.max(k[0], r[0]);
        
        k[1]=Math.max(k[1], l[1]);
        k[1]=Math.max(k[1], r[1]);
        
        k[2]=Math.max(k[2], l[2]);
        k[2]=Math.max(k[2], r[2]);
        
        k[3]=Math.max(k[3], l[3]);
        k[3]=Math.max(k[3], r[3]);
    }
    long[] query(int k,int x,int y){
        long[] res=new long[4];
        if (x==l[k]&&r[k]==y){
            res=s[k].clone();
        }
        else{
            long[] L,R;
            if (x<=mid[k]) L=query(k<<1,x,Math.min(y, mid[k])).clone();
            else L=new long[]{-inf,-inf,-inf,-inf};
            if (mid[k]<y) R=query(k<<1|1,Math.max(mid[k]+1, x),y).clone();
            else R=new long[]{-inf,-inf,-inf,-inf};
            up(res,L,R);
        }
        return res;
    }
    void update(int k,int x,long d){
        if (l[k]==r[k]){
            if ((mid[k]&1)>0){//odd
                s[k][0]=d;
                s[k][1]=s[k][2]=s[k][3]=-inf;
            }
            else{//even
                s[k][3]=d;
                s[k][0]=s[k][1]=s[k][2]=-inf;
            }
            return;
        }
        if (x<=mid[k]) update(k<<1,x,d);
        if (mid[k]<x) update(k<<1|1,x,d);
        up(s[k],s[k<<1],s[k<<1|1]);
    }
}

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

1010 Crazy Bobo

Posted Updated  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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
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。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
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;
}

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
/**
 * 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 Updated  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) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * 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做查询时，往死胡同里钻而且根本停不下来，啊啊啊啊…… 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#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 Updated  Semprathlon / Simfae Dean ACM-ICPC / Programinga minute read (About 160 words)

hdu 3853 LOOPS 递推求期望

hdu 3853 LOOPS

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#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 Updated  Semprathlon / Simfae Dean ACM-ICPC / Programinga minute read (About 133 words)

2015 Multi-University Training Contest 2

1002 Buildings

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#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 Updated  Semprathlon / Simfae Dean ACM-ICPC / Programing9 minutes read (About 1292 words)

2015 Multi-University Training Contest 1

1002 Assignment RMQ

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
/**
 * 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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
/**
 * 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 Updated  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……
后来就醉了一样的胡乱的写了个匹配也不太行……

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#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 Updated  Semprathlon / Simfae Dean ACM-ICPC / Programing2 minutes read (About 277 words)

hdu 5115 Dire Wolf 区间DP

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
/**
 * 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 Updated  Semprathlon / Simfae Dean ACM-ICPC / Programing2 minutes read (About 229 words)

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

贪心？走进死胡同了吧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
/**
 * 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 Updated  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，需枚举的状态略多；于是折成两半枚举。前后两段合拼时，不是正向地求和，而是逆向查询，节约了时间 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
/**
 * 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();
	}
}
Follow

Categories

Tags

ACM-ICPC14
AC自动机1
AWS2
Adobe1
Angular1
Apache1
Arch Linux2
BFS2
BIT3
Bestcoder23
Bitset3
Bootstrap1
C++2
CCPC1
Catalan1
CentOS3
Clover2
Compiler1
Contest6
Cpp1
DFS3
DNS1
DP13
DSDT3
Data Analytics2
Dinic1
Docker1
Eclipse1
Expect1
Fibonacci1
Frontend1
GLUT1
GPT1
GUI1
Gentoo1
Geometry1
Git1
Github2
Graduate1
HTML1
Hash2
Heap1
Interview1
JNUOJ1
Java12
K8s1
KMP1
Linux3
Live Archive2
MBR1
MS=DOS1
Mac14
Manhattan1
Multi-Uni5
MySQL8
Möbius反演1
NAS2
NetworkFlow1
NoSQL1
OS2
OpenCV1
OpenGL2
Python10
RMQ1
Regional3
Repost1
Ryzen1
SQLserver1
SSL1
System Design1
TOEFL1
Template3
Tree1
Trie2
UEFI4
UX1
Ubuntu14
Unix1
Windows2
Wordpress3
ZFS1
ZOJ1
ajax1
asm1
css1
cuda1
cudnn1
curl1
docker1
es61
font1
ftp1
git1
gitlab1
hardware1
hdu2
hexo1
html1
https1
iOS1
interview1
java1
javascript1
jdk1
jquery1
js7
json1
kext1
macOS2
network1
nginx4
node1
nodejs1
npm1
php8
python1
react2
react native1
regex1
string4
二分图1
二分查找3
博弈1
容斥原理3
并查集1
并行计算1
微积分1
扫描线3
数列1
数独1
数论1
概率2
模拟4
欧拉回路1
百度之星1
知乎1
离散化1
约瑟夫1
线段树3
组合数学1
网络赛2
背包1
背包问题1
转载博文1
递归1

Subscribe for updates

Links

×