Codeforec Contest 462

#codeforce

题目链接在这里

这次的题目比较简单,做完ABC后试了下如何hack别人哈哈。

A. Appleman and Easy Task

题意: n*n的矩阵,由字母xo组成,问是否每个格子四边的格子为o的个数是偶数。

分析: 对每个格子计算一遍即可

int main()
{
    int n;
    char a[100][100];

    cin >> n;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> a[i][j];
        }
    }

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            int count = 0;
            if (i > 0 && a[i - 1][j] == 'o') {
                count++;
            }
            if (i < n - 1 && a[i + 1][j] == 'o') {
                count++;
            }
            if (j > 0 && a[i][j - 1] == 'o') {
                count++;
            }
            if (j < n - 1 && a[i][j + 1] == 'o') {
                count++;
            }

            if (count & 1) {
                cout << "NO" << endl;
                return 0;
            }
        }
    }

    cout << "YES" << endl;
    return 0;
}

B. Appleman and Card Game

题意: A有n张卡片,卡片上写着1个大写字母,B可以抽k张,1≤k≤n≤1e5,对B的每张卡片,得分数为B的相同字母的卡片个数, 最后总的的分数就是B的每张卡片的分数和。

分析:对于一个字母B有a张,这a张得分为a2,假设要取10张,102 > a2 + (10 - a)2,因此能多取就多取,贪心算法即可。

int main()
{
    LL n, k, ans = 0;
    cin >> n >> k;
    char card;
    LL count[100] = {0};

    for (int i = 0; i < n; ++i) {
        cin >> card;
        ++count[card - 'A'];
    }

    sort(count, count + 26);
    int i = 25;

    while (k > 0 && i >= 0) {
        if (k >= count[i]) {
            k -= count[i];
            ans += (count[i] * count[i]);
        }
        else {
            ans += (k * k);
            k = 0;
        }
        --i;
    }

    cout << ans << endl;


    return 0;
}

C. Appleman and Toastman

题意:初始状态A有n个数字,作为一组全部给B,从现在开始A每次收到的这组如果只有一个数字,则丢弃,否则将该组数字分成两组,两组都交给B,B还给A,如此往复, 直到没有数字。B每次收到卡片计算收到的数字和累加。

分析:使得最大的数字能够最晚丢弃,最开始丢弃的都是最小的,贪心算法,可以参考Huffman的思想。

int main()
{
    LL n, a[300001], ans = 0;
    cin >> n;
    for (LL i = 1; i <= n; ++i) {
        cin >> a[i];
        ans += a[i];
    }
    sort(a + 1, a + n + 1);

    for (LL i = 1; i <= n; ++i) {
        ans += (i * a[i]);
    }
    ans -= a[n];

    cout << ans << endl;

    return 0;
}

D. Appleman and Tree

题意:n个顶点,编号0,1,..,n-1,其中有黑白两个颜色,后面的顶点有且只有一条边指向前面的顶点,因此可以看做这是树,而不是图,不要被误解了。求将树分成多个子树,同时每个子树有且只有一个黑色节点的方法数。

分析:动态规划,对顶点v
dp[v][0]表示以v为root的树对父节点贡献0个黑色的情况数
dp[v][1]表示以v为root的树对父节点贡献1个黑色的情况数
注意v与父节点的边如果切断需要保证v为root的子树黑色数为1,这样才能满足题目要求

假设v有3个子树a,b,c

  1. 假设v本身为白色
    dp[v][1]即v为父节点贡献1个黑色的情况数,即为一个子树贡献1个黑色其余子树贡献0个情况数和
    dp[v][0]分两种情况:
    a. 所有子树均贡献0个黑色
    b. 一个子树贡献1个黑色其余子树贡献0个情况数,同时v与父节点的边切断
    即:
    dp[v][1] = dp[a][1] * dp[b][0] * dp[c][0] +
    dp[a][0] * dp[b][1] * dp[c][0] +
    dp[a][0] * dp[b][0] * dp[c][1]
    dp[v][0] = dp[a][0] * dp[b][0] * dp[c][0] + dp[v][1]
  2. 假设v本身为黑色
    如果v对父节点贡献0个黑色,那么只能切断v与父节点的边,同时为了使得仍然只有1个黑色节点,那么要满足v的子树均贡献0个
    即dp[v][0] = dp[a][0] * dp[b][0] * dp[c][0]
    如果v对父节点贡献1个黑色,那么不能切断v与父节点的边,同时为了使得只有1个黑色节点,那么要满足v的子树均贡献0个
    即dp[v][1] = dp[v][0]。

第一次解决树形DP的题目,如有不对还请指出。
另外注意mod操作在每次子树操作时都要做,否则会溢出。

const LL MOD = 1e9 + 7;
const int N = 1e5;
LL dp[N][2];
bool vis[N];
int n,v;
vector<int> edge[N];
int color[N];

void dfs(int index)
{
    vis[index] = true;
    dp[index][0] = 1;
    dp[index][1] = 0;

    for (unsigned int i = 0; i < edge[index].size(); ++i) {
        int u = edge[index][i];
        if (vis[u])
            continue;

        dfs(u);

        dp[index][1] *= dp[u][0];
        dp[index][1] += dp[index][0] * dp[u][1];
        dp[index][0] *= dp[u][0];

        dp[index][0] %= MOD;
        dp[index][1] %= MOD;
    }

    if (color[index] == 1) {
        dp[index][1] = dp[index][0];
    }
    else {
        dp[index][0] += dp[index][1];
    }

    dp[index][0] %= MOD;
    dp[index][1] %= MOD;
}

int main()
{
    cin >> n;
    for (int i = 1; i < n; ++i) {
        cin >> v;
        edge[i].push_back(v);
        edge[v].push_back(i);
    }

    for (int i = 0; i < n; ++i) {
        cin >> color[i];
    }

    dfs(0);

    cout << dp[0][1] << endl;
    return 0;
}