HDU – Page 5 – hahaschool

HDU 1269 迷宫城堡

January 18, 20152015-01-18hahaschoolLeave a comment

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>


using namespace std;

vector<int> ljb[10005];
vector<int> ljbt[10005];
bool res[10005];

void dfs(bool t,int currNode){
	res[currNode] = true;
	vector<int> now;
	if(t) now = ljbt[currNode];
	else now = ljb[currNode];
	for (int i = 0;i < now.size();i++) {
		if (res[now[i]]) continue;
		dfs(t,now[i]);
	}
}

int main(){
	int n = 0,m = 0;
	while (scanf(" %d %d",&n,&m) != EOF) {
		if (n == 0 && m == 0){
			break;
		}else {
			for (int i = 1;i <= n;i++) {
				ljb[i].clear();
				ljbt[i].clear();
			}
			for (int i = 1;i <= m;i++) {
				int a = 0,b = 0;
				scanf(" %d %d",&a,&b);
				ljb[a].push_back(b);
				ljbt[b].push_back(a);
			}
			bool flag = true;
			memset(res,0,sizeof(res));
			dfs(true,1);
			for (int i = 1;i <= n;i++) {
				if(!res[i]){
					flag = false;
					break;
				}
			}
			if(flag){
				memset(res,0,sizeof(res));
				dfs(false,1);
				for (int i = 1;i <= n;i++) {
					if(!res[i]){
						flag = false;
						break;
					}
				}
			}
			if(flag){
				cout << "Yes" << endl;
			}else{
				cout << "No" << endl;
			}


		}
	}
	return 0;
}

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

using namespace std;

vector<int> ljb[10005];

vector<int> ljbt[10005];

bool res[10005];

