2024 SZTU-ACM寒期集训阶段赛

写在前面

难度	题号
签到	\(G\ H\)
简单	\(F\ J\)
中等	\(B\ C\ E\ I\)
困难	\(A\ D\)

A 又要迟到了

考点：

搜索
图论

题解：

困难题

解法一：两遍 \(BFS\) \(O(n*m + k)\)

从起点开始做 \(BFS\) 记录从起点到每个位置只走路（每步时间为 \(t_1\) ）的时间 \(t_{w}\)

从终点开始做 \(BFS\) 记录从终点到每个位置用单车（每步时间为 \(t_2\) ）的时间 \(t_c\)

维护一个最小值 \(ans\)

遍历所有的单车的位置 \((i,j)\) ，此时 \(ans = min(ans,\ t_w[i][j] + t_c[i][j])\)

再额外判断一次如果不找单车，直接用走路的方式从起点到终点 \((i,j)\) ，即 \(ans = min(ans,\ t_w[i][j])\)

如果 \(ans \le t\) 则输出结果，反之则不能按时到达

#include <bits/stdc++.h>
using namespace std;
const int N = 2e3 + 10;

int n, m, t, t1, t2;
pair<int, int> S, T;
vector<pair<int, int>> C;
char mp[N][N];
vector<vector<int>> t_w(N, vector<int>(N, 0x3f3f3f3f));
vector<vector<int>> t_c(N, vector<int>(N, 0x3f3f3f3f));
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
bool vis[N][N];

void bfs(pair<int, int> PII, vector<vector<int>> &t, int dt)
{
    memset(vis, 0, sizeof(vis));
    queue<pair<int, int>> q;

    vis[PII.first][PII.second] = true;
    t[PII.first][PII.second] = 0;
    q.push(make_pair(PII.first, PII.second));
    while (!q.empty())
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();

        for (int i = 0; i < 4; i++)
        {
            int tx = x + dx[i];
            int ty = y + dy[i];

            if (tx < 1 || ty < 1 || tx > n || ty > m || vis[tx][ty] || mp[tx][ty] == '#')
                continue;

            vis[tx][ty] = true;
            t[tx][ty] = t[x][y] + dt;
            q.push(make_pair(tx, ty));
        }
    }
}

int main()
{
    cin.tie(0)->ios::sync_with_stdio(false);

    cin >> n >> m >> t >> t1 >> t2;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            cin >> mp[i][j];
            if (mp[i][j] == 'S')
                S = make_pair(i, j);
            else if (mp[i][j] == 'T')
                T = make_pair(i, j);
            else if (mp[i][j] == 'C')
                C.push_back(make_pair(i, j));
        }
    }

    bfs(S, t_w, t1);
    bfs(T, t_c, t2);

    int ans = 0x3f3f3f3f;
    for (auto it : C)
    {
        int cx = it.first;
        int cy = it.second;
        ans = min(ans, t_w[cx][cy] + t_c[cx][cy]);
    }
    ans = min(ans, t_w[T.first][T.second]);

    if (ans <= t)
        cout << ans;
    else
        cout << "Oh no!";

    return 0;
}

解法二：BFS+优先队列 \(O(2nm \log (nm))\)

使用优先队列让最短时间在队首，时间相同的时候优先有车的。

\(BFS\) 直到到达终点，此时的时间即为答案。若队列结束也没有到达终点则返回 \(-1\)

#include <bits/stdc++.h>
using namespace std;
const int N = 2e3 + 10;

int n, m, t, t1, t2;
int sx, sy;
char mp[N][N];
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
bool vis[N][N][2];

struct node
{
    int x, y, t;
    bool flag;
    friend bool operator<(const node a, const node b)
    {
        if (a.t != b.t)
            return a.t > b.t;
        return a.flag < b.flag;
    }
};

int bfs()
{
    priority_queue<node> q;

    q.push({sx, sy, 0, 0});
    vis[sx][sy][0] = true;
    while (!q.empty())
    {
        node now = q.top();
        int x = now.x;
        int y = now.y;
        q.pop();

        if (mp[x][y] == 'T')
            return now.t;

        for (int i = 0; i < 4; i++)
        {
            int tx = x + dx[i];
            int ty = y + dy[i];
            int tt = now.t + (now.flag ? t2 : t1);
            bool flag = now.flag || mp[tx][ty] == 'C';

            if (tx < 1 || ty < 1 || tx > n || ty > m || vis[tx][ty][flag] || mp[tx][ty] == '#')
                continue;

            vis[tx][ty][flag] = true;
            q.push({tx, ty, tt, flag});
        }
    }
    return -1;
}

