提高组杂题选讲

暴力出奇迹 · 2021-10-16 21:02:02 · 题解

首先讲一下那个大家喜闻乐见的 P7075 [CSP-S2020] 儒略日。

这道题目一看就是个大模拟，从现场情况来看，开场 1h 全场键盘劈啪作响，肯定是都在写这道细节很多的题目。那么这道题目怎样做才能更简单呢？

部分分： 直接离线（把所有 r_i 从小到大排序，注意要记录每个 r_i 对应第几次询问）之后一天一天往后推即可。时间复杂度 O(Q \log Q+\max{r_i}) 或者 O(Q+\max{r_i})，期望分数 80pts，同机房同学试着写了一下得了 90pts！从最终结果来看，这样的暴力可能反而是最实惠的，基本上可以在 15min 内写完，并且得到一个几乎就是满分的成绩。

然后讲一下正解。首先考虑写一个暴力代码辅助：

#include <cstdio>
using namespace std;
const int Days[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
struct Date {
    int year, month, day;
    void add() { //直接暴力向后推
        int lim = Days[month];
        if(month == 2 && year % 4 == 0) lim = 29;
        if(day < lim) ++day;
        else {
            day = 1;
            if(month < 12) ++month;
            else {month = 1; ++year;}
        }
    }
    bool operator == (const Date &rhs) const {
        return year == rhs.year && month == rhs.month && day == rhs.day;
    }
}date = (Date){____, ____, ____};
int main() {
    int cnt = 0;
    while(!(date == (Date){____, ____, ____})) {date.add(); ++cnt;}
    printf("%d", cnt);
    return 0;
}

横线部分表示可以求出任意两个日期相差的天数，注意这个暴力代码是有缺陷的，它既没有考虑 1582.10.5 到 1582.10.14 之间的空缺，也没有考虑到这之后闰年判断的变化（不再是简简单单的 4 的倍数了），但是这些毕竟可以手工调整。

在正式开始之前，我们先定义日期的结构体，并且写好输出格式：

struct Date {
    int year, month, day;
    inline void print() {
        if(year <= 0) printf("%d %d %d BC\n", day, month, -year + 1); //详见下文
        else printf("%d %d %d\n", day, month, year);
    }
}date;

第一步：对公元前的年份进行转换。

把公元前的年份减去一再变成负数，比如说公元前 4713 年表示为 -4712，这样既处理了公元零年不存在的情况（公元前和公元后衔接上了），也能很方便地判断公元前某一年是否为闰年（直接对 4 取模即可）。

第二步：处理 1582.10.5 到 1582.10.14 的空缺。

处理方法很简单，用上述暴力代码算出 -4712.1.1 到 1582.10.4 之间的天数（这个天数为 2299160），如果 r_i 不超过这个天数则不处理，否则直接把 r_i 加上 10，相当于强行把这十天补进去。

注意如果不进行这一步转化，循环节在 1582 年将会断裂，1582 年支离破碎非常难以处理，将会导致对称性破缺，我现场就陷入了这一窘境。

注意：以下对这道题目的讨论，默认 1582.10.5 到 1582.10.14 这十天存在。 这样我们的暴力代码就不用删去这十天了。

第三步：分段讨论，用暴力代码求出 -4712.1.1 到 1600.1.1 的天数（2305458 天）。

我们发现 -4712 年恰好是闰年，所以这个循环节性质很好。如果 r_i \le 2305458，我们就先 4 年一循环，用上述暴力代码求出 -4712.1.1 到 -4708.1.1 的天数（1461 天）。

大循环后我们要细化小循环，发现每个四年循环中的第一年是闰年，多出来的这一天十分突兀。

考虑用同样的方法把 2.29 去除：算出 -4712.1.1 到 -4712.2.29 的天数（59 天），如果 r_i=59 显然就是 2.29，如果 r_i>59 可以将其减去一，相当于删去 2.29。

接下来逐步处理，先确定年份（365 天一循环），再细化到月份和日期，详见代码：

if(n <= 2305458) {
    date = (Date){-4712, 1, 1};
    date.year += (n / 1461) * 4; n %= 1461;
    if(n == 59) {date.month = 2; date.day = 29;}
    else {
        if(n > 59) --n;
        date.year += n / 365; n %= 365;
        for(register int i = 1; i <= 12; ++i)
            if(n < Days[i]) {date.month = i; date.day = n + 1; break;}
            else n -= Days[i];
    }
    date.print();
}

如果 r_i>2305458 呢？首先减去 2305458，并且将日期置为 1600.1.1。观察可知 1600 年以后和之前的差异，仅仅是闰年判断的规则不同，如果以 400 年作为一个大循环，那么第一个循环中 1700、1800、1900 年都是平年。

用暴力代码跑出每个 400 年循环的天数 （由此可见暴力代码有多么重要！），暴力代码算出的是 146100 天，但是我们要注意到暴力代码没有考虑到 1700、1800、1900 年是平年，所以我们手动减去多出来的 3 天，得出 400 年共有 146097 天。

接下来我们要细化到 400 年内部的讨论（比如说是 1600 年到 2000 年），运用化归思想，我们很想把 1700、1800、1900 三年都变成闰年，这样就又变成了四年一循环，可以直接套用前面那一部分的代码。

用暴力代码跑出 1600.1.1 到 1700.2.28 的天数（36583 天），所以 n=36584 时答案为 1700.3.1（其它四百年循环也类似），n>36584 的时候把 n 加上 1，相当于补上了 1700.2.29。

同理，可以把 1800.2.29、1900.2.29 用相同方法补上，最后套用前面四年循环的代码就做完了。代码如下：

else {
    date = (Date){1600, 1, 1}; n -= 2305458;
    date.year += (n / 146097) * 400; n %= 146097;
    if(n == 36584) {date.year += 100; date.month = 3; date.day = 1;}
    else {
        if(n > 36584) ++n;
        if(n == 73109) {date.year += 200; date.month = 3; date.day = 1;}
        else {
            if(n > 73109) ++n;
            if(n == 109634) {date.year += 300; date.month = 3; date.day = 1;}
            else {
                if(n > 109634) ++n;
                date.year += (n / 1461) * 4; n %= 1461;
                if(n == 59) {date.month = 2; date.day = 29;}
                else {
                    if(n > 59) --n;
                    date.year += n / 365; n %= 365;
                    for(register int i = 1; i <= 12; ++i)
                        if(n < Days[i]) {date.month = i; date.day = n + 1; break;}
                        else n -= Days[i];
                }
            }
        }
    }
    date.print();
}

总结： 大模拟题目不要着急下手，先考虑能不能用简单的方法拿到较多的部分分，考虑正解的时候先通过一些转化方法减少细节，必要的时候写暴力代码辅助。

讲下一道题目：P1979 [NOIP2013 提高组] 华容道。

连想都不用想，把空格位置记录下来，再把指定棋子的位置记录下来，每次询问跑一遍广搜，时间复杂度 O(n^2m^2q)，期望 60pts。

至于正解，我们仍然考虑刚才的做法，记指定棋子当前位置为 (x_1,y_1)，空格当前位置为 (x_2,y_2)，把当前状态表示为 (x_1,y_1,x_2,y_2)，并且将其抽象为图上的一个点，能够通过移动一次棋子相互转化的两个状态之间连一条边，会发现这就是要我们跑多次最短路。

读者不妨想象一下，把 (x_1,y_1) 相同的所有点想象在同一平面上，那么两个平面之间连接的边数实际上很少，只有 (x_1,y_1) 和 (x_2,y_2) 相邻的状态才有可能转移到其它平面上去（只有空格和指定棋子相邻，才可能通过一次操作改变指定棋子的位置），也就是说一个平面和外界的连边最多只有 4 条。

考虑到这一点，我们决定将一个平面简化为只有和外界相连的结点（不妨称之为 边界点），每一层内部我们用广搜求出边界点两两之间的距离，最后再跑最短路。

不难发现，除非 (SX,SY)=(TX,TY)（这种情况答案为 0，并且一定要记得特判），其余情况在结束的时候，空格一定是和目标格子相邻的，因为最后一步一定是把指定棋子移到目标格子上，不可能再花一步把空格挪走，使之与目标格子不相邻。

每一个询问，先枚举从初始点转移到哪个边界点上，然后把当前平面的边界点和 (TX,TY) 平面的边界点都求一次最短路，选出最短的即可。

代码又长又难写，还是放一下我巨丑的代码吧（这代码还是初三升高一暑假写的，现在我自己都不想看）：

#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
const int N = 35;
const int NN = 4010;
const int M = 20010;
const int INF = 1e9 + 10;
const int dir[4][2] = {
    {-1, 0}, {0, -1}, {0, 1}, {1, 0}
};
struct Node {
    int x, y;
};
queue<Node> que;
struct Node2 {
    int idx, dis;
    bool operator > (const Node2 &rhs) const {
        return dis > rhs.dis;
    }
};
priority_queue<Node2, vector<Node2>, greater<Node2> >pq;
struct Edge {
    int to, cost, next;
}edges[M];
bool a[N][N];
int dist[N][N][4][N][N], dis[NN];
int head[NN], idx[N][N], n, m, k, q, nedge;
inline int min(int x, int y) {return x < y ? x : y;}
inline void addedge(int u, int v, int w) {
    edges[++nedge].to = v;
    edges[nedge].cost = w;
    edges[nedge].next = head[u];
    head[u] = nedge;
}
inline bool canmove(int x, int y) {return x > 0 && y > 0 && x <= n && y <= m && a[x][y];}
inline void bfs(int x, int y, int d) {
    for(register int nx = 1; nx <= n; ++nx)
        for(register int ny = 1; ny <= m; ++ny)
            dist[x][y][d][nx][ny] = INF;
    int nx = x + dir[d][0], ny = y + dir[d][1];
    dist[x][y][d][nx][ny] = 0;
    que.push((Node){nx, ny});
    while(!que.empty()) {
        Node now = que.front(); que.pop();
        for(register int i = 0; i < 4; ++i) {
            nx = now.x + dir[i][0]; ny = now.y + dir[i][1];
            if(canmove(nx, ny) && (nx != x || ny != y))
                if(dist[x][y][d][now.x][now.y] + 1 < dist[x][y][d][nx][ny]) {
                    dist[x][y][d][nx][ny] = dist[x][y][d][now.x][now.y] + 1;
                    que.push((Node){nx, ny});
                }
        }
    }
}
inline void dijkstra(int s) {
    for(register int i = 0; i < 4 * k; ++i) dis[i] = INF;
    dis[s] = 0; pq.push((Node2){s, 0});
    while(!pq.empty()) {
        Node2 now = pq.top(); pq.pop();
        int u = now.idx;
        if(dis[u] < now.dis) continue;
        for(register int i = head[u]; i; i = edges[i].next) {
            int v = edges[i].to, w = edges[i].cost;
            if(dis[u] + w < dis[v]) {
                dis[v] = dis[u] + w;
                pq.push((Node2){v, dis[v]});
            }
        }
    }
}
int main() {
    scanf("%d %d %d", &n, &m, &q);
    for(register int i = 1; i <= n; ++i)
        for(register int j = 1; j <= m; ++j) {
            int x; scanf("%d", &x);
            if(x == 1) {idx[i][j] = ++k; a[i][j] = true;}
        }
    for(register int x = 1; x <= n; ++x)
        for(register int y = 1; y <= m; ++y)
            if(a[x][y]) {
                for(register int d = 0; d < 4; ++d) {
                    int nx = x + dir[d][0], ny = y + dir[d][1];
                    if(canmove(nx, ny)) bfs(x, y, d);
                }
            }
    for(register int x = 1; x <= n; ++x)
        for(register int y = 1; y <= m; ++y) {
            for(register int d = 0; d < 4; ++d) {
                int nx = x + dir[d][0], ny = y + dir[d][1];
                if(canmove(nx, ny))
                    addedge((idx[x][y] - 1) * 4 + d, (idx[nx][ny] - 1) * 4 + 3 - d, 1);
            }
            for(register int d1 = 0; d1 < 4; ++d1)
                for(register int d2 = 0; d2 < 4; ++d2)
                    if(d1 != d2) {
                        int nx1 = x + dir[d1][0], ny1 = y + dir[d1][1];
                        int nx2 = x + dir[d2][0], ny2 = y + dir[d2][1];
                        if(canmove(nx1, ny1) && canmove(nx2, ny2))
                            addedge((idx[x][y] - 1) * 4 + d1, (idx[x][y] - 1) * 4 + d2, dist[x][y][d1][nx2][ny2]);
                    }
        }
    while(q--) {
        int ex, ey, sx, sy, tx, ty;
        scanf("%d %d %d %d %d %d", &ex, &ey, &sx, &sy, &tx, &ty);
        if(sx == tx && sy == ty) {printf("0\n");}
        else {
            int ans = INF;
            for(register int d = 0; d < 4; ++d) {
                int nx = sx + dir[d][0], ny = sy + dir[d][1];
                if(canmove(nx, ny) && dist[sx][sy][d][ex][ey] < INF) {
                    int u = (idx[sx][sy] - 1) * 4 + d; dijkstra(u);
                    for(register int i = 0; i < 4; ++i) {
                        int v = (idx[tx][ty] - 1) * 4 + i;
                        ans = min(ans, dist[sx][sy][d][ex][ey] + dis[v]);
                    }
                }
            }
            if(ans == INF) printf("-1\n");
            else printf("%d\n", ans);
        }
    }
    return 0;
}

P1311 [NOIP2011 提高组] 选择客栈：

（加强版链接：P6032 选择客栈 加强版）

限于篇幅，直接开始讲线性做法：

考虑枚举右边的客栈的编号 i，那么对于左边的客栈 j 的要求就是：[j,i] 之间要有至少一个咖啡馆的最低消费 \le p。说句题外话， j=i 时 [j,i] 不是区间的规范写法！（王先阳：长见识了）

那我们用 t 来记录上一个最低消费 \le p 的咖啡馆，则所有满足 j \in [1,t] 的咖啡馆都是可供选择的，同时用 sum_i 数组动态地记录 [1,t] 的咖啡馆中色调为 i 的数目，color 数组记录每个咖啡馆的色调。

我们从左到右扫描 i，每当 i 增大时，看一下当前咖啡馆最低消费是否 \le p，如果不是则 t 和 sum 数组均不变，计数器 ans 增加 sum_{color_i}。

如果当前咖啡馆最低消费 \le p 呢？首先要把 t 更新到当前编号 i，然后要把原来的 t（记为 t_0）到当前编号 i 的所有色调加到 sum 数组中，那么我们就可以一边增加 t，一边更新 sum 数组，最后统计答案的时候 ans 要增加 sum_{color_i}-1，因为 sum 数组已经把当前咖啡馆的色调统计进去了，但实际上两人不能住同一间咖啡馆，所以减去 1。

时间复杂度为 O(n)，达到了理论下界（废话，读入所有数据的复杂度都是 O(n) 的）。

代码如下（数组大小为加强版数据范围）：

#include <cstdio>
using namespace std;
#define LL long long
const int N = 2000010;
const int K = 10010;
int sum[K], color[N], n, k, p;
int main() {
    scanf("%d %d %d", &n, &k, &p);
    int t = 0; LL ans = 0;
    for(register int i = 1; i <= n; ++i) {
        int pay; scanf("%d %d", &color[i], &pay);
        if(pay <= p) {
            while(t < i) ++sum[color[++t]];
            ans += sum[color[i]] - 1;
        }
        else ans += sum[color[i]];
    }
    printf("%lld", ans);
    return 0;
}

P2661 [NOIP2015 提高组] 信息传递

题意：n 个点，每个点出度为 1，求最小环。

依次连接每一条边，如果连接 (u,v) 时发现 u 和 v 已经联通，就在并查集上算出 v 到 u 的路径（不难发现 u 一定是并查集上的代表结点），再加上 1 表示 (u,v) 这条边，就是环的大小。如果 (u,v) 并不连通直接令 fa_u=v 即可。

至于维护每个点到并查集代表元的距离，用 len_u 表示 u 到 fa_u 的距离，路径压缩时相应更新。时间复杂度接近 O(n)，达到理论下界。

#include <cstdio>
using namespace std;
const int N = 200010;
int fa[N], len[N], n, ans;
inline int min(int x, int y) {return x < y ? x : y;}
inline int findroot(int x, int &dist) {
    if(fa[x] == x) {dist = 0; return x;}
    fa[x] = findroot(fa[x], dist);
    dist = len[x] = dist + len[x]; //路径压缩的同时要更新 len 数组（因为 fa[x] 已经变了），dist 表示的是原来的 fa[x] 到代表元的距离，那么 len[x] 应该更新为 dist+len[x]
    return fa[x];
}
int main() {
    scanf("%d", &n); ans = n;
    for(register int i = 1; i <= n; ++i) fa[i] = i;
    for(register int u = 1; u <= n; ++u) {
        int v, dist; scanf("%d", &v);
        if(findroot(v, dist) == u) ans = min(ans, dist + 1);
        else {fa[u] = v; len[u] = 1;}
    }
    printf("%d", ans);
    return 0;
}

类似的题目还有 P1196 [NOI2002] 银河英雄传说，和上面问题的不同之处是还要维护队列尾部的编号，代码如下：

#include <cstdio>
#include <cstring>
using namespace std;
const int N = 30010;
int fa[N], len[N], tail[N], T, n = 30000;
inline int abss(int x) {return x > 0 ? x : -x;}
inline int findroot(int x, int &dist) {
    if(fa[x] == x) {dist = 0; return x;}
    fa[x] = findroot(fa[x], dist);
    len[x] = dist = len[x] + dist;
    return fa[x];
}
int main() {
    for(register int i = 1; i <= n; ++i) fa[i] = tail[i] = i;
    scanf("%d", &T);
    while(T--) {
        char opt[5]; int u, v;
        scanf("%s %d %d", opt, &u, &v);
        if(opt[0] == 'M') {
            int dist1, dist2;
            u = findroot(u, dist1); v = findroot(v, dist2);
            fa[u] = tail[v]; len[u] = 1;
            tail[v] = tail[u]; //只有代表元位置的 tail 才是可信的
        }
        else {
            int dist1, dist2;
            u = findroot(u, dist1); v = findroot(v, dist2);
            if(u == v) printf("%d\n", abss(dist1 - dist2) - 1);
            else printf("-1\n");
        }
    }
    return 0;
}