Create your Gitee Account
Explore and code with more than 6 million developers,Free private repositories !:)
Sign up
This repository doesn't specify license. Without author's permission, this code is only for learning and cannot be used for other purposes.
Clone or download
ChuangGuanTest.h 3.00 KB
Copy Edit Web IDE Raw Blame History
fudum authored 2014-07-06 20:04 . 提交华为OJ程序
#pragma once
#include <string>
#include <vector>
//闯关测试
class ChuangGuanTest
{
public:
ChuangGuanTest(void);
~ChuangGuanTest(void);
/*
描述: 甲乙两个人用一个英语单词玩游戏。两个人轮流进行,每个人每次从中删掉
任意一个字母,如果剩余的字母序列是严格单调递增的(按字典序a < b < c
<....<z),则这个人胜利。两个人都足够聪明(即如果有赢的方案,都不会选输的方
案 ),甲先开始,问他能赢么? <><z),则这个人胜利。两个人都足够聪明(即如
果有赢的方案,都不会选输的方案 ),甲先开始,问他能赢么? <><z),则这个人
胜利。两个人都足够聪明(即如果有赢的方案,都不会选输的方案 ),甲先开始,
问他能赢么? <><z),则这个人胜利。两个人都足够聪明(即如果有赢的方案,都不
会选输的方案 ),甲先开始,问他能赢么? <>
输入: 一连串英文小写字母,长度不超过15,保证最开始的状态不是一个严格单增的
序列。
输出:1表示甲可以赢,0表示甲不能赢。
例如: 输入 bad, 则甲可以删掉b或者a,剩余的是ad或者bd,他就赢了,输出1。
又如: 输入 aaa, 则甲只能删掉1个a,乙删掉一个a,剩余1个a,乙获胜,输出0。
public static int who(String in);
知识点:
题目来源: 内部整理
练习阶段: 高级
运行时间限制: 10Sec
内存限制: 128MByte
输入:
输入一个字符串
输出:
输出计算
样例输入: bad
样例输出: 1
(摘录网络)解题思想:
甲乙两个人用一个英语单词玩游戏。两个人轮流进行,每个人每次从中删掉任意一个字母,如果剩余的字母序列是严格单调递增的(按字典序a<b<c)
输入:一连串英文小写字母,长度不超过15,保证最开始的状态不是一个严格单增的序列。
输出:1表示甲可以赢,0表示甲不能赢。
例如:输入bad,则甲可以删掉b或者a,剩余的是ad或者bd,他就赢了,输出1.
又如:输入aaa,则甲只能删掉1个a,乙删掉一个a,剩余1个a,乙获胜,输出0.
注:甲乙都足够聪明,能赢绝不会选输的那一个。
==================================================================================
最后那个注是我当时看题的时候有的,可是这次我再看题的时候,发现这个句话没了。
题目本质:
什么事情都要看其本质,这个题如果有最后那个注,那么这个题其实就是一个最优解的问题,我最后将其转为:在给定了一连串非严格单增序列中,找出最长的一串严格单增序列。如果没有那个注,那么就没有了限制,这样就没有了最终目的。而这道题,也没有要求说出最后的可能结果
解题思路:
看清了本质,那么解题思路就好说了。我为这个序列上的每个元素计算权。
权的定义为:
1.该元素的权为a,当且仅当该元素右边有a个比它大的元素,并且这些比它大的元素为严格单增序列。
2.若不满足1,将a减1,直到满足1为止。
计算每个元素的权,然后选出权最大的元素,用字符串长-权-1,就可以得出最少(因为甲乙足够聪明)去除的字符数。剩下的就是模2取余的事了。
而计算权的时候,个人感觉应该从右往左找:
例如:对于abdc这个来说,c、d的权都是0,对于b来说,右边有两个比它大的,所以此时权为2,但dc不是单增的,所以将权减1,此时为1,那么b的权就是1。
对于a来说,右边有3个比它大的,但它右边最大的权为1,所以a的权只能是2。
=================================================================================
思路就是这样一个思路,个人感觉这个是可实现的。如果有人用这个思路实现了,麻烦说下,有别的思路,也给分享下,锻炼一下逻辑能力。
*/
struct PM
{
char ch;
int quan;
};
int who(std::string in);
};

Comment ( 0 )

Sign in for post a comment