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;
} 
比亚迪二面9人在聊
投递联易融等公司10个岗位 >