520 PTA钻石争霸赛 2021（部分题解）

520的比赛一直比天梯赛的难度低不少，所以这次就找了两个有意思的题来写了一下题解。

这个题还是挺有意思的，当时看见题意后，第一反应是求前缀，然后暴力，但是n的范围是1e4，所以是会爆long long的（这样应该是少1分）。然后我就推了一下公式。
以下是我的推导过程：（好久没在纸上写过程了，字不好，请见谅）

接下来就是暴力了

code：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
const int N = 1e5 + 100;
const int INF = 0x3f3f3f3f;#define int long long
signed main(int argc, char const *argv[]) {int n;cin >> n;int ans = 0;for (int x = 1;; x++) {if (x * x == n * n * (2 * x + 2 * n + 1)) {ans = x;break;}}for (int i = ans; i <= ans + 2 * n; i++) {if (i == ans + n) {cout << i << "^2 =" << endl;} else if (i < ans + n) {cout << i << "^2 + ";} else if (i == ans + 2 * n) {cout << i << "^2";} elsecout << i << "^2 + ";}return 0;
}

题意很好理解，就是一个数的左视图和右视图。
有后序和中序，先建起来一个树。
在树的一边观察树，哪些节点被挡到了就是看不到的。所以对于左视图来看，每层的节点只会看到第一个节点。右视图就是只能看到每层的最后一个节点。

code：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
const int N = 1e5 + 100;int n;
int a[N], b[N], res[N];
int cnt;
int ma = 0;
void dfs(int l, int r, int kk) {if (l > r || cnt <= 0) return;int x = a[cnt], i;for (i = l; i <= r; i++) {if (b[i] == x) break;}res[kk] = b[i];ma = max(kk, ma);cnt--;dfs(i + 1, r, 2 * kk + 1);dfs(l, i - 1, 2 * kk);
}vector<int> ve[N];
int main(int argc, char const *argv[]) {cin >> n;for (int i = 1; i <= n; i++) cin >> b[i];for (int i = 1; i <= n; i++) cin >> a[i];cnt = n;dfs(1, n, 1);int sum = 0;for (int i = 1; i <= ma; i++) {if (res[i] != 0) {ve[(int)log2(i)].push_back(res[i]);}}cout << "R: ";for (int i = 0; i <= (int)log2(ma); i++) {if (ve[i].size() != 0) cout << ve[i][ve[i].size() - 1];if (i != (int)log2(ma)) cout << " ";}cout << endl;cout << "L: ";for (int i = 0; i <= (int)log2(ma); i++) {if (ve[i].size() != 0) cout << ve[i][0];if (i != (int)log2(ma)) cout << " ";}cout << endl;return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！