星爷杯

25-4-6 蓝桥杯模拟

A

用二分写的，0pts。

没有根据题目给的条件分析出同余的式子.

即区间前缀和用s[r]-s[l-1]表示，则区间和是k的倍数，可以得出，s[r]与s[l-1]在模k下同余。

细节：

开long long，注意在余数为零的时候，当前端点作为区间右端点也算。所以初始化cnt[0]=1。

#include<bits/stdc++.h>

using namespace std;
#define int long long 

typedef pair<int,int> pii;
const int N=1e5+10;
int a[N],sum[N];
int cnt[N];

signed main() {
  ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

  int n,k;
  cin>>n>>k;

  for(int i=1;i<=n;i++){
    cin>>a[i];
    sum[i]=sum[i-1]+a[i];
  }
  cnt[0]=1;
  for(int i=1;i<=n;i++){
    cnt[sum[i]%k]++;
  }

  int res=0;
  for(int i=0;i<k;i++){
    res+=cnt[i]*(cnt[i]-1)/2;
  }
  cout<<res<<endl;
  return 0;
}

B

用优先队列，60pts

开一个数组记录无敌状态的剩余步数。

#include<bits/stdc++.h>

using namespace std;

typedef pair<int,int> pii;
const int N=1e3+10;
char g[N][N];
int d[N][N];
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
int vis[N][N];

struct node{
  int d;
  int x,y;
  // int wd;
  int kb;
  // int flag=1;

  bool operator<(const node &M)const{
    return d>M.d;
  }
};

signed main() {
  ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

  int n,k;
  cin>>n>>k;

  for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
      cin>>g[i][j];
    }
  }

  priority_queue<node> q;
  memset(vis, -1, sizeof vis);
  q.push({0,1,1,0});
  vis[1][1]=0;
  while(q.size()){
    node dian=q.top();
    q.pop();
    int d=dian.d;
    int x=dian.x;
    int y=dian.y;
    int kb=dian.kb;

    if(x==n&&y==n){
      cout<<d<<endl;
      return 0;
    }
    for(int i=0;i<4;i++){
      int xx=dx[i]+x;
      int yy=dy[i]+y;
      if(kb==0&&g[xx][yy]=='X') continue;
      int wdb=max(0,kb-1);
      if(g[xx][yy]=='%') wdb=k;
      if(xx>=1&&xx<=n&&yy>=1&&yy<=n&&g[xx][yy]!='#'&&vis[xx][yy]<wdb){
        vis[xx][yy]=wdb;
        q.push({d+1,xx,yy,wdb});
      }

    }

  }
  cout<<-1<<endl;

  return 0;
}

C

只会暴力小数据，20pts

对题目理解不够透彻，关键在于统计完成所有操作后第i个区间内差分前缀和中1的数量和完成所有操作后0的数量。因为第i个区间1的数量就是有第i区间操作产生的

推荐题解

#include<bits/stdc++.h>

using namespace std;

typedef pair<int,int> pii;
const int N=3e5+10;
int d[N];
int pre1[N],pre0[N],l[N],r[N],a[N];
int n,m;

struct node{
  int x,y;
}ns[N];

void solve1(){
  for(int i=0;i<m;i++){
    int x,y;
    cin>>x>>y;
    ns[i]={x,y};
    d[x]+=1;
    d[y+1]-=1;
  }

  for(int i=0;i<m;i++){
    int x=ns[i].x;
    int y=ns[i].y;
    d[x]-=1;
    d[y+1]+=1;
    int res=0;
    for(int j=1;j<=n;j++){
      a[j]=a[j-1]+d[j];
      // cout<<a[j]<<' ';
      if(a[j]==0) res++;
    } 
    d[x]+=1;
    d[y+1]-=1;
    cout<<res<<endl;
  }
}

void solve2(){
  for(int i=0;i<m;i++){
    cin>>l[i]>>r[i];
    d[l[i]]++;
    d[r[i]+1]--;
  }

  for(int i=1;i<=n;i++){
    d[i]+=d[i-1];
    pre1[i]=pre1[i-1]+(d[i]==1);
    pre0[i]=pre0[i-1]+(d[i]==0);
  }

  for(int i=0;i<m;i++){
    cout<<(pre1[r[i]]-pre1[l[i]-1])+pre0[n]<<endl;
  }
}

