Camp Day5 Div2

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

线段相交的判断。

发表评论

电子邮件地址不会被公开。 必填项已用*标注