suzume

今天是 mx 的 NOIP2025 模擬 2。寫了前兩題。

Luogu P14520 戰爭遊戲

打gen來

第一眼猜答案前半部分是 \(0\)，後半部分是 \(1\)，看了看大樣例發現猜對了。

然後想想造成這個的原因大概是兩人都傾巢對拼，然後哪邊多哪邊贏。

然後這就是個前綴和吧，寫一寫。

然後被第二個大樣例卡了。

想了想又發現 L 可以先手吃一個 K 的格子，但是 K 也有可能吃回來。

這樣的話好像就不能確定了啊，但是別急，我們繼續猜倆人頂多互吃一次。

然後這樣如果 L 吃了一個還能接着吃，K 就要把這個退回去防止被吃。

如果 L 吃了一個結果 K 能吃回來，那麼 L 就不能往前吃。

如果 L 不能吃，那麼 L 應該把自己退回來。

然後這樣 L 可能會一直退到自己 老家 \(1\)

於是前綴和寫寫就行了。賽時因為忘了 K 還能退掛了 8pts，竟然只掛了 8pts。

92pts code

Show me the code 

#define rd read()
#define mkp make_pair
#define ls p<<1
#define rs p<<1|1
#define rep(i,a,b) for( int i=(a); i<=(b); ++i)
#define per(i,a,b) for( int i=(a); i>=(b); --i)
#include<bits/stdc++.h>
using namespace std;
typedef long long i64;
typedef unsigned long long u64;
typedef unsigned int u32;
typedef __int128 i128;
i64 read(){
  i64 x=0,f=1;
  char c=getchar();
  while(c>'9'||c<'0'){if(c=='-') f=-1;c=getchar();}
  while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
  return x*f;
}
void init(){

}
int a[200005];
void solve(){
  int n;cin>>n;
  i64 sum=0;
  for(int i=1;i<=n;i++){
    a[i]=rd;
    sum+=a[i];
  }
  i64 ps=0;
  int lk=0;
  for(int i=1;i<n;i++){
    ps+=a[i];
    i64 p2=ps;
    if(a[i]>a[i+1]){
      i64 t1=a[i]+a[i+1];
      if(a[i+2]>=t1){
        p2-=a[i];
      }
      else p2+=a[i+1];
    }
    if(p2<=sum-p2&&!lk)cout<<0;
    else {lk=1;cout<<1;}
  }
  cout<<'\n';
  return ;
}
int main(){
  
  int T;cin>>T;
  while(T--){
    init();solve();
  }
  
  return 0;
}

100pts code

Show me the code 

#define rd read()
#define mkp make_pair
#define ls p<<1
#define rs p<<1|1
#define rep(i,a,b) for( int i=(a); i<=(b); ++i)
#define per(i,a,b) for( int i=(a); i>=(b); --i)
#include<bits/stdc++.h>
using namespace std;
typedef long long i64;
typedef unsigned long long u64;
typedef unsigned int u32;
typedef __int128 i128;
i64 read(){
  i64 x=0,f=1;
  char c=getchar();
  while(c>'9'||c<'0'){if(c=='-') f=-1;c=getchar();}
  while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
  return x*f;
}
void init(){

}
int a[200005];
void solve(){
  int n;cin>>n;
  i64 sum=0;
  for(int i=1;i<=n;i++){
    a[i]=rd;
    sum+=a[i];
  }
  i64 ps=0;
  int lk=0;
  for(int i=1;i<n;i++){
    ps+=a[i];
    i64 p2=ps;
    if(a[i]>a[i+1]&&a[i]+a[i+1]>a[i+2]){
      p2+=a[i+1];
    }
    if(p2<=sum-p2&&!lk)cout<<0;
    else {lk=1;cout<<1;}
  }
  cout<<'\n';
  return ;
}
int main(){
  
  int T;cin>>T;
  while(T--){
    init();solve();
  }
  
  return 0;
}

Luogu P14521 加減乘除

長且了，於是建議評綠，於是：

