COGS
  • 图论工具
  • 演草纸
  • 帮助
  • 登录



    • 注册
    • 忘记密码
题目编号 用户编号
Gravatar
终焉折枝
积分：1831
提交：225 / 396

Pro2534  [SCOI 2005]骑士精神 题解

更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19526480


大意

最小的步数达到要求的地方。


思路

这个题目的目标状态也很简约，就是形如题目中的样子，这个我们转换思路就是拿着这个空格去和旁边的格子不断的交换，但是这样产生的状态是很多的，为了剪枝，我们采用 IDA*，这个题目的估价函数有个很显然的写法，就是记录错误位置的个数，因此，一定小于等于...吗？我们考虑这样的情况，如果现在只需要一步，将空格和一个棋子交换，这样的实际步数是 $1$，但是你的估价函数给的是 $2$，显然不行，特判一下即可。然后我们就正常的去迭代加深的搜索就好。


代码 


#include<iostream>
using namespace std;

int T, ans = 1e9;
int a[6][6];
int dx[] = {1, 1, -1, -1, 2, 2, -2, -2};
int dy[] = {2, -2, 2, -2, 1, -1, 1, -1};


int f(int b[6][6]){
	int res = 0;
	for(int j = 1;j <= 5;j ++){
		if(b[1][j] != 1) res ++;
	}
	for(int j = 1;j <= 5;j ++){
		if(b[5][j] != 0) res ++;
	}
	if(b[2][1] != 0) res ++;
	for(int j = 2;j <= 5;j ++){
		if(b[2][j] != 1) res ++;
	}
	if(b[4][5] != 1) res ++;
	for(int j = 1;j <= 4;j ++){
		if(b[4][j] != 0) res ++;
	}
	for(int j = 1;j <= 2;j ++){
		if(b[3][j] != 0) res ++;
	}
	if(b[3][3] != 2) res ++;
	for(int j = 4;j <= 5;j ++){
		if(b[3][j] != 1) res ++;
	}
	if(res == 2) return 1;
	return res;
}

void dfs(int dp, int now, int cnt[6][6]){
	if(now >= ans) return;
	if(f(cnt) == 0){
		ans = now;
		return;
	}
	if(now + f(cnt) > dp) return;
	if(now > dp){
		return;
	}
	int sx = 0, sy = 0;
	for(int i = 1;i <= 5;i ++){
		if(sx) break;
		for(int j = 1;j <= 5;j ++){
			if(cnt[i][j] == 2){
				sx = i, sy = j;
				break;
			}
		}
	}
	for(int i = 0;i < 8;i ++){
		int nx = sx + dx[i];
		int ny = sy + dy[i];
		if(nx < 1 || ny < 1 || nx > 5 || ny > 5) continue;
		int sum[6][6];
		for(int p = 1;p <= 5;p ++){
			for(int q = 1;q <= 5;q ++){
				sum[p][q] = cnt[p][q];
			}
		}
		swap(sum[sx][sy], sum[nx][ny]);
		dfs(dp, now + 1, sum);
	}
}

int main(){

	cin >> T;

	while(T --){
		for(int i = 1;i <= 5;i ++){
			string s; cin >> s;
			for(int j = 0;j < 5;j ++){
				if(s[j] == '*') a[i][j + 1] = 2;
				else a[i][j + 1] = s[j] - '0';
			}
		}
		ans = 1e9;
		for(int dp = 1;dp <= 15;dp ++){
			dfs(dp, 0, a);
			if(ans <= 15) break;
		}
		if(ans <= 15){
			cout << ans << '\n';
		}
		else{
			cout << -1 << '\n';
		}
	}

	return 0;
}



题目2534  [SCOI 2005]骑士精神      5      评论
2026-02-04 20:40:06    
Gravatar
终焉折枝
积分：1831
提交：225 / 396

Pro4261  [TJOI2011] 树的序 题解

更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19525640


大意

这个题要求输出字典序最小的等价的二叉查找树。


思路

