1:拼写检查

描述

现在有一些英语单词需要做拼写检查，你的工具是一本词典。需要检查的单词，有的是词典中的单词，有的与词典中的单词相似，你的任务是发现这两种情况。单词A与单词B相似的情况有三种：

1、删除单词A的一个字母后得到单词B；

2、用任意一个字母替换单词A的一个字母后得到单词B；

3、在单词A的任意位置增加一个字母后得到单词B。

你的任务是发现词典中与给定单词相同或相似的单词。

输入

第一部分是词典中的单词，从第一行开始每行一个单词，以"#"结束。词典中的单词保证不重复，最多有10000个。
第二部分是需要查询的单词，每行一个，以"#"结束。最多有50个需要查询的单词。
词典中的单词和需要查询的单词均由小写字母组成，最多包含15个字符。

输出

按照输入的顺序，为每个需要检查的单词输出一行。如果需要检查的单词出现在词典中，输出“?x is correct"，?x代表需要检查的单词。如果需要检查的单词没有出现在词典中，则输出"?x: ?x1 ?x2 ...?xn"，其中?x代表需要检查的单词，?x1...?xn代表词典中与需要检查的单词相似的单词，这些单词中间以空格隔开。如果没有相似的单词， 输出"?x:"即可。

样例输入

i
is
has
have
be
my
more
contest
me
too
if
award
#
me
aware
m
contest
hav
oo
or
i
fi
mre
#

样例输出

me is correct
aware: award
m: i my me
contest is correct
hav: has have
oo: too
or:
i is correct
fi: i
mre: more me

刪除位置窮舉 O(len)

插入位置窮舉 O(len * 26)

替換字元窮舉 O(len * 26)

#include <stdio.h>
#include <iostream>
#include <set>
#include <string.h>
#include <map>
using namespace std;
char word[10005][20], s[20];
int wlen[10005];
set<string> S[20];
map<string, int> M;
int main() {
    int n = 0;
    int i, j, k;
    while(scanf("%s", &word[n]) == 1) {
        if(!strcmp(word[n], "#"))
            break;
        wlen[n] = strlen(word[n]);
        S[wlen[n]].insert(word[n]);
        M[word[n]] = n;
        n++;
    }
    while(scanf("%s", s) == 1) {
        if(!strcmp(s, "#"))
            break;
        int len = strlen(s);
        if(S[len].find(s) != S[len].end()) {
            printf("%s is correct\n", s);
            continue;
        }
        printf("%s:", s);
        char err[20];
        for(i = 1; i < len; i++)
            err[i-1] = s[i];
        err[len-1] = '\0';
        set<string> ret;
        for(i = 0; i < len; i++) {
            if(S[len-1].find(err) != S[len-1].end())
                ret.insert(err);
            err[i] = s[i];
        }
        for(i = 0; i < len; i++)
            err[i] = s[i];
        err[len] = '\0';
        for(i = 0; i < len; i++) {
            for(j = 'a'; j <= 'z'; j++) {
                if(j == s[i])    continue;
                err[i] = j;
                if(S[len].find(err) != S[len].end())
                    ret.insert(err);
            }
            err[i] = s[i];
        }   
        for(i = 0; i < len; i++)
            err[i+1] = s[i];   
        err[len+1] = '\0';
        for(i = 0; i <= len; i++) {
            for(j = 'a'; j <= 'z'; j++) {
                err[i] = j;
                if(S[len+1].find(err) != S[len+1].end())
                    ret.insert(err);
            }
            err[i] = s[i];
        }
        set<int> R;
        for(set<string>::iterator it = ret.begin();
            it != ret.end(); it++) {
            R.insert(M[*it]);
        }
        for(set<int>::iterator it = R.begin();
            it != R.end(); it++)
            printf(" %s", word[*it]);
        puts("");
    }
    return 0;
}

2:正方形

描述

