AcWing 95. 费解的开关 原题链接
你玩过“拉灯”游戏吗？25盏灯排成一个5x5的方形。每一个灯都有一个开关，游戏者可以改变它的状态。每一步，游戏者可以改变某一个灯的状态。游戏者改变一个灯的状态会产生连锁反应：和这个灯上下左右相邻的灯也要相应地改变其状态。
我们用数字“1”表示一盏开着的灯，用数字“0”表示关着的灯。下面这种状态
10111
01101
10111
10000
11011
在改变了最左上角的灯的状态后将变成：
01111
11101
10111
10000
11011
再改变它正中间的灯后状态将变成：
01111
11001
11001
10100
11011
给定一些游戏的初始状态，编写程序判断游戏者是否可能在6步以内使所有的灯都变亮。
输入格式
第一行输入正整数nn，代表数据中共有nn个待解决的游戏初始状态。
以下若干行数据分为nn组，每组数据有5行，每行5个字符。每组数据描述了一个游戏的初始状态。各组数据间用一个空行分隔。
输出格式
一共输出nn行数据，每行有一个小于等于6的整数，它表示对于输入数据中对应的游戏状态最少需要几步才能使所有灯变亮。
对于某一个游戏初始状态，若6步以内无法使所有灯变亮，则输出“-1”。
数据范围
0<n≤5000<n≤500
输入样例：
3
00111
01011
10001
11010
11100
11101
11101
11110
11111
11111
01111
11111
11111
11111
11111
输出样例：
3
2
-1
题目思路
static String[] ss = new String[5];
static char[][] base = new char[5][5];
static char[][] bak = new char[5][5];
static int[] dx = new int[]{-1, 0, 1, 0, 0};
static int[] dy = new int[]{0, 1, 0, -1, 0};
private static void turn(int x, int y) {
for (int i = 0; i < 5; i++) {
int a = x + dx[i];
int b = y + dy[i];
if (a < 0 || a > 4 || b < 0 || b > 4) continue;
bak[a][b] ^= 1;
}
}
public static void main(String[] args) {
int n = in.nextInt();
ss = new String[5];
base = new char[5][5];
bak = new char[5][5];
while (n-- > 0) {
for (int i = 0; i < 5; i++) ss[i] = in.next();
for (int i = 0; i < 5; i++) base[i] = ss[i].toCharArray();
int res = Integer.MAX_VALUE;
// 枚举所有第一行所有状态
for (int op = 0; op < 32; op++) {
int count = 0;
for (int i = 0; i < 5; i++)
System.arraycopy(base[i], 0, bak[i], 0, 5);
for (int i = 0; i < 5; i++) {
if ((op >> i & 1) == 1) {
turn(0, i);
count++;
}
}
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 5; j++) {
if (bak[i][j] == '0') {
//按下他的下一个开关
turn(i + 1, j);
count++;
}
}
}
// 检查最后一行是否全亮
boolean success = true;
for (int i = 0; i < 5; i++) {
if (bak[4][i] == '0') {
success = false;
}
}
if (success && res > count) res = count;
}
if (res <= 6) out.println(res);
else out.println(-1);
}
out.flush();
out.close();
}
AcWing 97. 约数之和 原题链接
假设现在有两个自然数A和B，S是ABAB的所有约数之和。
请你求出S mod 9901的值是多少。
输入格式
在一行中输入用空格隔开的两个整数A和B。
输出格式
输出一个整数，代表S mod 9901的值。
数据范围
0≤A,B≤5×1070≤A,B≤5×107
输入样例：
2 3
输出样例：
15
注意: A和B不会同时为0。
题目思路
static int mod = 9901;
private static int fastPower(int a, int b, int q) {
long res = 1L;
a %= q;
while (b > 0) {
if ((b & 1) == 1) {
res = res * a % q;
}
b >>= 1;
a = a * a % q;
}
return (int) res;
}
private static int sum(int p, int k) {
if (k == 1) return 1;
if (k % 2 == 0) return (1 + fastPower(p, k / 2, mod)) * sum(p, k / 2) % mod;
return (sum(p, k - 1) + fastPower(p, k - 1, mod)) % mod;
}
public static void main(String[] args) {
int a = in.nextInt();
int b = in.nextInt();
int res = 1;
// 对a分解质因数
for (int i = 2; i * i <= a; i++) {
if (a % i == 0) {
int s = 0;
while (a % i == 0) {
a /= i;
s++;
}
res = res * sum(i, b * s + 1) % mod;
}
}
if (a > 1) res = res * sum(a, b + 1) % mod;
if (a == 0) res = 0;
out.println(res);
out.flush();
out.close();
}
AcWing 98. 分形之城 原题链接
城市的规划在城市建设中是个大问题。
不幸的是，很多城市在开始建设的时候并没有很好的规划，城市规模扩大之后规划不合理的问题就开始显现。
而这座名为 Fractal 的城市设想了这样的一个规划方案，如下图所示：
当城区规模扩大之后，Fractal 的解决方案是把和原来城区结构一样的区域按照图中的方式建设在城市周围，提升城市的等级。
对于任意等级的城市，我们把正方形街区从左上角开始按照道路标号。
虽然这个方案很烂，Fractal 规划部门的人员还是想知道，如果城市发展到了等级 N，编号为 A 和 B 的两个街区的直线距离是多少。
街区的距离指的是街区的中心点之间的距离，每个街区都是边长为 10 米的正方形。
输入格式
第一行输入正整数nn，表示测试数据的数目。
以下nn行，输入n组测试数据，每组一行。
每组数据包括三个整数 N,A,BN,A,B, 表示城市等级以及两个街区的编号，整数之间用空格隔开。
输出格式
一共输出nn行数据，每行对应一组测试数据的输出结果，结果四舍五入到整数。
数据范围
1≤N≤311≤N≤31, 1≤A,B≤22N1≤A,B≤22N, 1≤n≤10001≤n≤1000
输入样例：
3
1 1 2
2 16 1
3 4 33
输出样例：
10
30
50
题目思路
private static class Point{
long x;
long y;
public Point(long x, long y) {
this.x = x;
this.y = y;
}
}
private static Point get(long n, long a) {
if (n == 0) return new Point(0, 0);
long block = 1L << (n * 2 - 2);
long len = 1L << (n - 1);
Point p = get(n - 1, a % block);
long x = p.x;
long y = p.y;
int number = (int) (a / block);
if (number == 0) return new Point(y, x);
else if (number == 1) return new Point(x, y + len);
else if (number == 2) return new Point(x + len, y + len);
else return new Point(len * 2 - 1 - y, len - 1 - x);
}
public static void main(String[] args) {
int m = in.nextInt();
while (m-- > 0) {
long n = in.nextLong();
long a = in.nextLong();
long b = in.nextLong();
Point pa = get(n, a - 1);
Point pb = get(n, b - 1);
double dx = pa.x - pb.x;
double dy = pa.y - pb.y;
out.printf("%.0f\n", Math.sqrt((dx * dx + dy * dy)) * 10);
}
out.flush();
out.close();
}