首先考虑这个题目，插入键值之后的树，是按照权值与时间来说的，我们将其设为二元组 $(k, t)$，那么我们不难发现这个树是一颗 Treap，权值满足 BST，时间戳满足小根堆。

对于样例，我们可以建出来这样的树：

$(1, 1), (4, 2), (3, 3), (2, 4)$

那么显然 $2$ 和 $4$ 是叶子节点，我们如果要保持这个 Treap 的结构的话，我们如果交换这俩节点的时间戳是没有问题的。

所以对于这种二维结构的维护，那我们可以用笛卡尔树维护，因为笛卡尔树也是一个 Treap，我们按照节点从左到右，时间戳为权值建立笛卡尔树。

那么我们建出来的树，显然是在一个节点有两个子节点的时候，那就是先左再右最优，且父更优。

则我们的有限度为：

$$父节点 \ge 左子节点 \ge 右子节点$$

那不就是一个先序遍历过程嘛。

也就是我们只需要建出一颗笛卡尔树，就直接先序遍历即可。


代码 


#include<iostream>
#include<stack>
using namespace std;

const int MAXN = 1e5 + 5;
stack<int> stk;
int l[MAXN], r[MAXN];
int a, n;
int in[MAXN], pos[MAXN];

void dfs(int u){
	cout << u << ' ';
	if(l[u]) dfs(l[u]);
	if(r[u]) dfs(r[u]);
}

int main(){
	cin >> n;
	for(int i = 1;i <= n;i ++){
		cin >> a;
		pos[a] = i;
	}
	stk.push(1);
	for(int i = 2;i <= n;i ++){
		int lst = 0;
		while(!stk.empty() && pos[i] < pos[stk.top()]){
			lst = stk.top();
			stk.pop();
		}
		if(stk.empty()){
			l[i] = lst;
		}
		else{
			l[i] = r[stk.top()];
			r[stk.top()] = i;
		}
		stk.push(i);
	}

	int rt = 0;
	for(int i = 1;i <= n;i ++){
		in[l[i]] ++;
		in[r[i]] ++;
	}

	for(int i = 1;i <= n;i ++){
		if(!in[i]){
			rt = i;
			break;
		}
	}

//	cout << rt << '\n';

//	for(int i = 1;i <= n;i ++){
//		cout << i << ": " << l[i] << ' ' << r[i] << '\n';
//	}

	dfs(rt);

	return 0;
}



题目4261  [TJOI2011] 树的序 AAAAAAAAAA      6      评论
2026-02-04 20:39:57    
Gravatar
终焉折枝
积分：1831
提交：225 / 396

Pro1845  [JSOI 2008]球形空间产生器sphere 题解

更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19525292


大意

给你一个 $n$ 维空间，给我 $n + 1$ 个点，你要确定这个球的中心点的坐标。


思路

原始方程（$n + 1$ 个）对于每一个点 $i$，到球心 $(x_1, \dots, x_n)$ 的距离平方相等：$\sum_{j=1}^n (p_{i,j} - x_j)^2 = R^2$

降次消元（作差）用相邻两个方程 $(i+1)$ 和 $(i)$ 相减，消去二次项 $x_j^2$ 和 $R^2$：$$\sum_{j=1}^n (p_{i+1,j} - x_j)^2 - \sum_{j=1}^n (p_{i,j} - x_j)^2 = 0$$展开并整理：$$\sum_{j=1}^n (p_{i+1,j}^2 - 2p_{i+1,j}x_j) - \sum_{j=1}^n (p_{i,j}^2 - 2p_{i,j}x_j) = 0$$

标准线性方程将未知数 $x_j$ 移至左侧，常数移至右侧：$$\sum_{j=1}^n 2(p_{i+1,j} - p_{i,j})x_j = \sum_{j=1}^n (p_{i+1,j}^2 - p_{i,j}^2)$$

增广矩阵 $[A|B]$

