8.23 更新
大家好像对第一题比较感兴趣。
8.22更新
看到有人问怎么得到题目的，如果稍微懂一点前端的话就知道，打开浏览器开发者工具，然后copy element拿到HTML，然后转成Markdown就行了。
题目比较简单：
1. 找规律，展开一下发现系数是n/n, (n-1)/n, (n-2)/n, ..., 然后对相同的锁排序即可。
2. 额，模拟
3. 排序+双指针
4. 额，数据量比较小，暴力即可
5. 从边缘的 0 深搜即可，不被围起来的点肯定与边缘的0连通。
1. 开锁
题目描述
有n把钥匙，m个锁，每把锁只能由一把特定的钥匙打开，其他钥匙都无法打开。一把钥匙可能可以打开多把锁，钥匙也可以重复使用。
对于任意一把锁来说，打开它的钥匙是哪一把是等概率的。但你无法事先知道是哪一把钥匙，只能进行尝试。
已知每次尝试用第i把钥匙打开第j把锁会消耗的时间aij秒。
问最优策略下打开所有锁的总期望时间是多少秒。
对于任意一把锁来说，打开它的钥匙是哪一把是等概率的。但你无法事先知道是哪一把钥匙，只能进行尝试。
已知每次尝试用第i把钥匙打开第j把锁会消耗的时间aij秒。
问最优策略下打开所有锁的总期望时间是多少秒。
输入描述
第一行两个以空格分隔的正整数n,m。
接下来m行每行m个空格分隔的正整数aij。
1<=n,m,aij <=500
接下来m行每行m个空格分隔的正整数aij。
1<=n,m,aij <=500
输出描述
输出一个小数代表答案，你的答案会被认为是正确的当且仅当你的答案与正确答案的绝对误差或相对误差不超过10-6。
参考代码
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> a(m, vector<int>(n));
for (int j = 0; j < n; ++j) {
for (int i = 0; i < m; ++i) {
cin >> a[i][j];
}
}
double ans = 0;
for (int i = 0; i < m; ++i) {
sort(a[i].begin(), a[i].end());
for (int j = 0; j < n; ++j) {
ans += (n - j) * a[i][j];
}
}
printf("%.6lf\n", ans / n);
return 0;
} 2. 勇闯币圈
题目描述
最近以比特币为代表的数字货币市场非常动荡，聪明的小明打算用马尔科夫链来建模股市。如图所示，该模型有三种状态：“行情稳定”，“行情大跌”以及“行情大涨”。每一个状态都以一定的概率转化到下一个状态。比如，“行情稳定”以0.4的概率转化到“行情大跌”的状态。
有了概率转移矩阵P，我们只要知道一个初始状态 
，我们就容易可以知道第 t 步三种状态的概率了。由此可以知道行情什么时候大涨大跌，从而发家致富，赢取白富美，走向人生巅峰。比如我们想知道第1步之后“行情大跌”的概率，那么由全概率公式和马尔科夫链的性质(第t步的概率只和第t-1步有关)： 
可以通过该模型，计算出第t步的“行情大涨”的概率吗？如果这个概率大于0.5那么输出1，否则输出0。
不妨设“行情稳定”，“行情大跌”以及“行情大涨”分别为状态0，状态1和状态2。我们可以定义概率转移矩阵P，其中P(i,j)的数值表示的是状态j转移到状态i的概率。如图所示的概率转移矩阵为：
，我们就容易可以知道第 t 步三种状态的概率了。由此可以知道行情什么时候大涨大跌，从而发家致富，赢取白富美，走向人生巅峰。比如我们想知道第1步之后“行情大跌”的概率，那么由全概率公式和马尔科夫链的性质(第t步的概率只和第t-1步有关)： 可以通过该模型，计算出第t步的“行情大涨”的概率吗？如果这个概率大于0.5那么输出1，否则输出0。
输入描述
第1行输入为测试数据组数T(1<=T<1000)，接下来T组每5行的数据格式为
T组第1行是步长1<=t<=10。
T组第2行是一个3维的初始状态
T组第3行到第5行是3*3的概率转移矩阵P，每行有三个浮点数
T组第1行是步长1<=t<=10。
T组第2行是一个3维的初始状态
T组第3行到第5行是3*3的概率转移矩阵P，每行有三个浮点数
输出描述
如果第t步的“行情大涨”概率大于0.5那么输出1，否则输出0参考代码
#include <bits/stdc++.h>
using namespace std;
void solve() {
int t;
vector<double> a(3);
vector<vector<double>> p(3, vector<double>(3));
cin >> t;
for (int i = 0; i < 3; ++i) {
cin >> a[i];
}
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
cin >> p[i][j];
}
}
while (t--) {
auto tmp = a;
for (int i = 0; i < 3; ++i) {
a[i] = 0;
for (int j = 0; j < 3; ++j) {
a[i] += tmp[j] * p[i][j];
}
}
}
cout << (a[2] > 0.5 ? 1 : 0) << '\n';
}
int main() {
ios_base::sync_with_stdio(false), cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
solve();
}
return 0;
} 3. 迎宾车队
题目描述
今天正在进行赛车车队选拔，每一辆赛车都有一个不可以改变的速度。现在需要选取速度差距在10以内的车队（车队中速度的最大值减去最小值不大于10），用于迎宾。车队的选拔按照的是人越多越好的原则，给出n辆车的速度，你能选出满足条件的最多车辆的车队吗。
输入描述
第一行一个数字n(1<=n<=100000)。
接下来一行n个整数，speed[i] 表示第i辆车的速度为speed[i](1<=speed[i]<=109)。
接下来一行n个整数，speed[i] 表示第i辆车的速度为speed[i](1<=speed[i]<=109)。
输出描述
输出一行，最大车辆数目。参考代码
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false), cin.tie(nullptr);
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
sort(a.begin(), a.end());
int ans = 0;
for (int i = 0, j = 0; j < n; ++j) {
while (i < n && a[j] - a[i] > 10) {
i += 1;
}
ans = max(ans, j - i + 1);
}
cout << ans << '\n';
return 0;
} 4. 水站的水流量
题目描述
有一个水站网络共有n层，第i层有i个水站节点，如图所示连接，水流单向流动。
每个水站在达到MAX个水流量时，称该水站满负荷工作，后续流进该水站的水流量，将会分为两等份流向它后面所连接的两个水站。若每秒都有流入第一个水站MAX个水流量，请问第T秒有多少个水站是满负荷工作的？
输入描述
一行两个正整数，n和t。
输出描述
一个正整数，第t秒满负荷工作的水站数量。参考代码
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false), cin.tie(nullptr);
int n, t;
cin >> n >> t;
if (n == 1) {
cout << 1 << '\n';
return 0;
}
int N = n * (n + 1) / 2;
vector<int> a(N + 1);
int b = 1 << 10;
while (t--) {
a[1] += b;
int s = 1, d = 1;
while (s <= N - n - n + 2) {
for (int i = s; i < s + d; ++i) {
if (a[i] > b) {
int r = (a[i] - b) / 2;
a[i + d] += r;
a[i + d + 1] += r;
a[i] = b;
}
}
s += d;
d += 1;
}
}
int ans = 0;
for (int i = 1; i <= N; ++i) {
if (a[i] >= b) {
ans += 1;
}
}
cout << ans << '\n';
return 0;
} 5. 定点轰炸
题目描述
牛牛是军团的指挥官，这一天，高层来到团中检查，牛牛为了演示军团的实战能力，决定表演定点轰炸。
在事先既定的 n*n大小的矩形中，随机勾勒上几笔，轰炸位置即为被这几笔所包围的区域。
你作为自动化定点轰炸的创始人，需要为此书写一个程序，来完成这个任务。首先，你将整个 n*n的矩形看成一个全 0矩形，勾勒的笔画所经过的位置用 1表示，现在，你需要将被轰炸区域改成数字 2，用于标记，指引轰炸方位。
一个被 1包围的区域定义为：区域内部的点不能通过上下左右的移动，在不经过 1的前提下到达区域外的 0点或者矩形外部。
在事先既定的 n*n大小的矩形中，随机勾勒上几笔，轰炸位置即为被这几笔所包围的区域。
你作为自动化定点轰炸的创始人，需要为此书写一个程序，来完成这个任务。首先，你将整个 n*n的矩形看成一个全 0矩形，勾勒的笔画所经过的位置用 1表示，现在，你需要将被轰炸区域改成数字 2，用于标记，指引轰炸方位。
一个被 1包围的区域定义为：区域内部的点不能通过上下左右的移动，在不经过 1的前提下到达区域外的 0点或者矩形外部。
输入描述
第一行输入一个正整数n(1<=n<1000) ，代表矩形边长。
接下去 n 行，每行 n个整数，整数仅有可能为 0或 1，含义如题所述。
接下去 n 行，每行 n个整数，整数仅有可能为 0或 1，含义如题所述。
输出描述
输出一个 n*n的矩形，一共 n行，每行 n 个整数，该矩形代表标记完轰炸区域后的结果呈现。由于勾勒的随机性，有可能不能形成封闭区域，此时，只需要输出原矩形即可。
参考代码
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false), cin.tie(nullptr);
int n;
cin >> n;
vector<vector<int>> g(n, vector<int>(n)), gg(n, vector<int>(n));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
cin >> g[i][j];
gg[i][j] = g[i][j] ? 1 : 2;
}
}
int dx[] = {0, -1, 0, 1}, dy[] = {-1, 0, 1, 0};
function<void(int, int)> Dfs = [&](int i, int j) {
if (gg[i][j] != 2) {
return ;
}
gg[i][j] = 0;
for (int k = 0; k < 4; ++k) {
int r = i + dx[k], c = j + dy[k];
if (0 <= r && r < n && 0 <= c && c < n) {
Dfs(r, c);
}
}
};
for (int i = 0; i < n; ++i) {
Dfs(i, 0);
Dfs(i, n - 1);
}
for (int j = 0; j < n; ++j) {
Dfs(0, j);
Dfs(n - 1, j);
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
cout << gg[i][j] << " \n"[j == n - 1];
}
}
return 0;
} 
全部评论
(36) 回帖