题目1

P2241 统计方形（数据加强版）

题目背景:1997年普及组第一题

题目描述

有一个 $n \times m$ 方格的棋盘，求其方格包含多少正方形、长方形（不包含正方形）。

输入格式:

一行，两个正整数 $n,m$（$n \leq 5000,m \leq 5000$）。

输出格式:

一行，两个正整数，分别表示方格包含多少正方形、长方形（不包含正方形）。

输入输出样例 #1

输入 #1

1
2 3

输出 #1

1
8 10

题解

方法1

数学公式求解

思路

首先，我看到这题就回忆起了高中的排列组合，对于一个 $n \cdot m$ 的棋盘，我们可以把它看作n行m列。

选择其中的行列做正方形，那么对于边长为 $k$ 的正方形，对于 $n$ 行有 $n-k+1$ 总选择，对于 $m$ 列有 $m-k+1$ 总选择，所以边长为 $k$ 的正方形有 $(n-k+1) \cdot (m-k+1)$ 个。

那么，求出所有的正方形应该是在一个正方形棋盘中划分，这个正方形棋盘的边长显然是 $min(m,n)$ ，所以正方形的个数就是 $\sum_{i=1}^{min(m,n)}(n-i+1) \cdot (m-i+1)$，不妨记 $K=min(m,n)$ ，则有：

以上就是正方形的总个数 $S_1$ 。

下面我们来求长方形的个数 \( S_{2} \)。我们知道总矩形个数=总长方形个数+总正方形个数，那么总矩形个数不就是 \( C_{n+1}^{2} \cdot C_{m+1}^{2} \) 吗？那么长方形个数就是 \( C_{n+1}^{2} \cdot C_{m+1}^{2}-S_1 \)。

这里 \( C_{n+1}^{2} \cdot C_{m+1}^{2} \) 中的 \( n,m \) 需要+1是因为：由于矩形的边界由网格横纵的网格线决定，行方向由 \( n+1 \) 条网格线（包括最上和最下的边界），同理列方向。因此矩形的总数为 \( C_{n+1}^{2} \cdot C_{m+1}^{2} \)。

我们将公式整理一下，得到：

因此这题的答案就显然易见了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
ll n,m;
ll S1,S2;

int main()
{
    cin >> n >> m;
    ll K = min(n,m);
    S1 = (n+1)*(m+1)*K-(n+m+2)*K*(K+1)/2+K*(K+1)*(2*K+1)/6;
    S2 = (n*(n+1)/2)*(m*(m+1)/2)-S1;
    cout << S1 << " " << S2 << endl;
}

方法2

枚举法

思路

我们可以枚举在棋盘上边长为 $i,j$ 的矩形，如果 $i=j$ ，则可以认为是正方形并计入 $S_1$ ，否则认为是长方形并计入 $S_2$ 。

那么这时候求边长为 $i,j$ 的矩形个数，我们可以发现，对于边长为 $i$ 的矩形，有 $n-i+1$ 种选择，对于边长为 $j$ 的矩形，有 $m-j+1$ 种选择，所以边长为 $i,j$ 的矩形有 $(n-i+1) \cdot (m-j+1)$ 个。

因此，我们可以枚举 $i,j$ ，并求出 $S_1,S_2$ 。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
ll n,m;
ll S1,S2;

int main()
{
    cin >> n >> m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            ll t = (n-i+1)*(m-j+1);
            if(i==j) S1 += t;
            else S2 += t;
        }
    }
    cout << S1 << " " << S2 << endl;
}

实际上这个代码还可以优化，因为 $S_1$ 和 $S_2$ 的计算是重复的，我们可以先求出 $S_1$ ，然后 $S_2$ 就等于总矩形个数减去 $S_1$ 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
ll n,m;
ll S1,S2;

int main()
{
    cin >> n >> m;
    for(int i=1;i<=min(n,m);i++)
        S1+= (n-i+1)*(m-i+1);
    S2 = (n*(n+1)/2)*(m*(m+1)/2)-S1;
    cout << S1 << " " << S2 << endl;
}

这样就很像方法1了，只是我们把 $S_1$ 的求和算出来了，时间复杂度变成了 $O(1)$ ，这里的时间复杂度是 $O(min(n,m))$ 。

题目2

P2089 烤鸡

题目背景: 猪猪 Hanke 得到了一只鸡。

题目描述

猪猪 Hanke 特别喜欢吃烤鸡（本是同畜牲，相煎何太急！）Hanke 吃鸡很特别，为什么特别呢？因为他有 $10$ 种配料（芥末、孜然等），每种配料可以放 $1$ 到 $3$ 克，任意烤鸡的美味程度为所有配料质量之和。

现在， Hanke 想要知道，如果给你一个美味程度 $n$ ，请输出这 $10$ 种配料的所有搭配方案。

