“达梦杯”武汉理工大学第五届新生程序设计大赛

A. Awa开小车

思路

根据题意模拟。

遇到没触发过的导向板就进行转向，计数，并标记为来过，直到小车爆炸。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 111;

char mp[N][N];
bool vis[N][N];

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

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> mp[i][j];

    int ans = 0;
    char now = mp[x][y];
    vis[x][y] = 1;
    while (1)
    {
        if (now == 'D')
            x++;
        else if (now == 'U')
            x--;
        else if (now == 'L')
            y--;
        else if (now == 'R')
            y++;

        if (x < 1 || x > n || y < 1 || y > m)
            break;

        if (vis[x][y])
            continue;
        vis[x][y] = 1;

        if (mp[x][y] != now)
        {
            ans++;
            now = mp[x][y];
        }
    }

    cout << ans << '\n';
}

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

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

    return 0;
}

B. JokerXuan的明星梦

思路

\(now\) 表示当前的幸运数字，\(num0\) 和 \(num1\) 分别表示每个位全为 \(0\) 的数和全为 \(1\) 的数经过几天的操作后的结果

如果出现 \(null\)，我们查看 \(num0\) 和 \(num1\) 的每一位：

都为 \(1\) 则 \(now\) 的这一位一定是 \(1\)
都为 \(0\) 则 \(now\) 的这一位一定是 \(0\)
如果 \(num0\) 为 \(1\) 且 \(num1\) 为 \(0\) 则这一位要改变
否则这一位没有改变

Code

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

int now, num0 = 0, num1 = -1;

void func()
{
    for (int i = 0; i <= 30; i++)
    {
        if ((num0 & 1 << i) && (num1 & 1 << i))
            now |= 1 << i;
        else if ((!num0 & 1 << i) && !(num1 & 1 << i))
            now &= ~(1 << i);
        else if ((num0 & 1 << i) && !(num1 & 1 << i))
            now ^= 1 << i;
    }
}

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

    string t;
    cin >> t >> now;
    cout << now << '\n';

    for (int i = 2; i <= n; i++)
    {
        cin >> t;
        if (t == "null")
            func();
        else
        {
            int x;
            cin >> x;
            if (i == 1)
                now = x;
            else
            {
                int time = atoi(t.substr(0, t.size() - 3).c_str());
                if (time < 12)
                    now &= x, num0 &= x, num1 &= x;
                else if (time < 18)
                    now |= x, num0 |= x, num1 |= x;
                else
                    now ^= x, num0 ^= x, num1 ^= x;
            }
        }
        cout << now << '\n';
    }
}

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

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

    return 0;
}

C. What is ACM?

思路

遇到关键字符 \(ACM\) 就加入字符串 \(tmp\)，如果当前不是关键字符就输出 \(tmp\)

Code

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

void solve()
{
    int n;
    string s, t;
    cin >> n >> s >> t;

    string tmp, acm = "ACM";
    for (int i = 0; i < n; i++)
    {
        if (acm.find(t[i]) != string::npos)
            tmp += s[i];
        else
        {
            if (tmp != "")
                cout << tmp << ' ';
            tmp = "";
        }
    }
    cout << tmp << ' ';
}

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

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

    return 0;
}

D. 呼风唤雨

思路

将每个位置都作为分界点，记录最大值即可

Code

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

void solve()
{
    int n;
    cin >> n;
    vector<ll> v(n + 1);
    ll sum = 0;
    for (int i = 1; i <= n; i++)
    {
        cin >> v[i];
        v[i] *= 514;
        sum += v[i];
    }
    ll ans = 0;

    for (int k = 1; k < n; k++)
    {
        sum -= v[k];
        sum += v[k] / 514 * 114;
        ans = max(ans, sum);
    }
    cout << ans << '\n';
}

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

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

    return 0;
}

E. 急急国王修公路

思路

通过并查集记录每个州（联通块）有多少城池（度数）。

生成一颗树需要 \(n-1\) 条无向边，即 \(2*(n-1)\) 度数

二分答案 \(x\) ，每个联通块能提供 \(\min (size[i], x)\) 度数，其中 \(size[i]\) 为第 \(i\) 个联通块的度数，判断度数是否满足即可。

Code

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

vector<int> fa;
unordered_map<int, int> mp;

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

void merge(int x, int y) { fa[find(x)] = find(y); }

bool judge(int x)
{
    int sum = 0;
    for (auto [a, b] : mp)
        sum += min(x, b);
    return sum >= 2 * (mp.size() - 1);
}

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

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

    while (m--)
    {
        int a, b;
        cin >> a >> b;
        merge(a, b);
    }

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

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

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

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

    return 0;
}

F. 绒绒的括号序列

思路

待补

Code

待补

G. 神奇的礼物

思路

易知，如果两数之差的绝对值模 \(3\) 余 \(0\) ，则可以通过数次操作使这两数相等

Code

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

void solve()
{
    int g[5];
    for (int i = 1; i <= 3; i++)
        cin >> g[i];

    int i;
    cin >> i;
    swap(g[i], g[1]);

    if ((g[2] - g[3]) % 3 == 0)
        cout << "Yes\n";
    else
        cout << "No\n";
}

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

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

    return 0;
}

