2021牛客寒假算法基础集训营2

比赛地址：https://ac.nowcoder.com/acm/contest/9982

出题人题解：https://ac.nowcoder.com/discuss/593874

智乃姐姐的题解超级详细啊，认真看完之后嘴巴立马就会了。

A-牛牛与牛妹的RMQ

知识点：单调栈、树状数组

• 给定个下标，最多有种，分别为个下标点和个区间。
• 使用单调栈求出每个极值的作用范围。
• 使用树状数组求出每个极值左右作用范围内可选的下标个数，即可求出该极值对答案的贡献。

注：下面代码可，取就会超时，原因在于求区间极值时用的循环，没想到过了(QAQ)。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 1e6 + 117;

int n;
int a[MAXN];
stack<int> st;
int lid[MAXN], rid[MAXN];

int m, k;
int p[MAXN];
struct node {
    int x;
    LL fenzi;
    bool operator <(const node &a)const {
        return x < a.x;
    }
};
vector<node> ans;

int tree[MAXN];
int low_bit(int x) {
    return x & -x;
}
void update(int p, int x) {
    while(p <= n) {
        tree[p] += x;
        p += low_bit(p);
    }
}
int query(int p) {
    int ret = 0;
    while(p) {
        ret += tree[p];
        p -= low_bit(p);
    }
    return ret;
}
int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        while(!st.empty() && a[st.top()] < a[i]) {
            rid[st.top()] = i - 1;
            st.pop();
        }
        if(st.empty()) lid[i] = 1;
        else lid[i] = st.top() + 1;
        st.push(i);
    }
    while(!st.empty()) {
        rid[st.top()] = n;
        st.pop();
    }

    scanf("%d", &m);
    while(m--) {
        scanf("%d", &k);
        for(int i = 0; i < k; i++) {
            scanf("%d", &p[i]);
            update(p[i], 1);
        }
        sort(p, p + k);

        ans.clear();
        for(int i = 0; i < k; i++) {
            LL lcnt = query(p[i]) - query(lid[p[i]] - 1);
            LL rcnt = query(rid[p[i]]) - query(p[i] - 1);
            ans.push_back({a[p[i]], lcnt * rcnt * 2 - 1});

            //此处可hack
            if(i == k - 1) break;
            int id = p[i] + 1;
            for(int j = p[i] + 1; j < p[i + 1]; j++)
                if(a[id] < a[j]) id = j;
            if(id == p[i + 1]) continue;
            lcnt = query(id) - query(lid[id] - 1);
            rcnt = query(rid[id]) - query(id - 1);
            if(lcnt * rcnt != 0) ans.push_back({a[id], lcnt * rcnt * 2});
        }

        sort(ans.begin(), ans.end());
        int cnt = ans.size();
        for(int i = 0; i < cnt; i++) {
            LL gc = __gcd(ans[i].fenzi, (LL)k * k);
            printf("%d %lld/%lld\n", ans[i].x, ans[i].fenzi / gc, (LL)k * k / gc);
        }

        for(int i = 0; i < k; i++) update(p[i], -1);
    }
    return 0;
}

B-牛牛抓牛妹

知识点：最短路

• 建分层图，最多个点。
• 对于每一层，预处理出每个点的下一步，对于没有下一步的点就是终点（可能有多个）。
• 从起点出发广搜一遍，找到一条到达终点的路径后输出指令即可。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 1e6 + 117;

