Spoon Taking Problem(c++题解)

2024-04-05 00:36
文章标签 c++ 题解 problem taking spoon

本文主要是介绍Spoon Taking Problem(c++题解),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目描述

�N 人が円卓に座っており,各人は反時計回りに順に 1, …, �1, …, N と番号付けられています.各人はそれぞれ左右どちらか一方の利き手を持っています.

円卓上には 1, …, �1, …, N と番号付けられた計 �N 本のスプーンが,隣り合う二人の間に 11 本ずつ置いてあります.各 1 ≤ � ≤ �1 ≤ i ≤ N について,人 �i の左側,右側にはそれぞれスプーン �i,スプーン (�+1)(i+1) があります.ここで,スプーン (�+1)(N+1) はスプーン 11 のことを指します.

� = 4N = 4 での模式図を以下に示します.

(1, …, �)(1, …, N) の順列 (�1, …, ��)(P1​, …, PN​) が与えられます.�=1,…,�i=1,…,N の順に,人 ��Pi​ が以下のように行動します.

  • 自分の右側または左側にスプーンが残っているならば,そのうち 11 つを取る.
    • このとき自分の両側にスプーンが残っているならば,自分の利き手の側のスプーンを取る.
  • そうでないならば何もしない.

LR? からなる長さ �N の文字列 �S が与えられます.�N 人の利き手の組み合わせは 2�2N 通りありますが,そのうち以下の条件を全て満たすような組み合わせの数を 998244353998244353 で割った余りを求めてください.

  • �S の �i 番目の文字が L ならば,人 �i は左利きである.
  • �S の �i 番目の文字が R ならば,人 �i は右利きである.
  • 全員の行動が終了したとき,全員がスプーンを取っている.

输入格式

入力は以下の形式で標準入力から与えられる.

�N �1P1​ …… ��PN​ �S

输出格式

答えを 11 行に出力せよ.

题意翻译

问题陈述

有 �N 人围坐在一张圆桌旁,按逆时针顺序编号为 11 至 �N 。每个人都有一只优势手:左手或右手。

圆桌上有 �N 个勺子,编号从 11 到 �N ,每对相邻的人中间放一个勺子。在每个 1≤�≤�1≤i≤N 人 �i 的左边和右边,分别有勺子 �i 和 (�+1)(i+1) 。这里,勺子 (�+1)(N+1) 指的是勺子 11 。

下图是 �=4N=4 的示意图。

给定一个 (1,…,�)(1,…,N) 的排列组合 (�1,…,��)(P1​,…,PN​) ,这 �n 个人按照此排列的顺序行动。第 ��Pi​ 个人的行为如下:

  • 如果左侧或右侧有剩余的勺子,他们将拿走其中一个。
    • 如果两边都有剩余的勺子,他们会拿自己惯用手一边的勺子。
  • 否则,他们什么也不会做。

我们还给出了一个长度为 �N 的字符串 �S ,由 LR 和 ? 组成。在 2�2N 种可能的惯用手组合中,求有多少种满足以下所有条件,模数为 998244353998244353 :

  • 如果 �S 的 �i 个字符是 "L",那么 �i 是左撇子。
  • 如果 �S 的第 �i 个字符是 "R",那么 �i 就是右撇子。
  • 当所有人都行动完后,每个人都拿了一个勺子。

输入输出样例

输入 #1复制

3
1 2 3
L??

输出 #1复制

2

输入 #2复制

3
1 3 2
R?L

输出 #2复制

0

输入 #3复制

12
6 2 9 3 1 4 11 5 12 10 7 8
????????????

输出 #3复制

160

说明/提示

制約

  • 入力される数値は全て整数
  • 2 ≤ � ≤ 2 × 1052 ≤ N ≤ 2 × 105
  • (�1, …, ��)(P1​, …, PN​) は (1, …, �)(1, …, N) の順列
  • �S は LR? からなる長さ �N の文字列

Sample Explanation 1

人 1,2,31,2,3 がそれぞれ左利き,左利き,右利きのとき,以下のように行動が行われます. - 人 11 が行動を開始する.人 11 の両側にスプーンが残っているので,人 11 の利き手と同じ左側のスプーン 11 を取る. - 人 22 が行動を開始する.人 22 の両側にスプーンが残っているので,人 22 の利き手と同じ左側のスプーン 22 を取る. - 人 33 が行動を開始する.人 33 の右側にはスプーンが残っておらず,左側にはスプーン 33 が残っているので,スプーン 33 を取る.全員の行動が終了し,このとき全員がスプーンを取っている. この利き手の組み合わせは条件を満たします.他には人 1,2,31,2,3 がそれぞれ左利き,左利き,左利きの場合も条件を満たします.

Sample Explanation 2

条件を満たす利き手の組み合わせが存在しません.

_____________________________________________________________________________

写作不易,点个赞呗!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! 

_____________________________________________________________________________

唉...一份超时代码:

