2024.6.2 【明霄升海平，飞彩镌流年。】
Sunday 四月廿六
A. 矩形覆盖
题目描述
有N个矩形，矩形的底边边长为1，且均在X轴上，高度给出，第i个矩形的高为h[i]，求最少需要几个矩形才能覆盖这个图形。
例如h = [3, 2, 4, 2]的图形如下：
image
容易发现，只需要3个矩形就能覆盖这个图形。
输入格式
第一行一个整数N。接下来1行包含N个正整数，为h[i]。
输出格式
输出一个整数表示最少需要几个矩形能覆盖这个图形。
样例输入
10
2 3 2 4 2 1 3 4 3 2
样例输出
7
数据规模与约定
对于所有数据，N<=100000，h[i] <= 100。
对于部分数据，N<=10；
对于部分数据，N<=100；
对于部分数据，N<=1000；
对于部分数据，h[i] <= 10；
//2024.6.2
//by white_ice
#include<bits/stdc++.h>
#define itn int
using namespace std;
const int oo = 10000009;
int nk;
int stk[oo];
itn top;
int num;
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin >> nk;
for (int i=1;i<=nk;i++){
int x;
cin >> x;
while (stk[top]>x)
top--;
if (stk[top]!=x){
stk[++top] = x;
num++;
}
}
cout << num;
return 0;
}
考虑逐行消去，
使用栈维护每列高度。
最后形成单调栈。
B. 无敌的妹子2
土豪无敌有很多相机，因为需要秀相机，所以需要拍很多妹纸，现在，无敌招募了n只妹纸，从1到n编号摆在架子上。现在无敌要给妹纸穿各种衣服来增加妹纸的美丽值（由于无敌很正直，他懒得把妹纸的衣服卸下来，只会不停地给妹纸穿衣服（妹纸：热出翔）
他经常会把某个让他很不爽的区间内的妹纸全部替换掉；或者给某个区间内的妹纸都穿上某种衣服。
有时候无敌要试下某个相机，无敌就会随手在架子上的某个区间内找到最美丽的妹纸（一般是XXX）。
有时候会用些镜头歪斜的相机(都是小叶子给搞歪的)拍照，无敌为了防止美丽的妹纸（一般是XXX）生他的气，不敢乱拍美丽的妹纸，就只好随手在架子上的某个区间内找到最ugly的妹纸。
当然，还有时候无敌要给小叶子炫自己的妹纸，就会随手抱出在架子上的某个区间内的妹纸，并计算她们美丽值的和。
输入格式
第一行输入妹纸数n和操作数m
第二行n个数，表示妹纸自身的美丽值ai（这时候还没进行操作）
接下来m行，每行有四个数或五个数，c，dir，ql，qr，(v) (表示询问时，一行只有四个数，表示修改时，一行有五个数)
第一个数c若为1，表示询问：
第二个数dir若为1，表示无敌要对小叶子炫妹子，输出区间[ql,qr]内妹纸美丽值的总和
第二个数dir若为2，表示无敌只能用逗逼的镜头，输出区间[ql,qr]内最ugly的妹纸的美丽值
第二个数dir若为3，表示无敌试相机，输出区间[ql,qr]内最美丽的妹纸的美丽值
第一个数c若为2，表示修改：
第二个数dir若为1，表示无敌要给区间[ql,qr]内的妹纸都穿上一件美丽值为v的衣服
第二个数dir若为2，表示无敌要把区间[ql,qr]内的妹纸全部替换成美丽值为v的妹纸
输出格式
对于每个询问，输出一行对应的信息
样例输入
10 15
27 12 57 80 24 64 96 81 18 45
1 3 9 9
1 1 3 10
1 2 5 7
2 2 1 8 79
1 1 1 4
2 2 5 8 42
2 1 1 5 15
2 1 2 5 72
1 1 2 2
2 1 1 5 35
2 2 10 10 57
1 1 5 5
1 3 5 8
2 1 8 8 78
2 2 5 5 84
样例输出
18
465
24
316
166
164
164
数据规模与约定
n<=1000000,m<=100000
0<=v,ai<=10000
保证所有数据在int范围内
对于10%的数据，n,m<=10（数据十分有梯度！）
怎么都打不对的线段树板子罢了
C. 小奇的数列
题目描述
小奇总是在数学课上思考奇怪的问题。
给定一个长度为n的数列，以及m次询问，每次给出三个数l，r和P，询问(a[l'] + a[l'+1] + ... + a[r']) mod P的最小值。
其中l <= l' <= r' <= r。
即模意义下的区间子串和最小值。
输入格式
第一行包含两个正整数n和m，表示数列的长度和询问的个数。
第二行为n个整数，为a[1]..a[n]。
接下来m行，每行三个数l，r和P，代表一次询问。
输出格式
对于每次询问，输出一行一个整数表示要求的结果
样例输入
4 2
8 15 9 9
1 3 10
1 4 17
样例输出
2
1
数据规模与约定
对于20%的数据n<=100，m<=100，p<=200
对于40%的数据n<=200，m<=1000，p<=500
对于70%的数据n<=100000，m<=10000，p<=200
对于100%的数据n<=500000，m<=10000，p<=500，1<=a[i]<=10^9
//2024.6.2
//by white_ice
#include <bits/stdc++.h>
constexpr int oo = 500005;
#define itn int
using namespace std;
#define ll long long
int n,m,a[oo];
ll sum[oo];
bool e[500002];
ll min(ll a,ll b){
if(a<b) return a;
return b;
}
int main(){
cin >> n >> m;
for(itn i=1;i<=n;i++)
cin >> a[i];
int l,r,p;
while(m--){
cin >> l >> r >> p ;
if(r-l+1>p){
cout << "0" << endl;
continue;
}
for(itn i=1;i<=p;i++)
e[i]=0;
e[0]=1;
sum[l-1]=0;
ll ans= 1 << 30;
for(int i=l;i<=r;i++){
sum[i]=(sum[i-1]+a[i])%p;
for(int j=sum[i];j>=0;j--){
if(e[j]){
ans=min(ans,sum[i]-j);
break;
}
}
if(ans==0)
break;
e[sum[i]]=1;
}
cout << ans << endl;
}
return 0;
}
使用前缀和能拿到不少分，
如果再加一个关于取到0就跳出的判断得分将更多。
这里使用区间前缀和，
维护每次的查询需求。
使复杂度变得很好看。
标签：输出,2024.6,int,无敌,妹纸,美丽,区间 From： https://www.cnblogs.com/white-ice/p/18227502