「ABC 113A」Star

略。

#include<cstdio>
int x;
int main()
{
    scanf("%d",&x);
    for(int i=1;;++i)
    {
        if((x+i)%100==0)
        {
            printf("%d\n",i);
            break;
        }
    }
    return 0;
}

「ABC 192B」uNrEaDaBlE sTrInG

Link.

略。

#include<cstdio>
#include<cstring>
char s[1010];
int main()
{
    scanf("%s",s+1);
    bool flag=1;
    int n=strlen(s+1);
    for(int i=1;i<=n;++i)
    {
        if(i&1)
        {
            if(s[i]<'a'||s[i]>'z')
            {
                flag=0;
                break;
            }
        }
        else
        {
            if(s[i]<'A'||s[i]>'Z')
            {
                flag=0;
                break;
            }
        }
    }
    printf("%s\n",flag?"Yes":"No");
    return 0;
}

「ABC 192C」Kaprekar Number

Link.

照题意模拟。

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
long long las,now,n;
int k;
long long f(long long x)
{
    long long one=0,ano=0;
    vector<long long> num;
    while(x>0)
    {
        num.push_back(x%10);
        x/=10;
    }
    sort(num.begin(),num.end(),greater<long long>());
    for(auto val:num)    one=one*10+val;
    reverse(num.begin(),num.end());
    for(auto val:num)    ano=ano*10+val;
//    printf("%lld %lld\n",one,ano);
    return one-ano;
}
int main()
{
    scanf("%lld %d",&n,&k);
    las=n;
    if(k==0)    return printf("%lld\n",n)&0;
    while(k--)
    {
        now=f(las);
        las=now;
    }
    printf("%lld\n",now);
    return 0;
}

「ABC 192D」Base n

Link.

显然随着进制增大数字也会增大，所以可以二分。

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
struct bigInt : vector<long long>{
    bigInt &check( ){
        while( ! empty( ) && ! back( ) ) pop_back( );
        if( empty( ) )    return *this;
        for( unsigned i = 1; i < size( ); ++ i ){ ( *this )[i] += ( *this )[i - 1] / 10; ( *this )[i - 1] %= 10; }
        while( back( ) >= 10 ){ push_back( back( ) / 10 ); ( *this )[size( ) - 2] %= 10; }
        return *this;
    }
    bigInt( long long tpN = 0 ){ push_back( tpN ); check( ); }
};
istream &operator >> ( istream &is, bigInt &tpN ){
    string s;
    is >> s; tpN.clear( );
    for( int i = s.size( ) - 1; i >= 0; --i ) tpN.push_back( s[i] - '0' );
    return is;
}
ostream &operator << ( ostream &os, const bigInt &tpN ){
    if( tpN.empty( ) )    os << 0;
    for( int i = tpN.size( ) - 1; i >= 0; --i )    os << tpN[i];
    return os;
}
bool operator != ( const bigInt &one, const bigInt &another ){
    if( one.size( ) != another.size( ) )    return 1;
    for( int i = one.size( ) - 1; i >= 0; --i ){
        if( one[i] != another[i] )    return 1;
    }
    return 0;
}
bool operator == ( const bigInt &one, const bigInt &another ){
    return ! ( one != another );
}
bool operator < ( const bigInt &one, const bigInt &another ){
    if( one.size( ) != another.size( ) )    return one.size( ) < another.size( );
    for( int i = one.size( ) - 1; i >= 0; --i ){
        if( one[i] != another[i] )    return one[i] < another[i];
    }
    return 0;
}
bool operator > ( const bigInt &one, const bigInt &another ){ return another < one; }
bool operator <= ( const bigInt &one, const bigInt &another ){ return ! (one > another ); }
bool operator >= ( const bigInt &one, const bigInt &another ){ return ! (one < another ); }
bigInt &operator += ( bigInt &one, const bigInt &another ){
    if( one.size( ) < another.size( ) )    one.resize(another.size( ) );
    for( unsigned i = 0; i != another.size( ); ++ i ) one[i] += another[i];
    return one.check( );
}
bigInt operator + ( bigInt one, const bigInt &another ){ return one += another; }
bigInt &operator -= ( bigInt &one, bigInt another ){
    if( one < another )    swap( one, another );
    for( unsigned i = 0; i != another.size( ); one[i] -= another[i], ++ i ){
        if( one[i] < another[i] ){
            unsigned j = i + 1;
            while( ! one[j] ) ++ j;
            while( j > i ){ -- one[j]; one[--j] += 10; }
        }
    }
    return one.check( );
}
bigInt operator - ( bigInt one, const bigInt &another ){ return one -= another; }
bigInt operator * ( const bigInt &one, const bigInt &another ){
    bigInt tpN;
    tpN.assign( one.size( ) + another.size( ) - 1, 0 );
    for( unsigned i = 0; i != one.size( ); ++ i ){
        for( unsigned j = 0; j != another.size( ); ++ j ) tpN[i + j] += one[i] * another[j];
    }
    return tpN.check( );
}
bigInt &operator *= ( bigInt &one, const bigInt &another ){ return one = one * another; }
bigInt divMod( bigInt &one, const bigInt &another ){
    bigInt ans;
    for( int t = one.size( ) - another.size( ); one >= another; -- t ){
        bigInt tpS;
        tpS.assign( t + 1, 0 );
        tpS.back( ) = 1;
        bigInt tpM = another * tpS;
        while( one >= tpM ){ one -= tpM; ans += tpS; }
    }
    return ans;
}
bigInt operator / ( bigInt one, const bigInt &another ){ return divMod(one, another ); }
bigInt &operator /= ( bigInt &one, const bigInt &another ){ return one = one / another; }
bigInt &operator %= ( bigInt &one, const bigInt &another ){ divMod( one, another ); return one; }
bigInt operator % ( bigInt one, const bigInt &another ){ return one %= another; }
char s[70];
int n,cntot;
bigInt m,num[70],mx;
bool check(bigInt bas)
{
    bigInt res=0,sab=1;
    for(int i=1;i<=cntot;++i)
    {
        res+=num[i]*sab;
        sab*=bas;
        if(res>m)    return false;
    }
    return true;
}
int main()
{
    cin>>(s+1)>>m;
    n=strlen(s+1);
    for(int i=n;i>=1;--i)
    {
        num[++cntot]=s[i]-'0';
        mx=max(mx,num[cntot]);
    }
    if(cntot==1)    cout<<(num[cntot]<=m)<<"\n";
    else
    {
//        bigInt l=0,r=1e18,ans=0;
//        while(l<=r)
//        {
//            bigInt mid=(l+r)/2;
//            if(check(mid))
//            {
//                l=mid+1;
//                ans=mid;
//            }
//            else    r=mid-1;
//        }
//        bigInt l=mx,r=m+1;
//        while(l+1<r)
//        {
//            bigInt mid=(l+r)/2;
//            if(check(mid))    l=mid;
//            else    r=mid;
//        }
        bigInt l=mx+1,r=m+1,ans=mx;
        while(l<=r)
        {
            bigInt mid=(l+r)/2;
            if(check(mid))    l=mid+1,ans=mid;
            else    r=mid-1;
        }
        cout<<ans-mx<<"\n";
    }
    return 0;
}

