T20221120

Posted on 2022-11-20 Edited on 2026-03-02 In OI Word count in article: 2.3k Reading time ≈ 8 mins.

武汉理工大学新生杯

A Awa开小车

题目描述

Awa正在玩一款名叫明日方舟的游戏。

这款游戏在一个高度为n，宽度为m的网格上进行，玩家可以部署干员在格子上来击败敌人。

在这个问题中，我们定义第x行，第y列的格子的坐标为(x,y)，也就是说，从左上角到左下角依次为(1,1),(2,1),…,(n-1,1),(n,1)，从左上角到右上角依次为(1,1),(1,2),…,(1,m-1),(1,m)，右下角的格子坐标为(n,m)

在最新的一次活动中，场地上会有一个名叫“小车发射器”的装置，Awa在这里召唤小车！同时，Awa可以在其他格子上部署导向板：当小车开到一个未触发的导向板上时，小车就会按照导向板指向的方向前进，而当小车开出地图了，小车就会自爆！（在这个问题中，小车的油非常充足，只要没有自爆就会沿着当前行驶方向一直移动，同时，我们不考虑小车发射器的碰撞体积，也就是说小车发射器发射完小车就会消失，不会影响小车的后续运动）

当然，因为Awa的干员练度达到了力大砖飞的境界，他并不需要通过小车的帮助来击败敌人，因此，他非常随意的在地图上摆满了导向板，然后开动小车。同时，他非常好奇小车一共能转向多少次，因为小车开的太慢了，Awa懒得去数，因此他把这个问题扔给了你。

90度和180度转弯都算作“一次转向”，每个导向板只会在第一次走到的时候被触发，初始位置的导向板会被触发。

输入

第一行四个正整数 $n,m,x,y$，表示矩形区域大小为 $n$ 行 $m$ 列，以及小车发射器的位置 $(x,y)$ （对应位置上的方向就是小车的初始方向）之后 $n$ 行每行 $m$ 个字符 $U,D,L,R$ 之一，表示该格子的导向板类型，或者小车的初始方向。

$U$：向上； $D$：向下； $L$：向左； $R$：向右

输出

一个非负整数，表示小车的转向次数

模拟就好了，没什么难度

#include <bits/stdc++.h>

int n, m, x, y, ans;
int mx[] = {1, -1, 0, 0};
int my[] = {0, 0, 1, -1};
std::string board[105];
bool vis[105][105];
std::map <char, int> id;

int main() {
 id['U'] = 1, id['D'] = 0;
    id['L'] = 3, id['R'] = 2;
    std::ios::sync_with_stdio (0);
    std::cin.tie (nullptr);
    std::cin >> n >> m >> x >> y;
    for (int i = 0; i < n; ++i)
        std::cin >> board[i];
   
 x--, y--;
    int nx = x + mx[id[board[x][y]]];
    int ny = y + my[id[board[x][y]]];
    while (nx >= 0 && nx < n && ny >= 0 && ny < m) {
        vis[x][y] = 1;
        if (vis[nx][ny]) board[nx][ny] = board[x][y];
        if (board[x][y] ^ board[nx][ny]) ++ans;
        x = nx, y = ny;
        nx = x + mx[id[board[x][y]]];
        ny = y + my[id[board[x][y]]];
   
         }
   
     std::cout << ans << '\n';
    return 0;
   }

B JokerXuan的明星梦_

题目描述

过于冗杂，略

输入

第一行输入一个正整数 $T(1 \le T \le 3 \times 10^5)$ ，表示从薛之谦开始发博客到自己忘记密码过去了多少天。

接下来 $T$ 行，每行有一个字符串 $S(hh:mm)$ 表示发博客的时间或 “null” 表示当天没有发博客，如果发了博客，当天的幸运数字为 $X(0 \le X \le 2^{30})$ 。

输出

一共 $T$ 行。

每行一个正整数代表当天的幸运数字 $A$ 。

本质上是需要知道最终的幸运数字二进制下的状态。

想法一：用一个二位数组，表示第 $k$ 位最初为 $0/1$ 经过所有操作后的状态，可以更新 null，期望时间复杂度 $O(kn)$。

#include <bits/stdc++.h>

std::bitset <31> num;
std::bitset <31> update[2];
int n, x, tim;
 
char opt[10];

inline void upt() {
for (int i = 0; i < 31; ++i) 
    if (num[i]) num[i] = update[1][i];
    else num[i] = update[0][i];
}
 
int main() {
	scanf ("%d", &n);
	for (int i = 0; i < 31; ++i) update[1][i] = 1;
	for (int i = 0; i < n; ++i) {
        scanf  ("%s", opt);

        if (opt[0] == 'n') upt();
        else {
            sscanf (opt, "%d", &tim);
            scanf ("%d", &x);

            if (i == 0) num = x;
            else if (tim < 12)
                num &= x, update[0] &= x, update[1] &= x;
            else if (12 <= tim && tim < 18) 
                num |= x, update[0] |= x, update[1] |= x;
            else 
                num ^= x, update[0] ^= x, update[1] ^= x;
        }

        std::cout << num.to_ullong() << '\n';//bitset作为十进制数输出
    }
return 0;
}

进一步考虑优化 $upt$ 函数，能否优化掉这个 $log$ ?

考虑什么样的变化可以对答案产生贡献？

$1\rightarrow1\quad 0\rightarrow1$

即答案可以看作操作数与或按位取反再与 $0/1$ 开头的前缀，和上面有点相似。

#include <bits/stdc++.h>

std::bitset <31> num[3];
int n, x, tim;

char opt[10];

