蓝桥杯算法训练 Cowboys By Assassin dp+字符串操作

2019-11-06 07:17:09

字体：大中小

来源：转载

供稿：网友

问题描述　　一个间不容发的时刻：n个牛仔站立于一个环中，并且每个牛仔都用左轮手枪指着他旁边的人！每个牛仔指着他顺时针或者逆时针方向上的相邻的人。正如很多西部片那样，在这一刻，绳命是入刺的不可惜……对峙的场景每秒都在变化。每秒钟牛仔们都会分析局势，当一对相邻的牛仔发现他们正在互指的时候，就会转过身。一秒内每对这样的牛仔都会转身。所有的转身都同时在一瞬间发生。我们用字母来表示牛仔所指的方向。“A”表示顺时针方向，“B”表示逆时针方向。如此，一个仅含“A”“B”的字符串便用来表示这个由牛仔构成的环。这是由第一个指着顺时针方向的牛仔做出的记录。例如，牛仔环“ABBBABBBA”在一秒后会变成“BABBBABBA”；而牛仔环“BABBA”会变成“ABABB”。这幅图说明了“BABBA”怎么变成“ABABB” 一秒过去了，现在用字符串s来表示牛仔们的排列。你的任务是求出一秒前有多少种可能的排列。如果某个排列中一个牛仔指向顺时针，而在另一个排列中他指向逆时针，那么这两个排列就是不同的。输入格式　　输入数据包括一个字符串s，它只含有“A”和“B”。输出格式　　输出你求出来的一秒前的可能排列数。数据规模和约定　　s的长度为3到100（包含3和100）样例输入BABBBABBA样例输出2样例输入ABABB样例输出2样例输入ABABAB样例输出4样例说明测试样例一中，可能的初始排列为："ABBBABBAB"和 "ABBBABBBA"。测试样例二中，可能的初始排列为："AABBB"和"BABBA"。

思路：说真的是一个dp无疑，但是这个题目我做了将近两个小时！蓝桥杯决赛题目还是很有难度的…对我这种垃圾来说…下面分享我的思路，不过可能麻烦.

首先我们需要注意一下条件A代表顺时针，B代表逆时针，那么转换一下相当于A 代表向右，B代表向左 （自己推一下样例就行，千万别把方向弄错了！！！）然后我们观察一下，像AB 这样的下一秒一定会变成BA 就是-> <-变成了<- ->，但是BA就不会动！

所以我们可以推断存在的BA可能是上一次BA留下没动产生的，也可能是AB换位后产生的。而AB这种不可能通过BA转换，只能是ABB转化产生的，这个对我们推导无益，不考虑。也就是说我们重点关注的是BA

再分析在下一秒对换过程中存在不反转的点，比如说ABBBAB 或者是ABAAAB，我们分析可以得到除了连续的BA以外的点都是不变的！

但是问题来了，那么连续的BABA是什么情况呢？我们分析假设XYYX，那么BA的情况数是可两个XX状态有关的！我们假定XX为稳定的变化边界，即边界内发生变化，变化不包括边界及以外（上一段已经分析的其他情况不会翻转了）下面构造YY，构造期间必须满足稳定性，边界不会改变！ XX==AA,那么现在是AYYB为了保证稳定，YY==AB XX==AB,那么现在是AYYB为了保证稳定，YY==AB XX==BA,那么现在是AYYB为了保证稳定，YY==AB||BA XX==BB,那么现在是AYYB为了保证稳定，YY==AB

然后我们再分析，KKXYYX是由XYYX得到的,就是XYYX的第一个X边界是KKXYYX的第二个数据值，第一个K最为新的边界，那么就有dp所要的条件了。比如AABXXA的答案就能通过BXXA得到！

