3 条题解

  • 0
    @ 2025-3-29 18:58:19

    #include #define ll long long #include <bits/stdc++.h> using namespace std; ll x = 1;ll q,mod;ll n,m,t,k;ll a[500009],b[500009],c[500009]; inline ll read() { ll x=0,f=1;char ch=getchar(); while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();} while (isdigit(ch)){x=x10+ch-48;ch=getchar();} return xf; } void merge_sort(ll l,ll r,ll mid){ ll i = l,j = mid+1; for(ll p=l;p<=r;++p){ if((b[i]<=b[j]&&i<=mid)||(j>r)){c[p] = b[i++]; } else c[p] = b[j++]; } for(ll p=l;p<=r;++p){b[p] = c[p]; } } ll qpow(ll a){ ll res = 1, t = a, k = mod-2; while(k){ if(k&1)res*=t%mod; t*=t;t%=mod; k>>=1; } return res%mod; } bool judge(ll l,ll r,ll p){ r = min(r,n); for(ll i=l;i<=min(r+p,n);++i){ b[i] = a[i]; } sort(b+r+1,b+min(r+p+1,n+1)); merge_sort(l,min(n,r+p),r); ll x = l,y = min(r+p,n),ans = 0; for(ll i=1;i<=m;++i){ if(x>=y){break; } ans+=(b[y]-b[x])(b[y]-b[x]); x++;y--; } if(ans>t)return 0; for(ll i=l;i<=min(r+p,n);++i)a[i] = b[i]; return 1; } void solve(){ k=read(); while(k--){ n=read();m=read();t=read(); for(ll i=1;i<=n;++i){ a[i] = read(); } ll l=1,r=1,p=1,cnt=0; while(r<=n){p = 1; while(p){ if(r+p<=n&&judge(l,r,p)){r+=p;if(r>=n)break; p=2; } else p/=2; } l = r+1;r = l;cnt++; } printf("%lld\n",cnt); } } int main() { solve(); return 0; }

    • 0
      @ 2023-4-9 19:54:28
      #include <iostream>
      #define ll long long
      #include <bits/stdc++.h>
      using namespace std;
      ll x = 1;ll q,mod;ll n,m,t,k;ll a[500009],b[500009],c[500009];
      inline ll read()
      {
      	ll x=0,f=1;char ch=getchar();
      	while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
      	while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
      	return x*f;
      }
      void merge_sort(ll l,ll r,ll mid){
          ll i = l,j = mid+1;
          for(ll p=l;p<=r;++p){
              if((b[i]<=b[j]&&i<=mid)||(j>r)){c[p] = b[i++]; }
              else c[p] = b[j++];
          }
          for(ll p=l;p<=r;++p){b[p] = c[p]; }
      }
      ll qpow(ll a){
          ll res = 1, t = a, k = mod-2;
          while(k){
              if(k&1)res*=t%mod;
              t*=t;t%=mod;
              k>>=1;
          }
          return res%mod;
      }
      bool judge(ll l,ll r,ll p){
          r = min(r,n);
          for(ll i=l;i<=min(r+p,n);++i){
              b[i] = a[i];
          }
          sort(b+r+1,b+min(r+p+1,n+1));
          merge_sort(l,min(n,r+p),r);
          ll x = l,y = min(r+p,n),ans = 0;
          for(ll i=1;i<=m;++i){
              if(x>=y){break; }
              ans+=(b[y]-b[x])*(b[y]-b[x]);
              x++;y--;
          }
          if(ans>t)return 0;
          for(ll i=l;i<=min(r+p,n);++i)a[i] = b[i];
          return 1;
      }
      void solve(){
          k=read();
          while(k--){
              n=read();m=read();t=read();
              for(ll i=1;i<=n;++i){
                  a[i] = read();
              }
              ll l=1,r=1,p=1,cnt=0;
              while(r<=n){p = 1;
              while(p){
                  if(r+p<=n&&judge(l,r,p)){r+=p;if(r>=n)break; p*=2; }
                  else p/=2;
              }
              l = r+1;r = l;cnt++;
              }
              printf("%lld\n",cnt);
          }
      }
      int main()
      {
          solve();
          return 0;
      }
      

      最多80

      • @ 2023-5-2 21:05:10

        image

      • @ 2023-5-2 21:05:43

        向各大佬求救

      • @ 2023-8-15 12:35:10

        @ #include<bits/stdc++.h> #define ll long long #include using namespace std; ll x = 1;ll q,mod;ll n,m,t,k;ll a[500009],b[500009],c[500009]; inline ll read() { ll x=0,f=1;char ch=getchar(); while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();} while (isdigit(ch)){x=x10+ch-48;ch=getchar();} return xf; } void merge_sort(ll l,ll r,ll mid){ ll i = l,j = mid+1; for(ll p=l;p<=r;++p){ if((b[i]<=b[j]&&i<=mid)||(j>r)){c[p] = b[i++]; } else c[p] = b[j++]; } for(ll p=l;p<=r;++p){b[p] = c[p]; } } ll qpow(ll a){ ll res = 1, t = a, k = mod-2; while(k){ if(k&1)res*=t%mod; t*=t;t%=mod; k>>=1; } return res%mod; } bool judge(ll l,ll r,ll p){ r = min(r,n); for(ll i=l;i<=min(r+p,n);++i){ b[i] = a[i]; } sort(b+r+1,b+min(r+p+1,n+1)); merge_sort(l,min(n,r+p),r); ll x = l,y = min(r+p,n),ans = 0; for(ll i=1;i<=m;++i){ if(x>=y){break; } ans+=(b[y]-b[x])(b[y]-b[x]); x++;y--; } if(ans>t)return 0; for(ll i=l;i<=min(r+p,n);++i)a[i] = b[i]; return 1; } void solve(){ k=read(); while(k--){ n=read();m=read();t=read(); for(ll i=1;i<=n;++i){ a[i] = read(); } ll l=1,r=1,p=1,cnt=0; while(r<=n){p = 1; while(p){ if(r+p<=n&&judge(l,r,p)){r+=p;if(r>=n)break; p=2; } else p/=2; } l = r+1;r = l;cnt++; } printf("%lld\n",cnt); } } int main() { solve(); return 0; }

        可以AC的

    • -1
      @ 2023-8-13 12:41:58

      我做对啦~

      #include<bits/stdc++.h>
      #define ll long long
      #include 
      using namespace std;
      ll x = 1;ll q,mod;ll n,m,t,k;ll a[500009],b[500009],c[500009];
      inline ll read()
      {
      ll x=0,f=1;char ch=getchar();
      while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
      while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
      return x*f;
      }
      void merge_sort(ll l,ll r,ll mid){
      ll i = l,j = mid+1;
      for(ll p=l;p<=r;++p){
      if((b[i]<=b[j]&&i<=mid)||(j>r)){c[p] = b[i++]; }
      else c[p] = b[j++];
      }
      for(ll p=l;p<=r;++p){b[p] = c[p]; }
      }
      ll qpow(ll a){
      ll res = 1, t = a, k = mod-2;
      while(k){
      if(k&1)res*=t%mod;
      t*=t;t%=mod;
      k>>=1;
      }
      return res%mod;
      }
      bool judge(ll l,ll r,ll p){
      r = min(r,n);
      for(ll i=l;i<=min(r+p,n);++i){
      b[i] = a[i];
      }
      sort(b+r+1,b+min(r+p+1,n+1));
      merge_sort(l,min(n,r+p),r);
      ll x = l,y = min(r+p,n),ans = 0;
      for(ll i=1;i<=m;++i){
      if(x>=y){break; }
      ans+=(b[y]-b[x])*(b[y]-b[x]);
      x++;y--;
      }
      if(ans>t)return 0;
      for(ll i=l;i<=min(r+p,n);++i)a[i] = b[i];
      return 1;
      }
      void solve(){
      k=read();
      while(k--){
      n=read();m=read();t=read();
      for(ll i=1;i<=n;++i){
      a[i] = read();
      }
      ll l=1,r=1,p=1,cnt=0;
      while(r<=n){p = 1;
      while(p){
      if(r+p<=n&&judge(l,r,p)){r+=p;if(r>=n)break; p*=2; }
      else p/=2;
      }
      l = r+1;r = l;cnt++;
      }
      printf("%lld\n",cnt);
      }
      }
      int main()
      {
      solve();
      return 0;
      }
      
    • 1

    信息

    ID
    21
    时间
    1000ms
    内存
    128MiB
    难度
    5
    标签
    递交数
    206
    已通过
    84
    上传者