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 < 0) return true;
else if (y < 0 && a.y >= 0) return false;
if (y == 0 && a.y == 0){
if (x >= 0 && a.x < 0) return true;
if (x < 0 && a.x >= 0) return false;
return abs(x) < abs(a.x);
}
int t = x * a.y - y * a.x;
return t == 0 ? x*x + y*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, &y = 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, 0, sizeof(chk));
m = nv = 0;
for(i = 0; i < n; ++i) {
gets(line);
int len;
if((len=strlen(line)) <= 2) while(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(0, new Edge(0, 0));
int i;
for(i = 0; i < n; ++i) {
if(chk[i] == 0) break;
}
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求割的时候有根和非根两种情况，两种情况分成的联通块是不同的。