L3-001 凑零钱 (30 分)
01背包问题记录路径
#include<bits/stdc++.h>
using namespace std;
const int N = 1e4+10;
int n, m;
int a[N], dp[110], op[N][110];
int main()
{
cin >> n >> m;
for (int i = 1;i <= n;i ++) cin >> a[i];
sort (a+1, a+n+1, greater<int> ()); // 从大到小排序算得的是最小字典序,从小到大排序算得的是最大字典序
for (int i = 1;i <= n;i ++)
for (int j = m;j >= a[i];j --) {
if (dp[j] <= dp[j-a[i]] + a[i]) { // <=
dp[j] = dp[j-a[i]] + a[i];
op[i][j] = 1;
}
}
if (dp[m] != m) return puts ("No Solution"), 0;
int j = m, i = n, flag = 0;
while (i >= 1 && j >= 0) {
if (op[i][j]) {
if (flag) cout << ' ';
cout << a[i];
flag = 1;
j -= a[i];
}
i --;
}
return 0;
}
L3-003 社交集群 (30 分)
并查集,两个人只要存在至少一个相同,那么就算一类。
#include<bits/stdc++.h>
using namespace std;
const int N = 1e3+10;
int n, k, a, b, ans;
int st[N], cnt[N], fa[N], peo[N];
vector <int> fas;
int find (int x) {
return fa[x] == x ? fa[x] : fa[x] = find (fa[x]);
}
void join (int x, int y) {
int rx = find (x), ry = find (y);
if (rx!=ry) fa[rx] = ry;
}
bool cmp (int a, int b) {
return cnt[a] > cnt[b];
}
int main()
{
cin >> n;
for (int i = 0;i <= 1000;i ++) fa[i] = i;
for (int i = 1;i <= n;i ++) {
cin >> k;
getchar ();
cin >> a;
peo[i] = a;
st[a] = 1;
while (-- k) {
cin >> b;
join (a, b);
st[b] = 1;
}
}
for (int i = 1;i <= n;i ++) {
int rt = find (peo[i]);
cnt[rt] ++;
}
for (int i = 1;i <= 1000;i ++)
if (st[i] && fa[i] == i)
ans ++, fas.push_back (fa[i]);;
sort (fas.begin(), fas.end(), cmp);
cout << ans << endl;
cout << cnt[fas[0]];
for (int i = 1;i < fas.size();i ++)
cout << ' ' << cnt[fas[i]];
return 0;
}
L3-004 肿瘤诊断 (30 分)
DFS会爆栈。
#include<bits/stdc++.h>
using namespace std;
const int L = 100, M = 1500, N = 150;
int n, m, l, t, ans, sum;
int a[L][M][N], st[L][M][N];
int dir[3][6] = {-1, 1, 0, 0, 0, 0,
0, 0, -1, 1, 0, 0,
0, 0, 0, 0, -1, 1};
struct node {
int z, x, y;
};
void bfs (int z, int x, int y) {
queue <node> q;
q.push ({z, x, y});
st[z][x][y] = 1;
while (q.size ()) {
node t = q.front ();
int z = t.z, x = t.x, y = t.y;
q.pop ();
sum ++;
// cout << z << ' ' << x << ' ' << y << endl;
for (int k = 0;k < 6;k ++) {
int tz = z + dir[0][k], tx = x + dir[1][k], ty = y + dir[2][k];
if (tz > l || tz < 1 || tx > m || tx < 1 || ty > n || ty < 1) continue;
if (st[tz][tx][ty] || !a[tz][tx][ty]) continue;
st[tz][tx][ty] = 1;
q.push ({tz, tx, ty});
}
}
}
int main()
{
cin >> m >> n >> l >> t;
for (int i = 1;i <= l;i ++)
for (int j = 1;j <= m;j ++)
for (int k = 1;k <= n;k ++)
cin >> a[i][j][k];
for (int i = 1;i <= l;i ++)
for (int j = 1;j <= m;j ++)
for (int k = 1;k <= n;k ++) {
sum = 0;
if (!st[i][j][k] && a[i][j][k]) bfs (i, j, k);
if (sum >= t) ans += sum;
}
cout << ans << endl;
return 0;
}
L3-005 垃圾箱分布 (30 分)
题解链接
L3-007 天梯地图 (30 分)
题解链接
L3-008 喊山 (30 分)
#include<bits/stdc++.h>
using namespace std;
const int N = 1e4+10;
int ans = 0;
int st[N], dis[N];
int e[N<<2], ne[N<<2], h[N], idx;
void add (int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
void bfs (int x) {
queue <int> q;
q.push (x);
dis[x] = 1;
st[x] = 1;
int mx_dis = 0;
while (q.size ()) {
int t = q.front ();
q.pop ();
if (dis[t] > mx_dis) {
mx_dis = dis[t];
ans = t;
} else if (dis[t] == mx_dis) {
ans = min (ans, t);
}
for (int i = h[t];~i;i = ne[i]) {
int j = e[i];
if (st[j]) continue;
st[j] = 1;
dis[j] = dis[t] + 1;
q.push (j);
}
}
}
int main()
{
memset (h, -1, sizeof h);
int n, m, k;
cin >> n >> m >> k;
while (m --) {
int a, b;
cin >> a >> b;
add (a, b);
add (b, a);
}
while (k --) {
int s;
cin >> s;
ans = N;
memset (st, 0, sizeof st);
bfs (s);
if (ans == s) cout << 0 << endl;
else cout << ans << endl;
}
return 0;
}
L3-010 是否完全二叉搜索树 (30 分)
#include<bits/stdc++.h>
using namespace std;
const int N = 100;
int n, x, cnt;
int tr[N];
int main()
{
cin >> n;
for (int i = 1;i <= n;i ++) {
cin >> x;
int p = 1;
while (tr[p] != 0) {
if (x > tr[p]) p = (p << 1);
else p = (p << 1 | 1);
}
tr[p] = x;
}
for (int i = 1; ;i ++) {
if (tr[i]) {
cnt ++;
if (cnt == 1) cout << tr[i];
else cout << ' ' << tr[i];
}
if (cnt == n) {
cout << endl;
if (i == n) puts ("YES");
else puts ("NO");
return 0;
}
}
return 0;
}
L3-013 非常弹的球 (30 分)
#include<bits/stdc++.h>
using namespace std;
const double g = 9.8, eps = 1e-8; // 精度不能只开到1e-4
double m, p, s = eps, sum, E = 1000;
int main()
{
cin >> m >> p;
while (fabs (s) >= eps) {
s = 200.0 * E / m / g;
sum += s;
E *= (1 - p / 100.0);
}
printf ("%.3lf", sum);
return 0;
}
L3-018 森森美图 (30 分)
题解链接
L3-020 至多删三个字符 (30 分)
题解链接