P8044 [COCI2015-2016#4] YODA 题解

· · 题解

题目大意

将两个数 m,n 的各个数位从低到高进行比较，较大的数留下，较小的数淘汰，两个数相等就都保留下来。如果一个数各个数位上的数全部都淘汰了，那么输出"YODA"。

思路

如何求出一个数各个数位上的数呢？那就是最基础的取模运算了。将一个数对 10 取模就能得到这个数上最低位上的数。

while(m)
{
    num=m%10;
    m/=10;
}

对于 m 和 n，我们只需将 m 和 n 各个数位上的数从低到高进行比较后，用栈保存，最后就能实现从高到低位输出。

stack<int> sta,stb;

while(1)
{
    p=n%10,q=m%10;
    if(p>q) sta.push(p);
    if(p<q) stb.push(q);
    if(p==q) sta.push(p),stb.push(q);
    n/=10,m/=10;
    if(!n&&!m) break;
}

最后还需要判断这个数是不是各个数位上的数全部都淘汰了。可以使用 STL 中 stack 自带的 empty() 函数判断该数是否还有“幸存者”。

if(sta.empty()) puts("YODA");//表示栈是否为空，若空返回的值为真

注意：有的时候剩下的数有前导零，需要将这些零扔掉。

code

#include<bits/stdc++.h>
using namespace std;
stack<int> sta,stb;
long long n,m;
int p,q;
bool fla,flb;
int main()
{
//  freopen("P8044.in","r",stdin);
//  freopen("P8044.out","w",stdout);
    scanf("%lld%lld",&n,&m);
    while(1)
    {
        p=n%10,q=m%10;
        if(p>q) sta.push(p);
        if(p<q) stb.push(q);
        if(p==q) sta.push(p),stb.push(q);
        n/=10,m/=10;
        if(!n&&!m) break;
    }
    if(sta.empty()) puts("YODA");
    else 
    {
        while(!sta.empty()) 
        {
            if(sta.top()) {printf("%d",sta.top());fla=1;}
            else {if(fla) printf("%d",sta.top());}
            sta.pop();
        }
        if(!fla) puts("0");
        else puts("");
    }
    if(stb.empty()) printf("YODA");
    else 
    {
        while(!stb.empty())
        {
        if(stb.top()) {printf("%d",stb.top());flb=1;}
        else {if(flb) printf("%d",stb.top());}
        stb.pop();
        }
        if(!flb) puts("0");
    }
    return 0;
}