A 模拟

感觉有歧义，我写的按照每个数字包括几个2， 答案是624 ， 如果写每一年是否包括2就是563

#include <iostream>

using namespace std;

int main()
{
    int res = 0;
    for(int i = 1; i <= 2020; i ++)
    {
        int m = i;
        while(m)
        {
            if(m % 10 == 2)res ++;
            m /= 10;
        }
    }
    cout << res << endl;
    return 0;
}

$624$

B bfs

思路 ：为了保证下标为整数把，所有的横纵坐标扩大2500.

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>

#define x first
#define y second 

using namespace std;
typedef pair<int, int> PII; 
const int N = 7000;
int dist[N][N];
PII id[10] = {{2500, 2500}, {4570, 2511}, {2511, 2514}, {4500, 4500}};
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
void bfs()
{
    queue<PII> q;
    memset(dist, -1, sizeof dist);
    for(int i = 0; i < 4; i ++)
        q.push(id[i]), dist[id[i].x][id[i].y] = 0;
    while(q.size())
    {
        PII t = q.front();
        q.pop();
        if(dist[t.x][t.y] == 2020)continue;

        for(int i = 0; i < 4; i ++)
        {
            int a = t.x + dx[i], b = t.y + dy[i];
            if(dist[a][b]!= -1)continue;

            dist[a][b] = dist[t.x][t.y] + 1;
            q.push({a, b});
        }
    }
} 

int main()
{ 
    bfs();
    int res = 0;
    for(int i = 0; i < N; i ++)
        for(int j = 0; j < N; j ++)
            if(dist[i][j] != -1)res ++;
    cout << res << endl;
    return 0;
} 

$20413113$

C 简单数论

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>

#define x first
#define y second 

using namespace std;
typedef pair<int, int> PII; 
typedef long long LL;
const int N = 110, M = 10000010;
int primes[N], cnt;
bool st[N];
int res[N], idx;
void init(int n)
{
    for(int i = 2; i <= n; i ++)
    {
        if(!st[i])primes[cnt ++] = i;
        for(int j = 0; primes[j] <= n / i; j ++)
        {
            st[primes[j] * i] = true;
            if(i % primes[j] == 0)break;
        }
    }
}

int get(int n, int x)
{
    int res = 0;
    for(int i = n; i; i /= x)res += i / x;
    return res;
}

void mul(int x)
{
    int t = 0;
    for(int i = 0; i < idx; i ++)
    {
        res[i] = t + res[i] * x;
        t = res[i] / 10;
        res[i] %= 10;
    }

    while(t)
    {
        res[idx ++] = t % 10;
        t /= 10;
    }
}
int main()
{ 
    init(N - 1);
    res[idx ++] = 1;
    for(int i = 0; i < cnt && primes[i] <= 100; i ++)
    {
        int t = get(100, primes[i]);
        cout << t << endl;
        mul(t + 1);
    }
    for(int i = idx - 1; i >= 0; i --)cout << res[i];
    return 0;
} 

$39001250856960000$

D 字符串DP

设f[i][j] 为当前在第i为并且以字符为j结尾的个数，因为可能有多个位置的字符相同，可以很容易发现，如果两个字符相同，位置越靠后的字符肯定包括靠前的所有字符的数量，因此最后统计的时候只需要统计靠后的字符即可。

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>

#define x first
#define y second 

using namespace std;
typedef pair<int, int> PII; 
typedef long long LL;
const int N = 2560, M = 10000010;
int primes[N];
bool st[N];
int res[N], idx;
LL f[N][N];
char s[N];
int cnt[N], band[N], temp[N];
int main()
{ 
    cin >> s + 1;
    int n = strlen(s + 1);
    for(int i = n; i; i --)
        cnt[s[i]] ++; // 统计每个字符出现的次数。
    for(int i = 1; i <= n; i ++)
    {
        int j = s[i] - 'a';
        f[i][j] = 1; // 当前字符出现次数肯定为1

        memcpy(temp, band, sizeof band); // 统计出i之前的所有字符出现的次数
        for(int k = 1; k < i; k ++)
            if(-- temp[s[k]] == 0){ // 只有最后一个才值得统计
            if(s[k]< s[i])f[i][j] += f[k][s[k] - 'a']; 
        }
        band[s[i]] ++; // 从前往后依次记录每个字符出现的次数
        cout << i << ' ' << f[i][j] << endl;
    }

    LL res = 0;
    for(int i = 1;i <= n; i ++)
        if(--cnt[s[i]] == 0)
            res += f[i][s[i] - 'a'];
    cout << res << endl;
    return 0;
} 

$3616159$

E 爆搜呀

思路： 依次枚举1号点的位置一共是16个，再依次枚举其余点的位置，就是上下左右四个方向并且该位置没有被用过就可以统计。

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>

#define x first
#define y second 

