Xingkong vs C++

C++ learning
随笔 - 5, 文章 - 0, 评论 - 2, 引用 - 0
数据加载中……

2008年6月3日

Google Top Coder 850分的题目

假设有这样一种字符串,它们的长度不大于26,而且若一个这样的字符串其长度为
m,则这个字符串必定由a, b, c, . . . , z 中的前m 个字母构成,同时我们保证每个字母出
现且仅出现一次。比方说某个字符串长度为5,那么它一定是由a, b, c, d, e 这5 个字母
构成,不会多一个也不会少一个。嗯嗯,这样一来,一旦长度确定,这个字符串中有哪些
字母也就确定了,唯一的区别就是这些字母的前后顺序而已。
现在我们用一个由大写字母A 和B 构成的序列来描述这类字符串里各个字母的前
后顺序:
1.         如果字母b 在字母a 的后面,那么序列的第一个字母就是A(After),否则序列的
第一个字母就是B(Before);
2.          如果字母c 在字母b 的后面,那么序列的第二个字母就是A,否则就是B;
3.          如果字母d 在字母c 的后面,那么⋯⋯不用多说了吧?直到这个字符串的结束。
这规则甚是简单,不过有个问题就是同一个AB 序列,可能有多个字符串都与之相
符,比方说序列"ABA",就有"acdb"、"cadb" 等等好几种可能性。说的专业一点,这一
个序列实际上对应了一个字符串集合。那么现在问题来了:给你一个这样的AB 序列,
问你究竟有多少个不同的字符串能够与之相符?或者说这个序列对应的字符串集合有多
大?注意,只要求个数,不要求枚举所有的字符串。
注:如果结果大于10 亿就返回-1。
我把题目总结为:给定一个字符串"ABAB..."(以下称为模式串),计算出符合要求的所有"abcd..."字符串(以下称为结果串)的个数.
要解答这个问题,首先需要明确两点(为什么就不要说了吧,呵呵):
1. 如果模式串的长度为n,那么结果串的长度为n+1
2. 一个模式串至少对应一个结果串,一个结果串对应而且只能对应一个模式串
下面我把我的思考过程写出来:
一. 从一个给定的模式串递推出所有的结果串,假设给定的模式串是"ABAB":
     1.对于第一个字母"A",那么结果串只能是"ab"
     2.对于第二个字母"B",说明c在b之前,而b之前有2个空位可以插入,所以可能的结果串是"cab","acb"
     3.对于第三个字母"A",说明d在c之后.在"cab"中,d可以插到3个空位中,可能的结果串是"cdab","cadb","cabd";在"acb"中,d可以插到2个空位中----"acdb","acbd".所以总的可能数是5
     4.对于第四个字母"B",同样的道理可以算出总的可能的结果串有16个.
二. 总结一下刚才的递推过程,可以发现每一次递推只和前一次递推的结果和模式串相应位置的字母有关,而模式串是给定的,所以确切的说,只和前一次递推结果中最大字母(最大字母指的是按字母排序的大小,如z>y>x>...>c>b>a)的位置有关.
现在有点事没时间写了,明天接着写,不过规律已经给出了,就是根据前一次结果的最大字母的位置来计算.大家可以先自己想想.
接着写.
既然找到了问题的本质,那么就构造一个数据结构存储每次递推的最大字母的位置即可.本题可以用一个简单数组记录便可.如下所示,用一个整型数组num记录.(数组的具体大小视情况而定,在此不做细究,题目中说不会大于26).num[a] = b的含义是,在位置a上(第a位上)最大字母出现的次数是b次.
const int maxNum = 30;
int num[maxNum];
string moduleString;记录模式串.
程序的思想是:
1.      输入模式串的长度为n时,从模式串的第一个字母开始递推.
2.      数组num的第一位即num[0]做边界处理,真正的记录从num[1]开始.
3.      在递推时,如果当前字母是”A”,那么只关心”这次最大字母”在”前一次递推的结果中最大字母”右边的情况有几种.如果是”B”,那么只关心”这次最大字母”在”前一次递推的结果中最大字母”左边的情况有几种
下面举个具体的例子来分析:以输出”ABAB”为例,每一行表示每次递推之后num数组的变化
模式串/位置
第零位
第一位
第二位
第三位
第四位
第五位
A
0
0
1
AB
0
1
1
0
ABA
0
0
1
2
2
ABAB
0
5
5
4
2
0
1)        A: 此时最大字母为b,显然它出现在第2位(记住第零位永远是0,真正的记录从第一位开始)
2)        AB:此时最大字母为c,它要求出现在b之前,分别是cab,acb.所以c在第一位,第二位上各出现一次.
3)        ABA: 此时最大字母为d,它要求出现在c之后.显然d出现在第一位是不可能的,所以在第一位出现的次数是0.因为c在前一次结果的第一位出现过一次,所以d在那种情况下可以在第二位出现一次.下面来看d在第三位可能出现的次数,因为前一次结果中,在第三位之前c出现过2次,那么d可以在那两种情况下出现在第三位,所以d在第三位出现的次数为2.最后看d在第四位出现的次数,还是因为前一次结果中c在第四位之前出现的次数是2次,所以d在第四位出现的次数是2
4)        ABAB:   此时最大字母是e,计算它出现的次数的方法和前面的一样,只是它要求是在前一次最大字母d的左边,只要反过来从右往左遍历就行了,在此不再累述

