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;
}

POJ 2243





#include <algorithm>
#include <iostream>
#include <utility>
#include <deque>
using namespace std;
typedef std::pair<int,int> move;
enum state {OUT=0, OK=1, VISITED=2, TARGET=-1};
typedef state board[12][12];
const int MOVES[8][2]={
{-1,-2}, {-2,-1}, {-1,2}, {-2,1}, {1,-2}, {2,-1}, {1,2}, {2,1}
};
int go(board b,int x,int y){ //BFS
if(b[x][y]==TARGET)
return 0;
deque<int> stepx[2];
deque<int> stepy[2];
stepx[0].push_back(x);
stepy[0].push_back(y);
int level=0;
int l1=0,l2=1;
while(true){
++level;
if(stepx[l1].empty()) return -1;
while(!stepx[l1].empty()){
x=stepx[l1].front();
stepx[l1].pop_front();
y=stepy[l1].front();
stepy[l1].pop_front();
for(int i=0;i<8;++i){
int tx=x+MOVES[i][0],ty=y+MOVES[i][1];
if (b[tx][ty]==OUT) continue;
if (b[tx][ty]==VISITED) continue;
if (b[tx][ty]==TARGET) return level;
b[tx][ty]=VISITED;
stepx[l2].push_back(tx);
stepy[l2].push_back(ty);
}
}
l1^=l2^=l1^=l2;
}
return -1;
}

int main() {
for(char f[3],t[3];cin>>f>>t;){
const int xf=f[0]-'a',yf=f[1]-'1',xt=t[0]-'a',yt=t[1]-'1';
board b={OUT};
for(int i=2;i<10;++i)
for(int j=2;j<10;++j)
b[i][j]=OK;
b[xf+2][yf+2]=VISITED;
b[xt+2][yt+2]=TARGET;
cout<<"To get from "<<f<<" to "<<t<<" takes "<<go(b,xf+2,yf+2)
<<" knight moves."<<endl;
//cout<<go(b,xf+2,yf+2)<<endl;
}
return 0;
}