小白月赛100

A ACM 中的 A 题

你有三根长度分别为 $a, b, c$ 的木棒

现在必须选择将其中一根木棒，将其长度修改为原来的两倍

那么有没有可能仅用修改后的三根木棒组成一个三角形 ?

很坑

#define int long long
void solve() {
    int a, b, c;cin >> a >> b >> c;
    if (a * 2 + b > c && a * 2 + c > b && b + c > a * 2) {
        cout << "Yes\n";return;
    }
    if (a + b * 2 > c && a + c > b * 2 && b * 2 + c > a) {
        cout << "Yes\n";return;
    }
    if (a + b > c * 2 && a + c * 2 > b && b + c * 2 > a) {
        cout << "Yes\n";return;
    }

    cout << "No\n";
}

B ACM 中的 C 题

有一个长度为 $n$ 的数组 ${a_{i}}$

已知 ${a_{i}}$ 无相同元素且已经从小到大排序

你可以多次交换任何相邻位置的 2 个元素
直到每个位置的元素和原来都不相同
若有解请输出最小交换次数，反之无解输出 -1

void solve() {
    int n;cin >> n;
    vector<int> a(n + 1);
    for (int i = 1;i <= n;i++)cin >> a[i];
    if (n == 1) {
        cout << "-1\n";return;
    }
    cout << (n + 1) / 2 << '\n';
}

C ACM 中的 M 题

**有一个长度为 $n$ 的数组 ${a_{i}}$ ，每个 ${a_{i}}$ 属于且仅属于一个类别 ${b_{i}}$

已知 ${a_{i}}$ 无相同元素

你可以多次交换同一个类别下任意2 个元素
直到每个位置的元素和原来都不相同
若有解请输出最小交换次数，反之无解输出 -1

#define int long long
void solve() {
    int n;cin >> n;
    vector<int> a(n + 1), b(n + 1);
    map<int, int> mp;
    for (int i = 1;i <= n;i++)cin >> a[i];
    for (int i = 1;i <= n;i++)cin >> b[i], mp[b[i]]++;
    int ans = 0;
    for (auto [x, y] : mp) {
        if (y == 1) {
            cout << "-1\n";return;
        }
        ans += (y + 1) / 2;
    }
    cout << ans << '\n';
}

D ACM 中的 AC 题

众所周知，出题人没玩过双人成行，所以出了这道题

你一觉醒来，发现你和另一个时空的你被困在 $n * m$ 大小矩形孤岛的 $(x, y)$ 地块上

在地图中最多包含平地，陷阱和传送门三种不同地块

你和另外一个时空的你都可以上下左右移动到相邻的地块中

可是你和外一个时空的你只能同时以相反的方向移动

两人均不能跨过边界，即到达孤岛外的地方；任意人到达陷阱处会立刻死亡

现在，你能否给出一个移动序列，使得两人均能从传送门离开，其中任意一人到达传送门后一定会离开且不会再回到该孤岛中;

如果有，请输出该序列的最短长度、反之输出 -1

Solution

赛时写爆内存了...

本题的关键在于 dis 数组：dis[i][j] 用于求出 $(i, j)$ 点(非障碍物非传送门)到最近的传送门需要走的步数，方便后面两个人同时走时一次计算出结果。

妙的，还是挺 EDU 的

int vis[2010][2010], dis[2010][2010];
char s[2010][2010];
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
void solve() {
    int n, m, sx, sy;cin >> n >> m >> sx >> sy;
    queue<array<int, 3>>p;
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= m;j++) {
            cin >> s[i][j];
            if (s[i][j] == '@')p.push({i,j,0});
        }
    }
    while (p.size()) {
        auto [x, y, cnt] = p.front();p.pop();

        for (int i = 0;i < 4;i++) {
            int a = x + dx[i], b = y + dy[i];
            if (a<1 || b<1 || a>n || b>m || dis[a][b])continue;
            if (s[a][b] == '.') {
                p.push({a,b,cnt + 1});
                dis[a][b] = dis[x][y] + 1;
            }
        }
    }

    queue<array<int, 5>>q;
    q.push({sx,sy,sx,sy,0});
    int ans = 1e9;
    while (q.size()) {
        auto [x1, y1, x2, y2, cnt] = q.front();q.pop();

        for (int i = 0;i < 4;i++) {
            int ix = x1 + dx[i], iy = y1 + dy[i];
            int jx = x2 - dx[i], jy = y2 - dy[i];
            if (ix < 1 || iy < 1 || ix>n || iy>m || vis[ix][iy] || vis[ix][iy])continue;
            if (jx < 1 || jy < 1 || jx>n || jy>m)continue;
            if (s[ix][iy] == '@' && s[jx][jy] != '#') {
                ans = min(ans, cnt + 1 + dis[jx][jy]);
            }
            if (s[ix][iy] == '.' && s[jx][jy] == '.') {
                vis[ix][iy] = 1;
                q.push({ix,iy,jx,jy,cnt + 1});
            }
        }
    }
    if (ans == 1e9)ans = -1;
    cout << ans << '\n';
}

E ACM 中的 CM 题

现在在你前面有 $n$ 个地雷

刚刚学会瞬移的你决定排走所有地雷

遗憾的是，你的初始排雷能力 $m = 0$ ，但你知道

当排雷能力为 $m$ 时，你可以任何时刻在当前位置 $l$ 处将 $[l, l + m]$ 中的雷全部排走

也可以在任何时刻任何地点，将排雷能力从 $m$ 变为 $m + 1$

以上两种操作都需要花费 1 的时间，但瞬移不花费时间！

求排所有雷所需最小时间！

Solution

根据贪心的思想，一定是先提升排雷能力的。

void solve() {
    int n;cin >> n;
    vector<int> a(n + 1);
    for (int i = 1;i <= n;i++) cin >> a[i];
    sort(a.begin() + 1, a.end());

    auto check = [&](int i) {
        int ans = i, pos = a[i];
        while (1) {
            ans++;
            pos = upper_bound(a.begin() + 1, a.end(), pos + i) - a.begin();
            if (pos == a.end() - a.begin())break;
            pos = a[pos];
        }
        return ans;
        };
    int ans = 1e9;
    for (int i = 1;i <= n;i++) {
        ans = min(ans, check(i));
    }
    cout << ans << '\n';
}

F ACM 中的 ACM 题

无聊的你回想起了 $A$ 题的三角形，于是你想到了一个新的问题：

在一个连通图中，任何一条边都属于一个集合

如果两条边 $a, b$ 属于同一个集合当且仅当满足以下条件之一

1. $a, b$ 是某一个三角形的两条边

2. 存在边 $c$ ，使得 $a, c$ 属于同一个集合且 $b, c$ 属于同一个集合

那么请问，以下连通图的所有边是否都属于同一个集合？

Solution

三元环计数

环计数问题 - OI Wiki