AtCoder Beginner Contest 044 C D
文章目錄
- AtCoder Beginner Contest 044 C D
-
- C
-
- 題目
- 題目大意
- 思路
- 代碼
- D
-
- 題目
- 思路
- 代碼
C
題目
題目大意
在n張牌中有多少種選法，可以使這幾張牌的平均值為A
思路
dp
有一說一dp還真的是我的弱項
對于這道題我的想法是2^25的二進制暴力相加之後meet in the middle，但是因為最後的組合數學不大會，而且複雜度比較迷幻，是以放棄了
那麼這一題給我最大的教育就是，以後對于要選取多少個數字的時候，如果複雜度允許，可以考慮背包，dp
d p [ i ] [ j ] 表 示 選 取 前 i 張 牌 和 為 j 的 方 案 數 量 ， 那 麼 轉 移 方 程 為 d p [ i ] [ j ] + = d p [ i − 1 ] [ j − x ] dp[i][j]表示選取前i張牌和為j的方案數量，那麼轉移方程為dp[i][j] += dp[i - 1][j - x] dp[i][j]表示選取前i張牌和為j的方案數量，那麼轉移方程為dp[i][j]+=dp[i−1][j−x]
代碼
#include <iostream>
#include <cstdio>
#include <set>
#include <list>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <string>
#include <sstream>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <fstream>
#include <iomanip>
//#include <unordered_map>
using namespace std;
#define dbg(x) cerr << #x " = " << x << endl;
typedef pair<int, int> P;
typedef long long ll;
const int MAXN = 55;
ll a[MAXN];
ll dp[55][55*55];
int main()
{
//freopen("in.txt", "r", stdin);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll n, A;
cin >> n >> A;
for(int i = 1; i <= n; i++)
{
cin >> a[i];
}
dp[0][0] = 1;
for(int i = 1; i <= n; i++)
{
for(int j = i; j > 0; j--)
{
for(int k = A * n; k >= a[i]; k--)
{
dp[j][k] += dp[j - 1][k - a[i]];
}
}
}
ll ans = 0;
for(int i = 1; i <= n; i++)
{
ans += dp[i][i *A];
}
cout << ans << endl;
}
D
題目
思路
不得不說真的妙啊
受教了
數論nb
代碼
#include <iostream>
#include <cstdio>
#include <set>
#include <list>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <string>
#include <sstream>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <fstream>
#include <iomanip>
//#include <unordered_map>
using namespace std;
#define dbg(x) cerr << #x " = " << x << endl;
typedef pair<int, int> P;
typedef long long ll;
ll f(ll b, ll n)
{
ll ans = 0;
while(n)
{
ans += n % b;
n /= b;
}
ans += n;
return ans;
}
int main()
{
// freopen("in.txt", "r", stdin);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll n, s;
cin >> n >> s;
ll b = -1;
if(s > n)
{
cout << -1 << endl;
}
else if(s == n)
{
cout << n + 1 << endl;
}
else
{
for(ll i = 2; i <= sqrt(n) + 1; i++)
{
if(f(i, n) == s)
{
b = i;
break;
}
}
if(b != -1)
{
cout << b << endl;
return 0;
}
if(b == -1)
{
for(ll i = 1; i <= sqrt(n - s) + 1; i++)
{
if((n - s) % i == 0)
{
ll x1 = i;
ll x0 = s - x1;
ll tmpb = (n - s) / i + 1;
if(x1 < tmpb && x0 < tmpb && x0 >= 0 && tmpb >= 2)
{
if(b == -1) b = tmpb;
else
b = min(b, tmpb);
}
}
}
cout << b << endl;
}
}
}