首页 > 专题系列 > Java解POJ > POJ 1496 Word Index [解题报告] Java
2013
11-09

POJ 1496 Word Index [解题报告] Java

Word Index

问题描述 :

Encoding schemes are often used in situations requiring encryption or information storage/transmission economy. Here, we develop a simple encoding scheme that encodes particular types of words with five or fewer (lower case) letters as integers.

Consider the English alphabet {a,b,c,…,z}. Using this alphabet, a set of valid words are to be formed that are in a strict lexicographic order. In this set of valid words, the successive letters of a word are in a strictly ascending order; that is, later letters in a valid word are always after previous letters with respect to their positions in the alphabet list {a,b,c,…,z}. For example,

abc aep gwz

are all valid three-letter words, whereas

aab are cat

are not.

For each valid word associate an integer which gives the position of the word in the alphabetized list of words. That is:


a -> 1
b -> 2
.
.
z -> 26
ab -> 27
ac -> 28
.
.
az -> 51
bc -> 52
.
.
vwxyz -> 83681

Your program is to read a series of input lines. Each input line will have a single word on it, that will be from one to five letters long. For each word read, if the word is invalid give the number 0. If the word read is valid, give the word’s position index in the above alphabetical list.

输入:

The input consists of a series of single words, one per line. The words are at least one letter long and no more that five letters. Only the lower case alphabetic {a,b,…,z} characters will be used as input. The first letter of a word will appear as the first character on an input line.

The input will be terminated by end-of-file.

输出:

The output is a single integer, greater than or equal to zero (0) and less than or equal 83681. The first digit of an output value should be the first character on a line. There is one line of output for each input line.

样例输入:

z
a
cat
vwxyz

样例输出:

26
1
0
83681

解题代码:

//* @author: [email protected]
import java.util.*;
public class Main
{
	public static void main(String[] args)
	{
		Scanner in=new Scanner(System.in);
		while(in.hasNext())
		{
		String s=in.next();
		boolean bb=true;
		for(int i=0;i< s.length()-1;i++)
		{
		  if(s.charAt(i)-s.charAt(i+1)>=0)
		  {
			System.out.println(0);
			bb=false;
			break;
		   }
		}
		if(!bb)continue;
		int l=s.length();
		long ans=0;
		for(int i=1;i< l;i++)
			ans+=find(26,i);
		int k=0;
		for(int i=0;i< l;i++)
		{
		  k=0;
		  if(i!=0)k=s.charAt(i-1)-'a'+1;
		  int y=s.charAt(i)-'a'+1;
		  for(int j=y-1;j>k;j--)
		  {
			ans+=find(26-j,l-i-1);
		  }
		}
		System.out.println(ans+1);
		}
	}
	public static long find(int u,long a)
	{
		if(u< a) return 0;
		if(a==0) return 1;
		long l=1;
		for(int i=u;i>u-a;i--)
			l*=i;
		for(int i=1;i<=a;i++)
			l/=i;
		return l;
	}
}

  1. 第一句可以忽略不计了吧。从第二句开始分析,说明这个花色下的所有牌都会在其它里面出现,那么还剩下♠️和♦️。第三句,可以排除2和7,因为在两种花色里有。现在是第四句,因为♠️还剩下多个,只有是♦️B才能知道答案。

  2. 换句话说,A[k/2-1]不可能大于两数组合并之后的第k小值,所以我们可以将其抛弃。
    应该是,不可能小于合并后的第K小值吧

  3. #include <cstdio>
    #include <algorithm>

    struct LWPair{
    int l,w;
    };

    int main() {
    //freopen("input.txt","r",stdin);
    const int MAXSIZE=5000, MAXVAL=10000;
    LWPair sticks[MAXSIZE];
    int store[MAXSIZE];
    int ncase, nstick, length,width, tmp, time, i,j;
    if(scanf("%d",&ncase)!=1) return -1;
    while(ncase– && scanf("%d",&nstick)==1) {
    for(i=0;i<nstick;++i) scanf("%d%d",&sticks .l,&sticks .w);
    std::sort(sticks,sticks+nstick,[](const LWPair &lhs, const LWPair &rhs) { return lhs.l>rhs.l || lhs.l==rhs.l && lhs.w>rhs.w; });
    for(time=-1,i=0;i<nstick;++i) {
    tmp=sticks .w;
    for(j=time;j>=0 && store >=tmp;–j) ; // search from right to left
    if(j==time) { store[++time]=tmp; }
    else { store[j+1]=tmp; }
    }
    printf("%dn",time+1);
    }
    return 0;
    }