$$\left[\begin{array}{ccc|c}2(p_{2,1}-p_{1,1}) & \dots & 2(p_{2,n}-p_{1,n})  & \sum (p_{2,j}^2 - p_{1,j}^2) \\ 2(p_{3,1}-p_{2,1}) & \dots & 2(p_{3,n}-p_{2,n})  & \sum (p_{3,j}^2 - p_{2,j}^2) \\ \vdots & \ddots & \vdots  & \vdots \\ 2(p_{n+1,1}-p_{n,1}) & \dots & 2(p_{n+1,n}-p_{n,n})  & \sum (p_{n+1,j}^2 - p_{n,j}^2) \end{array}\right]$$


代码 


#include<iostream>
#include<cmath>
using namespace std;

const int MAXN = 15;
const double eps = 1e-6;

int n;
double a[MAXN][MAXN];
double p[MAXN][MAXN];

bool Jornh(){
    for(int i = 1;i <= n;i ++){
        int piv = i;
        for(int k = i + 1;k <= n;k ++){
            if(fabs(a[k][i]) > fabs(a[piv][i])){
                piv = k;
            }
        }
        for(int j = 1;j <= n + 1;j ++){
            swap(a[i][j], a[piv][j]);
        }
        if(fabs(a[i][i]) < eps){
            return false;
        }
        for(int k = 1;k <= n;k ++){
            if(k == i) continue;
            double fac = a[k][i] / a[i][i];
            for(int j = i;j <= n + 1;j ++){
                a[k][j] -= fac * a[i][j];
            }
        }
    }
    for(int i = 1;i <= n;i ++){
        a[i][n + 1] /= a[i][i];
    }
    return true;
}

int main(){

    cin >> n;
    for(int i = 1;i <= n + 1;i ++){
        for(int j = 1;j <= n;j ++){
            cin >> p[i][j];
        }
    }

    for(int i = 1;i <= n;i ++){
        double res = 0;
        for(int j = 1;j <= n;j ++){
            a[i][j] = 2.0 * (p[i + 1][j] - p[i][j]);
            res += (p[i + 1][j] * p[i + 1][j] - p[i][j] * p[i][j]);
        }
        a[i][n + 1] = res;
    }

    if(Jornh()){
        for(int i = 1;i <= n;i ++){
            printf("%.3lf ", a[i][n + 1]);
        }
    }
    return 0;
}




题目1845  [JSOI 2008]球形空间产生器sphere AAAAAAAAAA      6      评论
2026-02-04 20:39:29    
Gravatar
终焉折枝
积分：1831
提交：225 / 396

Pro660  [ZJOI 2007] 矩阵游戏 题解

更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19494007


大意

给你一个矩阵的黑白情况，求是否能通过交换行和列达到主对角线上全是黑点。


思路

我们考虑从这个点的行向列连边，跑二分图匹配。

原因在于，我们如果交换两行或者两列，无非是交换了连边，最终的匹配不会发生改变。

于是只需要二分图匹配一下，看看是否能刚刚好匹配出来即可。


代码 


#include <bits/stdc++.h>
using namespace std;
const int N = 300;
vector<int> g[N];
bool vst[N];
int rmatch[N];
bool dfs(int u) {
    for (int i = 0; i < g[u].size(); i++) {
        int v = g[u][i];
        if (!vst[v]) {
            vst[v] = true;
            if(rmatch[v] == -1 || dfs(rmatch[v])){
                rmatch[v] = u;
                return true;
            }
        }
    }
    return false;
}
int hungary(int n) {
    int cnt = 0;
    memset(rmatch, -1, sizeof(rmatch));
    for (int i = 1; i <= n; ++i) {
        memset(vst, 0, sizeof(vst));
        cnt += dfs(i);
    }
    return cnt;
}
int main() {
    int T, n, x;
    cin >> T;
    while (T--) {
        cin >> n;
        for (int i = 1; i <= n; i++) g[i].clear();
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                cin >> x;
                if(x == 1){
                    g[i].push_back(j);
                }
            }
        }
        if(hungary(n) == n){
            cout << "Yes\n";
        }
        else{
            cout << "No\n";
        }
    }
    return 0;
}



