【LGR-070】洛谷 3 月月赛 I & EE Round 1 Div.2 题解

作者: xht37 分类: 题解 发布时间: 2020-03-08 20:09

点击数:118

【LGR-070】洛谷 3 月月赛 I & EE Round 1 Div.2

苏联人

不考虑复杂度的模拟题,是个人都能 AC 吧。

代码瞎写的,可能可以简洁一点,但是不重要。

const int N = 11;
int n = 8, x, y;
bool v[N][N];
char s[N][N];

int main() {
    for (int i = 1; i <= n; i++) rds(s[i], n);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            v[i][j] = 1;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (s[i][j] == 'B') {
                v[i][j] = 0;
                x = i - 1, y = j - 1;
                while (x && x <= 8 && y && y <= 8 && s[x][y] == '.')
                    v[x][y] = 0, --x, --y;
                x = i - 1, y = j + 1;
                while (x && x <= 8 && y && y <= 8 && s[x][y] == '.')
                    v[x][y] = 0, --x, ++y;
                x = i + 1, y = j - 1;
                while (x && x <= 8 && y && y <= 8 && s[x][y] == '.')
                    v[x][y] = 0, ++x, --y;
                x = i + 1, y = j + 1;
                while (x && x <= 8 && y && y <= 8 && s[x][y] == '.')
                    v[x][y] = 0, ++x, ++y;
            }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (s[i][j] == 'R') {
                v[i][j] = 0;
                x = i - 1, y = j;
                while (x && x <= 8 && y && y <= 8 && s[x][y] == '.')
                    v[x][y] = 0, --x;
                x = i + 1, y = j;
                while (x && x <= 8 && y && y <= 8 && s[x][y] == '.')
                    v[x][y] = 0, ++x;
                x = i, y = j - 1;
                while (x && x <= 8 && y && y <= 8 && s[x][y] == '.')
                    v[x][y] = 0, --y;
                x = i, y = j + 1;
                while (x && x <= 8 && y && y <= 8 && s[x][y] == '.')
                    v[x][y] = 0, ++y;
            }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++)
            putchar(v[i][j] + '0');
        putchar('\n');
    }
    return 0;
}

迫害

贪心的构造,答案为 $2^m \times (n+1) – 1$。

int main() {
    int n, m;
    rd(n), rd(m);
    print(((modint)2 ^ m) * (n + 1) - 1);
    return 0;
}

代价

考虑一种简单的删除方法,按照 $1 \sim n$ 的顺序依次删除,这时的代价为 $\sum_{i = 1}^{n – 1} a_{i} \times a_{i+1} + a_{n}$。

实际上这已经是一个较优解了,事实上对于 $i \in [1,n)$,$a_i, a_{i+1}$ 在最终的答案中一定都要被相乘一次。原因在于假设不被相乘,就意味着 $a_i, a_{i+1}$ 其中有一个先被删除了,然而先被删除的时候一定有相乘过,因此矛盾。

现在我们找到了一个较优解 $\sum_{i = 1}^{n – 1} a_{i} \times a_{i+1} + a_{n}$,考虑如何变成最优解。

首先来看这个 $a_n$,显然可以变成 $\min_{i=1}^n a_i$,具体方法是,假设最小的位置为 $p$,我们先按照 $1 \sim p – 1$ 的顺序依次删除,再按照 $n \sim p + 1$ 的顺序依次删除即可。

再来看这个 $\sum_{i=1}^{n-1} a_i \times a_{i+1}$。

刚才提到每两个相邻的数一定要被相乘一次,但是相乘有两种情况。

上面的做法是从左往右依次删除,贡献为 $a_{i-1} \times a_i + a_i \times a_{i+1}$。

而如果从中间删除,贡献为 $a_{i-1} \times a_{i} \times a_{i+1}$。

通常情况下,前者要比后者小(因为前者只有两项相乘,而后者有三项),这也是为什么 $\sum_{i=1}^{n-1} a_i \times a_{i+1}$ 是个较优解。

但是这个「通常情况」指的是什么呢?

$a_{i-1} \times a_i + a_i \times a_{i+1} \le a_{i-1} \times a_{i} \times a_{i+1}$,即 $a_{i-1} + a_{i+1} \le a_{i-1} \times a_{i+1}$,然而后面这个等式必须要在 $a_{i-1},a_{i+1} > 1$ 的情况下才成立。

因此当某个 $a_{i} = 1$ 时,将会有更优解。

于是最终的贪心方法为:将序列从每个 $1$ 的位置分开成若干段,每一段内的代价为 $\sum a_{i} \times a_{i+1} + \min a_i$,最后再加上中间 $1$ 的个数即可。

const int N = 1e6 + 7;
int n, a[N];
ll ans = -1;

int main() {
    rd(n), rda(a, n);
    for (int i = 0, j = 1; i <= n; i = j, j = i + 1) {
        while (j <= n && a[j] != 1) ++j;
        ++ans;
        if (i + 1 != j) ans += *min_element(a + i + 1, a + j);
        for (int k = i + 1; k < j - 1; k++)
            ans += a[k] * a[k+1];
    }
    print(ans);
    return 0;
}

礼物

算几项即可找到规律:对于 $i \equiv 1 \pmod 2$,$a_i \equiv (k+1)^{\frac{i-1}2} \pmod i$。

因此答案就是所有要求整除的质数 $p$ 的积 $-1$。

接下来的问题就是如何筛出 $3 \times 10^8$ 以内的所有质数了,下面代码加了火车头也不保证一定能 AC(反正我交了三页)。

一定要用 bool!不要用 bitset!单点操作 bitset 慢成狗了!

const int N = 3e8 + 1;
bool a[N], v[N];
ll n, ans = 1;
int m, P;
vi p;

int main() {
    rd(n), rd(m), rd(P), a[1] = 1;
    for (int i = 1, x; i <= m; i++) {
        rd(x);
        if (x == 1) return print(-1), 0;
        a[x] = 1;
    }
    for (int i = 2; i <= n; i++) {
        if (!v[i]) {
            p.pb(i);
            if (!a[p.size()]) ans = ans * i % P;
        }
        for (int &j : p) {
            if (i * j > n) break;
            v[i*j] = 1;
            if (!(i % j)) break;
        }
    }
    print(ans - 1);
    return 0;
}

发表评论

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