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();
	}
}
Posted Updated  Semprathlon / Simfae Dean a few seconds read (About 0 words)

我的动态

Posted Updated  Semprathlon / Simfae Dean ACM-ICPC / Programing2 minutes read (About 232 words)

hdu 4810 Wall Painting 位操作

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

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

}
Posted Updated  Semprathlon / Simfae Dean ACM-ICPC / Programing2 minutes read (About 240 words)

hdu 4825 Xor Sum 位操作 字典树

遇到本题，在对象成员中申请数组空间的话，会不明就里地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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
/**
 * 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();
    }

}
Posted Updated  Semprathlon / Simfae Dean ACM-ICPC / Programing3 minutes read (About 398 words)

hdu 2604 Queuing 递推/DP 矩阵快速幂 Trie数辅助

过于傻气的递推公式！
状态傻傻分不清楚
写矩阵乘法，混淆了左乘与右乘。

引用一个类比字符串模式匹配的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
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
/**
 * 2015年7月14日 下午4:51:05
 * PrjName:hdu2604
 * @ Semprathlon
 */
import java.io.*;

class Matrix {
    int n, m, mod;
    int[][] dat;

    Matrix(int n, int m, int mod) {
        this.n = n;
        this.m = m;
        this.mod = mod;
        this.dat = new int[n][m];
    }

    Matrix(Matrix mat) {
        this.n = mat.n;
        this.m = mat.m;
        this.mod = mat.mod;
        this.dat = new int[n][m];
        for (int i = 0; i < mat.n; i++)
            for (int j = 0; j < mat.m; j++)
                this.dat[i][j] = mat.dat[i][j];
    }

    static Matrix one(Matrix mat) {
        Matrix res = new Matrix(mat.n, mat.m, mat.mod);
        for (int i = 0; i < Math.min(mat.n, mat.m); i++)
            res.dat[i][i] = 1;
        return res;
    }

    Matrix add(Matrix c) {
        Matrix res = new Matrix(this);
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++) {
                res.dat[i][j] += c.dat[i][j];
                res.dat[i][j] %= mod;
            }
        return res;
    }

    Matrix mul(Matrix c) {
        Matrix res = new Matrix(this.n, c.m, mod);
        for (int i = 0; i < this.n; i++)
            for (int j = 0; j < c.m; j++)
                for (int k = 0; k < this.m; k++) {
                    res.dat[i][j] += this.dat[i][k] * c.dat[k][j];
                    res.dat[i][j] %= mod;
                }

        return res;
    }

    Matrix pow(int m) {
        Matrix n = new Matrix(this);
        Matrix res = Matrix.one(n);
        while (m > 0) {
            if ((m & 1) > 0)
                res = res.mul(n);
            n = n.mul(n);
            m >>= 1;
        }
        return res;
    }
}

public class Main {
    static Matrix mat, p;

    static void init(int mod) {
        mat = new Matrix(4, 1, mod);
        mat.dat = new int[][] { { 9 }, { 6 }, { 4 }, { 2 } };
        p = new Matrix(4, 4, mod);
        p.dat = new int[][] { { 1, 0, 1, 1 }, { 1, 0, 0, 0 }, { 0, 1, 0, 0 },
                { 0, 0, 1, 0 } };
    }

    static int solve(int l, int m) {
        mat = p.pow(l - 4).mul(mat);
        if (l > 4)
            return mat.dat[0][0];
        else if (l > 0)
            return mat.dat[4 - l][0];
        return 0;
    }

    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));
        while (in.nextToken() != StreamTokenizer.TT_EOF) {
            int l = (int) in.nval;
            in.nextToken();
            int m = (int) in.nval;
            init(m);
            out.println(solve(l, m) % m);    
        }
        out.flush();
        out.close();
    }
}
Posted Updated  Semprathlon / Simfae Dean ACM-ICPC / Programing4 minutes read (About 537 words)

hdu 4185 Oil Skimming 二分图匹配

Oil Skimming

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
/** Aug 24, 2015 11:15:57 AM
 * PrjName:hdu4185
 * @author Semprathlon
 */
import java.io.*;
import java.util.*;
public class Main {

