# C

# 题目大意

给你一个序列 $A = (a_1, \ldots, a_n)$ ，序列内的数只能是 $1 \to 6$
你可以对这个序列进行任意次（可以为 $0$ ）操作，每次操作可以任意把一个位置变为 $1 \to 6$ 任意一个数
请问，把序列变成相邻的数不相等且相邻的数之和不为 $7$ 的最小操作次数是多少

# 数据范围

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

# 题解

很简单的 $DP$
定义 dp[i][j] 为第 $i$ 个数操作后为 $j$ 的合法序列的最小操作次数
那么显然

$dp[i][j] = \min_{1 \le k \le 6,k \neq j,k \neq 7 - j} dp[i-1][k] + (a[i] = k)?$

C++

void solve() {
    cin >> n;
    a = vector<int>(n + 1);
    dp = vector<vector<int>>(n + 1, vector<int>(7));

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

    for (int i = 1; i <= n; i++) {
        for (int num = 1; num <= 6; num++) {
            int minn = 1e18;

            for (int k = 1; k <= 6; k++)
                if (k != 7 - num && k != num)
                    minn = min(minn, dp[i - 1][k]);

            dp[i][num] = minn + (a[i] != num);
        }
    }

    int res = 1e18;
    for (int k = 1; k <= 6; k++)    res = min(res, dp[n][k]);

    cout << res << "\n\n";
}

# D

# 题目大意

这是一个构造题目
对于序列 $A = (a_1, \ldots, a_n)$ ，定义 $f(x)$ 如下

$f(x) = \sum\limits_{i = 1}^{n} a_i \times |i - x|$

现在，我给你 $f(1), \ldots, f(n)$ ，请你构造一个 $A = (a_1, \ldots, a_n)$

# 数据范围

$1 \le n \le 3 \times 10^5$
$|a_i| \le 1000$
| f(i) | \le 10^

# 题解

~~感觉比 C 简单，没啥算法，就数学变换一下~~
以 $n = 4$ 距离

describe

f(1) = 0*a1 + 1*a2 + 2*a3 + 3*a4
f(2) = 1*a1 + 0*a2 + 1*a3 + 2*a4
f(3) = 2*a1 + 1*a2 + 0*a3 + 1*a4
f(4) = 3*a1 + 2*a2 + 1*a3 + 0*a4

=>

f(4) - f(3) = SUM - 2*a4
f(3) - f(2) = SUM - 2*a3 - 2*a4
...

显然， f(4) - f(3) - ( f(3) - f(2) ) = 2*a3 ，然后以此类推，可以得到

a_2, \ldots, a_{n - 1}

然后利用

f_1

和

f_2

去计算

a_1

和

a_n

即可

C++

void solve() {
    cin >> n, f = vector<int>(n + 1), a = vector<int>(n + 1);

    for (int i = 1; i <= n; i++)    cin >> f[i];

    int l = n, r = n - 1;

    int pre = f[l] - f[r];
    l--, r--;

    while (r >= 1) {
        int ls = f[l] - f[r];
        a[l] = (pre - ls) / 2;
        pre = ls, l--, r--;
    }

    // f[1] = a2 + 2 * a3 + .... + (n - 1) an
    // an = f[1] - a2
    int sum1 = 0;
    for (int i = 2; i <= n - 1; i++)    sum1 += a[i] * (i - 1);
    a[n] = (f[1] - sum1) / (n - 1);

    // f[2] = a1 + 0 + a3 + ... + (n - 2) an
    int sum2 = 0;
    for (int i = 3; i <= n; i++)    sum2 += a[i] * (i - 2);
    a[1] = (f[2] - sum2);

    for (int i = 1; i <= n; i++)    cout << a[i] << ' ';
    cout << '\n';
}

# E

# 题目大意

你现在有一棵树，树有 $n + 1$ 个结点（ $n$ 是奇数）
$0$ 点的儿子是 $1$ ，且只有 $1$ 一个儿子；其余的点，要么有两个儿子，要么没有儿子

你现在需要计算的是，从 $1 \to n$ 任意一个点，到 $0$ 点的诡异距离，其定义是这样的
你要计算从当前点，进行诡异移动，移动到 $0$ 点的步数。这种移动的规则是，每个点有三种状态： L 、 R 、 空 ，初始时，全为空

如果当前点是叶子，则移动到其父亲
否则
- 如果当前点为 空 ，则变为 L 然后移动到左孩子
- 如果当前点为 L ，则变为 R 然后移动到右孩子
- 如果当前点为 R ，则变为 空 然后移动到父亲结点

# 数据范围

$1 \le 3 \times 10^5 \le n$
结果可能很大，你需要输出结果 $\mod 10^9 + 7$

# 题解

这种移动，看规则可能很奇怪，但其实就是，每个结点都要做一遍 $DFS$

有一个前置的知识，对于树的任意一个点，若深搜然后回到原点，其需要走的步数是：

$2 \cdot size - 2$

$size$ 是以该点为根的树的大小（包括当前根）

那么我们不妨做两遍 $DFS$ ，第一遍 $DFS$ 计算出 $size[]$ ，然后第二遍 $DFS$ 则可以计算出答案

C++

int dfs(int u) {
    if (u == 0) return 0;
    return (s[u] = (dfs(p[u].first) + dfs(p[u].second) + 1) % MOD);
}

void ddffss(int u, int resU) {
    if (u == 0)
        return;

    res[u] = (resU + 2 * s[u] % MOD - 1) % MOD;

    ddffss(p[u].first, res[u]), ddffss(p[u].second, res[u]);
}

void solve() {
    cin >> n;

    s = vector<int>(n + 1), p = vector<PII>(n + 1), res = vector<int>(n + 1);

    for (int i = 1; i <= n; i++)   cin >> p[i].first >> p[i].second;

    dfs(1), ddffss(1, 0);

    for (int i = 1; i <= n; i++)    cout << res[i] << ' ';

    cout << '\n';
}

# F

# 题目大意

给你 $n$ 个二次函数 $F = (f_1, \ldots, f_n), \quad f_i = a_i \cdot x^2 + b_i \cdot x + c_i$

如果对于所有的 $x \in \mathbb{R}$ 都满足 $f(x) \neq g(x)$ ，则称 $f$ 和 $g$ 是独立函数

请你对于 $i = 1 \to i = n$ ，找出包含 $f_i$ 的，最大的独立函数子集的大小

# 数据范围

$1 \le n \le 3000$

# 题解

对于 $f = a_1 \cdot x^2 + b_1 \cdot x + c_1$ 和 $g = a_2 \cdot x^2 + b_2 \cdot x + c_2$ ，若是独立函数，则 $f = g$ 无交点

$(a_1 - a_2) \cdot x^2 + (b_1 - b_2) \cdot x + (c_1 - c_2) = 0$

方程无实根

同时，两个函数无交点，则必然存在严格的大于 / 小于关系

根据上面的严格大于 / 小于的关系，那么可以建一个有向图，然后对于 $i$ ，则只要在图中找最长链即可

C++

int dfs(int u, int t) {
    if (res[t][u]) return res[t][u];

    if (g[t][u].size() == 0) {
        return (res[t][u] = 1);
    }

    int maxx = 0;

    for (int v : g[t][u])   maxx = max(maxx, dfs(v, t));

    return res[t][u] = maxx + 1;
}

void solve() {
    cin >> n, f = vector<F>(n + 1);
    rd1 = vector<int>(n + 1), rd2 = vector<int>(n + 1);
    res[1] = vector<int>(n + 1), res[2] = vector<int>(n + 1);

    for (int i = 1; i <= n; i++)
        cin >> f[i].a >> f[i].b >> f[i].c, g[1][i].clear(), g[2][i].clear();

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == j) continue;

            int a1 = f[i].a, b1 = f[i].b, c1 = f[i].c;
            int a2 = f[j].a, b2 = f[j].b, c2 = f[j].c;

            int delta = (b1 - b2) * (b1 - b2) - 4 * (a1 - a2) * (c1 - c2);

            if (delta < 0 || a1 == a2 && b1 == b2) {
                if (c1 > c2) {
                    g[1][i].push_back(j), rd1[j]++;

                    g[2][j].push_back(i), rd2[i]++;
                }
                else {
                    g[1][j].push_back(i), rd1[i]++;
                    g[2][i].push_back(j), rd2[j]++;
                }
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        if (rd1[i] == 0)    dfs(i, 1);
        if (rd2[i] == 0)    dfs(i, 2);
    }

    for (int i = 1; i <= n; i++)    cout << res[1][i] + res[2][i] - 1 << ' ';
    cout << '\n';
}

DP Div3 构造

# C

# 题目大意

# 数据范围

# 题解

# D

# 题目大意

# 数据范围

# 题解

# E

# 题目大意

# 数据范围

# 题解

# F

# 题目大意

# 数据范围

# 题解

CF-1076