输入格式:

一个正整数 $n$，表示美味程度。 对于 $100\%$ 的数据，$n \leq 5000$。

输出格式:

第一行，方案总数。

第二行至结束，$10$ 个数，表示每种配料所放的质量，按字典序排列。

如果没有符合要求的方法，就只要在第一行输出一个 $0$。

输入输出样例 #1

输入 #1

1
11

输出 #1

1
2
3
4
5
6
7
8
9
10
11
10
1 1 1 1 1 1 1 1 1 2 
1 1 1 1 1 1 1 1 2 1 
1 1 1 1 1 1 1 2 1 1 
1 1 1 1 1 1 2 1 1 1 
1 1 1 1 1 2 1 1 1 1 
1 1 1 1 2 1 1 1 1 1 
1 1 1 2 1 1 1 1 1 1 
1 1 2 1 1 1 1 1 1 1 
1 2 1 1 1 1 1 1 1 1 
2 1 1 1 1 1 1 1 1 1

题解

方法1

dfs递归

思路

这道题实际上在2月23日有人问我这题，刚好有时间就AC掉了，今天训练刚好又练到这题，就看着洛谷的提交历史代码，试着写下题解吧（之前很可能不是这个思路）。

由于这题显然是按照一定方式的全排列，我想到之前学的dfs刚好有可以打印全排列的方法，于是我就用dfs来写。

附上之前学dfs时的案例代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<stdio.h>
#include<stdbool.h>

int n=0;
bool st[1005];
int arr[1005];

void dfs(int x)
{
    ///用dfs递归生成n的连续整数全排列
    if(x>n)
    {
        for(int i=1;i<=n;i++)
            printf("%5d",arr[i]);
        printf("\n");
        return;
    }
    for(int i=1;i<=n;i++)
    {
        if(!st[i])
        {
            st[i]=true;
            arr[x]=i;            
            dfs(x+1);
            st[i]=false;
            arr[x]=0;
        }
    }
}

int main()
{
    scanf("%d",&n);
    dfs(1);
    return 0;
}

这里的st[]数组是用来标记当前位置是否被使用过，arr[]数组用来存储当前排列。

这里讨论n=3时
初始: [F, F, F]
选1 → [T, F, F] → 选2 → [T, T, F] → 选3 → [T, T, T] (输出123)
回溯 → [T, T, F] → 选3 → [T, F, T] → 选2 → [T, T, T] (输出132)
回溯 → [F, F, F] （进入下一个分支）
之后的操作同理，这里不在本题的讨论范围内。

那么本题就是打印符合不定方程

于是最直观的方法是枚举所有可能情况，即每个位置填1、2或3，然后检查总和是否等于n。但由于每个位置有3种选择，总共有 $3^{10} = 59049$ 种可能，直接枚举显然效率太低，需要优化。

那么为了减少不必要的计算，可以采用DFS + 剪枝的方法：

  1. 递归构建序列：从第1个位置开始，依次尝试填入1、2、3，然后递归处理下一个位置。
  2. 剪枝条件：
    • 剩余位置全填1仍超n：如果当前和 + 剩余位置数×1 > n，说明即使后面全填1也会超出，直接剪枝。
    • 剩余位置全填3仍不足n：如果当前和 + 剩余位置数×3 < n，说明即使后面全填3也无法达到n，直接剪枝。
  3. 终止条件：当填满10个位置时，检查总和是否等于n，如果是，则记录该序列。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<bits/stdc++.h>
using namespace std;
int n, cnt = 0, curr[10];
vector<vector<int>> res;


void dfs(int* curr, int idx, int s, int trg, int& cnt, vector<vector<int>>& res)
{
    if (idx==10)
    {
        if (s==trg)
        {
            res.push_back(vector<int>(curr, curr + 10));
            cnt++;
        }
        return;
    }
    if (s+(10-idx)>trg || s+(10-idx)*3<trg) return; 

    for (int i=1; i<=3; i++)
    {
        curr[idx]=i;
        dfs(curr, idx+1, s+i, trg, cnt, res);
    }
}

int main()
{
    cin >> n;
    if (n<10 || n>30)
    {
        cout << "0" << endl;
        return 0;
    }

    dfs(curr, 0, 0, n, cnt, res);
    cout << cnt << endl;
    for (const auto& res : res)
    {
        for (size_t j=0; j<res.size(); j++)
            cout << res[j] << (j < 9 ? " " : "");
        cout << endl;
    }
}

该程序最坏时间复杂度是 $O(3^{10})$ ，最好是 $O(1)$ ，平均时间复杂度是 $O(2^{10})$ ，所以时间复杂度是 $O(1)$ 量级的。
所以我预估是如果题目再加强点到选择 $5$ 种分支时，这个代码就TLE。

方法2

枚举

思路