Skip to content

2024CAS第一次月赛题解 #4

Open
Open
2024CAS第一次月赛题解#4
Labels
solutionAlgorithmic Problem Solution

Description

@wellwei
wellwei
opened on Nov 3, 2024

难度一览

  • 简单题：A、D、L
  • 中等题：B、G、H、I、M
  • 难题：E、F、J、K

A

题意：找到矩形的长和宽、利用最大公约数化简。

#include <stdio.h>
char s[520][520];
int n, m;

int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++)
        scanf("%s", (s + i));	// s + i 就相当于s[i]

    int wid = 0, hei = 0, stx, sty; // 矩形宽度、高度以及矩阵开始坐标
    int flag = 0; // 标记是否找到起始点'x'

    // 查找第一个'x'的位置作为起始点
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (s[i][j] == 'x') {
                stx = i;
                sty = j;
                flag = 1;
                break;
            }
        }
        if (flag) break; // 如果找到'x'，则退出循环
    }

    // 从起始点开始，向下计算高度
    for (int i = stx; i < n; i++) {
        if (s[i][sty] == 'x') ++hei;
        else break; // 如果遇到非'x'字符，则停止计算高度
    }

    // 从起始点开始，向右计算宽度
    for (int j = sty; j < m; j++) {
        if (s[stx][j] == 'x') ++wid;
        else break; // 如果遇到非'x'字符，则停止计算宽度
    }

    // 计算找到的矩形区域的宽和高的最大公约数，用于找到最小矩形
    int t = gcd(wid, hei);
    wid /= t;
    hei /= t;

    for (int i = 1; i <= hei; i++) {
        for (int j = 1; j <= wid; j++) {
            putchar('x');
        }
        puts(""); // 输出换行符
    }
    return 0;
}

B

题意：计算有多少个数，恰好等于集合中另外两个（不同的）数之和

方法一

用一个数组标记 $i$ 的数量，循环两数和与第一个数，判断另一个数是否存在。

int a[100010];
int num[100010];	//每个数的数量
int n, m;

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        num[a[i]]++;
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (a[j] > a[i]) continue;
            int k = a[i] - a[j];	//判断第二个数是否存在
            if (k == a[j]) {	//如果两数相同需要判断是否有两个
                if (num[k] > 1) {
                    ++ans;
                    break;
                }
            } else {
                if (num[k]) {	//如果第二个数存在那么答案++
                    ++ans;
                    break;
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}

方法二

// 先排序，再找前面有多少组数据满足
// 该题要注意：都是正整数，因此l++后，和一定增加，r--后，和一定减少
const int N = 100;
int a[N];
int n;
void solve()
{
	int ans = 0;// 答案
	int flag = n - 1;// 目标和的下标
	while (flag >= 2)// 一定要满足有三个数l, r, flag
	{
		int l = 0, r = flag - 1;
		while (l < r)
		{
			if (a[l] + a[r] == a[flag])
			{
				ans++;
				break;// 得出答案就退出，因为他并不需要计算有多少组满足 a[l] + a[r] = a[flag]
			}
			else if (a[l] + a[r] > a[flag])
				r--;
			else
				l++;
		}
		flag--;
	}
	cout << ans << endl;
}
int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> a[i];
	sort(a, a + n);
	solve();
	return 0;
}

C

签到题，按题意输出即可

#include<stdio.h>
int main()
{
	printf("Concentration Acceptance Software");
	return 0;
}

D

每个题单在当天 dyh 都会写一个题。
对于每个题单增长到最高的时候只有两种情况

  • ① 被清空后递增到 n 后又递减回来

  • ② 被清空后递减到 1 后又递增回来

    假设当前题单 i，前面有 x 个题单，后面有 y 个题单
    例举可以发现最大数量为 max(x,y)*2 个题。

#include <bits/stdc++.h>
using namespace std;
int n;
int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		// 对于当前题单i，计算其前面和后面的题单数量中的较大值
		// i表示当前题单的索引，n-i-1表示当前题单后面的题单数量
		int x = max(i, n - i - 1);
		// 1. 被清空后递增到n后又递减回来
		// 2. 被清空后递减到1后又递增回来
		// 在这两种情况下，最大数量都是前后题单数量的两倍
		cout << x * 2 << endl;
	}
	return 0;
}

E

//橙子蛋糕
#include<iostream>
using namespace std;

int main()
{
    long long n, k;
    scanf("%lld%lld",&n,&k);

    // 推断易得 k 与 n - k 的结果一样，故要判断补数n - k
    // 如果 k 大于 n 的一半，则计算 k 的补数，并赋值回 k
    if (k > n / 2)
        k = n - k; // 选择较小的 k 可以简化后续计算

    // 如果 k 等于 n 减 k，即刚好是对角，就可以直接输出 n
    if (k == n - k)
        printf("%lld",n);
    else
        // 正常的选取情况就是 n*k + 1
        printf("%lld",n * k + 1);

    return 0;
}

