Monday 4 May 2009

POJ 1012


#include<iostream>
using namespace std;
int main() {
int a[14]={2,7,5,30,169,441,1872,7632,1740,93313,459901,1358657,2504881,13482720};
for (int k;cin>>k&&k;cout<<a[k-1]<<endl);
return 0;
}

POJ 1318



题:(http://acm.pku.edu.cn/JudgeOnline/problem?id=1318)
Word Amalgamation

Description



In millions of newspapers across the United States there is a word game called Jumble. The object of this game is to solve a riddle, but in order to find the letters that appear in the answer it is necessary to unscramble four words. Your task is to write a program that can unscramble words.

Input



The input contains four parts: 1) a dictionary, which consists of at least one and at most 100 words, one per line; 2) a line containing XXXXXX, which signals the end of the dictionary; 3) one or more scrambled 'words' that you must unscramble, each on a line by itself; and 4) another line containing XXXXXX, which signals the end of the file. All words, including both dictionary words and scrambled words, consist only of lowercase English letters and will be at least one and at most six characters long. (Note that the sentinel XXXXXX contains uppercase X's.) The dictionary is not necessarily in sorted order, but each word in the dictionary is unique.

Output



For each scrambled word in the input, output an alphabetical list of all dictionary words that can be formed by rearranging the letters in the scrambled word. Each word in this list must appear on a line by itself. If the list is empty (because no dictionary words can be formed), output the line "NOT A VALID WORD" instead. In either case, output a line containing six asterisks to signal the end of the list.

Sample Input



tarp
given
score
refund
only
trap
work
earn
course
pepper
part
XXXXXX
resco
nfudre
aptr
sett
oresuc
XXXXXX

Sample Output



score
******
refund
******
part
tarp
trap
******
NOT A VALID WORD
******
course
******

Source





解:
自己瞎掰的hash,以前做浙大的某个比赛时也这么折腾的来着,感觉还挺好用。
#include <iostream>
#include <map>
#include <set>
#include <string>
using namespace std;
typedef char wordtype[16];
typedef unsigned int uint;

class dic {
map<uint,set<string> > mp[6];
public:
dic(){}
~dic(){}
uint hash(wordtype const& word,int len) const {
uint mask=0;
char ch=1;
for(int i=0;i<len;++i) {
mask|=1<<(word[i]-'a');
ch*=(word[i]-'a'+7);
}
mask|=ch<<26;
return mask;
}
void add_word(wordtype const& word, int len) {
uint h=hash(word,len);
mp[len-1][h].insert(string(word));
}
set<string> & get_words(wordtype const& word, int len) {
uint h=hash(word,len);
return mp[len-1][h];
}
};

int main()
{
dic d;
wordtype word;
for(;cin>>word&&*word!='X';)
d.add_word(word,strlen(word));
for(;cin>>word&&*word!='X';cout<<"******\n") {
set<string> const& p=d.get_words(word, strlen(word));
if(p.empty()){
cout<<"NOT A VALID WORD\n";
} else {
for(set<string>::const_iterator ctr=p.begin();ctr!=p.end();++ctr)
cout<<*ctr<<endl;
}
}
return 0;
}

POJ 1316


#include<iostream>
using namespace std;
int main() {
bool a[10001]={0};
for(int i=1;i<=10000;++i){
if(!a[i])
cout<<i<<endl;
int num=i,j=i;
for(;j;j/=10)
num+=j%10;
if(num<=10000)
a[num]=true;
}
return 0;
}

POJ 1552


#include <iostream>
using namespace std;
int main() {
for(int n,m;cin>>n&&n!=-1;){
bool a[101]={0};
a[n]=true; m=0;
for(;cin>>n&&n;a[n]=true);
for(int i=1,j=2;i<=50;++i,j+=2) if(a[i]&&a[j])++m;
cout<<m<<endl;
}
return 0;
}

POJ 1306


说是可以用double类型,但老用老错,烦了,直接上大数。
#include <iostream>
#include <deque>
#include <cmath>
#include <algorithm>
using namespace std;
typedef unsigned int uint;
typedef unsigned __int64 uint64;
class unsigned_big_integer{
protected:
typedef unsigned_big_integer class_type;
typedef uint celltype;
std::deque<celltype> m_num;
public:
unsigned_big_integer(const class_type& b):m_num(b.m_num){}
unsigned_big_integer(const uint integer):m_num(){
uint x=integer;
while(x){
m_num.push_front(x%10);
x/=10;
}
}
virtual ~unsigned_big_integer(){}
class_type& operator=(const class_type& bi){
this->m_num=bi.m_num;
return *this;
}
public:
virtual std::string str(){
std::string s(m_num.begin(),m_num.end());
for(std::string::iterator itr=s.begin();itr!=s.end();++itr)
*itr+='0';
return s;
}

class_type& mul(uint const x){
for(std::deque<celltype>::iterator itr=m_num.begin();itr!=m_num.end();++itr)
*itr*=x;
for(std::deque<celltype>::reverse_iterator ritr=m_num.rbegin();ritr!=m_num.rend()-1;++ritr){
*(ritr+1)+=(*ritr)/10;
*ritr%=10;
}
while(m_num.front()>=10){
celltype x=m_num.front()/10;
m_num.front()%=10;
m_num.push_front(x);
}
return *this;
}

class_type& operator/=(uint const x){
uint remained=0;
for(std::deque<celltype>::iterator itr=m_num.begin();itr!=m_num.end();++itr){
remained*=10;
remained+=*itr;
if(remained/x){
for(int j=9;j>=1;--j){
if(remained/(x*j)){
*itr=j;
remained-=x*j;
break;
}
}
}
else{
*itr=0;
}
}
for(;m_num.size()>1&&m_num.front()==0;m_num.pop_front())
;
return *this;
}

class_type& operator*=(uint const x){
return mul(x);
}
};

string C(uint n, uint m){
unsigned_big_integer x(n);
uint t=n-m;
for(--n;n>t;--n) x*=n;
for(;m>1;--m) x/=m;
return x.str();
}

int main() {
for(uint n,m;cin>>n>>m&&n&&m;)
cout<<n<<" things taken "<<m<<" at a time is "<<C(n,m)<<" exactly.\n";
return 0;
}

POJ 3210


n;main(){for(;scanf("%d",&n),n;n&1?printf("%d\n",n-1):puts("No Solution!"));}

POJ 2039


#include <iostream>
#include <string.h>
using namespace std;

int main() {
char code[2048];
int col,len,row;
for(;cin>>col&&col;){
cin>>code;
len=strlen(code);
row=len/col;
for(int j=0;j<col;++j)
for(int i=0;i<row;++i) {
if(i&1) {
cout<<code[i*col+col-j-1];
} else {
cout<<code[i*col+j];
}
}
cout<<endl;
}
return 0;
}

POJ 2136


#include <iostream>
#include <memory.h>
using namespace std;
typedef unsigned int uint;
int main() {
char line[128]={0};
uint occur[26]={0},mx=0;
for(;cin.getline(line,128);){
for(char* p=line;*p;++p)
if(*p>='A'&&*p<='Z')
if(++occur[*p-'A']>mx)
mx=occur[*p-'A'];
}
for(;mx>=1;--mx){
memset(line,0,64);
for(int i=0;i<26;++i){
if(occur[i]>=mx) {
line[i*2]='*';
for(int j=i*2-1;j>=0&&!line[j];--j)
line[j]=' ';
}
}
cout<<line<<endl;
}
for(char A='A';A<'Z';++A)
cout<<A<<" ";
cout<<"Z\n";
return 0;
}

POJ 2350


#include <iostream>
#include <iomanip>
using namespace std;
int main(){
int N,n,j,i,l[1024];
double a;
for(cin>>N;N--;){
cin>>n;
a=0;
for(i=0;i<n;++i){
cin>>l[i];
a+=l[i];
}
a/=n;
for(i=j=0;i<n;++i)
if(l[i]>a)
++j;
cout<<setprecision(3)<<fixed<<double(j)/double(n)*100.<<"%\n";
}
return 0;
}

POJ 1220


以前屡试不爽的大数类在这里扛不住超内存了,于是发现了一个更有效的方式——简单说就是一边乘一边除。
其实下面的代码还很有改进空间,不过思想也就只这样的了。
#include <iostream>
#include <algorithm>
using namespace std;
inline char to_char(int ch) {
static const char table[]=
"0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
return table[ch];
}
inline int from_char(char ch) {
static const int table[]= {
255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 63, 255, 62, 255, 255,
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 255, 255, 255, 255, 255, 255, 255, 10, 11, 12, 13,
14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33,
34, 35, 255, 255, 255, 255, 255, 255, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45,
46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 255, 255, 255,
255
};
return table[int(ch)];
}

int convert(char* dest, char* src, int from, int to) {
int mem[2048]={0},*tmp,*buff,len,i,j,carry;
tmp=mem; buff=mem+1024;
for(i=0;src[i];++i)
tmp[i]=from_char(src[i]);
for(len=i,j=0;len;++j){
carry=0;
for(i=0;i<len;++i){
carry*=from;
carry+=tmp[i];
buff[i]=carry/to;
carry%=to;
}
dest[j]=to_char(carry);
for(i=0;i<len&&buff[i]==0;++i,--len);
buff+=i;
swap(tmp,buff);
}
dest[j]=0;
return j;
}

int main(){
int n,f,t,len;
char str[1024],dest[1024];
for(cin>>n;n--;){
cin>>f>>t>>str;
cout<<f<<" "<<str<<endl<<t<<" ";
len=convert(dest,str,f,t);
for(--len;len>=0;--len) cout<<dest[len];
cout<<"\n\n";
}
return 0;
}