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语句共同实现回溯剪枝.

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

#include <iostream>
#include <vector>
using namespace std;
void findWays(int climbed,int index,int count,vector<int>& results,int n){
    if (climbed==n){
        count++;
        for (auto step:results){
            cout<<step<<' ';
        }
        cout<<'\n';
        return;
    }
    for (int i=1;i<=2;i++){
        if (climbed+i>n) break;
        results.push_back(i);
        findWays(climbed+i,index+1,count,results,n);
    }
}
int main(){
    int n;
    cin>>n;
    vector<int> results;
    findWays(0,0,0,results,n);
    return 0;
}

仍然有一些问题:count作为传值参数并不会正确累加; 使用push_back()会在容器后面添加值,而不是更改原有的值,但因为容器大小并不确定,也不好预分配vector容器.

那么,有没有什么方法可以覆盖或擦除vector最后一个元素呢?有的兄弟,有的.像这样好用的函数还有很多个:

  1. pop_back(): 移除 vector 中最后一个元素.
  2. push_back(value):在末尾添加元素value.
  3. clear(): 移除 vector 中的所有元素，但不释放内存.
  4. capacity(): 返回 vector 当前分配的容量，即可以存储的元素数量，而不需要重新分配内存
  5. front(): 返回 vector 中的第一个元素。
  6. back(): 返回 vector 中的最后一个元素。
  7. begin(): 返回指向 vector 第一个元素的迭代器。
  8. end(): 返回指向 vector 最后一个元素之后的迭代器。
  9. erase(iterator pos): 删除指定位置的元素
  10. at(size_t index): 返回指定索引位置的元素，提供边界检查。
  11. operator[](size_t index): 返回指定索引位置的元素，不进行边界检查。
  12. insert(iterator pos, const T& value): 在指定位置插入元素 value。

提问:

Q:一些函数为大多数STL成员共用,一些为单个专属,他们的名称有什么区别?

Q:以上函数中有些要用到迭代器(Iterator),具体怎么实现?

A:

//remove the first occurrence of a specific value 
auto it=find(vec.begin(),vec.end(),value);
if (it!=vec.end()){
	vec.erase(it);
}
//remove all occurrence of the value
vec.erase(remove(vec.begin(),vec.end(),value),vec.end());

Q:insert()的实现细节?它是将之后的元素全部向后易位吗? LinkedList和vector之间的差异?

Q:迭代器和指针有什么区别?

回到先前的问题,因为每条路径的长短可能不同,所以results不好预分配来像数组一样通过维护下标来存储和覆盖值. 所以通过push_back()&pop_back()来做出选择&撤销.

实现细节:递归函数返回(return)后,继续执行for循环,撤销上一次选择.

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

void findWays(int climbed,int& count,vector<int>& results,int n){
    if (climbed==n){
        count++;
        cout<<count<<". ";
        for (auto step:results){
            cout<<step<<' ';
        }
        cout<<'\n';
        return;
    }
    for (int i=1;i<=2;i++){
        if (climbed+i>n) break;
        results.push_back(i);
        findWays(climbed+i,count,results,n);
        results.pop_back();
    }
}
int main(){
    int n;
    cin>>n;
    vector<int> results;
    int count=0;
    findWays(0,count,results,n);
    return 0;
}

最短排队时间

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中