using namespace std;
typedef pair<int, int> PII; 
typedef long long LL;
int res;
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
const int N = 20;
bool st[N][N];
void dfs(int u, int x, int y)
{
    if(u == 16)
    {
        res ++;
        return ;
    }

    for(int i = 0; i < 4; i ++)
    {
        int a = x + dx[i], b = y + dy[i];
        if(a < 0 || a >= 4 || b < 0 || b >= 4)continue;
        if(st[a][b])continue;
        st[a][b] = true;
        dfs(u + 1, a, b);
        st[a][b] = false;
    }
}
int main()
{   
    for(int i = 0; i < 4; i ++)
        for(int j = 0; j < 4; j ++)
            dfs(1, i, j);
    cout << res << endl;
    return 0;                   
}

$3528$

F 不会 看着好像和分形之城那道题有点关系，又好像没有我太菜了

G 游园安排 最长上升子序列（变形版）

按照最长上升子序列的方法来做，由于要输出字典序最小，需要加一些特殊标记。我试了一些样例过了，如果哪位同学觉得我写的错请指正~

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstdio>

#define x first
#define y second 

using namespace std;
typedef pair<int, int> PII; 
typedef long long LL;
const int N = 1000010, M = 20;
char name[N][20];
int f[N];
int q[N];
int temp[N];
bool check(int x, int y)
{
    int l = strlen(name[x]), r = strlen(name[y]);
    if(l != r)return l > r;
    for(int i = 0; i < l; i ++)
    if(name[x][i] != name[y][i])return name[x][i] > name[y][i];
    return false;
}
int main()
{ 
    string s;
    cin >> s;
    int n = 0;
    for(int i = 0; i < s.size(); i ++)
    {
        int j = i + 1;
        while(j < s.size() && s[j] <= 'z' && s[j] >= 'a')j ++;
        for(int k = i, x = 0; k < j; k ++)
        name[n][x ++] = s[k], name[n][x] = 0;
        n ++;
        i = j - 1;
    } 
    int hh = 0;
    for(int i = 0; i < n; i ++)
    {
        f[i] = 1;
        if(!hh || check(i, q[hh]))// 如果栈为空或者栈顶小于当前值的数就直接加到栈顶
        {
            f[i] = hh + 1;
            q[++ hh] = i;
            for(int i = 1; i <= hh; i ++) // temp数组用来记录被更新过的栈，用于输出答案
            temp[i] = q[i];
            continue;
        }
        int l = 1, r = hh;
        while(l < r)
        {
            int mid = l + r >> 1;
            if(check(q[mid], i) || !strcmp(name[q[mid]], name[i])) r = mid;
            else l = mid + 1;
        }
        f[i] = r;
        q[r] = i;
    }
    int res = 1; // 记录如果后面的坐标都大于前面的坐标说明符合题意，直接输出，反正输出temp数组
    for(int i = 1; i < hh; i ++)
    if(q[i + 1] > q[i])res ++;
    if(res == hh)
    {
        for(int i = 1; i <= hh; i ++)
        printf("%s", name[q[i]]);
    }
    else
    {
        for(int i = 1; i <= hh; i ++)
        printf("%s", name[temp[i]]);
    }
    return 0;
} 

H 答疑 盲猜一波贪心（排序）

按照s + a 排序，样例是过了不知道最后能过几个， 代码就不写了~

I 出租车 题目太长没兴趣看

质数行者 记忆化搜索，由于需要的空间太大只能过一半

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>

#define x first
#define y second 

using namespace std;
typedef pair<int, int> PII; 
typedef long long LL;
const int N = 310, mod = 1000000007, M = 1010;
int primes[M], cnt;
bool st[M];
struct Node
{
    int x, y, z;
}t[2];
int res;
int f[N][N][N];
int n, m, w;

void init(int n)
{
    for(int i = 2; i <= n; i ++)
    {
        if(!st[i])primes[cnt ++] = i;
        for(int j = 0; primes[j] <= n / i; j ++)
        {
            st[primes[j] * i] = true;
            if(i % primes[j] == 0)break;
        }
    }
}

bool check(int x, int y, int z)
{
    for(int i = 0; i < 2; i ++)
        if(x == t[i].x && y == t[i].y && z == t[i].z)return true;
    return false;
}
int dfs(int x, int y, int z)
{
    if(f[x][y][z] != -1)return f[x][y][z];
    int res = 0;
    for(int i = 0; i < cnt; i ++)
    {
        int a = x + primes[i];
        if(a > n || check(a, y, z))continue;
        res = (res + dfs(a, y, z)) % mod;
    }
    for(int i = 0; i < cnt; i ++)
    {
        int a = y + primes[i];
        if(a > m || check(x, a, z))continue;
        res = (res + dfs(x, a, z)) % mod;
    }
    for(int i = 0; i < cnt; i ++)
    {
        int a = z + primes[i];
        if(a > w || check(x, y, a))continue;
        res = (res + dfs(x, y, a)) % mod;
    }
    f[x][y][z] = res;
    return res;
}
int main()
{ 

    memset(f, -1, sizeof f);
    cin >> n >> m >> w;
    int maxd = max(n, m);
    maxd = max(maxd, w);
    init(maxd);
    f[n][m][w] = 1;
    for(int i = 0; i < 2; i ++)
        cin >> t[i].x >> t[i].y >> t[i].z;

    cout << dfs(1, 1, 1) << endl;
    return 0;
}