A - Welcome to AtCoder Land
void solve() {
string s, t;
cin >> s >> t;
if (s == "AtCoder" && t == "Land"){
cout << "Yes\n";
return;
}
cout << "No\n";
}
B - Ticket Counter
题意：n个人排队买票，每个人到达的时间已给出，每个人买票的时间A也给出（一个定值，每个人都相等），问每个人最早什么时候买到票。题目保证每个人到达的时间按非降序排序。
思路：维护一个变量表示上一个人买完票的时间last，分两种情况讨论，第一种情况：当前考虑的第i个人的时间<=last，或者>last。
总结：一开始没好好看题，以为每个人到达的时间是乱序的。这里考虑一下如果时间是乱序的做法：同样的，先将到达的时间非降序排序，然后维护一个last值，依次考虑每次到达的时间，不过这次更新答案的时候，要看这个到达时间对应的是哪个人即可。
booth(售货棚)
void solve() {
int n, d;
cin >> n >> d;
vector<int> a(n);
for (auto& x : a){
cin >> x;
}
int last = 0;
for (int i = 0; i < n; ++i){
if (a[i] >= last){
cout << a[i] + d << '\n';
last = a[i] + d;
}
else{
cout << last + d << '\n';
last += d;
}
}
}
下面是假如到达时间是乱序的代码：
void solve() {
int n, A;
cin >> n >> A;
vector<int> a(n);
for (int i = 0; i < n; ++i){
cin >> a[i];
}
vector<int> pos(n);
iota(pos.begin(), pos.end(), 0);
sort(pos.begin(), pos.end(), [&](const int& i, const int& j){
return a[i] < a[j];
});
int last = 0;
vector<int> ans(n);
for (int i = 0; i < n; ++i){
int x = a[pos[i]];
if (x <= last){
last += A;
}
else{
last = x + A;
}
ans[pos[i]] = last;
}
for (int i = 0; i < n; ++i){
cout << ans[i] << "\n";
}
}
C - Popcorn
题意：给定n个长度为m的字符串，串中包含'o'或者’x'，如果第i个字符是o说明第i中popcorn在当前的字符串中可以买到，否则不行。问至少逛多少个字符串可以买到所有口味的popcorn。
思路：n, m <= 10，直接dfs暴力遍历即可。
总结：暴力传参字符串的时候，要有一个回溯的过程，如果传递的字符串是引用，要手动回溯一下，或者直接传递一个临时字符串过去。
popcorn（爆米花）, flavor(风味)， stand（货摊），
void solve() {
int n, m;
cin >> n >> m;
vector<string> s(n);
for (auto& x : s){
cin >> x;
}
int ans = n + 1;
function<void(int, int, int, string)> dfs = [&](int idx, int p, int cnt, string cur){
if (idx == p){
if (count(cur.begin(), cur.end(), 'o') == m){
ans = min(ans, cnt);
}
return;
}
dfs(idx + 1, p, cnt, cur);
auto temp = cur;
for (int i = 0; i < m; ++i){
if (s[idx][i] == 'o'){
temp[i] = 'o';
}
}
dfs(idx + 1, p, cnt + 1, temp);
};
dfs(0, n, 0, string(m, 'x'));
cout << ans << endl;
}
D - Souvenirs
题意：n个物品，每个物品的价格和价值相等，m个人，每个人至少得到价值为给定数值的candy。问最少需要花费多少money，能让m个人都得到对应的candy。如果不能满足，输出-1.
思路：该场景对糖果和分配的顺序没有要求，直接将物品和每个人需要的价值按非降序排序，然后双指针遍历即可。
总结：如果能一次排序完成的话，可以不考虑用堆，感觉是多次一举。降序排序规则是大顶堆，升序排序规则是小顶堆。（反正就是于正常的排序规则相反就对了）
souvenirs（纪念品）,yen（日元）
void solve() {
int n, m;
cin >> n >> m;
vector<int> a(n);
for (auto& x : a){
cin >> x;
}
vector<int> b(m);
for (auto& x : b){
cin >> x;
}
sort(a.begin(), a.end());
sort(b.begin(), b.end());
int i = 0, j = 0;
long long ans = 0;
while (i < n && j < m){
if (a[i] >= b[j]){
ans += a[i];
i ++;
j ++;
}
else {
i ++;
}
}
cout << (j == m ? ans : -1ll) << endl;
}
E - Alphabet Tiles
题意：求长度为1~k的只包含大写字母的字符串中，有多少字符串满足要求。要求：每个字母出现的次数不能超过给定的数值。
思路：背包dp，物品在外，容量在内，因为摆放可以乱序，所以在插入物品时，要考虑所有可能的排列，要知道当前考虑的物品数量在插入时，有多少种插入方式。
总结： 这个题目想了一个小时没想出来，为什么，因为思维卡死在背包容量在外面了，于是第一层for循环是背包容量，内层for循环是遍历在上一层背包容量中，每种字母所有可能的剩余方案。 这个时间复杂度巨大，特别是字母数量能达到1000的情况。。对于这种每个物品限制了数量的题目，应该考虑到：1、对于每个可能的背包容量，当前物品可能在该背包中是任意可能的合法值。2、对于任意可能的合法数量，必须由还没有考虑该物品时的状态转移过来。 考虑到这两点后，就能正确的理解并写出转移方程了。
对于组合数：按杨辉三角来递推，每行的首项（第0项）和最后一项为1。递推的时候，要计算第1~i-1项。
代码段中的MInt是一个自动计算模数的数据结构，如有需要请移步
https://github.com/yxc-s/programming-template/blob/master/NumberTheory/ModularInteger.cpp
nameplate(名牌，标识牌)
array<array<MInt, 1234>, 1234> combi;
void preProcess() {
for (int i = 0; i <= 1000; ++i){
combi[i][0] = combi[i][i] = 1;
}
for (int i = 1; i <= 1000; ++i){
for (int j = 1; j < i; ++j){
combi[i][j] = combi[i - 1][j - 1] + combi[i - 1][j];
}
}
}
void solve() {
int k;
cin >> k;
array<int, 26> c;
for (int i = 0; i < 26; ++i){
cin >> c[i];
}
vector<vector<MInt>> dp(27, vector<MInt> (k + 1));
int cur = 0;
dp[cur][0] = 1;
for (int i = 0; i < 26; ++i){
cur ^= 1;
fill(dp[cur].begin(), dp[cur].end(), (MInt)(0));
for (int j = 0; j <= k; ++j){
for (int k = 0; k <= min(c[i], j); ++k){
dp[cur][j] += dp[cur ^ 1][j - k] * combi[j][k];
}
}
}
MInt ans = 0;
for (int j = 1; j <= k; ++j){
ans += dp[cur][j];
}
cout << ans << endl;
}
后面的题不补了。
如果该博客对您有帮助，请您关注我的git仓库。
https://github.com/yxc-s/programming-template/tree/master
该仓库是一个新仓库，旨在打造一个通用的C++算法编程竞赛模板，包含数据结构，数论等各种实用的算法编程模板。如果您使用的语言不是C++，也可以将对应的代码实现翻译成其他语言来使用。