9.14题解T1T2T3T4

T1

对于这个数据范围，我们发现我们不断的乘$b$，什么都不加，$b$是最小的2，$T$是最小的1，最多也就乘大概60次就足够了，也就是说我们完全可以枚举乘过几个$b$，既然我们确定了需要乘几个$b$，那加$a$也就可以确定了，我们可以得到$m{times}a=T-S{times}b^x$，我们就可以得到m的值，而关键就是求出$b$进制下的m，这样的话我们就可以直接统计加了几次$a$了，显然是个进制转化，照着二进制乱搞就可以了

#include<cstdio>
#include<cstring>
#include<iostream>
#define maxx 1001000
#define ll long long
#define inf 2000000000000000000
using namespace std;
ll S,T,a,b,base=1,m,ans=inf;
ll ksm(ll a,int b)
{

ll ans=1;

while(b)

{

if(b&1)
ans*=a;

b=b>>1;
a*=a;

}

return ans;
}
int main()
{

scanf("%lld%lld%lld%lld",&S,&T,&a,&b);

for(int i=0;i<=64;++i)

{

if(base>T/S)
break;

ll cha=T-S*base;

if(cha%a==0)
m=cha/a;

else
{base*=b;
continue;}

ll sum=i;

for(int j=i;j>=0;--j)

{

ll mi=ksm(b,j);

sum+=m/mi;
m%=mi;

}

base*=b;
ans=min(ans,sum);

}

printf("%lldn",ans);

return 0;
}

T2

不知道为什么我像失忆了一般，我明明记得我打完了这道题，然而我残存的代码告诉我，我刚开始码他。。。。咕了

T3

他们发现了费用随特殊加热器的使用次数呈单谷函数，我们就可以愉快的开启三分的旅程，怎么$check$呢？考虑贪心，由于我们每次用普通加热器都会覆盖一段区间，所以用树状数组进行差分，首先预处理出来我如果在当前这个点使用普通加热器，最多能覆盖到哪一个点，$check$的时候从第一个点开始，如果还没有达到希望的能量，就使用加热器使他达到，顺带使可以和他一起使用加热器的点需要的能量值变少即可

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<bits/stdc++.h>
#define maxn 100100
#define int long long
using namespace std;
struct node{

int l,r;
}a[maxn];
int n,m,t,co_ba,maxx,l=0,r,head=1,minn=0x7fffffffffffffff;
int p[maxn],flag[maxn],c[maxn],to[maxn],sf[maxn];
bool cmp(const node &a,const node &b)
{

return a.l<b.l;
}
int lowbit(int x)
{

return x&(-x);
}
void add(int pos,int w)
{

for(;pos<=n;pos+=lowbit(pos))
c[pos]+=w;
}
int query(int pos)
{

int ans=0;

for(;pos>0;pos-=lowbit(pos))
ans+=c[pos];

return ans;
}
int check(int x)
{

memset(c,0,sizeof(c));

int sum=x*t;

for(int i=1;i<=n;++i)
sf[i]=max(1ll*0,p[i]-x);

for(int i=1;i<=n;++i)
add(i,sf[i]-sf[i-1]);

for(int i=1;i<=n;++i)

{

int ww=query(i);

if(ww<=0)
continue;

sum+=ww;
add(i,-ww);
add(to[i]+1,ww);

}

return sum;
}
signed main()
{

scanf("%lld%lld%lld",&n,&m,&t);

for(int i=1;i<=n;++i)
scanf("%lld",&p[i]);

for(int i=1;i<=m;++i)

{

scanf("%lld%lld",&a[i].l,&a[i].r);

for(int j=a[i].l;j<=a[i].r;++j)
flag[j]=1;

}

sort(a+1,a+m+1,cmp);

for(int i=1;i<=n;++i)

if(!flag[i])
maxx=max(maxx,p[i]);

for(int i=1;i<=n;++i)
{p[i]=max(1ll*0,p[i]-maxx);
r=max(r,p[i]);}

co_ba=t*maxx;
maxx=0;

for(int i=1;i<=n;++i)

{

while(a[head].l<=i&&head<=m)
{maxx=max(maxx,a[head].r);
head++;}

to[i]=maxx;

}

while(l+1<r)

{

int mid=(l+r)>>1;

int cost1=check(mid-1),cost2=check(mid);

minn=min(minn,cost1);
minn=min(minn,cost2);

if(cost1>=cost2)
l=mid;

else
r=mid;

}

co_ba+=minn;
printf("%lldn",co_ba);

return 0;
}

T4

说一下思路过程吧，一开始打了个暴力，枚举连接的两个端点直接求花费，然后只有30分，后来打了个小表发现一个端点确定之后另一个端点可以三分，就有了$T60$的好成绩，然后我就突然发现两个端点似乎可以三分套三分，但是由于中间平的地方太多，单谷不严格，所以三分本来就是死的，三分套三分就死透了，然后我惊讶的得知这道题数据水到随机化可$A$，然后我就$A$了。。。。。

#include<iostream>
#include<cstdio>
#define maxn 100010
using namespace std;
struct node{

int l,r;
}q[maxn];
int n,m,head,tail,ans=0x7fffffff;
int check()
{

int maxx=0;

for(int i=1;i<=m;++i)

{

int len=q[i].r-q[i].l;

if(head>q[i].l&&tail<q[i].r)
len=min(len,head-q[i].l+q[i].r-tail);

else if(head<=q[i].l&&tail>=q[i].r)
len=min(q[i].r-q[i].l,q[i].l-head+tail-q[i].r);

else if(head>q[i].l&&tail>=q[i].r)
len=min(q[i].r-q[i].l,head-q[i].l+tail-q[i].r);

else if(head<=q[i].l&&tail<q[i].r)
len=min(q[i].r-q[i].l,q[i].l-head+q[i].r-tail);

maxx=max(maxx,len);

if(maxx>=ans)
return maxx;

}

return maxx;
}
int main()
{

scanf("%d%d",&n,&m);

for(int i=1;i<=m;++i)
scanf("%d%d",&q[i].l,&q[i].r);

if(m==1)
{printf("0n");
return 0;}

for(int i=1;i<=n;++i)

{

int l=i+2,r=n;

while(l+1<r)

{

int mid=(l+r)>>1;

head=i;
tail=mid-1;

int cost1=check();

head=i;
tail=mid;

int cost2=check();

ans=min(ans,cost1);
ans=min(ans,cost2);

if(cost1>=cost2)
l=mid;

else
r=mid;

}

}

printf("%dn",ans);

return 0;
}