软件征途

2009年4月24日

A palindrome is a symmetrical string, that is, a string read identically from left to right as well as from right to left. You are to write a program which, given a string, determines the minimal number of characters to be inserted into the string in order to obtain a palindrome.

As an example, by inserting 2 characters, the string "Ab3bd" can be transformed into a palindrome ("dAb3bAd" or "Adb3bdA"). However, inserting fewer than 2 characters does not produce a palindrome.

Input

Your program is to read from standard input. The first line contains one integer: the length of the input string N, 3 <= N <= 5000. The second line contains one string with length N. The string is formed from uppercase letters from 'A' to 'Z', lowercase letters from 'a' to 'z' and digits from '0' to '9'. Uppercase and lowercase letters are to be considered distinct.

Output

Your program is to write to standard output. The first line contains one integer, which is the desired minimal number.

Sample Input

5
Ab3bd

Sample Output

Source

IOI 2000

[Submit] [Go Back] [Status] [Discuss]

//5042643 11410 1159 Memory Limit Exceeded   C++ 541B 2009-04-25 10:46:03
//5042698 11410 1159 Accepted 40676K 1454MS C++ 543B 2009-04-25 10:52:06
#include <iostream>
#define MAX 5002
using namespace std;
char str[MAX];
short dp[MAX][MAX]; //第一次用这种类型
int len;
int GetMin(int a,int b)
{
if(a>b)
  return b;
else
  return a;
}
int main()
{
int r,i,j;
while(scanf("%d",&len)!=EOF)
{
  scanf("%s",str+1);
  for(i=1;i<=len;i++)
   dp[i][i]=0;
  for(r=2;r<=len;r++)
   for(i=1;i<=len-r+1;i++)
   {
    j=i+r-1;
    if(str[j]==str[i])
     dp[i][j]=dp[i+1][j-1];
    else
     dp[i][j]=GetMin(dp[i+1][j]+1,dp[i][j-1]+1);
   }
  printf("%d\n",dp[1][len]);
}
return 0;
}

zoj2744 Palindromes

ZOJ Problem Set - 2744

Palindromes

Time Limit: 1 Second Memory Limit: 32768 KB

A regular palindrome is a string of numbers or letters that is the same forward as backward. For example, the string "ABCDEDCBA" is a palindrome because it is the same when the string is read from left to right as when the string is read from right to left.

Now give you a string S, you should count how many palindromes in any consecutive substring of S.

Input

There are several test cases in the input. Each case contains a non-empty string which has no more than 5000 characters.

Proceed to the end of file.

Output

A single line with the number of palindrome substrings for each case.

Sample Input

aba
aa

Sample Output

4
3

Author: LIU, Yaoting

Source: Zhejiang Provincial Programming Contest 2006
Submit Status

//1843510 2009-04-25 09:07:35 Memory Limit Exceeded 2744 C++ 0 32769 Wpl
//1843514 2009-04-25 09:21:07 Time Limit Exceeded 2744 C++ 1001 24612 Wpl
//1843524 2009-04-25 09:39:08 Accepted 2744 C++ 760 24612 Wpl
/*
最好边做边计算sum如果单独出来计算会超时
*/
#include <iostream>
#define MAX 5001
using namespace std;
bool mark[MAX][MAX];
char str[MAX];
int main()
{
int i,j,len,r;
while(scanf("%s",str+1)!=EOF)
{
  int sum=0;
  len=strlen(str+1);
  for(r=1;r<=len;r++)
   for(i=1;i<=len-r+1;i++)
   {
    j=i+r-1;
    if(i==j) //注意将这种情况统计在里面
    {
     mark[i][j]=1;
     sum++;
     continue;
    }
    if(j==i+1&&str[i]==str[j]) //注意将这种情况统计在里面
    {
     mark[i][j]=1;
     sum++;
     continue;
    }
    mark[i][j]=0;
    if(str[i]!=str[j])
     mark[i][j]=0;
    else
    {
     if(mark[i+1][j-1])
     {
      mark[i][j]=1;
      sum++;
     }
     else
      mark[i][j]=0;
    }
   }
  printf("%d\n",sum);
}
return 0;
}

poj1002 487-3279

487-3279

Time Limit: 2000MS		Memory Limit: 65536K
Total Submissions: 99181		Accepted: 16539

Description

Businesses like to have memorable telephone numbers. One way to make a telephone number memorable is to have it spell a memorable word or phrase. For example, you can call the University of Waterloo by dialing the memorable TUT-GLOP. Sometimes only part of the number is used to spell a word. When you get back to your hotel tonight you can order a pizza from Gino's by dialing 310-GINO. Another way to make a telephone number memorable is to group the digits in a memorable way. You could order your pizza from Pizza Hut by calling their ``three tens'' number 3-10-10-10.

The standard form of a telephone number is seven decimal digits with a hyphen between the third and fourth digits (e.g. 888-1200). The keypad of a phone supplies the mapping of letters to numbers, as follows:

A, B, and C map to 2
D, E, and F map to 3
G, H, and I map to 4
J, K, and L map to 5
M, N, and O map to 6
P, R, and S map to 7
T, U, and V map to 8
W, X, and Y map to 9

There is no mapping for Q or Z. Hyphens are not dialed, and can be added and removed as necessary. The standard form of TUT-GLOP is 888-4567, the standard form of 310-GINO is 310-4466, and the standard form of 3-10-10-10 is 310-1010.

Two telephone numbers are equivalent if they have the same standard form. (They dial the same number.)

