【解题报告】Codeforces Round #361 (Div. 2)

本文主要是介绍【解题报告】Codeforces Round #361 (Div. 2)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接

A. Mike and Cellphone（Codeforces 689A）

思路

当输入号码的相对位置形成的图形无法平移是就输出”YES”，否则输出”NO”。将平移分类成向上平移，向下平移，向左平移和向右平移三种情况。若输入数据包含1,2或3都使得图形不能上移，若输入数据包含7, 9或0都使得图形不能向下平移，若输入数据包含1, 4, 7或0都使得图形不能向左平移，若输入数据包含3, 6, 9或0都使得图形不能向右平移。因此总而言之，这四种平移都不能进行的时候就输出”YES”，否则输出”NO”。

代码

#include <bits/stdc++.h>
using namespace std;bool U = true, D = true, L = true, R = true, vis[20];
char ch;
int n, num;int main() {scanf("%d\n", &n);for(int i = 0; i < n; i++) {scanf("%c", &ch);num = ch - '0';vis[num] = true;}if(vis[7] == true || vis[9] == true || vis[0] == true) {D = false;}if(vis[1] == true || vis[2] == true || vis[3] == true) {U = false;}if(vis[1] == true || vis[4] == true || vis[7] == true || vis[0]) {L = false;}if(vis[3] == true || vis[6] == true || vis[9] == true || vis[0]) {R = false;}puts((D == false && U == false && L == false && R == false) ? "YES" : "NO");return 0;
}

B. Mike and Shortcuts（Codeforces 689B）

思路

原本想的是用动态规划来做，后来发现由于捷径的存在，最优路径可能是一个先前进，然后后退，再前进反复进行的路径。例如，从 $1$ 至 $970$ 的最短路径可能是 $1 , 6, 3, 80, 40, 999, 970$ 。所以就打算把一维的图变换成二维的图然后以点 $1$ 为起点跑最短路算法。变换的时候应该这样建图：相邻节点之间连无向边，捷径之间连有向边，所有边的边权为 $1$ 。

代码

#include <bits/stdc++.h>
using namespace std;typedef pair <int, int> p;
const int maxn = 2e5 + 10, INF = maxn;
int n, v;struct edge {int to, dist;edge() {}edge(int to, int dist): to(to), dist(dist) {}
};struct Dijkstra {int d[maxn];vector <edge> G[maxn];void addEdge(int u, int v, int w) {G[u].push_back(edge(v, w));}void solve(int s) {fill(d + 1, d + n + 1, INF);d[s] = 0;priority_queue < p, vector<p>, greater<p> > pq;pq.push(p(0, s));while(!pq.empty()) {p node = pq.top();pq.pop();int u = node.second;if(node.first > d[u]) {continue;}for(int i = 0; i < G[u].size(); i++) {edge& e = G[u][i];int v = e.to;int w = e.dist;if(d[v] > d[u] + w) {d[v] = d[u] + w;pq.push(p(d[v], v));}}}}
}o;int main() {scanf("%d", &n);for(int i = 1; i <= n; i++) {scanf("%d", &v);o.addEdge(i, i + 1, 1);o.addEdge(i + 1, i, 1);o.addEdge(i, v, 1);}o.solve(1);for(int i = 1; i <= n; i++) {printf("%d ", o.d[i]);}puts("");return 0;
}

C. Mike and Chocolate Thieves（Codeforces 689C）

思路

从 $m$ 得知 $n$ 是困难的，但是从 $n$ 得知 $m$ 却是可行的根据计数方法，将 $n$ 代入下面的 $c$ 函数中就能求出 $m$ 。于是我们可以枚举所有可能的 $n$ ，当结果等于 $m$ 的时候用当前 $n$ 更新最小解就好了。但是由于解空间太庞大，所以枚举肯定会超时。于是我们可以利用 $m$ 的“二分性”（ $m$ 这里是对 $n$ 的升序）来对 $n$ 进行二分查找。

代码