题目660  [ZJOI 2007] 矩阵游戏 AAAAAAAAAA      6      评论
2026-02-04 20:38:45    
Gravatar
终焉折枝
积分：1831
提交：225 / 396

Pro3454  [POJ 2559]直方图中最大的矩形 题解

更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19524914


大意

直方图中的最大矩形


思路

首先这个题目要求的是长直图中最大的矩形，我们考虑用笛卡尔树去完成这个题目。

首先我们以高度为点权建立笛卡尔树，然后我们如果知道一个点有多少个子节点，那么这个点的矩形并的答案为 $h[i] * sz[i]$，最后全部跑一次即可。

当然，朴素的单调栈也未尝不可，但是笛卡尔树更加形象。


代码 


#include<iostream>
#include<stack>
#include<algorithm>
#include<cstring>
using namespace std;

#define int long long
const int MAXN = 1e6 + 10;

int n, a[MAXN];
int l[MAXN], r[MAXN];
int sz[MAXN], in[MAXN];

int dfs(int x){
	if(!x) return 0;
	sz[x] = 1;
	sz[x] += dfs(l[x]);
	sz[x] += dfs(r[x]);
	return sz[x];
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	while(cin >> n && n){
		for(int i = 0;i <= n;i ++){
			l[i] = r[i] = sz[i] = in[i] = 0;
		}
		stack<int> st;
		for(int i = 1;i <= n;i ++){
			cin >> a[i];
		}
		for(int i = 1;i <= n;i ++){
			int last = 0;
			while(!st.empty() && a[st.top()] > a[i]){
				last = st.top();
				st.pop();
			}
			if(!st.empty()){
				r[st.top()] = i;
			}
			l[i] = last;
			st.push(i);
		}
		for(int i = 1;i <= n;i ++){
			if(l[i]) in[l[i]] ++;
			if(r[i]) in[r[i]] ++;
		}
		int root = 0;
		for(int i = 1;i <= n;i ++){
			if(!in[i]){
				root = i;
				break;
			}
		}
		dfs(root);
		int ans = 0;
		for(int i = 1;i <= n;i ++){
			ans = max(ans, a[i] * sz[i]);
		}
		cout << ans << '\n';
	}
	return 0;
}



题目3454  [POJ 2559]直方图中最大的矩形 A      6      1 条 评论
2026-02-04 20:38:34    
Gravatar
终焉折枝
积分：1831
提交：225 / 396

Pro2558  [NOIP 2016]换教室 题解

更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19525009


前置知识


前言


既然没人讲与概率有关的知识的话，那就让我来简单介绍一下概率的相关知识吧，这个如果不知道的话这道题还是很难写的。


概率相关

定理 $1$：互补法则

定义：若事件 $A$ 发生的概率为 $P(A)$，则其不发生概率为 $1 - P(A)$。

举例：早上起来有两种选择，吃饭和不吃饭，若吃饭的概率为 $\displaystyle\frac{3}{10}$，则有不吃饭的概率为 $1 - \displaystyle\frac{3}{10} = \displaystyle\frac{7}{10}$。

定理 $2$：加法法则（互斥事件）

定义：若事件 $A_1 \sim A_n \in S$ 且 $A_i \cap A_j=\emptyset \quad \forall i, j\in\{1,2,\dots,n\},\quad i \neq j$。

那么集合中所有事件发生的概率 $P = \sum_{i=1}^n P(A_i)$。

举例：掷一次骰子时，点数大于 $4$ 的概率 $P = P(5) + P(6) = \displaystyle\frac{1}{6} + \displaystyle\frac{1}{6} = \displaystyle\frac{1}{3}$。

定理 $3$：乘法法则（无关事件）

定义：若事件 $A$ 与 $B$ 互相独立，不受影响，那么$ P(A \cap B) = P(A) \times P(B)$。

举例：早上吃饭的概率为 $\displaystyle\frac{3}{10}$，吃完饭写作业的概率为 $\displaystyle\frac{5}{6}$，那么早上吃完饭后去写作业的概率为 $\displaystyle\frac{3}{10} \times \displaystyle\frac{5}{6} = \displaystyle\frac{1}{4}$。

