博客大概咕了很久了.........

T1 A

大概推下式子就好了，考试时数据点分治DFS前30点T了，然后后70分因为两数相乘爆long long然后本来可以A掉，就WA零了.......

式子推出来肯定能化成S*B^n+A*B^x+A*B^y.........

我们可以看出划出这样的式子，那么首先肯定要乘n次，即S乘的B的系数，然后加的操作就是剩下式子的系数和

当然n是大于x,y.....因为S是肯定要被乘最多次的

然后在求系数时考虑求lca的那种打法

如果确定T-S*B^n可以整除A那么肯定能拆分成若干个这样的数相加的形式

所以直接求即可

注意乘爆long long

 

1 #include
      
        2 #define int long long 3 #define MAXN 100000100 4 using namespace std; 5 int S,T,A,B;int ans=0;int TT; 6 int b[MAXN];int minn=0x7ffffffff; 7 int min1(int x,int y){ 8     if((double)x>(double)y)return y; 9     return x;10 }11 void work1(){12      b[0]=A;13      int ptt=1;TT=T;14      while(1){           15            if((b[ptt-1]/A)>(T/B)+1)break;16            b[ptt]=b[ptt-1]*B;17            ptt++;18      }19      ptt--;20      int me=0;int ok=0;21      for(int i=ptt;i>=0;--i){22          me=b[i]/A;23          ans=0;24          T=TT;25          if(S<=(T/me+1)&&(T-S*me)%A==0){26             ok=i;ans=i;T-=S*me;27             for(int j=ok;j>=0;--j){28                 if(T>=b[j]){29                    ans=ans+T/b[j];30                    T-=T/b[j]*b[j];31                  }32             }33             minn=min1(minn,ans);34             break;35          }36      }37      printf("%lld\n",minn);38 } 39 signed main(){40      scanf("%lld%lld%lld%lld",&S,&T,&A,&B);41      work1();42 }
      

 

 

 

T2 B

不会，咕了

 

T3 C

首先对于p<=30的数据我们可以直接循环需要多少个特殊加热器

然后贪心处理最少花费

贪心的话，对于当前位置，只要找到能覆盖其的最大范围将其覆盖上，当然也有可能无法覆盖，就只能用

特殊用电器，至于区间修改，线段树即可。

然后可以考虑三分

对于当前1-n的区间来说，我们在一开始用超级用电器，可能会使使用正常用电器的费用减少

但是随着超级用电器的使用次数增加，会有一些节点已经达到所要P值

所以，费用减少的速度越来越少

那么我们就可以发（da）现（biao）这是个三分函数，直接三分即可

 

1 #include
      
         2 #define MAXN 110000  3 #define int long long  4 using namespace std;  5 int read(){  6     int x=0;char c=getchar();  7     while(c<'0'||c>'9')c=getchar();  8     while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}  9     return x; 10 } 11 struct node{
    int l,r,p,f;}t[4*MAXN];int n,m,T; 12 struct no{
    int l,r;}e[MAXN];int p[MAXN]; 13 int v[MAXN][2]; 14 void build(int k,int l,int r){ 15      t[k].l=l;t[k].r=r;t[k].f=0; 16      if(l==r){t[k].p=p[l];return ;} 17      int mid=(l+r)>>1; 18      build(k*2,l,mid); 19      build(k*2+1,mid+1,r); 20 } 21 void down(int k){ 22      t[k*2].f+=t[k].f;t[k*2+1].f+=t[k].f; 23      t[k*2].p+=t[k].f;t[k*2+1].p+=t[k].f; 24      t[k].f=0; 25 } 26 void add(int k,int l,int r,int x){ 27      if(l<=t[k].l&&r>=t[k].r){ 28         t[k].p+=x;t[k].f+=x; 29         return ; 30      } 31      if(t[k].f)down(k); 32      int mid=(t[k].l+t[k].r)>>1; 33      if(l<=mid)add(k*2,l,r,x); 34      if(r>mid)add(k*2+1,l,r,x); 35 } 36 int ask(int k,int x){ 37      if(t[k].l==t[k].r)return t[k].p; 38      int mid=(t[k].l+t[k].r)>>1; 39      if(t[k].f)down(k); 40      if(x<=mid)return ask(k*2,x); 41      else return ask(k*2+1,x); 42 } 43 int minn=0x7fffffffff;int ans=0;int maxn_id=0,maxn_r=0; 44 int work(int wb){ 45      ans=0; 46      maxn_id=0;maxn_r=0; 47      build(1,1,n); 48      add(1,1,n,-wb); 49      ans=ans+T*wb; 50      for(int i=1;i<=n;++i){ 51          int id=v[i][1]; 52          if(e[id].r>maxn_r){ 53              maxn_r=e[id].r;maxn_id=id; 54          } 55          int me=ask(1,i); 56          if(maxn_r
       
        0){ 57               ans+=T*me;add(1,1,n,-me); 58          } 59          else if(me>0){ 60               ans+=me; 61               add(1,e[maxn_id].l,e[maxn_id].r,-me); 62          } 63      } 64      minn=min(ans,minn); 65      return ans; 66 } 67 int ma=0; 68 void third_divide(){ 69      int l=0;int r=ma; 70      while(l+2
        
         work(midd)){l=mid;} 74            else r=midd; 75      } 76      minn=min(minn,work(l)); 77      minn=min(minn,work(l+1)); 78      minn=min(minn,work(r)); 79      printf("%lld\n",minn); 80 } 81 signed main(){ 82      n=read();m=read();T=read(); 83      for(int i=1;i<=n;++i){ 84          p[i]=read();ma=max(ma,p[i]); 85      } 86      for(int i=1;i<=m;++i){ 87          e[i].l=read();e[i].r=read(); 88          if(e[i].r>v[e[i].l][0]){ 89             v[e[i].l][0]=e[i].r; 90             v[e[i].l][1]=i; 91          } 92      }     93      third_divide(); 94 } 95 /*#include
         
           96 #define int long long 97 using namespace std; 98 int random(int x){return rand()%x;} 99 int gcdd(int x,int y){100     return (y==0)?x:gcdd(y,x%y);101 }102 signed main(){       103        freopen("text.in","w",stdout);104        srand((unsigned)time(0));105        int n=4;int m=4;int T=10000;106        printf("%lld %lld %lld\n",n,m,T);107        for(int i=1;i<=n;++i){108            printf("%lld ",random(4)+1);109        }110        cout<