发表更新题解5 分钟读完 (大约740个字)

题解：Fence Loops

更好的阅读体验

这道题难点在于建图，建完图之后用 $\text{Dijkstra}$ 或 $\text{Floyd}$ 跑个最小环就行了。

我的建图方法和其他题解所赘述的有所不同（在同机房dalao的指点下想到的）。

建图

我们将题目中读入的边看做点，题目中的边权在这里就是点权，考虑边权的设计。不难发现，当篱笆可以组成环时，将两个点间的边权定义为其点权之和，那么环的权值就是所有边权之和的 $\frac{1}{2}$ （因为每个点权都被加了两次）。

最小环

我用的是 $\text{Dijkstra}$ 跑最小环。大致流程如下：

  • 枚举一条边 $(u,v)$ 并删除；

  • 从这条边的一个端点 $u$ 开始跑 $\text{Dijkstra}$ 到另一个端点 $v$ ，可以获得一个值 $dis_v$ 表示不经过 $(u,v)$ 时两点的最短路；

  • 最后统计全局最小环为 $ans=\min(w(u,v)+dis_v)$ 。在本题中最终答案为 $ans\times\frac{1}{2}$ 。

正确性显然。

一个小问题

有细心的读者会发现，如果我们将边转化成点，会出现一个问题：

按上文的找最小环的方法会找到三条边都交于一点的“环”，这样的答案是不合法的，因此我们要规定找最小环时，必须是从一边入另一边出。可以通过开一个 $flg_{u,v}$ 表示 $u$ 这个点，通往 $v$ 的边是在原图的哪一边。

但是由于我们读入时没有处理，即我们不知道谁的左边是谁的右边，因此在判断时要统一一个公共点来判断，于是在跑 $\text{Dijkstra}$ 时处理一个 $f$ 表示上一个点。具体实现间代码。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <bits/stdc++.h>
using namespace std;

int n;
int g[101][101];
bool flg[101][101];

struct node{
	int dis, u, f;
	bool operator<(const node& b) const {
		return dis > b.dis;
	}
};
priority_queue<node> q;
int dis[101];
bool vis[101];

int s, t;

bool dijkstra() {
	memset(dis, 0x3f, sizeof dis);
	memset(vis, 0, sizeof vis);
	dis[s] = 0;
	q.push({0, s, 0});
	while (!q.empty()) {
		int u = q.top().u, f = q.top().f;
		q.pop();
		if (vis[u]) continue;
		vis[u] = 1;
		for (int v = 1; v <= n; v++) {
			if (!g[u][v]) continue;
			if (u == s && v == t) continue;
			if (u == t && v == s) continue;
			if (u != s && flg[u][f] == flg[u][v]) continue;
			if (dis[v] > dis[u]+g[u][v]) {
				dis[v] = dis[u]+g[u][v];
				q.push({dis[v], v, u});
			}
		}
	}
	return dis[t]!=0x3f3f3f3f;
}

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		int k, v, n1s, n2s, x;
		cin >> k >> v >> n1s >> n2s;
		for (int i = 1; i <= n1s; i++) {
			cin >> x;
			g[k][x] += v, g[x][k] += v;
			flg[k][x] = 0;
		}
		for (int i = 1; i <= n2s; i++) {
			cin >> x;
			g[k][x] += v, g[x][k] += v;
			flg[k][x] = 1;
		}
	}
	int ans = 0x3f3f3f3f;
	for (s = 1; s <= n; s++) {
		for (t = s+1; t <= n; t++) {
			if (!g[s][t]) continue;
			if (dijkstra()) {
				ans = min(ans, (g[s][t]+dis[t])/2);
			}
		}
	}
	cout << ans;
}
发表更新题解6 分钟读完 (大约894个字)

题解：速战速决

进入博客食用更香！

一道贪心题。

无解

很明显的，当 $n=1$ 时，因为小I先手，小J可以直接收牌，所以小I无法获胜。

策略

Case 1 小 I 手上没有任何能配对的牌

也就是说对于每一对牌总有一张在小I的手上。

此时我们应该先打出对面出牌序列中最后一张牌，随后对面出什么牌我们就跟着出什么牌，确保小J出的牌能被我们立刻收掉。

最后对面出他的最后一张牌把我们出的第一张牌收掉，此时我们手上的牌全是成对的，对方只有一对牌。随便出一张手上的牌把对面的一张牌收掉，对面下次出牌就必输。