int n, m, k;
int p[77];
int ma[177][177];
int u, v;
//判断某个点在flag层是不是被锁住
bool isLock(int id, int flag) {
    id -= flag * n;
    for(int i = 0; i < k; i++)
        if(id == p[i] && (flag & (1 << i)) != 0) return true;
    return false;
}
//对每一层图进行搜索，不同层对应不同锁的状态
queue<int> que;
int to[MAXN];
bool vis[MAXN];
int dist[MAXN];
void bfs(int flag) {
    que.push(n + flag * n);
    dist[n + flag * n] = 0;
    vis[n + flag * n] = true;
    while(!que.empty()) {
        int now = que.front();
        que.pop();
        if(isLock(now, flag)) continue;
        for(int i = 1; i <= n; i++) {
            if(ma[now - flag * n][i] == 0) continue;
            if(vis[i + flag * n] == true) {//被访问过可能有更小的序号
                if(dist[i + flag * n] == dist[now] + 1)
                    to[i + flag * n] = min(to[i + flag * n], now);
            } else {//第一次访问
                to[i + flag * n] = now;
                que.push(i + flag * n);
                dist[i + flag * n] = dist[now] + 1;
                vis[i + flag * n] = true;
            }
        }
    }
}
//从起点搜索终点
int pre[MAXN];
int solve() {
    memset(pre, -1, sizeof(pre));
    memset(vis, false, sizeof(vis));
    que.push(1);
    vis[1] = true;
    while(!que.empty()) {
        int now = que.front();
        que.pop();
        if(now % n == 0) continue;
        if(to[now] == -1) return now;
        //在当前锁状态下走一步
        if(!vis[to[now]]) {
            que.push(to[now]);
            pre[to[now]] = now;
            vis[to[now]] = true;
        }
        //更改锁的状态
        for(int i = now - (now - 1) / n * n; i <= n * (1 << k); i += n) {
            if(vis[i]) continue;
            que.push(i);
            pre[i] = now;
            vis[i] = true;
        }
    }
    return -1;
}
//更改锁的状态输出对应指令
void checkLock(int now, int to) {
    int flagnow = (now - 1) / n;
    int flagto = (to - 1) / n;
    for(int i = 0; i < k; i++) {
        int a = flagnow & 1;
        int b = flagto & 1;
        if(a == 1 && b == 0) printf("unlock %d\n", p[i]);
        if(a == 0 && b == 1) printf("lock %d\n", p[i]);
        flagnow >>= 1;
        flagto >>= 1;
    }
}
int main() {
    scanf("%d%d%d", &n, &m, &k);
    for(int i = 0; i < k; i++) scanf("%d", &p[i]);
    for(int i = 0; i < m; i++) {
        scanf("%d%d", &u, &v);
        ma[u][v] = ma[v][u] = 1;
    }
    //对每一层建图
    memset(to, -1, sizeof(to));
    memset(vis, false, sizeof(vis));
    memset(dist, INF, sizeof(dist));
    for(int i = 0; i < (1 << k); i++) bfs(i);
    //找到终点和路径
    int ending = solve();
    stack<int> path;
    while(ending != -1) {
        path.push(ending);
        ending = pre[ending];
    }
    //根据路径输出指令
    while(path.size() > 1) {
        int now = path.top();
        path.pop();
        int to = path.top();
        if(now % n == to % n) checkLock(now, to);
        else puts("continue");
    }
    puts("checkmate!");
    return 0;
}

C-牛牛与字符串border

知识点：找规律

• 当时，循环节长度为，这样一个或者一个都恰好被若干个循环填满，从前往后取若干个和从后往前取若干个得到的串都是若干个完整的循环，一定相同。
• 当时，循环节长度为。
• 小心的情况。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 1e6 + 117;

int T;
int n, l, cycle;
int cnt[MAXN][27];
char s[MAXN];
int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d%d%s", &n, &l, s);
        if(n >= l * 2 || n == l) cycle = __gcd(n, l);
        else cycle = n - l;
        for(int i = 0; i < cycle; i++) {
            for(int j = 0; j < 27; j++) {
                cnt[i][j] = 0;
            }
        }

        for(int i = 0; i < n; i++) cnt[i % cycle][s[i] - 'a']++;
        for(int i = 0; i < cycle; i++) {
            int num = 0;
            for(int j = 0; j < 27; j++) {
                if(cnt[i][j] > cnt[i][num]) num = j;
            }
            for(int j = i; j < n; j += cycle) s[j] = 'a' + num;
        }

        puts(s);
    }
    return 0;
}

D-牛牛与整除分块

知识点：数论

当时输出，否则输出以为对称轴对称的值。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 1e6 + 117;

int T;
int n, k;
int solve() {
    int m = sqrt(n + 0.5);
    if(k <= m) return k;
    int ret = m * 2 - n / k;
    if(m != n / m) ret++;
    return ret;
}
int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d%d", &n, &k);
        printf("%d\n", solve());
    }
    return 0;
}

E-牛牛与跷跷板

知识点：

• 先按分组再按排序。
• 对于每一组双指针扫一遍建图。
• 最后跑。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 1e6 + 117;

