2026年10月5日（南山s day5）
2026-10-05 17:17:14
发布于：广东
17阅读
0回复
0点赞
第一题
//单调栈
//接雨水
//单调队列[]
// r
//1 4 5 2 3 6 7 5 4
//1 2 3 6 7 5
// 右端点为3：3
// 右端点为5：
// 3 5
// 右端点为3：[1,3][2,3][3,3]
// 3 3 3
// 右端点为4：
// 3 3 3 4
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
#define ll long long
ll a[N],mod=1e9+7;;
void solve(){
int n;cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
//单调栈，存储下标，且下标对应的值一定是单调递增的
stack<int>stk;
stk.push(0);//防止被踢出，导致栈空
ll ans=0,sum=0;//sum:累计当前栈产生的贡献。
for(int i=1;i<=n;i++){
//1 2 3 4 5 6 7 8 9
//1 4 5 2 3 6 6 5 4
//1 2 3 5
while(a[stk.top()]>=a[i]){
int inx=stk.top();stk.pop();
sum-=(inx-stk.top())*a[inx];
}
sum+=(i-stk.top())*a[i];
ans=(ans+sum)%mod;
stk.push(i);
}
cout<<ans<<endl;
}
int main(){
int t=1;
// cin>>t;
while(t--){
solve();
}
}
第二题
//对于n*m的地图
//总共有以下几种地形
//1.#：墙
//2..：空地
//3.k:钥匙 （可以拾取并累计，固定位置只能捡一次）
//4.d:门 （消耗一把钥匙打开）
// .kk..s...dd.....t
// vis[x][y][1<<10];//分层图，图上DP
// //将钥匙的状态进行压缩；
// dfs(int x,int y,int key_num){
// if(vis[x][y][key_num])return ;
// dfs(nx,ny,key_num);
// }
#include<bits/stdc++.h>
using namespace std;
const int N=100+10;
#define ll long long
int n,m;
int vis[N][N][1<<10];
char graph[N][N];
struct Node{
int x,y,key;//坐标，key:钥匙情况
};
int dx[]={0,0,1,-1};
int dy[]={-1,1,0,0};
void solve(){
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>graph[i][j];
queue<Node>que;
que.push({1,1,0});
vis[1][1][0]=1;
int ans=1e9;
while(que.size()){
auto cur=que.front();que.pop();
int x=cur.x,y=cur.y,key=cur.key;
if(x==n&&y==m)ans=min(ans,vis[x][y][key]-1);//更新答案
for(int i=0;i<4;i++){
int nx=x+dx[i],ny=y+dy[i],nkey=key;
if(1<=nx&&nx<=n&&1<=ny&&ny<=m);else continue;
if(graph[nx][ny]=='#')continue;
if('a'<=graph[nx][ny]&&graph[nx][ny]<='z')
nkey|=(1<<(graph[nx][ny]-'a'));//拿上钥匙
if('A'<=graph[nx][ny]&&graph[nx][ny]<='Z'&&
((nkey>>(graph[nx][ny]-'A'))&1)==0)//判断如果是门，且没有钥匙
continue;
if(vis[nx][ny][nkey])continue;
vis[nx][ny][nkey]=vis[x][y][key]+1;//标记位置，并记录答案
que.push({nx,ny,nkey});
}
}
if(ans==1e9)cout<<-1<<endl;
else cout<<ans<<endl;
}
int main(){
int t=1;
// cin>>t;
while(t--){
solve();
}
}
第三题
//40->2^40 int
//3e8-1e9 (1e8)
//40-> 20 20
//int a[3e7]
//2^20->1e6
//10 5[1,2,3,4,5] 5[6,7,8,9,0]
//[1,2,8,9]
//1011 ->0100
//1001 0110
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
#define ll long long
ll a[N],mod=998244353;
vector<ll>vec1,vec2;
void run(vector<ll>&arr,vector<ll>&vec){
vec.push_back(0);
for(auto cur:arr){
for(int i=0,len=vec.size();i<len;i++){
vec.push_back(vec[i]^cur);
}
}
sort(vec.begin(),vec.end());
}
ll count(vector<ll>&vec,ll x){//统计数组中x出现的个数
return upper_bound(vec.begin(),vec.end(),x)-
lower_bound(vec.begin(),vec.end(),x);
}
void solve(){
ll n,k;cin>>n>>k;
vector<ll>arr;
for(int i=1;i<=n;i++){
string s;cin>>s;
ll skill=0;
for(auto c:s)skill=((skill<<1)|(c&1));
arr.push_back(skill);
if(arr.size()>n/2){
run(arr,vec1);
arr.clear();
}
}
run(arr,vec2);
ll full=(1LL<<k)-1;//技能全部拿到的情况。
ll ans=0;
// for(auto cur:vec1)cout<<cur<<' '<<endl;
// for(auto cur:vec2)cout<<cur<<' '<<endl;
for(auto cur:vec1){
// cout<<cur<<' '<<cur^full<<' '<<count(vec2,cur^full)<<endl;
ans+=count(vec2,cur^full);
ans%=mod;
}
cout<<ans<<endl;
}
int main(){
int t=1;
// cin>>t;
while(t--){
solve();
}
}
第四题
//给定n个区间
//m个监控摄像头，问最少保留多少个区间，才能将m个摄像头全覆盖
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
#define ll long long
ll a[N];
//d=b+a*(p-x);
//d<=b+a*p-a*x;
//p=(d-b+a*x)/a;//右端可以得到的最大值
int n,m,k;
struct Node{//class
static ll d;//
ll x,a,b;
ll cal_d(ll p){//计算贡献d
return b+a*abs(x-p);
}
ll cal_mx_r(ll d){//在d的情况下，最大右端取值
return (d-b+a*x)/a;
}//求小于等于x的最后一个值/
bool operator<(const Node &other)const{
return (d-b+a*x)/a<
(other.d-other.b+other.a*other.x)/other.a;
}
};
ll Node::d=0;//静态类型初始化
Node node[N];
ll check(ll d){
Node::d=d;
sort(node+1,node+n+1);
ll last_inx=0,cnt=0;//最远中继站的下标,cnt表示当前最少需要的中继站个数
for(int i=1;i<=n;i++){
//第一次，或者当前监控的中继站不满足条件。
if(last_inx==0||node[i].cal_d(a[last_inx])>d){
last_inx=upper_bound(a+1,a+m+1,node[i].cal_mx_r(d))-a;
if(last_inx==0)return 1e18;//在d情况下没找到合适的中继站
last_inx-=1;
cnt++;
if(node[i].cal_d(a[last_inx])>d)return 1e18;//找到的中继器位置不符合
}else{
continue;
}
}
return cnt;
}
void solve(){
cin>>n>>m>>k;
for(int i=1;i<=n;i++)cin>>node[i].x>>node[i].a>>node[i].b;
for(int i=1;i<=m;i++)cin>>a[i];
ll l=0,r=1e18,ans,c;
while(l<=r){
ll mid=(l+r)/2;
ll res=check(mid);
if(res<=k){
ans=mid,c=res;
r=mid-1;
}else{
l=mid+1;
}
}
cout<<ans<<' '<<c<<endl;
}
int main(){
int t=1;
// cin>>t;
while(t--){
solve();
}
}
这里空空如也
有帮助，赞一个