https://atcoder.jp/contests/abc192/tasks
/*果然还是我太菜了qwq*/
D
当长度为1时需要特判一下，因为以任何大于该数为底的值都为该数。
长度大于1时直接二分就行。
/*
*/
char s[100];
int ma,len;
ll m;
bool check(ll x)
{
ll now=0;
rep(i,1,len)
{
if(m<s[i]-'0')return 0;
if(now>(m-(s[i]-'0'))/x)return 0;
now=now*x+s[i]-'0';
// pdd(i,now);
}
return 1;
}
void solve()
{
sc(s+1);
slld(m);
len=strlen(s+1);
rep(i,1,len)ma=max(ma,s[i]-'0');
if(len==1)
{
if(m>=ma)puts("1");
else puts("0");
return;
}
ll l=ma+1,r=m,ans=0;
while(l<=r)
{
ll mid=(l+r)>>1;
if(check(mid))l=mid+1,ans=mid-ma;
else r=mid-1;
// plld(mid);
}
plld(ans);
}
int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);
int T=1;
// sd(T);
while(T--)solve();
}
E
迪杰斯特拉
给你一个无向图
每条边有两个参数t,k代表经过这条边需要的时间t和时间为k的倍数时才可以通过
/*
*/
struct node{
int to,nex;
ll t,k;
}a[maxn<<1];
int n,m,head[maxn],cnt,x,y;
ll d[maxn];
void add(int fro,int to,ll t,ll k)
{
a[++cnt].to=to;
a[cnt].t=t;
a[cnt].k=k;
a[cnt].nex=head[fro];
head[fro]=cnt;
}
void bfs()
{
d[x]=0;
priority_queue<PLI,deque<PLI >,greater<PLI > >pq;
pq.push(mk(0,x));
while(!pq.empty())
{
PLI p=pq.top();
pq.pop();
ll val=p.fi;
int cur=p.se;
if(cur==y)return;
for(int i=head[cur];i;i=a[i].nex)
{
int to=a[i].to;
ll t=a[i].t,k=a[i].k;
ll tmp=val%k;
if(!tmp)tmp=k;
tmp=k-tmp;
if(d[to]>val+tmp+t)
{
d[to]=val+tmp+t;
pq.push(mk(d[to],to));
}
}
}
}
void solve()
{
sdd(n,m);sdd(x,y);
rep(i,1,n)d[i]=1e18;
rep(i,1,m)
{
int u,v;
ll t,k;
scanf("%d%d%lld%lld",&u,&v,&t,&k);
add(u,v,t,k);
add(v,u,t,k);
}
bfs();
if(d[y]==1e18)d[y]=-1;
plld(d[y]);
}
int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);
int T=1;
// sd(T);
while(T--)solve();
}
F
这题。。。比赛时debug半天都没过，而且还wa30，结果没想到是f的锅。
/*
n种材料 第i种能力为ai
从中选择大于等于1种材料混合它们
混合k种的话 能力为总的能力
每秒增加k能力 增加的是离散的不是连续的
最早什么时候能获得准确x能力
是可以获得x能力的
*/
int n,a[109],f[109];
//选择i件物品必须sum[i]%i==f[i]
ll x,res,sum;
int tmp[109][109];
void solve()
{
sd(n);slld(x);
rep(i,1,n)sd(a[i]),sum+=a[i];
if(sum==x)
{
puts("0");
return;
}
rep(i,1,n)f[i]=x%i;
sort(a+1,a+1+n);
res=x-a[n];
rep(i,2,n)//选i个
{
memset(tmp,-1,sizeof tmp);
tmp[0][0]=0;
rep(j,1,n)//排到当前
{
dep(ii,min(i-1,j-1),0)//前边选了ii个的和
rep(k,0,i-1)
{
if(tmp[ii][k]==-1)continue;
tmp[ii+1][(k+a[j])%i]=max(tmp[ii+1][(k+a[j])%i],tmp[ii][k]+a[j]);
}
}
if(tmp[i][f[i]]!=-1)res=min(res,(x-tmp[i][f[i]])/i);//,
// printf("%d %lld
",i,(x-tmp[i][f[i]])/i);
}
plld(res);
}
int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);
int T=1;
// sd(T);
while(T--)solve();
}