posted @ 2008-06-03 17:41 星空 阅读(494) | 评论 (0)编辑 收藏

Google 竞赛题 SecretSum

SecretSum 是本次 google 竞赛中第二轮淘汰赛的一道分值为 500 分竞赛题。事实上,这道题目反而比同轮比赛中的那道 1000 分值的RecurringNumbers 难(RecurringNumbers 的难度水准充其量不过是道初一学生奥数竞赛题)。好了,闲话少叙,来看 SecretSum 的题目吧:

一、竞赛题目

Problem Statement

We can substitute each digit of a number with a unique letter from ''A'' to ''Z''. This way we can write groups of numbers in a single representation. For example "ABA" can represent any of the following: 101, 151, 343, 767, 929. However, "ABA" cannot mean 555 because each letter must stand for a distinct digit. Furthermore, numbers cannot begin with 0 and thus ''A'' cannot be replaced by 0. Given two such representations num1 and num2 and the result of their summation return the total number of possible combinations of numbers for which the equation holds. If no combinations are possible then return 0.

Definition

Class: SecretSum
Method: countPossible
Parameters: String, String, String
Returns: int
Method signature: int countPossible(String num1, String num2, String result)
(be sure your method is public)

Constraints
- num1, num2, and result will each contain exactly 3 uppercase letters (''A'' - ''Z'').

Examples

0)

"AAA"
"BBB"
"CCC"
Returns: 32

1)

"ABB"
"DEE"
"TTT"
Returns: 112

2)

"ABC"
"ABA"
"ACC"
Returns: 0
Leading zeroes are not allowed.

3)

"AAA"
"CDD"
"BAA"
Returns: 32

4)

"TEF"
"FET"
"AAA"
Returns: 12

5)

"ABC"
"ABC"
"BCE"
Returns: 5
We can have the following 5 sums:
124 + 124 = 248
125 + 125 = 250
249 + 249 = 498
374 + 374 = 748
375 + 375 = 750


6)


"AAA"
"AAA"
"BBB"
Returns: 4
We can have the following 4 sums:
111 + 111 = 222
222 + 222 = 444
333 + 333 = 666
444 + 444 = 888


This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

posted @ 2008-06-03 17:38 星空 阅读(198) | 评论 (0)编辑 收藏

TopCoder真题

题目来源:SRM250 DIV2
级别:500Points
题目:
Problem Statement:
Problem Statement
    
For computers it can be hard to determine in which language a given text is written. A simple way to try to determine the language is the following: for the given text and for some sample texts, for which we know the languages, we determine the letter frequencies and compare these.
The frequency of a letter is the total number of occurrences of that letter divided by the total number of letters in the text. To determine this, we ignore case and non-letter characters.
Once the letter frequencies of the text and of a language are known, we can calculate the difference between the two. This difference we define by the sum of the squared differences of the frequencies:
 
The lesser this value, the closer text resembles that language. Compare text with each element of languages and return the (0-based) index of the language that has the smallest difference with text. In case of a tie, return the smallest index.
Definition
    
Class:
LanguageRecognition
Method:
whichLanguage
Parameters:
vector <string>, string
Returns:
int
Method signature:
int whichLanguage(vector <string> languages, string text)
(be sure your method is public)
    

