首页 > 其他分享 >题解:P10358 [PA2024] Obrazy

题解:P10358 [PA2024] Obrazy

时间:2024-08-25 10:48:25浏览次数:12  
标签:输出 le 题解 墙面 样例 PA2024 尺寸 Obrazy 画框

题解:P10358 [PA2024] Obrazy

题目传送门

即当最小的画框都不可能覆盖整个矩形墙面时,输出 −1。

[PA2024] Obrazy

题目背景

PA 2024 3C

题目描述

题目译自 PA 2024 Runda 3 Obrazy,感谢 Macaronlin 提供翻译

给定尺寸为 $h\times w$ 的矩形墙面,以及 $n$ 种尺寸的正方形画框,每种尺寸画框都有无穷多个。对于任意两种不同尺寸的画框,其中一个尺寸的边长总能整除另一个尺寸的边长。

现用这些画框完全覆盖墙面,而且画框之间不能重叠,只能边缘相接,请求出最少需要购买多少个画框?如果不可能完全覆盖墙面,则程序应输出 $-1$。

输入格式

第一行两个整数 $h$ 和 $w\ (1\le h,w\le 10^9)$,表示墙面大小。

第二行一个整数 $n\ (1\le n\le 30)$,表示画框个数。

第三行 $n$ 个整数 $d_1,d_2,\ldots,d_n\ (1\le d_i\le 10^9,d_i<d_{i+1})$,表示每个正方形画框的大小,保证 $d_{i+1}$ 能被 $d_i$ 整除。

输出格式

输出一行一个整数,如果可以完全覆盖墙面,输出最少要购买多少画框,否则输出 $-1$。

样例 #1

样例输入 #1

6 10
3
1 3 6

样例输出 #1

9

样例 #2

样例输入 #2

3 3
1
2

样例输出 #2

-1

提示

在第一个样例中,Byteasar 可以用九个画框(六个 $1\times 1$、两个 $3\times 3$ 和一个 $6\times 6$)覆盖一面墙,具体如下:

在第二个样例中,无法完全覆盖墙面。

--------------------分割线--------------------

意思

用最少的方块贴最大的墙,无遗漏重叠。

过程

我们先看图

特判

因为其中一个尺寸的边长总能整除另一个尺寸的边长。

也就是说,只要连最小的方块都不能整除(正好铺满)边长,就输出 -1 。

否则用大的尽量替换小的

怎么说呢,建议降橙。

代码不重要,主要是思路

#include <bits/stdc++.h>
using namespace std;
const int N = 35;
long long h, w, n, d[N], ans;
int main(){
    cin >> h >> w >> n;
    for(int i = 1; i <= n; i++) cin >> d[i];
    if((h % d[1]) || (w % d[1])){
        cout << -1;
        return 0;
    }
    ans = h / d[1] * w / d[1];
    for(int i = 2; i <= n; i++) ans -= (((d[i] / d[i - 1]) * (d[i] / d[i - 1]) - 1) * (h / d[i]) * (w / d[i]));
    cout << ans;
    return 0;
}

注意: int 存不下!!!

点个 (欲言又止)

标签:输出,le,题解,墙面,样例,PA2024,尺寸,Obrazy,画框
From: https://www.cnblogs.com/wayneoi/p/18378714

相关文章

  • SP10502 VIDEO - Video game combos 题解
    题目传送门前置知识AC自动机解法多模式串匹配考虑AC自动机。令\(f_{i,j}\)表示前\(i\)个字符,当前运行到AC自动机的状态\(j\)时的最大得分。状态转移方程为\(f_{i,k}=\max\limits_{k\inSon(j)}\{f_{i-1,j}+sum_{k}\}\),其中\(sum_{k}\)表示fail树上以\(k......
  • 历年CSP-J初赛真题解析 | 2015年CSP-J初赛阅读程序(23-26)
    学习C++从娃娃抓起!记录下CSP-J备考学习过程中的题目,记录每一个瞬间。附上汇总贴:历年CSP-J初赛真题解析|汇总_热爱编程的通信人的博客-CSDN博客#include<iostream>usingnamespacestd;intmain(){inta,b,c;a=1;b=2;c=3;if(a>b){......
  • abc368 题解
    切了ABCDF,G赛后1min切了(恼比赛链接:https://atcoder.jp/contests/abc368A-Cut题意:给定一个长度为\(n\)的序列,先输出后\(k\)个数,在输出前\(n-k\)个数。思路:按题意模拟即可。代码:https://atcoder.jp/contests/abc368/submissions/57030066B-Decrease2maxel......
  • CF241B Friends 题解
    是异或粽子的超级加强版,但是本题因为\(m\)很大,不能套用那一题的解法。换一种思路:考虑把\(a_i\)从高位到低位插入0-1Trie之后,二分第\(m\)大,通过第\(m\)大求答案。对于二分的一个值\(x\),枚举每个位置\(i\),在0-1Trie上找与\(a_i\)异或值大于等于\(x\)的值的......
  • qoj8546题解补充
    题解中第二种解法并没有具体解释是如何归纳的(害笔者想了两天两夜),这里给一个证明。考虑答案为(n,n)时,只需要全取max即可,接下来我们从n往n-1归纳,接下来所有位置初始都是取max的情况1:a中的n和b中的n在同一个位置上,我们只需在这个位置上取min即可归纳到n-1,那么接下来我们钦定不会......
  • P7515 [省选联考 2021 A 卷] 矩阵游戏 题解
    DescriptionAlice有一个\(n\timesm\)的矩阵\(a_{i,j}\)(\(1\lei\len\),\(1\lej\lem\)),其每个元素为大小不超过\({10}^6\)的非负整数。Bob根据该矩阵生成了一个\((n-1)\times(m-1)\)的矩阵\(b_{i,j}\)(\(1\lei\len-1\),\(1\lej\lem-1\)),每个......
  • VS2022 Visual Studio Installer 一直卡在0%,或者下载速度慢的问题解决办法
    C:\Users\Administrator\AppData\Local\Temp到c盘查看日志,发现是下载一个叫vs_installer.opc的东西失败了, 直接复制日志里的https://aka.ms/vs/17/release/installer,下载,发现成功下载,然后放到installer安装器同级目录,重新打开setup安装,就成功了打开了,然后会一直正在准备中,......
  • P10933 创世纪 题解
    题目传送门前置知识树形DP解法将\(a_{i}\)向\(i\)连一条有向边,这样就形成了基环外向树森林。设\(f_{x,0/1}\)表示\(x\)不选/选时,以\(x\)为根的子树的最多选择个数,状态转移方程为\(\begin{cases}f_{x,0}=\sum\limits_{y\inSon(x)}\max(f_{y,0},f_{y,1})\\f_......
  • P10957 环路运输 题解
    题目传送门前置知识单调队列/单调栈优化解法在仓库\(1\)和\(n\)之间把环断开,然后复制一倍接在末尾,形成长度为\(2n\)的直线公路,即有\(a_{i}=a_{i+n}(1\lei\len)\)。对于原来环形公路上的任意两座仓库\(i,j(1\lej<i\len)\),代价为\(\begin{cases}a_{i}+a_{j}......
  • Chain Contestant 题解
    前言题目链接:洛谷;AtCoder。最慢的点才跑\(2\)ms的题解确定不看一看?题意简述给定长度为\(n\)的字符串\(s\),其中\(s_i\in\Omega\),求有多少子序列\(T\)满足任意\(x\in\Omega\),其在\(T\)出现的位置为连续一段,当然,对\(998244353\)取模。\(n\leq10^5\),\(|\Omeg......