蓝桥杯 2020 国赛

　A

#include <bits/stdc++.h>
#define sc(x) scanf("%lld", &(x))
#define pr(x) printf("%d\n", (x))
#define rep(i, l, r) for (int i = l; i <= r; ++i)
using namespace std;
typedef long long ll;
const int N = 1e5 + 7;
const int mod = 1e9 + 7;
bool chk(int n) {
    while (n) {
        if (n % 10 == 2) return 1;
        n /= 10;
    }
    return 0;
}
int main() {
    int res = 0;
    rep(i, 1, 2020) res += chk(i);
    pr(res);  // 563
    return 0;
}

B

#include <bits/stdc++.h>
#define pr(x) printf("%d\n", (x))
#define rep(i, l, r) for (int i = l; i <= r; ++i)
using namespace std;
typedef long long ll;
#define id(x) x + 2500
const int N = id(5007);
bool a[N][N];
void spread(int x, int y, int sz = 2020) {
    rep(i, 0, 2020) {
        a[y + i][x] = 1;
        a[y - i][x] = 1;
        rep(j, 1, sz) {
            a[y + i][x + j] = 1;
            a[y + i][x - j] = 1;
            a[y - i][x + j] = 1;
            a[y - i][x - j] = 1;
        }
        --sz;
    }
}
int main() {
    spread(id(0), id(0));
    spread(id(2020), id(11));
    spread(id(11), id(14));
    spread(id(2000), id(2000));
    int res = 0;
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
            if (a[i][j]) ++res;
    pr(res);  // 20312088
    return 0;
}

C

#include <bits/stdc++.h>
#define pr(x) printf("%lld\n", (x))
#define rep(i, l, r) for (int i = l; i <= r; ++i)
using namespace std;
typedef long long ll;
const int N = 105;
vector<int> primes;
bitset<N> isPrime;
void sieve() {
    isPrime.set();
    isPrime[0] = isPrime[1] = 0;
    for (int i = 2; i < N; ++i) {
        if (isPrime[i]) primes.emplace_back(i);
        for (int p : primes) {
            if (i * p >= N) break;
            isPrime[i * p] = 0;
            if (i % p == 0) break;
        }
    }
}
map<int, ll> cnt;
void div(int n) {
    for (int p : primes) {
        if (n % p == 0)
            while (n % p == 0) n /= p, ++cnt[p];
        if (isPrime[n]) {
            ++cnt[n];
            return;
        }
    }
}
int main() {
    sieve();
    rep(i, 1, 100) div(i);
    ll res = 1;
    for (auto p : cnt) res *= p.second + 1;  // 每个幂次都可以选或者不选
    pr(res);                                 // 39001250856960000
    return 0;
}

D

#include <bits/stdc++.h>
#define sc(x) scanf("%lld", &(x))
#define pr(x) printf("%lld\n", (x))
#define rep(i, l, r) for (int i = l; i <= r; ++i)
using namespace std;
typedef long long ll;
const int N = 207;
const int mod = 1e9 + 7;
char s[N] =
    " tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhfiadgdcdjstemphmnjihecoa"
    "pdjjrprrqnhgccevdarufmliqijgihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvf"
    "madvrnaaahahndsikzssoywakgnfjjaihtniptwoulxbaeqkqhfwl";
ll dp[N], ans;
set<char> vis[N];
int main() {
    // scanf("%s", s + 1);
    int n = strlen(s + 1);
    rep(i, 1, n) {
        dp[i] = 0;
        if (!vis[0].count(s[i])) dp[i] += 1, vis[0].insert(s[i]);
        for (int j = 1; j < i; ++j) {
            if (s[i] > s[j]) {
                if (!vis[j].count(s[i])) {
                    dp[i] += dp[j];
                    vis[j].insert(s[i]);
                }
            }
        }
        ans += dp[i];
    }
    pr(ans);  // 3616159
    return 0;
}

E

