1. 题目列表
- POJ3252（组合数的递推计算、杨辉三角形、组合思想）
- poj1850（组合求序列标号）
2. 组合问题的思路
组合问题多以求序列标号形式出现，问题转换为求其之前序列的个数，先用组合求序列长度为1,2,...,len - 1的组合数，再穷举长度为len的每一位，根据实际问题再求组合数。
3. POJ3252——Round Numbers
3.1 问题描述
Description
The cows, as you know, have no fingers or thumbs and thus are unable to play Scissors, Paper, Stone' (also known as 'Rock, Paper, Scissors', 'Ro, Sham, Bo', and a host of other names) in order to make arbitrary decisions such as who gets to be milked first. They can't even flip a coin because it's so hard to toss using hooves.
They have thus resorted to "round number" matching. The first cow picks an integer less than two billion. The second cow does the same. If the numbers are both "round numbers", the first cow wins,
otherwise the second cow wins.
A positive integer N is said to be a "round number" if the binary representation of N has as many or more zeroes than it has ones. For example, the integer 9, when written in binary form, is 1001. 1001 has two zeroes and two ones; thus, 9 is a round number. The integer 26 is 11010 in binary; since it has two zeroes and three ones, it is not a round number.
Obviously, it takes cows a while to convert numbers to binary, so the winner takes a while to determine. Bessie wants to cheat and thinks she can do that if she knows how many "round numbers" are in a given range.
Help her by writing a program that tells how many round numbers appear in the inclusive range given by the input (1 ≤ Start < Finish ≤ 2,000,000,000).
Input
Line 1: Two space-separated integers, respectively Start and Finish.
Output
Line 1: A single integer that is the count of round numbers in the inclusive range Start..Finish
Sample Input
2 12
Sample Output
6
2.2 解决思路
参考：https://blog.csdn.net/lyy289065406/article/details/6648458
2.3 代码
#include <cstdio>
#include <cstring>
using namespace std;
/*
题意：字符串按递增排序顺序标号，问给定任意一个字符串，求其标号。
组合问题：问题转换，先求在该字符串前面的字符串个数，最后+1即可。
由于组合唯一确定了一个递增序列，在该字符串前面的字符串个数 =
长度为1,2,...,len-1的字符串个数和，之后，再穷举每一个位置，求
在该字符串前面的字符串个数即可。
注意：字符与序号的转换，序号 = 字符 - 'a' + 1
*/
int c[30][30];
char word[50];
void init_table(){
c[0][0] = 0;
for (int i = 1; i <= 26; i++)
for (int j = 0; j <= i; j++)
if (i == j || j == 0)
c[i][j] = 1;
else
c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
}
int main(){
scanf("%s", word);
int len = strlen(word);
int sum = 0;
init_table();
for (int i = 1; i < len; i++)
if (word[i] < word[i - 1]){
printf("0\n");
return 0;
}
// 先计算 len - 1共有多少种选法
for (int i = 1; i < len; i++){
sum += c[26][i];
}
// 计算len长度有多少种选法
for (int i = 0; i < len; i++){
int start, end;
if (i == 0)
start = 1;
else
start = word[i - 1] - 'a' + 1 + 1; // 字符序号 = 字符 - 'a' + 1，且从word[i - 1]的下一位开始
end = word[i] - 'a' + 1 - 1;
for (int j = start; j <= end; j++) // j = 26 - 字符序号
sum += c[26 - j][len - i - 1];
}
printf("%d\n", sum + 1);
}
3. POJ1850——Code
3.1 题目描述
Description
Transmitting and memorizing information is a task that requires different coding systems for the best use of the available space. A well known system is that one where a number is associated to a character sequence. It is considered that the words are made only of small characters of the English alphabet a,b,c, ..., z (26 characters). From all these words we consider only those whose letters are in lexigraphical order (each character is smaller than the next character).
The coding system works like this:
• The words are arranged in the increasing order of their length.
• The words with the same length are arranged in lexicographical order (the order from the dictionary).
• We codify these words by their numbering, starting with a, as follows:
a - 1
b - 2
...
z - 26
ab - 27
...
az - 51
bc - 52
...
vwxyz - 83681
...
Specify for a given word if it can be codified according to this coding system. For the affirmative case specify its code.
Input
The only line contains a word. There are some constraints:
• The word is maximum 10 letters length
• The English alphabet has 26 characters.
Output
The output will contain the code of the given word, or 0 if the word can not be codified.
Sample Input
bf
Sample Output
55
3.2 解决思路
题意：字符串按递增排序顺序标号，问给定任意一个字符串，求其标号。
组合问题：问题转换，先求在该字符串前面的字符串个数，最后+1即可。
由于组合唯一确定了一个递增序列，在该字符串前面的字符串个数 =
长度为1,2,...,len-1的字符串个数和，之后，再穷举每一个位置，求
在该字符串前面的字符串个数即可。
注意：字符与序号的转换，序号 = 字符 - 'a' + 1
3.3 代码
#include <cstdio>
#include <cstring>
using namespace std;
int c[30][30];
char word[50];
void init_table(){
c[0][0] = 0;
for (int i = 1; i <= 26; i++)
for (int j = 0; j <= i; j++)
if (i == j || j == 0)
c[i][j] = 1;
else
c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
}
int main(){
scanf("%s", word);
int len = strlen(word);
int sum = 0;
init_table();
for (int i = 1; i < len; i++)
if (word[i] < word[i - 1]){
printf("0\n");
return 0;
}
// 先计算 len - 1共有多少种选法
for (int i = 1; i < len; i++){
sum += c[26][i];
}
// 计算len长度有多少种选法
for (int i = 0; i < len; i++){
int start, end;
if (i == 0)
start = 1;
else
start = word[i - 1] - 'a' + 1 + 1; // 字符序号 = 字符 - 'a' + 1，且从word[i - 1]的下一位开始
end = word[i] - 'a' + 1 - 1;
for (int j = start; j <= end; j++) // j = 26 - 字符序号
sum += c[26 - j][len - i - 1];
}
printf("%d\n", sum + 1);
}
网友评论