關(guān)于加強(qiáng)網(wǎng)站建設(shè)的意見(jiàn)網(wǎng)站后臺(tái)管理系統(tǒng)
A~D比較簡(jiǎn)單就不寫了,哎嘿
E. Negatives and Positives

給出一個(gè)數(shù)組a,可以對(duì)數(shù)組進(jìn)行若干次操作,每次操作可以將相鄰的兩個(gè)數(shù)換為它們的相反數(shù),求進(jìn)行若干次操作之后能得到數(shù)組和的最大值是多少。
思路:最大的肯定是把負(fù)數(shù)都變成正數(shù)吧,從這里開(kāi)始考慮,對(duì)于兩個(gè)相鄰的數(shù)為--的,可以進(jìn)行一次操作讓它們變?yōu)?#43;+;對(duì)于類似-+-這樣的,可以進(jìn)行若干次操作使得所有的數(shù)都變?yōu)檎龜?shù):-+- -> +-- -> +++。所以對(duì)于數(shù)組中負(fù)數(shù)個(gè)數(shù)為偶數(shù)的,所有的負(fù)數(shù)都可以被變成正數(shù);對(duì)于負(fù)數(shù)個(gè)數(shù)為奇數(shù)的,若要得到最大的值,應(yīng)當(dāng)保留絕對(duì)值最小的那個(gè)數(shù)為負(fù)值。
AC Code:
#include <bits/stdc++.h>typedef long long ll;
const int N = 2e5 + 5;
int t, n;
ll a[N];int main() {std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);std::cin >> t;while(t --) {std::cin >> n;ll cnt = 0, min = 2e9;for(int i = 1; i <= n; i ++) {std::cin >> a[i];min = std::min(min, abs(a[i]));if(a[i] < 0) cnt ++;}ll sum = 0;for(int i = 1; i <= n; i ++) {sum += abs(a[i]);}if(cnt & 1)sum -= 2 * min;std::cout << sum << '\n';}return 0;
}
F. Range Update Point Query

給出一個(gè)序列a,有兩種操作,一個(gè)是對(duì)于區(qū)間[l, r]內(nèi)的數(shù)進(jìn)行如下操作:將數(shù)替換為所有位的數(shù)字之和;一個(gè)是給出x,輸出位于x的數(shù)。
思路:樹(shù)狀數(shù)組裸題練習(xí)。用樹(shù)狀數(shù)組維護(hù)前綴和,每次進(jìn)行操作就在區(qū)間內(nèi)+1,看數(shù)據(jù)范圍,范圍內(nèi)最大的數(shù)經(jīng)過(guò)3次操作后也會(huì)變成一位,后面就不變了,所以顯而易見(jiàn),我們維護(hù)的前綴和的含義是修改次數(shù),輸出結(jié)果的時(shí)候加入判斷即可。
AC Code:
#include <bits/stdc++.h>typedef long long ll;
const int N = 2e5 + 5;
int t, n, q;
int c[N], a[N];int lowbit(int x) {return x & -x;
}void update(int pos, int x) {for(; pos <= n; pos += lowbit(pos)) {a[pos] += x;}
}int query(int x) {int tot = 0;for(; x > 0; x -= lowbit(x)) {tot += a[x];}return tot;
}int getnum(int x) {int num = 0;while(x) {num += (x % 10);x /= 10;}return num;
}int main() {std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);std::cin >> t;while(t --) {std::cin >> n >> q;for(int i = 1; i <= n; i ++) {std::cin >> c[i];}for(int i = 0; i <= n + 1; i ++) {a[i] = 0;}while(q --) {int op;std::cin >> op;if(op == 1) {int l, r;std::cin >> l >> r;update(l, 1);update(r + 1, -1);}else {int x;std::cin >> x;if(c[x] < 10)std::cout << c[x] << '\n';else {int cnt = query(x);cnt = std::min(3, cnt);int num = c[x];while(cnt --) {num = getnum(num);}std::cout << num << '\n';}}}}return 0;
}
G1. Teleporters (Easy Version)

給出一個(gè)有0~n個(gè)點(diǎn)的數(shù)軸,1~n每個(gè)點(diǎn)有一個(gè)傳送門,每走一步會(huì)消耗一個(gè)金幣,走傳送門也有相應(yīng)的消耗a[i],每個(gè)傳送門只能走一次,傳送門會(huì)傳送到0點(diǎn),問(wèn)最多可以走幾個(gè)傳送門。
思路:每個(gè)傳送門的消耗是到達(dá)步數(shù)+傳送門消耗,排序,貪心求解即可。
AC Code:
#include <bits/stdc++.h>typedef long long ll;
const int N = 2e5 + 5;
int t, n, c;
ll a[N];int main() {std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);std::cin >> t;while(t --) {std::cin >> n >> c;int cnt = 0;std::vector<int> vec;for(int i = 1; i <= n; i ++) {std::cin >> a[i];vec.push_back(i + a[i]);}std::sort(vec.begin(), vec.end());for(int i = 0; i < (int) vec.size(); i ++) {if(vec[i] <= c)cnt ++, c -= vec[i];}std::cout << cnt << '\n';}return 0;
}
G2. Teleporters (Hard Version)

給出一個(gè)有0~n個(gè)點(diǎn)的數(shù)軸,1~n每個(gè)點(diǎn)有一個(gè)傳送門,每走一步會(huì)消耗一個(gè)金幣,走傳送門也有相應(yīng)的消耗a[i],每個(gè)傳送門只能走一次,傳送門會(huì)傳送到0點(diǎn)或n+1點(diǎn),問(wèn)最多可以走幾個(gè)傳送門。
思路:因?yàn)楝F(xiàn)在位于點(diǎn)0,所以對(duì)于從那個(gè)點(diǎn)開(kāi)始,需要我們討論。然后,對(duì)于其他點(diǎn),我們可以選擇從兩側(cè)哪一側(cè)到達(dá),可以枚舉起點(diǎn),對(duì)于其他點(diǎn)采用前綴和維護(hù)消費(fèi),二分查找答案,具體細(xì)節(jié)看代碼。
AC Code:
#include <bits/stdc++.h>typedef long long ll;
const int N = 2e5 + 5;
int t, n, c;
ll b[N];
std::pair<ll, ll> a[N];int main() {std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);std::cin >> t;while(t --) {std::cin >> n >> c;ll ans = 0;for(int i = 0; i < n; i ++) {int m;std::cin >> m;a[i].first = std::min(m + i + 1, m + n - i);a[i].second = m + i + 1;}std::sort(a, a + n);for(int i = 0; i < n; i ++) {b[i + 1] = b[i] + a[i].first;}for(int i = 0; i < n; i ++) {if(a[i].second <= c) {int l = 0, r = n;while(l < r) {int mid = (l + r + 1) >> 1;ll sum = b[mid];if(mid > i)sum -= a[i].first;if(a[i].second + sum <= c)l = mid;elser = mid - 1;}ans = std::max(ans, (ll)l + 1 - (l > i));}}std::cout << ans << '\n';}return 0;
}