Codeforces Round #751 (Div. 2)

知识点整理：

题号	知识点	难度	备注
A	字符串	800
B	构造	1100
C	数学	1300
D	BFS，DP	1900
E	分治，贪心，线段树	2300
F	排序，贪心	2700

A题

题意：

给你一个字符串s，把他拆成两个字符串，a和b，要求a的字典序最小。

题解：

找到s里最小的字符，单独把它拿出来，然后把剩下的构成一个新字符串。

#include <bits/stdc++.h>using namespace std;typedef long long ll;
typedef pair<int, int> pii;const int MAXN = 1e5 + 10;
const int MOD = 1e9 + 7;int main() {
#ifdef LOCALfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);
#endifios::sync_with_stdio(false), cin.tie(0);int t;string s;cin>>t;while(t--) {cin>>s;char m = CHAR_MAX;int id = 0;for(int i=0;i<s.size();i++) {char ch = s[i];if (ch < m) {m = ch;id = i;}}s.erase(id, 1);cout << m << ' ' << s << endl;}return 0;
}

B题

题意：

给你个数组$A$， 做以下操作若干次：

把上一次每个数出现的次数替换成下一轮的数。

给你$q$次询问，问$k$轮的时候，$a_i$是多少？

题解：

写几次发现操作若干次之后就不会变了。

所以把变的都记下来，直到不变为止。

#include <bits/stdc++.h>using namespace std;typedef long long ll;
typedef pair<int, int> pii;const int MAXN = 2e3 + 10;
const int MOD = 1e9 + 7;int t, n, q, x, k;
int a[MAXN], b[MAXN][MAXN];map<int, int> cnt;bool check() {for (auto [k, v] : cnt) {if (k != v)return true;}return false;
}
int main() {
#ifdef LOCALfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);
#endifios::sync_with_stdio(false), cin.tie(0);cin >> t;while (t--) {cnt.clear();cin >> n;for (int i = 1; i <= n;i++) {cin >> a[i];cnt[a[i]]++;b[0][i] = a[i];}int j = 1;while (check()) {for (int i = 1; i <= n; i++) {b[j][i] = cnt[b[j - 1][i]];}cnt.clear();for (int i = 1; i <= n; i++) {cnt[b[j][i]]++;}j++;}j--;cin >> q;while (q--) {cin >> x >> k;cout << b[min(j, k)][x] << endl;}}return 0;
}

C题

题意：

给你个数组$A$， 让你进行一个$k$-消除操作：

• 在$A$中找$k$个数
• 求他们的and值，记作x
• 这k个数都减去x

重复上面操作直到全变成0，求所有可行的k

题解：

把数组里面每个数按二进制位拆开，发现每次都是找$k$个数同时变0，否则不变

所以，要想让这个$k$可行，必须是每一位中1的个数的gcd，这样才可以每次选k个数让他同时变0.

那么k的最大值既然知道了，其所有约数也都是答案。

特殊的，如果全都是0，是一种特殊情况，输出所有1～n

#include <bits/stdc++.h>using namespace std;typedef long long ll;
typedef pair<int, int> pii;const int MAXN = 2e5 + 10;
const int MOD = 1e9 + 7;int t,n,a[MAXN];int cnt[30];
int main() {
#ifdef LOCALfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);
#endifios::sync_with_stdio(false), cin.tie(0);cin>>t;while(t--){int n;cin >> n;for(int i=1; i<=n; i++)cin>>a[i];memset(cnt, 0, sizeof(cnt));int m = 0;for (int i = 0; i < 30; i++) {int mask = 1<<i;for (int j = 1; j <= n; j++) {if (a[j]&mask)cnt[i]++;}m = __gcd(m, cnt[i]);}// 全是0if (m == 0) {for (int i = 1; i <= n; i++) cout << i << ' ';cout << endl;} else {// 输出m的约数set<int> s;for (int i = 1; i*i <= m; i++) if (m%i==0) {s.insert(i);s.insert(m/i);}for (auto it : s)cout << it << ' ';cout << endl;}        }return 0;
}

D题

题意

题目大意就是，你现在在一个深度为m的坑里，给你两个数组a和b

a[i]表示深度为i时最多往上跳多少

b[i]表示你跳到这里之后必须要往下滑多少

问你跳出去至少几步，以及输出方案

题解

一开始tle了，发现可以优化：每次枚举一个状态$<j,k>$， 其中$j$是从上一步跳上来的点，$k$是滑下去的点。

当前处在$k$位置，那么下一步的跳上去的点可能是$[k-a[k],k]$之间，而如果这些值都搜索过之后，后面再算$k-a[k]$以后的$j$值就都没必要了，根据bfs的特性，后面搜的步数大于等于前面的，所以再重复搜$j$也不可能得到更优解，因此每次搜索状态之后，更新枚举过的$k-a[k]$的最小值，只有比他更小才有搜索的必要。因此$j$是单调递减的，整个时间复杂度可以优化到$O(n)$.

#include <bits/stdc++.h>using namespace std;typedef long long ll;
typedef pair<int, int> pii;const int MAXN = 3e5 + 10;
const int MOD = 1e9 + 7;int n, a[MAXN], b[MAXN];
int dis[MAXN];int pre[MAXN];typedef struct Node {int x;int y;int steps;
} Node;int bfs(pii st) {int x = st.first, y = st.second;memset(dis, 0x3f, sizeof(dis));queue<Node> q;q.push({ x, y, 0 });dis[n] = 0;int dep = n;while (!q.empty()) {auto nd = q.front();q.pop();int j = nd.x, k = nd.y;if (j == 0) {return dis[j];}for (int i = a[k]; i >= 1; i--) {int nextj = k - i;if (nextj >= dep) break;int nextk = nextj + b[nextj];if (dis[nextk] > dis[k] + 1) {dis[nextk] = dis[k] + 1;pre[nextj] = j;q.push({nextj, nextk, nd.steps+1});}}dep = min(dep, k - a[k]);}return -1;
}int main() {
#ifdef LOCALfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);
#endifios::sync_with_stdio(false), cin.tie(0);cin >> n;for (int i = 1; i <= n; i++) {cin >> a[i];}for (int i = 1; i <= n;i++)cin >> b[i];int res = bfs({ n, n });cout << res << endl;if (res != -1) {vector<int> ans;for (int i = 1, j = n; i <= res; i++, j = pre[j])ans.push_back(pre[j]);for (int i = res-1; i >= 0; i--)cout << ans[i] << ' ';cout << endl;}return 0;
}