热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

HDU614017多校8HybridCrystals(思维题)

题目传送:HybridCrystalsProblemDescription>Kybercrystals,alsocalledthelivingcrystalorsimply

题目传送:

Hybrid Crystals Problem Description > Kyber crystals, also called the living crystal or simply the kyber, and known as kaiburr crystals in ancient times, were rare, Force-attuned crystals that grew in nature and were found on scattered planets across the galaxy. They were used by the Jedi and the Sith in the construction of their lightsabers. As part of Jedi training, younglings were sent to the Crystal Caves of the ice planet of Ilum to mine crystals in order to construct their own lightsabers. The crystal's mix of unique lustre was called "the water of the kyber" by the Jedi. There were also larger, rarer crystals of great power and that, according to legends, were used at the heart of ancient superweapons by the Sith.
>
> — Wookieepedia

Powerful, the Kyber crystals are. Even more powerful, the Kyber crystals get combined together. Powered by the Kyber crystals, the main weapon of the Death Star is, having the firepower of thousands of Star Destroyers.

Combining Kyber crystals is not an easy task. The combination should have a specific level of energy to be stablized. Your task is to develop a Droid program to combine Kyber crystals.

Each crystal has its level of energy (i-th crystal has an energy level of ai). Each crystal is attuned to a particular side of the force, either the Light or the Dark. Light crystals emit positive energies, while dark crystals emit negative energies. In particular,

* For a light-side crystal of energy level ai, it emits +ai units of energy.
* For a dark-side crystal of energy level ai, it emits ai units of energy.

Surprisingly, there are rare neutral crystals that can be tuned to either dark or light side. Once used, it emits either +ai or ai units of energy, depending on which side it has been tuned to.

Given n crystals' energy levels ai and types bi (1in), bi=N means the i-th crystal is a neutral one, bi=L means a Light one, and bi=D means a Dark one. The Jedi Council asked you to choose some crystals to form a larger hybrid crystal. To make sure it is stable, the final energy level (the sum of the energy emission of all chosen crystals) of the hybrid crystal must be exactly k.

Considering the NP-Hardness of this problem, the Jedi Council puts some additional constraints to the array such that the problem is greatly simplified.

First, the Council puts a special crystal of a1=1,b1=N.

Second, the Council has arranged the other n1 crystals in a way that
aij=1i1aj[bj=N]+j=1i1aj[bi=Lbj=L]+j=1i1aj[bi=Dbj=D](2in).
[cond] evaluates to 1 if cond holds, otherwise it evaluates to 0.

For those who do not have the patience to read the problem statements, the problem asks you to find whether there exists a set S{1,2,,n} and values si for all iS such that

iSaisi=k,

where si=1 if the i-th crystal is a Light one, si=1 if the i-th crystal is a Dark one, and si{1,1} if the i-th crystal is a neutral one.
 

 

Input The first line of the input contains an integer T, denoting the number of test cases.

For each test case, the first line contains two integers n (1n103) and k (|k|106). 

The next line contains n integer a1,a2,...,an (0ai103).

The next line contains n character b1,b2,...,bn (bi{L,D,N}).
 

 

Output If there exists such a subset, output "yes", otherwise output "no".  

 

Sample Input 25 9 1 1 2 3 4N N N N N 6 -101 0 1 2 3 1N L L L L D  

 

Sample Output yesno 神坑题,打死一大帮懒的,又打死一大帮视力不好的总而言之前面的aij=1i1aj[bj=N]+j=1i1aj[bi=Lbj=L]+j=1i1aj[bi=Dbj=D](2in).告诉你将组成一个连续区间,证明见此博客  2017多校八 1008题 hdu 6140 Hybrid Crystals 推理具体做法看官方题解即可 
 1 #include
2 #include
3 #include
4 #include
5 #include<string>
6 using namespace std;
7 const int maxn= 1005;
8 int aa[maxn];
9 char bb[maxn];
10
11
12 int main()
13 {
14 int T,n,k,a,b;
15 scanf("%d",&T);
16 while(T--)
17 {
18 a=0;b=0;
19 scanf("%d%d",&n,&k);
20 for(int i=0;i)
21 cin>>aa[i];
22 for(int i=0;i)
23 cin>>bb[i];
24 for(int i=0;i)
25 {
26 if(bb[i]=='N')
27 {
28 b+=abs(aa[i]);
29 a-=abs(aa[i]);
30 }
31 else if(bb[i]=='L')
32 b+=aa[i];
33 else
34 a-=aa[i];
35 }
36 if(k>=a&&k<=b)
37 printf("yes\n");
38 else
39 printf("no\n");
40 }
41 return 0;
42 }

 


