当前位置: 代码迷 >> 综合 >> Codeforces Round #493 (Div. 2) D. Roman Digits
  详细解决方案

Codeforces Round #493 (Div. 2) D. Roman Digits

热度:39   发布时间:2023-10-29 05:55:47.0

题意

你现在有n个格子,每个格子必须填入1,5,10,50中的一个数,问你有多少种不同的和

前言

菜鸡选手已经只能做div2
还好之前上了个紫,要不现在就要蓝能不能上都是问题

题解

想了挺久。。但其实并不难
我们先把序列全部填1,解决每个格子都有数的限制
然后发现,我们可以对总和造成+4,+9,+49+4,+9,+49的变化
如果一个数有多种变化方式,那么取次数最少的一次
于是可以得到
4?9=9?44?9=9?4因此,填44的个数不超过 9
9?49=49?99?49=49?9因此,填99的个数不超过 49
除此之外,我们还发现
4?8+49=9?94?8+49=9?9,因此,如果44个个数是 8 ,那么4949的个数不能超过11
9 ? 14 = 4 ? 7 + 2 ? 49 ,因此,99的个数不超过 14
容易证明,没有别的步数替代方式了
于是得到做法:

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
typedef long long LL;
LL n;
//vector<LL> a;
int main()
{scanf("%lld",&n);LL ans=0;for (LL u=0;u<=8;u++)for (LL i=0;i<14;i++)if (u+i<=n){if (u>=1&&i>=5) continue;LL lalal=0;LL t=(n-u-i);if (u==8) ans++;else ans=ans+t+1;}printf("%lld\n",ans);return 0;
}
  相关解决方案