|
|
2009年8月31日
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();
}
}
2009年8月28日
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());
}
}
2009年8月26日
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];
}
}
2009年8月24日
http://acm.pku.edu.cn/JudgeOnline/problem?id=3643
这题的正解应该是枚举a, b然后用半平面交求解.
但是看了别人的代码长度, 我就立刻放弃的这种做法.
事实上, 这题可以用迭代的方法不断逼近解.
假设s = a * xi + b * yi + c * zi + d;
要使s从小于0变成大于等于0, 只需要使a = a + x[i], b = b + y[i], c = c + z[i], d = d + 1, 使不等式满足要求为止.
虽然可以不断逼近解, 但是不能估算出究竟需要多少步才能得到解, 所以这个只是一种近似解法.
/**
* @version 2009/08/24
* @author sbzlyessit
*/
import java.io.*;
import java.util.*;
public class Main {
private static final int MAX_N = 400;
private static BufferedReader in =
new BufferedReader(new InputStreamReader(System.in));
private static StringTokenizer st;
private static int[] x = new int[MAX_N], y = new int[MAX_N], z = new int[MAX_N];
private static int N, M, size;
public static void main(String[] argv) throws Exception {
while ((N = nextInt()) >= 0) {
readIn();
solve();
}
}
private static void readIn() throws Exception {
int i;
for (i = 0; i < N; i++) {
x[i] = nextInt();
y[i] = nextInt();
z[i] = nextInt();
}
M = nextInt();
size = N + M;
for (i = N; i < size; i++) {
x[i] = nextInt();
y[i] = nextInt();
z[i] = nextInt();
}
}
private static void solve() {
double a = 0.0, b = 0.0, c = 0.0, d = 0.0;
int i, j;
boolean refresh = true;
for (i = 2 * M * N; refresh && i > 0; i--) {
refresh = false;
for (j = 0; j < N; j++) {
if (a * x[j] + b * y[j] + c * z[j] + d > 0) {
a -= x[j];
b -= y[j];
c -= z[j];
d--;
refresh = true;
}
}
for (j = N; j < size; j++) {
if (a * x[j] + b * y[j] + c * z[j] + d <= 0) {
a += x[j];
b += y[j];
c += z[j];
d++;
refresh = true;
}
}
}
System.out.println(a + " " + b + " " + c + " " + d);
}
private static int nextInt() throws Exception {
while (st == null || !st.hasMoreTokens()) {
st = new StringTokenizer(in.readLine());
}
return Integer.parseInt(st.nextToken());
}
}
2009年8月23日
http://acm.pku.edu.cn/JudgeOnline/problem?id=3657
题目问题可以转化为判断questions是否矛盾, 然后二分找到最先发生矛盾的question.
那如何判断矛盾? 若我们把questions依照Ai值从大到小的顺序进行区间覆盖, 若一个区间加入时, 此区间已被完全覆盖, 则说明此区间的取值均比Ai大, 故questions矛盾, 否则一定可以构造出一个取值分布.
区间覆盖最好的方法应该是线段树, 然而此题只需要判断某段区间是否被覆盖, 所以可以用并查集维护.
复杂度O(aQlogQ)(a为并查集系数)
/**
* @version 2009/08/22
* @author sbzlyessit
*/
import java.io.*;
import java.util.*;
public class Main {
private static final int MAX_N = 25000;
private static BufferedReader in =
new BufferedReader(new InputStreamReader(System.in));
private static StringTokenizer st;
private static int[][] que = new int[MAX_N][3];
private static int[] x = new int[2 * MAX_N];
private static Integer[] list = new Integer[MAX_N];
private static int[] r = new int[2 * MAX_N];
private static boolean[] used = new boolean[2 * MAX_N];
private static int N, xSize;
public static void main(String[] argv) throws Exception {
readIn();
solve();
}
private static void readIn() throws Exception {
int i, temp;
nextInt();
N = nextInt();
for (xSize = 0, i = 0; i < N; i++) {
que[i][0] = x[xSize++] = nextInt();
que[i][1] = x[xSize++] = nextInt() + 1;
que[i][2] = nextInt();
list[i] = i;
}
Arrays.sort(x, 0, xSize);
for (temp = xSize, xSize = i = 1; i < temp; i++) {
if (x[i] != x[i - 1]) {
x[xSize++] = x[i];
}
}
for (i = 0; i < N; i++) {
que[i][0] = Arrays.binarySearch(x, 0, xSize, que[i][0]);
que[i][1] = Arrays.binarySearch(x, 0, xSize, que[i][1]);
}
Arrays.sort(list, 0, N, new Comparator<Integer>(){
public int compare(Integer a, Integer b) {
return que[a][2] < que[b][2] ? 1 : -1;
}
});
}
private static void solve() {
int min = 0, max = N - 1, mid;
while (min < max) {
mid = (min + max + 1) / 2;
if (check(mid)) {
min = mid;
} else {
max = mid - 1;
}
}
if (min == N - 1) {
System.out.println(0);
} else {
System.out.println(min + 2);
}
}
private static boolean check(int pos) {
int i, j, x, min, max;
boolean found;
for (i = 0; i < xSize - 1; i++) {
r[i] = -1;
used[i] = false;
}
for (i = 0; i < N; i++) {
x = list[i];
if (i == 0 || que[x][2] != que[list[i - 1]][2]) {
min = Integer.MIN_VALUE;
max = Integer.MAX_VALUE;
for (j = i; j < N && que[list[j]][2] == que[x][2]; j++) {
if (list[j] <= pos) {
min = Math.max(min, que[list[j]][0]);
max = Math.min(max, que[list[j]][1]);
}
}
if (min != Integer.MIN_VALUE) {
for (found = false, j = min; j < max; j++) {
if (!used[j]) {
used[j] = found = true;
insert(j);
}
j = find(j);
}
if (!found) {
return false;
}
}
}
if (x <= pos) {
for (j = que[x][0]; j < que[x][1]; j++) {
if (!used[j]) {
used[j] = true;
insert(j);
}
j = find(j);
}
}
}
return true;
}
private static void insert(int pos) {
if (pos > 0 && used[pos - 1]) {
r[pos - 1] = pos;
}
if (pos < xSize - 2 && used[pos + 1]) {
r[pos] = find(pos + 1);
}
}
private static int find(int x) {
int y = x, z;
while (r[y] != -1) {
y = r[y];
}
while (x != y) {
z = x;
x = r[x];
r[z] = y;
}
return y;
}
private static int nextInt() throws Exception {
while (st == null || !st.hasMoreTokens()) {
st = new StringTokenizer(in.readLine());
}
return Integer.parseInt(st.nextToken());
}
}
2009年8月22日
http://acm.pku.edu.cn/JudgeOnline/problem?id=3688
把牌从小到大排序, 然后DP.
复杂度O(NlogN + NM).
/**
* @version 2009/08/22
* @author sbzlyessit
*/
import java.io.*;
import java.util.*;
public class Main {
private static final int MAX_N = 10000, MAX_M = 100000;
private static BufferedReader in =
new BufferedReader(new InputStreamReader(System.in));
private static StringTokenizer st;
private static int[] list = new int[MAX_N];
private static int[] state = new int[MAX_M + 1];
private static int N, M;
public static void main(String[] argv) throws Exception {
int i, j, limit, len, result;
while (((N = nextInt()) | (M = nextInt())) != 0) {
for (i = 0; i < N; i++) {
list[i] = nextInt();
}
Arrays.sort(list, 0, N);
Arrays.fill(state, 0, M + 1, 0);
limit = 0;
state[0] = 2;
for (i = 0; i < N; i++) {
len = Math.min(limit, M - list[i]);
for (j = len; j >= 0; j--) {
if (state[j] > 0) {
if (state[j] == 3) {
state[j + list[i]] = 3;
} else {
state[j + list[i]] |= 3 - state[j];
}
}
}
limit = Math.min(limit + list[i], M);
}
for (result = 0, i = 1; i <= M; i++) {
if (state[i] == 1) {
result++;
}
}
System.out.println(result);
}
}
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=3658
以H为关键字建立笛卡尔树, 沿笛卡尔树dfs一次即可算出每个层面的覆盖时间.
复杂度O(N).
/**
* @version 2009/08/21
* @author sbzlyessit
*/
import java.io.*;
import java.util.*;
public class Main {
private static final int MAX_N = 100000;
private static BufferedReader in =
new BufferedReader(new InputStreamReader(System.in));
private static StringTokenizer st;
private static int[] height = new int[MAX_N];
private static long[] width = new long[MAX_N + 1];
private static long[] area = new long[MAX_N + 1];
private static int[] l = new int[MAX_N], r = new int[MAX_N];
private static int[] stack = new int[MAX_N + 1];
private static int[] min = new int[MAX_N], max = new int[MAX_N];
private static long[] base = new long[MAX_N];
private static boolean[] used = new boolean[MAX_N];
private static long[] result = new long[MAX_N];
private static int N, pos, root;
public static void main(String[] argv) throws Exception {
readIn();
solve();
}
private static void readIn() throws Exception {
int top = 0, minH = Integer.MAX_VALUE;
int i, x;
N = nextInt();
width[0] = area[0] = 0;
for (i = 0; i < N; i++) {
x = nextInt();
height[i] = nextInt();
width[i + 1] = width[i] + x;
area[i + 1] = area[i] + (long) x * height[i];
if (height[i] < minH) {
minH = height[i];
pos = i;
}
for (stack[top] = -1; top > 0 && height[stack[top - 1]] < height[i]; top--);
if (top > 0) {
r[stack[top - 1]] = i;
}
l[i] = stack[top] != -1 ? stack[top] : -1;
r[i] = -1;
stack[top++] = i;
}
root = stack[0];
}
private static void solve() {
int top = 0;
int i, x, y;
stack[top++] = root;
min[root] = 0; max[root] = N;
base[root] = 0;
while (top > 0) {
x = stack[top - 1];
if (!used[x]) {
result[x] = base[x] + (width[max[x]] - width[min[x]]) * (height[x] + 1) - area[max[x]] + area[min[x]];
used[stack[top - 1]] = true;
}
if ((y = getChild(x)) == 0) {
top--;
} else if (y < 0) {
stack[top++] = l[x];
min[l[x]] = min[x]; max[l[x]] = x;
base[l[x]] = base[x] + (pos > x ? (width[max[x]] - width[x + 1]) * height[x] -
area[max[x]] + area[x + 1] : 0);
} else {
stack[top++] = r[x];
min[r[x]] = x + 1; max[r[x]] = max[x];
base[r[x]] = base[x] + (pos < x ? (width[x] - width[min[x]]) * height[x] -
area[x] + area[min[x]] : 0);
}
}
for (i = 0; i < N; i++) {
System.out.println(result[i]);
}
}
private static int getChild(int x) {
if (l[x] != -1 && !used[l[x]]) {
return -1;
} else if (r[x] != -1 && !used[r[x]]) {
return 1;
}
return 0;
}
private static int nextInt() throws Exception {
while (st == null || !st.hasMoreTokens()) {
st = new StringTokenizer(in.readLine());
}
return Integer.parseInt(st.nextToken());
}
}
|