算法1-3暴力枚举

P2241统计方形

参考的大佬的题解：https://www.luogu.com.cn/problem/solution/P2241

注意要开long long，因为最坏的情况是从1➕到5000 * 5000，超出了int

等差数列求和公式：

S=n*(n+1) / 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;
int n,m;
typedef long long ll;

ll zheng,chang;

int main()
{
	cin >> n >> m;			   //对于正方形来说，子矩阵的个数是有原矩阵减去相同的数得到
	for(int i = 0; i < n; i ++)//对于长方形来说，子矩形构成的矩阵的长宽是由原矩形长宽减去不同数而得
		for(int j = 0; j < m;j++)//棋盘中的矩阵不是正方形就是长方形，
		{
			if(i == j) zheng += (n-i)*(m - i);
			else chang += (n-i)*(m-j);
		}
	cout << zheng << " " << chang << endl;
	return 0;
}

P2089烤鸡

题目链接： https://www.luogu.com.cn/problem/P2089

一道比较简单的dfs，这里需要考虑的是最多有几种方案，因为题目说n最大5000，但是从题目意思可知，美味程度最大是30.数据量较小，如果非要说确定的话，3的10次方，最多开6w即可。

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
#include<bits/stdc++.h>

using namespace std;
int n,ans; //n表示需要的美味程度
int a[10000][10],cmp[10];

void dfs(int id,int degree){//id表示接下来考虑的是哪种配料，degree表示目前的美味程度
	if(id > 10 || degree > n) return;
	
	if(id == 10 && degree == n){
		for(int i = 0; i < 10;i++) a[ans][i] = cmp[i];
		ans++;
	}
	
	for(int i = 1; i <= 3; i ++){
		cmp[id] = i;
		dfs(id + 1,degree + i);//无需恢复现场，因为下次的值会覆盖
	}
}

int main()
{
	cin >> n;
	dfs(0,0);
	cout << ans << endl;
	if(ans){
		for(int i = 0; i < ans ;i++)
		{
			for(int j = 0; j < 10; j ++) cout << a[i][j] << " ";
			cout << endl;
		}
	}
	return 0;
}

P1618三连击