题解

NOIP半年训练day1

A. Grid

如果下侧和右侧的格子都不相同的话,显然只需要贪心去最小地往下走就可以了。
但是如果相同呢?那就要考虑后面的格子了。
可以发现一个规律,每个格子下侧的点和右侧的点在同一条对角线上,而且到左上角的距离相等。如果进行 $BFS$ 的话,这些点恰好在同一层,因为 $BFS$ 是一层一层做的嘛。
设$ans[i]$ 表示答案的第 $i – 1$ 位,不难看出 $ans[i]$ 只会被到左上角距离为 $i$ 的点更新。而这些点都在同一条对角线上,都在 $BFS$ 的同一层。
这样的话,只需要 $BFS$ 的时候,从几条可能是答案的路径进行搜索取最小的就可以了。

代码

#include <cstring>
#include <climits>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstdio>
const int MAXN = 2e3 + 7;
const int dx[] = {0, 1, 0};
const int dy[] = {0, 0, 1};
int n, m;
char map[MAXN][MAXN];
char ans[MAXN];
bool vis[MAXN][MAXN];
struct Node {
    int x, y, dis;
    char s;
};
void bfs() {
    std::queue<Node> q;
    ans[0] = map[1][1];
    q.push((Node){1, 1, 0, map[1][1]});
    vis[1][1] = true;
    while (!q.empty()) {
        Node u = q.front(); q.pop();
        if (ans[u.dis] != u.s) continue;//保证路径合法
        for (int i = 1; i <= 2; i++) {
            int x = u.x + dx[i];
            int y = u.y + dy[i];
            int dis = u.dis + 1;
            if (x >= 1 && x <= n && y >= 1 && y <= m && !vis[x][y]) {
                vis[x][y] = true;
                q.push((Node){x, y, dis, map[x][y]});
                if (map[x][y] < ans[dis]) {
                    ans[dis] = map[x][y];//更新答案
                }
            }
         }
    }
    ans[n + m - 1] = 0;
}
int main(int argc, char *argv[]) {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%s", map[i] + 1);
    }
    for (int i = 0; i < n + m - 1; ++i)
        ans[i] = 'z' + 1;
    bfs();
    printf("%s", ans);
    return 0;
}

B. Water

看到数据范围这么小,很容易想到状压 $DP$。
但是考场上写状压 $DP$ 写到一半,觉得好像$O(n^22^n)$过不去,所以就没敢写,换成了记忆化搜索。
实际上是能过的,因为整个过程里没有取模没有乘法和除法,底层的常数非常小。

代码

#include <cstring>
#include <climits>
#include <cmath>
#include <cstdio>
#include <iostream>
const int MAXN = 30;
int c[MAXN][MAXN];
int n, k;
int f[MAXN][1 << 22];
int dfs(int step, int s) {
    if (step == n - k) return 0;
    if (f[step][s] <= 10000000) return f[step][s];
    int tmp = INT_MAX;
    for (int i = 0; i < n; i++) {
        if ((s >> i) & 1) {
            for (int j = 0; j < n; j++) {
                if (i == j) continue;
                if ((s >> j) & 1) tmp = std::min(tmp, c[i + 1][j + 1] + dfs(step + 1, s ^ (1 << i)));
            }
        }
    }
    return f[step][s] = tmp;
}
int main(int argc, char *argv[]) {
    scanf("%d %d", &n, &k);
    memset(f, 0x7f, sizeof(f));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            scanf("%d", &c[i][j]);
        }
    }
    int ans = INT_MAX;
    int s = (1 << n ) - 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == j) continue;
            ans = std::min(ans, c[i][j] + dfs(1, s ^ (1 << (i - 1))));
        }
    }
    printf("%d\n", ans);
    return 0;
}

C.Pal

可以看出来如果 $a[1..i]=a[j..n]$ ,那么在最优解里 $a[i]$ 和 $a[i+1]$ 是不会合并到一起的, $a[j]$ 和 $a[j-1]$ 也不会。
所以定义两个指针 $l = 1, r = n$,然后一直扫,

  • 当 $a[l] = a[r]$ 的时候就跳过
  • 当 $a[l] < a[r]$ 的时候要把 $a[l]$ 和 $a[l+1]$ 合并。
  • 当 $a[l] > a[r]$ 的时候要把 $a[r]$ 和 $a[r-1]$ 合并。

第一条规则很显然,那么后两条是为什么呢?
因为要回文,所以两边要对称相等,就是说让对应位置的数尽可能地接近,让小的数尽可能变大来使得和另一边尽可能接近,况且让大的一边变得更大显然不优且没有意义。

代码

#include <cstring>
#include <climits>
#include <cstdio>
#include <cmath>
#include <iostream>
const int MAXN = 1e6 + 7;
int a[MAXN];
int main(int argc, char *argv[]) {
    int n, ans = 0;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", a + i);
    }
    int l = 1, r = n;
    while (l < r) {
        if (a[l] == a[r]) l++, r--;
        else {
            if (a[l] < a[r]) a[l + 1] += a[l], ans++, l++;
            else a[r - 1] += a[r], ans++, r--;
        }
    }
    printf("%d\n", ans);
    return 0;
}

