ACSaber

1.5万

fengwei2002

BestAc
Robin.

acw_fky

Syw丶

InkSans
__Reliauk__

codehorse
liuxiaocs

ACSaber
3个月前

## IDA* 算法

import java.util.*;
class Main {
static int x, y;
static int N = 5;
static int[][] w = new int[N][N];
static int[][] target = new int[][]{
{1,1,1,1,1},
{0,1,1,1,1},
{0,0,-1,1,1},
{0,0,0,0,1},
{0,0,0,0,0}
};
static Set<String> set = new HashSet<>();
static int[][] dirs = new int[][]{{-2,-1},{-2,1},{-1,2},{-1,-2},{1,-2},{1,2},{2,1},{2,-1}};
static int f() {
int ans = 0;
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
if (target[i][j] == -1 || w[i][j] == -1) continue;
if (target[i][j] != w[i][j]) ans++;
}
}
if (target[x][y] != -1) ans++;
return ans;
}
static String hash() {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
sb.append(w[i][j]);
}
sb.append(" ");
}
return sb.toString();
}
static boolean dfs(int u, int maxDepth) {
if (u + f() > maxDepth) return false;
if (f() == 0) return true;
for (int[] di : dirs) {
int nx = x + di[0], ny = y + di[1];
if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
swap(x, y, nx, ny);
int a = x, b = y;
x = nx;
y = ny;
if (dfs(u + 1, maxDepth)) return true;
x = a;
y = b;
swap(x, y, nx, ny);
}
return false;
}
static void swap(int a, int b, int i, int j) {
int tmp = w[a][b];
w[a][b] = w[i][j];
w[i][j] = tmp;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
sc.nextLine();
while (t-- > 0) {
set = new HashSet<>();
for (int i = 0; i < 5; i++) {
String ss = sc.nextLine();
char[] cs = ss.toCharArray();
for (int j = 0; j < 5; j++) {
w[i][j] = (cs[j] == '*') ? -1 : (int)(cs[j] - '0');
if (w[i][j] == -1) {
x = i;
y = j;
}
}
}

// System.out.println(hash());

int depth = 0;
while (depth <= 15 && !dfs(0, depth)) depth++;

// System.out.println(depth);
// System.out.println(set.size());

if (depth > 15) System.out.println(-1);
else System.out.println(depth);
}
}
}


ACSaber
3个月前

## IDA* 算法

import java.util.*;
class Main {
static int[][] ops = new int[][] {
{0, 2, 6, 11, 15, 20, 22},
{1, 3, 8, 12, 17, 21, 23},
{10, 9, 8, 7, 6, 5, 4},
{19, 18, 17, 16, 15, 14, 13},
{23, 21, 17, 12, 8, 3, 1},
{22, 20, 15, 11, 6, 2, 0},
{13, 14, 15, 16, 17, 18, 19},
{4, 5, 6, 7, 8, 9, 10}
};
static int[] opposite = new int[]{5, 4, 7, 6, 1, 0, 3, 2};
static int[] center = new int[]{6, 7, 8, 11, 12, 15, 16, 17};
static int N = 24;
static int[] w = new int[N];
static char[] path = new char[200];

static void update(int x) {
int[] locs = ops[x];
int t = w[locs[0]];
for (int i = 0; i < 6; i++) {
int cur = locs[i], next = locs[i + 1];
w[cur] = w[next];
}
w[locs[6]] = t;
}

static int f() {
int[] cnts = new int[4];
int max = 0;
for (int i = 0; i < 8; i++) {
int loc = center[i];
int x = w[loc];
cnts[x]++;
max = Math.max(max, cnts[x]);
}
return 8 - max;
}

// 已经进行了 u 步，最多进行 maxDepth 步，上一步的操作是 last
static boolean dfs(int u, int maxDepth, int last) {
if (u + f() > maxDepth) return false;
if (f() == 0) return true;

for (int i = 0; i < 8; i++) {
if (opposite[i] != last) {
update(i);
path[u] = (char)(i + 'A');
if (dfs(u + 1, maxDepth, i)) return true;
update(opposite[i]);
}
}
return false;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (true) {
String ss = sc.nextLine();
ss = ss.replace(" ", "");
if (ss.charAt(0) == '0') break;
char[] cs = ss.toCharArray();
if (cs[0] == 0) break;
for (int i = 0; i < 24; i++) w[i] = (int)(cs[i] - '0');

int depth = 0;
while (!dfs(0, depth, -1)) depth++;

if (depth == 0) System.out.print("No moves needed");
else {
for (int i = 0; i < depth; i++) {
System.out.print(path[i]);
}
}
System.out.println("");
System.out.println(w[6]);
}
}
}