Case 2 小 I 贪心每一回合

此时我们手中必有一对牌。我们能用这对牌来干嘛呢？一开始我们埋下这张牌作为保险，如果后面对面想收牌（牌堆里的或是我手上的），我们就打出这对牌的另一张把整个牌堆清空。

我们可以像 $\text{Case 1}$ 一样，对面出牌我们紧跟着收牌 ，考虑以下几种情况（以下 $A_i$ 指我们出的编号为 $i$ 的牌，$B_i$ 指对面出的编号为 $i$ 的牌，$[\cdot\cdot\cdot]$ 表示当前时刻之后的假设情况）：

  • $A_?…B_i[…A_i]$ 以及 $A_?…B_i[…B_i]$ 这两种情况都会对我们的策略造成威胁，因此在这个时候应该立即收掉所有牌。

  • $A_i…A_iB_j[…]$ 这种情况会使我们误收场上所有牌，导致对方出的 $B_j$ 要么收不掉（这意味着我们要花额外的步数去收这张牌）或是对面会在后面某一时刻清场（这意味着我们要么输，要么步数更多）。

  • 其余情况按正常的成对出牌。

基于以上几点对方就不能在任何时刻收牌，因为我们要么快人一步把前面的收了要么把他出的第一张牌直接收了，而此时也会达到步数最小值，不难发现这个步数最小值是 $n$ 。

* 蒟蒻个人理解，可能有些问题欢迎大家指出！

码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 300010;

int n;
int s[2*MAXN], top, cnts[MAXN];
int mine[MAXN];
int a[MAXN];
queue<int> q;

void pop(int x) {  // 清理公共牌堆
    while (s[top] != x) {
        cnts[s[top]]--;
        mine[s[top]]++;
        q.push(s[top]);
        top--;
    }
    cnts[s[top]]--;
    mine[s[top]]++;
    q.push(s[top]);
    top--;
}

void push(int x) {  // 打牌
    s[++top] = x;
    cnts[x]++;
}

int main() {
    scanf("%d", &n);
    if (n == 1) return printf("-1")&0;  // 无解
    for (int i = 1; i <= n; i++) {
        mine[i] = 2;
    }
    int st = -1;
    for (int i = 1; i <= n; i++) {
        scanf("%d", a+i);
        mine[a[i]]--;
    }
    for (int i = 1; i <= n && st == -1; i++) if (mine[i] == 2) st = i;
    for (int i = 1; i <= n; i++) {
        for (int j = mine[i]-(i==st); j >= 1; j--) q.push(i);
    }

    if (st == -1) {  // 没有成对的牌
        printf("%d\n%d", n+2, a[n]);
        for (int i = 1; i < n; i++) printf(" %d", a[i]);
        printf(" %d %d", a[1], a[1]);
        return 0;
    }

    printf("%d\n%d", n, st);
    mine[st]--;
    push(st);
    push(a[1]);
    for (int i = 2; i <= n; i++) {
        int x = a[i];
        if (mine[x] || cnts[x]) {  // 有威胁。清空牌堆
            printf(" %d", s[1]);
            pop(s[1]);
        } else {
            if (q.front() == s[1]) {  // 会误收牌堆
                q.push(q.front());  // 将队首移到队尾
                q.pop();
            }
            int nxt = q.front();
            printf(" %d", nxt);
            if (cnts[nxt]) {
                pop(nxt);
            } else {
                push(nxt);
                mine[nxt]--;
                q.pop();
            }
        }
        push(x);
    }
}
发表更新题解4 分钟读完 (大约604个字)

题解：Sending a Sequence Over the Network

更好的阅读体验

本蒟蒻的第一篇题解。

这道题我看大家都是用一维 DP 做的，本蒟蒻今天在考场上写了种二维 DP 的做法。我个人认为这种可能理解起来会简单一些（虽说写起来麻烦了点），于是就有了这篇题解。

思路

当时（考场上）想了半天没想出来怎么使用一维 DP 解决这道题，便想了一种二维 DP 的做法。

我们定义 $f[0][i]$ 表示以 $i$ 作为一段的头部时是否可行，$f[1][i]$ 表示以 $i$ 作为一段的结尾是否可行。并且在原序列中添加两个点：$0$ 和 $n+1$。

