# E

# 题目大意

给定 $n$ 个数 $A = (a_1, \ldots, a_n)$ ，然后需要你回答 $n$ 个问题，第 $i$ 个问题，请问 $i$ 是否能被若干个 $A$ 中的数的乘积表示？（可以重复选数）

# 数据范围

$1 \le a_i \le n \le 3 \times 10^5$

# 题解

因数 DP

不妨设 $dp_i$ 为乘积为 $i$ 所需的最小的数量（初始化为 1e18 ）
那么显然可以得到转移方程

$dp_i = \min_{x \in d(i)}(dp_i, dp_{i / x} + dp_x)$

其中， $d(x)$ 代表 $x$ 的所有因数

我们可以用 $n \log n$ 的复杂度预处理出所有因数，然后用 $\sum\limits_{i=1}^{n} | d(i) |$ 的复杂度，处理完

C++

void init() {
    for (int i = 1; i <= N; i++)
        for (int j = i; j <= N - 1; j += i)
            g[j].push_back(i);
}

void solve() {
    cin >> n, a = vector<int>(n + 1), dp = vector<int>(n + 1, 1e18);
    for (int i = 1; i <= n; i++)    cin >> a[i], dp[a[i]] = 1;

    for (int i = 1; i <= n; i++) {
        for (int t : g[i])    dp[i] = min(dp[i], dp[i / t] + dp[t]);
        cout << (dp[i] == 1e18 ? -1 : dp[i]) << ' ';
    }

    cout << '\n';
}

# F

# 题目大意

给定一个起点 $(fx, fy)$ 和一个终点 $(ex, ey)$
在其中有 $n$ 个点，每次只能 向右 ， 向上 ， 向下 三种走的方式
问从起点到终点最少需要走多少步？

# 数据范围

$1 \le n \le 2 \times 10^5$
$1 \le fx, fy, ex, ey \le 10^9, \quad fx < x_i < e_x, \quad 1 \le y_i \le 10^9$

# 题解

Status = (value, Point(x, y))
显然，为了不多走，我肯定每次的终点都是相同 $x$ 的最高 $/$ 最低点
不妨假设， $Status ~ dp[i][0]$ 为第 $i$ 步以 dp[i][0].point 作为结尾，需要最少走 dp[i][0].value 步； dp[i][1] 则是以最高点，其他含义类似

$p1$ 为当前步的最低点， $p2$ 为当前步的最高点
$lsP1$ 为上一步的最低点， $lsP2$ 为上一步的最高点

则转移方程为
dp[i][0].value = min(getDis(lsP2, p2) + lsV2, getDis(lsP1, p2) + lsV1) + getDis(p1, p2);
dp[i][1].value = min(getDis(lsP2, p1) + lsV2, getDis(lsP1, p1) + lsV1) + getDis(p1, p2);

C++

struct Point {
    int x, y;
};

struct Status {
    int value;
    Point p;
};

vector<Point> points;
int n, fx, fy, ex, ey;

vector<vector<Status>> dp;

int getDis(Point a, Point b) {
    return abs(a.x - b.x) + abs(a.y - b.y);
}

void solve() {
    cin >> n >> fx >> fy >> ex >> ey, n += 1;
    points = vector<Point>(n + 1);
    dp = vector<vector<Status>>(n + 1, vector<Status>(2));

    // dp[i][0], dp[i][1] 分别表示，第 i 步，以最高点、最低点作为起点，那么就以相反的点作为终点

    for (int i = 1; i < n; i++)    cin >> points[i].x;
    for (int i = 1; i < n; i++)    cin >> points[i].y;
    points[n] = {ex, ey};

    sort(points.begin() + 1, points.end(), [](Point a, Point b) {
        if (a.x == b.x)
            return a.y < b.y;
        return a.x < b.x;
    });

    dp[0][0] = dp[0][1] = {0, {fx, fy}};

    int i = 1;

    for (int k = 1; k <= n; k++) {
        Point p1 = points[k];

        int tmpIdx = k;
        while (tmpIdx <= n && points[tmpIdx].x == points[k].x)  tmpIdx++;
        tmpIdx--;

        Point p2 = points[tmpIdx];

        Point lsP1 = dp[i - 1][0].p, lsP2 = dp[i - 1][1].p;
        int lsV1 = dp[i - 1][0].value, lsV2 = dp[i - 1][1].value;

        dp[i][0].p = p1, dp[i][1].p = p2;

        dp[i][0].value = min(getDis(lsP2, p2) + lsV2, getDis(lsP1, p2) + lsV1) + getDis(p1, p2);
        dp[i][1].value = min(getDis(lsP2, p1) + lsV2, getDis(lsP1, p1) + lsV1) + getDis(p1, p2);

        i += 1, k = tmpIdx;
    }

    cout << dp[i - 1][0].value << '\n';
}

