2022年上海市大学生程序设计竞赛

N.Nine Is Greater Than Ten(签到）

直接比较字典序。

#include <bits/stdc++.h>
using namespace std;
int main()
{
    string a, b;
    cin >> a >> b;
    if (a > b)
    {
        cout << a << ">" << b << "\n";
    }
    else if (a < b)
    {
        cout << a << "<" << b << "\n";
    }
    else
    {
        cout << a << "=" << b << "\n";
    }
    return 0;
}

G.Gua!(签到)

细节比较多的签到，主要是0的问题。若R = 0，那么一枪都开不出，否则能开出 ⌊RxS/60⌋ + 1枪。

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        int b, r, d, s;
        scanf("%d%d%d%d", &b, &r, &d, &s);
        if (r == 0)
        {
            if (d > 0)
            {
                printf("gua!\n");
            }
            else
            {
                printf("ok\n");
            }
        }
        else if (s == 0)
        {
            if (d > b)
            {
                printf("gua!\n");
            }
            else
            {
                printf("ok\n");
            }
        }
        else
        {
            int ans = s * r;
            int cnt;
            cnt = (ans / 60 + 1) * b;
            if (d > cnt)
            {
                printf("gua!\n");
            }
            else
            {
                printf("ok\n");
            }
        }
    }
    return 0;
}

E.Expenditure Reduction（dp）

题意：给一个字符串S，和S一个子序列F。求最短的S的子串T，使F也是T的子序列。

思路：正解是dp（还可以枚举二分卡过去）

dp[i][j]表示S到i，F匹配到第j位的最短长度。

若s[i] != f[j]， 则dp[i][j] = min(dp[i][j], dp[i - 1][j] + 1);

若s[i] == f[j]，则dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + 1);

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int dp[N][108];
const int INF = 0x3f3f3f3f;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int tt;
    cin >> tt;
    while (tt--)
    {
        string s, f;
        cin >> s >> f;
        int n = s.size();
        int m = f.size();
        s = '#' + s;
        f = '#' + f;
        for (int i = 0; i <= n; i++)
        {
            for (int j = 1; j <= m; j++)
            {
                dp[i][j] = INF;
            }
        }
        dp[0][0] = 0;
        int pos = 0;
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= m; j++)
            {
                if (s[i] == f[j])
                {
                    dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + 1);
                }
                else
                {
                    dp[i][j] = min(dp[i][j], dp[i - 1][j] + 1);
                }
            }
            if (dp[pos][m] > dp[i][m])
            {
                pos = i;
            }
        }
        // cout << pos << " " << dp[pos][m] << "\n";
        for (int i = pos - dp[pos][m] + 1; i <= pos; i++)
        {
            cout << s[i];
        }
        // cout << s + pos - dp[pos][m] + 1;
        cout << "\n";
    }
    return 0;
}

H.Heirloom Painting（模拟，贪心）

题意：用刷子刷长度为n的墙，每次用一种颜色刷连续的长度为k的一段，后刷的颜色会覆盖前刷的颜色。问给定结果，最小的刷墙次数。

思路：容易想到，如果结果中根本没有长度不小于k的一段颜色相同，那么不可能刷出来，否则都可以刷出这个结果。

我们发现只要有一段长度大于等于k，就一定能刷出来，所以直接从第一个连续段开始，从前往后刷就行了

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 10;
int a[N];
int b[N];
signed main()
{
    int t;
    scanf("%lld", &t);
    while (t--)
    {
        int n, m, k;
        scanf("%lld%lld%lld", &n, &m, &k);
        for (int i = 1; i <= n; i++)
        {
            b[i] = 0;
            scanf("%lld", &a[i]);
        }
        int cnt = 0;
        a[0] = -1;
        for (int i = 1; i <= n; i++)
        {
            if (a[i] != a[i - 1])
            {
                b[++cnt] += 1;
            }
            else
            {
                b[cnt] += 1;
            }
        }
        if (a[1] == a[n] && cnt != 1) //看1和最后面的有无联系，如果相同就合并
        {
            b[1] += b[cnt];
            cnt -= 1;
        }
        int flag = 0;
        int sum = 0;
        for (int i = 1; i <= cnt; i++)
        {
            if (b[i] >= k)
            {
                flag = 1;
            }
            sum += ceil(b[i] * 1.0 / k);
        }
        if (flag == 0)
        {
            printf("-1\n");
        }
        else
        {
            printf("%lld\n", sum);
        }
    }
    return 0;
}