int n;
struct node {
    int id;
    int l, r;
} x;
vector<node> v[MAXN];
bool cmp(node a, node b) {
    return a.l < b.l;
}
///建图
int head[MAXN], edge[MAXN], ne[MAXN], tot;
void addedge(int u, int v) {
    edge[tot] = v;
    ne[tot] = head[u];
    head[u] = tot++;
}
void build() {
    tot = 0;
    memset(head, -1, sizeof(head));
    for(int i = 0; i <= 100000; i++) {
        for(int j = 0, k = 0; j < v[i].size(); j++) {
            if(j - 1 >= 0 && v[i][j - 1].r == v[i][j].l) {
                addedge(v[i][j - 1].id, v[i][j].id);
                addedge(v[i][j].id, v[i][j - 1].id);
            }
            if(i == 0) continue;
            while(k < v[i - 1].size() && v[i - 1][k].r <= v[i][j].l) k++;
            while(k < v[i - 1].size() && v[i - 1][k].l < v[i][j].r) {
                addedge(v[i][j].id, v[i - 1][k].id);
                addedge(v[i - 1][k].id, v[i][j].id);
                k++;
            }
            if(k) k--;
        }
    }
}
///bfs
bool f[MAXN];
queue<pair<int, int>> q;
int bfs() {
    q.push({1, 0});
    f[1] = true;
    while(!q.empty()) {
        pair<int, int> p = q.front();
        q.pop();
        if(p.first == n) return p.second;
        for(int i = head[p.first]; i != -1; i = ne[i]) {
            if(!f[edge[i]]) {
                f[edge[i]] = true;
                q.push({edge[i], p.second + 1});
            }
        }
    }
    return -1;
}
int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        int y, l, r;
        scanf("%d%d%d", &y, &l, &r);
        v[y].push_back({i, l, r});
    }
    for(int i = 0; i <= 100000; i++) sort(v[i].begin(), v[i].end(), cmp);
    build();
    printf("%d\n", bfs());
    return 0;
}

F-牛牛与交换排序

知识点：双端队列

• 遍历数组找到值。
• 数组依次进入双端队列，从第个开始检查队首元素是不是，如果不是就翻转队列。队首是则队首出队，否则无解。
• 入队结束后需要检查队列中剩余元素是否有序，无序则无解。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 1e6 + 117;

int n, k;
int a[MAXN];
struct deQue {
    int buffer[MAXN * 2];
    int head = MAXN, tail = MAXN;
    bool rev = false;
    bool empty() {
        return tail <= head;
    }
    int size() {
        return tail - head;
    }
    int front() {
        return rev ? buffer[tail - 1] : buffer[head];
    }
    int back() {
        return rev ? buffer[head] : buffer[tail - 1];
    }
    void push_front(int x) {
        if(rev) buffer[tail++] = x;
        else buffer[--head] = x;
    }
    void push_back(int x) {
        if(rev) buffer[--head] = x;
        else buffer[tail++] = x;
    }
    void pop_front() {
        if(rev) tail--;
        else head++;
    }
    void pop_back() {
        if(rev) head++;
        else tail--;
    }
    void reverse() {
        rev = !rev;
    }
} q;
void solve() {
    for(int i = 1; i < k; i++) q.push_back(a[i]);
    for(int i = k; i <= n; i++) {
        q.push_back(a[i]);
        if(q.front() != i - k + 1) q.reverse();
        if(q.front() != i - k + 1) {
            puts("no");
            return;
        }
        q.pop_front();
    }
    for(int i = n - k + 2; i <= n; i++) {
        if(q.front() != i) {
            puts("no");
            return;
        }
        q.pop_front();
    }
    printf("yes\n%d", k);
}
int main() {
    k = 0;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for(int i = 1; i <= n; i++) {
        if(a[i] != i) {
            for(int j = i + 1; j <= n; j++)
                if(a[j] == i) k = j - i + 1;
            break;
        }
    }
    if(k) solve();
    else puts("yes\n1");
    return 0;
}

G-牛牛与比赛颁奖

知识点：差分前缀和

• 先离散化，然后利用差分的性质修改区间值。
• 桶装计数得到通过道题的队伍数量。
• 处理输出。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 1e6 + 117;