ACSaber
3个月前

### IDA* 算法

import java.util.*;
class Main {
static int n;
static int N = 20;
static int[] w = new int[N];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while (t-- > 0) {
n = sc.nextInt();
for (int i = 1; i <= n; i++) w[i] = sc.nextInt();
int depth = 0;
while (depth <= 5 && !dfs(0, depth)) depth++;
if (depth >= 5) System.out.println("5 or more");
else System.out.println(depth);
}
}
// 通常爆搜函数的设计：要么是已经消耗了多少次交换次数，或者当前是第几次交换，这两种定义
// 当前消耗的修改次数为 u；最多修改次数为 maxDepth
static boolean dfs(int u, int maxDepth) {
if (u + f() > maxDepth) return false;
if (f() == 0) return true;
for (int len = 1; len <= n; len++) {
for (int l = 1; l + len - 1 <= n; l++) {
int r = l + len - 1;
for (int k = r + 1; k <= n; k++) {
int[] clone = w.clone();
int[] nw = move(w, l, r, k);
w = nw;
if (dfs(u + 1, maxDepth)) return true;
w = clone;
}
}
}
return false;
}
static int[] move(int[] arr, int l, int r, int k) {
int[] ans = new int[N];
int idx = 1;
for (int i = 1; i <= l - 1; i++) ans[idx++] = arr[i];
for (int i = r + 1; i <= k; i++) ans[idx++] = arr[i];
for (int i = l; i <= r; i++) ans[idx++] = arr[i];
for (int i = k + 1; i <= n; i++) ans[idx++] = arr[i];
return ans;
}
static int f() {
int ans = 0;
for (int i = 1; i < n; i++) {
if (w[i] != w[i + 1] - 1) ans++;
}
// 这里其实是想计算 ans / 3 的上取整
// a / b 的上取整 = (a + b - 1) / b 的下取整
return (ans + 2) / 3;
}
}


ACSaber
3个月前

### 双向 DFS

1. 先用 dfs1 对物品 [1, n / 2] 下标的物品进行爆搜，并将不超过 w 价值的数值放到 set 里面（去重）
2. 使用 set 构造出列表 list，并进行排序
3. 使用 dfs2 对物品 [n / 2 + 1, n] 下标物品进行爆搜，对于每个爆搜结果 k, 在 list 进行二分找到最大的符合 “cur + k <= w” 的值
import java.util.*;
class Main {
static int N = 50;
static int n;
static long w;
static int[] arr = new int[N];
static Set<Long> set = new HashSet<>();
static List<Long> list;
static long ans = 0;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
w = sc.nextLong();
n = sc.nextInt();
for (int i = 1; i <= n; i++) arr[i] = sc.nextInt();
dfs1(1, n / 2, 0);
list = new ArrayList<>(set);
Collections.sort(list);
// System.out.println(list);
dfs2(n / 2 + 1, n, 0);
System.out.println(ans);
}
static void dfs1(int u, int max, long cur) {
if (cur > w) return;
if (u > max) {
return;
}
dfs1(u + 1, max, cur + arr[u]);
dfs1(u + 1, max, cur);
}
static void dfs2(int u, int max, long cur) {
if (cur > w) return;
if (u > max) {
int l = 0, r = list.size() - 1;
while (l < r) {
int mid = l + r + 1 >> 1;
if (list.get(mid) + cur <= w) {
l = mid;
} else {
r = mid - 1;
}
}
if (list.get(r) + cur <= w) {
ans = Math.max(cur + list.get(r), ans);
}
return;
}
dfs2(u + 1, max, cur);
dfs2(u + 1, max, cur + arr[u]);
}
}