A.Another A+B Problem（搜索）

思路：这题题意读着很难受，做不出来大概率是因为没读懂题QAQ

本题主要难点就是搜索出满足约束的答案。容易发现，如果某个地方对应的是G，那么我们可以完全不管这个地方。然后我们查看每个数字对应的’P’,’B’个数。如果一个数字没有对应的’P’,’B’，意味着他在搜索时可以随便拿，没有数量限制。如果一个数字对应的全都是’P’（假设k个）,那么意味着它至少出现k次。如果一个数字既有’P’（k个）也有’B’，说明这个数字要刚好出现k次。同时，最后搜索结果要满足等式。

#include <bits/stdc++.h>
using namespace std;
const int N = 11;
char a[11], b[11];
vector<int> v[11];
int num[N];
int vis[N];
char c[N];
const int INF = 0x3f3f3f3f;
int cnt = 0;
char ans[1000000 + 10][N];
void dfs(int x)
{
    if (x == 9)
    {
        for (int i = 0; i < 10; i++)
        {
            if (num[i] > 0 && num[i] < 1e4)
            {
                return;
            }
        }
        int z = (c[1] - '0') * 10 + c[2] - '0';
        int x = (c[4] - '0') * 10 + c[5] - '0';
        int m = (c[7] - '0') * 10 + c[8] - '0';
        if (z + x != m)
        {
            return;
        }
        cnt += 1;
        for (int i = 1; i <= 8; i++)
        {
            ans[cnt][i] = c[i];
        }
        return;
    }
    if (b[x] == 'G')
    {
        dfs(x + 1);
        return;
    }
    for (int i = 0; i < 10; i++)
    {
        if (vis[i] == 0 && num[i] == 0 || i == a[x] - '0')
        {
            continue;
        }
        num[i] -= 1;
        c[x] = i + '0';
        dfs(x + 1);
        num[i] += 1;
    }
}
int main()
{
    cin >> a + 1 >> b + 1;
    for (int i = 0; i < 10; i++)
    {
        num[i] = 1e5;
        vis[i] = 1;
    }
    for (int i = 1; i <= 8; i++)
    {
        if (b[i] == 'G')
        {
            c[i] = a[i];
            continue;
        }
        v[a[i] - '0'].push_back(i);
        // printf("%d %d\n", a[i] - '0', i);
    }
    // for (int i = 0; i < 10; i++)
    // {
    //     printf("%d\n", v[i]);
    // }
    for (int i = 0; i < 10; i++)
    {
        if (v[i].size() == 0)
        {
            continue;
        }
        int sum = 0;
        for (auto t : v[i])
        {
            if (b[t] == 'P')
            {
                sum++;
            }
            else
            {
                vis[i] = 0;
            }
        }
        num[i] = sum;
    }
    // for (int i = 0; i < 10; i++)
    // {
    //     printf("%d\n", num[i]);
    // }
    dfs(1);
    cout << cnt << "\n";
    for (int i = 1; i <= cnt; i++)
    {
        cout << ans[i] + 1 << "\n";
    }
    return 0;
}

M.My University Is Better Than Yours（tarjan缩点）

题意：m个排行榜，只要有一个排行榜中a比b前，那么a就比b好。（a比b好和b比a好可以同时成立）且如果a比b好，b比c好，那么a比c好。求每所学校好于多少所学校。