#include <bits/stdc++.h>
using namespace std;
long long n,ans;
int a[200005];
int b[200005];//0为左1为右-1为未知 
bool c[200005];//标记 
string s;
bool check(){memset(c,0,sizeof(c));for(int i=1;i<=n;i++){int x=a[i];if(x!=n){if(c[x]&&c[x+1])return false;else if(!c[x]&&!c[x+1])c[x+b[x]]=true;else if(!c[x])c[x]=true;else if(!c[x+1])c[x+1]=true;}else{if(c[x]&&c[1])return false;else if(!c[x]&&!c[1]){if(b[x]==0)c[x]=true;else c[1]=true;}else if(!c[x])c[x]=true;else if(!c[1])c[1]=true;}}return true;
} 
void f(int x){if(x==n+1){if(check())ans=ans%998244353+1;return;}if(b[x]==-1){b[x]=1;f(x+1);b[x]=0;f(x+1);b[x]=-1;}else f(x+1);
}
int main(){cin>>n;for(int i=1;i<=n;i++)cin>>a[i];cin>>s;int len=s.size();for(int i=0;i<len;i++){if(s[i]=='L')b[i+1]=0;if(s[i]=='R')b[i+1]=1;if(s[i]=='?')b[i+1]=-1;}f(1);cout<<ans;
}	

这篇关于Spoon Taking Problem(c++题解)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/877222

相关文章

C++ 中的 if-constexpr语法和作用

《C++中的if-constexpr语法和作用》if-constexpr语法是C++17引入的新语法特性,也被称为常量if表达式或静态if(staticif),:本文主要介绍C++中的if-c... 目录1 if-constexpr 语法1.1 基本语法1.2 扩展说明1.2.1 条件表达式1.2.2 fa

C++中::SHCreateDirectoryEx函数使用方法

《C++中::SHCreateDirectoryEx函数使用方法》::SHCreateDirectoryEx用于创建多级目录,类似于mkdir-p命令,本文主要介绍了C++中::SHCreateDir... 目录1. 函数原型与依赖项2. 基本使用示例示例 1:创建单层目录示例 2:创建多级目录3. 关键注

C++从序列容器中删除元素的四种方法

《C++从序列容器中删除元素的四种方法》删除元素的方法在序列容器和关联容器之间是非常不同的,在序列容器中,vector和string是最常用的,但这里也会介绍deque和list以供全面了解,尽管在一... 目录一、简介二、移除给定位置的元素三、移除与某个值相等的元素3.1、序列容器vector、deque

C++常见容器获取头元素的方法大全

《C++常见容器获取头元素的方法大全》在C++编程中,容器是存储和管理数据集合的重要工具,不同的容器提供了不同的接口来访问和操作其中的元素,获取容器的头元素(即第一个元素)是常见的操作之一,本文将详细... 目录一、std::vector二、std::list三、std::deque四、std::forwa

C++字符串提取和分割的多种方法

《C++字符串提取和分割的多种方法》在C++编程中,字符串处理是一个常见的任务,尤其是在需要从字符串中提取特定数据时,本文将详细探讨如何使用C++标准库中的工具来提取和分割字符串,并分析不同方法的适用... 目录1. 字符串提取的基本方法1.1 使用 std::istringstream 和 >> 操作符示

C++原地删除有序数组重复项的N种方法

《C++原地删除有序数组重复项的N种方法》给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度,不要使用额外的数组空间,你必须在原地修改输入数组并在使用O(... 目录一、问题二、问题分析三、算法实现四、问题变体:最多保留两次五、分析和代码实现5.1、问题分析5.

C++ 各种map特点对比分析

《C++各种map特点对比分析》文章比较了C++中不同类型的map(如std::map,std::unordered_map,std::multimap,std::unordered_multima... 目录特点比较C++ 示例代码 ​​​​​​代码解释特点比较1. std::map底层实现:基于红黑

C++中函数模板与类模板的简单使用及区别介绍

《C++中函数模板与类模板的简单使用及区别介绍》这篇文章介绍了C++中的模板机制,包括函数模板和类模板的概念、语法和实际应用,函数模板通过类型参数实现泛型操作,而类模板允许创建可处理多种数据类型的类,... 目录一、函数模板定义语法真实示例二、类模板三、关键区别四、注意事项 ‌在C++中,模板是实现泛型编程

利用Python和C++解析gltf文件的示例详解

《利用Python和C++解析gltf文件的示例详解》gltf,全称是GLTransmissionFormat,是一种开放的3D文件格式,Python和C++是两个非常强大的工具,下面我们就来看看如何... 目录什么是gltf文件选择语言的原因安装必要的库解析gltf文件的步骤1. 读取gltf文件2. 提

C++快速排序超详细讲解

《C++快速排序超详细讲解》快速排序是一种高效的排序算法,通过分治法将数组划分为两部分,递归排序,直到整个数组有序,通过代码解析和示例,详细解释了快速排序的工作原理和实现过程,需要的朋友可以参考下... 目录一、快速排序原理二、快速排序标准代码三、代码解析四、使用while循环的快速排序1.代码代码1.由快