2009年4月24日
poj 1159 Palindrome
| Time Limit: 3000MS | Memory Limit: 65536K | |
| Total Submissions: 22525 | Accepted: 7549 |
Description
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
Output
Sample Input
5 Ab3bd
Sample Output
2
Source
[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
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
//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
| Time Limit: 2000MS | Memory Limit: 65536K | |
| Total Submissions: 99181 | Accepted: 16539 |
Description
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
Output
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
[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
| 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 Wi (1 ≤ Wi ≤ 400), a 'desirability' factor Di (1 ≤ Di ≤ 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: Wi and Di
Output
* Line 1: A single integer that is the greatest sum of charm desirabilities that can be achieved given the weight constraints
Sample Input
4 6 1 4 2 6 3 12 2 7
Sample Output
23
Source
[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;
}
zoj2339 Hyperhuffman
You might have heard about Huffman encoding - that is the coding system that minimizes the expected length of the text if the codes for characters are required to consist of an integral number of bits.
Let us recall codes assignment process in Huffman encoding. First the Huffman tree is constructed. Let the alphabet consist of N characters, i-th of which occurs Pi times in the input text. Initially all characters are considered to be active nodes of the future tree, i-th being marked with Pi. On each step take two active nodes with smallest marks, create the new node, mark it with the sum of the considered nodes and make them the children of the new node. Then remove the two nodes that now have parent from the set of active nodes and make the new node active. This process is repeated until only one active node exists, it is made the root of the tree.
Note that the characters of the alphabet are represented by the leaves of the tree. For each leaf node the length of its code in the Huffman encoding is the length of the path from the root to the node. The code itself can be constrcuted the following way: for each internal node consider two edges from it to its children. Assign 0 to one of them and 1 to another. The code of the character is then the sequence of 0s and 1s passed on the way from the root to the leaf node representing this character.
In this problem you are asked to detect the length of the text after it being encoded with Huffman method. Since the length of the code for the character depends only on the number of occurences of this character, the text itself is not given - only the number of occurences of each character. Characters are given from most rare to most frequent.
Note that the alphabet used for the text is quite huge - it may contain up to 500 000 characters.
This problem contains multiple test cases!
The first line of a multiple input is an integer N, then a blank line followed by N input blocks. Each input block is in the format indicated in the problem description. There is a blank line between input blocks.
The output format consists of N output blocks. There is a blank line between output blocks.
Input
The first line of the input file contains N - the number of different characters used in the text (2 <= N <= 500 000). The second line contains N integer numbers Pi - the number of occurences of each character (1 <= Pi <= 109, Pi <= Pi+1 for all valid i).
Output
Output the length of the text after encoding it using Huffman method, in bits.
Sample Input
1
3
1 1 4
Sample Output
8
Author: Andrew Stankevich
//1842068 2009-04-23 15:48:35 Accepted 2339 C++ 1170 10244 Wpl
#include <iostream>
#include <queue>
#define MAX 500000
using namespace std;
typedef struct node
{
long long w;
node(){}
node(long long ww)
{
w=ww;
}
friend bool operator<(node a,node b)
{
return a.w>b.w;
}
}Point;
priority_queue<Point>Q;
Point temp1,temp2,data[MAX];
int t,n;
void Init()
{
int i;
long long ww;
scanf("%d",&n);
while(!Q.empty())
Q.pop();
for(i=0;i<n;i++)
{
//scanf("%I64d",&ww);
cin>>ww;
data[i]=node(ww);
Q.push(data[i]);
}
}
long long HuffmanCodeLen()
{
long long sum=0;
if(n==1)
return data[0].w;
while(!Q.empty())
{
temp1=Q.top();
Q.pop();
if(!Q.empty())
{
temp2=Q.top();
Q.pop();
Q.push(node(temp1.w+temp2.w));
sum+=temp1.w+temp2.w;
}
}
return sum;
}
int main()
{
scanf("%d",&t);
while(t--)
{
Init();
//printf("%I64d\n",HuffmanCodeLen());
cout<<HuffmanCodeLen()<<endl;
if(t>0)
printf("\n");
}
return 0;
}
2009年4月22日
HOJ1015 合并果子
|
合并果子 Time Limit:2000MS Memory Limit:65536K Description 在一个果园里，果农已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。果农决定把所有的果子合成一堆。 Input 输入包含多组测试数据。每组输入数据包括两行，第一行是一个整数n( 1<＝n<=10000 )，表示果子的种类数。第二行包含n个整数，用空格分隔，第i个整数ai( 1<＝ai<=20000 )是第i种果子的数目。 Output 对应每组输入，输出包括一行，这一行只包含一个整数，也就是最小的体力耗费值。输入数据保证这个值小于2的31次方。 Sample Input
Sample Output
Source 校第三届大学生程序设计竞赛 |
[Submit] [Go Back] [Status] [Discuss]
Home Page 
Go Back 
To top
//6622 wupanlei 1015 Accepted 940K 166MS G++ 0.63K 2009-04-12 14:19:41
#include <iostream>
#include <queue>
using namespace std;
typedef struct node
{
int data;
friend bool operator < (node n1,node n2) //默认是最大堆
{
return n1.data>n2.data;
}
}Point;
priority_queue <node> Q;
Point p,m1,m2;
int main()
{
int n,a,sum;
while(scanf("%d",&n)!=EOF)
{
while(!Q.empty())
Q.pop();
while(n--)
{
scanf("%d",&a);
p.data=a;
Q.push(p);
}
sum=0;
while(!Q.empty())
{
m1=Q.top();
Q.pop();
if(!Q.empty())
{
m2=Q.top();
Q.pop();
p.data=m1.data+m2.data;
sum+=p.data;
Q.push(p);
}
}
printf("%d\n",sum);
}
return 0;
}
poj3253 Fence Repair
| Time Limit: 2000MS | Memory Limit: 65536K | |
| Total Submissions: 4038 | Accepted: 1251 |
Description
Farmer John wants to repair a small length of the fence around the pasture. He measures the fence and finds that he needs N (1 ≤ N ≤ 20,000) planks of wood, each having some integer length Li (1 ≤ Li ≤ 50,000) units. He then purchases a single long board just long enough to saw into the N planks (i.e., whose length is the sum of the lengths Li). FJ is ignoring the "kerf", the extra length lost to sawdust when a sawcut is made; you should ignore it, too.
FJ sadly realizes that he doesn't own a saw with which to cut the wood, so he mosies over to Farmer Don's Farm with this long board and politely asks if he may borrow a saw.
Farmer Don, a closet capitalist, doesn't lend FJ a saw but instead offers to charge Farmer John for each of the N-1 cuts in the plank. The charge to cut a piece of wood is exactly equal to its length. Cutting a plank of length 21 costs 21 cents.
Farmer Don then lets Farmer John decide the order and locations to cut the plank. Help Farmer John determine the minimum amount of money he can spend to create the N planks. FJ knows that he can cut the board in various different orders which will result in different charges since the resulting intermediate planks are of different lengths.
Input
Lines 2..N+1: Each line contains a single integer describing the length of a needed plank
Output
Sample Input
3 8 5 8
Sample Output
34
Hint
The original board measures 8+5+8=21. The first cut will cost 21, and should be used to cut the board into pieces measuring 13 and 8. The second cut will cost 13, and should be used to cut the 13 into 8 and 5. This would cost 21+13=34. If the 21 was cut into 16 and 5 instead, the second cut would cost 16 for a total of 37 (which is more than 34).
Source
[Submit] [Go Back] [Status] [Discuss]
//5030660 11410 3253 Wrong Answer C++ 1317B 2009-04-23 10:41:38
//5030756 11410 3253 Accepted 388K 32MS C++ 827B 2009-04-23 11:05:26
//注意用64位数字,和石子合并是一样的思路
#include <iostream>
#include <queue>
#define MAX 20002
using namespace std;
typedef struct node
{
int w;
node(){}
node(int ww)
{
w=ww;
}
friend bool operator<(node a,node b)
{
return a.w>b.w;
}
}Point;
priority_queue<Point>Q;
Point temp1,temp2;
int t,n;
void Init()
{
int i,ww;
while(!Q.empty())
Q.pop();
for(i=0;i<n;i++)
{
scanf("%d",&ww);
Q.push(node(ww));
}
}
__int64 Huffman()
{
__int64 sum=0;
if(n==1)
{
temp1=Q.top();
Q.pop();
return temp1.w;
}
while(!Q.empty())
{
temp1=Q.top();
Q.pop();
if(!Q.empty())
{
temp2=Q.top();
Q.pop();
Q.push(node(temp1.w+temp2.w));
sum+=temp2.w+temp1.w;
}
}
return sum;
}
int main()
{ while(scanf("%d",&n)!=EOF)
{
Init();
printf("%I64d\n",Huffman());
}
return 0;
}
zoj3182 Nine Interlinks
"What are you doing now?"
"Playing Nine Interlinks!"
"What is that?"
"Oh it is an ancient game played over China. The task is to get the nine rings off the stick according to some rules. Now, I have got them off, would you like to have a try to get them on?"
Input
The first line of the input contains an integer T (T <= 30), indicating the number of cases.
Each case consists of a simple integer n (1 < n < 30), which is the number of the total rings you need to get on the stick.
At the beginning, all rings are off the stick.
In each step, you can only get one ring on or off by the following rules:
1. You can get the first ring on or off freely at each step.
2. If the ith ring is on the stick, and the 1st, 2nd... (i-1)st rings are off the stick, you can get the (i+1)st ring on or off freely at each step.
Output
For each case, print in a single line the minimum number of steps you need to get n rings on the stick.
Sample Input
2 2 3
Sample Output
2 5
Hint
The first sample: 1 on, 2 on.
The second sample: 1 on, 2 on, 1 off, 3 on, 1 on.
Author: YU, Zhi
Contest: The 9th Zhejiang University Programming Contest
#include <iostream>
#include <cmath>
using namespace std;
int dp[31],ch[31];
int main()
{
int i,t,n;
cin>>t;
for(i=1;i<=30;i++)
{
dp[i]=(int)pow(2.0,i-1);
}
while(t--)
{
cin>>n;
int sum=0;
for(i=n;i>=0;i=i-2)
sum+=dp[i];
printf("%d\n",sum);
}
return 0;
}