AtCoder Beginner Contest 248 赛时记录

目录

• A – Lacked Number
• B – Slimes
• C – Dice Sum
• D – Range Count Query
• E – K-colinear Line
• F – Keep Connect

手速场。手速场。手速场。手速场。手速场。

上大分。上大分。上大分。上大分。上大分。

A – Lacked Number

随便标记看看哪个数没出现过，或者拿 /(45/) 去把所有数减掉剩下的数就是。

B – Slimes

暴力乘，算次数，做完了。

C – Dice Sum

简单 DP。

设 /(f_{i,j}/) 表示前 /(i/) 个数的和为 /(j/) 的方案数。

/[f_{i,j} = /sum_{k=1}^{m} f_{i-1,j-k}
/]

D – Range Count Query

对每个颜色开一个 vector，然后存出现的位置。

对于每次询问直接在对应 vector 里 upper_bound 出和合法的左右端点相减就能得到答案。

signed main() {
    n = read();
    for(int i = 1; i <= n; ++i) {
        a[i] = read();
        b[a[i]].push_back(i);
    }
    Q = read();
    for(int i = 1, l, r, x; i <= Q; ++i) {
        l = read(), r = read(), x = read();
        int L = upper_bound(b[x].begin(), b[x].end(), l - 1) - b[x].begin() - 1;
        int R = upper_bound(b[x].begin(), b[x].end(), r) - b[x].begin() - 1;
        cout << R - L << "/n";
    }
	return 0;
}

E – K-colinear Line

枚举两个点确定一条直线，然后枚举第三个点判断有多少点在这个直线上。

判断直线的方式我们采用向量的形式，/(i,j,k/) 三个点可以得到两个向量 /((a,b) = (x_i-x_k,y_i-y_k), (c,d) = (x_j-x_k,y_j-y_k)/)，那如果 /(ad=bc/) 就说明这三个点在一条直线上。

然后发现这样会算重很多。

对于一条有 /(K/) 个点的直线来说，会被算重 /(/frac{K(K-1)}{2}/)，所以统计 /(K/) 个点的直线有几条，计算贡献的时候除以 /(/frac{K(K-1)}{2}/) 就好了。

bool Check(int i, int j, int k) {
    int ax = x[i] - x[k], ay = y[i] - y[k];
    int bx = x[j] - x[k], by = y[j] - y[k];
    return ax * by == ay * bx;
}

signed main() {
    n = read(), K = read();
    if(K == 1) { return puts("Infinity"), 0; }
    for(int i = 1; i <= n; ++i) x[i] = read(), y[i] = read();
    for(int i = 1; i <= n; ++i) {
        for(int j = i + 1; j <= n; ++j) {
            int res = 2;
            for(int k = 1; k <= n; ++k) {
                if(k == i || k == j) continue;
                if(Check(i, j, k)) res ++;
            }
            cnt[res] ++;
        }
    }
    for(int i = K; i <= n; ++i) ans += cnt[i] * 2 / i / (i - 1);
    cout << ans << "/n";
	return 0;
}

F – Keep Connect

考虑直接 DP。

一开始的一个想法是设 /(f_{i,j,0/1}/) 表示前 /(i/) 列删了 /(j/) 条边第 /(i/) 列中间那条边删没删，然后发现你转移的时候不知道最后的结果合不合法，因为不知道连通性，所以把意义换一下，改成表示前 /(i/) 列删了 /(j/) 条边是否联通的方案数。

然后在打草纸上画一下所有情况进行转移即可。

最后可以得出：

初始化 /(f_{1,0,1} = f_{1,1,0} = 1/)，

/[/begin{aligned}
f_{i,j,1} & = f_{i-1,j,1} + 3 f_{i-1,j-1,1} + f_{i-1,j,0} //
f_{i,j,0} & = f_{i-1,j-1,0} + 2 f_{i-1,j-2,1}
/end{aligned}
/]

答案就是 /(f_{n,i,1}/)。

signed main() {
    n = read(), P = read();
    f[1][0][1] = 1, f[1][1][0] = 1;
    for(int i = 1; i <= n; ++i) {
        for(int j = 0; j <= n - 1; ++j) {
            f[i][j][1] += f[i - 1][j][1];
            if(j > 0) f[i][j][1] += f[i - 1][j - 1][1] * 3;
            f[i][j][1] += f[i - 1][j][0];
            if(j > 0) f[i][j][0] += f[i - 1][j - 1][0];
            if(j > 1) f[i][j][0] += f[i - 1][j - 2][1] * 2;
            f[i][j][1] %= P, f[i][j][0] %= P;
        }
    }
    for(int i = 1; i <= n - 1; ++i) {
        cout << f[n][i][1] << " ";
    }
	return 0;
}