状态转移（以下 $i$ 均指当前考虑的位置）：

  • 头的转移
  1. 如果上一个位置可以作为尾，那么这个位置就可以作为头。
    也就是 $f[0][i] = f[1][i-1]$
  2. 如果当前位置作为头，那么下一段的头的位置也可以作为头。
    也就是 $f[0][i+a[i]+1] = f[0][i]$
  • 尾的转移
  1. 如果上一段的尾的位置可以做尾，则当前位置可以做尾。
    也就是 $f[1][i] = f[1][i-a[i]-1]$
  2. 如果这一段的头的位置可以做头，那么当前位置也可以做尾。
    也就是 $f[1][i]=f[0][i-a[i]]$

注意：写代码的时候要注意下标不能越界。

根据以上的转移（可能有点乱），我们能知道初始状态为：
$$
f[1][0] = f[0][1] = 1
$$

而最后我们只需要判断第 $n$ 个位置能否做尾或第 $n+1$ 个位置能否做头就好。

代码

（供群众批判）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>
using namespace std;

int n;
int a[200010];
bool f[2][200010];
/*
  0: 作为头
  1: 作为尾
 */

int main() {
	int T;
	cin >> T;
	while (T--) {
		cin >> n;
		for (int i = 1; i <= n; i++) cin >> a[i];
		memset(f, 0, sizeof f); // 多测不清空，爆零两行泪
		f[1][0] = 1;
		f[0][1] = 1;
		for (int i = 1; i <= n; i++) {
			// i作为头
			// 从上一个是尾转移
			f[0][i] |= f[1][i-1];
			// 隐藏情况：之前有人帮它更新了
			// 更新下一个可能作为头的
			if (f[0][i] && i+a[i]+1 <= n+1) f[0][i+a[i]+1] = 1;
			// i作为尾
			if (i-a[i]-1 >= 0) f[1][i] |= f[1][i-a[i]-1];
			if (i-a[i] >= 0) f[1][i] |= f[0][i-a[i]];
		}
		if (f[1][n] || f[0][n+1]) cout << "Yes" << endl;
		else cout << "No" << endl;
	}
}
发表更新题解3 分钟读完 (大约473个字)

题解：对称二叉树

思路

因为这道题只要求最大的节点数量，所以我们只用枚举“根节点”的位置，然后判断是否对称，如果对称，统计这棵子树的节点数并记录 ans 。
cnt 与 main 函数过于简单故不在此处展开赘述，单独看看 same 函数——判断是否对称。我们一次需要两个位置来判断对称，而这两棵子树对称，当且仅当它们的儿子们全部对称，便可以从此处向下递归。递归的两边就是同时向内收 (ls[RootR],rs[RootL]) 或同时向外放 (ls[RootL],rs[RootR])，如果不这样的话遍历的两个位置本身就不对称。基于此，我们再来看实现。

实现

在代码实现方面，存树我们使用两个列表 ls 与 rs，这里开成了一个结构体，除此之外，我们还需要一个 id 用于存储树上节点的 value 。其余部分和思路部分所论述的一样。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

/*头文件及数组略*/

bool same(long long x, long long y) {
    if (x < 0 && y < 0) return true;     // 如果两边遍历到此处均为空，这棵树仍然对称
    if (x < 0 || y < 0) return false;    // 前面把都为空的情况return了，这里是只有一个点为空的情况
    if (t[x].id != t[y].id) return false;  // 值不匹配
    bool r = same(t[x].ls, t[y].rs)&&same(t[x].rs, t[y].ls);  // 递归检查子树是否符合要求
    return r;  // 略(?)
}

long long cnt(long long u) {  // 简单的节点统计
    if (u < 0) return 0;
    return cnt(t[u].ls)+cnt(t[u].rs)+1;
}

int main() {
    /* 输入略 */
    for (long long i = 1; i <= n; i++) {
        if (same(i, i)) {  // 如果以i为根的子树对称，统计节点并记录ans
            ans = max(ans, cnt(i));
        }
    }
    cout << ans;
    return 0;  // 结束
}
关注我

链接

最新文章

归档

标签

乘法逆元1
二分图1
优化2
动态规划4
图论2
存储2
思想1
总结13
技巧1
排列组合1
数学2
数据结构1
最短路2
欧拉反演1
游记1
算法1
背包问题1
解题报告1
连通块1
随笔1
题解4
×