int main()
{
    cin.tie(0)->ios::sync_with_stdio(false);

    cin >> n >> m >> t >> t1 >> t2;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            cin >> mp[i][j];
            if (mp[i][j] == 'S')
                sx = i, sy = j;
        }
    }

    int ans = bfs();
    if (ans == -1)
        cout << ans;
    else
        cout << "Oh no!";

    return 0;
}

B 最大生成树

考点：

图论

题解：

中等题

最小生成树板子题，将比较时小的优先改为大的优先即可

复杂度： \(O(m \log m)\)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct Edge
{
    int u, v, w;
    bool operator<(Edge const &a) const { return w < a.w; }
};

vector<int> fa;

int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }

void solve()
{
    int n, m;
    cin >> n >> m;
    fa.resize(n + 1);

    for (int i = 1; i <= n; i++)
        fa[i] = i;

    priority_queue<Edge> e;
    for (int i = 0; i < m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        e.push({u, v, w});
    }

    int ans = 0;
    while (!e.empty())
    {
        auto [u, v, w] = e.top();
        e.pop();

        int fu = find(u), fv = find(v);
        if (fu != fv)
        {
            fa[fu] = fv;
            ans += w;
        }
    }

    cout << ans;
}

int main()
{
    cin.tie(0)->ios::sync_with_stdio(false);

    int t = 1;
    // cin >> t;
    while (t--)
        solve();

    return 0;
}

C 最短路

考点：

图论

题解：

中等题

通过 \(floyd\) 将全源最短路都找出来，最后判断这条边是否可以被另一条最短路替代，计数即可。

复杂度： \(O(n^3)\)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct Edge
{
    int u, v, w;
};

void solve()
{
    int n, m;
    cin >> n >> m;

    vector<vector<int>> dis(n + 1, vector<int>(n + 1, 0x3f3f3f3f));
    vector<Edge> e(m);
    for (int i = 0; i < m; i++)
    {
        cin >> e[i].u >> e[i].v >> e[i].w;
        dis[e[i].u][e[i].v] = dis[e[i].v][e[i].u] = e[i].w;
    }

    for (int k = 1; k <= n; k++)
        for (int u = 1; u <= n; u++)
            for (int v = 1; v <= n; v++)
                dis[u][v] = min(dis[u][v], dis[u][k] + dis[k][v]);

    int ans = 0;
    for (auto [u, v, w] : e)
    {
        bool flag = false;
        for (int k = 1; k <= n; k++)
        {
            if (dis[u][k] + dis[k][v] <= w)
                flag = true;
        }
        ans += flag;
    }
    cout << ans;
}

int main()
{
    cin.tie(0)->ios::sync_with_stdio(false);

    int t = 1;
    // cin >> t;
    while (t--)
        solve();

    return 0;
}

D 相撞的房子

考点：

树状数组

题解：

困难题

本题可以理解为两个一维数组（行和列）进行单点修改和区间求和，很明显是树状数组的板子题，不过还需要进行一些分析。

以题目的样例为例，先以 \((2,2)\) 为中心向东南西北建房子

o x o o
x o x x
o x o o
o x o o

再以 \((4,4)\) 为中心向东南西北建房子

o x o x
x o x o
o x o x
x o x o

我们可以得到房子的数量应该是：

放过的行数×m + 放过的列数×n − 抵消块数

放过的行数和列数用树状数组来维护即可

而抵消的块数该怎么讨论呢？

在算行列的时候，每一个交叉点是记了两次的。图中有多少交叉点呢？记放过的行数为 \(x\)，放过的列数为 \(y\)，每行每列交叉一个，抵消的块数就是 \(2xy\)。

所以现在只需要求出 \(x,y\) 就可以了

如果放在的行和列是已经放过的那就会变为没房子状态，如果要放的行和列没房子，那就会变成有房子状态，相当于异或操作。

复杂度： \(O(q\log n)\)

#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int maxn = 1e5 + 10;
int ax[maxn], ay[maxn];
int dx[maxn], dy[maxn];
int n, m, q;

int lowbit(int i)
{
    return i & (-i);
}

void update(int c[], int len, int x, int add)
{
    for (int i = x; i <= len; i += lowbit(i))
    {
        c[i] += add;
    }
}

ll query(int c[], int x)
{
    ll sum = 0;
    for (int i = x; i; i -= lowbit(i))
    {
        sum += c[i];
    }
    return sum;
}

void solve(int x, int y)
{
    if (ax[x] == 1)
    {
        update(dx, n, x, -1);
    }
    else
    {
        update(dx, n, x, 1);
    }
    ax[x] ^= 1;
    if (ay[y] == 1)
    {
        update(dy, m, y, -1);
    }
    else
    {
        update(dy, m, y, 1);
    }
    ay[y] ^= 1;
}

