A. Wrath
题目大意
给你一个\(L\)数组和\(n\)个人，第\(i\)个人可以使用威力为\(L_i\)的闪电旋风劈击杀前面\(L_i\)人，问你最后能存活多少人？
思路
差分。开一个数组来标记当前威力的闪电旋风劈能击杀到的最远的人和使用技能的人，最远击杀的人所在的位置+1，自己的位置-1，这样算前缀和时所在位置被标记为0的人就是存活的人
ac代码
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const i64 inf = 8e18;
typedef pair<int, int> pii;
const int N = 3e5 + 10;
void solve() {
int n;
cin >> n;
int ans = 0;
std::vector<int> v(n + 1), st(n + 1);
for (int i = 1; i <= n; i++) cin >> v[i];
for (int i = 2; i <= n; i++) {
int t = max(1, i - v[i]);
st[t] += 1;
st[i] -= 1;
}
for (int i = 1; i <= n; i++) {
st[i] += st[i - 1];
if (!st[i]) ans ++;
}
cout << ans << endl;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int t = 1;
//cin >> t;
while (t --) solve();
return 0;
}
B. Chtholly's request
题目大意
定义长度为偶数的十进制回文数为\(zcy\)数，让你求前\(n\)个zcy数之和再模上\(p\)的结果
思路
很明显，第\(i\)个\(zcy\)数就是\(i\)后面接上\(i\)的逆序，例如第\(114514\)个\(zcy\)数就是114514415411
ac代码
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const i64 inf = 8e18;
typedef pair<int, int> pii;
const int N = 3e5 + 10;
void solve() {
i64 k, p;
cin >> k >> p;
i64 ans = 0;
for (int i = 1; i <= k; i++) {
string tmp1 = to_string(i);
string tmp2 = tmp1;
reverse(tmp2.begin(), tmp2.end());
tmp1 = tmp1 + tmp2;
ans += stoll(tmp1);
ans %= p;
}
cout << ans % p << endl;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int t = 1;
//cin >> t;
while (t --) solve();
return 0;
}
C. Powers Of Two
题目大意
给你两个整数\(n\)和\(k\)，问你\(n\)是否可以由\(k\)个2的幂组成，例如8可以由4、4或者1、1、1、1、2、2组成
思路
用sum记录\(n\)写成二进制时\(1\)的个数，这里表示\(n\)最少能用sum个2的幂组成。我们能看到，这 sum个 2的幂里 大于\(1\)的数 每除一下2，就能多出来一个 2的幂，我们可以用这种方法可以找出能组成\(n\)的\(k\)个数
ac代码
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const i64 inf = 8e18;
typedef pair<int, int> pii;
const int N = 3e5 + 10;
void solve() {
i64 n, k, sum = 0;
cin >> n >> k;
i64 cnt[70] = {0};
for (i64 i = 0; i < 64; i++) {//记录一下n的二进制里哪些位置有1
if ((n >> i) & 1) {
cnt[i] ++;
sum ++;
}
}
int idx = 64;
while (idx && sum < k) {//从后往前枚举
if (cnt[idx]) {
while (cnt[idx] && sum < k) {
if (idx) {
sum ++;
cnt[idx] --;
cnt[idx - 1] += 2;
}
}
}
idx --;
}
if (sum != k) cout << "NO\n";
else {
cout << "YES\n";
for (int i = 0; i < 70; i++) {
while (cnt[i] --) cout << (1 << i) << ' ';
}
}
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int t = 1;
//cin >> t;
while (t --) solve();
return 0;
}
D. Fadi and LCM
题目大意
给你一个整数\(x\)，让你找出两个数\(a\)、\(b\)，使得\(LCM(a, b) == x\)，且\(max(a, b)\)尽量小
思路
\(x\)的范围有1e12，\(\sqrt{x}\)只有1e6，直接枚举即可。
还有，我们知道\(gcd(a, b) * lcm(a, b) == a * b\)
ac代码
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const i64 inf = 8e18;
typedef pair<int, int> pii;
const int N = 3e5 + 10;
void solve() {
i64 x, a = inf, b = inf;
cin >> x;
for (i64 i = 1; i * i <= x; i ++) {
if (x % i) continue;
i64 tmpa = i, tmpb = x / i;
if (tmpa * tmpb /__gcd(tmpa, tmpb) == x)
if (max(tmpa, tmpb) < max(a, b))
a = tmpa, b = tmpb;
}
cout << a << ' ' << b << endl;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int t = 1;
//cin >> t;
while (t --) solve();
return 0;
}
E. Line Empire
题目大意
太长了不想打
思路
当换首都的贡献小于不换首都的贡献时就换首都
ac代码
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const i64 inf = 8e18;
typedef pair<int, int> pii;
const int N = 3e5 + 10;
void solve() {
i64 n, a, b, ans = 0;
cin >> n >> a >> b;
std::vector<int> v(n + 1), s(n + 1);
for (int i = 1; i <= n; i++) {
cin >> v[i];
s[i] = s[i - 1] + v[i];
}
int now_cap = 0;
for (int i = 1; i <= n; i++) {
ans += b * (v[i] - now_cap);
i64 t1 = b * (s[n] - s[i] - (n - i) * now_cap);//不换首都，且用当前首都攻击后面的全部首都
i64 t2 = a * (v[i] - now_cap) + b * (s[n] - s[i] - (n - i) * v[i]);//换首都，且用更换后的首都攻击后面的全部首都
if (t2 < t1) {
ans += a * (v[i] - now_cap);
now_cap = v[i];
}
}
cout << ans << endl;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int t = 1;
cin >> t;
while (t --) solve();
return 0;
}