YottaByte_7

4049

emanual20
noicracker
syt

_whiz
Xiaodingdang

DavisElppa
hello_world111
Amazing_
Lims
yxc
william555
acwing_7639
Sign
qing_lin
fun

YottaByte_7
2个月前
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 32, M = N * 1e4;
int a[N], n, x, s;
int dp[M];

int main()
{
cin >> n >> x;
for (int i = 1; i <= n; i ++ ) {
cin >> a[i];
s += a[i];
}

for (int i = 1; i <= n; i ++ )
for (int j = s - x; j >= a[i]; j -- )
dp[j] = max(dp[j], dp[j - a[i]] + a[i]);

cout << s - dp[s - x] << endl;
}


YottaByte_7
2个月前
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 22;
int a[N], r[N];

int main()
{
int n, m;
cin >> n >> m;
a[0] = 1;
for (int i = 1; i <= n; i ++ )
{
cin >> a[i];
a[i] *= a[i - 1];
}

for (int i = n; i >= 1; i -- ) {
r[i] = m / a[i - 1];
m %= a[i - 1];
}

for (int i = 1; i <= n; i ++ ) {
cout << r[i] << " ";
}
}


YottaByte_7
3个月前
#include <iostream>
#include <algorithm>
#include <cstring>

#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 1010;
int n, m, dist[N][N], dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
char a[N][N];
PII q[N * N];

void bfs()
{
int hh = 0, tt = -1;
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
if (a[i][j] == '1')
{
dist[i][j] = 0;
q[++ tt] = {i, j};
}

while (hh <= tt)
{
auto t = q[hh ++ ];
for (int i = 0; i < 4; i ++ )
{
int xx = t.x + dx[i], yy = t.y + dy[i];
if (xx < 1 || xx > n || yy < 1 || yy > m || !dist[xx][yy] || (dist[xx][yy] != -1 && dist[xx][yy] <= dist[t.x][t.y] + 1)) continue;

q[++ tt] = {xx, yy};
dist[xx][yy] = dist[t.x][t.y] + 1;
}
}
}

int main()
{
cin >> n >> m;
memset(dist, -1, sizeof dist);
for (int i = 1; i <= n; i ++ )
cin >> a[i] + 1;

bfs();

for (int i = 1; i <= n; i ++ ) {
for (int j = 1; j <= m; j ++ )
cout << dist[i][j] << " ";
cout << "\n";
}
}


YottaByte_7
3个月前
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
int n, k;
const int N = 1e5 + 5;
int q[N * 3];
int dist[N];
int d[3] = {-1, 1, 0};

int bfs(int s)
{
int hh = 0, tt = 0;
q[0] = s;
memset(dist, -1, sizeof dist);
dist[s] = 0;
while (hh <= tt)
{
int t = q[hh ++ ];
for (int i  = 0; i < 3; i ++ )
{
int nxt = t + d[i];
if (!d[i]) nxt <<= 1;
if (nxt == k) return dist[t] + 1;
if (nxt > N || nxt < -N || dist[nxt] != -1) continue;

q[++ tt] = nxt;
dist[nxt] = dist[t] + 1;
}
}
}

int main()
{
cin >> n >> k;
if (n == k) cout << 0 << endl;
else cout << bfs(n) << endl;
}


YottaByte_7
3个月前
//这个题意感觉不太清楚，说了和马一样的规则，但是没有马的“拌脚”。。
#include <iostream>
#include <algorithm>
#include <cstring>

#define x first
#define y second

using namespace std;
typedef pair<int, int> PII;

const int N = 155;
int n, m, dx[8] = {-1, -1, -2, -2, 1, 1, 2, 2}, dy[8] = {2, -2, 1, -1, 2, -2, 1, -1};
char a[N][N];
PII q[N * N];
int layer[N][N];
PII st = {-1, -1}, ed = {-1, -1};

void bfs(int sx, int sy)
{
int cnt = 0;
q[0] = {sx, sy};
int hh = 0, tt = 0;
memset(layer, -1, sizeof layer);
layer[sx][sy] = 0;
while (hh <= tt)
{
auto t = q[hh ++ ];
for (int i = 0; i < 8; i ++ )
{
int _x = t.x + dx[i], _y = t.y + dy[i];
// int mid_x = _x + (dx[i] >> 1), mid_y = t.y + (dy[i] >> 1);
if (_x < 1 || _x > n || _y < 1 || _y > m || layer[_x][_y] != -1 || a[_x][_y] == '*') continue;
q[++ tt] = {_x, _y};
layer[_x][_y] = layer[t.x][t.y] + 1;
if (_x == ed.x && _y == ed.y) return;
}
}
}

int main()
{
cin >> m >> n;
for (int i = 1; i <= n; i ++ ) {
cin >> a[i] + 1;
for (int j = 1; j <= m; j ++ )
if (a[i][j] == 'K')
st = {i, j};
else if (a[i][j] == 'H')
ed = {i, j};
}

bfs(st.x, st.y);
cout << layer[ed.x][ed.y] << endl;
// for (int i = 1; i <= n; i ++ ) {
//     for (int j = 1; j <= m; j ++ ) {
//         cout << layer[i][j] << " ";
//     }
//     cout << endl;
// }
return 0;
}


YottaByte_7
3个月前
#include <iostream>
#include <algorithm>
#include <cstring>

#define x first
#define y second

using namespace std;
typedef pair<int, int> PII;
const int N = 1010;
int n, a[N][N], dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
PII q[N * N], pre[N][N];

