Camp Day5 Div2

Jan 24, 2019 由 小羊

Problem A - Gactus Draw

由于有要求边不能有公共点，那么我们可以让每颗子树都相离较远。如果我们将树的 dfs序 作为横坐标，depth 作为纵坐标，那么构造出来的图形一定是符合要求的。

Problem C - Division

题中的操作相当于将数字进行一次右移，相当于减去了某个某个指定的数值。

如果我们将会被减去的数记录下来，至多 $32n$ 个，那么先把和保存下来，然后减去的数保存下来排个序，把最前面至多 $k$ 个数字加进和即可。

Problem F - Kropki

考虑做一个状压dp，记为 $dp[S][n]$，表示以状态 $S$ 排布的数字以 $n$ 为结尾的方案数，其中 $S$ 中已选上的元素数量为 $c(S)$。另外点的01串存在 $stat[]$ 中。那么有

$dp[S][n] = \begin{cases} \sum_{u=2n,n/2} dp[S-\lbrace n \rbrace][u], & stat[c(S)]=1 \\ \sum_{u\not= 2n,n/2}dp[S-\lbrace n\rbrace][u], & stat[c(S)]=0 \end{cases}$

然后计算即可。可以写成搜索的形式，用起bitset，然后记忆化，这样写法似乎会舒服一点（大雾）。

#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
const int LEN = 1 << 15;
const int mod = 1e9+7;
lld dp[LEN][16], n, dpt;
char st[20];

lld dfs(int S, int end)
{
    bitset<15> wtf(S);
    size_t len = wtf.count();
    if (!wtf[end-1]) return 0;
    if (len == 1) return 1;
    if (dp[S][end] != -1) return dp[S][end];

    lld ans = 0;
    wtf.flip(end-1);
    dpt++;
    for (int i = 1; i <= n; i++)
    {
        if (!wtf[i-1]) continue;

        if (end == i * 2)
        {
            if (st[len-2] == '1')
                ans += dfs(wtf.to_ulong(), i);
        }
        else if (i == end * 2)
        {
            if (st[len-2] == '1')
                ans += dfs(wtf.to_ulong(), i);
        }
        else
        {
            if (st[len-2] == '0')
                ans += dfs(wtf.to_ulong(), i);
        }
    }

    return dp[S][end] = ans % mod;
}

int main()
{
    memset(dp, -1, sizeof(dp));
    scanf("%lld %s", &n, st);
    lld ans = 0;
    for (int i = 1; i <= n; i++)
        ans = (ans + dfs((1<<n)-1, i)) % mod;
    printf("%lld\n", ans);
    return 0;
}

很迷啊，不会写最原始的状压dp，所以只能写写这种奇怪的东西了。

Problem H - Nested Tree

考虑一棵树的每对点间距离和的一个性质：对于某个边 $e(u,v)$，在距离和中的贡献是 $u$ 侧的节点数乘以 $v$ 侧节点数。那么，我们可以利用一次dfs，对以某节点为根的子树进行搜索，统计出子树中的节点个数 $x$，则边另一侧的节点个数为 $nm-x$，所以答案就可以很轻松的维护出来。

#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
const int mod = 1e9+7;
vector<int> G[1000010];
bool vis[1000010];
int n, m;
long long ans;

int dfs(int u)
{
    if (vis[u]) return -1;
    vis[u] = true;

    int cnt = 1;
    for (auto v : G[u])
    {
        int x = dfs(v);
        if (x == -1) continue;
        ans += 1LL * x * (n*m - x) % mod;
        cnt += x;
    }

    return cnt;
}

int main()
{
    int a, b, u, v;
    scanf("%d %d", &n, &m);

    for (int i = 1; i < n; i++)
    {
        scanf("%d %d", &u, &v);

        for (int j = 0; j < m; j++)
        {
            G[j*n+u].push_back(j*n+v);
            G[j*n+v].push_back(j*n+u);
        }
    }

    for (int i = 1; i < m; i++)
    {
        scanf("%d %d %d %d", &a, &b, &u, &v);
        G[(a-1)*n+u].push_back((b-1)*n+v);
        G[(b-1)*n+v].push_back((a-1)*n+u);
    }

    assert(dfs(1) == n*m);
    printf("%lld\n", (ans % mod + mod) % mod);
    return 0;
}

Problem J - Special Judge

线段相交的判断。