#include <bits/stdc++.h>
using namespace std;typedef long long ll;
ll m, l, r, mid;ll c(ll n) {ll res = 0;for(ll q = 2; n >= q * q * q; q++) {res += n / (q * q * q);}return res;
}int main() {cin >> m;l = 7;r = 100 * m;while(r - l > 1) {mid = (l + r) >> 1;if(c(mid) >= m) {r = mid;}else {l = mid;}}if(c(r) == m) {cout << r << endl;}else {cout << -1 << endl;}return 0;
}

D. Friends and Subsequences（Codeforces 689D）

思路

我们定义 $max(i, j)$ 为 $a[i]$ 到 $a[j]$ 之间的最大值。那么 $max$ 函数有这样的性质：当 $i$ 为定值的时候， $max(i, j)$ 随着 $j$ 的增大而非减。同样， $min(i, j)$ 随着j的增大而非增。也就是说 $max(i, j) - min(i, j)$ 在 $i$ 为定值的情况下对于 $j$ 是非减函数。有了“序”以后一切都好办了。我们相当于找到了 $max(i, j) - min(i, j)$ 的二分性。于是对于每个 $i$ ，我们可以枚举 $j$ ，找出满足 $max(i, j) - min(i, j)$ 的连续的 $j_1, ..., j_k$ ，那么对于当前的i而言，满足 $max(i, j) - min(i, j)$ 的 $j$ 的个数就是 $j_k - j_1 + 1$ （j的合法区间的长度），我们将其加到答案 $ans$ 中。枚举完 $i$ 以后， $ans$ 就是最终答案了。其中，根据二分性我们将对于 $j$ 的枚举改成对于 $j$ 的二分查找能够将时间复杂度控制在合理的范围内。另外快速查询 $max(i, j)$ 和 $min(i, j)$ 可以用 $ST$ 表 $(O(1))$ 或线段树 $(O(logn))$ 这样的数据结构，否则仍然会超时。

代码

#include <bits/stdc++.h>
using namespace std;typedef long long ll;
const int maxn = 2e5 + 10;
int n, lb, ub, a[maxn], b[maxn];
ll ans;struct table {int stTable[maxn][32][2];int preLog2[maxn];void init(int n, int* array) {preLog2[1] = 0;for(int i = 2; i <= n; i++) {preLog2[i] = preLog2[i-1];if((1 << preLog2[i] + 1) == i) {++preLog2[i];}}for(int i = n - 1; i >= 0; i--) {stTable[i][0][0] = stTable[i][0][1] = array[i];for(int j = 1; (i + (1 << j) - 1) < n; j++) {stTable[i][j][0] = max(stTable[i][j-1][0], stTable[i+(1<<j-1)][j-1][0]);stTable[i][j][1] = min(stTable[i][j-1][1], stTable[i+(1<<j-1)][j-1][1]);}}}int rmq(int l, int r, int d) {int len = r - l + 1, k = preLog2[len];if(d == 0) {return max(stTable[l][k][0], stTable[r-(1<<k)+1][k][0]);}else {return min(stTable[l][k][1], stTable[r-(1<<k)+1][k][1]);}}
}A, B;int binary(int L, int& lb, int& ub) {int l = L - 1, r = n;while(r - l > 1) {int mid = (l + r) >> 1;int tmp = A.rmq(L, mid, 0) - B.rmq(L, mid, 1);if(tmp < 0) {l = mid;}else {r = mid;}}lb = r;l = L - 1, r = n;while(r - l > 1) {int mid = (l + r) >> 1;int tmp = A.rmq(L, mid, 0) - B.rmq(L, mid, 1);if(tmp <= 0) {l = mid;}else {r = mid;}}ub = r;
}int main() {scanf("%d", &n);for(int i = 0; i < n; i++) {scanf("%d", &a[i]);}A.init(n, a);for(int i = 0; i < n; i++) {scanf("%d", &b[i]);}B.init(n, b);for(int L = 0; L < n; L++) {binary(L, lb, ub);ans += ub - lb;}printf("%I64d\n", ans);return 0;
}