117

#### C++ 代码

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int N = 1010;
int n, m;
int f[N][N];
int v[N], w[N];

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

for (int i = 1; i <= n; i++)
for (int j = 0; j <= m; j++) {
f[i][j] = f[i - 1][j];  // 第i件物品不选
if (j >= v[i]) {
f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);  // 第i件物品选
}
}

int res = 0;
for (int j = 0; j <= m; j++) res = max(res, f[n][j]);

cout << res << endl;
return 0;
}


#### C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 100010, M = 2 * N;

int n, m;
int element[M];  //元素
int ne[M];  // next指针
int idx;  // 游标
bool st[N];

int ans = N;

void add_edge(int a, int b) {
}

// 返回以u为根的子树大小
int dfs (int u) {
st[u] = true;
int sum = 1, res = 0;
for (int i = head[u]; i != -1; i = ne[i]) {
int j = element[i];
if (!st[j]) {
int s = dfs(j); // 当前子树大小
res = max(res, s);
sum += s;
}
}
res = max(res, n - sum);
ans = min(ans, res);

return sum;
}

int main() {
cin >> n;
for (int i = 0; i < n -1; i++) {
int a, b;
cin >> a >> b;
}
dfs(1);
cout << ans << endl;

return 0;
}


#### C++ 代码

#include <iostream>
#include <cstring>
using namespace std;

const int N = 100010, M = 2 * N;

int n, m;
int vertex[N], edge[M], redge[M], idx;
bool st[N];

int ans = N;

void add_edge(int a, int b) {
edge[idx] = b, redge[idx] = vertex[a], vertex[a] = idx++;
}

int dfs (int u) {
st[u] = true;
int sum = 1, res = 0;
for (int i = vertex[u]; i != -1; i = redge[i]) {
int j = edge[i];
if (!st[j]) {
int s = dfs(j);
res = max(res, s);
sum += s;
}
}
res = max(res, n - sum);
ans = min(ans, res);

return sum;
}

int main() {
cin >> n;
memset(vertex, -1, sizeof vertex);
for (int i = 0; i < n -1; i++) {
int a, b;
cin >> a >> b;
}
dfs(1);
cout << ans << endl;

return 0;
}


#### C++ 代码

#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
#include <unordered_map>

using namespace std;

int bfs(string start) {
string end = "12345678x";
queue<string> q;
unordered_map<string, int> d;

q.push(start);
d[start] = 0;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

while (q.size()) {
auto t = q.front();
q.pop();
int dis = d[t];
if (t == end) return dis;
int k = t.find('x');
int x = k / 3, y = k % 3;
for (int i = 0; i < 4; i++) {
int a = x + dx[i], b = y + dy[i];
if (a >= 0 && a < 3 && b >= 0 && b < 3) {
swap(t[k], t[a * 3 + b]);
if (!d.count(t)) {
d[t] = dis + 1;
q.push(t);
}
swap(t[k], t[a * 3 +b]); // 状态恢复
}
}
}
return -1;
}

int main() {
string start;

for (int i = 0; i < 9; i++) {
char c;
cin >> c;
start += c;
}

cout << bfs(start) << endl;

return 0;
}


### 题目描述

#### 样例

#include <iostream>
using namespace std;

double n, l, r, mid;
double cube(double x) { return x * x * x; }

int main() {
scanf("%f", &n);

l = -25, r = 25;
while (r - l >= 1e-8) {
mid = (l + r) / 2;
if (cube(mid) >= n) r = mid;
else l = mid;
}
printf("%lf\n", l);

return 0;
}