マイクロソフト必応・英雄会第3回オンラインプログラミング大会:いくつのbing?
テーマの詳細
今回の大会はマイクロソフトが必ず辞書の冠名を冠し、必ず辞書(http://cn.bing.com/dict/?form=BDVSP4&mkt=zh-CN&setlang=ZH)はマイクロソフトが発売した次世代英語学習エンジンで、私たちがよく使う単語がたくさん収録されています.しかし、現実の生活では、規則のない文字列もよく見られ、辞書が正常に収録できないことがありますが、規則のない文字列から正規の単語を抽出することができますか?
例えば、異なる位置の文字「b」、「i」、「n」、「g」を切り取って単語「bing」に組み合わせた文字列「iinbinbing」がある.1から計数を開始すると、「b」「i」「n」「g」の4文字の出現位置はそれぞれ(4,5,6,10)(4,5,9,10)、(4,8,9,10)、(7,8,9,10)であるため、合計4単語「bing」に組み合わせることができる.
私达の问题は:今任意の文字列を与えて、ただ‘b’‘i’‘n’‘g’のこの4种类のアルファベットを小文字するだけで、すみません全部で何个の単语bingに组み合わせることができますか?
文字列の長さは10000を超えません.結果が大きい場合がありますので、10^9+7の余剰数を取った後の結果を出力してください.
方法2を選んで、結果は失敗しました!
方法1:再帰的過剰スタックオーバーフロー(文字列長は数百を超えてはならない)
今回の大会はマイクロソフトが必ず辞書の冠名を冠し、必ず辞書(http://cn.bing.com/dict/?form=BDVSP4&mkt=zh-CN&setlang=ZH)はマイクロソフトが発売した次世代英語学習エンジンで、私たちがよく使う単語がたくさん収録されています.しかし、現実の生活では、規則のない文字列もよく見られ、辞書が正常に収録できないことがありますが、規則のない文字列から正規の単語を抽出することができますか?
例えば、異なる位置の文字「b」、「i」、「n」、「g」を切り取って単語「bing」に組み合わせた文字列「iinbinbing」がある.1から計数を開始すると、「b」「i」「n」「g」の4文字の出現位置はそれぞれ(4,5,6,10)(4,5,9,10)、(4,8,9,10)、(7,8,9,10)であるため、合計4単語「bing」に組み合わせることができる.
私达の问题は:今任意の文字列を与えて、ただ‘b’‘i’‘n’‘g’のこの4种类のアルファベットを小文字するだけで、すみません全部で何个の単语bingに组み合わせることができますか?
文字列の長さは10000を超えません.結果が大きい場合がありますので、10^9+7の余剰数を取った後の結果を出力してください.
方法2を選んで、結果は失敗しました!
方法1:再帰的過剰スタックオーバーフロー(文字列長は数百を超えてはならない)
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Bing
{
/// <summary>
/// 、 ， ：b......g
/// 、 "b" "i" "n" ； "i" "n" ... "i" "n" 。
/// 、 "g" （ ）, ... "g"
/// 、 "b"（ ）, 、 ... "b"
/// </summary>
class Program
{
/// <summary>
/// b......g bing
/// </summary>
/// <param name="oldstr"> </param>
/// <param name="newstr"> ， "i" "n" </param>
/// <param name="count"> </param>
/// <returns></returns>
public static void getCount( string oldstr, string newstr, ref int count)
{
//newstr = "hjsdhifdnnsi";
int indexI = newstr.IndexOf('i' );
if (indexI > 0)
{
StringBuilder m = new StringBuilder();
StringBuilder n = new StringBuilder();
//m = new StringBuilder(newstr.Substring(indexI));
m = new StringBuilder (newstr).Remove(0, indexI);
// "i" "n"
count += ( from c in m.ToString() where c == 'n' select c).Count();
// "i"
//newstr = newstr.Remove(indexI, 1);
n = new StringBuilder (newstr).Remove(indexI, 1);
newstr = n.ToString();
m.Clear();
n.Clear();
//
getCount(oldstr, newstr, ref count);
}
else
{
if (oldstr.IndexOf('i' ) > 0 && oldstr.Length >= 4)
{
//b...g, 2 "g"
oldstr = oldstr.Remove(oldstr.Length - 1, 1).TrimEnd( new char [] { 'i', 'n', 'b' });
newstr = oldstr;
getCount(oldstr, newstr, ref count);
}
}
}
static void Main(string[] args)
{
int n = 0, count = 0, totalCount = 0;
string[] bing = new [] { "b", "i", "n" , "g" };
StringBuilder bingStringBuilder = new StringBuilder();
Random r = new Random();
for (int i = 0; i < 10000; i++)
{
n = r.Next(0, 4);
bingStringBuilder = bingStringBuilder.Append(bing[n]);
}
// ‘b’、‘i’、‘n’、‘g’ 10000
string bingStr = bingStringBuilder.ToString();
// bing b......g
bingStr = bingStr.TrimStart( new char [] { 'i', 'n', 'g' }).TrimEnd( new char [] { 'i', 'n', 'b' });
while ((from c in bingStr where c == 'b' select c).Count() != 0)
{
//b......g bing
getCount(bingStr, bingStr, ref count);
totalCount += count;
// "b"
bingStr = bingStr.Remove(0, 1);
//b......g, "b"
bingStr = bingStr.TrimStart( new char [] { 'i', 'n', 'g' });
count = 0;
}
Console.WriteLine(" ‘b’、‘i’、‘n’、‘g’ 10000 ：" + bingStringBuilder);
Console.WriteLine();
Console.WriteLine(" \"bing\" ：" + totalCount);
Console.WriteLine();
Console.WriteLine(" 10^9 + 7 ：" + totalCount % 1000000007 );
Console.ReadLine();
}
}
}
using System;
using System.Collections;
using System.Collections.Generic;
//using System.Linq;
using System.Text;
/// <summary>
/// ：
/// 、 ‘b’、‘i’、‘n’、‘g’ 10000 bingStr， iList gList "i","g"
/// 、 iList ， "i" "b" ； gList ， "i" "g" "n" 。
/// </summary>
public class Test
{
public static int howmany(string s)
{
return 0;
}
//start ： ， 。
public static void Main()
{
int n = 0;
long totalCount = 0;
string[] bing = new[] { "b", "i", "n", "g" };
StringBuilder bingStringBuilder = new StringBuilder();
List<int> iList = new List<int>();
List<int> gList = new List<int>();
Random r = new Random();
for (int i = 0; i < 1000; i++)
{
n = r.Next(0, 4);
bingStringBuilder = bingStringBuilder.Append(bing[n]);
if (bing[n] == "i")
{
iList.Add(i);
}
if (bing[n] == "g")
{
gList.Add(i);
}
}
// ‘b’、‘i’、‘n’、‘g’ 10000
string bingStr = bingStringBuilder.ToString();
foreach (int i in iList)
{
// "i"
string bingStrLeft = bingStr.Substring(0, i);
// "i" "b"
//int bCount = (from c in bingStrLeft where c == 'b' select c).Count();
int bCount = bingStrLeft.Replace("i", "").Replace("n", "").Replace("g", "").Length;
if (bCount > 0)
{
foreach (int g in gList)
{
// "i" "g"
if (g > i)
{
// "i" "g" ( "g")
string subBingStr = bingStr.Substring(i, g - i);
// "n"
//int nCount = (from c in subBingStr where c == 'n' select c).Count();
int nCount = subBingStr.Replace("b", "").Replace("i", "").Replace("g", "").Length;
// "i" "g" "bing"
totalCount += bCount * nCount;
}
}
}
}
Console.WriteLine(" ‘b’、‘i’、‘n’、‘g’ 10000( 1000) ：" + bingStr);
Console.WriteLine();
Console.WriteLine(" \"bing\" ：" + totalCount);
Console.WriteLine();
Console.WriteLine(" 10^9 + 7 ：" + (totalCount == 0 ? 0 : (totalCount % 1000000007)));
}
//end // ： ， 。
}