F

因为要求舍入后的最大值，所以只需要找到能舍入的最高位即可（从左往右第一个 $ >=5 $的数）

const int N = 2e5 + 10;
char s[N];
int n, t;
int main() {
    scanf("%d %d", &n, &t);
    scanf("%s", s);
    int pos;//记录小数点的位置
    for (int i = 0; i < n; i++) {
        if (s[i] == '.') {
            pos = i;
            break;
        }
    }
    int len = n; //记录保留字符串的长度
    for (int i = pos + 1; i < n; i++) {
        if (s[i] >= '5') { //从左往右找到第一个大于等于5的数字的位置开始四舍五入
            len = i;
            t--;
            i--;
            while (s[i] == '4' && t != 0) { //检查是否能继续四舍五入
                len = i;
                t--;
                i--;
            }
            if (s[i] == '.') { //检查是否需要进位到整数部分
                len = i;
                i--;
                while (s[i] == '9') { //处理如果进位到整数最后一位是9的情况
                    s[i] = '0';
                    i--;
                }
                if (i == -1) {
                    printf("1");//处理进位到最前面的情况（如99.5到100）
                }
                else s[i] += 1;
            }
            else s[i] += 1;
            break;
        }
    }
    for (int i = 0; i < len; i++) {
        printf("%c", s[i]);
    }
    return 0;
}

G

int t, n;
int a[200005], x;
int ans = -1000000;
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        if (x + a[i] > 0)
            x += a[i];
        // 判断是否将当前整数加入当前的子序列中
        // 如果加入后子序列的和仍然为正，则加入
        else
            x = a[i]; //说明a[i]是负数，但记下这个负数的原因是防止所有元素都是负数
        //都是负数的话，答案理应是最大的那个负数
        ans= max(ans, x);
    }
    printf("%d\n", ans);
}

H

注意一个地方可以购买多次，如果位置 $i$ 的价格是 $ i $ 到 $ n $ 价格中最小的那么就尽可能多购买。

const int N=2e5+10;
int a[N],mi[N];

void solve() {
	int n;
    scanf("%d", &n);
	for (int i = 0; i < n; ++i) {
        scanf("%d", &a[i]);
	}
	mi[n] = 2e9; // 将最后一个元素初始化为一个很大的值，以便后续比较
	for (int i = n - 1; i >= 0; --i) {
		mi[i] = min(a[i], mi[i + 1]); // 从后往前找最小值
	}
	int ans = 0;
	int sum = 0;
	for (int i = 0; i < n; ++i) {
		++sum; // 每次循环增加计数
		if (a[i] == mi[i]) { // 如果当前元素是该位置后的最小值
			int t = sum / a[i]; // 计算可以“消耗”的块数
			ans += t; // 更新结果
			sum -= t * a[i]; // 减去所“消耗”的数量
		}
	}
    printf("%d\n", ans);
}
int main() {
	solve();
	return 0;
}

I

对于唐嘉富来说，最优的策略是对数组中最大的 x 个元素取反。因此，为了最小化唐嘉富造成的损害，孙洁龙应该总是移除一些最大的元素。
为了解决这个问题，我们可以对数组进行排序，并遍历 i（0≤i≤k），其中 i 是孙洁龙移除的元素数量。
对于每个 i，我们知道孙洁龙将移除数组中最大的 i 个元素，然后唐嘉富会对剩下的 x 个最大元素取反。
因此，我们可以利用前缀和快速计算出最终的和。由于排序的存在，时间复杂度为 O(nlogn)。

#include <bits/stdc++.h>
using namespace std;
int A[2000010];
void solve() {
	int n, k, x;
	cin >> n >> k >> x;
	for (int i = 1; i <= n; i++)
		cin >> A[i];
	sort(A + 1, A + n + 1, greater<int>()); // 这里使用了C++的排序函数sort，C语言可使用qsort函数或者手搓快速排序。

	for (int i = 1; i <= n; i++)
		A[i] += A[i - 1];// 计算前缀和，A[i]现在表示前i个元素的和

	int ans = -1e9; // 初始化答案为一个非常小的数（负无穷大的近似值）
	// 遍历孙洁龙可能移除的元素数量 i（ 0 到 k ）
	for (int i = 0; i <= k; i++)
		// 更新答案，取当前答案和（ A[n]（总和）- 2 * A[min(i + x, n)]（
		//移除i个后唐嘉富取反x个的和的两倍，因为取反相当于减去两倍）+ A[i]（孙洁龙移除i个的和））的较大值
		ans = max(ans, A[n] - 2 * A[min(i + x, n)] + A[i]);

    printf("%d\n", ans);
}
int main() {
	int tc;
    scanf("%d", &tc);
	while (tc--)
		solve();
}

J

通过画图易得：

1 x n 答案就是 n，m 中得较大者