ACSaber
3个月前
import java.util.*;
class Main {
static int N = 810, M = 810;
static char[][] cs = new char[N][M];
static int n, m;
static int[] boy;
static int[] gril;
static Deque<int[]> x;
static boolean[][] st = new boolean[N][M];
static int[][] dir = new int[][]{{1,0}, {-1,0}, {0,1}, {0,-1}};
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while (t-- > 0) {
n = sc.nextInt();
m = sc.nextInt();
sc.nextLine();
x = new ArrayDeque<>();
for (int i = 1; i <= n; i++) {
char[] ss = sc.nextLine().toCharArray();
for (int j = 1; j <= m; j++) {
st[i][j] = false;
cs[i][j] = ss[j - 1];
if (cs[i][j] == 'M') {
boy = new int[]{i, j};
} else if (cs[i][j] == 'G') {
gril = new int[]{i, j};
} else if (cs[i][j] == 'Z') {
st[i][j] = true;
cs[i][j] = 'X';
}
}
}
int ans = bfs();
System.out.println(ans);
}
}
static Integer hash(int[] loc) {
return loc[0] * m + loc[1];
}
static int bfs() {
Deque<int[]> qa = new ArrayDeque<>(), qb = new ArrayDeque<>();
Map<Integer, Integer> da = new HashMap<>(), db = new HashMap<>();
da.put(hash(boy), 0);
db.put(hash(gril), 0);
int cnt = 0;
while (!qa.isEmpty() && !qb.isEmpty()) {
int t = 0;
// 鬼：两步
infection();
infection();

// log();

t = move(qa, qb, da, db, cnt++);
if (t != -1) return t;
}
return -1;
}
static int move(Deque<int[]> qa, Deque<int[]> qb, Map<Integer, Integer> da, Map<Integer, Integer> db, int cnt) {
for (int i = 0; i < 3; i++) {
int size = qa.size();
while (size-- > 0) {
int[] poll = qa.pollFirst();
int dx = poll[0], dy = poll[1];
if (cs[dx][dy] == 'X') continue;
for (int[] d : dir) {
int nx = dx + d[0], ny = dy + d[1];
if (nx <= 0 || nx > n || ny <= 0 || ny > m) continue;
if (cs[nx][ny] == 'X') continue;
int[] cur = new int[]{nx, ny};
int key = hash(cur);
if (da.containsKey(key)) continue;
if (db.containsKey(key)) {
// return cnt + 1 + db.get(key);
return cnt + 1;
} else {
da.put(key, cnt + 1);
}
}
}
}

for (int i = 0; i < 1; i++) {
int size = qb.size();
while (size-- > 0) {
int[] poll = qb.pollFirst();
int dx = poll[0], dy = poll[1];
if (cs[dx][dy] == 'X') continue;
for (int[] d : dir) {
int nx = dx + d[0], ny = dy + d[1];
if (nx <= 0 || nx > n || ny <= 0 || ny > m) continue;
if (cs[nx][ny] == 'X') continue;
int[] cur = new int[]{nx, ny};
int key = hash(cur);
if (db.containsKey(key)) continue;
if (da.containsKey(key)) {
// return cnt + 1 + da.get(key);
return cnt + 1;
} else {
db.put(key, cnt + 1);
}
}
}
}

return -1;
}
static void log() {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
System.out.print(cs[i][j]);
}
System.out.println("");
}
System.out.println("");
}
static void infection() {
int size = x.size();
while (size-- > 0) {
int[] poll = x.pollFirst();
int dx = poll[0], dy = poll[1];
for (int[] d : dir) {
int nx = dx + d[0], ny = dy + d[1];
if (nx <= 0 || nx > n || ny <= 0 || ny > m) continue;
if (!st[nx][ny]) {
cs[nx][ny] = 'X';
st[nx][ny] = true;
}
}
}
}
}