    /**
     * @param args
     */
    static char[][] mp;
    //static int[][] adj;
    static int[] match;
    static boolean[] vis;
    static int n,cnt,sum;
    final static int[][] dir={ {-1,0},{1,0},{0,-1},{0,1}};
    final static int maxn=605;
    static Vector<Integer>[] adj=new Vector[maxn*maxn>>1];
    static HashMap<Integer, Integer> sta=new HashMap<Integer,Integer>();
    static HashMap<Integer, Integer> stb=new HashMap<Integer,Integer>();
    static int geta(Pt p){
        int hash=p.hashCode();
        if (sta.containsKey(hash))
            return sta.get(hash);
        else{
            sta.put(hash, ++cnt);
            return cnt;
        }
    }
    static int getb(Pt p){
        int hash=p.hashCode();
        if (stb.containsKey(hash))
            return stb.get(hash);
        else{
            stb.put(hash, ++sum);
            return sum;
        }
    }
    static boolean cango(int x,int y){
        if (x<0||x>=n||y<0||y>=n||mp[x][y]!='#') return false;
        return true;
    }
    static boolean dfs(int u){
        for(int v:adj[u]){
            if (vis[v]) continue;
            vis[v]=true;
            if (match[v]<0||dfs(match[v])){
                match[v]=u;
                return true;
            }
        }
        return false;
    }
    static int maxmatch(){
        int res=0;
        Arrays.fill(match, -1);
        for(int i=1;i<=cnt;i++){
            Arrays.fill(vis, false);
            if (dfs(i)) res++;
        }
        return res;
    }
    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);
        for(int i=0;i<maxn*maxn>>1;i++) adj[i]=new Vector<Integer>();
        int T=in.nextInt(),cas=0;
        
        while(T-->0){
            n=in.nextInt();
            mp=new char[n][n];
            for(int i=0;i<n*n>>1;i++) adj[i].clear();
            sta.clear();stb.clear();cnt=sum=0;
            for(int i=0;i<n;i++){
                String s=in.next();
                for(int j=0;j<n;j++)
                    mp[i][j]=s.charAt(j);
            }
            for(int i=0;i<n;i++)
                for(int j=0;j<n;j++)
                    if (mp[i][j]=='#'){
                        Pt p=new Pt(i, j,n);
                        for(int k=0;k<4;k++){
                            int x=i+dir[k][0];
                            int y=j+dir[k][1];
                            if (((x+y)&1)>0&&cango(x,y)){
                                Pt q=new Pt(x, y,n);
                                adj[geta(p)].add(getb(q));
                                //adj[q.hashCode()].add(p);
                            }
                        }
                    }
            match=new int[sum+1];
            vis=new boolean[sum+1];
            out.println("Case "+(++cas)+": "+maxmatch());
        }
        out.flush();
        out.close();
    }

}
class Pt{
    int x,y,n;
    Pt(int _x,int _y,int _n){
        x=_x;y=_y;n=_n;
    }
    Pt(int hash,int _n){
        n=_n;
        y=hash%n;
        x=hash/n;
    }
    public int hashCode(){
        return x*n+y;
    }
}
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());
    }
 
}

折腾了过长的时间，原因：
这不是通常意义上的可随意匹配的二分图。
既然是二分图，就有把节点分为两类的依据。
由题中给定的结合规则，一定是一个(x+y)为偶数的点与一个(x+y)为奇数的点相匹配，且是相邻点的匹配。
所以会将两类点分别加入两个表中，并进行hash操作节约存储空间。
“奇”的点总是不少于“偶”的点？

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
Docker2
Eclipse1
Expect1
Fibonacci1
Frontend1
GLUT1
GPT1
GUI1
Gentoo1
Geometry1
Git1
Github2
Graduate1
HTML1
Hash2
Heap1
Interview4
JNUOJ1
Java12
K8s1
KMP1
Linux3
Live Archive2
MBR1
MS=DOS1
Mac14
Manhattan1
Multi-Uni5
MySQL8
Möbius反演1
NAS2
NetworkFlow1
NoSQL1
OS2
OpenCV1
OpenGL2
Python11
RMQ1
React2
Regional3
Repost1
Ryzen1
SQLserver1
SSH1
SSL1
System Design1
TOEFL1
Template3
Tree1
Trie2
TypeScript2
UEFI4
UX1
Ubuntu15
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
network2
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

×