ll work(int x1, int y1, int x2, int y2)
{
    ll s1 = query(dx, x2) - query(dx, x1 - 1);
    ll s2 = query(dy, y2) - query(dy, y1 - 1);
    return 1LL * s1 * (y2 - y1 + 1) + 1LL * s2 * (x2 - x1 + 1) - 1LL * 2 * s1 * s2;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m >> q;
    while (q--)
    {
        int op;
        cin >> op;
        if (op == 1)
        {
            int x, y;
            cin >> x >> y;
            solve(x, y);
        }
        else
        {
            int x1, y1, x2, y2;
            cin >> x1 >> y1 >> x2 >> y2;
            cout << work(x1, y1, x2, y2) << '\n';
        }
    }
    return 0;
}

E 动感超人

考点：

背包问题

题解：

中等题

这题可以用背包的思路来做；首先，设\(dp[j]\)表示运 \(j\) 只玩具回家的最小时间，\(tim[i]\) 表示一次性运 \(i\) 只玩具回家的时间，那么状态转移方程就是：\(dp[j] = min(dp[j],dp[j-i]+tim[i])\) ,最后输出 \(dp[n]\)

\(tim[i]\) 的计算我们运用前缀和，由于每一次都要加上从家到商场的时间，所以我们在第一项 \(tim[1]\) 加上 \(2m\) ,最后输出的时候再减去 \(m\)，因为最后一次不用从家到商场

复杂度： \(O(n^2)\)

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
const int maxn = 1e5 + 10;
const int inf = 1e9;
int n, m, w[maxn], tim[maxn], dp[maxn];//dp 表示运完 j只所需要的最短时间
void solve()
{
     cin >> n >> m;
     for (int i = 1; i <= n; ++i)
     {
          dp[i] = inf;
          cin >> w[i];
          tim[i] = w[i] + tim[i - 1];
          if(i==1)
          {
               tim[i] += 2 * m;
          }
     }

     for (int i = 1; i <= n; ++i)//一次性运几只
     {
          for (int j = i; j <= n; ++j)
          {
               dp[j] = min(dp[j], dp[j - i] + tim[i]);
          }
     }

     cout << dp[n] - m << endl;
}

int main()
{
     // std::ios::sync_with_stdio(false);
     // cin.tie(0);
     // cout.tie(0);
     solve();
     return 0;
}

F 01矩阵

考点：

前缀和
二分

题解：

简单题

通过二维前缀和快速查询矩形内 \(1\) 的个数。用二分答案确认边长。

复杂度 \(O(n^2\log n)\)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

vector<vector<int>> a;
int n, m;

bool check(int x)
{
    for (int i = x; i <= n; i++)
    {
        for (int j = x; j <= m; j++)
        {
            if (a[i][j] - a[i - x][j] - a[i][j - x] + a[i - x][j - x] == x * x)
                return true;
        }
    }
    return false;
}

void solve()
{
    cin >> n >> m;

    a.resize(n + 1, vector<int>(m + 1));
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            cin >> a[i][j];
            a[i][j] = a[i][j] + a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];
        }
    }

    int l = 0, r = min(n, m), ans = 0;
    while (l <= r)
    {
        int mid = (l + r) / 2;
        if (check(mid))
            ans = mid, l = mid + 1;
        else
            r = mid - 1;
    }

    cout << ans << endl;
}

int main()
{
    cin.tie(0)->ios::sync_with_stdio(false);

    int t = 1;
    // cin >> t;
    while (t--)
        solve();

    return 0;
}

G 简单问题

考点：

排序

题解：

签到题

一个数如果是 \(3\) 的倍数，那么它每个位上的数之和也是 \(3\) 的倍数。

判断是不是 \(3\) 的倍数后，可以用 \(O(n\log n)\) 的排序或者计数排序将卡片降序排序即可。

复杂度： \(O(n\log n)\)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

void solve()
{
    int n;
    string s;
    cin >> n >> s;
    int t = 0;
    for (int i = 0; i < n; i++)
        t += s[i] - '0';

    if (t % 3)
    {
        cout << -1;
        return;
    }

    sort(s.begin(), s.end(), greater<char>());
    cout << s;
}

int main()
{
    cin.tie(0)->ios::sync_with_stdio(false);

    int t = 1;
    // cin >> t;
    while (t--)
        solve();

    return 0;
}

H 回文串

考点：

基础语法

题解：

签到题

从两边开始一一比较。

如果两边都不是 \(?\) 且这两个位置的字母不同，则这个字符串不可能是回文串。

如果两边都是 \(?\) 则有 \(26\) 种可能。

如果只有一个 \(?\) 则只有 \(1\) 种可能。

复杂度： \(O(n)\)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;