题目

题目大意

牛牛需要在 $n$ 个时间段内完成 $2n$ 节课程，每时间段有两节课程分别安排在教室 $c_i$ 和 $d_i$。牛牛可以申请更换教室，申请通过的概率为 $k_i$，最多申请 $m$ 次。更换教室后，牛牛需要在教室间移动，移动的体力消耗为最短路径的体力值。求最小的体力消耗期望值。

题目类型

我们发现对于每一个时间段 $i$ 的课程，都有选 $c_i$ 和 $d_i$ 两种，我们可以很快想到用动态规划来解决期望概率的问题，而最短路径的话可以用弗洛伊德算法求解，因为本题 $1 \le v \le 300$，那么我们的状态如何设计呢？

状态设计

首先，对于每个时间段是一定要在状态里面的。其次，牛牛对于换教室这个事情其实是不感冒的，可以换或者不换，因此换了多少个教室是一定要在条件里面的。最后，因为我们按时间段向后 dp 的话，当前的 $i$ 时间段是由 $i - 1$ 推出的，但是无法记录上一个时间段到底换没换教室，如果要开个别的东西记录一下就太麻烦，因此就需记录上一个时间段是否换了教室。

所以我们可以这样记录状态，用 $dp_{i,j,k}$ 来表示，在第 $i$ 个时间段内，已经选了 $j$ 间教室更换，$k$ 表示当前的为这个时间段是否更换，$k \in \{0,1\}$。

转移方程（分类讨论）

一：选择不更换当前的教室，再次分类讨论。

由互补法则可知，当前成功更换的概率为 $v_i$，失败的概率即为 $1 - v_i$，而下文的 $2$ 与 $3$ 属于互斥事件，因此用加法法则，将两者的概率加到一起。

1. 前一个教室不做更改，当前期望值即为 $f_{c_{i-1},c_i}$。

2. 前一个教室做更改，且更改成功，当前期望值即为 $v_{i-1} \times f_{d_{i-1},c_i}$。

3. 前一个教室做更改，且更改失败，当前期望值即为 $(1 - v_{i-1}) \times f_{c_{i-1},c_i}$。

总结第一大类的情况，为了求最小值，所以取小，即可得出选择不更换当前教室的转移方程：

$dp_{i,j,0} \gets \min(dp_{i-1,j,0} + f_{c_{i-1},c_i},dp_{i-1,j,1} + v_{i-1} \times f_{d_{i-1},c{i}} + (1 - v_{i-1}) \times f_{c_{i-1},c_i})$

二：选择更换当前教室，再次分类讨论

下文的 $1$ 和 $2$ 属于互斥事件，而 $3,4,5,6$ 也属于互斥事件，因此用加法法则，将两者的概率加到一起。而对于 $3,4,5,6$，由乘法法则，则将两次概率相乘。

1. 前一个教室不做更改，且当前教室更改成功，当前期望值即为 $v_i \times f_{c_{i-1},d_i}$

2. 前一个教室不做更改，且当前教室更改失败，当前期望值即为 $(1 - v_i) \times f_{c_{i-1},c_i}$

3. 前一个教室做更改，且前一个更改成功，当前教室更改成功，当前期望值即为 $v_{i-1} \times v_i \times f_{d_{i-1},d_i}$

4. 前一个教室做更改，且前一个更改成功，当前教室更改失败，当前期望值即为 $v_{i-1} \times (1 - v_i) \times f_{d_{i-1},c_i}$

5. 前一个教室做更改，且前一个更改失败，当前教室更改成功，当前期望值即为 $(1 - v_{i-1}) \times v_i \times f_{c_{i-1},d_i}$

6. 前一个教室做更改，且前一个更改失败，当前教室更改失败，当前期望值即为 $(1 - v_{i-1}) \times (1 - v_i) \times f_{c_{i-1},c_i}$

总结第二大类的情况，这里的 $j$ 不要忘记 $-1$，即可得出选择更换当前教室的转移方程：