int main() {
    scanf ("%d", &n);
    num[1] = (1 << 31) - 1;
    for (int i = 0; i < n; ++i) {
        scanf  ("%s", opt);

        if (opt[0] == 'n') 
            num[2] = (num[2] & num[1]) | (~num[2] & num[0]);
        else {
            sscanf (opt, "%d", &tim);
            scanf ("%d", &x);

            if (i == 0) num[2] = x;
            else if (tim < 12)
                num[2] &= x, num[0] &= x, num[1] &= x;
            else if (12 <= tim && tim < 18) 
                num[2] |= x, num[0] |= x, num[1] |= x;
            else 
                num[2] ^= x, num[0] ^= x, num[1] ^= x;
        }

        std::cout << num[2].to_ullong() << '\n';
    }
	return 0;
}

E 急急国王修公路

题目描述

急急国王的国家里有 $N$ 座城池，标号为 $1 \sim N$，以及 $M$ 条双向道路，第 $i$ 条道路 $(1\le i \le M)$ 连接了城池$u_i$ 和 $v_i$。

最初，国内的城池被分为一些州，每个州内部的城池互相可达，而任意两个州之间互不可达，即一个州的任意城池与另一个州的任意城池互不可达。

急急国王希望修建一些新道路，使得国民可以从任意一座城池出发，去到所有其他城池（即任意两座城池都是互相可达的）。

由于人力物力的限制，每座城池最多只能再新建一条道路。且为了安全考虑，每个州新修建的道路数量不能过多，否则当一个州被敌国攻陷时，其他州也将面临较大的危机。

现在他想知道，每个州新修建的道路数量最低不超过多少时，可以使得各州互通。

输入

第 $1$ 行：两个整数 $N,M\quad 1 \le N \le 2 \times10^5, 1 \le M \le min\left(6\times10^5,\frac{N\times (N-1)}{2}\right)$。

第 $2\sim M$ 行：共有 $M $行，每行 $2$ 个整数 $u$、$v$，表示一条连接 $u$、$v$ 的双向道路。

输出

一个整数，表示可以使各州互通时，每个州新修建的道路数量上限的最小值。若无论如何都不能使各州互通，则输出 $-1$。

贪心：尽可能平均

特殊情况：叶子节点

考虑到叶子节点的特殊性，它只能连一条边，那就先不考虑它🐕

先将度数大于一的点连成一条链，此时答案已经为二

再考虑将叶子节点连到链上，注意两端的处理

#include <bits/stdc++.h>

using namespace std;

const int maxn = 2e5 + 10;
int n, m, u, v, cnt, siz, num;
bool vis[maxn];
vector <int> edge[maxn];
vector <int> s;

void getc(int x) {
    ++siz;
    vis[x] = 1;
    for (auto son : edge[x])
        if (!vis[son]) getc(son);
}

int main () {
    ios::sync_with_stdio (0);
    cin.tie (nullptr);
    cin >> n >> m;
    while (m--) {
        cin >> u >> v;
        edge[u].push_back (v);
        edge[v].push_back (u);
    }

    for (int i = 1; i <= n; ++i)
        if (!vis[i]) {
            ++cnt;
            siz = 0;
            getc(i);
            if (siz == 1) ++num;
            else s.push_back (siz);
        }

    if ((cnt - 1) * 2 > n) cout << -1 << '\n';
    else if (cnt == 1) cout << 0 << '\n';
    else if (cnt == 2) cout << 1 << '\n';
    else  {
        int ans(2);
        s[0]++, s[1]++;
        if (num >= 1) s[0]--, num--;
        if (num >= 1) s[1]--, num--;
        while (num) {
            for (auto &res : s)
                if (res > 2 && num) --res, --num;
            ++ans;
        }
        cout << ans << endl;
    }
    return 0;
}

I 优雅太优雅了

题目描述

在维护世界和平的道路上，阿尼亚负重前行。为成为皇帝的学徒，优雅的亨利·亨德森老师对她展开了考试。

亨利·亨德森认为对于一个有 $n$ 个正整数的数组 $A$

当且仅当对于任意一个下标区间 $[l,r] \left(1\leq l<r\leq n-1\right)$ 都满足$min(A[l],A[l+1],....A[r-1],A[r]) \geq gcd(A[l],A[l+1],....A[r-1],A[r+1])$

这个数组才是优雅的数组。

现在亨德森给可爱的阿尼亚一个长度为 $n$ 的数组 $A$，要求阿尼亚立刻回答出这个数组是否优雅。但可爱的阿尼亚太笨了，于是她向聪明的你求助，你需要帮助阿尼亚做出正确的回答。

输入

第一行输入一个整数 $n(2 \le n \le 2×10^5)$。

第二行输入nnn个整数 $A[i](1 \le A[i] \le 10^9)$。

输出

输出仅一行，若是优雅的数组则输出 $\text{“Elegant"}$，反之则输出 $\text{“Rude"}$。(不包含引号）

考虑：若 $\min\{b, c\}\ge\gcd\{b,d\}$ 成立，则 $\min\{a, b, c\}\ge\gcd\{a,b,d\}$ 一定成立

所以只需验证 $\min\{b, c\}\ge\gcd\{b,d\}$ 是否成立

#include <bits/stdc++.h>

int gcd (int x, int y) {
    if (y == 0) return x;
    return gcd (y, x % y);
}

int main() {
    std::ios::sync_with_stdio (0);
    std::cin.tie (nullptr);
    int n;
    bool flag(0);
    std::cin >> n;
    std::vector <int> a(n);
    for (int i = 0; i < n; ++i)
        std::cin >> a[i];
    for (int i = 1; i < n - 1; ++i)
        if (std::min(a[i - 1], a[i]) < gcd(a[i - 1], a[i + 1])) flag = 1;
    if (flag) std::cout << "Rude\n";
    else std::cout << "Elegant\n";
    return 0;
}