Count Rectangle

考虑一个M*N规格的棋盘,计算其中各种大小的矩形的数量.

问题可以抽象成求边长的组合方式数量.令1<=n<=N , 1<=m<=M , 求所有可能的n*m的和(几何意义上1*2和2*1有区别,都记入).自然而然想到嵌套循环

#include <iostream>
using namespace std;
#define ll long long
int main(){
    int M,N;
    cin>>M>>N;
    if (M<N) swap(M,N);
    ll rectSum=0;
    ll squreSum=0;
    for (int m=1;m<=M;m++){
        for (int n=1;n<=N;n++){
            rectSum+=m*n;
            if (m-n==abs(M-N)){
                squreSum+=m*n;
            }
        }
    }
    cout<<squreSum<<' '<<rectSum-squreSum<<endl;
    return 0;
}

以下是在网上找到的公式

在m*n规格的棋盘中，包含的矩形（包括正方形和长方形）的总数可以通过以下公式计算得出：

总数 = 1 + 2 + 3 + … + (m-1) + 1 + 2 + 3 + … + (n-1)

其中，每个加号代表的是在棋盘中从上到下或从左到右的一个单位增加的矩形数量。

具体来说：

1是1*1的方格数量
1+2+3+…+(m-1) 是所有1到m-1的 rows 的矩形数量
1+2+3+…+(n-1) 是所有1到n-1的 columns 的矩形数量
上述序列的和可以用等差数列求和公式计算，即：
S = n(a1 + an) / 2

对每行和每列分别进行计算，然后将两者相加。因此，总矩形数量的计算公式为：

总数 = [n(m+1)/2] + [m(n+1)/2]

注意，此公式考虑的是不重复的矩形，即每个更小的矩形都被包含在更大的矩形中，没有重复计数。

美味しさの程度

十种配料,每种可以放1~3g,输入总质量, 打印所有可能的搭配方案(按字典序排列),若无一符合要求,输出0.

首先想到的就是排列组合. 先分成10份找出所有的搭配比例,再排列组合.但在纸上比划了一下后发现很复杂.又想到之前写过的八皇后的题目,好像回溯可以解决.

#include <iostream>
#include <vector>
using namespace std;

void allWays(int index,int sum,int ocl,
vector<int>& curr,vector<vector<int>>& results){
    if (index==10){
        if (sum==ocl){
            results.push_back(curr);//符合条件记录
        }
        return;//返回上一层节点
    }
    for (int i=1;i<=3;i++){
        if (sum+i>ocl) break;//停止探索同级节点
        curr[index]=i;
        allWays(index+1,sum+i,ocl,curr,results);//配料索引,重量,goal,内容器(缓存),方法容器(已储存)
    }
}
int main(){
    int oclevel;
    cin>>oclevel;
    vector<vector<int>> results;//
    vector<int> curr(10);
    if (oclevel<3||oclevel>30) cout<<'0'<<"\n";
    else {
        allWays(0,0,oclevel,curr,results);
        for (auto res:results){
            for (int num: res){
                cout<<num<<' ';
            }
            cout<<'\n';
        }
    };
    return 0;
}

有些值得注意的地方:

  • 嵌套容器
  • 将数值作为函数的初始参数,在递归调用中更新数值.函数调用大量参数,和我的习惯不一样
  • for循环中的break是直接结束整个循环吗,还是只是跳过当前?

在通过调试观察各种变量的值如何变化时没有看出什么名堂,之后引入递归树的概念后开始摸清思路,但对于具体实现不是很理解,只是知道return语句和break语句共同实现回溯剪枝.

再考虑一个之前的问题:20级楼梯,一次上1级or2级,求方法总数并打印所有结果. 留着明天写,毕竟带着解决问题的目的是最好进入状态的方式().

最短排队时间

N个人排队取水,每个人花费的时间长短不一,求最短的平均等待时间.

按花费时间长短排序,且最后一个人花费的时间不算在等待时间内.每个人的等待时间都会在前一个人的基础上加上后者的花费时间.平均等待时间=总等待时间/人数

long long currentime=0,sum=0;
for (int i=0;i<n;i++){
	sum+=currentime;//求和
	currentime+=costimes[i].time;//累加
}

当i=n-1时currentime更新后会加上最后一个人的耗时(多算了ghost的等待时间,而这并不需要).但这没关系,因为for循环会在这之后停止,也就不会加进sum中