|
|
2009年8月26日
http://acm.pku.edu.cn/JudgeOnline/problem?id=3747
题目中爆炸的扩大速度与人的逃走速度是一致, 这就决定了逃走的最佳路线一定是一条直线, 而且这样使得长度与时间的比较等价, 这个是这道题目的关键.
若假设YYF的逃出点为C, YYF的起点为A, 爆炸发生点为B, 那么一定有AC > AB.
所以对于一个爆炸点来说AB中垂线划分出的A所在一边为安全区域. 接下来的就是经典的圆周覆盖问题了.
复杂度: O(N)
/**
* @version 2009/08/31
* @author sbzlyessit
*/
import java.io.*;
import java.util.*;
public class Main {
private static BufferedReader in =
new BufferedReader(new InputStreamReader(System.in));
private static StringTokenizer st;
private static double[] x = new double[10], y = new double[10];
private static double[] d = new double[20];
private static double x0, y0;
private static int N;
private static double R;
public static void main(String[] argv) throws Exception {
while (in.ready()) {
N = nextInt();
R = nextDouble();
x0 = nextDouble();
y0 = nextDouble();
for (int i = 0; i < N; i++) {
x[i] = nextDouble();
y[i] = nextDouble();
}
solve();
}
}
private static void solve() {
double a, b, c, delta, t1, t2, a0, a1, b0, b1, x1, y1;
for (int i = 0; i < N; i++) {
if (doubleCmp(x[i], x0) == 0 && doubleCmp(y[i], y0) == 0) {
System.out.println("No");
return;
}
a0 = x[i] - x0;
b0 = y[i] - y0;
x1 = x0 + a0 / 2;
y1 = y0 + b0 / 2;
a1 = -b0;
b1 = a0;
a = sqr(a1) + sqr(b1);
b = 2 * a1 * x1 + 2 * b1 * y1;
c = sqr(x1) + sqr(y1) - sqr(R);
delta = Math.sqrt(sqr(b) - 4 * a * c);
t1 = (-b + delta) / 2 / a;
t2 = (-b - delta) / 2 / a;
d[2 * i] = Math.atan2(y1 + t1 * b1, x1 + t1 * a1);
d[2 * i + 1] = Math.atan2(y1 + t2 * b1, x1 + t2 * a1);
}
Arrays.sort(d, 0, 2 * N);
for (int i = 0; i < 2 * N; i++)
if (check(d[i], d[(i + 1) % (2 * N)])) {
System.out.println("Yes");
return;
}
System.out.println("No");
}
private static boolean check(double xt, double yt) {
if (yt < xt) yt += 2 * Math.PI;
xt = (xt + yt) / 2;
yt = R * Math.sin(xt);
xt = R * Math.cos(xt);
for (int i = 0; i < N; i++)
if (doubleCmp(dist(x[i], y[i], xt, yt), dist(x0, y0, xt, yt)) < 0) return false;
return true;
}
private static double dist(double x1, double y1, double x2, double y2) {
return Math.sqrt(sqr(x1 - x2) + sqr(y1 - y2));
}
private static int doubleCmp(double a, double b) {
if (Math.abs(a - b) < 1e-6) return 0;
return a < b ? -1 : 1;
}
private static double sqr(double x) {
return x * x;
}
private static int nextInt() throws Exception {
return Integer.parseInt(next());
}
private static double nextDouble() throws Exception {
return Double.parseDouble(next());
}
private static String next() throws Exception {
while (st == null || !st.hasMoreTokens())
st = new StringTokenizer(in.readLine());
return st.nextToken();
}
}
http://acm.pku.edu.cn/JudgeOnline/problem?id=3742
高精度加法和乘法.
复杂度: O(aN 2)(a为高精度的代价)
/**
* @version 2009/08/28
* @author sbzlyessit
*/
import java.io.*;
import java.util.*;
import java.math.*;
public class Main {
private static final int MAX_N = 200;
private static BufferedReader in =
new BufferedReader(new InputStreamReader(System.in));
private static StringTokenizer st;
private static BigInteger[][] C = new BigInteger[MAX_N + 1][];
private static BigInteger[] a = new BigInteger[MAX_N + 1];
private static BigInteger[] pow = new BigInteger[MAX_N + 1];
public static void main(String[] argv) throws Exception {
int N, t, signalt, signal;
int i, j;
BigInteger T, x;
initialize();
while (in.ready()) {
N = nextInt();
t = nextInt();
if (t < 0) {
t = -t;
signalt = 1;
} else signalt = -1;
T = BigInteger.valueOf(t);
pow[0] = BigInteger.ONE;
for (i = 1; i <= N; i++) pow[i] = pow[i - 1].multiply(T);
for (i = 0; i <= N; i++)
a[i] = BigInteger.valueOf(nextInt());
for (i = N; i >= 0; i--) {
for (signal = signalt, j = i - 1; j >= 0; j--, signal *= signalt) {
x = a[i].multiply(C[i][j]).multiply(pow[i - j]);
if (signal < 0) a[j] = a[j].subtract(x.negate());
else a[j] = a[j].subtract(x);
}
}
for (i = 0; i <= N; i++) {
if (i != 0) System.out.print(" ");
System.out.print(a[i]);
}
System.out.println();
}
}
private static void initialize() {
int i, j;
C[0] = new BigInteger[1];
C[0][0] = BigInteger.ONE;
for (i = 1; i <= MAX_N; i++) {
C[i] = new BigInteger[i + 1];
C[i][0] = C[i][i] = BigInteger.ONE;
for (j = 1; j < i; j++)
C[i][j] = C[i - 1][j - 1].add(C[i - 1][j]);
}
}
private static int nextInt() throws Exception {
return Integer.parseInt(next());
}
private static String next() throws Exception {
while (st == null || !st.hasMoreTokens())
st = new StringTokenizer(in.readLine());
return st.nextToken();
}
}
http://acm.pku.edu.cn/JudgeOnline/problem?id=3744
从题意可以得出递推式: P N = p * P N - 1 + (1 - p) * P N - 2;
可导出通项公式: P N = P start / (p - 2) * ((p - 1) N + 1 - 1)
之后就可以直接套用公式了.
/**
* @version 2009/08/28
* @author sbzlyessit
*/
import java.io.*;
import java.util.*;
public class Main {
private static BufferedReader in =
new BufferedReader(new InputStreamReader(System.in));
private static StringTokenizer st;
public static void main(String[] argv) throws Exception {
int[] list = new int[10];
int i, temp, last;
int N;
double p, val;
boolean found;
while (true) {
N = nextInt();
p = nextDouble();
for (i = 0; i < N; i++) list[i] = nextInt();
Arrays.sort(list, 0, N);
for (temp = N, N = i = 1; i < temp; i++)
if (list[i] != list[i - 1]) list[N++] = list[i];
for (found = false, i = 0; !found && i < N; i++)
if (list[i] == 1 || i > 0 && list[i] == list[i - 1] + 1)
found = true;
if (found) {
System.out.println("0.0000000");
continue;
}
last = 1;
val = 1.0;
for (i = 0; i < N; i++) {
val = val * (Math.pow(p - 1, list[i] - last) - 1.0) / (p - 2.0) * (1 - p);
last = list[i] + 1;
}
System.out.format("%.7f%n", val);
}
}
private static int nextInt() throws Exception {
return Integer.parseInt(next());
}
private static double nextDouble() throws Exception {
return Double.parseDouble(next());
}
private static String next() throws Exception {
while (st == null || !st.hasMoreTokens())
st = new StringTokenizer(in.readLine());
return st.nextToken();
}
}
http://acm.pku.edu.cn/JudgeOnline/problem?id=3740
按照题目条件暴力枚举.
复杂度: O(2 NM)
/**
* @version 2009/08/28
* @author sbzlyessit
*/
import java.io.*;
import java.util.*;
public class Main {
private static BufferedReader in =
new BufferedReader(new InputStreamReader(System.in));
private static StringTokenizer st;
private static int[] matrix = new int[300];
public static void main(String[] argv) throws Exception {
int N, M;
int i, j, x;
boolean found;
while (in.ready()) {
N = nextInt();
M = nextInt();
Arrays.fill(matrix, 0);
for (i = 0; i < N; i++)
for (j = 0; j < M; j++)
if (nextInt() == 1)
matrix[j] |= 1 << i;
for (found = false, i = (1 << N) - 1; !found && i >= 0; i--) {
for (j = 0; j < M; j++) {
x = i & matrix[j];
if (x == 0 || x - (x & (-x)) != 0) break;
}
if (j == M) {
found = true;
System.out.println("Yes, I found it");
}
}
if (!found) System.out.println("It is impossible");
}
}
private static int nextInt() throws Exception {
while (st == null || !st.hasMoreTokens())
st = new StringTokenizer(in.readLine());
return Integer.parseInt(st.nextToken());
}
}
http://acm.pku.edu.cn/JudgeOnline/problem?id=3633
搜索题. 状态不多, 可用记忆化搜索, 但是转移耗费巨大, 所以仍需剪枝. 最主要的一项剪枝就是每一位匹配时都要取最长的长度进行下一步搜索.
/**
* @version 2009/08/26
* @author sbzlyessit
*/
import java.io.*;
import java.util.*;
public class Main {
private static final int MAX_N = 18;
private static BufferedReader in =
new BufferedReader(new InputStreamReader(System.in));
private static char[] s, t, sr;
private static int[] matchs, matchsr;
private static int[] hash = new int[1 << MAX_N];
public static void main(String[] argv) throws Exception {
for(int caseSize = Integer.parseInt(in.readLine()); caseSize > 0; caseSize--){
if (!readIn()) {
System.out.println("impossible");
} else {
System.out.println(solve(0));
}
}
}
private static boolean readIn() throws Exception {
String S = in.readLine(), T = in.readLine();
int i;
if ((!S.contains("A") && T.contains("A")) || (!S.contains("C") && T.contains("C")) ||
(!S.contains("G") && T.contains("G")) || (!S.contains("T") && T.contains("T"))) {
return false;
}
s = S.toCharArray();
t = T.toCharArray();
sr = new char[s.length];
matchs = new int[t.length];
matchsr = new int[t.length];
Arrays.fill(hash, Integer.MAX_VALUE);
hash[(1 << t.length) - 1] = 0;
reverse(s, sr);
for (i = 0; i < t.length; i++) {
matchs[i] = longestMatch(i, t.length, s);
matchsr[i] = longestMatch(i, t.length, sr);
}
return true;
}
private static void reverse(char[] a, char[] ar) {
for (int i = 0; i < a.length; i++) {
ar[i] = a[a.length - i - 1];
}
}
private static int longestMatch(int from, int to, char[] a) {
int i, len, max = 0;
for (i = 0, len = 0; i < a.length; i++, len = 0) {
while (len < to - from && i + len < a.length && a[i + len] == t[from + len]) {
len++;
}
max = Math.max(max, len);
}
return max;
}
private static int solve(int state) {
if (hash[state] != Integer.MAX_VALUE) {
return hash[state];
}
char[] done = new char[t.length];
char[] doner = new char[t.length];
int i, m = 0, len, g;
for (i = 0; i < done.length; i++) {
done[i] = (state & (1 << i)) != 0 ? t[i] : '0';
}
reverse(done, doner);
for(i = 0; i < t.length; i++) {
if ((state & (1 << i)) != 0) {
m = 0;
continue;
}
len = 1;
while (i + len < t.length && (state & (1 << (i + len))) == 0) {
len++;
}
g = Math.min(len, Math.max(matchs[i], matchsr[i]));
g = Math.max(g, longestMatch(i, i + len, done));
g = Math.max(g, longestMatch(i, i + len, doner));
if(g > m - 1) {
hash[state] = Math.min(hash[state], 1 + solve(state | ((1 << (i + g)) - (1 << i))));
}
m = g;
}
return hash[state];
}
}
|