A.Lucky Numbers
题意:给一个区间[l,r],任意给出一个数,使得各个数位上的最大值减去最小值最大,比如1735=7-1
Solution
暴力
对于r-l+1>=200的区间,一定存在一个值使得最大值为9,最小值为0
对于r-l+1<200的区间,直接暴力找
void solve()
{
int l,r;cin>>l>>r;
if(r-l+1>=200)
{
cout<<((l+100)/100)*100+9<<"\n";
}else
{
int ans=0;
int ans1=l;
for(int i=l;i<=r;i++)
{
int temp=i;
int maxx=0,minn=9;
while(temp>0)
{
int x=temp%10;
maxx=max(maxx,x);
minn=min(minn,x);
temp/=10;
}
if(ans<maxx-minn)
{
ans1=i;ans=maxx-minn;
}
}
cout<<ans1<<"\n";
}
}
B.Playing in a Casino
题意:给出n张卡牌,每张上面有m个数a1,a2,...,am,每名玩家都将拿到一张卡牌,并且相互进行比赛,胜者将拿到Σ|aik-ajk|的奖金,问一共需要多少奖金
Solution
将每一列上的数按从小到大排序,然后计算一下所有的差出现的次数即可
void solve()
{
int n,m;cin>>n>>m;
vector<vector<int> >a(n+5,vector<int>(m+5));
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>a[i][j];
}
}
int ans=0;
for(int j=1;j<=m;j++)
{
vector<int>v;
for(int i=1;i<=n;i++)
{
v.push_back(a[i][j]);
}
sort(v.begin(),v.end());
for(int i=0;i+1<v.size();i++)
{
ans+=(i+1)*(v.size()-i-1)*(v[i+1]-v[i]);
}
}
cout<<ans<<"\n";
}
C.Unlucky Numbers
题意:同题A一样,不过求的是最小的数
Solution
贪心,对于区间[l,r],如果有进位,那么一定会出现一个数由9组成,例如[150,2345],答案可以是999
我们来想没有进位的情况,枚举数位最小值min和最大值max,然后尽可能的将答案往l靠
枚举答案与l相同的前几位数,然后剩下的数用枚举的min和max组成,最高那位用max,剩下的都用min
代码写的很烂,不推荐看
void solve()
{
int ll,rr;cin>>ll>>rr;
if(ll==rr||ll<10)
{
cout<<ll<<"\n";
return;
}
int temp=rr;
int cnt1=0;
while(temp>0)
{
b[++cnt1]=temp%10;
temp/=10;
}
temp=ll;
int cnt2=0;
while(temp>0)
{
a[++cnt2]=temp%10;
temp/=10;
}
if(cnt1>cnt2)
{
for(int i=1;i<=cnt2;i++)cout<<"9";
cout<<"\n";
return;
}
int ans1=10,ans2=INF;
for(int l=0;l<10;l++)
{
for(int r=l;r<10;r++)
{
for(int i=1;i<=cnt2;i++) //从第i位开始由枚举的l和r醉成
{
int x=0; //组成的答案
for(int j=1;j<=i-1;j++) //前i-1位与l相同
{
x*=10;
x+=a[cnt2-(j-1)];
}
x*=10;
x+=r;
for(int j=i+1;j<=cnt2;j++)
{
x*=10;
x+=l;
}
int tt=0;
int temp=x;
int maxx=0;
int minn=10;
while(temp>0)
{
maxx=max(temp%10,maxx);
minn=min(temp%10,minn);
temp/=10;
}
tt=maxx-minn;
//cout<<tt<<" "<<x<<"\n";
if(x>=ll&&x<=rr&&ans1>tt) //判断x是否合法
{
ans1=tt;
ans2=x;
}
}
}
}
cout<<ans2<<"\n";
}