那么就可以得到dp的关系式了！假定dp[i] [j]其中i表示BA的对数，j=0，1，2，3分别表示AA,AB,BA,BB为边界情况。那么就有关系是如下 dp[i][j]=⎧⎩⎨⎪⎪⎪⎪⎪⎪dp[i−1][2],dp[i−1][3],dp[i−1][0]+dp[i−1][2],dp[i−1][2],j==0j==1j==2j==3 $dp[i][j] =/begin{cases}dp[i-1][2], & /text{j==0} //dp[i-1][3], & /text{j==1}//dp[i-1][0]+dp[i-1][2], & /text{j==2}//dp[i-1][2], & /text{j==3}/end{cases}$

然后我们将所有情况对应的情况数相乘即可！

就是这样！那么接下来还有两个问题！ 1.确定连续BA的边界！ 2.这是一个环，可能存在ABBBB的情况！

那么我是这么处理的，先找到第一个连续的BA，那么取连续BA完成后的第一个数作为起点，去找BA，这样就保证，一定有最后是BA了！边界问题使用取模找到对应的值即可！

注意特例！ 1.如果是BABABA全串都是连续BA时，答案为dp[i-1][1]+dp[i-1][2] (i为连续BA的对数) 2.如果是全A或者全B不存在答案为0，没有翻转

讲完了，还是很复杂的…下面是代码，不太好懂，不好意思~

#include<bits/stdc++.h>using namespace std;long long dp[51][4]={0};int main(){ dp[1][0]=1; dp[1][1]=1; dp[1][2]=2; dp[1][3]=1; for(int i=2;i<=50;i++){ //打表dp情况数 dp[i][0]=dp[i-1][2]; dp[i][1]=dp[i-1][3]; dp[i][2]=dp[i-1][0]+dp[i-1][2]; dp[i][3]=dp[i-1][2]; } string target; int length,i; while(cin>>target){ length=target.size(); string tmp1="",tmp2=""; //检查是否存在全A或者全B情况 for(int k=0;i<length;k++){ tmp1+="A"; tmp2+="B"; } if(target==tmp1||target==tmp2){ cout<<0<<endl; return 0; } if(length%2==0){ tmp1=""; tmp2=""; for(int i=1;i<=length/2;i++){ //检查是否全串都是一个BA串！ tmp1+="AB"; tmp2+="BA"; } if(tmp1==target||tmp2==target){ cout<<dp[length/2-1][1]+dp[length/2-1][2]<<endl; return 0; } } for(i=0;i<length;i++){ //找到第一组BA开始位置 if(target[i]=='B'&&target[(i+1)%length]=='A'){ break; } } for(int j=i;;j=(j+2)%length){ //找到第一组BA结束位置 if(target[j]!='B'||target[(j+1)%length]!='A'){ i=j; break; } } int times=0,start,end; long long ans=1; for(int j=i;j<i+length;j++){ if(target[j%length]=='B'&&target[(j+1)%length]=='A'){ if(times==0){ start=(j+length-1)%length; //记录开始位置，记得-1 } times++; j++; //循环中有++那么这里再++就够了 } else { if(times!=0){ //如果已经记录了BA组数 end=j%length; //记录结束位置 if(target[start]=='A'&&target[end]=='A') ans*=dp[times][0]; else if(target[start]=='A'&&target[end]=='B') ans*=dp[times][1]; else if(target[start]=='B'&&target[end]=='A') ans*=dp[times][2]; else if(target[start]=='B'&&target[end]=='B') ans*=dp[times][3]; times=0; //一个串记录的组数清零 } } } if(times!=0){ //别忘了最后一组！看我实现构造的方法，最后一组是被忽略掉的 end=i%length; if(target[start]=='A'&&target[end]=='A') ans*=dp[times][0]; else if(target[start]=='A'&&target[end]=='B') ans*=dp[times][1]; else if(target[start]=='B'&&target[end]=='A') ans*=dp[times][2]; else if(target[start]=='B'&&target[end]=='B') ans*=dp[times][3]; } cout<<ans<<endl; } return 0;}

欢迎大家提问~

上一篇：Qt QComboBox自定义的下拉框

下一篇：maven+spring mvc环境搭建xml版（无web.xml，maven jetty插件运行）