标签：2024.12 cout vis int nx ny 周一 define
2024.12.9 周一
问是否可以用给定的n^2个数构造出已定n*n的矩阵。
给定2行n列数组，从(1,1)走到(2,n)，只能向右/下走。你可以任意交换2列，问经过元素的和的最大值。
你有任意张面值为1,3,6,10,15的纸币。给定n，问凑出n元需要最小的纸币张数。
给定字符迷宫，问作为起点无法出迷宫的位置数。
------------------------独自思考分割线------------------------
-
被Q3卡了。一个半小时结束，Q1+Q2半小时，Q3半小时，速度还可以。深搜比广搜确实好写...
A1. 2点
1.数据结构map维护个数，一一判断。
2.另解：生成矩阵判等。
A2. 2点
1.2行注定有一个拐点。任意交换列代表可以任意排列。
2.分析本质：任意选择n-1个max(a[i][0],a[i][1])，加上拐点的另一半，显然未被选择的最大值最优。
1. 好题：思维+暴力 / dp+贪心
A4. 2点
1.反向搜索必出迷宫的块。
2.搜索剩下块：对每个块数量>1就可以做到无法出迷宫。
------------------------代码分割线------------------------
A1.
#include <bits/stdc++.h>
#define int long long //
#define endl '\n' // 交互/调试 关
using namespace std;
#define bug(BUG) cout << "bug:# " << (BUG) << endl
#define bug2(BUG1, BUG2) cout << "bug:# " << (BUG1) << " " << (BUG2) << endl
#define bug3(BUG1, BUG2, BUG3) cout << "bug:# " << (BUG1) << ' ' << (BUG2) << ' ' << (BUG3) << endl
void _();
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cout << fixed << setprecision(6);
int T = 1;
cin >> T;
while (T--)
_();
return 0;
}
void _()
{
int n, c, d;
cin >> n >> c >> d;
map<int, int> has;
for (int i = 0; i < n * n; i++)
{
int x;
cin >> x;
has[x]++;
}
int minw = (*has.begin()).first;
int ans = 1;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
{
if (!has[minw + i * c + j * d])
ans = 0;
else
has[minw + i * c + j * d]--;
}
cout << (ans ? "YES" : "NO") << endl;
}
A2.
#include <bits/stdc++.h>
#define int long long //
#define endl '\n' // 交互/调试 关
using namespace std;
#define bug(BUG) cout << "bug:# " << (BUG) << endl
#define bug2(BUG1, BUG2) cout << "bug:# " << (BUG1) << " " << (BUG2) << endl
#define bug3(BUG1, BUG2, BUG3) cout << "bug:# " << (BUG1) << ' ' << (BUG2) << ' ' << (BUG3) << endl
void _();
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cout << fixed << setprecision(6);
int T = 1;
cin >> T;
while (T--)
_();
return 0;
}
void _()
{
int m;
cin >> m;
vector<pair<int, int>> vec(m);
for (auto &[x, y] : vec)
cin >> x;
for (auto &[x, y] : vec)
cin >> y;
int sum = 0, maxw = -1e12;
for (auto [x, y] : vec)
{
maxw = max(maxw, min(x, y));
sum += max(x, y);
}
cout << sum + maxw << endl;
}
A3.
#include <bits/stdc++.h>
#define int long long //
#define endl '\n' // 交互/调试 关
using namespace std;
#define bug(BUG) cout << "bug:# " << (BUG) << endl
#define bug2(BUG1, BUG2) cout << "bug:# " << (BUG1) << " " << (BUG2) << endl
#define bug3(BUG1, BUG2, BUG3) cout << "bug:# " << (BUG1) << ' ' << (BUG2) << ' ' << (BUG3) << endl
void _();
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cout << fixed << setprecision(6);
int T = 1;
cin >> T;
while (T--)
_();
return 0;
}
void _()
{
int n;
cin >> n;
int res = 1e12;
vector<int> vec{15, 10, 6, 3, 1};
int cnt[] = {0, 2, 4, 1, 2};
for (int i = 0; i <= 2; i++)
for (int j = 0; j <= 4; j++)
for (int k = 0; k <= 1; k++)
for (int h = 0; h <= 2; h++)
{
int x = n - (i * 10 + j * 6 + k * 3 + h);
if (x >= 0 && x % 15 == 0)
res = min(res, i + j + k + h + x / 15);
}
cout << res << endl;
}
// void _()
// {
// int n;
// cin >> n;
// int res = 1e12;
// int a[] = {1, 3, 6, 10, 15}, vis[5] = {};
// vector<int> vec{15, 10, 6, 3, 1};
// int vnt = 0;
// auto get = [&]()
// {
// vnt++;
// int t = 0, tn = n;
// for (auto v : vec)
// {
// t += tn / v;
// tn %= v;
// }
// res = min(res, t);
// for (auto v : vec)
// cout << v << ' ';
// cout << endl;
// bug(t);
// };
// function<void(int)> dfs = [&](int k)
// {
// if (k == 5)
// {
// get();
// return;
// }
// for (int i = 0; i < 5; i++)
// if (!vis[i])
// {
// vis[i] = 1;
// vec[k] = a[i];
// dfs(k + 1);
// vis[i] = 0;
// }
// };
// dfs(0);
// cout << res << endl;
// // bug(vnt);
// }
A4.
#include <bits/stdc++.h>
#define int long long //
#define endl '\n' // 交互/调试 关
using namespace std;
#define bug(BUG) cout << "bug:# " << (BUG) << endl
#define bug2(BUG1, BUG2) cout << "bug:# " << (BUG1) << " " << (BUG2) << endl
#define bug3(BUG1, BUG2, BUG3) cout << "bug:# " << (BUG1) << ' ' << (BUG2) << ' ' << (BUG3) << endl
void _();
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cout << fixed << setprecision(6);
int T = 1;
cin >> T;
while (T--)
_();
return 0;
}
void _()
{
int n, m;
cin >> n >> m;
vector<string> s(n + 2);
for (int i = 1; i <= n; i++)
{
cin >> s[i];
s[i] = " " + s[i] + " ";
}
vector<vector<int>> vis(n + 2, vector<int>(m + 2));
queue<pair<int, int>> q;
vis[0][0] = 1;
int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};
q.push({0, 0});
while (q.size())
{
auto [x, y] = q.front();
// bug2(x, y);
q.pop();
for (int i = 0; i < 4; i++)
{
int nx = x + dx[i], ny = y + dy[i];
if (nx < 0 || nx > n + 1 || ny < 0 || ny > m + 1 || vis[nx][ny])
continue;
if (nx == 0 || nx == n + 1 || ny == 0 || ny == m + 1)
{
q.push({nx, ny});
// bug2(nx, ny);
vis[nx][ny] = 1;
}
else
{
if (i == 0)
{
if (s[x + 1][y] - 'U')
continue;
}
else if (i == 1)
{
if (s[x - 1][y] - 'D')
continue;
}
else if (i == 2)
{
if (s[x][y + 1] - 'L')
continue;
}
else if (s[x][y - 1] - 'R')
continue;
// bug(s[nx][ny]);
q.push({nx, ny});
vis[nx][ny] = 1;
}
}
}
int res = 0, cnt = 0;
function<void(int, int)> dfs = [&](int i, int j)
{
if (vis[i][j])
return;
vis[i][j] = 1;
cnt++;
for (int k = 0; k < 4; k++)
dfs(i + dx[k], j + dy[k]);
};
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
if (!vis[i][j])
{
cnt = 0;
// bug2(i, j);
dfs(i, j);
res += cnt == 1 ? 0 : cnt;
}
cout << res << endl;
}
标签：2024.12,
cout,
vis,
int,
nx,
ny,
周一,
define
From： https://www.cnblogs.com/jkkk/p/18596957