int n, m;
int l[MAXN], r[MAXN];
int a[MAXN], tot;///离散化
int score[MAXN];///区间[a[i],a[i+1])队伍过了score[i]题
int jishu[MAXN];///过了i道题的有jishu[i]个队
int get_hash(int x) {
    return lower_bound(a, a + tot, x) - a;
}
int solve(int x) {
    for(int i = m; i > 0; i--)
        if(jishu[i] >= x) return jishu[i];
    return jishu[1];
}
int main() {
    scanf("%d%d", &n, &m);
    for(int i = 0; i < m; i++) {
        scanf("%d%d", &l[i], &r[i]);
        a[i * 2] = l[i];
        a[i * 2 + 1] = ++r[i];
    }
    ///离散化
    sort(a, a + m * 2);
    tot = unique(a, a + m * 2) - a;
    ///差分
    for(int i = 0; i < m; i++) {
        score[get_hash(l[i])]++;
        score[get_hash(r[i])]--;
    }
    ///前缀和并计数
    for(int i = 0; i < tot - 1; i++) {
        if(i) score[i] += score[i - 1];
        jishu[score[i]] += a[i + 1] - a[i];
    }

    for(int i = m - 1; i >= 0; i--) jishu[i] += jishu[i + 1];
    int jin = solve((n + 9) / 10);
    int yin = solve((n + 3) / 4);
    int tong = solve((n + 1) / 2);
    printf("%d %d %d\n", jin, yin - jin, tong - yin);
    return 0;
}

H-牛牛与棋盘

知识点：模拟

直接输出即可。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 1e6 + 117;

int n;
int main() {
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            if((i + j) & 1) putchar('1');
            else putchar('0');
        }
        putchar(10);
    }
    return 0;
}

I-牛牛的“质因数”

知识点：线性筛

第一种：，参考神崎兰子的博客。

对于任意一个数，考虑不大于中最小质因子的质数有哪些可以放在的前面。

代码中表示当前数字是，的最小质因子是第个，，有位。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 4e6 + 117;
const int MAXM = 1e6 + 117;

int n;
LL ans;
int wei[MAXN];
LL po[MAXN];
int prime[MAXN];
void init() {
    wei[0] = 0, wei[1] = 1;
    po[0] = 1, po[1] = 10;
    for(int i = 2; i <= n; i++) {
        wei[i] = wei[i / 10] + 1;
        po[i] = po[i - 1] * 10 % mod;
        if(!prime[i]) prime[++prime[0]] = i;
        for(int j = 1; j <= prime[0] && prime[j] <= n / i; j++) {
            prime[prime[j]*i] = 1;
            if(i % prime[j] == 0) break;
        }
    }
}
void dfs(int id, LL num, LL sum, int cnt) {
    for(int i = 1; i <= id; i++) {
        LL newnum = num * prime[i];
        if(newnum > n) break;
        LL newsum = (prime[i] * po[cnt] + sum) % mod;
        ans = (ans + newsum) % mod;
        dfs(i, newnum, newsum, cnt + wei[prime[i]]);
    }
}
int main() {
    scanf("%d", &n);
    init();
    dfs(prime[0], 1, 0, 0);
    printf("%lld\n", ans);
    return 0;
}

第二种：线性筛建树(出题人解法)。

若，其中是的最小质因子，则的根结点为，边权为，的值是从结点往根结点走边权拼接的值。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 4e6 + 117;
const int MAXM = 1e6 + 117;

int n;
LL ans;
int wei[MAXN];
LL po[MAXN];
int prime[MAXN];
int root[MAXN], edge[MAXN];
void init() {
    wei[0] = 0, wei[1] = 1;
    po[0] = 1, po[1] = 10;
    for(int i = 2; i <= n; i++) {
        wei[i] = wei[i / 10] + 1;
        po[i] = po[i - 1] * 10 % mod;
        if(!prime[i]) {
            prime[++prime[0]] = i;
            root[i] = 1;
            edge[i] = i;
        }
        for(int j = 1; j <= prime[0] && prime[j] <= n / i; j++) {
            prime[prime[j]*i] = 1;
            root[prime[j]*i] = i;
            edge[prime[j]*i] = prime[j];
            if(i % prime[j] == 0) break;
        }
    }
}
void up(int i) {
    LL x = 0;
    while(i != 1) {
        x = (x * po[wei[edge[i]]] + edge[i]) % mod;
        i = root[i];
    }
    ans = (ans + x) % mod;
}
int main() {
    scanf("%d", &n);
    init();
    for(int i = 2; i <= n; i++) up(i);
    printf("%lld\n", ans);
    return 0;
}

J-牛牛想要成为hacker

知识点：构造

斐波那契数列是不能组成三角形并且增长速度最慢的数列。

前面用斐波那契数列，后面用1。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 1e6 + 117;

int n;
int a[MAXN];
int main() {
    a[0] = 2, a[1] = 3;
    for(int i = 2; i <= 41; i++) a[i] = a[i - 1] + a[i - 2];
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        if(i <= 41) printf("%d ", a[i]);
        else printf("1 ");
    }
    return 0;
}