}
poj 1035 Spell checker
开始做字符串的题目，本人觉得最头痛噶野，好鬼唔锺意处理字符串噶野。不过唯有硬住头皮上啦。
呢条题有个奇怪噶地方，就系用STL做的话，点都系TLE，后来改翻用C语言甘样慢慢搞先过，重要用左将近1s.
注意：（1）用另一个字符数组记录字典，然后排序，用于二分查找的。
（2）先处理与被检查数组相同长度的，然后系，比距长的，最后系比距短的。
（3）数组开得足够大啦
#include
int cmp(const void *p, const void *q) { return strcmp((char *) p, (char *) q); }
struct s {
char word[20]; int len; } str1[10005];
char str2[10005][20], bc[20], ch[20], *p; int bcl, n;
void input() { int i = 0;
while (strcmp(gets(str1[++i].word), \ str1[i].len = strlen(str1[i].word); strcpy(str2[i], str1[i].word); }
n = i;
qsort(str2 + 1, n, sizeof (str2[0]), cmp); }
void solve() { int i, j, k;
while (strcmp(gets(bc), \ bcl = strlen(bc);
p = (char *) bsearch(&bc, str2 + 1, n, sizeof (str2[0]), cmp); if (p)
cout << bc << \ else {
cout << bc << \
for (i = 1; i <= n; i++) { if (str1[i].len == bcl) { int flag = 0;
for (j = 0; j < str1[i].len; j++) { if (str1[i].word[j] != bc[j]) flag++; }
if (flag < 2) cout << \ } else if (bcl == str1[i].len + 1) {
for (j = 0; j < bcl; j++) { strcpy(ch, bc);
for (k = j; k < bcl; k++) ch[k] = ch[k + 1];
//cout< } else if (bcl == str1[i].len - 1) { for (j = 0; j < str1[i].len; j++) { strcpy(ch, str1[i].word); for (k = j; k < str1[i].len; k++) ch[k] = ch[k + 1]; //cout< printf(\ break; } } } } cout << endl; } } } int main() { input(); solve(); return 0; } POJ 1200 Crazy Search 这个是说一段字符串 有nc种字符组成 问长度为n的不同的字符串有多少个 非常关键的一条信息是 nc^n最多只有16 000 000 so 我们用nc进制的HASH来做 #include char str[20000000]; char asca[128]; int hash[16000005]; int main() { while(scanf(\ { scanf(\ int i=0; int j; int key=0; while(str[i]) { if(asca[str[i]]==0) asca[str[i]]=++key; i++; if(key==nc) break; } int len=strlen(str); int sum; int cnt=0; for(i=0;i+n-1 sum=0; for(j=i;j<=i+n-1;j++) { sum=sum*nc+asca[str[j]]-1; } if(hash[sum]==0) { hash[sum]=1; cnt++; } } printf(\ } } POJ 2002 hash(枚举+哈希) 简单hash,具体做法是枚举任意两个点，因为有这由两个点所构成的边属于某个正方形那么可以计算出属于该正方形的另外两个点。如有两个点(a1,a2)和(b1,b2),那么如果点(a1+(a2-b2), a2-(a1-b1))和点(b1+(a2-b2), b2-(a1-b1))都存在则这四个点可以构成一个正方形。同时如果点(a1-(a2-b2), a2+(a1-b1))和点(b1-(a2-b2), b2+(a1-b1))存在那么点(a1,a2)，(b1,b2)，(a1-(a2-b2), a2+(a1-b1))和(b1-(a2-b2), b2+(a1-b1))又可以构成一个正方形，差不多思想就是这个样子，不过好像时间比较长1500多ms，应该还可以优化。 #include point() { index=-1; next=NULL; } point(int index,point* next) { this->index=index; this->next=next; } int index; point* next; }; int a[1001][2]; bool find(point hash_table[],int,int); int main() { int n,value; while(scanf(\ { long result=0; point hash_table[40001]; for(int e=0;e scanf(\ value=a[e][0]+a[e][1]; if(value<0)value=-value; if(hash_table[value].index==-1)hash_table[value].index=e; else { point* p=&hash_table[value]; while(p->next!=NULL)p=p->next; p->next=new point(e,NULL); } } for(int x=0;x int d_x=a[x][0]-a[y][0]; int d_y=a[x][1]-a[y][1]; if(find(hash_table,a[x][0]-d_y,a[x][1]+d_x)&& find(hash_table,a[y][0]-d_y,a[y][1]+d_x)) result++; if(find(hash_table,a[x][0]+d_y,a[x][1]-d_x)&& find(hash_table,a[y][0]+d_y,a[y][1]-d_x)) result++; } printf(\ } return 0; } bool find(point hash_table[40001],int x,int y) { int value=(x+y)<0?-(x+y):(x+y); point* p=&hash_table[value]; if(p->index==-1)return false; while(p!=NULL) { if(a[p->index][0]==x&&a[p->index][1]==y)return true; p=p->next; } return false; }