给定直角坐标系中的若干整点，请寻找可以由这些点组成的正方形，并统计它们的个数。

输入

包括多组数据，每组数据的第一行是整点的个数n(1<=n<=1000)，其后n行每行由两个整数组成，表示一个点的x、y坐标。输入保证一组数据中不会出现相同的点，且坐标的绝对值小于等于20000。输入以一组n=0的数据结尾。

输出

对于每组输入数据，输出一个数，表示这组数据中的点可以组成的正方形的数量。

样例输入

4
1 0
0 1
1 1
0 0
9
0 0
1 0
2 0
0 2
1 2
2 2
0 1
1 1
2 1
4
-2 5
3 7
0 0
5 2
0

样例输出

1
6
1 

考慮只向單邊進行增加，找到另外兩點。

對於窮舉的兩點得到線的法向量，再對這兩點走法向量分別拉出相對應的兩點。

#include <stdio.h>
#include <set>
#include <algorithm>
using namespace std;
struct Pt {
    int x, y;
    Pt(int a=0, int b=0):
        x(a), y(b) {}
    bool operator<(const Pt &a) const {
        if(x != a.x)
            return x < a.x;
        return y < a.y;
    }
};
int main() {
    int n;
    int i, j, k;
    Pt D[1005];
    while(scanf("%d", &n) == 1 && n) {
        for(i = 0; i < n; i++)
            scanf("%d %d", &D[i].x, &D[i].y);
        sort(D, D+n);
        int ret = 0;
        set<int> S[40005];
        for(i = 0; i < n; i++)
            S[D[i].x+20000].insert(D[i].y);
        int x, y;
        for(i = 0; i < n; i++) {
            for(j = i+1; j < n; j++) {
                int dx = D[j].x - D[i].x;
                int dy = D[j].y - D[i].y;
                x = D[i].x - dy;
                y = D[i].y + dx;
                if(-dy < 0)    continue;
                if(x + 20000 < 0 || x + 20000 >= 40005)
                    continue;
                if(S[x+20000].find(y) == S[x+20000].end())
                    continue;
                x = D[j].x - dy;
                y = D[j].y + dx;
                if(x + 20000 < 0 || x + 20000 >= 40005)
                    continue;
                if(S[x+20000].find(y) == S[x+20000].end())
                    continue;/*
                printf("%d %d\n", D[i].x, D[i].y);
                printf("%d %d\n", D[j].x, D[j].y);
                printf("%d %d\n", x, y);
                printf("x ------ %d %d\n", dx, dy);*/
                ret++;
            }
        }
        printf("%d\n", ret);
    }
    return 0;
}

3:发现它，抓住它

描述

一 个城市中有两个犯罪团伙A和B，你需要帮助警察判断任意两起案件是否是同一个犯罪团伙所为，警察所获得的信息是有限的。假设现在有N起案件 （N<=100000），编号为1到N，每起案件由团伙A或团伙B所为。你将按时间顺序获得M条信息（M<=100000），这些信息分为两 类：

1. D [a] [b]

其中[a]和[b]表示两起案件的编号，这条信息表明它们属于不同的团伙所为

2. A [a] [b]

其中[a]和[b]表示两起案件的编号，这条信息需要你回答[a]和[b]是否是同一个团伙所为

注意你获得信息的时间是有先后顺序的，在回答的时候只能根据已经接收到的信息做出判断。

输入

第一行是测试数据的数量T（1<=T<=20）。
每组测试数据的第一行包括两个数N和M，分别表示案件的数量和信息的数量，其后M行表示按时间顺序收到的M条信息。

输出

对于每条需要回答的信息，你需要输出一行答案。如果是同一个团伙所为，回答"In the same gang."，如果不是，回答"In different gangs."，如果不确定，回答”Not sure yet."。

样例输入

1
5 5
A 1 2
D 1 2
A 1 2
D 2 4
A 1 4

样例输出

Not sure yet.
In different gangs.
In the same gang.