幻想扑克牌题解

cq_zry · 2022-12-06 18:06:42 · 个人记录

【题意解释】

先将 l 至 r 区间中所有数字进行 k 次操作，每次操作的规则如下：

将扑克牌翻转 r-l+1 次。其中第 i 次翻转时，从左往右数 i 张扑克牌，将其全部翻转至另一面，并将其顺序调换。
将扑克牌翻转 r-l 次。其中第 i 次翻转时，从左往右数 r-l+1-i 张扑克牌，将其全部翻转至另一面，并将其顺序调换。

进行了 k 次操作，并将所有背面朝上的扑克牌丢弃。从左往右输出剩下的每个数。

然后给定 m 个数字，并将其按照一定顺序排列好后，与上面剩下的数字都从左往右相比较。如果给定的数字小于其相对应的数字，则用该数字后面一个数字进行比较。直到给定的数字比较完或剩下的数字全部消失为止。

【模拟分析】

按照题目要求模拟即可。其中，我们定义一个布尔类型的数组，用来记录每张扑克牌的正反面情况。

接着，我们来想决斗的过程。因为我们可以将扑克牌 b 进行排序，且 a 的顺序一定。所以为了获得胜利，我们需要尽可能地让每个 B_i 都大于等于 A_i。于是我们将 b 按照从大到小排序，再将 a 从大到小排序。这样虽然违背了题意，但是也不影响我们计算。在排序完之后，我们只需枚举 a，若 B_i<A_i，此时的 B_i 已经是最大的了，所以一定失败，输出 NO。若全部满足，输出 YES 就行啦。

【模拟代码】

#include<bits/stdc++.h>
using namespace std;
#define int long long
int m,n,k;
int a[30000000],u[30000000];
int l,r;
int N;
bool b[30000000];
bool cmp(int x,int y)
{
    return x>y;
}
int main()
{
    ios::sync_with_stdio(0),cin.tie(),cout.tie();
    memset(b,1,sizeof(b));//开始是都是正面朝上
    cin>>n>>k>>m;
    for(int i=1;i<=n;i++) 
    {
        cin>>a[i];
    }
    cin>>l>>r;  
    n=0;//取出的扑克牌张数
    for(int i=l;i<=r;i++)
    {
        a[++n]=a[i];
    }
    for(int kkk=0;kkk<k;kkk++)//操作k次
    {
        for(int i=1;i<=r-l+1;i++)
        {
            reverse(a+1,a+i+1);//调换顺序
            for(int j=1;j<=i;j++)//翻转
            {
                b[j]=(b[j]?false:true);
            }
            reverse(b+1,b+i+1);
        }
        for(int i=1;i<=r-l;i++)
        {
            reverse(a+1,a+r-l-i+2);//调换顺序
            for(int j=1;j<=r-l-i+1;j++)//翻转
            {
                b[j]=(b[j]?false:true);
            }
            reverse(b+1,b+r-l-i+2);
        }
    }   
    for(int i=1;i<=n;i++)
    {
        if(b[i]==1)//正面朝上 
        {
            a[N++]=a[i];
        }
    }
    for(int i=0;i<N;i++)//输出
    {
        cout<<a[i]<<' ';
    }   
    for(int i=0;i<m;i++) 
    {
        cin>>u[i];
    }   
    if(N>m)
    {
        cout<<endl<<"NO";
        return 0;
    }
    sort(a,a+N,cmp);
    sort(u,u+m,cmp);
    for(int i=0;i<N;i++)
    {
        if(u[i]<a[i])
        {
            cout<<endl<<"NO";
            return 0;
        }
    }
    cout<<endl<<"YES";  
    return 0;
}

可以得到 20 分。

【正解分析】

我们模拟样例 1 发现：对于取出的牌数量为偶数且 k 为奇数时，所以的牌以 2 个为一组交换了位置。若将样例 1 中的 k 改为 2（偶数），重新模拟样例，又能发现：对于取出的牌数量为偶数且 k 为偶数时，所有牌的位置不变。

我们模拟样例 2 发现：对于取出的牌数量为奇数且 k 为奇数时，第一张牌背面朝上，丢弃，其余的牌以 2 个为一组交换了位置。若将样例 2 中的 k 改为 2（偶数），重新模拟样例，又能发现：对于取出的牌数量为奇数且 k 为偶数时，所有牌的位置不变。

综上，得到以下规律：

当取出的牌数量为偶数，k 为奇数时，所以的牌以 2 个为一组交换位置。
当取出的牌数量为奇数，k 为奇数时，丢弃第一个张牌，其余的牌以 2 个为一组交换位置。
当 k 为偶数时，所以的牌均正面朝上且位置不变。

那么，根据上面的规律，我们就可以用 O(\frac{r-l+1}{2}) 的时间复杂度完成这 k 次操作啦。

决斗过程同上，不多赘述。

【正解代码】

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,k;
int l,r;
int a[30000000];
int A[30000000];
int idx;//取出的扑克牌张数
int b[30000000];
bool cmp(int x,int y)
{
    return x>y;
}
signed main()
{
    ios::sync_with_stdio(0),cin.tie(),cout.tie();
    cin>>n>>k>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>A[i];
    }
    cin>>l>>r;
    for(int i=l;i<=r;i++)
    {
        a[++idx]=A[i];
    }
    for(int i=1;i<=m;i++)
    {
        cin>>b[i];
    }
    if(idx&1)//按照规律进行计算
    {
        if(k&1)
        {
            for(int i=2;i<idx;i+=2)
            {
                swap(a[i],a[i+1]);//交换  
                a[i-1]=a[i];//因为第一张牌是背面，所以每张牌往前移一位
                a[i]=a[i+1];
            }
            idx--;//牌数减一
        }
    }
    else
    {
        if(k&1)
        {
            for(int i=1;i<idx;i+=2)
            {
                swap(a[i],a[i+1]);//交换
            }   
        }
    }
    for(int i=1;i<=idx;i++)//输出
    {
        cout<<a[i]<<" ";
    }
    cout<<endl; 
    if(idx>m)//给定牌数不足，一定失败
    {
        cout<<"NO";
        return 0;
    }
    else
    {
        sort(a+1,a+idx+1,cmp);//排序
        sort(b+1,b+m+1,cmp);        
        for(int i=1;i<=idx;i++)
        {
            if(b[i]<a[i])//失败
            {
                cout<<"NO";
                return 0;
            }
        }   
        cout<<"YES";
        return 0;
    }   
    return 0;
}

幻想扑克牌 题解