AtCoder Beginner Contest 192
AK啦，AK啦
A - Star
题意：(100)分可以得到一个星星，给出一个数(x)，问离下一个星星还有多远。
特判一下是不是刚拿了一个星星即可。
B - uNrEaDaBlE sTrInG
题意：如果一个字符串满足奇数位上的字符都是小写，偶数位上的字符都是大写的话，那么称它为难理解的，输入一个字符串判断其是否难理解。
按题意模拟即可。
C - Kaprekar Number
题意：(g1(x))表示(x)重排后最大值，(g2(x))表示(x)重排后最小值，设(f(x)=g1(x)-g2(x))，给出(a_0)，(a[i+1]=f(a[i]))，求(a[k])。
首先一个显然的结论是(digit(f(x))leq digit(x))，(digit(i))表示(i)的位数。
那么由于(a[0]leq10^9)，每次维护一个长小于(10)的数组暴力即可。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 200005
using namespace std;
int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*f;
}
int b[20],a[N],n,k;
int doit(int x)
{
int cnt=0,minn=0,maxn=0;
while(x)
{
b[++cnt]=x%10;
x/=10;
}
sort(b+1,b+1+cnt);
for(int i=1;i<=cnt;i++)minn=minn*10+b[i];
sort(b+1,b+1+cnt,greater<int>());
for(int i=1;i<=cnt;i++)maxn=maxn*10+b[i];
return maxn-minn;
}
int main()
{
n=read();k=read();
a[0]=n;
for(int i=1;i<=k;i++)
{
a[i]=doit(a[i-1]);
}
printf("%d
",a[k]);
}
D - Base n
这题交了(11)次，写了(1)个小时，自闭了。
题意：给出(n),(m),设(n)中最大的数字为(x)，问在不同的进制（(bas>x)）下，小于等于(m)的不同的数有多少个
如果以为是进制的话你就会不停WAWAWA。
考虑二分进制的上界，如果当前进制下(n)已经大于(m)了那么显然不行，否则可以。
特判掉(n)为(1)位数的情况即可。
#include<iostream>
#include<cstdio>
#include<cstring>
#define N 200005
#define int __uint128_t
using namespace std;
int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*f;
}
void write(int x)
{
if(x>9)write(x/10);
putchar(x%10+'0');
}
int n,m,X,a[N],cnt;
char ch[N];
int check(int bas)
{
int now=0,maxn=0,tmp=1;
for(int i=2;i<=cnt;i++)
{
if(tmp*bas<tmp)return 0;
tmp*=bas;
}
for(int i=1;i<=cnt;i++)
{
if(now&&m/now+10<bas)return 0;
now=now*bas+a[i];maxn=max(maxn,now);
if(now>m)return 0;
}
if(maxn!=now)return 0;
return 1;
}
signed main()
{
scanf("%s",(ch+1));cnt=strlen(ch+1);
for(int i=1;i<=cnt;i++)a[i]=ch[i]-'0',X=max(X,a[i]);
m=read();
if(cnt==1&&a[1]<=m)return puts("1"),0;
int l=X+1,r=m,tmp=m,cntt=0;
while(m){cntt++;m/=10;}
if(cntt<cnt)r=10;
m=tmp;
while(l<=r)
{
int mid=(l+r)/2;
if(check(mid))l=mid+1;
else r=mid-1;
}
write((l-1)-(X+1)+1);
}
/*
1000000000000000000
1000000000000000000
*/
E - Train
题意：有(n)座城市之间有(m)条双向高铁线路连接，第(i)条高铁线路会在(k_i|time)的时刻(time)进站(包括(0))，花费(t_i)的时间到另一个端点，问(S)到(T)的最短时间。
我们发现如果有两个状态((i,j),(i,k))表示第(j/k)时刻到(i)节点，且(j<k)，那么从这两个状态走到(T)，((i,j))一定是不劣于$ (i,k)(的，因为)k(能赶上的车)j$一定能赶上，因此直接最短路即可，从一个位置转出去的时候要加上等车的时间。
大力(dij)即可。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define N 200005
#define int long long
#define mp make_pair
using namespace std;
int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*f;
}
int n,m,S,T,v[N],head[N],nxt[N],t[N],k[N],cnt,dis[N],vis[N];
void add(int a,int b,int c,int d)
{
v[++cnt]=b;
t[cnt]=c;
k[cnt]=d;
nxt[cnt]=head[a];
head[a]=cnt;
}
int Nxt(int x,int y)
{
if(x%y==0)return x;
int now=x%y;
return (y-now)+x;
}
void dij()
{
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;
memset(dis,0x3f,sizeof(dis));q.push(mp(0,S));dis[S]=0;
while(!q.empty())
{
int x=q.top().second;q.pop();
if(vis[x])continue;vis[x]=1;
//cout<<x<<" "<<dis[x]<<endl;
for(int i=head[x];i;i=nxt[i])
{
//cout<<x<<" "<<dis[x]<<" "<<v[i]<<" "<<k[i]<<" "<<Nxt(dis[x],k[i])<<endl;
if(Nxt(dis[x],k[i])+t[i]<dis[v[i]])
{
dis[v[i]]=Nxt(dis[x],k[i])+t[i];
q.push(mp(dis[v[i]],v[i]));
}
}
}
}
signed main()
{
n=read();m=read();S=read();T=read();
for(int i=1;i<=m;i++)
{
int A=read(),B=read(),C=read(),D=read();
add(A,B,C,D);add(B,A,C,D);
}
dij();
if(dis[T]!=dis[0])printf("%lld
",dis[T]);
else puts("-1");
}
F - Potion
最后两分钟过的，太刺激了。
题意：有(n)个数，你可以在第(0)个时刻条任意多个数出来，并让计数器加上他们的和，设你挑了(k)个数，那么之后每个时刻计数器都会加(k)，你要最小化计数器恰好到(x)的时间（加是一下子加的，如果你从(1)直接到了(3)，不认为恰好到了(2)）。
考虑枚举第(0)个时刻那多少个数出来，设挑了(s)个数出来，那么为了满足题意，他们的和对(s)取余一定等于(x\%s)。
那么考虑(dp)，(f(i,j,k))表示前(i)个数挑了(j)个数出来，对(s)取余结果为(k)，枚举第(i)个数是否取即可。
#include<iostream>
#include<cstdio>
#include<cstring>
#define N 105
#define int long long
using namespace std;
int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*f;
}
int n,f[N][N][N],a[N],X,ans=1e18;
signed main()
{
n=read();X=read();
for(int i=1;i<=n;i++)a[i]=read();
for(int S=1;S<=n;S++)
{
memset(f,-0x3f,sizeof(f));
f[0][0][0]=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=S;j++)
{
for(int k=0;k<=n;k++)
{
//cout<<k<<" "<<a[i]<<" "<<((k-a[i])%S+S)%S<<endl;
f[i][j][k]=max(f[i-1][j][k],f[i-1][j-1][((k-a[i])%S+S)%S]+a[i]);
}
}
}
if(f[n][S][X%S]<0)continue;
else ans=min(ans,(X-f[n][S][X%S])/S);
//cout<<S<<" "<<X%S<<" "<<f[n][S][X%S]<<" "<<(X-f[n][S][X%S])/S<<endl;
}
printf("%lld
",ans);
return 0;
}