USACO题库题解——Section1.1

USACO刷题计划Section1.1

你的飞碟在这儿Your Ride Is Here

这道题太水了，不讲了，直接上代码。

不过对于初学字符串的选手是道好题。

#include <iostream>
using namespace std;
int main() {
    string s;
    cin >> s;
    int a = 1, b = 1;
    for (int i = 0; i < s.length(); i++) a = (a * (s[i] - 'A' + 1)) % 47;
    cin >> s;
    for (int i = 0; i < s.length(); i++) b = (b * (s[i] - 'A' + 1)) % 47;
    cout << (a == b ? "GO" : "STAY");
    return 0;
}

贪婪的送礼者Greedy Gift Givers

STL大法好！

这道题其实就是一个简单的模拟，关键是我们要怎么知道哪个名字对应哪个人。

当然我们可以用字符串哈希来映射，这里我介绍一个更简单的方法——map（映射）。

map其实就是从key（关键值）到value（实际值）之间的映射。通过“[]”来解析关键值（有点像数组，可以理解为下标为任意类型的数组）。

map的定义很简单，如下

#include <map>
map<type, type> a;//变量名

type是任意数据类型。

而它的用法也很简单，我们这道题只用简单的映射关系。

//下面是一个简单的应用
#include <iostream>
#include <cstdio>
#include <map>
using namespace std;
map<string, int> a;
map<string, char> b;
int main() {
    a["333"] = 1000;
    cout << a["333"] <<endl;
    b["123"] = 'a';
    cout << b["123"] << endl; 
    return 0;
}

输出结果

回到此题，我们定义两个map，一个叫give代表给出去的钱，一个叫get代表拿到的前。

它们都是从string映射到int的。give[s]代表叫s的人给出去的钱，get同理。

这样没输入一个名字就很好处理了，剩下部分我就不讲了。

还要注意两个点：

1，如果给0个人则没有给出任何钱直接continue即可。

2，钱没有分数，所以给到每个人的钱要向下取整，即给出去的钱不一定是原有的钱。

#include <iostream>
#include <cstdio>
#include <map>
using namespace std;
map<string, int> Get, Give;
string name[100];
int n;
string s;
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> name[i];
    }
    for (int i = 1; i <= n; i++) {
        cin >> s;
        int p, q;
        cin >> p >> q;
        if (q == 0) {
            continue;//不给任何人直接continue
        }
        Give[s] += p / q * q;//不一定要全部给出
        for (int j = 1; j <= q; j++) {
            cin >> s;
            Get[s] += p / q;
        }
    }
    for (int i = 1; i <= n; i++) {
        cout << name[i] << " " << Get[name[i]] - Give[name[i]] << endl;
    }
    return 0;
}

map虽然好写，但它的底层实现是一棵红黑树，复杂度是log级别的（虽然此题无伤大雅），慎用。

黑色星期五Friday the Thirteenth

暴力枚举。

直接枚举年份，月份和日期，如果是13号就统计。

统计是用一个变量记录经过了多少天，模7就得到今天是星期几（星期日就是0）。

#include <iostream>
#include <cstdio>
using namespace std;
int n;
int ans[10];
int days[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int cnt;
bool check(int x) {
    if (x % 400 == 0) return 1;
    if (x % 100 != 0 && x % 4 == 0) return 1;
    return 0;
}
int main() {
    scanf("%d", &n);
    for (int i = 1900; i <= 1900 + n - 1; i++) {
        for (int j = 1; j <= 12; j++) {
            if (j != 2) {
                for (int k = 1; k <= days[j]; k++) {
                    cnt++;
                    if (k == 13) {
                        ans[cnt % 7]++;
                    }
                }
            } else {
                if (check(i)) {
                    for (int k = 1; k <= days[j] + 1; k++) {
                        cnt++;
                        if (k == 13) {
                            ans[cnt % 7]++;
                        }
                    }
                } else {
                    for (int k = 1; k <= days[j]; k++) {
                        cnt++;
                        if (k == 13) {
                            ans[cnt % 7]++;
                        }
                    }
                }
            }
        }
    }
    printf("%d %d %d %d %d %d %d", ans[6], ans[0], ans[1], ans[2], ans[3], ans[4], ans[5]);
    return 0;
}

时间复杂度；$O(N imes 365)$

坏掉的项链Broken Necklace

持续更新

你可能想找：USACO题库刷题计划