首页
关于
笔记
文章
友链

Solution Set -「ABC 192」

cirnovsky /

☆ 「ABC 113A」Star

Link.

略。

#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.

考虑枚举 kk，设 fi,j,cf_{i,j,c} 为前 ii 位选了 jj 个数 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;
}