C 奋发
题目描述
算法
因为数列单调直接 找第i层的最小值 第i-1层的最大值
(模拟) $O(n)$
#include<bits/stdc++.h>
//#define x first
//#define y second
#define IOS ios::sync_with_stdio(0);
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 3e6+10;
int x[N], y[N];
int T, n, m;
int l, r, ans;
inline int read() {
int s = 0, f = 1;char ch = getchar();
while (ch < '0' || ch > '9') { if (ch == '-') f = -1;
ch = getchar(); }
while (ch >= '0' && ch <= '9') {s = s * 10 + ch - '0';
ch = getchar(); }
return s * f;
}
void solve() {
for (int i = 1; i <= n; i ++)
x[i] = read(), y[i] = read();
for (int i = 1; i <= n; i ++) {
l = min(x[i], y[i]);
r = max(x[i - 1], y[i - 1]);
if (l >= r) {
ans += l - r;
if (x[i-1] != y[i-1]){ // 如果不同 那么就会有操作使他们相同 ans得++
ans ++;
}
}
}
cout << ans << endl;
}
int main() {
n = read();
solve();
return 0;
}
G 冷静
题目描述
算法
(离线查询 加 树状数组) $O(nlogn)$
大于等于 K 的质数的乘积 ——> 可以推出来我们直接维护每个数的最小质因子即可
离线思路 : 将所有查询区间记录下来
我们需要考虑数据结构来维护每个最小质因子 因为单点操作 可以用树状数组
添加 : 对于每个数 我们在树状数组上对他的最小质因子 +1 即可
查询 : 查询l, r的前缀区间即可
#include<bits/stdc++.h>
using namespace std;
const int N = 1e7;
int primes[N], cnt, f[N];
int tr[N];
bool st[N];
struct Node{
int n, k, id;
bool operator < (const Node &t) const {
return n < t.n;
}
}g[N];
int lowbit(int x)
{
return x & -x;
}
void add(int x, int k)
{
for(int i = x; i <= 3e6; i += lowbit(i)) tr[i] += k;
}
int ask(int x)
{
int res = 0;
for (int i = x; i; i -= lowbit(i)) res += tr[i];
return res;
}
void init(int n) // 线性筛质数
{
for(int i = 2 ; i <= n ;i++ )
{
if(!st[i])
{
primes[cnt++] = i;
f[i] = i;
}
for(int j = 0 ; primes[j] <= n/i ;j++ )
{
f[primes[j] * i] = primes[j];
st[primes[j]*i] = true;
if(i % primes[j] == 0) break;
}
}
}
int main()
{
init(N);
int T;
scanf("%d", &T);
for (int i = 1; i <= T; i ++)
{
int a, b;
scanf("%d%d",&a, &b);
g[i] = {a, b, i};
}
sort(g+1, g+T+1);
vector<int> ans(T + 1);
int t = 1;
for (int i = 1; i <= T; i ++) {
while (t < g[i].n) add(f[++ t], 1);
ans[g[i].id] = g[i].n - ask(g[i].k - 1) - 1;
}
for (int i = 1; i <= T; i ++) printf("%d\n", ans[i]);
return 0;
}
H 终别
题目描述
珂朵莉面对了共nn只十七兽,它们站成一排,每只十七兽站在一个位置上,她的斩击可以使连续33个位置上的十七兽(也可以只使一只,或相邻两只受到伤害),每一只受到一点伤害,当一个十七兽的血量归零时,视为该十七兽被消灭(但位置仍然保留),她还拥有一个魔法,魔法可以在战斗的任意时刻使用,但只能使用一次,可以直接消灭相邻的22个位置上的十七兽(只有一只也可以使用,位置仍然保留),请问,她最少需要挥出多少次斩击,能够消灭所有十七兽?因为她已经筋疲力尽了,所以需要聪明的你来帮帮她!
算法
(前后缀) $O(n)$
不考虑使用魔法的话
我们需要对数组进行顺序斩3个的操作
但考虑魔法的话
我们需要枚举一个位置使用魔法 使操作次数最小
那么我们就可以用前后缀预处理操作数 求最小值
对于枚举到i 结果就是 pre[i-1]+bac[i+2]
注:
处理边界
1. 即对前两个使用魔法 ans = bac[2]
2. 即对后两个使用魔法 ans = min(bac[2], pre[n-3])
C++ 代码
// 前后缀
#include <bits/stdc++.h>
typedef long long LL;
using namespace std;
const int N = 1e6+10;
LL a[N], b[N], pre[N], bac[N];
int n;
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i ++) scanf("%d", &a[i]), b[i] = a[i];
if (n < 3)
{
printf("%lld\n", 0);
return 0;
}
LL d = a[0];
for (int i = 0; i < n - 2; i ++) {
d = max(0ll, a[i]);
if (i) pre[i] = pre[i - 1] + d;
else pre[i] = d;
a[i] = 0;
a[i+1] -= d, a[i+2] -= d;
}
for (int i = n - 1; i >= 2; i --)
{
d = max(0ll, b[i]);
if (i != n - 1) bac[i] = bac[i + 1] + d;
else bac[i] = d;
b[i] = 0;
b[i-1] -= d, b[i-2] -= d;
}
LL ans = 0;
ans = bac[2]; // 边界 对前两个使用魔法
ans = min(ans, pre[n - 3]); //边界 对后两个施用魔法
for (int i = 1; i < n - 2; i ++) {
ans = min(ans, pre[i - 1] + bac[i + 2]);
}
printf("%lld\n", ans);
return 0;
}