ACSaber
3个月前
import java.util.*;
class Main {
static int[] a = new int[10];
static int[] t = new int[10];
static Map<String, Integer> dist = new HashMap<>();
static Map<String, int[]> g = new HashMap<>();
static Map<String, Character> op = new HashMap<>();
static Deque<int[]> q = new ArrayDeque<>();

static int[][] tmp = new int[2][4];
static void set(int[] cur) {
for (int i = 0; i < 4; i++) tmp[0][i] = cur[i + 1];
for (int i = 0; i < 4; i++) tmp[1][i] = cur[8 - i];
}
static int[] get() {
int[] ans = new int[10];
for (int i = 0; i < 4; i++) ans[i + 1] = tmp[0][i];
for (int i = 0; i < 4; i++) ans[5 + i] = tmp[1][3 - i];
return ans;
}
static int[] move0(int[] cur) {
set(cur);
for (int i = 0; i < 4; i++) {
int c = tmp[0][i];
tmp[0][i] = tmp[1][i];
tmp[1][i] = c;
}
return get();
}
static int[] move1(int[] cur) {
set(cur);
int x = tmp[0][3], y = tmp[1][3];
for (int i = 3; i >= 1; i--) {
tmp[0][i] = tmp[0][i - 1];
tmp[1][i] = tmp[1][i - 1];
}
tmp[0][0] = x;
tmp[1][0] = y;
return get();
}
static int[] move2(int[] cur) {
set(cur);
int c = tmp[1][1];
tmp[1][1] = tmp[1][2];
tmp[1][2] = tmp[0][2];
tmp[0][2] = tmp[0][1];
tmp[0][1] = c;
return get();
}

static String getHash(int[] cur) {
StringBuilder sb = new StringBuilder();
for (int i : cur) {
sb.append(String.valueOf(i) + "_");
}
return sb.toString();
}

static void bfs() {
dist.put(getHash(a), 0);
while (!q.isEmpty()) {
int[] poll = q.pollFirst();

// System.out.println(Arrays.toString(poll));
// System.out.println(q.size());

int di = dist.get(getHash(poll));
if (check(poll, t)) {
return;
}
List<int[]> list = new ArrayList<>();
for (int i = 0; i < 3; i++) {
int[] cc = list.get(i);
String key = getHash(cc);
if (!dist.containsKey(key)) {
// System.out.println(key);
dist.put(key, di + 1);
op.put(key, (char)('A' + i));
g.put(key, poll);
if (check(cc, t)) return;
}
}
}
}
static boolean check(int[] a, int[] b) {
for (int i = 1 ; i <= 8; i++) {
if (a[i] != b[i]) return false;
}
return true;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
for (int i = 1; i <= 8; i++) {
t[i] = sc.nextInt();
a[i] = i;
}
bfs();
System.out.println(dist.get(getHash(t)));
StringBuilder sb = new StringBuilder();
if (dist.get(getHash(t)) != 0) {
while (!check(t, a)) {
sb.append(op.get(getHash(t)));
t = g.get(getHash(t));
}
sb.reverse();
System.out.println(sb.toString());
}
}
}


ACSaber
3个月前
import java.util.*;
class Main {
static int[] a = new int[1009];
static int[] s = new int[1009];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), k = sc.nextInt(), p = sc.nextInt(), x = sc.nextInt(), y = sc.nextInt();
List<Integer> list = new ArrayList<>();
for (int i = 1; i <= k; i++) {
a[i] = sc.nextInt();
s[i] = s[i - 1] + a[i];
}

for (int i = k + 1; i <= n; i++) {
a[i] = 1;
s[i] = s[i - 1] + a[i];
}

int sum = s[n];
if (sum > x) {
System.out.print("-1");
return;
}
int m = list.size();
Collections.sort(list);
// System.out.print(list.get(m / 2));
int idx = k + 1;
while (list.get(m / 2) < y) {
// System.out.println(list.get(m / 2));
// System.out.println(a[idx]);
int curr = list.get(m / 2);
int min = a[idx];
int diff = y - min;
// System.out.println(diff);
if (sum + diff <= x) {
sum += diff;
list.set(0, a[idx] + diff);
a[idx] += diff;
idx++;
} else {
System.out.print("-1");
return;
}
Collections.sort(list);
}

