PKU3034 Whac-a-Mole
很有意思的題目，打地鼠。
簡(jiǎn)單的記憶化搜索。trick在于你有可能移出地鼠區(qū)，形成一個(gè)更優(yōu)的解。
PKU2280 Amphiphilic Carbon Molecules首先可以證明要求的線一定由兩點(diǎn)確定。
基本算法：枚舉點(diǎn)+極角序+一圈掃描。
難點(diǎn)1：計(jì)較排序
難點(diǎn)2：一圈掃描時(shí)候的計(jì)數(shù)。
巧妙的轉(zhuǎn)化：枚舉一個(gè)點(diǎn)x之后將所有的黑點(diǎn)移到關(guān)于x的對(duì)稱點(diǎn)上，這樣題目就轉(zhuǎn)化成了：
求一條線，這條線上和這條線的一側(cè)的點(diǎn)的和最大。簡(jiǎn)單多了。
這是去年省賽A題，當(dāng)時(shí)就是用這種方法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經(jīng)典題。
首先將輸入的單詞看成一條邊。它連接的左右各2字符形成的點(diǎn)。
那么新的圖點(diǎn)為26*26個(gè)。
然后二分枚舉答案ans，將原來的圖的權(quán)w轉(zhuǎn)化為ans-w,
用Bellman Ford判負(fù)權(quán)回路。如果有負(fù)權(quán)回路，說明
sigma(ans) + sigma(w) < 0
即 ans * cycle_length < sigma(w)
sigma(w)是原本的單詞長(zhǎng)度和，而ans * cycle_length則是枚舉答案之后那個(gè)環(huán)的單詞長(zhǎng)度和
所以 ans 可以繼續(xù)增大。 這樣就構(gòu)成了二分。
// 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這個(gè)題目的要求：
1.求一個(gè)圖所有的環(huán)的長(zhǎng)度
2.判斷一個(gè)圖中任意兩個(gè)環(huán)是否共邊
3.判斷一個(gè)圖是否連通
一個(gè)圖的環(huán)的求法(DFS)：
若現(xiàn)在在dfs 節(jié)點(diǎn)x，其子節(jié)點(diǎn)y是一個(gè)灰色節(jié)點(diǎn)（已經(jīng)遍歷到，但子樹沒有遍歷完的節(jié)點(diǎn)），那么就存在一個(gè)x->y->...->x的環(huán)。從x向上找一直到y(tǒng)就是環(huán)了。
// solution by alpc12
// 注意這個(gè)代碼在pku上會(huì)runtime error，棧溢出。
// 因?yàn)閖ava的棧空間很小。
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
求一個(gè)圖（可能非聯(lián)通）去掉一個(gè)點(diǎn)之后最多的連通塊數(shù)。
做法：dfs求割。
在dfs中一個(gè)點(diǎn)x，有子節(jié)點(diǎn)y1，y2...yN.
比如y1的這棵子樹沒有一個(gè)點(diǎn)能夠有邊連到比x更淺層的點(diǎn)，那么y1這棵子樹在去掉x點(diǎn)之后會(huì)是一個(gè)獨(dú)立的聯(lián)通塊。同樣的對(duì)于y2...yN.
要注意的地方：
1.單點(diǎn)。去掉個(gè)單點(diǎn)這個(gè)單點(diǎn)聯(lián)通塊就不存在了，聯(lián)通塊數(shù)量會(huì)減少
2.dfs求割的時(shí)候有根和非根兩種情況，兩種情況分成的聯(lián)通塊是不同的。