A - Legendary Players

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <sstream>
#include <vector>
#include <cmath>
#include <stack>
#include <map>
#include <queue>
#include <set>

using namespace std;
#define PII pair<int,int>
typedef long long LL;
const int N = 1e5 + 10;

int main()
{
    map<string,int> rankings;
    rankings["tourist"] = 3858;
    rankings["ksun48"] = 3679;
    rankings["Benq"] = 3658;
    rankings["Um_nik"] = 3648;
    rankings["apiad"] = 3638;
    rankings["Stonefeang"] = 3630;
    rankings["ecnerwala"] = 3613;
    rankings["mnbvmar"] = 3555;
    rankings["newbiedmy"] = 3516;
    rankings["semiexp"] = 3481;

    string s; cin >> s;
    cout << rankings[s] << endl;

    return 0;
}

B - Measure

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <sstream>
#include <vector>
#include <cmath>
#include <stack>
#include <map>
#include <queue>
#include <set>

using namespace std;
#define PII pair<int,int>
typedef long long LL;
const int N = 1e5 + 10, M = N * 2;

int main()
{
    int n; cin >> n;
    for (int i = 0; i <= n; i ++)
    {
        int s = -1;
        for (int j = 1; j <= 9; j ++)
        {
            if (n % j == 0 && i % (n / j) == 0) 
            {
                s = j;
                break;
            }
        }
        if (s != -1) cout << s;
        else cout << "-";
    }

    return 0;
}

C - False Hope

使用全排列函数生成所有可能的顺序，然后对所有的情况进行判断找到答案。注意本题中判断三个相邻位置上数的同时只要确保先后顺序一致即可，而不需要看的顺序相邻。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <sstream>
#include <vector>
#include <cmath>
#include <stack>
#include <map>
#include <queue>
#include <set>

using namespace std;
#define PII pair<int,int>
typedef long long LL;
const int N = 20, M = N * 2;
int g[N], p[N], s[N];

int check(int x, int y, int z)
{
    // 枚举三个数的所有可能顺序并与当前顺序进行判断
    if (g[x] == g[y] && ((s[x] < s[y] && s[y] < s[z]) || (s[y] < s[x] && s[x] < s[z]))) return 0;
    if (g[x] == g[z] && ((s[x] < s[z] && s[z] < s[y]) || (s[z] < s[x] && s[x] < s[y]))) return 0;
    if (g[y] == g[z] && ((s[y] < s[z] && s[z] < s[x]) || (s[z] < s[y] && s[y] < s[x]))) return 0;
    return 1;
}

int main()
{
    int n = 9;
    for (int i = 1; i <= n; i ++) cin >> g[i];
    for (int i = 1; i <= n; i ++) p[i] = i;

    int res = 0;
    // 枚举所有查看的顺序
    do {
        for (int i = 1; i <= n; i ++)
            s[p[i]] = i; // 记录每个点查看的顺序
        if (check(1, 2, 3) && check(4, 5, 6) && check(7, 8, 9) && check(1, 4, 7) && check(2, 5, 8) && check(3, 6, 9) && 
            check(1, 5, 9) && check(3, 5, 7))
            res ++;
    } while(next_permutation(p + 1, p + 10));

    printf("%.10lf\n", res / 362880.0);

    return 0;
}

D - Minimum Width

二分答案，然后在O(n)的时间复杂度内进行模拟判断

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <sstream>
#include <vector>
#include <cmath>
#include <stack>
#include <map>
#include <queue>
#include <set>

using namespace std;
#define PII pair<int,int>
#define int long long
typedef long long LL;
const int N = 2e5 + 10, M = N * 2;
int a[N], maxv;
int n, m;

bool check(int w)
{
    if (maxv > w) return false;
    int cnt = 1, k = w;
    for (int i = 0; i < n; i ++)
    {
        if (k != w) {
            if (k - a[i] - 1 < 0) {
                cnt ++;
                k = w - a[i];
            } else k = k - a[i] - 1;
        } else k -= a[i];
    }

    return cnt <= m;
}

signed main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i ++) cin >> a[i], maxv = max(maxv, a[i]);

    int l = 0, r = 1e18;
    while (l < r)
    {
        int mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }

    cout << l << endl;

    return 0;
}

E - Bus Stops

容易注意到我们只需计算所有约数的最小公倍数即可得到所有的情况，最后加上初始的时间即可。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <sstream>
#include <vector>
#include <cmath>
#include <stack>
#include <map>
#include <queue>
#include <set>

using namespace std;
#define PII pair<int,int>
#define int long long
typedef long long LL;
const int N = 2e5 + 10, M = N * 2;
int res[850];
int X, Y, n;
int P[N], T[N];

int get(int x, int p)
{
    if (x % p == 0) return 0;
    return (x / p + 1) * p - x;
}

signed main()
{
    cin >> n >> X >> Y;

    for (int i = 0; i < n - 1; i ++) cin >> P[i] >> T[i];

    for (int j = 0; j <= 840; j ++) 
    {
        int t = j + X;
        for (int i = 0; i < n - 1; i ++) 
        {
            int t1 = get(t, P[i]), t2 = T[i];
            t += t1 + t2;
        }
        t += Y;
        res[j] = t;
    }

    int q; cin >> q;
    while (q --)
    {
        int x; cin >> x;
        cout << res[x % 840] + x / 840 * 840 << endl;
    }

    return 0;
}