2021牛客OI賽前集訓營-提高組（第一場）補題_i++

其實賽時想的挺快的，就是欽定用 \(1\)

然後能到這個點的前提是之前也能到，於是處理完範圍之後再從初始點開始跑 DFS，過程把區間取個交即可。

如果無根樹還可做嗎？問題出在可以在某些點橫跳攢值。

詢問離線即可。最初寫了一版還以為詢問都很小，結果一打開大樣例直接傻眼了，還好寫的代碼加上離散化就行了。

然後就要從 \(-10^{18}\)

又要用 __int128，然後大樣例大的離譜上了快讀。

讀題這一塊。

code

Show me the code 

#define rd read()
#define mkp make_pair
#define ls p<<1
#define rs p<<1|1
#define rep(i,a,b) for( int i=(a); i<=(b); ++i)
#define per(i,a,b) for( int i=(a); i>=(b); --i)
#include<bits/stdc++.h>
using namespace std;
typedef long long i64;
typedef unsigned long long u64;
typedef unsigned int u32;
typedef __int128 i128;
i64 read(){
  i64 x=0,f=1;
  char c=getchar();
  while(c>'9'||c<'0'){if(c=='-') f=-1;c=getchar();}
  while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
  return x*f;
}
const int N=5e5+1145;
struct edge{
  int v;
  i64 l,r;
};
pair<i128,i128> rg[N];
vector<edge> e[N];
char op[N];
i64 dt[N];
vector<i64> ql,dis;
vector<i64>::iterator rb;
void dfs(int u,int fa,i128 d){
  if(op[u]=='+'){d+=dt[u];}
  else d-=dt[u];
  for(edge s:e[u]){
    int v=s.v;
    if(v==fa)continue;
    i64 l=s.l;
    i64 r=s.r;
    if(d<l){
      i128 rel=(i128)(-1e18)+(l-d);
      i128 rer=rel+r-l;
      rg[v].first=rel;
      rg[v].second=rer;
    }
    else if(l<=d&&d<=r){
      i128 rel=(i128)-1e18;
      i128 rer=rel+r-d;
      rg[v].first=rel;
      rg[v].second=rer;
    }
    else{
      rg[v].first=(i128)1e30;
      rg[v].second=(i128)-1e30;
    }
    dfs(v,u,d);
  }
  return ;
}
i64 det[1000999];
void dfs2(int u,int fa,i128 l,i128 r){
  l=max(l,rg[u].first);
  r=min(r,rg[u].second);
  int llb,rrb;
  llb=lower_bound(dis.begin(),rb,l)-dis.begin();
  rrb=upper_bound(dis.begin(),rb,r)-dis.begin()-1;
  if(llb<=rrb){det[llb]++;det[rrb+1]--;}
  for(edge s:e[u]){
    int v=s.v;
    if(v==fa)continue;
    dfs2(v,u,l,r);
  }
  return ;
}
int main(){
  
  int n,q;cin>>n>>q;
  for(int i=2;i<=n;i++){
    int v;i64 l,r;
    v=rd;l=rd;r=rd;
    e[i].push_back(edge{v,l,r});
    e[v].push_back(edge{i,l,r});  
  }
  for(int i=1;i<=n;i++){
    cin>>op[i]>>dt[i];
  }
  for(int i=1;i<=q;i++){
    i64 mr=rd;
    ql.push_back(mr);
    dis.push_back(mr);
  }
  sort(dis.begin(),dis.end());
  rb=unique(dis.begin(),dis.end());

  rg[1].first=(i64)-1e18;
  rg[1].second=(i64)1e18;
  dfs(1,0,-1e18);
  dfs2(1,0,-1e18,1e18);
  for(int i=0;i<=q;i++){
    det[i]=det[i-1]+det[i];
  }
  for(i64 v:ql){
    int wp=lower_bound(dis.begin(),rb,v)-dis.begin();
    cout<<det[wp]<<'\n';
  }
  
  return 0;
}

再找個時間寫寫昨晚的獵奇 ABC，還要去背一下 pbds 科技。