Poj 1850 Code
题意:由最多8位的小写字母组成的单词(每个单词各个位置上的字母按照升序排列)先按长度排序再按照字典序排列,先给出一个单词,问此单词的排名;
解法:首先求出长度小于l该单词长度的单词的个数。然后开始统计相同长度且排在前面的单词数,从第一个字母开始,对于每个字母x,求出第i为是x前面的字母时能组成多少单词。。。
int res=0,len=s.length(),last=-1; for(int i=1;i<len;i++){ if(s.charAt(i)<=s.charAt(i-1)) { System.out.println(0); return; } res+=c[26][i]; } for(int i=0;i<len;i++){ int k=s.charAt(i)-'a'; if(k==0){ last=k; continue; } for(int j=last+1;j<k;j++) res+=c[26-j-1][len-i-1]; last=k; }
Poj 1715 Hexadecimal Numbers
题意:为第x大的十六进制数是几(这里的十六进制数至多8位且各位各不相同)
解法:首先依次统计长度为i的十六进制数有多少个然后确定第x大的十六进制是几位。然后依次确定每一位(思路和确定位数相似,枚举若此位是目前可用的第i大的数字时有多少种组合,直至叠加只和大于x);
String hex[] = { "", "0", "1", "2", "3", "4", "5", "6", "7", "8", "9", "A", "B", "C", "D", "E", "F" }; boolean vis[] = new boolean[17]; int kth(int k) { int i = 0, j; for (j = 1; j <= 16; j++) if (!vis[j] && ++i == k) break; return j; } void run() { init(); int k = scan.nextInt(); Arrays.fill(vis, false); int m = 0, sum = 0; for (m = 8; m > 0; m--) { sum += num[m]; if (sum >= k) break; } if (m < 8) k -= (sum - num[m]); String ans = ""; for (int i = m; i > 0; i--) { int j; sum = 0; for (j = 16 - m + i; j > 0; j--) { sum += a[16 - m + i - 1][i - 1]; if (sum >= k) break; } sum -= a[16 - m + i - 1][i - 1]; int temp = kth(j); ans += hex[temp]; vis[temp] = true; k -= sum; } System.out.println(ans); }
Poj 2282 The counting problem
题意:统计位于x和y之间的正整数,0---9出现了多少次。
解法:求1---n中各个数出现的次数,然后相减。对于一个数n和要统计的i,分别求i位于n的个位十位百位。。。时出现的次数,对于一个数n分成XjY三部分,j表示当前要统计的为的值,X表示当前位之前的值,Y表示当前位之后的值。根据i和j的大小关系便可以确定组合数。注意对于0的统计要稍微处理一下,since 不能有前导0。
long count(String s,int k){//统计1--s中k出现的次数 long ans=0; int len=s.length(); for(int i=0;i<len;i++){ int x=0,y=-1; int key=Integer.parseInt(s.substring(i,i+1)); if(i>0) x=Integer.parseInt(s.substring(0,i)); if(i<len-1) y=Integer.parseInt(s.substring(i+1,len)); if(k==0) x--; if(key<k) ans+=x*Math.pow(10, len-i-1); if(key==k){ if(i==len-1) y++; ans+=x*Math.pow(10, len-i-1)+y+1; } if(key>k) ans+=(x+1)*Math.pow(10, len-i-1); } return ans; }