2021上海市小学生人工智能算法设计活动 问题 E: 长方形

作者： 作者的头像   洛白さん ,  2021-12-18 12:29:49 ,  所有人可见 ,  阅读 910

4


4

问题 E: 长方形

输入文件: 标准输入 输出文件: 标准输出
时间限制: 1 Sec 内存限制: 256 MB

题目描述

有一个N∗N的正方形，沿平行于边的方向画几条线段，可以得到很多个长方形。
如图所示，竖直方向有一条线段，水平方向有两条线段。
图片1.png
一共可以得到18个长方形，其中：
截图20211218122239.png
截图20211218122255.png
截图20211218122328.png
给出竖直方向上每一段的宽度，水平方向上每一段的高度，请你计算有多少个大小不同的长方形，以及这些大小不相同的长方形的面积之和。
两个长方形大小不同，是指无论如何旋转，都无法使两个长方形重合。重合只需要考虑边框，不需要考虑内部结构。也就是只要旋转后能让长方形的长、宽相等就算重合。
注意，此题中正方形不算长方形。

输入

第一行空格分开的两个整数a和b，分别表示正方形的竖直方向上分成a段和水平方向上分成b段。
第二行空格分开的a个整数，表示竖直方向上每一段的长度。
第三行空格分开的b个整数，表示水平方向上每一段的长度。
保证水平竖直方向上所有长度之和等于水平方向上所有长度之和，都等于N。

输出

第一行一个整数，表示大小不同的长方形的数量。
第二行一个整数，表示大小不同的长方形的面积之和。

样例输入 #1

2 3
2 2
1 2 1

样例输出 #1

5
32

样例说明 #1

1格的大小不同的长方形有1种：1∗2（4个）。2∗2是正方形，不是长方形。
2格的大小不同的长方形有3种：1∗4（2个）、2∗4（1个）、2∗3（4个）。
3格的大小不同的长方形有1种：2∗4（2个）。和之前有重复。
4格的大小不同的长方形有1种：3∗4（2个）。
6格的大小不同的长方形有0种。4∗4是正方形，不是长方形。
共有5种不同的长方形，面积之和为1 ∗ 2 + 1 ∗ 4 + 2 ∗ 4 + 2 ∗ 3 + 3 ∗ 4 = 32。

数据范围

1 ≤ a, b ≤ 100，1 ≤ N ≤ 1,000

谢谢浏览！

4 评论

用户头像
James007   2022-08-18 21:38         踩      回复

大哥，这道题目做出来了吗，能不能给一下源码，谢谢！

用户头像
Tianxn   2022-01-18 16:32         踩      回复 
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
using namespace std;

int n, m, a[110], b[110], sa[110], sb[110];
set<int> x, y;
set<int>::iterator p, g;
set<pair<int, int>> sv;

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        sa[i] = sa[i-1] + a[i];
        x.insert(a[i]);
        x.insert(sa[i]);
    }
    for (int i = 1; i <= m; i++)
    {
        cin >> b[i];
        sb[i] = sb[i-1] + b[i];
        y.insert(b[i]);
        y.insert(sb[i]);
    }
    for (p = x.begin(); p != x.end(); p++)
        for (g = y.begin(); g != y.end(); g++)
        {
            if (*p == *g) continue;
            if (*p > *g) sv.insert({*g, *p});
            else sv.insert({*p, *g});
        }
    cout << sv.size() << endl;
    int sum = 0;
    for (auto it:sv)
    {
        sum += it.first * it.second;
    }
    cout << sum << endl;
    return 0;
}
用户头像
James007   2022-07-25 13:57         踩      回复

鹅，我在另一个题库交只有10分？求帮助

用户头像
T800Model101   2022-10-29 16:23    回复了 James007 的评论         踩      回复

因为本身就有bug，他缺了不少线段