void solve()
{
    string s;
    cin >> s;
    ll ans = 1;
    for (int i = 0, j = s.size() - 1; i <= j; i++, j--)
    {
        if (s[i] != s[j] && s[i] != '?' && s[j] != '?')
        {
            cout << 0 << endl;
            return;
        }
        if (s[i] == '?' && s[j] == '?')
            ans = (ans * 26) % mod;
    }

    cout << ans;
}

int main()
{
    cin.tie(0)->ios::sync_with_stdio(false);

    int t = 1;
    // cin >> t;
    while (t--)
        solve();

    return 0;
}

I Apple Catching G

考点：

记忆化搜索

题解：

中等题

可以发现，每⼀时刻前，都可以移动，所以，每⼀时刻前往后，设

\(n_1\) = (移动，移动之后，当前时刻能吃到的苹果 + 往后时刻能吃到的苹果)
\(n_2\) = (不移动，之后，在当前时刻能吃到的苹果 + 往后时刻能吃到的苹果)

当前可以吃到的苹果的数量都等于 \(max(n_1,n_2)\)，发现状态减少，可以⽤记忆化搜索递归下去（或者⽤ \(dp\)）

复杂度： \(O(NW)\)

#include <bits/stdc++.h>
using namespace std;
#define max_len 1010
// 苹果掉落的位置
int apple_location[max_len];
int N;
// 记忆化数组
int save_data[max_len][2][40];
bool is_visit[max_len][2][40];
int get_max(int now_i, int now_in, int can_move)
{
    if (now_i >= N)
    {
        return 0;
    }
    else
    {
        if (is_visit[now_i][now_in][can_move] == true)
        {
            return save_data[now_i][now_in][can_move];
        }
        int can_get = 0;

        can_get = (apple_location[now_i] == now_in) +
                  get_max(now_i + 1, now_in, can_move);
        if (can_move > 0)
            can_get = max(can_get, (apple_location[now_i] != now_in) +
                                       get_max(now_i + 1, !now_in, can_move - 1));

        save_data[now_i][now_in][can_move] = can_get;
        is_visit[now_i][now_in][can_move] = true;
        return can_get;
    }
}
int main()
{
    int W;
    cin >> N >> W;
    for (int i = 0; i < N; i++)
    {
        cin >> apple_location[i];
        // 使位置变为0和1，下个位置可用!操作
        apple_location[i]--;
    }
    cout << get_max(0, 0, W) << endl;
}

J Xor

考点：

位运算

题解：

简单题

解法一：暴力 \(O(63 * q)\)

按照题意对每次操作对每一位进行异或

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

void solve()
{
    ll x, q;
    cin >> x >> q;
    while (q--)
    {
        int l, r;
        cin >> l >> r;

        ll p = 1;
        for (int i = l; i <= r; i++)
            x ^= p << i;
    }
    cout << x;
}

int main()
{
    cin.tie(0)->ios::sync_with_stdio(false);

    int t = 1;
    // cin >> t;
    while (t--)
        solve();

    return 0;
}

解法二：差分 \(O(q)\)

通过异或偶数次会还原的性质，差分后如果前缀和数组里是奇数则这位置需要异或。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

void solve()
{
    ll x, q;
    cin >> x >> q;
    vector<int> a(64);

    while (q--)
    {
        int l, r;
        cin >> l >> r;
        a[l]++;
        a[r + 1]--;
    }

    partial_sum(a.begin(), a.end(), a.begin());

    for (int i = 0; i < 63; i++)
    {
        if (a[i] % 2)
            x ^= (1LL << i);
    }

    cout << x;
}

int main()
{
    cin.tie(0)->ios::sync_with_stdio(false);

    int t = 1;
    // cin >> t;
    while (t--)
        solve();

    return 0;
}

ACM > 题解 > SZTU_ACM

#算法 #SZTU_ACM

2024 SZTU-ACM寒期集训阶段赛

http://xiaowhang.github.io/archives/3504666746/

作者

Xiaowhang

发布于

2024年2月2日

许可协议

Codeforces Round 929 (Div. 3) 上一篇

SZTU_ACM2024寒期集训训练赛-基础组第二场下一篇

2024 SZTU-ACM寒期集训阶段赛

写在前面

A 又要迟到了

考点：

题解：

解法一：两遍 \(BFS\) \(O(n*m + k)\)

解法二：BFS+优先队列 \(O(2nm \log (nm))\)

B 最大生成树

考点：

题解：

C 最短路

考点：

题解：

D 相撞的房子

考点：

题解：

E 动感超人

考点：

题解：

F 01矩阵

考点：

题解：

G 简单问题

考点：

题解：

H 回文串

考点：

题解：

I Apple Catching G

考点：

题解：

J Xor

考点：

题解：

解法一：暴力 \(O(63 * q)\)

解法二：差分 \(O(q)\)​

解法二：差分 \(O(q)\)