#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;
}
Monday 4 May 2009
POJ 1012
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 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;
}
POJ 3332
这题完全应该用 java + regex 做的。
#include <iostream>
#include <cctype>
using namespace std;
bool ok(char* x){
if(*x=='+'||*x=='-')
if (!isdigit(*++x)) return false;
if(!isdigit(*x)) return false;
for(;isdigit(*x);++x);
if (*x==0) return true;
else if (*x=='.') {
if (!isdigit(*++x)) return false;
for(;isdigit(*x);++x);
}
if (*x=='e'||*x=='E') {
++x;
if (*x=='+'||*x=='-') ++x;
if(!isdigit(*x)) return false;
for(;isdigit(*x);++x);
}
return *x==0;
}
int main() {
int n; char x[1024];
for(cin>>n;n--;cout<<(ok(x)?"LEGAL":"ILLEGAL")<<endl)cin>>x;
return 0;
}
POJ 1565
#include <iostream>
#include <string.h>
using namespace std;
typedef unsigned int uint;
uint de(char* x){
uint n=1,r=0;
char *p;
for(p=x;*p;++p);
for(--p;p>=x;--p)r+=((n<<=1)-1)*(*p-'0');
return r;
}
int main(){
for(char x[1024];cin>>x;cout<<de(x)<<endl)
if(!strcmp(x,"0"))break;
return 0;
}
POJ 2602
#include <stdio.h>
int main() {
char a[1000001],b[1000000],c=0;
int N,i;
for(scanf("%d\n",&N),i=0;i<N;++i)
a[i]=getchar(),getchar(),b[i]=getchar(),getchar();
for(--i;i>=0;--i){
a[i]+=b[i]-'0'+c;
if(c=a[i]>'9')
a[i]-=10;
}
for(i=0;i<N;++i)
putchar(a[i]);
return 0;
}
POJ 1658
#include <iostream>
using namespace std;
int next(int* arr){
bool p=true,q=true;
int P=arr[1]-arr[0],Q=arr[1]/arr[0],i;
for(i=2;i<4;++i) {
if(arr[i]-arr[i-1]!=P)p=false;
if(arr[i]/arr[i-1]!=Q)q=false;
}
return p?arr[3]+P:arr[3]*Q;
}
int main() {
int N,arr[4],i;
for(cin>>N;N--;){
for(i=0;i<4;++i){
cin>>arr[i];
cout<<arr[i]<<" ";
}
cout<<next(arr)<<endl;
}
return 0;
}
POJ 2406
#if 0
#include <stdio.h>
#define XSIZE 1000001
char str[XSIZE];
int next[XSIZE],len;
int kmpNext(char*x,int*next){
int i,j;
for(i=0,j=next[0]=-1;x[i];){
for(;j>-1&&x[i]!=x[j];j=next[j]);
++i;++j;
next[i]=x[i]==x[j]?next[j]:j;
}
return i;
}
int main() {
for(;scanf("%str",str),*str!='.';printf("%d\n",len%(next[0]=len-next[len])?1:len/next[0]))
len=kmpNext(str,next);
return 0;
}
#else
char s[1000001];n[1000001],i,j;main(){for(;gets(s),*s-'.';printf("%d\n",i%(j=i-n[i])?1:i/j))for(i=0,j=*n=-1;s[i];++i,++j,n[i]=s[i]==s[j]?n[j]:j)for(;j>-1&&s[i]!=s[j];j=n[j]);}
#endif
POJ 1517
#include <iostream>
int main(){
std::cout<<
"n e\n"
"- -----------\n"
"0 1\n"
"1 2\n"
"2 2.5\n"
"3 2.666666667\n"
"4 2.708333333\n"
"5 2.716666667\n"
"6 2.718055556\n"
"7 2.718253968\n"
"8 2.71827877\n"
"9 2.718281526";
return 0;
}
POJ 2656
n,m,d,a,b,i;main(){for(;scanf("%d",&n),n;){for(m=i=0;n-i;a+b>m&&(m=a+b,d=i))scanf("%d%d",&a,&b),++i;m<=8?puts("0"):printf("%d\n",d);}}
POJ 1731
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int main() {
char str[256];
int len;
cin>>str;
len=strlen(str);
sort(str,str+len);
do cout<<str<<endl; while (next_permutation(str,str+len));
return 0;
}
POJ 1218
#include <iostream>
#include <cmath>
using namespace std;
int main() {
int N,n;
for(cin>>N;N--;cout<<int(sqrt(double(n)))<<endl)cin>>n;
return 0;
}
Saturday 25 April 2009
HDOJ 1075
我自己挺满意的，用 std::map 通不过，所以就写了个字典树~
而此题写的字典树和 getword 函数都具有很强的可重用性，您认为呢
#include <iostream>
#include <cstring>
#include <string>
using namespace std;
template <class T>
struct node {
T value;
node* next;
};
template <class T>
class trie_tree {
public:
typedef trie_tree type;
typedef node<type*> child_type;
protected:
char key;
T* value;
child_type* children;
public:
trie_tree():key('*'),value(0),children(0){}
~trie_tree(){
if (value)
delete value;
for(child_type *p=0,*itr=children;itr;itr=p) {
if (itr) p=itr->next;
delete itr->value;
delete itr;
}
}
T* operator[](char* str){
T* what=0;
get(str,what);
return what;
}
bool get(char* str, T*&what) {
if (*str==0){
what=value;
return what!=0;
} else {
char ch=*str;
for(child_type* itr=children;itr;itr=itr->next) {
if ( itr->value->key==ch ) {
return itr->value->get(str+1, what);
}
}
what=0;
return false;
}
return false;
}
bool insert(char* str,T const& v){
if(*str==0){
value=new T(v);
return true;
} else {
char ch=*str;
child_type* itr;
if(children==0) {
children=new child_type;
children->next=0;
children->value=new trie_tree;
children->value->key=ch;
}
for(itr=children;itr&&itr->next;itr=itr->next) {
if ( itr->value->key==ch ) {
return itr->value->insert(str+1, v);
}
}
if(itr->value->key!=ch){
itr->next=new child_type;
itr->next->value=new trie_tree;
itr=itr->next;
itr->next=0;
}
itr->value->key=ch;
return itr->value->insert(str+1,v);
}
}
bool erase(char* str){
return false;
}
};
inline bool accept(char ch){
return ch>='a'&&ch<='z'||ch>='A'&&ch<='Z'||ch>='0'&&ch<='9';
}
bool getword(char* pos, char*& pos_after, char* buff) {
if(*pos==0)
return false;
pos_after=pos;
for(;*pos&&!accept(*pos);++pos) {
*buff=*pos;
++buff;
}
*buff=0;
if(pos!=pos_after) {
pos_after=pos;
return true;
}
for(;*pos&&accept(*pos);++pos){
*buff=*pos;
++buff;
}
*buff=0;
pos_after=pos;
return true;
}
int main(){
char mars[16],earth[16];
char line[3005]="1,3,43,2, sdl!!!";
// for(char* p=line,*p2;getword(p,p2,mars);p=p2)
// cout<<mars<<endl;
trie_tree<string> dic;
scanf("%s\n",mars);//START
for(;scanf("%s",earth)&&strcmp(earth,"END");){
scanf("%s",mars);
dic.insert(mars,earth);
}
scanf("%s\n",mars);//START
for(;gets(line)&&strcmp(line,"END");){
string* pstr=0;
for(char *p=line,*p2;getword(p,p2,mars);p=p2){
pstr=dic[mars];
if(pstr)
cout<<*pstr;
else
cout<<mars;
}
cout<<endl;
}
return 0;
}
Saturday 11 April 2009
POJ 2140
这题精妙得很，值得好好研究
/**
Mr lixiaoyi's algorithm
其实我还不知其所以然，无耻的AC了。
*/
#include<stdio.h>
//int main() {
// int s,n,x,c;
// scanf("%d",&x);
// for (s=c=n=0;s<=x;c+=(x-s)%n==0&&(x-s)/n!=0)
// s+=n++;
// printf("%d",c);
// return 0;
//}
s,n,x,c;main(){scanf("%d",&x);for(s=c=n=0;s<=x;c+=(x-s)%n==0&&(x-s)/n)s+=n++;printf("%d",c);}
//#include <stdio.h>
//int main(){
// int s,n,x,c=0;
// for(scanf("%d",&x),s=n=1;s<=x;++n){
// s+=n;
// if there is an integer 1 + Sqrt(1 + 4*n - 4*Power(n,2) - 8*x))/2. then ...
// if(n&1==1&&x%n==0)++c;
// else if((2*x)%n==0&&((2*x)/n)%2==1)++c;
// }
// printf("%d\n",c);
// return 0;
//}
POJ 2017
a,b,c,d,e;main(){for(;scanf("%d",&a),a+1;printf("%d miles\n",b))for(b=c=0;a--;b+=d*(e-c),c=e)scanf("%d%d",&d,&e);}
POJ 2027
水题
a,b,n;main(){for(scanf("%d",&n);n--;printf("%s BRAINS\n",a<b?"NO":"MMM"))scanf("%d%d",&a,&b);}
POJ 3461
神奇的KMP
#include <stdio.h>
#include <string.h>
#define XSIZE 10001
int preKmp(char *x, int kmpNext[]) {
int i, j;
for(i=0,j=kmpNext[0]=-1;x[i];) {
while (j>-1 && x[i]!=x[j])
j = kmpNext[j];
++i;
++j;
if (x[i] == x[j])
kmpNext[i] = kmpNext[j];
else
kmpNext[i] = j;
}
return i;
}
int KMP(char *x, char *y){
int i, j, kmpNext[XSIZE];
int nc=0;
/* Preprocessing */
int m=preKmp(x, kmpNext);
/* Searching */
for(i=j=0;y[j];){
while (i>-1 && x[i]!=y[j])
i = kmpNext[i];
++i;
++j;
if(i>=m){
++nc;
i=kmpNext[i];
}
}
return nc;
}
int main() {
int N;
char W[XSIZE],T[1000001];
for(scanf("%d",&N);N;--N){
scanf("%s%s",W,T);
printf("%d\n",KMP(W,T));
}
return 0;
}
POJ 1547
/**
Problem Result Memory Time Language Code Length Submit Time
1547 Accepted 432K 0MS G++ 558B 2009-03-25 19:14:33
*/
#include <iostream>
#include <string>
using namespace std;
void itsucks(int n){
typedef unsigned int uint;
string bully,victim,someone;
uint max=0,min=0xffffffff,a,b,c;
for(++n;--n;){
cin>>a>>b>>c>>someone;
a*=(b*=c);
if(a>max){
max=a;
bully=someone;
}
if (a<min) {
min=a;
victim=someone;
}
}
cout<<bully<<" took clay from "<<victim<<".\n";
}
int main() {
for(int n;cin>>n&&n+1;itsucks(n));
return 0;
}
POJ 1519
#include <iostream>
#include <string>
using namespace std;
int itsucks(string const& digit){
unsigned int x=0,y;
for(int i=0;i<digit.length();x%=9,++i)x+=digit[i]-'0';
return x==0?9:x;
}
int main(){
for(string str;cin>>str&&str!="0";cout<<itsucks(str)<<endl);
return 0;
}
POJ 1298
#include <iostream>
#include <string>
using namespace std;
int main() {
for(string str;getline(cin,str)&&str!="ENDOFINPUT"&&getline(cin,str);cout<<endl&&getline(cin,str))
for(int i=0;i<str.length();++i)
cout<<(str[i]>'Z'||str[i]<'A'?str[i]:"VWXYZABCDEFGHIJKLMNOPQRSTU"[str[i]-'A']);
return 0;
}
POJ 1047
#include <iostream>
#include <string>
#include <deque>
using namespace std;
typedef unsigned int uint;
string mul_ui(string const& a, uint b){
typedef deque<uint>::iterator iterator;
typedef deque<uint>::reverse_iterator riterator;
iterator itr;
riterator ritr;
deque<uint> c(a.begin(),a.end());
for(itr=c.begin();itr!=c.end();++itr){
(*itr)-='0';
(*itr)*=b;
}
int remaineder=0;
for(ritr=c.rbegin();ritr!=c.rend();++ritr){
(*ritr)+=remaineder;
remaineder=(*ritr)/10;
(*ritr)%=10;
(*ritr)+='0';
}
for(;remaineder;remaineder/=10)
c.push_front(remaineder%10+'0');
// for(;c.front()=='0'&&c.size()>1;c.pop_front());
return string(c.begin(),c.end());
}
int main() {
for(string str;cin>>str;
cout<<str<<" is "
<<(string(str.length(),'9')==mul_ui(str,str.length()+1)?"":"not ")
<<"cyclic\n");
return 0;
}
POJ 1051
水题。
#include <iostream>
#include <vector>
#include <string.h>
using namespace std;
char Mcode[30][5]={
/*A-G:*/".-","-...","-.-.","-..",".","..-.","--.",
/*H-N:*/"....","..",".---","-.-",".-..","--","-.",
/*O-U:*/"---",".--.","--.-",".-.","...","-","..-",
/*V-Z:*/"...-",".--","-..-","-.--","--..",
/*_.,?*/"..--","---.",".-.-","----"
};
int len[30]={
2, 4, 4, 3, 1, 4, 3,4, 2, 4, 3, 4, 2, 2,
3, 4, 4, 3, 3, 1, 3,4, 3, 4, 4, 4,
4, 4, 4, 4
};
int index(char ch){
if(ch<='Z'&&ch>='A')
return ch-'A';
switch(ch){
case '_':return 26;
case '.':return 27;
case ',':return 28;
case '?':return 29;
}
return -1;
}
char* encode(char c,int& n){
int i=index(c);
n=len[i];
return Mcode[i];
}
char decode(char* m,int n){
for(int i=0;i<30;++i){
if(n!=len[i]||strncmp(Mcode[i],m,n))
continue;
if(i<26)
return i+'A';
switch(i){
case 26: return '_';
case 27: return '.';
case 28: return ',';
case 29: return '?';
}
}
return 0;
}
int main(){
int N,n;cin>>N;
for(n=1;n<=N;++n){
char msg[128],crypt[128*4]={0},*p,*q;
vector<int> codelen;
int tmp;
cin>>msg;
for(p=msg,q=crypt;*p;++p){
strcpy(q,encode(*p,tmp));
codelen.push_back(tmp);
q+=tmp;
}
q=crypt;
cout<<n<<": ";
for(int i=codelen.size()-1;i>=0;--i){
cout<<decode(q,codelen[i]);
q+=codelen[i];
}
cout<<endl;
}
return 0;
}
POJ 2390
水
#include <iostream>
using namespace std;
typedef unsigned int uint;
uint suck(int R,int M,int Y){
double g=M,r=1.+R/100.;
for(;Y--;g*=r);
return g;
}
int main(){
for(int R,M,Y;cin>>R>>M>>Y;cout<<suck(R,M,Y)<<endl);
return 0;
}
POJ 1056
#include <iostream>
#include <string.h>
using namespace std;
bool sub(char const* a,char const* b){
for(;*a==*b&&*a&&*b;++a,++b);
return *a==0||*b==0;
}
bool ok(char vs[1024][11],int n){
for(int i=0;i<n-1;++i)
for(int j=i+1;j<n;++j)
if(sub(vs[i],vs[j]))
return false;
return true;
}
int main(){
int N=0;
for(char buf[1024][11];;){
int n=0;
for(;cin>>buf[n]&&0[buf[n++]]!='9';);
if(cin.eof())break;
--n;
cout<<"Set "<<++N<<(ok(buf,n)?" is":" is not")<<" immediately decodable"<<endl;
}
return 0;
}
POJ 1207
由于 f 可以比 t 小，卡住了无数次——而且就算改过来了还是不对——直到说出了粗口，它就突然 AC 了。
#include <iostream>
using namespace std;
typedef unsigned int uint;
uint fuck(int f,int t){
uint b,x,n;
if(f>t)f^=t^=f^=t;
for(b=0;f<=t;++f){
for(x=1,n=f;n-1;n=n&1?3*n+1:n>>1)++x;
if(x>b)b=x;
}
return b;
}
int main(){
for(uint f,t,b,x;cin>>f>>t;){
if(f>10000||t>10000||f==0||t==0)break;
cout<<f<<" "<<t<<" "<<fuck(f,t)<<endl;
}
return 0;
}
POJ 1046
水。
#include <iostream>
#include <cstdio>
using namespace std;
inline int p(int n){
return n*n;
}
int main() {
int R[16],G[16],B[16],r,g,b,i,j,min,tmp;
for(i=0;i<16;++i)
cin>>R[i]>>G[i]>>B[i];
for(;cin>>r>>g>>b&&r+1;){
min=0x7fffffff;
for(i=0;i<16;++i) {
tmp=p(R[i]-r)+p(G[i]-g)+p(B[i]-b);
if(tmp<min){
min=tmp;
j=i;
}
}
printf("(%d,%d,%d) maps to (%d,%d,%d)\n",r,g,b,R[j],G[j],B[j]);
}
return 0;
}
POJ 1068
笨方法
#include <iostream>
using namespace std;
enum bracket{
LEFT=0,
RIGHT=1,
VISITED=2
};
int main() {
int N;
for(cin>>N;N;--N){
int n,i,a[32];
bracket b[64]={LEFT};
cin>>n;
for(i=0;i<n;++i) {
cin>>a[i];
b[a[i]+i]=RIGHT;
}
for(i=0;i<n<<1;++i){
if(b[i]==RIGHT){
int t=0;
for(int j=i;j>=0;--j){
if(b[j]==RIGHT) ++t;
else if(b[j]==LEFT){
b[j]=VISITED;
break;
}
}
cout<<t<<" ";
}
}
cout<<endl;
}
return 0;
}
POJ 1159
注意这个的最长公共子序列算法的空间复杂度
#include <stdio.h>
#include <string.h>
typedef unsigned int uint;
uint max(uint a,uint b){
return a>b?a:b;
}
uint LCS(char* a,char*b){
static uint matrix[2][5*1024]={{0},{0}};
int i,j,k;
for(i=0;a[i];++i) matrix[0][i]=0;
for(i=1;a[i-1];++i){
k=i%2;
for(j=1;b[j-1];++j){
if(a[i-1]==b[j-1])
matrix[k][j]=matrix[!k][j-1]+1;
else
matrix[k][j]=max(matrix[k][j-1],matrix[!k][j]);
}
}
return matrix[k][j-1];
}
int main() {
char str[5001],s[5001];
for(int n;scanf("%d%s",&n,str)+1;){
strcpy(s,str);
printf("%d\n",n-LCS(s,strrev(str)));
}
return 0;
}
POJ 1057
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
struct dir {
string name;
vector<dir> subdir;
vector<string> files;
bool operator<(dir const& other) const {
return this->name<other.name;
}
};
void input(dir& d, string & str){
switch(str[0]){
case 'f':{
d.files.push_back(str);
cin>>str;
input(d,str);
} break;
case 'd':{
dir subdir;
subdir.name=str;
cin>>str;
input(subdir,str);
d.subdir.push_back(subdir);
} break;
default:
return;
}
}
ostream& spacer(int n){
for(;n;--n) cout<<"| ";
return cout;
}
void output(dir & d,int level){
if(!d.subdir.empty()){
spacer(level+1)<<d.name<<endl;
// sort(d.subdir.begin(),d.subdir.end());
for(vector<dir>::iterator i=d.subdir.begin();i!=d.subdir.end();++i)
output(*i,level+2);
}
sort(d.files.begin(),d.files.end());
for(vector<string>::const_iterator i=d.files.begin();i!=d.files.end();++i)
spacer(level)<<*i<<endl;
}
int main() {
int N=0;
for(string str;cin>>str;){
if(str[0]=='#')break;
else if(str[0]=='*')continue;
dir d;
input(d,str);
cout<<"DATA SET "<<++N<<":"<<endl;
output(d,0);
cout<<endl;
}
return 0;
}
POJ 1936
混乱版：main(){char s[100001],t[100001],*p,*q;for(;scanf("%s%s",s,t)+1;puts(*p?"No":"Yes"))for(p=s,q=t;*p&&*q;*p==*q++&&++p);}
#include <iostream>
using namespace std;
bool isin(char* s,char *t){
for(;*t;++t) if (*s==*t&&*++s==0) return true;
return false;
}
int main() {
for(char s[100001],t[100001];cin>>s>>t;cout<<(isin(s,t)?"Yes\n":"No\n"));
return 0;
}
Subscribe to:
Posts (Atom)