推荐阅读
  • [大整数乘法] java代码实现
    本文介绍了使用java代码实现大整数乘法的过程,同时也涉及到大整数加法和大整数减法的计算方法。通过分治算法来提高计算效率,并对算法的时间复杂度进行了研究。详细代码实现请参考文章链接。 ... [详细]
  • CF:3D City Model(小思维)问题解析和代码实现
    本文通过解析CF:3D City Model问题,介绍了问题的背景和要求,并给出了相应的代码实现。该问题涉及到在一个矩形的网格上建造城市的情景,每个网格单元可以作为建筑的基础,建筑由多个立方体叠加而成。文章详细讲解了问题的解决思路,并给出了相应的代码实现供读者参考。 ... [详细]
  • 本文主要解析了Open judge C16H问题中涉及到的Magical Balls的快速幂和逆元算法,并给出了问题的解析和解决方法。详细介绍了问题的背景和规则,并给出了相应的算法解析和实现步骤。通过本文的解析,读者可以更好地理解和解决Open judge C16H问题中的Magical Balls部分。 ... [详细]
  • 本文介绍了UVALive6575题目Odd and Even Zeroes的解法,使用了数位dp和找规律的方法。阶乘的定义和性质被介绍,并给出了一些例子。其中,部分阶乘的尾零个数为奇数,部分为偶数。 ... [详细]
  • 也就是|小窗_卷积的特征提取与参数计算
    篇首语:本文由编程笔记#小编为大家整理,主要介绍了卷积的特征提取与参数计算相关的知识,希望对你有一定的参考价值。Dense和Conv2D根本区别在于,Den ... [详细]
  • 本文介绍了南邮ctf-web的writeup,包括签到题和md5 collision。在CTF比赛和渗透测试中,可以通过查看源代码、代码注释、页面隐藏元素、超链接和HTTP响应头部来寻找flag或提示信息。利用PHP弱类型,可以发现md5('QNKCDZO')='0e830400451993494058024219903391'和md5('240610708')='0e462097431906509019562988736854'。 ... [详细]
  • 前景:当UI一个查询条件为多项选择,或录入多个条件的时候,比如查询所有名称里面包含以下动态条件,需要模糊查询里面每一项时比如是这样一个数组条件:newstring[]{兴业银行, ... [详细]
  • 本文介绍了一个题目的解法,通过二分答案来解决问题,但困难在于如何进行检查。文章提供了一种逃逸方式,通过移动最慢的宿管来锁门时跑到更居中的位置,从而使所有合格的寝室都居中。文章还提到可以分开判断两边的情况,并使用前缀和的方式来求出在任意时刻能够到达宿管即将锁门的寝室的人数。最后,文章提到可以改成O(n)的直接枚举来解决问题。 ... [详细]
  • 3.223.28周学习总结中的贪心作业收获及困惑
    本文是对3.223.28周学习总结中的贪心作业进行总结,作者在解题过程中参考了他人的代码,但前提是要先理解题目并有解题思路。作者分享了自己在贪心作业中的收获,同时提到了一道让他困惑的题目,即input details部分引发的疑惑。 ... [详细]
  • IB 物理真题解析:比潜热、理想气体的应用
    本文是对2017年IB物理试卷paper 2中一道涉及比潜热、理想气体和功率的大题进行解析。题目涉及液氧蒸发成氧气的过程,讲解了液氧和氧气分子的结构以及蒸发后分子之间的作用力变化。同时,文章也给出了解题技巧,建议根据得分点的数量来合理分配答题时间。最后,文章提供了答案解析,标注了每个得分点的位置。 ... [详细]
  • 本文介绍了一种划分和计数油田地块的方法。根据给定的条件,通过遍历和DFS算法,将符合条件的地块标记为不符合条件的地块,并进行计数。同时,还介绍了如何判断点是否在给定范围内的方法。 ... [详细]
  • http:my.oschina.netleejun2005blog136820刚看到群里又有同学在说HTTP协议下的Get请求参数长度是有大小限制的,最大不能超过XX ... [详细]
  • 本文介绍了解决二叉树层序创建问题的方法。通过使用队列结构体和二叉树结构体,实现了入队和出队操作,并提供了判断队列是否为空的函数。详细介绍了解决该问题的步骤和流程。 ... [详细]
  • Python正则表达式学习记录及常用方法
    本文记录了学习Python正则表达式的过程,介绍了re模块的常用方法re.search,并解释了rawstring的作用。正则表达式是一种方便检查字符串匹配模式的工具,通过本文的学习可以掌握Python中使用正则表达式的基本方法。 ... [详细]
  • 《数据结构》学习笔记3——串匹配算法性能评估
    本文主要讨论串匹配算法的性能评估,包括模式匹配、字符种类数量、算法复杂度等内容。通过借助C++中的头文件和库,可以实现对串的匹配操作。其中蛮力算法的复杂度为O(m*n),通过随机取出长度为m的子串作为模式P,在文本T中进行匹配,统计平均复杂度。对于成功和失败的匹配分别进行测试,分析其平均复杂度。详情请参考相关学习资源。 ... [详细]
author-avatar
a105451223
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有