第五周的题感觉更偏向基础一点，没有太高的思维难度，锻炼的都是基础算法（其实还砍掉了一道大模拟）。
希望各位新生做的开心😋
A 夏虫
题意：
求前 m/l 大的值的和
解法：
把所有树枝按照营养从大到小排序，然后计算最多可以飞到几个树枝上，然后把营养最多的前几个树枝的营养加起来即为答案。
#include <stdio.h>
int a[1005];
int main()
{
int n, m, l;
scanf("%d%d%d", &n, &m, &l);
for (int i = 0; i < n; i++)
scanf("%d", &a[i]);
for (int i = 0; i < n - 1; i++)
for (int j = i + 1; j < n; j++)
if (a[i] < a[j])
{
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
int ans = 0;
for (int i = 0; i < n && i < m / l; i++)
ans += a[i];
printf("%d", ans);
}
B 万分之一的光(easy version)
题意：
计算给出所有方格之间相邻的边的数量乘以4。
解法：
因为是easy version所以解法有很多，可以每两个方格都对比一下，看是否有边相邻，也可以使用hard version的方法（下面再讲），但使用简单的排序算法。
#include <stdio.h>
//大楼结构体，包括两个成员记录横纵坐标
struct build
{
int x, y;
} a[1005];
int main()
{
int n, k;
//读入数据
scanf("%d%d", &n, &k);
for (int i = 0; i < k; i++)
scanf("%d%d", &a[i].x, &a[i].y);
//ans记录相邻的边的数量
int ans = 0;
//按照先横再纵的方式排序
for (int i = 0; i < k; i++)
for (int j = i + 1; j < k; j++)
if (a[i].x != a[j].x)
{
if (a[i].x > a[j].x)
{
struct build temp = a[j];
a[j] = a[i];
a[i] = temp;
}
}
else
{
if (a[i].y > a[j].y)
{
struct build temp = a[j];
a[j] = a[i];
a[i] = temp;
}
}
//如果两栋楼横坐标相同且纵坐标相差1(说明两建筑相邻)，答案+1
for (int i = 1; i < k; i++)
if ((a[i].y == a[i - 1].y + 1 && a[i].x == a[i - 1].x))
ans++;
//先纵后横，与上面同理
for (int i = 0; i < k; i++)
for (int j = i + 1; j < k; j++)
if (a[i].y != a[j].y)
{
if (a[i].y > a[j].y)
{
struct build temp = a[j];
a[j] = a[i];
a[i] = temp;
}
}
else
{
if (a[i].x > a[j].x)
{
struct build temp = a[j];
a[j] = a[i];
a[i] = temp;
}
}
for (int i = 1; i < k; i++)
if ((a[i].x == a[i - 1].x + 1 && a[i].y == a[i - 1].y))
ans++;
//输出答案
printf("%d", ans * 4);
}
C 万分之一的光(hard version)
题意：
同上
解法：
相比于easy version增加了数据范围。对楼房先按横坐标排序，然后判断排序后的楼之间是否相邻（优先按照纵坐标排序，再按照横坐标排序，这样对比数组中相邻的楼房是否相邻即可），然后按照纵坐标排序，再判断排序后的楼之间是否相邻（同理），由于每条相邻的边上都有4栈路灯，所以只要将答案乘4即可。（使用快速排序，时间复杂度（n*logn））
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
struct lou {
int x, y;
} a[MAXN];
int n, k, ans;
bool cmp1(lou a, lou b) {
if (a.x != b.x) return a.x < b.x;
else return a.y < b.y;
}
bool cmp2(lou a, lou b) {
if (a.y != b.y) return a.y < b.y;
else return a.x < b.x;
}
int main() {
scanf("%d%d", &n, &k);
for (int i = 1; i <= k; i++) {
int x, y;
scanf("%d%d", &x, &y);
a[i].x = x;
a[i].y = y;
}
sort(a + 1, a + k + 1, cmp1);
for (int i = 1; i < k; i++)
if (a[i].x == a[i + 1].x && a[i].y == a[i + 1].y - 1)
ans++;
sort(a + 1, a + k + 1, cmp2);
for (int i = 1; i < k; i++)
if (a[i].y == a[i + 1].y && a[i].x == a[i + 1].x - 1)
ans++;
printf("%d", ans * 4);
return 0; // qwq
}
D 一花依世界
题意：
计算出按照题目所给规则所能吃到的最大包子数。
解法：
首先，可能有很多同学选择优先吃一半的方法，但显然不对，如果吃一半后仍为偶数相当于给了对手一半包子所以不是最优选择。所以应该在对手的角度考虑，如何让对手吃的最少，自己就吃的最多。显然让对手吃的最少的情况是，每次轮到对手来取的时候都是奇数，对手只能吃一个，对手吃过以后是偶数，所以自己可以吃一半。所以最优策略是如果吃过一半后是偶数，选择吃一个，这样对手也只能吃一个，如果吃一半后是奇数，这时自己得到一半的包子，而对手只能选择吃一个，如果剩4个包子是例外（这时按照上述策略不是最优）。
#include <stdio.h>
int main ()
{
int t, n;
scanf("%d", &t);
while (t--)
{
scanf("%d", &n);
int ans = 0, now = 1;//now用来记录目前是哪个人在吃包子，1即为自己0则是对手
while (n > 0)
{
int cnt = 0;
if (!(n & 1) && n / 2 % 2 == 1)
{
n >>= 1;
cnt = n;
}
else if (n == 4)
{
n = 1;
cnt = 3;
}
else
{
cnt = 1;
n--;
}
ans += cnt * now;
now = !now;
}
printf("%d\n", ans);
}
return 0;
}
E 九九八十一
题意：
计算出地图上蜘蛛网形成的块的数量。
解法：
一道dfs算法的入门题（也可以拿bfs算法做），遍历每个点，如果这个点是蜘蛛网且还没有被烧掉，则对这个格子进行dfs，把所有与这个格子相连的蜘蛛网都标记为已经烧掉，答案+1。当对一个点dfs时，首先把自身标记为已经烧掉，然后判断它周围的四个格子，如果有格子是蜘蛛网却还未被烧掉，则再对这个点dfs。直到所有与原先蜘蛛网链接的蜘蛛网被标记为烧掉。
#include <stdio.h>
#include <stdlib.h>
int n, m;
char dt[1005][1005];
int vis[1005][1005];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
void dfs(int x, int y)
{
//标记自身为烧掉的状态
vis[x][y] = 1;
for (int i = 0; i < 4; i++)
{
int xx = x + dx[i], yy = y + dy[i];
//如果它周围的某个方向的格子是蜘蛛网且还未被烧掉，则dfs那个格子
if (dt[xx][yy] == '#' && vis[xx][yy] == 0)
dfs(xx, yy);
}
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
scanf("%s", dt[i] + 1);
int ans = 0;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
//如果这个格子是蜘蛛网且还未被烧掉
if (dt[i][j] == '#' && vis[i][j] == 0)
{
dfs(i, j);
ans++;
}
}
}
printf("%d", ans);
return 0;
}
F 达拉崩吧
签到题！！！
#include <stdio.h>
#include <stdlib.h>
int main()
{
printf("6\n达拉崩吧斑得贝迪卜多比鲁翁\n米娅莫拉苏娜丹妮谢莉红\n昆图库塔卡提考特苏瓦西拉松\n蒙达鲁克硫斯伯古比奇巴勒城");
return 0;
}
G 夜间出租车
题意：
快速计算出租车通过某个路口的时间
解法：
模拟题，按照题意，通过绿灯不耗时间，但等待绿灯的过程需要时间，所以从前往后模拟每经过一个红绿灯就把经过这个红绿灯消耗的时间记录一下加在时刻上（由题意知最多等待两分钟），且所有本题需要预处理一遍通过每个红绿灯的时间，然后查询的时候直接回答即可。
#include <stdio.h>
int n, q, h, m;
char str[100005];
int ti[100005];
//这里记录分别为绿灯黄灯红灯时要等的时间
//a[0]代表绿灯的情况，a[1]代表黄灯的情况，a[2]代表红灯的情况
//因为路灯三分钟一循环，所以记录三个值就行
int a[3][3] = {{0, 2, 1}, {2, 1, 0}, {1, 0, 2}};
int main ()
{
scanf("%d%d", &n, &q);
scanf("%d:%d", &h, &m);
scanf("%s", str);
int now = 0;
for (int i = 0; i < n; i++) {
if (str[i] == 'g') {
now += a[0][now % 3];
} else if (str[i] == 'y') {
now += a[1][now % 3];
} else if (str[i] == 'r') {
now += a[2][now % 3];
}
ti[i] = now;
}
for (int i = 1; i <= q; i++) {
int x;
scanf("%d", &x);
printf("%02d:%02d\n", ((ti[x - 1] + m) / 60 + h) % 24, (ti[x - 1] + m) % 60);
}
return 0;
}
H 一半一半
题意：
求出所给直线把整个平面分割成的块数
解法：
#include <stdio.h>
#include <math.h>
#define eps 1e-5
struct line {
int a, b;
} lines[505];
typedef struct point {
double x, y;
} point;
//用来标记这条直线是否和前面的直线重合
int st[505];
int main() {
long long ans = 0;
int n;
//读入
scanf("%d", &n);
for (int i = 0; i < n; i++) {
//读入直线
scanf("%d%d", &lines[i].a, &lines[i].b);
//创建一个数组用来存放这条直线与前面几条直线的交点
point points[505] = {0};
int cnt = 0;
for (int j = 0; j < i; j++) {
//如果这条直线与其他直线重复（重合）就跳过
if (st[j]) continue;
// 与第j条线平行
if (lines[i].a == lines[j].a) {
// 与第j条线重合
if (lines[i].b == lines[j].b) {
// 标记为重复，没有增加任何分块，直接break
st[i] = 1;
break;
} else {
// 仅平行，没有焦点
continue;
}
}
point p;
// 计算出直线i和直线j的交点坐标
p.x = (lines[j].b - lines[i].b) * 1.0 / (lines[i].a - lines[j].a);
p.y = (lines[i].a * p.x + lines[i].b);
int flag = 1;
for (int k = 0; k < cnt; k++) {
//如果与之前计算的交点重复则不计入（这里有误差判断）
if (fabs(points[k].x - p.x) < eps && fabs(points[k].y - p.y) < eps) {
flag = 0;
break;
}
}
if (flag) {
points[cnt++] = p;
}
}
// 与前面的所有直线有cnt个交点，即增加了cnt+1个分块
if (!st[i]) ans += cnt + 1;
}
// 输出ans+1(因为初始时相当于一整块区域)
printf("%lld", ans + 1);
return 0;
}
写完了才发现牛客可以插入公式😓！！
京公网安备 11010502036488号