蓝桥杯13
P8779 [蓝桥杯 2022 省 A] 推导部分和题目形貌
对于一个长度为 N N N 的整数数列 A 1 , A 2 , ⋯ A N A_{1}, A_{2}, \cdots A_{N} A1,A2,⋯AN，小蓝想知道下标 l l l 到 r r r 的部分和 ∑ i = l r A i = A l + A l + 1 + ⋯ + A r \sum\limits_{i=l}^{r}A_i=A_{l}+A_{l+1}+\cdots+A_{r} i=l∑rAi=Al+Al+1+⋯+Ar 是多少?
然而，小蓝并不知道数列中每个数的值是多少，他只知道它的 M M M 个部分和的值。其中第 i i i 个部分和是下标 l i l_{i} li 到 r i r_{i} ri 的部分和 ∑ j = l i r i = A l i + A l i + 1 + ⋯ + A r i \sum_{j=l_{i}}^{r_{i}}=A_{l_{i}}+A_{l_{i}+1}+\cdots+A_{r_{i}} ∑j=liri=Ali+Ali+1+⋯+Ari, 值是 S i S_{i} Si 。
输入格式
第一行包含 3 个整数 N 、 M N 、 M N、M 和 Q Q Q。分别代表数组长度、已知的部分和数量 和询问的部分和数量。
接下来 M M M 行，每行包含 3 3 3 个整数 l i , r i , S i l_{i}, r_{i}, S_{i} li,ri,Si。
接下来 Q Q Q 行，每行包含 2 2 2 个整数 l l l 和 r r r，代表一个小蓝想知道的部分和。
输出格式
对于每个询问, 输出一行包含一个整数体现答案。假如答案无法确定, 输出 UNKNOWN。
https://i-blog.csdnimg.cn/direct/122a746022ec4b1a8d492a0c84d5b813.png
#include <bits/stdc++.h>
using namespace std;
#define asd(i,a,b) for(int i=a;i<=b;i++)
#define int long long
const int inf=0x3f3f3f3f;
const int N = 1e6 + 5;
int n,m,q,pre,sum;
int root(int x){
if(x==pre)return x;
int t=root(pre);
sum+=sum];
pre=t;
return pre;
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin>>n>>m>>q;
asd(i,1,n)pre=i;
while(m--){
int l,r,s;
cin>>l>>r>>s;
l--;
int fl=root(l),fr=root(r);
if(fl==fr)continue;
pre=fr;
sum=-s-sum+sum;
}
while(q--)
{
int l,r;cin>>l>>r;l--;
if(root(l)!=root(r))cout<<"UNKNOWN"<<endl;
else cout<<sum-sum<<endl;
}
return 0;
}
P8773 [蓝桥杯 2022 省 A] 选数异或
题目形貌
给定一个长度为 n n n 的数列 A 1 , A 2 , ⋯ , A n A_{1}, A_{2}, \cdots, A_{n} A1,A2,⋯,An 和一个非负整数 x x x, 给定 m m m 次查询, 每次询问能否从某个区间 [ l , r ] 中选择两个数使得他们的异或即是 x x x 。
输入格式
输入的第一行包含三个整数 n , m , x n, m, x n,m,x 。
第二行包含 n n n 个整数 A 1 , A 2 , ⋯ , A n A_{1}, A_{2}, \cdots, A_{n} A1,A2,⋯,An。
接下来 m m m 行，每行包含两个整数 l i , r i l_{i}, r_{i} li,ri 体现询问区间 [ l i , r i ] \left 。
输出格式
对于每个询问, 假如该区间内存在两个数的异或为 x x x 则输出 yes, 否则输出 no。
https://i-blog.csdnimg.cn/direct/f608276400da41e6b203c5b8a1e4cfb9.png
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int dp, n, m, x;
int main() {
cin >> n >> m >> x;
unordered_map<int, int> last;
for(int i=1; i<=n; i++) {
int a; cin >> a;
dp = max(dp, last);
//这句应该放到后面， 否则当x=0时会不正确(当x等于0时dp = i, 但是要选两个不同位置的数)
//更正于2023/01/01
last = i;
}
while (m -- ) {
int l, r; cin >> l >> r;
cout << (dp >= l ? "yes" : "no") << endl;
}
return 0;
}
https://i-blog.csdnimg.cn/direct/6e59751444e64c35be8da714bb4655fa.png
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
const int N=1000010; // 定义最大字符数
char s; // 存储输入的字符串
int l, r; // 分别存储每个字符的前驱和后继位置
int st; // 标记数组，用于标记字符是否被删除
vector<int> q, w; // q表示备删的元素，w表示待删元素
// 插入函数，用于将待删除的元素加入w中
void insert(int temp) {
if (st == 0) { // 如果该元素未被标记为删除
st = 1; // 标记为删除
w.push_back(temp); // 加入待删除列表
}
}
// filterfun函数，用于找到待删除的边缘字符
void filterfun() {
w.clear(); // 清空待删除列表
for (int t : q) { // 遍历备删元素
int a = l, b = t, c = r; // 获取当前字符及其前驱和后继
if (s == s && s != s && s != '#') { // 如果当前字符是边缘字符
insert(b); // 标记为待删除
insert(c); // 标记为待删除
}
if (s != s && s == s && s != '#') { // 如果当前字符是边缘字符
insert(a); // 标记为待删除
insert(b); // 标记为待删除
}
}
}
int main() {
scanf("%s", s + 1); // 读取输入的字符串
int n = strlen(s + 1); // 获取字符串长度
s = '#', s = '#'; // 在字符串两端添加特殊字符'#'作为边界
for (int i = 1; i <= n; i++) { // 初始化双链表
l = i - 1;
r = i + 1;
q.push_back(i); // 初始化备删元素
}
r = 1; // 设置第一个字符的后继
l = n; // 设置最后一个字符的前驱
while (1) { // 循环直到没有边缘字符可以删除
filterfun(); // 找到待删除的边缘字符
if (w.empty()) break; // 如果没有待删除的字符，退出循环
q.clear(); // 清空备选删除列表
for (int t : w) { // 遍历待删除的字符
int a = l, b = t, c = r; // 获取当前字符及其前驱和后继
if (a != 0 && st == 0 && (q.empty() || a != q.back())) q.push_back(a); // 更新备选删除列表
if (c != n + 1 && st == 0) q.push_back(c); // 更新备选删除列表
r = c; // 更新双链表
l = a; // 更新双链表
}
}
if (r == n + 1) puts("EMPTY"); // 如果最终字符串为空，输出"EMPTY"
else { // 否则输出最终的字符串
for (int i = r; i != n + 1; i = r)
cout << s;
}
return 0;
}
https://i-blog.csdnimg.cn/direct/482eb73f12674057beb3f61224158248.png
//本题考查二分算法,核心是找到第M大的数
//给出的n组数据本质上是n个递减的等差数列,首项为A,公差为B
//可以将这n个等差数列展开,发现核心就是从这些等差数列中找到M个最大的数并累加
//因此可以用二分算法找到数列中第M大的数x,然后遍历所有的等差数列,将所有大于等于x的数累加即可
//附:本题若暴力求解可以使用优先队列,不断令当前最大数出队并累加,递减后再次入队
//如果使用暴力解法可以较快地通过5个测试点,但后5个会超时
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
ll n, m;
ll A,B;
bool check(ll x)//验证第M大的数能否是x(求等差数列中有几个数大于等于x)
{
ll cnt = 0;
for(int i = 1; i <= n; i++)
{
if(A < x)continue;
int k = (A - x) / B;
cnt += k + 1;
}
if(cnt >= m)return true;//大于等于x的数的数量不少于m个,返回true
else return false;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>A>>B;
int left=0,right=1e6+10,x=0;//x为第M大的数
while(left<=right)//开始二分
{
int mid = (left + right) >> 1;
if(check(mid))//等差数列中不小于mid的元素的数量大于等于m,说明mid选小了
{
x=mid;//记录之
left=mid+1;//扩大左边界
}
else right=mid-1;//否则缩小右边界
}
//经过以上循环,第M大数为x,接下来只需要求解数列中所有大于等于x的数的和即可
//此处要注意一个细节,那就是数列中可能存在多个等于x的数
//因此不能直接累加数列中所有大于等于x的数,否则可能出现多次累加等于x的数,总次数超过m
//比较好的做法是只累加大于x的数,然后计算还剩下几个等于x的数没有累加,累加上即可
ll cnt=0,sum=0;//大于x的数字个数为cnt,数字之和为sum
for(int i=1;i<=n;i++)//遍历每个等差数列
{
if(A<x)continue;//第一个数就小于x,后面不可能大于x,直接跳过
int k=(A-x)/B;//计算该数列中有几个数大于x
if(k*B != (A - x))k++;//k向上取整
sum=sum+(A+A-(k-1)*B)*k/2;//等差数列求和公式
cnt=cnt+k;//记录已经计算了几个数
}
sum+=(m-cnt)*x;//最终要累加m个数,已经累加了cnt个比x大的数,还应累加m-cnt个等于x的数(细节)
cout<<sum<<endl;
return 0;
}
P8787 [蓝桥杯 2022 省 B] 砍竹子
题目形貌
这天，小明在砍竹子，他面前有 n n n 棵竹子排成一排，一开始第 i i i 棵竹子的高度为 h i h_{i} hi.
他以为一棵一棵砍太慢了，决定利用邪术来砍竹子。邪术可以对连续的一段相同高度的竹子利用，假设这一段竹子的高度为 H H H，那么利用一次邪术可以把这一段竹子的高度都变为 ⌊ ⌊ H 2 ⌋ + 1 ⌋ \left\lfloor\sqrt{\left\lfloor\frac{H}{2}\right\rfloor+1}\right\rfloor ⌊⌊2H⌋+1 ⌋, 其中 ⌊ x ⌋ \lfloor x\rfloor ⌊x⌋ 体现对 x x x 向下取整。小明想知道他最少利用多少次邪术可以让全部的竹子的高度都变为 1 1 1。
输入格式
第一行为一个正整数 n n n，体现竹子的棵数。
第二行共 n n n 个空格分开的正整数 h i h_{i} hi，体现每棵竹子的高度。
题解1
题解2
P8784 [蓝桥杯 2022 省 B] 积木画
题目形貌
小明最近迷上了积木画，有这么两种范例的积木，分别为 I I I 型（巨细为 2 2 2 个单位面积) 和 L L L 型 (巨细为 3 3 3 个单位面积):
https://i-blog.csdnimg.cn/img_convert/3e5ea9aed3124bb02703fb8c1ca77806.jpeg
同时，小明有一块面积巨细为 2 × N 2 \times N 2×N 的画布，画布由 2 × N 2 \times N 2×N 个 1 × 1 1 \times 1 1×1 地域构成。小明需要用以上两种积木将画布拼满，他想知道总共有多少种不同的方式? 积木可以任意旋转，且画布的方向固定。
输入格式
输入一个整数 N N N，体现画布巨细。
输出格式
输出一个整数体现答案。由于答案大概很大，以是输出其对 1000000007 1000000007 1000000007（即 1 0 9 + 7 10^9+7 109+7）取模后的值。
题解
P8774 [蓝桥杯 2022 省 A] 爬树的甲壳虫
题目形貌
有一只甲壳虫想要爬上一颗高度为 n n n 的树，它一开始位于树根, 高度为 0 0 0，当它实验从高度 i − 1 i-1 i−1 爬到高度为 i i i 的位置时有 P i P_{i} Pi 的概率会掉回树根, 求它从树根爬到树顶时, 经过的时间的期望值是多少。
输入格式
输入第一行包含一个整数 n n n 体现树的高度。
接下来 n n n 行每行包含两个整数 x i , y i x_{i}, y_{i} xi,yi, 用一个空格分隔，体现 P i = x i y i P_{i}=\frac{x_{i}}{y_{i}} Pi=yixi 。
输出格式
输出一行包含一个整数体现答案，答案是一个有理数，请输出答案对质数 998244353 998244353 998244353 取模的结果。其中有理数 a b \frac{a}{b} ba 对质数 P P P 取模的结果是整数 c c c 满足 0 ≤ c < P 0 \leq c<P 0≤c<P 且 c ⋅ b ≡ a ( m o d P ) c \cdot b \equiv a\pmod P c⋅b≡a(modP) 。
题解1
题解2
P8775 [蓝桥杯 2022 省 A] 青蛙过河
题目形貌
小青蛙住在一条河滨，它想到河对岸的学校去学习。小青蛙计划经过河里的石头跳到对岸。
河里的石头排成了一条直线，小青蛙每次跳跃必须落在一块石头或者岸上。不外，每块石头有一个高度，每次小青蛙从一块石头起跳，这块石头的高度就会降落 1 1 1，当石头的高度降落到 0 0 0 时小青蛙不能再跳到这块石头上（某次跳跃后使石头高度降落到 0 0 0 是允许的)。
小青蛙一共需要去学校上 x x x 天课，以是它需要往返 2 x 2x 2x 次。当小青蛙具有一个跳跃能力 y y y 时，它能跳不超过 y y y 的间隔。
请问小青蛙的跳跃能力至少是多少才能用这些石头上完 x x x 次课。
输入格式
输入的第一行包含两个整数 n , x n, x n,x, 分别体现河的宽度和小青蛙需要去学校的天数。请注意 2 x 2x 2x 才是实际过河的次数。
第二行包含 n − 1 n-1 n−1 个非负整数 H 1 , H 2 , ⋯ , H n − 1 H_{1}, H_{2}, \cdots, H_{n-1} H1,H2,⋯,Hn−1, 其中 H i > 0 H_{i}>0 Hi>0 体现在河中与 小青蛙的家相距 i i i 的地方有一块高度为 H i H_{i} Hi 的石头， H i = 0 H_{i}=0 Hi=0 体现这个位置没有石头。
输出格式
输出一行, 包含一个整数, 体现小青蛙需要的最低跳跃能力。
题解
P8776 [蓝桥杯 2022 省 A] 最长不降落子序列
题目形貌
给定一个长度为 N N N 的整数序列： A 1 , A 2 , ⋯ , A N A_{1}, A_{2}, \cdots, A_{N} A1,A2,⋯,AN。现在你有一次时机，将其中连续的 K K K 个数修改成任意一个相同值。请你计算如何修改可以使修改后的数列的最长不降落子序列最长，请输出这个最长的长度。
最长不降落子序列是指序列中的一个子序列，子序列中的每个数不小于在它之前的数。
输入格式
输入第一行包含两个整数 N N N 和 K K K 。
第二行包含 N N N 个整数 A 1 , A 2 , ⋯ , A N A_{1}, A_{2}, \cdots, A_{N} A1,A2,⋯,AN 。
输出格式
输出一行包含一个整数体现答案。
题解1
题解2
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5+9;
int n,k,m,a,b,dp,t;
void updata(int o,int l,int r,int pos,int val){
t=max(t,val);
if(l==r)return;
int mid=(l+r)>>1;
if(pos<=mid)updata(2*o,l,mid,pos,val);
else updata(2*o+1,mid+1,r,pos,val);
}
int getmax(int o,int l,int r,int nl,int nr){
if(l==nl&&r==nr)return t;
int mid=(l+r)>>1;
if(mid>=nr)return getmax(2*o,l,mid,nl,nr);
else if(mid<nl)return getmax(2*o+1,mid+1,r,nl,nr);
else return max(getmax(2*o,l,mid,nl,mid),getmax(2*o+1,mid+1,r,mid+1,nr));
}
// 1 2 3 4 5 6 7 8
void solve(){
cin>>n>>k;
for(int i=1;i<=n;i++)cin>>a,b=a;
// 离散化
sort(b+1,b+n+1);
m=unique(b+1,b+n+1)-b-1;
for(int i=1;i<=n;i++)a=lower_bound(b+1,b+m+1,a)-b;
for(int i=1;i<=n;i++){
dp=getmax(1,1,m,1,a)+1;
updata(1,1,m,a,dp);
}
int ans=0;
memset(t,0,sizeof t);
for(int i=n;i>k;i--){
ans=max(ans,dp+k-1+getmax(1,1,m,a,m)+1);
int tem=getmax(1,1,m,a,m)+1;
updata(1,1,m,a,tem);
}
ans=max(ans,k+getmax(1,1,m,a,m));
cout<<ans<<'\n';
}
// 1 2 3 ... i-k i-k+1 i-k+2 i-k+3 ... i ...
int main(){
ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
int q=1;
//cin>>q;
while(q--){
solve();
}
return 0;
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]