链接:
https://ac.nowcoder.com/acm/contest/44007
B. Card
前缀和
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
using i128 = __int128;
void solve() {
int n, k;
cin >> n >> k;
vector<i64> a(n + 1), b(n + 1);
i64 sum = 0;
for (int i = 1; i <= n; i++) {
cin >> a[i];
sum += a[i];
}
for (int i = 1; i <= n; i++) {
cin >> b[i];
}
vector<pair<i64, int>> c(n + 1);
for (int i = 1; i <= n; i++) {
c[i].first = b[i] - a[i];
c[i].second = i;
}
sort(c.begin() + 1, c.end(), greater<>());
vector<int> id(n + 1);
for (int i = 1; i <= n; i++) {
id[i] = c[i].second;
}
vector<int> pos(n + 1);
for (int i = 1; i <= n; i++) {
pos[id[i]] = i;
}
vector<i64> pre(n + 1);
for (int i = 1; i <= n; i++) {
pre[i] = c[i].first;
pre[i] += pre[i - 1];
}
int m;
cin >> m;
for (int i = 0; i < m; i++) {
int len;
cin >> len;
int more = 0;
i64 add = 0;
vector<int> d;
for (int j = 0; j < len; j++) {
int x;
cin >> x;
if (pos[x] <= k) {
more++;
add += c[pos[x]].first;
} else {
d.push_back(pos[x]);
}
}
sort(d.begin(), d.end());
for (auto di : d) {
if (di <= k + more) {
more++;
add += c[di].first;
} else {
break;
}
}
cout << pre[k + more] - add + sum << '\n';
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int tt = 1;
//cin >> tt;
while (tt--) {
solve();
}
return 0;
}
D. Hash
进制转换
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
constexpr int mod = 5999993;
i64 get(string s) {
i64 res = 0;
for (char c : s) {
res = (res * 29 + (c - 'a' + 1)) % mod;
}
return res;
}
void solve() {
string s;
cin >> s;
i64 h1 = get(s);
i64 ori = h1;
for (int i = 0; i < 6; i++) {
h1 = h1 * 29 % mod;
}
i64 h2 = ori - h1;
if (h2 < 0) {
h2 += mod;
}
for (int i = 0; i < 200; i++) {
i64 tmp = h2 + i * mod;
string ans;
bool ok = 1;
for (int j = 0; j < 6; j++) {
int num = tmp % 29;
if (num == 0 || num > 26) {
ok = 0;
break;
}
tmp -= num;
ans += (char) (num + 'a' - 1);
tmp /= 29;
}
if (ok) {
cout << s;
for (int i = 5; i >= 0; i--) {
cout << ans[i];
}
cout << '\n';
return;
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int tt = 1;
cin >> tt;
while (tt--) {
solve();
}
return 0;
}
G. 2D-Lake
二分
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
using i128 = __int128;
constexpr i64 N = 1E18;
void print(i128 x) {
i64 num1 = x / N;
i64 num2 = x % N;
if (x <= N) {
cout << (i64) x << '\n';
return;
}
cout << num1 << setw(18) << setfill('0') << num2;
}
void solve() {
i64 n, m;
cin >> n >> m;
i128 n1 = n, m1 = m;
if (n1 != 1 && n1 != 2) {
if (n1 % 2 == 1 && (n1 - 1) * (n1 - 1) / 4 >= m1) {
print((n1 - 1) * (n1 - 1) / 4);
return;
} else if (n1 % 2 == 0 && n1 * (n1 - 2) / 4 >= m1) {
print(n1 * (n1 - 2) / 4);
return;
}
}
// odd
i128 ans1 = 0;
i128 l = 2, r = 1E10;
while (l <= r) {
i128 mid = (l + r) >> 1;
auto check1 = [&](i128 x) {
i128 tmp = x * 2 - 1;
if ((tmp - 1) * (tmp - 1) / 4 >= m) {
return true;
}
return false;
};
if (check1(mid)) {
r = mid - 1;
ans1 = mid;
} else {
l = mid + 1;
}
}
// even
l = 3, r = 1E10;
i128 ans2 = 0;
while (l <= r) {
i128 mid = (l + r) >> 1;
auto check2 = [&](i128 x) {
i128 tmp = (x - 1) * 2;
if (tmp * (tmp - 2) / 4 >= m) {
return true;
}
return false;
};
if (check2(mid)) {
r = mid - 1;
ans2 = mid;
} else {
l = mid + 1;
}
}
i128 ans = min(2 * ans1 - 1, (ans2 - 1) * 2);
print(ans);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int tt = 1;
//cin >> tt;
while (tt--) {
solve();
}
return 0;
}
H. Cute Rabbit
数据过弱
J. Make it Equal
签到
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
void solve() {
int n;
cin >> n;
vector<int> a(n);
set<int> s;
for (int i = 0; i < n ;i++) {
cin >> a[i];
s.insert(a[i]);
}
if ((int) s.size() == 1) {
cout << n << '\n';
return;
}
cout << n - 1 << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int tt = 1;
//cin >> tt;
while (tt--) {
solve();
}
return 0;
}
标签:陕西省,return,int,i64,2022,using,i128,n1
From: https://www.cnblogs.com/kiddingma/p/16820100.html