思路：每一个排行榜相邻两点建图的话是一条链状DAG，如果多个排行榜一起建图的话就会形成很多环，容易发现环上的点是共享答案的。因此可以缩成一个点。可以证明，缩完点之后的DAG也是链状的，因此可以直接求得。

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;
int n, m, b;
vector<int> e[N];
int dfn[N], low[N], tot;
stack<int> s;
int scc[N], siz[N], cnt;
int din[N], dout[N];
int a[N];
int num[N];
vector<int> v[N];
void tarjan(int x)
{
    dfn[x] = low[x] = ++tot;
    s.push(x);
    for (auto y : e[x])
    {
        if (!dfn[y])
        {
            tarjan(y);
            low[x] = min(low[x], low[y]);
        }
        else if (!scc[y])
        {
            low[x] = min(low[x], dfn[y]);
        }
    }
    if (dfn[x] == low[x])
    {
        ++cnt;
        while (1)
        {
            int y = s.top();
            s.pop();
            scc[y] = cnt;
            ++siz[cnt];
            if (x == y)
            {
                break;
            }
        }
    }
}
void dfs(int x, int fa)
{
    for (int t : v[x])
    {
        if (t == fa)
        {
            continue;
        }
        dfs(t, x);
        siz[x] += siz[t];
    }
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int j = 1; j <= m; j++)
    {
        for (int i = 1; i <= n; i++)
        {
            scanf("%d", &a[i]);
            if (i > 1)
            {
                e[a[i - 1]].push_back(a[i]);
            }
        }
    }
    for (int i = 1; i <= n; i++)
    {
        if (!dfn[i])
        {
            tarjan(i);
        }
    }
    for (int i = 1; i <= n; i++)
    {
        for (auto t : e[i])
        {
            if (scc[t] != scc[i])
            {
                e[scc[i]].push_back(scc[t]);
            }
        }
    }
    for (int i = 1; i <= cnt; i++)
    {
        siz[i] += siz[i - 1];
    }
    for (int i = 1; i <= n; i++)
    {
        printf("%d ", siz[scc[i]] - 1);
    }
    printf("\n");
    return 0;
}

L.Last Warning of the Competition Finance Officer（AC自动机+dp）

思路：

设dp[i]为1-i的得分, 划分中没有包含的子串）dp[i]=dp[i−1](划分中没有包含i的子串）+∑j dp[i−len(tj)]∗val[tj] 我们可以发现，不同长度的t最多只有 ∑t 个，所以AC自动机压缩完路径后跳fail指针最多不超过 ∑t 个，直接AC自动机+转移即可。

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int ch[N][26];
int idx;
int ne[N];
char str[N], s[N];
int e[N], g[N];
const int mod = 998244353;
int fuck[N];
int dp[N];
void insert(int x)
{
    int p = 0;
    int len = strlen(s + 1);
    for (int i = 1; i <= len; i++)
    {
        int j = s[i] - 'a';
        if (!ch[p][j])
        {
            ch[p][j] = ++idx;
        }
        p = ch[p][j];
    }
    e[p] = x;
    g[p] = len;
}
void build()
{
    queue<int> q;
    for (int i = 0; i < 26; i++)
    {
        if (ch[0][i])
        {
            q.push(ch[0][i]);
        }
    }
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        if (e[u])
        {
            fuck[u] = u;
        }
        else
        {
            fuck[u] = fuck[ne[u]];
        }
        for (int i = 0; i < 26; i++)
        {
            int v = ch[u][i];
            if (v)
            {
                ne[v] = ch[ne[u]][i];
                q.push(v);
            }
            else
            {
                ch[u][i] = ch[ne[u]][i];
            }
        }
    }
}
int main()
{
    scanf("%s", str + 1);
    int m;
    scanf("%d", &m);
    int ans;
    for (int i = 1; i <= m; i++)
    {
        scanf("%s%d", s + 1, &ans);
        insert(ans);
    }
    build();
    dp[0] = 1;
    int n = strlen(str + 1);
    for (int i = 1, u = 0; i <= n; i++)
    {
        dp[i] = dp[i - 1];
        u = ch[u][str[i] - 'a'];
        for (int j = fuck[u]; j; j = fuck[ne[j]])
        {
            if (g[j] <= i)
            {
                dp[i] += 1ll * dp[i - g[j]] * e[j] % mod;
                dp[i] %= mod;
            }
        }
        printf("%d ", dp[i]);
    }
    // printf("\n");
    return 0;
}