$dp_{i,j,1} \gets \min(dp_{i-1,j-1,0} + v_i \times f_{c_{i-1},d_i} + (1 - v_i) \times f_{c_{i-1},c_i},dp_{i-1,j-1,1} + v_{i-1} \times v_i \times f_{d_{i-1},d_i} + v_{i-1} \times (1 - v_i) \times f_{d_{i-1},c_i} + (1 - v_{i-1}) \times v_i \times f_{c_{i-1},d_i} + (1 - v_{i-1}) \times (1 - v_i) \times f_{c_{i-1},c_i})$


代码 

#include<iostream>
#include<algorithm>
#include<iomanip>
//#define int long long
using namespace std;

const int MAXN = 2005;
const int MAXV = 305;
double f[MAXV][MAXV];
int n,m,e,v;
int c[MAXN],d[MAXN];
double k[MAXN];
double dp[MAXN][MAXN][2];

signed main(){
	cin.tie(0) -> ios::sync_with_stdio(0);
	cin >> n >> m >> v >> e;
	for(int i = 1;i <= n;i ++) cin >> c[i];
	for(int i = 1;i <= n;i ++) cin >> d[i];
	for(int i = 1;i <= n;i ++) cin >> k[i];
	for(int i = 1;i <= v;i ++){
		for(int j = 1;j <= v;j ++){
			f[i][j] = 1e18;
		}
		f[i][i] = 0;
	}
	for(int u,v,w,i = 1;i <= e;i ++){
		cin >> u >> v >> w;
		f[v][u] = f[u][v] = min(f[u][v],w * 1.0);
	}
	for(int t = 1;t <= v;t ++){
		for(int i = 1;i <= v;i ++){
			for(int j = 1;j <= v;j ++){
				if(f[i][t] + f[t][j] < f[i][j]){
					f[i][j] = f[i][t] + f[t][j];
				}
			}
		}
	}
	for(int i = 1;i <= n;i ++){
		for(int j = 0;j <= m;j ++){
			dp[i][j][1] = dp[i][j][0] = 1e18;
		}
	}
	dp[1][0][0] = 0;
	dp[1][1][1] = 0;
	for(int i = 2;i <= n;i ++){
		for(int j = 0;j <= m;j ++){
			dp[i][j][0] = min(dp[i - 1][j][0] + f[c[i - 1]][c[i]],dp[i - 1][j][1] + k[i - 1] * f[d[i - 1]][c[i]] + (1 - k[i - 1]) * f[c[i - 1]][c[i]]);
			if(j > 0) dp[i][j][1] = min(dp[i - 1][j - 1][0] + f[c[i - 1]][d[i]] * k[i] + f[c[i - 1]][c[i]] * (1 - k[i]),dp[i - 1][j - 1][1] + k[i - 1] * k[i] * f[d[i - 1]][d[i]] + k[i - 1] * (1 - k[i]) * f[d[i - 1]][c[i]] + (1 - k[i - 1]) * k[i] * f[c[i - 1]][d[i]] + (1 - k[i - 1]) * (1 - k[i]) * f[c[i - 1]][c[i]]);
		}
	}
	double ans = 1e18;
	for(int i = 0;i <= m;i ++){
		ans = min(ans,min(dp[n][i][1],dp[n][i][0]));
	}
	cout << fixed << setprecision(2) << ans << '\n';
	return 0;
}


题目2558  [NOIP 2016]换教室 AAAAAAAAAAAAAAAAAAAAAAAAA      6      评论
2026-02-04 20:36:02    
中文繁體 中文简体

2026-04-11 06:59:52 以 Twitter Bootstrap 作为界面框架，应用 bootstrap 主题。 进程运行 0.0274 s ，处理完成数据库 36 次。

由 CmYkRgB123 在线评测系统 强力驱动，版本 2.8.2.1 ，由 王者自由 二次开发。原作者 © BYVoid，保留部分权利。技术支持：河南省实验中学 邮箱：syxinxi@sina.cn