7-7 与零交换
给定排列\(p:0,1,2...n-1\),每次操作你只能将一个数字和\(0\)进行交换，然后将初始排列升序排列，请你找出最少的与\(0\)交换的次数
题解：思维 + 环
- 样例一： \(4,0,1,2,3\)
- 我们观察位置 \(0,1,2,3,4\) 发现形成了\(0->1->2->3->4\)的环，那么交换次数就是环的长度-1,即\(n-1\)
- 那么如果一个环中不存在\(0\)，我们实际上可以先将\(0\)交换进去，答案贡献加1，然后现在环的长度+1，所以最后该环的交换次数为\(n+1\)
#include <bits/stdc++.h>
#define Zeoy std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0)
#define debug(x) cerr << #x << '=' << x << endl
#define all(x) (x).begin(), (x).end()
#define rson id << 1 | 1
#define lson id << 1
#define int long long
#define mpk make_pair
#define endl '\n'
using namespace std;
typedef unsigned long long ULL;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-9;
const int N = 2e5 + 10, M = 4e5 + 10;
int n;
int a[N];
int vis[N];
int pos[N];
void solve()
{
cin >> n;
for (int i = 0; i < n; ++i)
{
cin >> a[i];
pos[a[i]] = i;
}
int ans = 0;
for (int i = 0; i < n; ++i)
{
if (!vis[a[i]])
{
map<int, int> mp;
int p = a[i];
while (!vis[p])
{
vis[p] = 1;
mp[p]++;
p = pos[p];
}
if (mp.count(0) && mp.size() > 1)
ans += mp.size() - 1;
else if (mp.size() > 1)
ans += mp.size() + 1;
}
}
cout << ans << endl;
}
signed main(void)
{
Zeoy;
int T = 1;
// cin >> T;
while (T--)
{
solve();
}
return 0;
}
7-8 出栈序列的合法性
给定一个最大容量为 M 的堆栈，将 N 个数字按 1, 2, 3, ..., N 的顺序入栈，允许按任何顺序出栈 ,给出\(q\)次询问，每次回答给定的出栈序列是否合法
题解：模拟栈 \(O(n)\)
首先出栈的顺序存在三种情况：
- 一入栈就出栈，例如：1 2 3
- 入栈几次后再出栈，例如：3 2 1
- 前面两种情况的复合情况
对于本题我们只需模拟栈即可，因为一个数字如果要出栈，说明这个数字之前的所有数字都已经入栈过一次了，利用该性质我们利用栈模拟该过程即可；我们发现每个数字只会被入栈和出栈依次，所以查询一次的复杂度为\(O(n)\)
#include <bits/stdc++.h>
#define Zeoy std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0)
#define debug(x) cerr << #x << '=' << x << endl
#define all(x) (x).begin(), (x).end()
#define rson id << 1 | 1
#define lson id << 1
#define int long long
#define mpk make_pair
#define endl '\n'
using namespace std;
typedef unsigned long long ULL;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-9;
const int N = 2e5 + 10, M = 4e5 + 10;
int m, n, q;
int stk[N], tt;
int a[N];
void solve()
{
cin >> m >> n >> q;
while (q--)
{
int flag = true;
tt = 0;
for (int i = 1; i <= n; ++i)
cin >> a[i];
int pre = 1;
for (int i = 1; i <= n; ++i)
{
if (tt == 0)
{
for (int j = 1; j <= a[i]; ++j)
stk[++tt] = j;
if (tt > m)
{
flag = false;
break;
}
pre = a[i];
tt--;
}
else if (tt && pre < a[i])
{
for (int j = pre + 1; j <= a[i]; ++j)
stk[++tt] = j;
if (tt > m)
{
flag = false;
break;
}
pre = a[i];
tt--;
}
else if (tt && pre > a[i])
{
if (stk[tt] != a[i])
{
flag = false;
break;
}
tt--;
}
}
if (flag)
cout << "Yes" << endl;
else
cout << "No" << endl;
}
}
signed main(void)
{
Zeoy;
int T = 1;
// cin >> T;
while (T--)
{
solve();
}
return 0;
}
7-12 肿瘤诊断
给定\(L\)层切片，每层切片大小为\(N×M\)，体积限制为\(T\)，每层切片只由0和1组成，让你数所有切片中形成的连通块中1的数量，如果该连通块中1的数量少于\(T\)，则不计入答案，六个面中只要有一个面存在1就能说明两个1连通
题解：三维\(BFS\)
三维\(BFS\)板子题，当时没理解题意，没看出来是三维，裂开
#include <bits/stdc++.h>
#define Zeoy std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0)
#define debug(x) cerr << #x << '=' << x << endl
#define all(x) (x).begin(), (x).end()
#define rson id << 1 | 1
#define lson id << 1
#define int long long
#define mpk make_pair
#define endl '\n'
using namespace std;
typedef unsigned long long ULL;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-9;
const int N = 2e5 + 10, M = 4e5 + 10;
int n, m, L, limit;
int g[65][1300][135];
bool vis[65][1300][135];
int dir[6][3] = {{0, 0, -1}, {0, 0, 1}, {0, -1, 0}, {0, 1, 0}, {1, 0, 0}, {-1, 0, 0}};
int ans;
struct node
{
int k, x, y;
};
void bfs(int k, int x, int y)
{
queue<node> q;
q.push({k, x, y});
vis[k][x][y] = true;
int res = 0;
while (q.size())
{
node u = q.front();
q.pop();
res++;
for (int i = 0; i < 6; ++i)
{
int nk = u.k + dir[i][0];
int nx = u.x + dir[i][1];
int ny = u.y + dir[i][2];
if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && nk >= 1 && nk <= L && !vis[nk][nx][ny] && g[nk][nx][ny] == 1)
{
vis[nk][nx][ny] = true;
q.push({nk, nx, ny});
}
}
}
if (res >= limit)
ans += res;
}
void solve()
{
cin >> n >> m >> L >> limit;
for (int k = 1; k <= L; ++k)
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
cin >> g[k][i][j];
for (int k = 1; k <= L; ++k)
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
{
if (!vis[k][i][j] && g[k][i][j] == 1)
bfs(k, i, j);
}
cout << ans << endl;
}
signed main(void)
{
Zeoy;
int T = 1;
// cin >> T;
while (T--)
{
solve();
}
return 0;
}
7-13 凑零钱
一个人手里有\(10^4\)枚硬币，每种硬币只能用\(1\)次，需要请你帮她盘算一下，是否可能精确凑出要付的款额\(m\)，输出字典序最小的方案
题解：贪心 + 变种\(01\)背包求方案 / \(DFS\)回溯
方法1：\(dp\)
- 状态表示：\(f[i]\):精准凑出金额\(i\)的钱最多需要几个硬币
- 状态属性：\(MAX\)
- 状态转移：转移的前提是前一个状态必须是合法的（也就是说前一个状态代表的金额能被硬币凑出）\(f[j] = max(f[j],f[j-a[i]]+1)\ \&\& \ (f[j-a[i]]>0\ ||\ j-a[i]==0)\)
- 状态初始：\(f[i]=0\)
- 答案呈现：如果\(f[m]>0\)，代表金额\(m\)能被精准凑出，我们利用\(vector\)记录方案即可
- 如何求字典序最小的方案：贪心，将硬币升序排列即可，这样记录的方案一定是字典序最小的
方法2：\(dfs\)搜索
贪心升序排序后\(dfs\)爆搜即可
//dp
#include <bits/stdc++.h>
#define Zeoy std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0)
#define debug(x) cerr << #x << '=' << x << endl
#define all(x) (x).begin(), (x).end()
#define int long long
#define mpk make_pair
#define endl '\n'
using namespace std;
typedef unsigned long long ULL;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-9;
const int N = 2e5 + 10, M = 4e5 + 10;
int n, m;
int a[N];
int f[N];
vector<int> pre[N];
void solve()
{
cin >> n >> m;
for (int i = 1; i <= n; ++i)
cin >> a[i];
sort(a + 1, a + n + 1);
for (int i = 1; i <= n; ++i)
{
for (int j = m; j >= a[i]; --j)
{
if (f[j] <= f[j - a[i]] + 1 && (f[j - a[i]] || j - a[i] == 0))
{
f[j] = f[j - a[i]] + 1;
pre[j] = pre[j - a[i]];
pre[j].push_back(a[i]);
}
}
}
if (f[m])
{
for (int i = 0; i < pre[m].size(); ++i)
cout << pre[m][i] << "\n "[i < pre[m].size() - 1];
}
else
cout << "No Solution" << endl;
}
signed main(void)
{
Zeoy;
int T = 1;
// cin >> T;
while (T--)
{
solve();
}
return 0;
}
//dfs回溯
#include <bits/stdc++.h>
#define Zeoy std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0)
#define debug(x) cerr << #x << '=' << x << endl
#define all(x) (x).begin(), (x).end()
#define rson id << 1 | 1
#define lson id << 1
#define int long long
#define mpk make_pair
#define endl '\n'
using namespace std;
typedef unsigned long long ULL;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-9;
const int N = 2e5 + 10, M = 4e5 + 10;
int n, m;
int a[N];
bool vis[N];
vector<int> ans;
bool flag;
void dfs(int idx, int sum)
{
if (sum > m)
return;
if (sum == m)
{
flag = true;
for (int i = 0; i < ans.size(); ++i)
cout << ans[i] << "\n "[i < ans.size() - 1];
return;
}
for (int i = idx; i <= n; ++i)
{
if (!vis[i])
{
vis[i] = true;
ans.push_back(a[i]);
dfs(i + 1, sum + a[i]);
ans.pop_back();
vis[i] = false;
if (flag)
return;
}
}
}
void solve()
{
cin >> n >> m;
int sum = 0;
for (int i = 1; i <= n; ++i)
cin >> a[i], sum += a[i];
if (sum < m)
{
cout << "No Solution" << endl;
return;
}
sort(a + 1, a + n + 1);
dfs(1, 0);
if (!flag)
cout << "No Solution" << endl;
}
signed main(void)
{
Zeoy;
int T = 1;
// cin >> T;
while (T--)
{
solve();
}
return 0;
}