D.Lis

首先直接做显然不行。
我们按照题意转化一下,可以发现对于一个 $lis$,一定在 $a$ 中存在一个最靠左的点,记为 $i$,使得 $lis$ 中的所有元素都在这个数右边。那么 $lis$ 就一定是以该数为首元素的 $lis$ 和 $lds$ 拼起来的(因为可以把 $lds$ 翻转后放到 $i$ 左边)。这么做有什么好处呢?可以非常显然的发现以 $i$ 为首元素的 $lis$ 和 $lds$ 是不重合的,因为一旦重合那么就与 $lis$ 和 $lds$ 的定义冲突了。
那么我们转化一下。
枚举一个 $i$ 使其一定在 $a[i] \dots a[n]$ 组成的序列中的 $lis$ 中出现,最长的 $lis$ 一定被包含在这些情况中。
既然这个数一定在 $lis$ 中出现,那么第 $i$ 个数后面的比它大的,要放到它后面,小的放到前面,否则就没有贡献。
然后求后缀的 $lis$ 和 $lds$,拼起来就是原来的 $lis$ 的长度。
方案数怎么求呢?求 $lis$ 和 $lds$ 的时候如果更优就覆盖掉,如果相同就加法原理加起来。
有了长度和 $lis$ 的方案数,那么剩下的数怎么放其实是不关心的,最终的方案数只要再乘上一个 $2^{n-len}$ 就可以了。

代码

#include <cstdio>
#include <climits>
#include <cmath>
#include <cstring>
#include <queue>
#include <algorithm>
#include <iostream>
#include <map>
typedef long long ll;
const int MAXN = 5e5 + 7;
const ll HA = 1e9 + 7;
int n, a[MAXN], set[MAXN], end;
ll frac[MAXN];
struct Node {
    int len;
    ll cnt;
} lis[MAXN], lds[MAXN], t1[MAXN], t2[MAXN];
inline int lowbit(int x) {
    return x & (-x);
}
inline Node upd(Node x, Node y) {
    if (x.len < y.len) x = y;
    else if (x.len == y.len) {
        x.cnt = (x.cnt + y.cnt) % HA;
    }
    return x;
}
inline void prepare() {
    frac[0] = 1;
    for (int i = 1; i < MAXN; i++) {
        frac[i] = (frac[i - 1] * 2) % HA;
    }
}
void updateLis(int x, Node delta) {
    for (int i = x; i <= end; i += lowbit(i)) {
        t1[i] = upd(t1[i], delta);
    }
}
void updateLds(int x, Node delta) {
    for (int i = x; i; i -= lowbit(i)) {
        t2[i] = upd(t2[i], delta);
    }
}
Node queryLis(int x) {
    Node ret = (Node){0, 0};
    for (int i = x; i; i -= lowbit(i)) {
        ret = upd(ret, t1[i]);
    }
    return ret;
}
Node queryLds(int x) {
    Node ret = (Node){0, 0ll};
    for (int i = x; i <= end; i += lowbit(i)) {
        ret = upd(ret, t2[i]);
    }
    return ret;
}
int main(int argc, char *argv[]) {
    scanf("%d", &n);
    prepare();
    for (int i = 1; i <= n; i++) {
        scanf("%d", a + i);
        set[i] = a[i];
    }
    std::sort(set + 1, set + n + 1);
    end = std::unique(set + 1, set + n + 1) - set - 1;
    for (int i = 1; i <= n; i++) {
        a[i] = std::lower_bound(set + 1, set + end + 1, a[i]) - set;
    }
    for (int i = n; i >= 1; i--) {
        Node p = queryLis(a[i] - 1);
        if (p.len == 0) {
            lis[i] = (Node){0, 1ll};
            updateLis(a[i], (Node){1, 1ll});
        } else {
            lis[i] = p;
            p.len++;
            updateLis(a[i], p);
        }
    }
    for (int i = n; i >= 1; i--) {
        Node p = queryLds(a[i] + 1);
        if (p.len == 0) {
            lds[i] = (Node){0, 1ll};
            updateLds(a[i], (Node){1, 1ll});
        } else {
            lds[i] = p;
            p.len++;
            updateLds(a[i], p);
        }
    }
    Node ans = (Node){0, 0ll};
    for (int i = 1; i <= n; i++) {
        ans = upd(ans, (Node){lis[i].len + lds[i].len + 1, (lis[i].cnt * lds[i].cnt % HA)});
    }
    ans.cnt = (ans.cnt * frac[n - ans.len]) % HA;
    printf("%d %lld\n", ans.len, ans.cnt);
    return 0;
}

一条评论

发表评论

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