void dfs(bool t,int currNode){

res[currNode] = true;

vector<int> now;

if(t) now = ljbt[currNode];

else now = ljb[currNode];

for (int i = 0;i < now.size();i++) {

if (res[now[i]]) continue;

dfs(t,now[i]);

}

int main(){

int n = 0,m = 0;

while (scanf(" %d %d",&n,&m) != EOF) {

if (n == 0 && m == 0){

break;

}else {

for (int i = 1;i <= n;i++) {

ljb[i].clear();

ljbt[i].clear();

}

for (int i = 1;i <= m;i++) {

int a = 0,b = 0;

scanf(" %d %d",&a,&b);

ljb[a].push_back(b);

ljbt[b].push_back(a);

}

bool flag = true;

memset(res,0,sizeof(res));

dfs(true,1);

for (int i = 1;i <= n;i++) {

if(!res[i]){

flag = false;

break;

}

if(flag){

memset(res,0,sizeof(res));

dfs(false,1);

for (int i = 1;i <= n;i++) {

if(!res[i]){

flag = false;

break;

}

if(flag){

cout << "Yes" << endl;

}else{

cout << "No" << endl;

}

return 0;

}

这个问题的类型是有向图强连通，有几种好的固定算法。我会开个小总结的。

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>


using namespace std;

vector<int> ljb[10005];

bool vis[10005];
bool instk[10005];
int dfn[10005];
int low[10005];
int tim = 0;
stack<int> stk;
vector<vector<int> > ccs;

void dfs(int currNode){
    vis[currNode] = true;
    dfn[currNode] = low[currNode] = tim++;
    stk.push(currNode);
    instk[currNode] = true;
    vector<int> now = ljb[currNode];
    for (int i = 0;i < now.size(); i++) {
        if (!vis[now[i]]) {
            dfs(now[i]);
            low[currNode] = min(low[currNode],low[now[i]]);
        }else if (instk[now[i]]) {
                low[currNode] = min(low[currNode],dfn[now[i]]);
        }
    }
    if (dfn[currNode] == low[currNode]) {
        int tmp = 0;
        vector<int> res;
        while (currNode != tmp) {
            tmp = stk.top();
            res.push_back(tmp);
            //cout << tmp << "~";
            stk.pop();
            instk[tmp] = false;
        }
        //sort(res.begin(),res.end());
        ccs.push_back(res);
        //cout << endl;
    }
}


int main(){
    int n = 0,m = 0;
    while (scanf(" %d %d",&n,&m) != EOF) {
        if (n == 0 && m == 0){
            break;
        }else {
            for (int i = 1;i <= n;i++) {
                ljb[i].clear();
            }
            for (int i = 1;i <= m;i++) {
                int a= 0,b = 0;
                scanf(" %d %d",&a,&b);
                ljb[a].push_back(b);
            }
            memset(vis, 0, sizeof(vis));
            memset(instk, 0, sizeof(instk));
            memset(dfn, 0, sizeof(dfn));
            memset(low, 0, sizeof(low));
            ccs.clear();
            while (!stk.empty()) {
                stk.pop();
            }
            dfs(1);
            bool flag = false;
            for (int i = 0; i < ccs.size(); i++) {
                if (ccs[i].size() == n) {
                    flag = true;
                }
            }
            if (flag) {
                cout << "Yes" << endl;
            }else {
                cout << "No" << endl;
            }
        }
    }
    return 0;
}

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

using namespace std;

vector<int> ljb[10005];

bool vis[10005];

bool instk[10005];

int dfn[10005];

int low[10005];

int tim = 0;

stack<int> stk;

vector<vector<int> > ccs;

void dfs(int currNode){

vis[currNode] = true;

dfn[currNode] = low[currNode] = tim++;

stk.push(currNode);

instk[currNode] = true;

vector<int> now = ljb[currNode];

for (int i = 0;i < now.size(); i++) {

if (!vis[now[i]]) {

dfs(now[i]);

low[currNode] = min(low[currNode],low[now[i]]);

}else if (instk[now[i]]) {

low[currNode] = min(low[currNode],dfn[now[i]]);

}

if (dfn[currNode] == low[currNode]) {

int tmp = 0;

vector<int> res;

while (currNode != tmp) {

tmp = stk.top();

res.push_back(tmp);

//cout << tmp << "~";

stk.pop();

instk[tmp] = false;

}

//sort(res.begin(),res.end());

ccs.push_back(res);

//cout << endl;

}

int main(){

int n = 0,m = 0;

while (scanf(" %d %d",&n,&m) != EOF) {

if (n == 0 && m == 0){

break;

}else {

for (int i = 1;i <= n;i++) {

ljb[i].clear();

}

for (int i = 1;i <= m;i++) {

int a= 0,b = 0;

scanf(" %d %d",&a,&b);

ljb[a].push_back(b);

}

memset(vis, 0, sizeof(vis));

memset(instk, 0, sizeof(instk));

memset(dfn, 0, sizeof(dfn));

memset(low, 0, sizeof(low));

ccs.clear();

while (!stk.empty()) {

stk.pop();

}

dfs(1);

bool flag = false;

for (int i = 0; i < ccs.size(); i++) {

if (ccs[i].size() == n) {

flag = true;

}

if (flag) {

cout << "Yes" << endl;

}else {

cout << "No" << endl;

}

return 0;

}

HDU 1908 Double Queue

January 17, 20152015-01-17hahaschoolLeave a comment

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <map>
#include <stack>


using namespace std;



int main(){
    multiset<pair<int, int> > q;
    int cmd = 0;
    while (scanf(" %d",&cmd) != EOF){
        if (!cmd) {
            break;
        }else if (cmd == 1) {
            //add client
            int k,p;
            scanf(" %d %d",&k,&p);
            q.insert(make_pair(p, k));

        }else if (cmd == 2) {
            //high priority
            if(q.size()==0){
                cout << 0 << endl;
                continue;
            }
            multiset<pair<int, int> >::iterator it = q.end();
            it--;
            cout << (*it).second << endl;
            q.erase(it);

        }else if(cmd == 3){
            //low proirity
            if(q.size()==0){
                cout << 0 << endl;
                continue;
            }
            multiset<pair<int, int> >::iterator it = q.begin();
            cout << (*it).second << endl;
            q.erase(it);

        }
    }
    return 0;

}

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <map>

#include <stack>

using namespace std;

int main(){

multiset<pair<int, int> > q;

int cmd = 0;

while (scanf(" %d",&cmd) != EOF){

if (!cmd) {

break;

}else if (cmd == 1) {

//add client

int k,p;

scanf(" %d %d",&k,&p);

q.insert(make_pair(p, k));

}else if (cmd == 2) {

//high priority

if(q.size()==0){

cout << 0 << endl;

continue;

}

multiset<pair<int, int> >::iterator it = q.end();

it--;

cout << (*it).second << endl;

q.erase(it);

}else if(cmd == 3){

//low proirity

if(q.size()==0){

cout << 0 << endl;

continue;

}

multiset<pair<int, int> >::iterator it = q.begin();

cout << (*it).second << endl;

q.erase(it);

}

return 0;

}

那帮老逼太机智了，双端优先队列他们居然用map实现也是diao。。。

HDU 1702 ACboy needs your help again!

January 17, 20152015-01-17hahaschoolLeave a comment

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <map>
#include <stack>


using namespace std;

int main(){
    int casecnt;
    cin >> casecnt;
    while (casecnt--) {
        int cnt;
        string type;
        cin >> cnt >> type;
        if (type == "FIFO") {
            //queue resolutions
            queue<int> q;
            while (cnt--) {
                string cmd;
                int arg;
                cin >> cmd;
                if (cmd == "IN") {
                    cin >> arg;
                    q.push(arg);
                }else{
                    if (q.size() == 0) {
                        cout << "None" << endl;
                        continue;
                    }
                    cout << q.front() << endl;
                    q.pop();
                }

            }
        }else{
            //stack resolutions
            stack<int> s;
            while (cnt--) {
                string cmd;
                int arg;
                cin >> cmd;
                if (cmd == "IN") {
                    cin >> arg;
                    s.push(arg);
                }else{
                    if (s.size() == 0) {
                        cout << "None" << endl;
                        continue;
                    }
                    cout << s.top() << endl;
                    s.pop();
                }
            }

        }
    }


    return 0;
}

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <map>

#include <stack>

using namespace std;

int main(){

int casecnt;

cin >> casecnt;

while (casecnt--) {

int cnt;

string type;

cin >> cnt >> type;

if (type == "FIFO") {

//queue resolutions

queue<int> q;

while (cnt--) {

string cmd;

int arg;

cin >> cmd;

if (cmd == "IN") {

cin >> arg;

q.push(arg);

}else{

if (q.size() == 0) {

cout << "None" << endl;

continue;

}

cout << q.front() << endl;

q.pop();

}

}else{

//stack resolutions

stack<int> s;

while (cnt--) {

string cmd;

int arg;

cin >> cmd;

if (cmd == "IN") {

cin >> arg;

s.push(arg);

}else{

if (s.size() == 0) {

cout << "None" << endl;

continue;

}

cout << s.top() << endl;

s.pop();

}

return 0;

}

STL小练习

其实手写应该会很带感

HDU 1264 Counting Squares

January 17, 20152015-01-17hahaschoolLeave a comment

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>

using namespace std;

#define MAXN 1000


bool board[MAXN][MAXN];


void outputBoard(){
    int res = 0;
    for (int x = 0; x < MAXN-1; x++) {
        for (int y = 0; y< MAXN;y++){
            if (board[y][x]) {
                res++;
            }
        }
    }
    cout << res << endl;
    memset(board, 0, sizeof(board));
}

int main(){
    memset(board, 0, sizeof(board));
    int startx = 0,starty = 0,endx = 0,endy = 0;
    while (cin >> startx >> starty >> endx >> endy){
        if (endx < startx) {
            swap(startx, endx);
        }
        if (endy < starty) {
            swap(starty, endy);
        }
        if (startx == -1 && starty == -1 && endx == -1 && endy == -1) {
            outputBoard();
            continue;
        }
        if (startx == -2 && starty == -2 && endx == -2 && endy == -2) {
            outputBoard();
            break;
        }
        for (int x = startx; x <= endx-1; x++) {
            for (int y = starty; y<= endy-1;y++){
                board[y][x] = true;
            }
        }


    }


}

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

using namespace std;

#define MAXN 1000

bool board[MAXN][MAXN];

void outputBoard(){

int res = 0;

for (int x = 0; x < MAXN-1; x++) {

for (int y = 0; y< MAXN;y++){

if (board[y][x]) {

res++;

}

cout << res << endl;

memset(board, 0, sizeof(board));

}

int main(){

memset(board, 0, sizeof(board));

int startx = 0,starty = 0,endx = 0,endy = 0;

while (cin >> startx >> starty >> endx >> endy){

if (endx < startx) {

swap(startx, endx);

}

if (endy < starty) {

swap(starty, endy);

}

if (startx == -1 && starty == -1 && endx == -1 && endy == -1) {

outputBoard();

continue;

}

if (startx == -2 && starty == -2 && endx == -2 && endy == -2) {

outputBoard();

break;

}

for (int x = startx; x <= endx-1; x++) {

for (int y = starty; y<= endy-1;y++){

board[y][x] = true;

}

两个对角线坐标的先后顺序不一定要自己判断，不好好看题谁也救不了。。。

HDU 1062 Text Reverse

January 16, 20152015-01-16hahaschoolLeave a comment

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>

using namespace std;




int main(int argc, char *argv[]) {
	int cnt;
	cin >> cnt;
	getchar();
	while (cnt--) {
		string str;
		getline(cin,str);
		str += ' ';
		string res;
		int startpos = 0,endpos = 0,status = 0;;
		for (int i = 0;i < str.size();i++) {
			if(str[i] == ' ' && status == 0){
				res += ' ';
			}
			else if (status == 0) {
				startpos = i;
				status++;
			}else if(status == 1 && str[i] == ' '){
				endpos = i-1;
				status--;
				for (int j = endpos;j >= startpos;j--) {
					res += str[j];
				}
				res += ' ';
			}else{

			}

		}
		res.erase(res.end()-1,res.end());
		cout << res << endl;
	}
	return 0;
}

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

using namespace std;

int main(int argc, char *argv[]) {

int cnt;

cin >> cnt;

getchar();

while (cnt--) {

string str;

getline(cin,str);

str += ' ';

string res;

int startpos = 0,endpos = 0,status = 0;;

for (int i = 0;i < str.size();i++) {

if(str[i] == ' ' && status == 0){

res += ' ';

}

else if (status == 0) {

startpos = i;

status++;

}else if(status == 1 && str[i] == ' '){

endpos = i-1;

status--;

for (int j = endpos;j >= startpos;j--) {

res += str[j];

}

res += ' ';

}else{

}

res.erase(res.end()-1,res.end());

cout << res << endl;

}

return 0;

}

请替我问候出题人全家。。。

这个题绝对是良／心／题；为啥你会黄呢？给你个样例吧：
—-watashi-wa-saiko–desu!—-
—-ihsataw-aw-okias–!used—-

上面的－都是空格嗯。。。

HDU 1039 Easier Done Than Said?

January 16, 20152015-01-16hahaschoolLeave a comment

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>

using namespace std;

int main(int argc, char *argv[]) {
	string str;
	while (cin >> str) {
		if (str == "end"){
			break;
		}
		//vowel check
		bool vowelflag = false;
		for (int i = 0;i < str.size();i++) {
			if(str[i] == 'a' || str[i] == 'e' || str[i] == 'i' || str[i] == 'o' || str[i] == 'u'){
				vowelflag = true;
				break;
			}
		}
		bool onajiflag = false;
		char prev = str[0];
		for (int i = 1;i < str.size();i++) {
			if(str[i] == prev){
				if(prev == 'e' || prev == 'o'){
					continue;
				}else {
					onajiflag = true;
					break;
				}
			}
			prev = str[i];
		}
		bool threeflag = false;
		for (int i = 0;i < (int)str.size()-2;i++) {//kengkengkeng
			bool isvowel[3] = {false,false,false};
			for (int j = 0;j <= 2;j++){
			if(str[i+j] == 'a' || str[i+j] == 'e' || str[i+j] == 'i' || str[i+j] == 'o' || str[i+j] == 'u'){
				isvowel[j] = true;
			}
			}
			if((isvowel[0] && isvowel[1] && isvowel[2]) || (!isvowel[0] && !isvowel[1] && !isvowel[2])){
				threeflag = true;
				break;
			}
		}

		//cout << vowelflag << onajiflag << threeflag << endl;
		if(vowelflag && !onajiflag && !threeflag)
		cout << '<' << str << '>' << " is acceptable." << endl;
		else cout << '<' << str << '>' << " is not acceptable." << endl;

	}
	return 0;
}

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

using namespace std;

int main(int argc, char *argv[]) {

string str;

while (cin >> str) {

if (str == "end"){

break;

}

//vowel check

bool vowelflag = false;

for (int i = 0;i < str.size();i++) {

if(str[i] == 'a' || str[i] == 'e' || str[i] == 'i' || str[i] == 'o' || str[i] == 'u'){

vowelflag = true;

break;

}

bool onajiflag = false;

char prev = str[0];

for (int i = 1;i < str.size();i++) {

if(str[i] == prev){

if(prev == 'e' || prev == 'o'){

continue;

}else {

onajiflag = true;

break;

}

prev = str[i];

}

bool threeflag = false;

for (int i = 0;i < (int)str.size()-2;i++) {//kengkengkeng

bool isvowel[3] = {false,false,false};

for (int j = 0;j <= 2;j++){

if(str[i+j] == 'a' || str[i+j] == 'e' || str[i+j] == 'i' || str[i+j] == 'o' || str[i+j] == 'u'){

isvowel[j] = true;

}

if((isvowel[0] && isvowel[1] && isvowel[2]) || (!isvowel[0] && !isvowel[1] && !isvowel[2])){

threeflag = true;

break;

}

//cout << vowelflag << onajiflag << threeflag << endl;

if(vowelflag && !onajiflag && !threeflag)

cout << '<' << str << '>' << " is acceptable." << endl;

else cout << '<' << str << '>' << " is not acceptable." << endl;

}

return 0;

}

c++课后作业系列，但是有坑。

注意看我标kengkengkeng那里，string.size()默认返回的类型是unsigned long，当字符串长度为1时，减去2会发生啥估计大家也都清楚，

HDU 1020 Encoding

January 16, 20152015-01-16hahaschoolLeave a comment

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>

using namespace std;

int main(int argc, char *argv[]) {
	int cnt;
	cin >> cnt;
	while (cnt--) {
		string str;
		cin >> str;
		string res;
		char curr = str[0];
		int occ = 1;
		for (int i = 1;i < str.size();i++) {
			if(str[i] != curr){
				if(occ == 1){

				}else{
					char tmp[5];
					sprintf(tmp,"%d",occ);
					res += tmp;
				}
				res += curr;
				curr = str[i];
				occ = 1;
			}else{
				occ++;
			}
		}
		if(occ == 1){

		}else{
			char tmp[5];
			sprintf(tmp,"%d",occ);
			res += tmp;
		}
		res += curr;
		cout << res << endl;

	}
	return 0;
}

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

using namespace std;

int main(int argc, char *argv[]) {

int cnt;

cin >> cnt;

while (cnt--) {

string str;

cin >> str;

string res;

char curr = str[0];

int occ = 1;

for (int i = 1;i < str.size();i++) {

if(str[i] != curr){

if(occ == 1){

}else{

char tmp[5];

sprintf(tmp,"%d",occ);

res += tmp;

}

res += curr;

curr = str[i];

occ = 1;

}else{

occ++;

}

if(occ == 1){

}else{

char tmp[5];

sprintf(tmp,"%d",occ);

res += tmp;

}

res += curr;

cout << res << endl;

}

return 0;

}

非常非常非常水。连sprintf都放跑了。。。

HDU 1251 统计难题

January 16, 20152015-01-16hahaschoolLeave a comment

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>

using namespace std;

struct trieNode{
    trieNode* child[30];
    int count;
    bool exist;
    trieNode(){
        memset(child, NULL, sizeof(child));
        count = 0;
        exist = false;
    }
} trie,*currNode;


int main(){
    string str;
    bool status = true;
    while (getline(cin,str)) {
        if (str.size() == 0) {
            status = false;
            continue;
        }
        if (status) {
            currNode = &trie;
            for (int i = 0; i < str.size(); i++) {
                if((*currNode).child[str[i]-'a'] == NULL){
                    (*currNode).child[str[i]-'a'] = new trieNode;

                }else{
                    (*currNode).child[str[i]-'a']->count++;
                    if (i == str.size()-1) (*currNode).child[str[i]-'a']->exist = true;
                }
                currNode = (*currNode).child[str[i]-'a'];
            }
        }else{
            currNode = &trie;
            bool flag = false;
            for (int i = 0; i < str.size(); i++) {
                if((*currNode).child[str[i]-'a'] == NULL){
                    break;
                }else{
                    if (i == str.size()-1) {
                        cout << (*currNode).child[str[i]-'a']->count+1<< endl;
                        flag = true;
                    }
                }
                currNode = (*currNode).child[str[i]-'a'];
            }
            if (!flag) {
                cout << 0 << endl;
            }

        }

    }

}

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

using namespace std;

struct trieNode{

trieNode* child[30];

int count;

bool exist;

trieNode(){

memset(child, NULL, sizeof(child));

count = 0;

exist = false;

}

} trie,*currNode;

int main(){

string str;

bool status = true;

while (getline(cin,str)) {

if (str.size() == 0) {

status = false;

continue;

}

if (status) {

currNode = &trie;

for (int i = 0; i < str.size(); i++) {

if((*currNode).child[str[i]-'a'] == NULL){

(*currNode).child[str[i]-'a'] = new trieNode;

}else{

(*currNode).child[str[i]-'a']->count++;

if (i == str.size()-1) (*currNode).child[str[i]-'a']->exist = true;

}

currNode = (*currNode).child[str[i]-'a'];

}

}else{

currNode = &trie;

bool flag = false;

for (int i = 0; i < str.size(); i++) {

if((*currNode).child[str[i]-'a'] == NULL){

break;

}else{

if (i == str.size()-1) {

cout << (*currNode).child[str[i]-'a']->count+1<< endl;

flag = true;

}

currNode = (*currNode).child[str[i]-'a'];

}

if (!flag) {

cout << 0 << endl;

}

涨姿势了，new开辟的内存空间中变量是没有被初始化的，要自己写一个初始化的constructor才可以，否则就是RERERE。。。

然后Trie的实现方法基本就是这样，指针写法还是比较好弄的，但是以后还要考虑垃圾回收的问题。

HDU 1007 Quoit Design

January 05, 20152015-01-05hahaschoolOne Comment

#include <iostream>
#include <cmath>
#include <cstdio>
#include <algorithm>

#define MAXD 998998998998

using namespace std;

struct point{
	double x,y;
}p[100005];

bool cmp(point a,point b){
	return a.x<b.x;
}

int main(){
	int n = 0;
	while (cin >> n && n){
		for (int i = 1;i <= n;i++){
			cin >> p[i].x >> p[i].y;
		}
		sort(p+1,p+1+n,cmp);
		double res = MAXD;
		for (int i = 1;i <= n;i++){
			for (int j = i+1;j <= n;j++){
				res = min(sqrt((p[i].x-p[j].x)*(p[i].x-p[j].x)+(p[i].y-p[j].y)*(p[i].y-p[j].y))/2,res);
			}
		}
		printf("%.2lfn",res);
	}
	return 0;
}

#include <iostream>

#include <cmath>

#include <cstdio>

#include <algorithm>

#define MAXD 998998998998

using namespace std;

struct point{

double x,y;

}p[100005];

bool cmp(point a,point b){

return a.x<b.x;

}

int main(){

int n = 0;

while (cin >> n && n){

for (int i = 1;i <= n;i++){

cin >> p[i].x >> p[i].y;

}

sort(p+1,p+1+n,cmp);

double res = MAXD;

for (int i = 1;i <= n;i++){

for (int j = i+1;j <= n;j++){

res = min(sqrt((p[i].x-p[j].x)*(p[i].x-p[j].x)+(p[i].y-p[j].y)*(p[i].y-p[j].y))/2,res);

}

printf("%.2lfn",res);

}

return 0;

}

这个题略邪乎，数据好像不对。