oyjpArt ACM/ICPC算法程序设计空间

// I am new in programming, welcome to my blog
I am oyjpart(alpc12, 四城)
posts - 224, comments - 694, trackbacks - 0, articles - 6

说题

Posted on 2008-08-02 16:05 oyjpart 阅读(3212) 评论(3)  编辑 收藏 引用 所属分类: ACM/ICPC或其他比赛
PKU3034 Whac-a-Mole
很有意思的题目,打地鼠。
简单的记忆化搜索。trick在于你有可能移出地鼠区,形成一个更优的解。

PKU2280 Amphiphilic Carbon Molecules
首先可以证明要求的线一定由两点确定。
基本算法:枚举点+极角序+一圈扫描。
难点1:计较排序
难点2:一圈扫描时候的计数。
巧妙的转化:枚举一个点x之后将所有的黑点移到关于x的对称点上,这样题目就转化成了:
求一条线,这条线上和这条线的一侧的点的和最大。简单多了。
这是去年省赛A题,当时就是用这种方法AC的。
// Solution by alpc12
#include 
<algorithm>
#include 
<math.h>
using namespace std;

#define Max(a,b)((a)>(b)?(a):(b))

struct Point{
    
int x, y;
    
bool mk;
    
    
bool operator < (const Point &a) const{
        
if (y >= 0 && a.y < 0return true;
        
else if (y < 0 && a.y >= 0return false;
        
if (y == 0 && a.y == 0){
            
if (x >= 0 && a.x < 0return true;
            
if (x < 0 && a.x >= 0return false;
            
return abs(x) < abs(a.x); 
        }
        
int t = x * a.y - y * a.x;
        
return  t == 0 ? x*+ y*< a.x*a.x + a.y*a.y : t > 0;
    };

} p[
1010], pp[1010];

int n;
int nn;
int ans;

int det(Point &a, Point &b){
    
return a.x * b.y - a.y * b.x;
}

int dot(Point &a, Point &b){
    
return a.x * b.x + a.y * b.y;
}

void solve(int x){
    
//printf("Center %d (%d, %d)\n", x, p[x].x, p[x].y);
    nn = 0;
    
int i;
    
for (i = 0; i < n; i++if (i != x){
        pp[nn].x 
= p[i].x - p[x].x;
        pp[nn].y 
= p[i].y - p[x].y;
        pp[nn].mk 
= p[i].mk;
        
if(pp[nn].mk) pp[nn].x = -pp[nn].x, pp[nn].y = -pp[nn].y;
        nn
++;
    }
    sort(pp, pp 
+ nn);
    
int a = 0, b = 0, cnt = 0;
    
for(i = 0; i < nn; ++i) {
        
if(det(pp[a], pp[i]) >= 0) {
            b 
= i;
            cnt
++;
        } 
    }
    ans 
= Max(ans, cnt);
    
while(1) {
        
int aa = a;
        
for(; det(pp[aa], pp[a]) == 0 && dot(pp[aa], pp[a]) >= 0 && aa < nn; ++aa) {
            cnt
--;
        }
        
if(aa == nn) break;
        a 
= aa;
        
int bb = (b+1)%nn;
        
for(; det(pp[aa], pp[bb]) >= 0; bb = (bb+1)%nn) {
            cnt
++;
            b 
= bb;
        }
        ans 
= Max(ans,cnt);
    }
}

int main(){

    
//freopen("t.in", "r", stdin);

    
while (scanf("%d"&n), n){
        
int t, i;
        
for (i = 0; i < n; i++){
            scanf(
"%d%d%d"&p[i].x, &p[i].y, &t);
            p[i].mk 
= (t == 1);
        }
        
if (n == 1) {printf("1\n"); continue;}
        ans 
= 0;
        
for (i = 0; i < n; i++)
            solve(i);
        printf(
"%d\n", ans + 1);
    }
    
return 0;   
}

PKU2949 Word Rings
经典题。
首先将输入的单词看成一条边。它连接的左右各2字符形成的点。
那么新的图点为26*26个。
然后二分枚举答案ans,将原来的图的权w转化为ans-w,
用Bellman Ford判负权回路。如果有负权回路,说明
sigma(ans) + sigma(w) < 0
即 ans * cycle_length < sigma(w)
sigma(w)是原本的单词长度和,而ans * cycle_length则是枚举答案之后那个环的单词长度和
所以 ans 可以继续增大。 这样就构成了二分。
// Solution by alpc12
#include <stdio.h>
#include 
<string.h>

#define Max(a,b) ((a)>(b)?(a):(b))

const int M = 200020;
const int N = 26*26;

struct Edge
{
    
int x, y;
    
double w;
    Edge() {}
    Edge(
int xx, int yy, double ww) : x(xx), y(yy), w(ww) {
    }
};

int n, m, nv;
Edge e[M];
double dist[N];

bool bellman_ford(double ans) {
    
int i,j;
    
for(i = 0; i < nv; ++i) {
        
bool change = false;
        
for(j = 0; j < m; ++j) {
            
int &x= e[j].x, &= e[j].y;
            
double w = e[j].w;
            
if(dist[y] > dist[x] + ans - w) {
                change 
= true;
                dist[y] 
= dist[x] + ans - w;
            }
        }
        
if(!change) return true;
    }
    
return false;
}

int calc(char a, char b) {
    
return (a-'a'* 26 + b-'a';
}

int main()
{
    freopen(
"t.in""r", stdin);

    
char line[1010];
    
int i, max;
    
bool chk[N];
    
while(scanf("%d\n"&n), n) {
        memset(chk, 
0sizeof(chk));
        m 
= nv = 0;
        
for(i = 0; i < n; ++i) {
            gets(line);
            
int len;
            
if((len=strlen(line)) <= 2while(1) printf("1");
            max 
= Max(max, len);
            
int a = calc(line[0], line[1]), b = calc(line[len-2], line[len-1]);
            
if(!chk[a]) chk[a] = 1, nv++
            
if(!chk[b]) chk[b] = 1, nv++;
            e[m
++= Edge(a,b,(double)len);
        }


        
double lo = 0, hi = max;
        
while(hi > lo + 0.005) {
            
double mid = lo+(hi-lo)/2;
            
if(!bellman_ford(mid)) {
                lo 
= mid;
            } 
else hi = mid;
        }
        
if(lo < 1e-7) printf("No solution.\n");
        
else printf("%.2lf\n", lo);
    }

    
return 0;
}


PKU2793 Cactus
这个题目的要求:
1.求一个图所有的环的长度
2.判断一个图中任意两个环是否共边
3.判断一个图是否连通

一个图的环的求法(DFS):
若现在在dfs 节点x,其子节点y是一个灰色节点(已经遍历到,但子树没有遍历完的节点),那么就存在一个x->y->...->x的环。从x向上找一直到y就是环了。
// solution by alpc12 
// 注意这个代码在pku上会runtime error,栈溢出。
// 因为java的栈空间很小。
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.PrintStream;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    
int n;

    final 
int N = 20010;
    
    
private class Edge {
        
int x, y;
        
public boolean inCycle;
        
int other(int z) {
            
return x == z ? y : x;
        }
        
public Edge(int x, int y) {
            super();
            
this.x = x;
            
this.y = y;
            inCycle 
= false;
        }
    }

    ArrayList
<Edge>[] head = new ArrayList[N];
    
    Edge[] fa 
= new Edge[N]; 

    
int[] chk = new int[N];

    ArrayList
<Integer> Clen = new ArrayList<Integer>();
    
    BigInteger Ans 
= BigInteger.ONE;

    boolean hasSol;
    
    PrintStream 
out

    
void run() throws FileNotFoundException {
        
//Scanner cin = new Scanner(System.in);
        Scanner cin = new Scanner(new BufferedReader(new FileReader("43")));
        
out = System.out;
        
int m;
        n 
= cin.nextInt();
        
for (int i = 0; i < n; ++i) {
            head[i] 
= new ArrayList<Edge>();
        }
        m 
= cin.nextInt();
        
while (m-- != 0) {
            
int c = cin.nextInt();
            ArrayList
<Integer> ar = new ArrayList<Integer>();
            
for (int i = 0; i < c; ++i) {
                
int x = cin.nextInt();
                ar.add(x);
            }
            
for (int i = 0; i < ar.size() - 1++i) {
                
int x = ar.get(i) - 1, y = ar.get(i + 1- 1;
                head[x].add(
new Edge(x, y));
                head[y].add(
new Edge(y, x));
            }
        }

        Arrays.fill(chk, 
0);
        hasSol 
= true;
        dfs(
0new Edge(00));
        
int i;
        
for(i = 0; i < n; ++i) {
            
if(chk[i] == 0break;
        }
        
if (i < n || !hasSol) {
            
out.println("0");
            
return;
        }
        
out.println(Ans);
    }

    
private void dfs(int x, Edge e) {
        fa[x] 
= e;
        
        
int i;
        chk[x] 
= 1;
        
for(i = 0; i < head[x].size(); ++i) {
            
int y = head[x].get(i).y;
            
if(chk[y] == 0) {
                dfs(y, head[x].
get(i));
            } 
else if(chk[y] == 1 && y != e.other(x)){ // y is a ance of x
                hasSol &= !head[x].get(i).inCycle;
                head[x].
get(i).inCycle = true;
                
int c = 2;
                
for(int j = x; j != y; j = fa[j].other(j)) {
                    hasSol 
&= !fa[j].inCycle;
                    fa[j].inCycle 
= true;
                    c
++;
                }
                Ans 
= Ans.multiply(new BigInteger("" + c));
            }
        }
        chk[x] 
= 2;
    }

    
private boolean conn() {
        
int i;
        Arrays.fill(chk, 
0);
        dfs0(
0);
        
for (i = 0; i < n && chk[i] == 1++i);
        
return i == n;
    }

    
private void dfs0(int x) {
        
int i;
        chk[x] 
= 1;
        
for (i = 0; i < head[x].size(); ++i) {
            
if (chk[head[x].get(i).y] == 0) {
                dfs0(head[x].
get(i).y);
            }
        }
    }

    
public static void main(String[] args) throws FileNotFoundException {
        
new Main().run();
    }

}

PKU2117 Electricity
求一个图(可能非联通)去掉一个点之后最多的连通块数。
做法:dfs求割。
在dfs中一个点x,有子节点y1,y2...yN.
比如y1的这棵子树没有一个点能够有边连到比x更浅层的点,那么y1这棵子树在去掉x点之后会是一个独立的联通块。同样的对于y2...yN.
要注意的地方:
1.单点。去掉个单点这个单点联通块就不存在了,联通块数量会减少
2.dfs求割的时候有根和非根两种情况,两种情况分成的联通块是不同的。           

Feedback

# re: 说题  回复  更多评论   

2008-08-11 22:20 by Leon916
又来你的blog看答案了!

我发现在里面的题不好做,就是想不出来改怎么做!
请教一下你平时怎么练习的?

# re: 说题  回复  更多评论   

2008-08-12 10:09 by oyjpart
现在暑假都是做比赛,这些题目都是比赛的题目。
比赛可以在TJU(http://acm.tju.edu.cn)上自己帖,很方便的。

# re: 说题  回复  更多评论   

2008-10-16 20:18 by lxc0601
大牛,能讲解下 PKU2117 Electricity ?

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理