P3915 树的分解 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
- 这道题感觉更考到了递归的本质。我们说递归，我目前的理解是，把无数个相似的问题拆分成一个个个体，然后去依次分类解决，然后返回给上层，这么一个感觉。
- 这道题难点虽然是普及难度，但是实话实说，我在树的方面基础还是比较薄弱的，想了比较久。
- 如果你宏观的去看这个题，应该是觉得难以入手，毕竟它没有去局限于是二叉树还是什么什么树，这是很任意的一个树
- 能不能把这个问题简化呢？根据上面提到的递归思想，把问题简化成一个个模块，可以想到的是，如果考虑其就是一棵深度为2的树，以一个微观的角度来看，可以发现只有如下两个可能性（极其简易的一种想法）：
- 当然，向外推广多叉树也是可能出现的。
- 但是能够判断的是（在k = 2的情况下），有且只有图一中左边的情况是成立的，也就是我们说的有k个节点的一棵子树，我们说他是一棵可以分离的树。其他情况是不可能实现的即，不可拆分。
- 进一步发现其实我们只需要维护根节点有多少个还未成功配对（即除开可以分离的树以外还有多少个剩余结点）
- 推广到n层
- 这里假设常见的3种情况，子树1为没有配对成功的，即返回的结点
num > k，子树2为配对成功num = k，num < k, 子树3还有可能配对成功，和根节点相加 - 那么代码就已经出来了，我们只需要dfs，然后判断当前结点获得的返回子节点的情况，若过num > k，配对没有成功，设置为-1返回上去，num = k，跳过这次循环，num < k，与根节点相加，再上层再结点再判断是否为配对成功
- main中为最上层结点，如果它都配对成功（返回的值为k），那么就是说这颗树可以配对成功，否则不可以
import java.io.*;
import java.util.*;
public class Main {
static StreamTokenizer cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static PrintWriter cout = new PrintWriter(new OutputStreamWriter(System.out));
static int t, n, k;
static final int N = (int) (1e5 + 10);
static Vector<Integer>[] node = new Vector[N];
public static int dfs(int now, int parent) {
int num = 1;
for (Integer i : node[now]) {
if(i == parent) continue;
int cnt = dfs(i, now);
if(cnt == -1 || cnt > k) return -1;
if(cnt == k) continue;
num += cnt;
}
return num;
}
public static void main(String[] args) throws IOException {
for (int i = 0; i < N; i++) {
node[i] = new Vector<>();
}
cin.nextToken();
t = (int) cin.nval;
while(t-- != 0) {
for (int i = 0; i < N; i++) {
node[i].clear();
}
cin.nextToken();
n = (int) cin.nval;
cin.nextToken();
k = (int) cin.nval;
for(int i = 1; i <= n - 1; i++) {
cin.nextToken();
int a = (int) cin.nval;
cin.nextToken();
int b = (int) cin.nval;
node[a].add(b);
node[b].add(a);
}
int ans = dfs(1, 1);
if(ans == k) {
cout.println("YES");
} else {
cout.println("NO");
}
}
cout.flush();
}
}
P1747 好奇怪的游戏 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
- 逆向思维，通过预处理，将（1，1）到（20，20）这个正方形范围内的区域预处理，找到每个点到（1，1）的最优解并维护下来
- 每一次输入x，y，只需要直接找就可以了
import java.io.*;
import java.util.*;
public class Main {
static StreamTokenizer cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static Scanner scanner = new Scanner(System.in);
static PrintWriter cout = new PrintWriter(new OutputStreamWriter(System.out));
static int x1, y1;
static int x2, y2;
static int ans;
static final int N = 22;
// static boolean[][] str = new boolean[N][N];
static int[][] g = new int[N][N];
public static void dfs(int x, int y, int cnt) {
if(x <= 0 || x > 20 || y <= 0 || y > 20) {
return;
}
if(cnt >= g[x][y]) {
return;
} else {
g[x][y] = Math.min(g[x][y], cnt);
}
// 走象
dfs(x - 2, y - 2, cnt + 1);
dfs(x + 2, y - 2, cnt + 1);
dfs(x - 2, y + 2, cnt + 1);
dfs(x + 2, y + 2, cnt + 1);
// 走马
dfs(x - 2, y - 1, cnt + 1);
dfs(x - 1, y - 2, cnt + 1);
dfs(x + 1, y - 2, cnt + 1);
dfs(x + 2, y - 1, cnt + 1);
dfs(x - 1, y + 2, cnt + 1);
dfs(x - 2, y + 1, cnt + 1);
dfs(x + 1, y + 2, cnt + 1);
dfs(x + 2, y + 1, cnt + 1);
}
public static void main(String[] args) throws IOException{
cin.nextToken();
x1 = (int) cin.nval;
cin.nextToken();
y1 = (int) cin.nval;
cin.nextToken();
x2 = (int) cin.nval;
cin.nextToken();
y2 = (int) cin.nval;
for(int i = 1; i <= 20; i++) {
Arrays.fill(g[i], 0x3f3f3f3f);
}
dfs(1, 1, 0);
cout.println(g[x1][y1]);
cout.println(g[x2][y2]);
cout.flush();
}
}
[P3956 NOIP2017 普及组] 棋盘 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
- 大模拟了，可以确定有四种可能 有色到有色，有色到无色， 无色到无色， 无色到有色， 通过分类讨论可以得50分
- 后面发现了一个bug就是，我们施展魔法， 如果无色变为红色，而红色如果到黄色 是+3，所以做了修改，60分了
- 然后发现还可以维护每个点得最优距离，就100分了
import java.io.*;
import java.util.*;
public class Main {
static StreamTokenizer cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static Scanner scanner = new Scanner(System.in);
static PrintWriter cout = new PrintWriter(new OutputStreamWriter(System.out));
static int m, n;
static final int N = (int) (1e2 + 10);
static int[][] color = new int[N][N];
static boolean[][] str = new boolean[N][N];
static int[] dx = {1, 0, -1, 0};
static int[] dy = {0, 1, 0, -1};
static int ans = 0x3f3f3f3f;
static int[][] dist = new int[N][N];
/*
color = 1 黄色
color = 0 红色
color = 2 无色
*/
// mofahouyanse
public static void dfs(int x, int y, int cnt, boolean shiyongmofa, int mofahouyanse) {
if(cnt >= ans) return;
if(cnt >= dist[x][y]) {
return;
} else {
dist[x][y] = Math.min(dist[x][y], cnt);
}
if(x == m && y == m) {
ans = Math.min(ans, cnt);
return;
}
for (int i = 0; i < 4; i++) {
int nowx = x + dx[i];
int nowy = y + dy[i];
if(nowx >= 1 && nowx <= m && nowy >= 1 && nowy <= m && !str[nowx][nowy]) {
if(color[x][y] != 2) {
if(color[nowx][nowy] != 2) { //有色到有色
if(color[nowx][nowy] != color[x][y]) {
str[nowx][nowy] = true;
dfs(nowx, nowy, cnt + 1, false, 2);
str[nowx][nowy] = false;
} else {
str[nowx][nowy] = true;
dfs(nowx, nowy, cnt, false, 2);
str[nowx][nowy] = false;
}
} else { //有色到无色
str[nowx][nowy] = true;
if(color[x][y] == 0) {
dfs(nowx, nowy, cnt + 2, true, 0);
}
if(color[x][y] == 1) {
dfs(nowx, nowy, cnt + 2, true, 1);
}
str[nowx][nowy] = false;
}
} else {
if(color[nowx][nowy] != 2) {// 无色到有色
if(color[nowx][nowy] != mofahouyanse) {
str[nowx][nowy] = true;
dfs(nowx, nowy, cnt + 1, false, 2);
str[nowx][nowy] = false;
} else {
str[nowx][nowy] = true;
dfs(nowx, nowy, cnt, false, 2);
str[nowx][nowy] = false;
}
} else {// 无色到无色
continue;
}
}
}
}
}
public static void main(String[] args) throws IOException{
cin.nextToken();
m = (int) cin.nval;
cin.nextToken();
n = (int) cin.nval;
for(int i = 1; i <= m; i++) {
Arrays.fill(color[i], 2);
Arrays.fill(dist[i], 0x3f3f3f3f);
}
for(int i = 1; i <= n; i++) {
cin.nextToken();
int x = (int) cin.nval;
cin.nextToken();
int y = (int) cin.nval;
cin.nextToken();
int c = (int) cin.nval;
color[x][y] = c;
}
str[1][1] = true;
// dist[1][1] = 0;
dfs(1, 1, 0, false, 0);
if(ans == 0x3f3f3f3f) {
cout.println(-1);
} else {
cout.println(ans);
}
cout.flush();
}
}