14 solutions
-
1
-
0
#根据谢老师发的视频讲解得出的暴力方法,详情请看https://www.bilibili.com/video/bv11L4y1b7JQ#
- 1
Information
- ID
- 106
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- 6
- Tags
- # Submissions
- 550
- Accepted
- 174
- Uploaded By
这道题 看了下 up 主 的视频,然后总结了下 自己的理解。确实 这种 思路 还是要有的,可能 对于 是小白的我,刚接触 是很难想到的。再接再厉。
#include <iostream>
using namespace std;
int main(void) {
long long ans = 0;
for (int a = 1; a <= 2021; ++a) {
for (int b = 1; b <= 2021 - a; ++b) {
for (int c = 1; c <= 2021 - a - b; ++c) {
int de = 2021 - a - b - c;// d + e 的 总和
if (de >= 2) {// 只要 d + e 可以再 分出两个整数,就代表 我们这个 五个数是成立的
ans+= de -1;// 但是 那我们也要 从 1 开始选择 d 的值,才能够 得到 e 的值吧。然后 才算是一种方案。
//比如 5 是 d + e 的总和,那么 d = 1 的时候 e = 4 依此类推 你会发现 有 四种 方案 是满足的
// 也就是说 de - 1 总和数 - 1 等于 两个数 满足的 方案数。
}
else {
break;
}
}
}
}
cout << ans << endl;
return 0;
}
https://www.bilibili.com/video/bv11L4y1b7JQ
不难发现,用隔板法,组合数学C20204就是答案
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000009
#define endl "\n"
#define PII pair<int,int>
ll ksm(ll a,ll b) {
ll ans = 1;
for(;b;b>>=1LL) {
if(b & 1) ans = ans * a % mod;
a = a * a % mod;
}
return ans;
}
ll lowbit(ll x){return -x & x;}
const int N = 2e6+10;
int n,a[N];
int main()
{
// cout<<691677274345<<endl;
// return 0;
ll ans = 1;
for(ll i = 2020,j = 1;i >= 2017; --i,++j) {
ans *= i;
ans /= j;
}
cout<<ans<<endl;
return 0;
}
//ans = 691677274345
dp+前缀和,dp[i][j]代表使用 j 个正整数组成 i 的方案数,最终输出dp[2021][5]即可。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll dp[2022][6];
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
for (int i = 1; i <= 2021; ++ i) {
dp[i][1] = 1;
}
for (int j = 2; j <= 5; j++) {
for (int i = 1; i <= 2021; i++) {
long long sum = 0;
for (int x = 1; x <= i - j + 1; x++) {
sum += dp[i - x][j - 1];
}
dp[i][j] = sum;
}
}
cout << dp[2021][5];
return 0;
}
枚举前 3 个数,后 2 个数找下规律,开 O2 氧气优化,勉强可以 1s 以内暴力跑出结果。
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
#define DBG(x) cout << #x << "=" << x << endl
#define rep(i, k, n) for (int i = (k); i <= (n); ++i)
using LL = long long;
const int N = 2021;
LL ans;
// 答案:691677274345
// 隔板法 2020C4
void solve() {
rep(a, 1, N - 4)
rep(b, 1, N - a - 3)
rep(c, 1, N - a - b - 2) {
int de = N - a - b - c;
if (de >= 2) {
ans += de - 1;
}
}
cout << ans << endl;
}
int main() {
solve();
// cout << "691677274345" << endl;
return 0;
}
方法一:暴力法(会超时),可以算出来后直接输出答案
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,e,ans;
int main()
{
for(ll a=1;a<=2021;++a)
{
for(ll b=1;b<=2021;++b)
{
for(ll c=1;c<=2021;++c)
{
ll d=2021-a-b-c;
if(d>=2) ans+=d-1;//d-1种分解方法(难点)
else break;
}
}
}
cout<<ans<<"\n";
//ans = 691677274345
return 0;
}
方法二;找规律(隔板法)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll ans=1,b;
int main()
{
b=1;
for(int a=2020;a>=2017;--a)
{
ans*=a;
ans/=b;
b++;
}
cout<<ans<<"\n";
return 0;
}
将暴力的做法进行优化即可得出答案
//#include<stdio.h>
//int main()
//{
// int a,b,c,d,e;
// long long ac=0;
// for (a=1;a<=2021;a++)
// {
// for (b=1;b<=(2021-a);b++)
// {
// for (c=1;c<=(2021-a-b-1);c++)
// {
// ac=ac+(2021-a-b-c-1);
// // printf("A=%d B=%d C=%d ANS=%d\n",a,b,c,ac);
// }
// }
// }
// printf("%lld\n",ac);
//}
#include<stdio.h>
int main()
{
printf("691677274345");
return 0;
}
#根据谢老师发的视频讲解得出的暴力方法,详情请看https://www.bilibili.com/video/bv11L4y1b7JQ#
#include <iostream>
using namespace std;
typedef long long ll;
int main()
{
ll count=0;
for(ll i=1;i<2021;i++)
{
for(ll j=1;j<2021;j++)
{
for(ll u=1;u<2021;u++)
{
ll m=2021-i-j-u;
if(m>=2)
{
count+=m-1;
}
else
break;
}
}
}
cout<<count<<endl;
return 0;
}
直接暴力出答案
#include<bits/stdc++.h>
using namespace std;
int main(){
int num=0;
for(int i=0;i<2018;i++){
for(int j=0;j<2018;j++){
for(int k=0;k<2018;k++){
for(int l=0;l<2018;l++){
for(int m=0;m<2018;m++){
if(i+j+l+k+m==2021){
num++;
}
}
}
}
}
}
cout<<num;
return 0;
}
By signing up a 追梦算法网 universal account, you can submit code and join discussions in all online judging services provided by us.