A、最小生成树
小 A 有一张 n 个点的带权无向图，这张无向图非常特别，首先第 i 个点有一个点权 ai，之后这张无向图是一张完全图，且边 (u,v) 的权值为 au+av
现在小 A 想找一个这张图的边权之和最小的生成树，需要你来帮帮他
题解：
每个点都和最小那个点连接形成的树即最小生成树
注意：使用长整形
AC代码：
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
const int maxn = 1e5 + 15;
ll a[maxn];
int main()
{
int n; cin >> n;
for (int i = 0; i < n; i++)
cin >> a[i];
sort(a, a + n);
ll ans = 0;
for (int i = 1; i < n; i++)
ans += a[0] + a[i];
cout << ans << endl;
return 0;
}
B、病毒感染
有一天clccle和rqy走在某个国家的街头上,机智的rqy却发现周围的行人不太对劲,他们嘴里念念有词,说着"sqn tql!",一边漫无目的的行走,clccle也发现了这一点,却惊讶的发觉这种奇怪的病毒会向周围的城市,最终会感染整个国家,因为网络已经崩溃,所以她们忘记了自己所在的城市,她们唯一知道的是这种病毒是从当前她们所在的城市开始传播的,并且这个国家的所有城市到这个城市的距离和最小（所有道路的距离都为1）,现在给定聪明的你一张整个国家的地图,请你帮rqy和clccle找到她们现在可能在这个国家的哪一个城市.
题解：
树的重心板子题
AC代码：
#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<vector>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
const int maxn = 1e5 + 15;
vector<int>G[maxn];
vector<int>ans[maxn];
int minn;
int d[maxn];
int n, m;
/*
树的重心求法：遍历所有点的子树的大小，然后重心存在的那个点就是最大子树最小的那个点
*/
void dfs(int u, int fa) {
d[u] = 1;
int maxx = 0;
for (int i = 0; i < G[u].size(); i++) {
int v = G[u][i];
if (v != fa) {
dfs(v, u);
d[u] += d[v];
maxx = max(maxx, d[v]);
}
}
maxx = max(maxx, n - d[u]);
if (maxx <= minn) {
minn = maxx;
ans[minn].push_back(u);
}
}
int main()
{
cin >> n >> m;
for (int i = 0; i < m; i++) {
int x, y; cin >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
minn = inf;
dfs(1, 0);
sort(ans[minn].begin(), ans[minn].end());
for (int i = 0; i < ans[minn].size(); i++)
cout << ans[minn][i] << " ";
return 0;
}
C、Shooping
你要买n件物品，其中有一些是凳子。
商场正在举行促销活动，如果购物车中有至少一个凳子，那么你可以半价购买这个购物车中最贵的一个物品。
你有m辆购物车，请最小化你的花费。
题解：
找出min(m,凳子数量)，然后对前k大的物品进行打折就好
AC代码：
#include<iostream>
#include<algorithm>
#include<stdio.h>
using namespace std;
#define ll long long
const int maxn = 1e3 + 15;
bool cmp(double a, double b) {
return a > b;
}
int main()
{
int t; cin >> t;
while (t--) {
double a[maxn];
int num = 0;
int n, m;
cin >> n >> m;
int x;
double ans = 0;
for (int i = 0; i < n; i++) {
cin >> a[i] >> x;
ans += a[i];
if (x == 1)
num++;
}
sort(a, a + n, cmp);
for (int i = 0; i < min(num, m); i++)
ans -= a[i] / 2;
printf("%.1lf\n", ans);
}
return 0;
}
D、铺地毯
为了准备一个独特的颁奖典礼，组织者在会场的一片矩形区域（可看做是平面直角坐标系的第一象限）铺上一些矩形地毯。一共有n张地毯，编号从1到n。现在将这些地毯按照编号从小到大的顺序平行于坐标轴先后铺设，后铺的地毯覆盖在前面已经铺好的地毯之上。地毯铺设完成后，组织者想知道覆盖地面某个点的最上面的那张地毯的编号。注意：在矩形地毯边界和四个顶点上的点也算被地毯覆盖。
题解：
将所有地毯按顺序依次铺上，然后倒序查找最上面的即可
AC代码：
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
const int maxn = 1e6 + 15;
struct node {
int a, b, g, k;
}a[maxn];
int main()
{
int n; cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i].a >> a[i].b >> a[i].g >> a[i].k;
int x, y; cin >> x >> y;
int is_ok = 0;
for (int i = n; i >= 1; i--) {
if (a[i].a > x || a[i].b > y)
continue;
else if (x <= a[i].a + a[i].g && x >= a[i].a && y >= a[i].b && y <= a[i].b + a[i].k) {
cout << i << endl;
is_ok = 1;
break;
}
}
if (is_ok == 0)
cout << -1 << endl;
return 0;
}
E、金币陷阱
最近，奶牛们热衷于把金币包在面粉里，然后把它们烤成馅饼。第i块馅饼中含有Ni(1<=Ni<=25)块金币，并且，这个数字被醒目地标记在馅饼表面。
奶牛们把所有烤好的馅饼在草地上排成了一个R行(1<=R<=100)C列(1<=C<=100)的矩阵。你现在站在坐标为(1,1)的馅饼边上，当然，你可以拿到那块馅饼里的所有金币。你必须从现在的位置，走到草地的另一边，在坐标为(R,C)的馅饼旁边停止走动。每做一次移动，你必须走到下一列的某块馅饼旁边，并且，行数的变动不能超过1（也就是说，如果现在你站在坐标为(r,c)的馅饼边上，下一步你可以走到坐标为(r-1,c+1),(r,c+1),或者(r+1,c+1)的馅饼旁边）。当你从一块馅饼边经过，你就可以拿走馅饼里所有的金币。当然啦，你一定不会愿意因半路离开草地而失去唾手可得的金币，但，最终你一定得停在坐标为(R,C)的馅饼旁边。
现在，你拿到了一张标记着馅饼矩阵中，每一块馅饼含金币数量的表格。那么，按照规则，你最多可以拿到多少金币呢？
题解：
大佬们拿dp写的，卑微的我看不懂，只好裸dfs了
搜索代码：
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
const int N = 1e2 + 5;
#define inf 0x3f3f3f3f
int a[N][N];
int vis[N][N];
int R, C;
int dir[3][2] = { {0, 1}, {-1, 1}, {1, 1} };
int dfs(int x, int y) {
if (x == R && y == C)
return 0;
if (vis[x][y])
return vis[x][y];
vis[x][y] = -inf;
for (int i = 0; i < 3; i++) {
int xx = x + dir[i][0];
int yy = y + dir[i][1];
if (xx >= 1 && xx <= R && yy >= 1 && yy <= C)
vis[x][y] = max(vis[x][y], dfs(xx, yy) + a[xx][yy]);
}
return vis[x][y];
}
int main()
{
cin >> R >> C;
for (int i = 1; i <= R; i++)
for (int j = 1; j <= C; j++)
cin >> a[i][j];
int ans = dfs(1, 1) + a[1][1];
cout << ans << endl;
return 0;
}
dp代码：
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
#define ll long long
const int N = 1e2 + 5;
#define inf 0x3f3f3f3f
int a[N][N], dp[N][N];
int R, C;
int main()
{
cin >> R >> C;
for (int i = 1; i <= R; i++)
for (int j = 1; j <= C; j++)
cin >> a[i][j];
dp[1][1] = a[1][1];
for (int i = 2; i <= C; i++) {
for (int j = 1; j <= R; j++) {
if (dp[j][i - 1] != 0)
dp[j][i] = max(dp[j][i], dp[j][i - 1] + a[j][i]);
if (dp[j + 1][i - 1] != 0)
dp[j][i] = max(dp[j][i], dp[j + 1][i - 1] + a[j][i]);
if (dp[j - 1][i - 1] != 0) {
dp[j][i] = max(dp[j][i], dp[j - 1][i - 1] + a[j][i]);
}
}
}
cout << dp[R][C] << endl;
return 0;
}
京公网安备 11010502036488号