#include <bits/stdc++.h>
#define sc(x) scanf("%lld", &(x))
#define pr(x) printf("%lld\n", (x))
#define rep(i, l, r) for (int i = l; i <= r; ++i)
using namespace std;
typedef long long ll;
const int N = 5;
const int mod = 1e9 + 7;
int a[5][5], ans;
int dx[] = {0, 0, -1, 1};
int dy[] = {1, -1, 0, 0};
void dfs(int id, int x, int y) {
    a[x][y] = id;
    if (id == 16) {
        ++ans;
        return;
    }
    rep(i, 0, 3) {
        int xx = x + dx[i];
        int yy = y + dy[i];
        if (xx >= 1 and xx <= 4 and yy >= 1 and yy <= 4 and !a[xx][yy]) {
            dfs(id + 1, xx, yy);
            a[xx][yy] = 0;
        }
    }
}
int main() {
    rep(i, 1, 4) rep(j, 1, 4) {
        memset(a, 0, sizeof a);
        dfs(1, i, j);
    }
    printf("%d", ans);  // 552
    return 0;
}

F

G

#include <bits/stdc++.h>
#define sc(x) scanf("%lld", &(x))
#define pr(x) printf("%lld\n", (x))
#define rep(i, l, r) for (int i = l; i <= r; ++i)
using namespace std;
typedef long long ll;
const int N = 1e5 + 7;
const int mod = 1e9 + 7;
#define sub(l, r) s.substr(l, r - l + 1)
struct node {
    string s;
    int id;
    int ord;
};
vector<node> a;
int LIS(int a[], int n) {
    int len = 1;
    int d[N];
    d[1] = a[1];
    rep(i, 2, n) {
        if (a[i] > d[len])
            d[++len] = a[i];
        else {
            int j = lower_bound(d + 1, d + 1 + len, a[i]) - d;
            d[j] = a[i];
        }
    }
}
int main() {
    string s = "WoAiLanQiaoBei";

    int lst = 0;
    for (int i = 1, n = s.length(); i < n; ++i)
        if (isupper(s[i])) {
            a.push_back({sub(lst, i - 1), 0, 1});
            lst = i;
        }

    a.push_back({s.substr(lst), 0, 1});
    for (int i = 0; i < a.size(); ++i) a[i].id = i + 1;
    sort(a.begin(), a.end(), [&](node u, node v) { return u.s < v.s; });

    for (int i = 1, n = a.size(); i < n; ++i)
        if (a[i - 1].s < a[i].s)
            a[i].ord = a[i - 1].ord + 1;
        else
            a[i].ord = a[i - 1].ord;
    sort(a.begin(), a.end(), [&](node u, node v) { return u.id < v.id; });

    // LIS
    return 0;
}

H

#include <bits/stdc++.h>
#define sc(x) scanf("%lld", &(x))
#define pr(x) printf("%lld\n", (x))
#define rep(i, l, r) for (int i = l; i <= r; ++i)
using namespace std;
typedef long long ll;
const int N = 1e3 + 7;
const int mod = 1e9 + 7;
struct node {
    int pre, e;
} a[N];
int n, u, v;
ll cal() {
    ll res = 0, now = 0;
    rep(i, 1, n) {
        now += a[i].pre;
        res += now;
        now += a[i].e;
    }
    return res;
}
int main() {
    scanf("%d", &n);
    rep(i, 1, n) {
        scanf("%d%d%d", &u, &v, &a[i].e);
        a[i].pre = u + v;
    }
    sort(a + 1, a + 1 + n,
         [&](node u, node v) { return u.pre + u.e < v.pre + v.e; });
    ll res = cal();
    rep(i, 1, n - 1) {
        swap(a[i], a[n]);
        res = min(cal(), res);
        swap(a[i], a[n]);
    }
    pr(res);
    return 0;
}
/*
3
10000 10000 10000
20000 50000 20000
30000 20000 30000
*/