「ABC 192E」Train

Link.

我也不知道我怎么过的，反正就是 Dijkstra 板子套上去后把 if(dis[y]>dis[x]+z) 改成了 if(dis[y]>get(dis[x],k)+z)，其中 get(dis[x],k) 就是算下一班车来的时间加上 dis[x] 本身。

然后就莫名其妙过了，可能算个贪心？

#include<queue>
#include<cstdio>
using namespace std;
const long long INF=1e18;
priority_queue<pair<long long,long long>,vector<pair<long long,long long> >,greater<pair<long long,long long> > > q;
vector<pair<long long,pair<long long,long long> > > e[100010];
long long n,m,st,ed,dis[100010],vis[100010];
long long get(long long val,long long k)
{
    if(val%k==0)    return val;
    else    return val+k-(val%k);
}
void find()
{
    for(long long i=1;i<=n;++i)    dis[i]=INF;
    dis[st]=0;
    q.push(make_pair(dis[st],st));
    while(!q.empty())
    {
        long long now=q.top().second;
        q.pop();
        if(!vis[now])
        {
            vis[now]=1;
            for(long long i=0;i<e[now].size();++i)
            {
                long long y=e[now][i].first,w=e[now][i].second.first,k=e[now][i].second.second;
                if(dis[y]>get(dis[now],k)+w)
                {
                    dis[y]=get(dis[now],k)+w;
                    q.push(make_pair(dis[y],y));
                }
            }
        }
    }
}
int main()
{
    scanf("%lld %lld %lld %lld",&n,&m,&st,&ed);
    for(long long i=1;i<=m;++i)
    {
        long long u,v,w,k;
        scanf("%lld %lld %lld %lld",&u,&v,&w,&k);
        e[u].push_back(make_pair(v,make_pair(w,k)));
        e[v].push_back(make_pair(u,make_pair(w,k)));
    }
    find();
    printf("%lld\n",dis[ed]==INF?-1:dis[ed]);
    return 0;
}

「ABC 192F」Potion

Link.

考虑枚举 $k$，设 $f_{i,j,c}$ 为前 $i$ 位选了 $j$ 个数 balabala。

我也不知道怎么 DP 的，可能是本能做出来的。

后面自己意会吧，反正也没难度了。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
long long n,x,a[110],f[110][110][110],ans=1145141919810233454;
int main()
{
    scanf("%lld %lld",&n,&x);
    for(int i=1;i<=n;++i)    scanf("%lld",&a[i]);
    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<=min(s,i);++j)
            {
                for(int k=0;k<n;++k)    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)    ans=min(ans,(x-f[n][s][x%s])/s);
    }
    printf("%lld\n",ans);
    return 0;
}

Solution Set -「ABC 192」

「ABC 113A」Star

「ABC 192B」uNrEaDaBlE sTrInG

「ABC 192C」Kaprekar Number

「ABC 192D」Base n

「ABC 192E」Train

「ABC 192F」Potion