20230311比赛题解

Andy Shen2023/3/11大约 3 分钟

前言

本次比赛其实都是老题目，FJ 看着好（简单）的题目选了三道，连个思维题都没有。

第一题第二题是Quidrem出的，分别是腐朽阁内部赛 R1 的 T1 和 T3.第三题是我出的，是腐朽阁内部赛 R2 的 T3。欢迎大家加入重生阁

新手杀

我这里用了完全没有必要但是很 naive 的一个方法：先进行正常除法，然后使用 sprintf 输出到一个字符串中（sprintf 的用法和 printf 很像，区别在于前者是将结果输出到字符串，而后者是将结果输出到输入输出流。）然后手动遍历去除后置 0。

这题太简单了，所以我就给个 C 代码。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main()
{
    float a, b;
    scanf("%f%f", &a, &b);
    char ans[1000000];
    memset(ans, 0, sizeof(ans));
    sprintf(ans, "%.3f", a / b);
    int i;
    for (i = 999999; i >= 0; i--) {
        if (ans[i] == '.') {
            i--;
            break;
        }
        if (ans[i] != 0 && ans[i] != '0') {
            break;
        }
    }
    for (int j = 0; j <= i; j++) {
        putchar(ans[j]);
    }
    return 0;
}

数组的最大代价

一个线性动规题。

首先，要考虑到一点： $A_{i}$ 只有两种可能，要么取 $1$ ，要么取 $B_{i}$ 。取前者有利于后面的计算（后面的值减去这个值得到的绝对值更大）。取后者有利于当前计算（当前值减去前面值更大）。

显然后面的决策和过去怎么选是没有相关性的（后面怎么选择只和与它最近的一个元素选择 $1$ 还是 $B_{i - 1}$ 相关），符合无后效性原则。

后面问题的决策可以通过前面的决策得出，前面的决策分成两类（选 $1$ 还是选 $B_{i}$ ），然后可以用这两类的结果推出后者，符合最优子结构特性。

显然，到这一步就可以发现这是个动规了。

我们列出动规式子就是这样（ $d p [i] [0]$ 表示第 $i$ 位取 $1$ ， $d p [i] [1]$ 表示第 $i$ 位取 $B_{i}$ ）：

{\begin{aligned} d p [i] [0] & = m a x (d p [i - 1] [0], d p [i - 1] [1] + A b s (B [i] - 1)) \\ d p [i] [1] & = m a x (d p [i - 1] [0] + A b s (B [i] - 1), d p [i - 1] [1] + A b s (B [i] - B [i - 1])) \end{aligned}

std:

#include <bits/stdc++.h>

using namespace std;

int b[50001];
int dp[50001][2];

int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> b[i];
    }
    for (int i = 2; i <= n; i++) {
        dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + abs(b[i] - 1));
        dp[i][1] = max(dp[i - 1][0] + abs(b[i] - 1), dp[i - 1][1] + abs(b[i] - b[i - 1]));
    }
    cout << max(dp[n][0], dp[n][1]) << endl;
    return 0;
}

分组

二分图判定板子题。

如果不知道二分图是什么，请移步OIWiki

显然，不存在男男，女女之间的搭配以及除了男女之外的性别，故搭配一定是男女。

很显然在二分图当中红色节点连接的一定是蓝色节点，蓝色节点连接的一定是红色节点。故我们从任意一个起点开始，将这个点标为红色，然后跑深搜进行红蓝染色。将遍历到的所有红色节点和蓝色节点分别加入两个 set 中，最后输出即可。

#include <bits/stdc++.h>

using namespace std;

constexpr int NOCOLOR = 0;
constexpr int RED = 1;
constexpr int BLUE = 2;
vector<int> G[100010];
int color[100010];
set<int> red;
set<int> blue;

void dfs(int x, int curcolor)
{
    if (curcolor == RED) {
        red.emplace(x);
        color[x] = RED;
    } else if (curcolor == BLUE) {
        blue.emplace(x);
        color[x] = BLUE;
    }
    for (auto it : G[x]) {
        if (!color[it]) {
            if (curcolor == RED) {
                dfs(it, BLUE);
            } else if (curcolor == BLUE) {
                dfs(it, RED);
            }
        }
    }
}

int main()
{
    int n, m;
    cin >> n >> m;
    int u, v;
    for (int i = 1; i <= m; i++) {
        cin >> u >> v;
        G[u].emplace_back(v);
        G[v].emplace_back(u);
    }
    dfs(1, RED);
    if (red.size() > blue.size()) {
        for (auto it : red) {
            cout << it << ' ';
        }
        cout << endl;
        for (auto it : blue) {
            cout << it << ' ';
        }
        cout << endl;
    } else {
        for (auto it : blue) {
            cout << it << ' ';
        }
        cout << endl;
        for (auto it : red) {
            cout << it << ' ';
        }
        cout << endl;
    }
    return 0;
}