Problem A 物资调度
题目链接:http://nyoj.top/problem/1249
题意:求方案总数，有n个数，每个数的个数已知，求能拼凑出m的方案数。
思路:类似与01背包，每一种状态都是由上一种状态继承来的，dp数组存贮能够组合当前数的总个数，则状态转移方程为：dp[j]+=dp[j-a[i]].另外一种方法就是用DFS搜。
DP:
#include <bits/stdc++.h>
using namespace std;
int val[105], dp[1005];
int main() {
int t, n, m;
scanf("%d", &t);
while (t--) {
memset(dp, 0, sizeof(dp));
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++)
scanf("%d", &val[i]);
dp[0] = 1;
for (int i = 0; i < n; i++) {
for (int j = m; j >= val[i]; j--)
dp[j] += dp[j - val[i]];
}
printf("%d\n", dp[m]);
}
return 0;
} DFS:
#include <bits/stdc++.h>
using namespace std;
int sum, ans, n, m, v[105], vis[105];
void DFS(int cnt, int k) {
if (cnt >= m) {
if (cnt == m)
ans++;
return ;
}
for (int i = k; i < n; i++) {
if (!vis[i]) {
vis[i] = 1;
DFS(cnt + v[i], i + 1);
vis[i] = 0;
}
}
}
int main() {
int t;
scanf("%d", &t);
while (t--) {
ans = 0;
memset(vis, 0, sizeof(vis));
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++) {
scanf("%d", &v[i]);
}
DFS(0, 0);
printf("%d\n", ans);
}
return 0;
} Problem B 海岛争霸
题目链接:http://nyoj.top/problem/1248
题意:求A到B所经过的航线危险程度的最小值。
思路:最短路变形题，稍微修改一下状态转移方程就可以了。最短路是求和，这题是取最大。这道题其实也可以用并查集做，先把权值从小到大排一下序，然后就开始加边，直到A与B能连通。
最短路:
#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
struct edge {
int u, v, w;
} e[1005];
int f[105], vis[105], dis[105], cnt = 0;
void Add(int u, int v, int w) {
e[++cnt] = (edge){f[u], v, w};
f[u] = cnt;
}
void Spfa(int s) {
queue <int> Q;
Q.push(s);
vis[s] = 1;
dis[s] = 0;
while (!Q.empty()) {
int u = Q.front();
Q.pop();
vis[u] = 0;
for (int i = f[u]; i; i = e[i].u) {
int v = e[i].v;
if (dis[v] > max(dis[u], e[i].w)) {
dis[v] = max(dis[u], e[i].w);
if (!vis[v]) {
Q.push(v);
vis[v] = 1;
}
}
}
}
}
int main() {
int n, m, u, v, w, q, A, B;
scanf("%d%d", &n, &m);
for (int i = 0; i < m; i++) {
scanf("%d%d%d", &u, &v, &w);
Add(u, v, w);
Add(v, u, w);
}
scanf("%d", &q);
while (q--) {
for (int i = 0; i <= n; i++)
dis[i] = inf;
memset(vis, 0, sizeof(vis));
scanf("%d%d", &A, &B);
Spfa(A);
if (dis[B] < inf)
printf("%d\n", dis[B]);
else printf("-1\n");
}
return 0;
} 并查集:
#include <bits/stdc++.h>
using namespace std;
struct edge {
int u, v, w;
}e[505];
int f[105];
bool cmp(edge a, edge b) {
return a.w < b.w;
}
int getf(int v) {
if (f[v] != v)
return f[v] = getf(f[v]);
return v;
}
bool merge(int u, int v) {
int t1 = getf(u);
int t2 = getf(v);
if (t1 != t2) {
f[t2] = t1;
return true;
}
return false;
}
int main() {
int a, b, n, m, q, ans, max_;
scanf("%d%d", &n, &m);
for (int i = 0; i < m; i++)
scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);
sort(e, e + m, cmp);
scanf("%d", &q);
while (q--) {
max_ = -1;
scanf("%d%d", &a, &b);
for (int i = 0; i <= n; i++)
f[i] = i;
for (int i = 0; i < m && !~max_; i++) {
if (merge(e[i].u, e[i].v))
ans = e[i].w;
if (getf(a) == getf(b))
max_ = ans;
}
printf("%d\n", max_);
}
return 0;
} Problem D 山区修路
题目链接:http://nyoj.top/problem/1251
题意:把一串序列变为一段连续不增，或者连续不减的最小花费。
思路:解题关键是要注意到不同的高度数并不多，无论使路段上升还是下降，总是可以调整到另一个已经存在的高度，使得结果最优。dp[i][j]代表第i个元素换为第j个值的前i个总的最小花费,可列出状态转移方程:
dp[i][j]=abs(a[i]-b[j])+ab,ab为转化为1~j间的最小花费;由于是单调不增或者单调不减，只需要升序降序下b数组就可以了.
#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
int n, a[505], b[505], dp[505][505];
int solve() {
int min_;
memset(dp, 0, sizeof(dp));
for (int i = 0; i < n; i++) {
min_ = inf;
for (int j = 0; j < n; j++) {
min_ = min(min_, dp[i][j]);
dp[i + 1][j] = abs(b[j] - a[i]) + min_;
}
}
min_ = inf;
for (int i = 0; i < n; i++)
min_ = min(min_, dp[n][i]);
return min_;
}
int main() {
int t, min_;
scanf("%d", &t);
while (t--) {
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
b[i] = a[i];
}
sort(b, b + n);
min_ = solve();
reverse(b, b + n);
min_ = min(min_, solve());
printf("%d\n", min_);
}
return 0;
} Problem E 世界之威
题目链接:http://nyoj.top/problem/1252
题意:n个武器，希望被卖出的武器中都至少有一种限制它的武器在手中，求最多能卖出去多少武器。
思路:图的遍历。首先是建图，如果u克制v，就连一条有向边uv。因为一种武器只能克制一种武器，所以图的结构可能出现链和环，还有可能多条边汇聚在一个点，不可能出现一个点引出多条边。首先我们找到所有入度为0的点，这些武器肯定是不能卖的，因为无法克制它们。如果u入度为0，我们就从u开始遍历，一定能得到一条链，这条链的贡献就是链长度/2。把所有入度为0的点处理完后，所有的链就处理完了，剩下的就是环。从每个环的任意一个点开始遍历，得到环的长度，这个环的贡献就是环长度/2。
#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
int deg[1000005], pre[1000005], vis[1000005];
int main() {
int t, n, x, ans;
scanf("%d", &t);
while (t--) {
ans = 0;
scanf("%d", &n);
memset(deg, 0, sizeof(deg));
memset(pre, 0, sizeof(pre));
memset(vis, 0, sizeof(vis));
for (int i = 1; i <= n; i++) {
scanf("%d", &x);
pre[i] = x;
deg[x]++;
}
for (int i = 1; i <= n; i++) {
if (!deg[i]) {
int cnt = 0, a = i;
while (a && !vis[a]) {
vis[a] = 1;
a = pre[a];
cnt++;
}
ans += cnt >> 1;
}
}
for (int i = 1; i <= n; i++) {
if (!vis[i]) {
int cnt = 0, a = i;
while (!vis[a]) {
vis[a] = 1;
a = pre[a];
cnt++;
}
ans += cnt >> 1;
}
}
printf("%d\n", ans);
}
return 0;
} Problem F Turing equation
题目链接:http://nyoj.top/problem/1253
题意:机器会将数倒着看，请判断输入的式子是否正确。
思路:把数翻一下，验证正确性就行了。
#include <bits/stdc++.h>
using namespace std;
char str[30];
int Judge(char *str, int l, int r) {
int ans = 0;
for (int i = l; i >= r; i--)
ans = ans * 10 + str[i] - '0';
return ans;
}
int main() {
int m, k, len, s[3];
while (~scanf("%s", str)) {
len = strlen(str);
if (len == 5 && str[0] + str[2] + str[4] == 3 * '0')
break;
k = m = 0;
for (int i = 0; i < len; i++) {
if (str[i] == '+' || str[i] == '=') {
s[k++] = Judge(str, i - 1, m);
m = i + 1;
}
}
s[k++] = Judge(str, len - 1, m);
if (s[0] + s[1] != s[2])
printf("FALSE\n");
else printf("TRUE\n");
}
return 0;
} Problem G Code the Tree
题目链接:http://nyoj.top/problem/1254
题意:给你一个字符串表示一棵无根树。让你求出该树的purfer序列。
思路:模拟题。根据给的串建树，左括号进入下一层，右括号返回上一层。建树完成后，维护每个点的度，依次删除度为1的最小的点和它唯一的边，输出边连接的另一个点。注意树根也可以作为叶子，只要点的度为1，它就是叶子。
#include <bits/stdc++.h>
using namespace std;
int p, n, deg[55], mp[55][55];
int Create(char str[]) {
int num, wei, ans;
while (str[p]) {
if (isdigit(str[p])) {
sscanf(str + p, "%d%n", &num, &wei);
p += wei;
n++;
}
else if (str[p] == '(') {
p++;
ans = Create(str);
deg[num]++;
deg[ans]++;
mp[ans][num] = mp[num][ans] = 1;
}
else if (str[p] == ')') {
p++;
return num;
}
else p++;
}
}
int main() {
char str[250];
while (~scanf("%[^\n]", str)) {
getchar();
n = 0, p = 1;
memset(mp, 0, sizeof(mp));
memset(deg, 0, sizeof(deg));
Create(str);
for (int i = 0; i < n - 2; i++) {
for (int j = 1; j < n; j++) {
if (deg[j] == 1) {
deg[j] = 0;
for (int k = 1; k <= n; k++) {
if (mp[j][k]) {
deg[k]--;
printf("%d ", k);
mp[j][k] = mp[k][j] = 0;
break;
}
}
break;
}
}
}
printf("%d\n", n);
}
return 0;
} Problem H Rectangles
题目链接:http://nyoj.top/problem/1255
题意:有n个矩阵，如果大的套小的看最多能套几层。大的矩阵必须有一边大于小矩阵的一边，例如2*2的矩阵可以套2*1的矩阵，但是不能套2*2的矩阵，注意矩形是可以旋转的。
思路:首先将矩阵长的边算作x边，小的算y边，然后将n个矩阵按照x的长短排序若x相同则按照y排序，然后跑一遍LIS就行了。
#include <bits/stdc++.h>
using namespace std;
struct edge {
int l, w;
}e[105];
int dp[105];
bool cmp(edge A, edge B) {
if (A.l != B.l)
return A.l < B.l;
return A.w < B.w;
}
bool Judge(int a, int b) {
if (e[a].l <= e[b].l && e[a].w < e[b].w)
return true;
if (e[a].l < e[b].l && e[a].w <= e[b].w)
return true;
return false;
}
int main() {
int t, n, max_, tempmax_;
scanf("%d", &t);
while (t--) {
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d%d", &e[i].l, &e[i].w);
if (e[i].l < e[i].w)
swap(e[i].l, e[i].w);
}
sort(e, e + n, cmp);
max_ = dp[0] = 1;
for (int i = 1; i < n; i++) {
tempmax_ = 0;
for (int j = 0; j < i; j++) {
if (Judge(j, i) && tempmax_ < dp[j])
tempmax_ = dp[j];
}
dp[i] = tempmax_ + 1;
max_ = max(max_, dp[i]);
}
printf("%d\n", max_);
}
return 0;
}
京公网安备 11010502036488号