Your company is compiling a directory of telephone numbers from local businesses. As part of the quality control process you want to check that no two (or more) businesses in the directory have the same telephone number.

Input

The input will consist of one case. The first line of the input specifies the number of telephone numbers in the directory (up to 100,000) as a positive integer alone on the line. The remaining lines list the telephone numbers in the directory, with each number alone on a line. Each telephone number consists of a string composed of decimal digits, uppercase letters (excluding Q and Z) and hyphens. Exactly seven of the characters in the string will be digits or letters.

Output

Generate a line of output for each telephone number that appears more than once in any form. The line should give the telephone number in standard form, followed by a space, followed by the number of times the telephone number appears in the directory. Arrange the output lines by telephone number in ascending lexicographical order. If there are no duplicates in the input print the line:

No duplicates.

Sample Input

12
4873279
ITS-EASY
888-4567
3-10-10-10
888-GLOP
TUT-GLOP
967-11-11
310-GINO
F101010
888-1200
-4-8-7-3-2-7-9-
487-3279

Sample Output

310-1010 2
487-3279 4
888-4567 3

Source

East Central North America 1999

[Submit] [Go Back] [Status] [Discuss]

#include <iostream>
#include <string>
#include <map>
using namespace std;
map<string,int>M;
map<string,int>::iterator p;
int main()
{
int n,len,i,k;
string str,temp;
while(scanf("%d",&n)!=EOF)
{
  M.clear();
  while(n--)
  {
   cin>>temp;
   len=temp.length();
   k=0;
   str="";
   for(i=0;i<len;i++)
   {
    if(temp[i]=='-')
     continue;
    else if(temp[i]>='A'&&temp[i]<='Z')
    {
     switch(temp[i])
     {
      case 'A':
      case 'B':
      case 'C':
       str+='2';
       k++;
       break;
      case 'D':
      case 'E':
      case 'F':
       str+='3';
       k++;
       break;
      case 'G':
      case 'H':
      case 'I':
       str+='4';
       k++;
       break;
      case 'J':
      case 'K':
      case 'L':
       str+='5';
       k++;
       break;
      case 'M':
      case 'N':
      case 'O':
       str+='6';
       k++;
       break;
      case 'P':
      case 'R':
      case 'S':
       str+='7';
       k++;
       break;
      case 'T':
      case 'U':
      case 'V':
       str+='8';
       k++;
       break;
      case 'W':
      case 'X':
      case 'Y':
       str+='9';
       k++;
       break;
     }
    }
    else
    {
     str+=temp[i];
     k++;
    }
    if(k==3)
    {
     str+='-';
     k++;
    }
   }
   if(M[str]==0)
    M[str]=1;
   else
    M[str]++;
  }
  bool mark=false;
  for(p=M.begin();p!=M.end();p++)
  {
   if(p->second>1)
   {
    cout<<p->first<<" "<<p->second<<endl;
    mark=true;
   }
  }
  if(!mark)
   cout<<"No duplicates."<<endl;
}
return 0;
}

2009年4月23日

poj3624 Charm Bracelet

Charm Bracelet

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 1783		Accepted: 780

Description

Bessie has gone to the mall's jewelry store and spies a charm bracelet. Of course, she'd like to fill it with the best charms possible from the N (1 ≤ N ≤ 3,402) available charms. Each charm i in the supplied list has a weight W_i (1 ≤ W_i ≤ 400), a 'desirability' factor D_i (1 ≤ D_i ≤ 100), and can be used at most once. Bessie can only support a charm bracelet whose weight is no more than M (1 ≤ M ≤ 12,880).

Given that weight limit as a constraint and a list of the charms with their weights and desirability rating, deduce the maximum possible sum of ratings.

Input

* Line 1: Two space-separated integers: N and M
* Lines 2..N+1: Line i+1 describes charm i with two space-separated integers: W_i and D_i

Output

* Line 1: A single integer that is the greatest sum of charm desirabilities that can be achieved given the weight constraints

Sample Input

Sample Output

Source

USACO 2007 December Silver

[Submit] [Go Back] [Status] [Discuss]

//5037530 11410 3624 Accepted 284K 250MS C++ 693B 2009-04-24 13:59:01
#include <iostream>
#define MAX 12882
using namespace std;
struct node
{
int w;
int v;
}data[MAX];
int dp[MAX],n,m;
void Init()
{
int i;
for(i=1;i<=n;i++)
  scanf("%d%d",&data[i].w,&data[i].v);
}
int GetMax(int a,int b)
{
if(a>b)
  return a;
else
  return b;
}
void Knapsack()
{
int i,j;
for(i=0;i<=m;i++)
{
  if(i>=data[n].w)
   dp[i]=data[n].v;
  else
   dp[i]=0;
}
for(i=n-1;i>=1;i--)
  for(j=m;j>=1;j--)
  {
   if(j>=data[i].w)
   {
    dp[j]=GetMax(dp[j],dp[j-data[i].w]+data[i].v);
   }
   else
    break;
  }
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
  Init();
  Knapsack();
  printf("%d\n",dp[m]);
}
return 0;
}

Time Limit: 3000MS		Memory Limit: 65536K
Total Submissions: 22525		Accepted: 7549

软件征途

我的资料

标签

存档

2009年4月24日

软件征途: poj 1159 Palindrome

poj 1159 Palindrome

zoj2744 Palindromes

poj1002 487-3279

2009年4月23日

poj3624 Charm Bracelet