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求割的時候有根和非根兩種情況，兩種情況分成的聯通塊是不同的。