signed main() {
  ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

  cin>>n>>m;
  int ans=0;
  // if(n<5010&&m<5010){
  //   solve1();
  // }else{
  //   solve2();
  // }
  solve2();

  return 0;
}

D

暴力小数据，只拿了第一组小数据的分，20pts

大数据范围在赛时想到了郭老师的前缀和blog的一个技巧，把二位的子矩阵转换成一维的序列，但是没有在赛时想到小于K的矩阵用双指针计算，卡在了求 有几个子序列的元素之和小于等于 k

推荐题解

#include<bits/stdc++.h>

using namespace std;

typedef pair<int,int> pii;
#define int long long 
const int N=510;
int a[N][N],b[N];
int sum[N][N];
int n,m,K;
int res;

void solve(){
  for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
      for(int u=i;u<=n;u++){
        for(int v=j;v<=m;v++){
          int ans=sum[u][v]-sum[i-1][v]-sum[u][j-1]+sum[i-1][j-1];
          if(ans<=K) res++;
        }
      }
    }
  }
  cout<<res<<endl;
}

void solve1(){

  // for(int i=1;i<=n;i++){
  //   for(int j=1;j<=m;j++){
  //     cout<<a[i][j]<<' ';
  //   }
  //   cout<<endl;
  // }

  
  for(int i=1;i<=n;i++){
    for(int j=i;j<=n;j++){
      for(int k=1;k<=m;k++) b[k]=a[j][k]-a[i-1][k];

      int l=1,r=1,pre=0;
      while(r<=m){
        pre+=b[r];
        if(pre<=K){
          res+=(r-l+1);
        }else{
          while(pre>K){
            pre-=b[l];
            l++;
          }
          res+=(r-l+1);
        }
        r++;
      }
    }
  }
  cout<<res<<endl;
}

void solve2(){

}

signed main() {
  ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

  
  cin>>n>>m>>K;
  for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
      cin>>a[i][j];
      sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];
      a[i][j] += i == 1 ? 0 :a[i - 1][j];
    }
  }
  solve1();



  return 0;
}

G

赛时最后五分钟看了题目，赛后贪心小价格+正序，90pts，洛谷数据弱了。

正解思路：

考虑保质期长的最小价格，如果较小价格保质期较短，那么就会产生较小价格的商品选不了，多选了较大价格的商品。推荐题解。也可以这样想，如果后面天数用保质期长且便宜的巧克力，那么前面就能有选保质期较短但是价格适中的巧克力了。

见测试样例：

3 3
1 3 2
5 1 1
100 3 5

wrong answer:102
right answer：7

正解：

用优先队列维护当前天能买的巧克力，如果没有则输出-1，有就优先选择保质期短的。

#include<bits/stdc++.h>

using namespace std;

typedef pair<int,int> pii;
const int N=1e5+10;

struct node{
  int mon;
  int day;
  int cnt;
  //大根堆重载小于号，当前对象比M的钱大，M的优先级高
  bool operator<(const node&M)const{
    return mon>M.mon;
  }
}ns[N];


bool cmp(node&a,node&b){
  return a.day>b.day;
}

signed main() {
  ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

  int x,n;
  cin>>x>>n;

  for(int i=0;i<n;i++){
    cin>>ns[i].mon>>ns[i].day>>ns[i].cnt;
  }

  sort(ns,ns+n,cmp);

  priority_queue<node> q;
  int res=0;
  int tol=0;
  for(int i=x;i>=1;i--){
    while(tol<n&&ns[tol].day>=i){
      q.push({ns[tol]});
      tol++;
    }
    while(q.size()&&q.top().cnt==0) q.pop();
    if(!q.size()){
      cout<<-1<<endl;
      return 0;
    }
    auto [mon,day,cnt]=q.top();
    // cout<<mon<<' ';
    q.pop();
    cnt--;
    res+=mon;
    q.push({mon,day,cnt});
  }
  // cout<<endl;
  cout<<res<<endl;

  return 0;
}