2 x n分三种情况：

  • 第一种即 m 可以被 2 整除但不可以被 4 整除，那么最优方案即 n + m
  • 第二种即 m 即可被 2 整除又可被 4 整除，最优方案即放满其中一排即 max(n, m)
  • 第三种即 m 为奇数，最优方案为max(n, m) + 1

其他情况易得数量为 (n x m + 1) / 2

void solve() {
    int n, m;
    cin >> n >> m;
    if (n == 1 || m == 1)
        printf("%d\n", max(n, m));
    else if (n == 2 || m == 2) {
        if (n == 2 && m % 2 == 0 && m % 4 != 0)
            printf("%d\n", n + m);

        else if (m == 2 && n % 2 == 0 && n % 4 != 0)
            printf("%d\n", n + m);

        else if (max(n, m) % 2 == 0)
            printf("%d\n", max(n, m));

        else printf("%d\n", max(n, m) + 1);
    }
    else printf("%d\n", (n * m + 1) / 2);
}

int main() {
    int t = 1;
    while (t--)
        solve();
    return 0;
}

K

只需要先将每一个学妹以结束时间排一次序，得到一个排序后的结构体数组，
存储第一个学妹的结束时间，然后以结束时间为准，
跟下一个学妹开始时间比较，不小于第一个学妹的结束时间就证明不冲突，然后计数，
再记录下这个学妹的结束时间，以此类推，最后输出总次数就可以了。
（因为将结束时间排序，所以只要确定开始时间没有冲突，那整段时间就不会又任何冲突）

#include<stdio.h>
#include<algorithm>//算法库(包含sort函数)
struct st { //（定义一个结构体数组，分别储存开始时间和结束时间）
	int a;//（开始时间）
	int b;//（结束时间）
} x[1000010];

bool cmp(st x, st y) { //（不管开始时间，直接按照结束时间排序）
	return x.b < y.b;
}

int main() {
	int n, ans = 1, cnt;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d%d", &x[i].a, &x[i].b);
	}
	std::sort(x + 1, x + n + 1, cmp); //（排序）亦可手写自定义关键字快速排序
	cnt = x[1].b; //（无脑记录第一个值）
	for (int i = 2; i <= n; i++) {
		if (x[i].a >= cnt) { //（找到符合要求的，记录）
			ans++;//（计数）
			cnt = x[i].b;
		}
	}

	printf("%d\n",ans);
	return 0;
}

L

由题意可得，合法得字符串一定是由 iguang 和 guangshen 组合而成得，所以我们只需要判断整个字符串是否只由这两种字符串组成。

#include <stdio.h>
#include <string.h>

char s[500010];

void solve() {
    scanf("%s", s);
    int f = 0;
    int i;
    char a[7];
    char b[10];
    int len = strlen(s);
    for (i = 0; i < len; ) {

        f = 0;
        strncpy(a, s + i, 6);
        a[6] = '\0';

        if (strcmp(a, "iguang") == 0) {
            f = 6;
        }

        strncpy(b, s + i, 9);
        b[9] = '\0';

        if (strcmp(b, "guangshen") == 0) {
            f = 9;
        }

        if (f == 9) i += 9;
        else if (f == 6) i += 6;
        else break;
    }
    if (f == 0 && i < len) printf("No\n");
    else printf("Yes\n");
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) solve();
    return 0;
}

M

能最多把 k 个 0 变成 1 的话，并且要求最多连续 1 的长度，那我们就可以直接遍历这
个数组，找到符合题目条件的长度，然后一直取到最大值即可，如果暴力遍历的
话肯定是会超时的，n 最大是1e5，k 最大是1e5，O（n * k）的复杂度是不行的，
本题可以先进行前缀和再采取双指针的解决方案复杂度为 O（n）。
因为数组中只有 0 或 1，因此前缀和的意思是方便找出区间的 1 的总个数，在遍历
的时候，判断条件必须是 $ (s[r] - s[l - 1] + k >= r - l + 1 ) $ ，r指针才会
往右加，不然就算 l 指针往右加。这个判断是意思是[l，r]区间的 1 的个数加上可
以把 0 变成 1 的个数，要大于这个区间长度，因为这个 k 是最多，所以可能会超
出.

#include <iostream>
using namespace std;
int a[100520],s[100520];
int main() {
	int n, k;
    scanf("%d%d", &n, &k);
	for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);

	for (int i = 1; i <= n; i++) {
		s[i] = s[i - 1] + a[i];
	}
	int ans = -0x3f3f3f3f;
	int l = 1, r = 1;
	while (r <= n) {
		if (s[r] - s[l - 1] + k >= r - l + 1) {
			ans = max(ans, r - l + 1);
			r++;
		} else {
			l++;
		}
	}
    printf("%d\n", ans);
	return 0;
}

Metadata

Metadata

Assignees

No one assigned

    Labels

    solutionAlgorithmic Problem Solution

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions