Kalorona

P3914:染色计数题解

主要思路

这道题比较有趣，一开始我想出了\(O(n^3)\)的复杂度，打上去 TLE 之后思考前缀做差的方法，但是我太 Naive，不太相信（？）模意义下的减法，所以这个思路在我看了题解之后才搞定。

这道题的 DP 方程不难想到，为：

\[ dp[u][i] = \sum_{t \in dst} \sum_{j \in color(t)} dp[t][j], i \neq j \]

其实我们可以把第二维消掉，考虑总和\(tot[]\)数组，得：

\[ dp[u][i] = \sum_{t \in dst} tot[t] – dp[t][i] \]

然后就出来了。

代码

// P3914.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 5050, MOD = 1e9 + 7;
int head[MAX_N], current, n, m, tmpx, tmpy, dp[MAX_N][MAX_N], tot[MAX_N];
struct edge
{
    int to, nxt;
} edges[MAX_N << 1];
void addpath(int src, int dst)
{
    edges[current].to = dst, edges[current].nxt = head[src];
    head[src] = current++;
}
void dfs(int u, int fa)
{
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (edges[i].to != fa)
            dfs(edges[i].to, u);
    for (int i = 1; i <= m; i++)
    {
        if (!dp[u][i])
            continue;
        for (int e = head[u]; e != -1; e = edges[e].nxt)
        {
            if (edges[e].to == fa)
                continue;
            dp[u][i] = (1LL * dp[u][i] * 1LL * (tot[edges[e].to] - dp[edges[e].to][i])) % MOD;
        }
        while (dp[u][i] < 0)
            dp[u][i] += MOD;
        tot[u] = (1LL * tot[u] + 1LL * dp[u][i]) % MOD;
    }
}
int main()
{
    memset(head, -1, sizeof(head));
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &tmpy);
        for (int j = 1; j <= tmpy; j++)
            scanf("%d", &tmpx), dp[i][tmpx] = 1;
    }
    for (int i = 1; i < n; i++)
        scanf("%d%d", &tmpx, &tmpy), addpath(tmpx, tmpy), addpath(tmpy, tmpx);
    dfs(1, 0);
    printf("%d", tot[1] % MOD);
    return 0;
}

POJ2891:Strange Way to Express Integers 题解

思路

嗯，我这种数学菜鸡来写数学题的确很难过。

首先分析题意，明显的就是提供一些线性同余方程，然后求解。但是，与中国剩余定理不同的是，这道题不保证模数互质。

\[ x \equiv a_1 (mod\ m_1) \\ x \equiv a_2 (mod\ m_2) \\ x \equiv a_3 (mod\ m_3) \\ \dots \\ x \equiv a_i (mod\ m_i) \]

但是我们仍然可以用古老的扩展欧几里得算法来解这个问题，合并方程即可。

假设我们正在解第\(k\)个方程，设\(m=\prod_{i=1}^{k-1}\)，\(x\)为满足\(1\)~\(k-1\)个方程的解。我们知道，\(tm+x\)为前\(k-1\)个方程的通解，那么我们只需要在这一轮求出\(k\)并更新答案即可，也就是解：

\[ tm_{k-1} + x_{k-1} \equiv a_k(mod\ m_k) \\ tm_{k-1} + m_k y \equiv a_k – x_{k-1}(mod\ m_k) \]

放进 \(exgcd\) 里面解下即可。

代码

// POJ2891.cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX_N = 1e6 + 200;
ll exgcd(ll a, ll b, ll &x, ll &y)
{
    if (b == 0)
    {
        x = 1, y = 0;
        return a;
    }
    ll d = exgcd(b, a % b, x, y), z = x;
    x = y, y = z - (a / b) * y;
    return d;
}
int main()
{
    ll n;
    while (~scanf("%lld", &n))
    {
        ll x, y, a, b, k;
        scanf("%lld%lld", &a, &b);
        ll lcm = a, ans = b;
        bool flag = true;
        n--;
        while (n--)
        {
            scanf("%lld%lld", &a, &b);
            b = (b - ans % a + a) % a;
            ll d = exgcd(lcm, a, x, y);
            if (b % d)
                flag = false;
            else
                k = x * (b / d);
            ans += k * lcm;
            lcm = lcm / d * a;
            ans = (ans % lcm + lcm) % lcm;
        }
        if (flag)
            printf("%lld\n", ans);
        else
            puts("-1");
    }
    return 0;
}

 

P1072:Hankson 的趣味题题解

超级简洁的做法

看到这篇题解之后立马 A 掉了，真的很简洁的一个做法。

我们有\(gcd(x,a_0)=a_1\)，根据结论\(gcd(a,b)=c \to gcd(\frac{a}{c},\frac{b}{c})=1\)，可以推出：

\[gcd(\frac{x}{a_1},\frac{a_0}{a_1})\]

另一个式子\(lcm(x,b_0)=b_1\)可以转换为：

\[ lcm(x,b_0)=b_1 \\ gcd(x,b_0)*lcm(x,b_0)=xb_0 \\ gcd(x,b_0)=\frac{xb_0}{b_1} \\ gcd(\frac{b_1}{b_0},\frac{b_1}{x})=1 \]

可以看出，\(x\)为\(b_1\)的一个约数，\(a_1\)是\(x\)的一个约束，根据这两个条件和两个\(gcd\)条件，进行枚举即可。

代码

// CH3201.cpp
#include <bits/stdc++.h>
using namespace std;
int n, a0, a1, b0, b1;
int gcd(int a, int b) { return (b == 0) ? a : gcd(b, a % b); }
int main()
{
    scanf("%d", &n);
    while (n--)
    {
        int ans = 0;
        scanf("%d%d%d%d", &a0, &a1, &b0, &b1);
        int p = b1 / b0, q = a0 / a1;
        for (int x = 1; x * x <= b1; x++)
            if (b1 % x == 0)
            {
                if (x % a1 == 0 && gcd(p, b1 / x) == 1 && gcd(q, x / a1) == 1)
                    ans++;
                int y = b1 / x;
                if (x == y)
                    continue;
                if (y % a1 == 0 && gcd(p, b1 / y) == 1 && gcd(q, y / a1) == 1)
                    ans++;
            }
        printf("%d\n", ans);
    }
    return 0;
}

BZOJ1257:「CQOI2007」余数之和题解

神仙思路与证明

这道题可以将式子化简为：

\[ nk-\sum_{i=1}^{n} \lfloor \frac{k}{i} \rfloor * i \]

第一部分乘积即可，第二部分直觉告诉我们\(\lfloor \frac{k}{i} \rfloor\)在一段连续的\(i\)上会相等，也就是说，是分段的。每一段的和可以直接用等差数列来求就行。我们来探究一下段区间的左右端点。我们假设目标区间是\([i,?]\)，那么这一段区间的值肯定就是\(\lfloor \frac{k}{i} \rfloor\)，反求一下那么右端点就是\( \lfloor \frac{k}{\lfloor \frac{k}{i} \rfloor} \rfloor \)。可以证明右端点大于等于左端点。等差数列求和即可。

代码

// BZ1257.cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll n, k;
int main()
{
    scanf("%lld%lld", &n, &k);
    ll ans = n * k, gx;
    for (int x = 1; x <= n; x = gx + 1)
    {
        gx = (k / x) ? min(k / (k / x), n) : n;
        // x ~ gx same;
        ans -= (k / x) * (gx - x + 1) * (gx + x) / 2;
    }
    printf("%lld", ans);
    return 0;
}

P1108:低价购买题解

主要思路

第一问还是很好答的，用\(O(n^2)\)的时间来完成求最长下降子序列的 DP。第二问我们可以设一个数组为\(g[]\)来储存方案数。转移方程可以很显然的得出为：

\[ g[i] = \sum_{j = 1}^{i-1} g[j], 当 f[i] = f[j] + 1 且 arr[i]<arr[j] \]

但是我们还需要去重，假设我们已经计算了之前转移过来的情况，那么我们要消去之前等效的状态，也就是消去第\(j\)项，满足\(f[j] == f[i] 且 arr[i] == arr[j]\)。下面是代码：

代码

// P1108.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 5050;
int n, arr[MAX_N], f[MAX_N], g[MAX_N], tot;
bool cmp(int a, int b) { return a > b; }
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &arr[i]);
    for (int i = 1; i <= n; i++)
    {
        f[i] = 1;
        for (int j = 1; j < i; j++)
            if (arr[j] > arr[i])
                f[i] = max(f[j] + 1, f[i]);
        tot = max(tot, f[i]);
    }
    for (int i = 1; i <= n; i++)
    {
        if (f[i] == 1)
            g[i] = 1;
        for (int j = 1; j < i; j++)
        {
            if (f[i] == f[j] && arr[i] == arr[j])
                g[j] = 0;
            if (f[i] == f[j] + 1 && arr[j] > arr[i])
                g[i] += g[j];
        }
    }
    long long ans = 0;
    for (int i = 1; i <= n; i++)
        if (f[i] == tot)
            ans += g[i];
    printf("%d %lld", tot, ans);
    return 0;
}

P1415:拆分数列题解

思路

这道题其实第一个方程非常的显然，即\(f[i] = max\{f[i], j\}, number(f[j-1], j-1)<number(j,i)\)。第二个方程其实就是重构了一下状态结构，跟原本的\(f[]\)差不多，转移式\(dp[i] = max\{dp[i], j\}, number(i,j)<number(j+1, dp[j+1)\)。注意这道题要写高精度比较，要不然会 gg （我调这玩意半个小时）。

代码

// P1415.cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX_N = 550;
int f[MAX_N], dp[MAX_N], numarr[MAX_N];
string str;
bool smaller(int i, int j, int a, int b)
{
    int cur1 = i, cur2 = a;
    for (; j - cur1 > b - cur2; cur1++)
        if (numarr[cur1])
            return false;
    for (; j - cur1 < b - cur2; cur2++)
        if (numarr[cur2])
            return true;
    while (cur1 <= j)
    {
        if (numarr[cur1] < numarr[cur2])
            return true;
        else if (numarr[cur1] > numarr[cur2])
            return false;
        cur1++, cur2++;
    }
    return false;
}
int main()
{
    ios::sync_with_stdio(false);
    cin >> str;
    int siz = str.length();
    str = " " + str;
    for (int i = 1; i <= siz; i++)
        numarr[i] = str[i] - '0';
    for (int i = 1; i <= siz; i++)
    {
        f[i] = 1;
        for (int j = i; j >= 1; j--)
            if (smaller(f[j - 1], j - 1, j, i))
            {
                f[i] = max(f[i], j);
                break;
            }
    }
    dp[f[siz]] = siz;
    int cnt = 0;
    for (int i = f[siz] - 1; i >= 1 && !numarr[i]; i--)
        cnt++, dp[i] = siz;
    for (int i = f[siz] - cnt - 1; i >= 1; i--)
    {
        dp[i] = i;
        for (int j = f[siz] - 1; j >= i; j--)
            if (smaller(i, j, j + 1, dp[j + 1]))
            {
                dp[i] = max(dp[i], j);
                break;
            }
    }
    bool flag = true;
    for (int pos = 1; pos <= siz;)
    {
        if (flag)
            flag = false;
        else
            printf(",");
        for (int i = pos; i <= dp[pos]; i++)
            printf("%d", numarr[i]);
        pos = dp[pos] + 1;
    }
    return 0;
}