H. 小F的圣诞树

思路

对于重量较大的礼物，相互作用为它的重量乘以它们的深度之和。

从 \(1\) 号节点进行搜索，记录每个节点的深度，再按重量对节点降序排序。

对于节点 \(i\) 它和它后面 \(n\) 个节点的相互作用之和为节点 \(i\) 的重量乘以后面节点的深度加上 \(n\) 个节点 \(i\) 的深度之和。

通过前缀和优化求深度和的时间复杂度

Code

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

struct node
{
    int val, dep;
};

void solve()
{
    int n;
    cin >> n;
    vector<node> v(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> v[i].val;

    vector<vector<int>> g(n + 1);
    for (int i = 1; i < n; i++)
    {
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }

    queue<pair<int, int>> q;
    vector<int> vis(n + 1);
    q.push({1, 0});
    while (!q.empty())
    {
        auto [now, dep] = q.front();
        q.pop();

        v[now].dep = dep;
        vis[now] = 1;

        for (auto it : g[now])
        {
            if (!vis[it])
                q.push({it, dep + 1});
        }
    }

    sort(v.begin() + 1, v.end(), [](node a, node b)
         { return a.val > b.val; });

    ll ans = 0;

    vector<ll> sum(n + 1);
    for (int i = 1; i <= n; i++)
        sum[i] = sum[i - 1] + v[i].dep;

    for (int i = 1; i <= n; i++)
        ans = (ans + (v[i].val * (sum[n] - sum[i] + 1LL * (n - i) * v[i].dep) % mod)) % mod;

    cout << ans << '\n';
}

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

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

    return 0;
}

I. 优雅太优雅了

思路

已知 \(\forall[l, r], \min (a[l], a[l+1], \cdots, a[r]) \geqslant \operatorname{gcd}(a[l], a[l+1], \cdots, a[r])\) 成立

那么 \(\forall[l, r], \min (a[l], a[l+1], \cdots, a[r-1]) \geqslant \operatorname{gcd}(a[l], a[l+1], \cdots, a[r-1])\) 成立

当 \(a_i\) 不能改变区间最小值的时候，不管 \(a_{i+1}\) 是什么数，区间 \(gcd\) 都不会增加，都有 \(\forall[l, r], \min (a[l], a[l+1], \cdots, a[r]) \geqslant \operatorname{gcd}(a[l], a[l+1], \cdots, a[r+1])\)

反之当 \(a_i\) 为区间最小值时考虑 \(\forall[l, r],a_r \geqslant \operatorname{gcd}(a[l], a[l+1], \cdots, a[r+1])\)，区间 \(gcd\) 会随着 \(l\) 减小而减小

当 \(l\) 最靠近 \(r\) 时，右侧取最大值 \(\operatorname{gcd}(a[r-1], a[r+1])\)

故只需证明 \(\forall[l, r],a_r \geqslant \operatorname{gcd}(a[r-1], a[r+1])\)

Code

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

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

void solve()
{
    int n;
    cin >> n;
    vector<int> v(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> v[i];

    for (int i = 2; i < n; i++)
    {
        if (v[i] < gcd(v[i - 1], v[i + 1]))
        {
            cout << "Rude";
            return;
        }
    }
    cout << "Elegant";
}

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

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

    return 0;
}

J. 逆序对

思路

见题解

Code

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

const int N = 1e6 + 5;

int nex[31 * N][2], tot = 0;
int cnt[31 * N][2][2];
int a[N], b[N];

void insert(int x, int y)
{
    int p = 0;
    for (int i = 30; i >= 0; i--)
    {
        int tmp1 = (x >> i) & 1;
        int tmp2 = (y >> i) & 1;
        int tmp = tmp1 ^ tmp2;

        if (!nex[p][tmp])
            nex[p][tmp] = ++tot;
        cnt[p][tmp1][tmp2]++;
        p = nex[p][tmp];
    }
}

int query(int x, int y)
{
    int p = 0, res = 0;
    for (int i = 30; i >= 0; i--)
    {
        int tmp1 = (x >> i) & 1;
        int tmp2 = (y >> i) & 1;
        int tmp = tmp1 ^ tmp2;

        res += cnt[p][tmp2 ^ 1][tmp1];
        if (!nex[p][tmp])
            return res;
        p = nex[p][tmp];
    }
    return res;
}

void init()
{
    for (int i = 0; i < tot; i++)
    {
        for (int j = 0; j < 2; j++)
        {
            nex[i][j] = 0;
            for (int k = 0; k < 2; k++)
                cnt[i][j][k] = 0;
        }
    }
    tot = 0;
}

void solve()
{
    init();

    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int i = 0; i < n; i++)
        cin >> b[i];

    ll ans = 0;
    for (int i = 0; i < n; i++)
    {
        ans += query(a[i], b[i]);
        insert(a[i], b[i]);
    }

    cout << ans << '\n';
}

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

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

    return 0;
}

ACM > 题解

#算法

“达梦杯”武汉理工大学第五届新生程序设计大赛

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

作者

Xiaowhang

发布于

2024年3月10日

许可协议

字典树上一篇

Codeforces Round 929 (Div. 3) 下一篇