void bfs(int sx, int sy)
{
int hh = 0, tt = 0;
q[0] = {sx, sy};
memset(pre, -1, sizeof pre);
pre[sx][sy] = {0, 0};
while (hh <= tt)
{
auto t = q[hh ++ ];
for (int i = 0; i < 4; i ++ )
{
int x = t.x + dx[i], y = t.y + dy[i];
if (x >= n || x < 0 || y >= n || y < 0 || pre[x][y].x != -1 || a[x][y]) continue;

q[++ tt] = {x, y};
pre[x][y] = {t.x, t.y};
}
}
}

int main()
{
cin >> n;
for (int i = 0; i < n; i ++ )
for (int j = 0; j < n; j ++ )
cin >> a[i][j];

bfs(n - 1, n - 1);

PII now(0, 0);

while (true) {
cout << now.x << " " << now.y << endl;
if (now.x == n - 1 && now.y == n - 1) break;
now = pre[now.x][now.y];
}

return 0;
}


YottaByte_7
3个月前
// 调了半天的搜索......
#include <iostream>
#include <algorithm>
#include <cstring>
#define x first
#define y second

using namespace std;
typedef pair<int, int> PII;
const int N = 1010;
int a[N][N], n;
PII q[N * N];
bool st[N][N];

int bfs(int sx, int sy)
{
int hh = 0, tt = 0;
q[0] = {sx, sy};
st[sx][sy] = true;
int flag = 0;
while (hh <= tt)
{
auto t = q[hh ++];

for (int i = t.x - 1; i <= t.x + 1; i ++ )
for (int j = t.y - 1; j <= t.y + 1; j ++ )
{
if (i == t.x && j == t.y) continue;
if (i < 1 || i > n || j < 1 || j > n) continue;
if (a[i][j] != a[t.x][t.y]) {
if (!flag)
flag = a[t.x][t.y] > a[i][j] ? 1 : -1;
else if (flag == -2) continue;
else if (flag * (a[t.x][t.y] - a[i][j]) < 0) flag = -2;
}
else if (!st[i][j]) {
q[++ tt] = {i, j};
st[i][j] = true;
}
}
}
if (tt == n * n - 1 && !flag) flag = 2;
if (flag == -2) flag = 0;
return flag;
}

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

int top = 0, bottom = 0, cnt = 0;
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
if (!st[i][j])
{
cnt = bfs(i, j);
// cout << i << ", " << j << ", val: " << cnt << endl;
if (cnt == 1)
top ++;
else if (cnt == 2) {
top ++;
bottom ++;
}
else if (cnt < 0) bottom ++;
}

cout << top << " " << bottom << endl;
}


YottaByte_7
3个月前
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
#define x first
#define y second

typedef pair <int, int> PII;
const int N = 55;
int m, n, a[N][N];
PII q[N * N];
bool st[N][N];
int dx[4] = {0, -1, 0, 1}, dy[4] = {-1, 0, 1, 0};

int bfs(int sx, int sy) {
int hh = 0, tt = 0;
q[0] = {sx, sy};
st[sx][sy] = true;
while (hh <= tt) {
auto t = q[hh ++ ];
for (int i = 0; i < 4; i ++ )
{
int x = t.x + dx[i], y = t.y + dy[i];
if (st[x][y] || x < 1 || x > n || y < 1 || y > m) continue;
if (a[t.x][t.y] >> i & 1) continue;

q[++ tt] = {x, y};
st[x][y] = true;
}
}
return tt + 1;
}

int main()
{
cin >> n >> m;
int cnt = 0;
int ans = 0;
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
cin >> a[i][j];
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
if (!st[i][j]) {
ans = max(ans, bfs(i, j));
cnt ++;
}
cout << cnt << "\n" << ans << endl;
}


YottaByte_7
3个月前
#include <iostream>
#include <algorithm>
#include <cstring>

#define x first
#define y second

using namespace std;

typedef pair <int, int> PII;
const int N = 1010;
char a[N][N];
PII q[N * N];
int n, m;
bool st[N][N];

void bfs(int xx, int yy)
{
int hh = 0, tt = -1;
q[0] = {xx, yy};
st[xx][yy] = true;
tt ++;
while (hh <= tt) {
auto t = q[hh ++];
for (int i = t.x - 1; i <= t.x + 1; i ++ )
for (int j = t.y - 1; j <= t.y + 1; j ++ )
{
if (i == xx && yy == j) continue;
if (st[i][j] || i < 1 || i > n || j < 1 || j > m) continue;
if (a[i][j] == '.') continue;

q[++ tt] = {i, j};
st[i][j] = true;
}
}
}

int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++ )
cin >> a[i] + 1;

int cnt = 0;
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
{
if (a[i][j] == 'W' && !st[i][j]) {
bfs(i, j);
cnt ++;
}
}

cout << cnt << endl;
}


YottaByte_7
3个月前
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
const int N = 110, M = 25e3 + 5;
int T, n, a[N], f[M];

int main()
{
cin >> T;
while (T -- ) {
cin >> n;
for (int i = 1; i <= n; i ++ ) {
cin >> a[i];
}

sort(a + 1, a + n + 1);

int maxv = a[n];

int num = 0;
memset(f, 0, sizeof f);
f[0] = 1;
for (int i = 1; i <= n; i ++ ) {
if (!f[a[i]]) num ++;
for (int j = a[i]; j <= maxv; j ++ ) {
f[j] |= f[j - a[i]];
}
}

cout << num << endl;
}
}