列表

详情

NC220364. F钓卡游戏

描述


Alice与Bob最近在玩一种卡牌游戏，规则如下：

牌库有 张牌。

一开始两个人手上没有卡牌。

在你的回合，你首先需要从牌库顶端抽一张卡牌，卡牌的数值只有 和 且 ，接着你可以选择

    1. 打出这张卡牌到得分区并获得这张卡对应数值的分数

    2. 把这张卡牌反盖在你的盖牌区的顶部

在对手的回合，如果对手打出的卡牌和你盖牌区顶部的卡牌数值一致，你可以翻开盖牌区顶部的牌放入你的得分区，并把对手打出的牌从对手的得分区钓入你的得分区。

Bob已经连胜Alice很多场了，Bob领先着Alice多达 分。

这时只剩下最后一场卡牌游戏，Bob认为Alice已经不可能翻盘，最后这场卡牌游戏Bob将一张不盖，完成绝杀。（即Bob只执行选择1）

但Alice在经过这么多的挫败以后，已经把整个牌库的牌记了下来，Alice想知道她有没有机会完成翻盘。

本场游戏Alice先手。如果最终分数相等则算作Bob胜利。



输入描述

第一行输入 T 表示 T 组数据.
接下来每组数据：
第一行输入 4 个整数 n,k,a,b 。
第二行输入  个数，表示牌库的抽取顺序。
保证。

输出描述

一行，输出 "Yes" 或 "No" 。

示例1

输入: 

1
3 0 1 2
1 2 1 2 1 2

输出: 

No

说明:


示例2

输入: 

1
3 3 2 1
2 1 2 1 1 1

输出: 

Yes

说明:

alice的牌序为221，可盖下1以钓取bob的牌111中最后一张1，最后alice为6分，bob为5分，故alice获胜。

示例3

输入: 

1
4 8 1 3
3 1 1 3 3 1 1 3

输出: 

Yes

说明:

alice的牌序为3131，bob的牌序为1313，alice可以盖下两张3把bob的两张3钓走，最后alice为14分，bob为10分，故alice获胜。

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++(clang++11) 解法, 执行用时: 591ms, 内存消耗: 15608K, 提交时间: 2021-04-01 11:56:35 

#include<bits/stdc++.h>
using namespace std;
int alice[1000000],bob[1000000];
char ch[1000000];
int main()
{
	int T;cin>>T;
	for(;T;T--){
		int n,k,a,b,sum=0,ln=0,rn=0,top=-1,res=0;
		cin>>n>>k>>a>>b;
		for(int i=0;i<n;i++){
			cin>>alice[i]>>bob[i];
			sum+=alice[i]+bob[i];
			if(alice[i]==bob[i]) res+=alice[i]*2;
			else res+=alice[i];
			if(alice[i]>bob[i]){
				ch[++top]='(';ln++;
			}
			if(alice[i]<bob[i]){
				if(top==-1||(top!=-1&&ch[top]==')')){
					ch[++top]=')';rn++;
				}
				else{
					top--;res+=max(a,b);ln--;
				}
			}
		}
		res+=min(a,b)*min(ln,rn);
		if((long long)2*res-sum>k) printf("Yes\n");
		else printf("No\n");
	}
}

上一题

© 2024 nowcoder.com