C - Popcorn
思路：从集合 S 中选出非空子集，使得子集中糖果口味有 M 种。观察到集合 S 中的元素数量 n<=10。因此，总共的子集数为 C<=2^10-1，考虑枚举所有的子集。
代码：
#include <bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define ios ios::sync_with_stdio(0)
#define endl '\n'
#define pii pair<int, int>
#define debug(x) cout << "x = " << x << endl;
#define lowbit(x) (x & (-x))
using namespace std;
const int N = 5e2 + 5, P = 13331;
int n, m, key;
int a[N];
bool vst[N];
bool dfs(int d, int x, int num, int last)
{
if (d > x)
{
if (num == key)
return true;
else
return false;
}
for (int i = last + 1; i <= n; i++)
{
if (vst[i])
continue;
vst[i] = 1;
if (dfs(d + 1, x, num | a[i], i))
return true;
vst[i] = 0;
}
return false;
}
bool check(int x)
{
memset(vst, 0, sizeof(vst));
return dfs(1, x, 0, 0);
}
void solve()
{
int T = 1;
// cin>>T;
while (T--)
{
cin >> n >> m;
key = (1 << m) - 1;
string s;
for (int i = 1; i <= n; i++)
{
cin >> s;
int num = 0;
for (int j = 0; j < s.size(); j++)
{
if (s[j] == 'o')
num = num | (1 << j);
}
a[i] = num;
}
int l = 0, r = n + 1;
while (l + 1 < r)
{
int mid = (l + r) / 2;
if (check(mid))
r = mid;
else
l = mid;
}
cout << r;
}
}
signed main()
{
ios;
solve();
return 0;
}
D - Souvenirs
思路：对于每一个 Bi，我们可以贪心的去找最接近 Bi 的 Aj,且满足 Aj>= Bi。这一操作我们可以利用二分在 logn 内完成。同时，题目要求不允许给一个人多个盒子，也不允许给多个人同一个盒子。因此，我们还需要在 logn 的时间复杂度内删除 Aj。使用multiset维护即可。
代码：
#include <bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define ios ios::sync_with_stdio(0)
#define endl '\n'
#define pii pair<int, int>
#define debug(x) cout << "x = " << x << endl;
#define lowbit(x) (x & (-x))
using namespace std;
const int N = 5e5 + 5, P = 13331;
int n, m;
multiset<int> st;
void solve()
{
int T = 1;
// cin>>T;
while (T--)
{
cin >> n >> m;
for (int i = 1,x; i <= n; i ++)
{
cin >> x;
st.emplace(x);
}
int cost = 0;
for (int i = 1, x; i <= m; i ++)
{
cin >> x;
auto it = st.lower_bound(x);
if(it == st.end())
{
cout << -1;
return;
}
cost += *it;
st.erase(it);
}
cout << cost;
}
}
signed main()
{
ios;
solve();
return 0;
}
E - Alphabet Tiles
思路：观察到这是一道计数题，计数题通常解法为组合数学和动态规划，可以发现本题的数据规模较小。因此，考虑动态规划。不难发现，这其实是一道分组背包的变形，我们令 DPi,j 表示前 i 组中，选用 j 个字母的方案数。转移方程为 ：
\[dp(i,j) = \sum_{k=0}^j(dp(i-1,j-k)*C_j^k) \]代码：
#include <bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define ios ios::sync_with_stdio(0)
#define endl '\n'
#define pii pair<int, int>
#define debug(x) cout << "x = " << x << endl;
#define lowbit(x) (x & (-x))
using namespace std;
const int N = 1e3 + 5, P = 998244353;
int k, c[N];
int f[N][N], dp[N][N];
void solve()
{
int T = 1;
// cin>>T;
while (T--)
{
cin >> k;
for (int i = 1; i <= 26; i++)
{
cin >> c[i];
}
f[0][0] = dp[0][0] = 1;
for (int i = 1; i <= k; i++)
{
f[i][0] = 1;
for (int j = 1; j <= i; j++)
{
f[i][j] = (f[i - 1][j] + f[i - 1][j - 1]) % P;
}
}
for (int i = 1; i <= 26; i++)
{
for (int j = 0; j <= k; j++)
{
for (int z = 0; z <= j && z <= c[i]; z++)
{
dp[i][j] = (dp[i][j] + dp[i - 1][j - z] * f[j][z]) % P;
}
}
}
int ans = 0;
for (int i = 1; i <= k; i++)
{
ans = (ans + dp[26][i]) % P;
}
cout << ans << endl;
}
}
signed main()
{
ios;
solve();
return 0;
}