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

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

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

A-牛牛与牛妹的RMQ

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

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

注：下面代码可$hack$，取$n=m=1e5,k_i=2,p_1=1,p_2=n$就会超时，原因在于求区间极值时用的循环，没想到过了(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-牛牛抓牛妹

知识点：最短路

  • 建分层图，最多$n*2^k$个点。
  • 对于每一层，预处理出每个点的下一步，对于没有下一步的点就是终点（可能有多个）。
  • 从起点出发广搜一遍，找到一条到达终点的路径后输出指令即可。
#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

知识点：找规律

  • 当$n \geq l*2$时，循环节长度为$gcd(n,l)$，这样一个$l$或者一个$n$都恰好被若干个循环填满，从前往后取若干个$l$和从后往前取若干个$l$得到的串都是若干个完整的循环，一定相同。
  • 当$n < l*2$时，循环节长度为$n-l$。
  • 小心$n==l$的情况。
#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-牛牛与整除分块

知识点：数论

当$k \leq \sqrt{n}$时输出$k$，否则输出以$x=\sqrt{n}$为对称轴对称的值。

#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-牛牛与跷跷板

知识点：$two \;pointer、bfs$

  • 先按$y$分组再按$l$排序。
  • 对于每一组双指针扫一遍建图。
  • 最后跑$bfs$。
#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-牛牛与交换排序

知识点：双端队列

  • 遍历数组找到$k$值。
  • 数组依次进入双端队列，从第$k$个开始检查队首元素是不是$k$，如果不是就翻转队列。队首是$k$则队首出队，否则无解。
  • 入队结束后需要检查队列中剩余元素是否有序，无序则无解。
#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-牛牛与比赛颁奖

知识点：差分前缀和

  • 先离散化，然后利用差分的性质$o(1)$修改区间值。
  • 桶装计数得到通过$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 = 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-牛牛的“质因数”

知识点：线性筛

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

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

代码中$dfs(int \;id, LL \;num, LL \;sum, int \;cnt)$表示当前数字是$num$，$num$的最小质因子是第$id$个，$F(num)=sum$，$sum$有$cnt$位。

#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;
}

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

若$x=p*k$，其中$p$是$x$的最小质因子，则$x$的根结点为$k$，边权为$p$，$F[x]$的值是从$x$结点往根结点走边权拼接的值。

#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;
}

版权属于：小影

本文链接：http://kindkidll.com/index.php/archives/180/

所有原创文章采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可。 您可以自由的转载和修改，但请务必注明文章来源并且不可用于商业目的。

Last modification：July 21st, 2021 at 12:27 pm
© 允许规范转载
如果觉得我的文章对你有用，请随意赞赏