Constraints
-
languages contains between 1 and 50 elements, inclusive.
-
Each element of languages has length between 1 and 50, inclusive.
-
text has length between 1 and 50, inclusive.
-
Each element of languages and text consists only of characters with ASCII value between 32 and 127, inclusive.
-
Each element of languages and text contains at least one letter ('A'-'Z' and 'a'-'z').
Examples
0)

    
{"This is an English sentence.",
 "Dieser ist ein Deutscher Satz.",
 "C'est une phrase Francaise.",
 "Dit is een Nederlandse zin."
}
"In welke taal is deze zin geschreven?"
Returns: 3
The differences are 0.0385, 0.0377, 0.0430 and 0.0276, so the sentence is written in language 3, Dutch. Note that Dutch is somewhat similar to German, somewhat less similar to English and not similar to French.
1)

    
{"aaaaa","bbbb","ccc","dd","e"}
"xxx"
Returns: 0
In case of a tie, return the language with the smallest index.
2)

    
{"AABB","AaBb","A? B!","ab!@#$%"}
"ab"
Returns: 0
Ignore case and the non-letter characters.

posted @ 2008-06-03 17:32 星空 阅读(522) | 评论 (0)编辑 收藏

优化的冒泡排序

//优化的冒泡排序
//编译成功

#include<iostream.h>
void swap(int a,int b);
int main()
{
 
 int a[10],i,j;
 for( i=0;i<10;i++)
 {
  cout<<"enter";
  cin>>a[i];
 }
 cout<<"数组的原次序为:";
 for( i=0;i<10;i++)
  cout<<a[i];
 for( i=0;i<9;i++)
 {
  int temp=0;
  for( j=8;j>i;j--)
  {
   if(a[j]<a[j-1])
   {
    swap(a[j],a[j-1]);
    temp=1;
   }
  }
  if(temp==0)
   break;
 }
cout<<"排序后次序为";
for(i=0;i<10;i++)
cout<<a[i];
 return 0;
}
void swap(int a,int b)
{
 int temp;
 temp=a;
 a=b;
 b=temp;
}

posted @ 2008-06-03 17:10 星空 阅读(501) | 评论 (1)编辑 收藏

kruskal算法实现

//给出kruskal球联通网络的最小生成树的算法实现
//调试成功
#include<iostream>
#include<stack>
using namespace std;
int main()
{
 stack<int> travstack;
 int i,j,k,n=5;
 cout<<"以矩阵形式表示"<<endl;
 int a[5][5],b[5][5],c[5][5],d[5];
 cout<<"请输入各路径权值";
 for( i=0;i<n;i++)
    for(j=i+1;j<n;j++)
 {
        cout<<"a[i][j]="<<endl;
        cin>>a[i][j];
 }
 int biggest=0,big=1000;
 for(k=0;k<n*n-n;k++)
     for(i=0;i<n;i++)
        for(j=i+1;j<n;j++)
  {
            if(a[i][j]>biggest&&a[i][j]<big)
   {
                 biggest=a[i][j];
                 travstack.push(i);
                 travstack.push(j);
   }
           big=a[i][j];
  }
 for(i=0;i<n;i++)
     for(j=0;j<n;j++)
  {
         int p1,p2;
         p1=travstack.top();//p1=j
         travstack.pop();
         p2=travstack.top();//p2=i
         travstack.pop();
         if(b[p1][p2]==0)
   {
            b[p1][p2]=1;
            b[p2][p1]=1;
            c[p2][p1]=a[p2][p1];
            if(d[p1]==0&&d[p2]==0)
              d[p1]=d[p2]=1;
  
            else if(d[p1]==0)
   {
              d[p1]=1;
              for( i=0;i<n;i++)
     {
                 if(b[p2][i]==1)
     {
                    b[p1][i]=1;
                    b[i][p1]=1;
     }
     }
   }
           else if(d[p2]==0)
     {
              d[p2]=1;
              for(i=0;i<n;i++)
     {
                 if(b[p1][i]==1)
     {
                    b[p2][i]=1;
                    b[i][p2]=1;
     }
     }
     }
   }
  }
  for(i=0;i<n;i++)
  {
      for(j=i+1;j<n;j++)
      cout<<"c[i][j]="<<c[i][j];
      cout<<endl;
      for(int k=0;k<n;k++)
      cout<<"*";
 }
 return 0;
}

posted @ 2008-06-03 17:06 星空 阅读(996) | 评论 (1)编辑 收藏