# G

# 题目大意

这是一道交互题

给你一棵树，然后系统会指定一条 “路径”**

你可以对电脑进行询问，问 $(a, b)$ 是否和指定的那条路径相交，系统会回复 $0 / 1$
最多可以询问不超过 $\lfloor \frac{n}{2} \rfloor + 1$ 次
** 交互器是 $adaptive$ 的，指定的路径会根据询问发生变化

你需要做的是，输出任意一个在指定路径上的点

# 数据范围

$1 \le n \le 2 \times 10^5$

# 题解

最后结果，应该是只剩了一个点，那我们不妨每次两个两个点去排除，那怎么排除呢？
我们不妨按深度升序排序，然后两个两个点问，为什么能这样做呢？我们不妨证明一下

对于询问的两个点 $(a, b)$ ，不妨记他们的深度为 $(d_a, d_b)$
深度只会有两种情况

$d_a = d_b$ ，由于此时， $d_{a / b} - 1$ 的点，都被询问过了，所以如果得到了 $1$ 的回答，那一定 $a$ 或 $b$ 点就是答案
$d_a + 1 = d_b$ ，同理上方，深度小于等于 $d_a + 1$ 的其他点，都被排除过了，那么如果得到了 $1$ 的回答，那一定 $a$ 或 $b$ 点就是答案

如果有偶数个点，那经过这样的询问，最差可能是问到 $\lfloor \frac{n}{2} \rfloor$ 次的时候，返回 $1$ 。那么再问一次最后一次询问的 $(a, b)$ 中的某个点的任意一个点即可得到答案
如果有奇数个点，那经过这样的询问，最差可能是问到 $\lfloor \frac{n}{2} \rfloor$ 次的时候，返回 $0$ 。那么还没问到的点，就是答案

C++

int n;
vector<int> g[N];
vector<int> a, depth;
bitset<N> st;

void dfs(int u, int dep) {
    for (int v : g[u])
        if (!st[v])
            depth[v] = dep + 1, st[v] = true, dfs(v, dep + 1);
}

void solve() {
    cin >> n;

    a = vector<int>(n + 1), depth = vector<int>(n + 1);

    for (int i = 1; i <= n; i++)    g[i].clear(), st[i] = false;
    for (int i = 1, u, v; i < n; i++) {
        cin >> u >> v;
        g[u].push_back(v), g[v].push_back(u);
    }

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

    depth[1] = 1, st[1] = true;
    dfs(1, 1);

    sort(a.begin() + 1, a.end(), [](int x, int y) {
        return depth[x] < depth[y];
    });

    int flag;
    for (int i = 1; i < n; i += 2) {
        cout << "? " << a[i] << " " << a[i + 1] << endl;
        cin >> flag;

        if (flag == 1) {
            cout << "? " << a[i] << " " << a[i] << endl;
            cin >> flag;
            
            cout << "! "  << (flag ? a[i] : a[i + 1]) << endl;
            return;
        }
    }

    cout << "! " << a[n] << endl;
    cout.flush();
}

# E

# 题目大意

# 数据范围

# 题解

# F

# 题目大意

# 数据范围

# 题解

# G

# 题目大意

# 数据范围

# 题解

ABC-444