C - 高橋君とカード / Tak and Cards
dp。记dp[i][j]为选了i张牌，和为j的方案数。
#include#include using namespace std;long long dp[55][2505], ans;int n, a, m;int main() { scanf("%d%d", &n, &a); dp[0][0] = 1; m = a * n; for (int t, i = 1; i <= n; ++i) { scanf("%d", &t); for (int j = i; j; --j) for (int k = m; k >= t; --k) dp[j][k] += dp[j-1][k-t]; } for (int i = 1; i <= n; ++i) ans += dp[i][i*a]; printf("%lld\n", ans); return 0;}
D - 桁和 / Digit Sum
这题很妙啊！
一句话题意：一个数N在b进制下表示为
。记
。现在告诉你
和
，请你求出满足条件的最小的
，如果这样的
不存在，请输出-1。
把分为两种情况讨论。
当
时：
直接枚举。
当
时：
显然
。又因为
。所以
。
和是已知的，只需要枚举
的因数
即可。
#include#include #include using namespace std;typedef long long ll;ll s, n, m;ll f(ll b, ll n) { return n < b ? n : f(b, n / b) + n % b;}int main() { cin >> n >> s; m = sqrt(n) + 1; if (s > n) return puts("-1"), 0; if (s == n) return printf("%lld\n", s + 1), 0; for (ll i = 2; i <= m; ++i) if (f(i, n) == s) return printf("%lld\n", i), 0; ll b, q, res = 1e11; n -= s; for (ll p = 1; p * p <= n; ++p) { if (n % p == 0 ) { b = n / p + 1; q = s - p; if (q >= 0 && b >= 2 && q < b && p < b) res = min(res, b); } } printf("%lld\n", res == 1e11 ? -1 : res); return 0;}