xp04 - day03
2025-08-14 21:00:26
发布于：浙江
171阅读
0回复
0点赞
⭐知识 (离散化)
原地去重
#include<bits/stdc++.h>
using namespace std;
const int N = 500010;
long long a[N],b[N];
int main() {
int n;
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> a[i];
b[i] = a[i];
}
sort(b + 1, b + n + 1);
int m = 1;
for(int i=2;i<=n;i++)if(b[i]!=b[m])b[++m] = b[i];
for(int i = 1; i <= n; i++) {
int idx = lower_bound(b+1,b+1+m,a[i]) - b;
cout << idx << " ";
}
return 0;
}
树状数组 单点修改 区间查询
树状数组 区间修改，单点查询
逆序对 离散化 普通前缀和
单调栈
发射站
#include<bits/stdc++.h>
using namespace std;
long long a[1000010],b[1000010],ans[1000010];
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i]>>b[i];
stack<int> s;
for(int i=1;i<=n;i++){
//栈顶元素在右边找到第一个比他大的元素
while(s.size() && a[s.top()] < a[i]){
ans[i] += b[s.top()];
s.pop();
}
s.push(i);
}
while(s.size())s.pop();
for(int i=n;i>=1;i--){
//栈顶元素在左边找到第一个比他大的元素
while(s.size() && a[s.top()] < a[i]){
ans[i] += b[s.top()];
s.pop();
}
s.push(i);
}
long long mx = 0;
for(int i=1;i<=n;i++)mx = max(mx,ans[i]);
cout<<mx;
return 0;
}
玉蟾宫
// 矩形土地 面积最大
// 5 6
// R F F F F F
// F F F F F F
// R R R F F F
// F F F F F F
// F F F F F F
// 0 1 1 1 1 1
// 1 2 2 2 2 2
// 0 0 0 3 3 3
// 1 1 1 4 4 4
// 2 2 2 5 5 5
#include<bits/stdc++.h>
using namespace std;
int n,m;
char g[1010][1010];
int a[1010],l[1010],r[1010];
int main(){
cin>>n>>m;
long long ans = 0;
for(int i=1;i<=n;i++){
//输入，并且处理每一行的 a 地基数组
for(int j=1;j<=m;j++){
cin>>g[i][j];
if(g[i][j]=='R')a[j] = 0;
else a[j]++;
//cout<<a[j]<<" ";
}
//cout<<endl;
stack<int> s;
for(int j=1;j<=m;j++)r[j] = m;//假设所有点都可以扩散到最右边
for(int j=1;j<=m;j++){
while(s.size() && a[s.top()]>a[j]){
r[s.top()] = j - 1;
s.pop();
}
s.push(j);
}
while(s.size())s.pop();
for(int j=1;j<=m;j++)l[j] = 1;//假设所有点都可以扩散到最左边
for(int j=m;j>=1;j--){
while(s.size() && a[s.top()]>a[j]){
l[s.top()] = j + 1;
s.pop();
}
s.push(j);
}
for(int j=1;j<=m;j++){
long long len = (r[j] - l[j] + 1) * a[j];
ans = max(ans,len);
}
}
cout<<ans*3;
return 0;
}
爆米花 01DFS
#include<bits/stdc++.h>
using namespace std;
char g[20][20];
int a[20],ans = 1e9;
int n,m;
int main(){
cin>>n>>m;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
cin>>g[i][j];
// n = 3 000 - 111 0-7 2^3 - 1
// n = 4 0000 - 1111 0-15 2^4 - 1
// n 2^n - 1
//枚举所有的 01状态了
for(int i=0;i<1<<n;i++){
for(int j=0;j<m;j++)a[j] = 0;//所有爆米花口味我都没选
int cnt = 0;//摊位数量
for(int j=0;j<n;j++){
if(i>>j&1==1){//如果当前二进制这一位是1，表示当前摊位我选择了
cnt++;//摊位数量++
//把摊位当中所有的口味都记录一下
for(int k=0;k<m;k++){
if(g[j][k]=='o')a[k]++;
}
}
}
bool flag = true;
for(int j=0;j<m;j++){
if(a[j]==0){
flag = false;
}
}
if(flag)ans=min(ans,cnt);
}
cout<<ans;
return 0;
}
有帮助，赞一个