前言:
- 题解主要参考于
- bilibili牛客官方视频讲解 ——这次由苯环哥讲题
- _Vector_的题解
A - 小红不想做炸鸡块粉丝粉丝题
- 跳过
B - 小红不想做鸽巢原理
思路:
- 首先做到
sum % k
求出之后必定剩下的数量 - 然后,按照颜色的数量,从大到小贪心查找即可
- 若符合,则数量
+1
,否则,忽略。 详情请见代码部分
以下是代码部分
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 10;
int a[N];
int main()
{
int n, k;
cin >> n >> k;
ll sum = 0;
//输入,并求和
for(int i = 1; i <= n; i ++)
cin >> a[i], sum += a[i];
//从小到大排序
sort(a + 1, a + n + 1);
//求剩余小球的数量
ll temp = sum % (ll)k;
//统计可以剩下的颜色数量
int ans = 0;
//按照每种颜色的数量,从大到小遍历
for(int i = n; i >= 1; i --)
{
if(temp <= 0) break;
//如果符合要求,就更新剩余的小球数量
temp -= a[i];
//统计可以剩余的小球颜色种类
ans ++;
}
cout << ans << '\n';
return 0;
}
C&D - 小红不想做完全背包
注意事项:
- 测试数据已经更新。
- 赛时的AC代码,部分错误
思路:
BFS
广度优先搜索- 把每一个可以到达的余数抽象为地图上的一个个点
- 然后用
BFS
遍历最短路径,路径即为所需最少的个数 - 输出点
0
的最短路径是多少
以下是代码部分,代码来源——_Vector_
#include<bits/stdc++.h>
using namespace std;
const int N = 2e3 + 10;
int mp[N];
bool vis[N];
int main()
{
int n, p;
cin >> n >> p;
queue<pair<int, int> > q;
for(int i = 1; i <= n; i ++)
{
int x;
cin >> x;
//把点放进去,并标记为已有
//mp[] == 1 代表地图上此结点存在
//vis[] == 1 代表此结点已有最短路径,且数值为1
if (mp[x % p] == 0)
{
//放入结点(x % p),初始路径为1
q.emplace(x % p, 1);
//标记为已经走过
vis[x % p] = true;
//标记为地图上存在这个结点
mp[x % p] = 1;
}
}
//BFS广度优先搜索
while(!q.empty())
{
int pos = q.front().first;
int num = q.front().second;
//如果在余数为0的时候已经存在数,则跳出
if(!pos)
{
cout << num;
return 0;
}
//如果此地图没有被走过vis[] == false,且存在向这下一步的结点mp[] == 1
for(int i = 0; i < p; i ++)
if(mp[i] == 1 && vis[(pos + i) % p] == 0)
{
//标记为已经走过
vis[(pos + i) % p] = true;
q.emplace((pos + i) % p, num + 1);
}
//队首出队
q.pop();
}
return 0;
}
E - 小红不想做莫比乌斯反演杜教筛求因子和的前缀和
思路:
n m p
都必须为正整数- 规定:
n
为长。m
为宽。p
为高。 - 观察即可得出面积公式
x = n * m + (n + m) * 2 * p
- 由这两个,就可以O(1)求出p, 再进行判断即可
以下是代码部分
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n, m, p, x;
cin >> n >> m >> p >> x;
//ans 记录合法数量
int ans = 0;
//穷举n和m
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= m; j ++)
{
//此时fugai代表了侧面覆盖黄油的面积
//fugai = (i + j) * p * 2
int fugai = x - i * j;
//面积小于0, 不合法
if(fugai <= 0) continue;
int p_2 = (i + j) * 2;
//不能整除(i + j) % 2, 代表p不是整数,不合法
if(fugai % p_2 != 0) continue;
//代表p == 0, 不合法
if(fugai / p_2 == 0) continue;
//求可能的p的值
int v_p = fugai / (i + j) / 2;
//如果v_p合法,则ans ++
if(v_p >= 1 && v_p <= p) ans ++;
}
//输出合法值
cout << ans << '\n';
return 0;
}
F - 小红不想做模拟题
思路:
- 手搓线段树
- 来bilibili牛客竞赛观看视频, 跟着苯环哥哥学习Lazy线段树
以下是代码部分, 代码参考来源——bilibili牛客官方视频讲解
#include <bits/stdc++.h>
using namespace std;
constexpr int N = 1e5 + 10;
int n, q, a[N], b[N];
// 苯环哥的带懒标记的线段树
typedef struct Node{
//a1:为a[]为1的个数
//b1:为b[]为1的个数
//c :为a[] b[]同时为1的个数
int l, r, a1, b1, c;
//两个懒标记
//一个用于 A[]字符串
//一个用于 B[]字符串
int lazy1, lazy2;
}Node;
//线段树空间开四倍,具体可以看 [OI Wiki](https://oi-wiki.org/ds/seg/)网站上的解释
Node Tr[N<<2];
//更新父节点Tr[u]
//用左右 两个 子结点 更新 父结点
void push_up(int u)
{
//u结点 u的左子节点 u的右子节点
//更新a1
Tr[u].a1 = (Tr[u << 1].a1 + Tr[u << 1 | 1].a1);
//更新b1
Tr[u].b1 = (Tr[u << 1].b1 + Tr[u << 1 | 1].b1);
//更新c
Tr[u].c = (Tr[u << 1].c + Tr[u << 1 | 1].c );
}
//线段树的建立
void build(int u, int l, int r)
{
//当递归到树的叶子时,也就是[l, r]的区间只有一个元素时,赋值
if(l == r)
Tr[u] = {l, r, a[l], b[l], a[l] & b[l]};
else
{
Tr[u] = {l, r};
int mid = (l + r) >> 1;
//递归左分支
build(u << 1, l, mid);
//递归右分支
build(u << 1 | 1, mid + 1, r);
//记得更新Tr[u]结点的值
push_up(u);
}
}
//懒标记下放——更新
//用父节点更新左右两个子节点
void push_down(int u)
{
//修改A[]的懒标记
if(Tr[u].lazy1)
{
int lazy = Tr[u].lazy1;
Tr[u << 1].a1 = (Tr[u << 1].r - Tr[u << 1].l + 1);
Tr[u << 1].c = Tr[u << 1].b1;
Tr[u << 1 | 1].a1 = (Tr[u << 1 | 1].r - Tr[u << 1 | 1].l + 1);
Tr[u << 1 | 1].c = Tr[u << 1 | 1].b1;
Tr[u << 1].lazy1 = 1;
Tr[u << 1 | 1].lazy1 = 1;
Tr[u].lazy1 = 0;
}
//修改B[]的懒标记
if(Tr[u].lazy2)
{
int lazy = Tr[u].lazy2;
Tr[u << 1].b1 = (Tr[u << 1].r - Tr[u << 1].l + 1);
Tr[u << 1].c = Tr[u << 1].a1;
Tr[u << 1 | 1].b1 = (Tr[u << 1 | 1].r - Tr[u << 1 | 1].l + 1);
Tr[u << 1 | 1].c = Tr[u << 1 | 1].a1;
Tr[u << 1].lazy2 = 1;
Tr[u << 1 | 1].lazy2 = 1;
Tr[u].lazy2 = 0;
}
}
//线段树的修改
//op == 1, 则修改A[], 否则修改B[]
void modify(int u, int l, int r, int op)
{
//如果当前结点的区间完全包含于被修改区间
if(Tr[u].l >= l && Tr[u].r <= r)
{
//修改后,1的个数恰好等于区间长度
if(op == 1)
{
Tr[u].a1 = Tr[u].r - Tr[u].l + 1;
//A[]都变为1后,A&B就是B中为1的个数了
Tr[u].c = Tr[u].b1;
//懒标记
Tr[u].lazy1 = 1;
}
else
{
Tr[u].b1 = Tr[u].r - Tr[u].l + 1;
Tr[u].c = Tr[u].a1;
Tr[u].lazy2 = 1;
}
return ;
}
//懒标记下放
push_down(u);
//一般情况
int mid = (Tr[u].l + Tr[u].r) >> 1;
//涉及到左分支
if(l <= mid) modify(u << 1, l, r, op);
//涉及到右分支
if(r > mid) modify(u << 1 | 1, l, r, op);
//每次更新结点Tr[u]的状况
push_up(u);
}
//线段树的区间查询
//int ask_interval(int v,int a,int b)//区间查询[a,b]
//{
// if(tree[v].l>=a&&tree[v].r<=b)
// {
// return tree[v].w;
// }
//
// if(tree[v].lazy!=0) downadd(v);
// //if(tree[v].lazy!=-1) downupdate(v);//区间改值用-1
//
// int sum=0;
// int mid=(tree[v].l+tree[v].r)/2;
// if(a<=mid) sum+=ask_interval(v*2,a,b);
// if(b>mid) sum+=ask_interval(v*2+1,a,b);
//
// return sum;
//}
int main ()
{
string A, B;
cin >> n >> A >> B >> q;
int ans = 0;
//字符串转为数组,存储的对应的a[] b[]中
for(int i = 0; i < n; i ++)
{
a[i + 1] = A[i] - '0';
b[i + 1] = B[i] - '0';
}
//建线段树
build(1, 1, n);
while(q --)
{
char op;
int l, r;
cin >> op >> l >> r;
int x = int(op - 'A') + 1;
modify(1, l, r, x);
cout << Tr[1].c << '\n';
}
return 0;
}
G - 小红不想做平衡树
思路:
- 建议直接观看——bilibili牛客官方视频讲解
- 首先,原本就是升序的连续区间,设其长度为n
- 易得它的好数数量为(n + n - 1 + n - 2 + …… + 2 + 1)。
- 一段降序的连续区间,设其好数组数量为
sum
, 长度为len
- 则其本身可以组成的好数组数量为
(len - 1) * len / 2 + len
- 其中
len * (lne - 1) / 2
实际上是在这段区间范围内,任取两个端点组合,求出组合数 +len
为每个好数组的长度为1时的数量之和
- 对于降序区段,它可以和升序区间组合出更多好数组。共有三种组合方式
- 只和前段的升序区间组合
- 要求:降序区间的所有元素均大于前段升序区间
- 只和后段的升序区间组合
- 要求:降序区间的所有元素均小于后段升序区间
- 可以和后段或者前段的升序区间组合
- 同时满足1&2的要求
- 只和前段的升序区间组合
之后就可以得出,具体的线段翻转要求的讲解,可以观看牛客视频
以下是代码部分——bilibili牛客官方视频讲解
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
int n, a[N];
ll pre[N], suf[N], ans;
void calc(int l, int r)
{
for(int i = l; i <= r; i ++)
{
//此降序区段大于左边的升序区段的最大值
if(a[i] <= a[l - 1] || l == 1) break;
//加上它本身全都组成的好数组数量
//好数组数量为 (n + n-1 + n-2 + …… + 2 + 1)
else ans += l - pre[l];
}
//因为所选取的端点的问题,减去多算的一组
ans -= l - pre[l];
for(int i = r; i >= l; i --)
{
//此降序区段小于左边的升序区段的最大值
if(a[i] >= a[r + 1] || r == n) break;
//加上它本身全都组成的好数组数量
//好数组数量为 (n + n-1 + n-2 + …… + 2 + 1)
else ans += suf[r] - r;
}
//因为所选取的端点的问题,减去多算的一组
ans -= suf[r] - r;
int len = r - l + 1;
//C(2, len),len的点中,任取两个端点的组合数
ans += (len - 1) * len / 2;
//如果降序数组与前后均可相连
//则可以选取的不同端点数为此乘积
if(l > 1 && r < n && a[r] > a[l - 1] && a[r + 1] > a[l])
ans += (suf[r] - r) * (l - pre[l]);
}
int main ()
{
cin >> n;
for(int i = 1; i <= n; i ++)
{
cin >> a[i];
//升序
if(i > 1 && a[i] > a[i - 1])
pre[i] = pre[i - 1];//pre[i]代表升序区段的左断点
else
pre[i] = i;
//一段连续的升序区间,设它的长度为n
//好数组数量为 (n + n-1 + n-2 + …… + 2 + 1)
//求出了原本升序区间的所有好数组的数量得出的好数数量
//以及所有长度为1的好数组的和
ans += i - pre[i] + 1;
}
for(int i = n; i; i --)
{
//升序
if(i < n && a[i] < a[i + 1])
suf[i] = suf[i + 1];//suf[i]代表升序区段的右断点
else suf[i] = i;
}
//双指针
for(int i = 1; i < n; i ++)
{
int j = i;
//获得最大降序区间
while(j < n && a[j] > a[j + 1]) j ++;
if(j > i) calc(i, j);
//更新i值
i = j;
}
cout << ans << '\n';
return 0;
}