for (int i = k + 1; i <= n; i++) {
System.out.print(a[i] + " ");
}

}
}


ACSaber
3个月前
import java.util.*;
class Main {
static class Node{
int l, r; //代表左右儿子的下标
int cnt;  //存储当前值域中数字的个数
}

static int N = 100009;
static Node[] tr = new Node[N * 30];
static int[] version = new int[N];
static int idx = 0;
static int[] a = new int[N];
static List<Integer> list; // 离散化数组

// 找「起始值」对应的「离散化值」，即「起始值」的排序数组的对应下标
static int find(int x) {
return Collections.binarySearch(list, x);
}

static int build(int l, int r) {
// 先将当前节点构造出来
int q = ++idx;
tr[q] = new Node();

// 如果是叶子节点，直接返回
if (l == r) return q;

// 如果不叶子节点，将左右儿子建立出来
int mid = l + r >> 1;
tr[q].l = build(l, mid);
tr[q].r = build(mid + 1, r);
return q;
}

// 上个版本 / 在 [l, r] 范围中的 x 位置 +1
// [l, r] 起始都是传完整的区间
static int insert(int p, int l, int r, int x) {
// 新建节点
int q = ++idx;
tr[q] = new Node();
// 将上个版本的信息复制过来
tr[q].l = tr[p].l;
tr[q].r = tr[p].r;
tr[q].cnt = tr[p].cnt;
if (l == r) {
tr[q].cnt++;
return q;
} else {
int mid = l + r >> 1;
if (x <= mid) tr[q].l = insert(tr[p].l, l, mid, x);
else tr[q].r = insert(tr[p].r, mid + 1, r, x);
pushup(q, tr[q].l, tr[q].r);
return q;
}
}

static void pushup(int u, int l, int r) {
tr[u].cnt = tr[l].cnt + tr[r].cnt;
}

// 上一版本/当前版本/ [l, r] 里面找第 k 小的数
// [l, r] 起始都是传完整的区间
static int query(int p, int q, int l, int r, int k) {
if (l == r) return l;
int cnt = tr[tr[q].l].cnt - tr[tr[p].l].cnt;
int mid = l + r >> 1;
if (k <= cnt) return query(tr[p].l, tr[q].l, l, mid, k);
else return query(tr[p].r, tr[q].r, mid + 1, r, k - cnt);
}

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), m = sc.nextInt();
Set<Integer> set = new HashSet<>();
for (int i = 1; i <= n; i++) {
a[i] = sc.nextInt();
}

// 离散化
list = new ArrayList<>(set);
Collections.sort(list);

int size = list.size();

// 建立空的线段树
version[0] = build(0, size - 1);

for (int i = 1; i <= n; i++) {
version[i] = insert(version[i - 1], 0, size - 1, find(a[i]));
}

while (m-- > 0) {
int l = sc.nextInt(), r = sc.nextInt(), k = sc.nextInt();
int ans = query(version[l - 1], version[r], 0, size - 1, k);
System.out.println(list.get(ans));
}
}
}


ACSaber
3个月前
import java.util.*;
class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while (t-- > 0) {
int n = sc.nextInt(), x = sc.nextInt();
if (n == 1 || n == 2) System.out.println(1);
else {
int ans = 1;
int cur = 2;
while (n > cur) {
cur += x;
ans++;
}
System.out.println(ans);
}
}
}
}


ACSaber
3个月前
import java.util.*;
class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; i++) a[i] = sc.nextInt();
Arrays.sort(a);
double ans = 0;
for (int i = n - 1, j = 0; i >= 0; i--, j++) {
int r = a[i];
double cur = r * r * 3.1415926535897932384626433832795028841971;
if (j % 2 == 1) {
ans -= cur;
} else {
ans += cur;
}
}
System.out.println(new Formatter().format("%.6f", ans).toString());
}
}