解题报告 – Page 16

HDU 1233 还是畅通工程

January 19, 20152015-01-19hahaschoolLeave 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 <stack>

using namespace std;

struct requestType{
    int a;
    int b;
    int cost;
};
vector<requestType> req;

int parent_bcj[1005];

void init_bcj(){
    for (int i = 0; i < 1005; i++) {
        parent_bcj[i] = i;
    }
}

int query_bcj(int currNode){
    if (parent_bcj[currNode] == currNode) {
        return currNode;
    }else return parent_bcj[currNode] = query_bcj(parent_bcj[currNode]);
}

void unify_bcj(int a,int b){
    int pa = query_bcj(a);
    int pb = query_bcj(b);
    if (pa == a) {
        parent_bcj[pa] = pb;
    }else {
        parent_bcj[pb] = pa;
    }

}

bool check_bcj(int a,int b){
    int pa = query_bcj(a);
    int pb = query_bcj(b);
    if (pa == pb) {
        return true;
    }else{
        return false;
    }
}

bool cmp(requestType a,requestType b){
    return a.cost < b.cost;
}

int main(){
    int n= 0;
    while (cin >> n && n) {
        init_bcj();
        req.clear();
        for (int i = 1; i <= n*(n-1)/2; i++) {
            int a,b,c;
            scanf(" %d %d %d",&a,&b,&c);
            requestType tmp;
            tmp.a = a,tmp.b = b,tmp.cost = c;
            req.push_back(tmp);
        }
        sort(req.begin(), req.end(), cmp);
        int res = 0;
        for (int i = 0; i < req.size(); i++) {
            requestType &now = req[i];
            if (check_bcj(now.a, now.b)) {
                continue;
            }else{
                res += now.cost;
                unify_bcj(now.a, now.b);
            }
        }
        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>

#include <stack>

using namespace std;

struct requestType{

int a;

int b;

int cost;

};

vector<requestType> req;

int parent_bcj[1005];

void init_bcj(){

for (int i = 0; i < 1005; i++) {

parent_bcj[i] = i;

}

int query_bcj(int currNode){

if (parent_bcj[currNode] == currNode) {

return currNode;

}else return parent_bcj[currNode] = query_bcj(parent_bcj[currNode]);

}

void unify_bcj(int a,int b){

int pa = query_bcj(a);

int pb = query_bcj(b);

if (pa == a) {

parent_bcj[pa] = pb;

}else {

parent_bcj[pb] = pa;

}

bool check_bcj(int a,int b){

int pa = query_bcj(a);

int pb = query_bcj(b);

if (pa == pb) {

return true;

}else{

return false;

}

bool cmp(requestType a,requestType b){

return a.cost < b.cost;

}

int main(){

int n= 0;

while (cin >> n && n) {

init_bcj();

req.clear();

for (int i = 1; i <= n*(n-1)/2; i++) {

int a,b,c;

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

requestType tmp;

tmp.a = a,tmp.b = b,tmp.cost = c;

req.push_back(tmp);

}

sort(req.begin(), req.end(), cmp);

int res = 0;

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

requestType &now = req[i];

if (check_bcj(now.a, now.b)) {

continue;

}else{

res += now.cost;

unify_bcj(now.a, now.b);

}

cout << res << endl;

}

return 0;

}

拿1232的代码改一下就好了。

HDU 1232 畅通工程

January 19, 20152015-01-19hahaschoolLeave 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 <stack>

using namespace std;

struct requestType{
    int a;
    int b;
    int cost;
};
vector<requestType> req;

int parent_bcj[1005];

void init_bcj(){
    for (int i = 0; i < 1005; i++) {
        parent_bcj[i] = i;
    }
}

int query_bcj(int currNode){
    if (parent_bcj[currNode] == currNode) {
        return currNode;
    }else return parent_bcj[currNode] = query_bcj(parent_bcj[currNode]);
}

void unify_bcj(int a,int b){
    int pa = query_bcj(a);
    int pb = query_bcj(b);
    if (pa == a) {
        parent_bcj[pa] = pb;
    }else {
        parent_bcj[pb] = pa;
    }

}

bool check_bcj(int a,int b){
    int pa = query_bcj(a);
    int pb = query_bcj(b);
    if (pa == pb) {
        return true;
    }else{
        return false;
    }
}

bool cmp(requestType a,requestType b){
    return a.cost < b.cost;
}

int main(){
    int n= 0,m = 0;
    while (cin >> n && n) {
        cin >> m;
        init_bcj();
        req.clear();
        for (int i = 1; i <= m; i++) {
            int a,b;
            scanf(" %d %d",&a,&b);
            requestType tmp;
            tmp.a = a,tmp.b = b,tmp.cost = 1;
            req.push_back(tmp);
        }
        sort(req.begin(), req.end(), cmp);
        int res = n-1;
        for (int i = 0; i < req.size(); i++) {
            requestType &now = req[i];
            if (check_bcj(now.a, now.b)) {
                continue;
            }else{
                res -= now.cost;
                unify_bcj(now.a, now.b);
            }
        }
        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>

#include <stack>

using namespace std;

struct requestType{

int a;

int b;

int cost;

};

vector<requestType> req;

int parent_bcj[1005];

void init_bcj(){

for (int i = 0; i < 1005; i++) {

parent_bcj[i] = i;

}

int query_bcj(int currNode){

if (parent_bcj[currNode] == currNode) {

return currNode;

}else return parent_bcj[currNode] = query_bcj(parent_bcj[currNode]);

}

void unify_bcj(int a,int b){

int pa = query_bcj(a);

int pb = query_bcj(b);

if (pa == a) {

parent_bcj[pa] = pb;

}else {

parent_bcj[pb] = pa;

}

bool check_bcj(int a,int b){

int pa = query_bcj(a);

int pb = query_bcj(b);

if (pa == pb) {

return true;

}else{

return false;

}

bool cmp(requestType a,requestType b){

return a.cost < b.cost;

}

int main(){

int n= 0,m = 0;

while (cin >> n && n) {

cin >> m;

init_bcj();

req.clear();

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

int a,b;

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

requestType tmp;

tmp.a = a,tmp.b = b,tmp.cost = 1;

req.push_back(tmp);

}

sort(req.begin(), req.end(), cmp);

int res = n-1;

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

requestType &now = req[i];

if (check_bcj(now.a, now.b)) {

continue;

}else{

res -= now.cost;

unify_bcj(now.a, now.b);

}

cout << res << endl;

}

return 0;

}

Kruskal算法，并查集老写挫，正确的写法是合并操作是把parentA和parentB合并（链接根节点），查询的时候压缩，就是

return parent_bcj[currNode] = query_bcj(parent_bcj[currNode]);

这句。

HDU 1285 确定比赛名次

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>
#include <stack>

using namespace std;

struct typeNode{
    int in;
    vector<int> from;
    vector<int> to;
} node[505];

vector<int> req;
vector<int> res;
int main(){
    int n = 0,m = 0;
    while (cin >> n >> m) {
        req.clear();
        res.clear();
        for (int i = 1; i <= n; i++) {
            node[i].to.clear();
            node[i].from.clear();
            node[i].in = 0;
        }
        for (int i = 1; i <= m; i++) {
            int a = 0,b = 0;
            cin >> b >> a;
            node[b].to.push_back(a);
            node[a].from.push_back(b);
            node[a].in++;
        }
        bool flag = true;
        while (flag) {
            flag = false;
            for (int i = 1; i <= n; i++) {
                if (node[i].in == 0) {
                    res.push_back(i);
                    node[i].in--;
                    flag = true;
                    for (int j = 0; j < node[i].to.size(); j++) {
                        node[node[i].to[j]].in--;
                    }
                    break;
                }
            }
        }
        for (int i = 0; i < res.size();i++) {
            cout << res[i];
            if (i != res.size()-1) {
                cout << " ";
            }
        }
        cout << 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;

struct typeNode{

int in;

vector<int> from;

vector<int> to;

} node[505];

vector<int> req;

vector<int> res;

int main(){

int n = 0,m = 0;

while (cin >> n >> m) {

req.clear();

res.clear();

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

node[i].to.clear();

node[i].from.clear();

node[i].in = 0;

}

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

int a = 0,b = 0;

cin >> b >> a;

node[b].to.push_back(a);

node[a].from.push_back(b);

node[a].in++;

}

bool flag = true;

while (flag) {

flag = false;

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

if (node[i].in == 0) {

res.push_back(i);

node[i].in--;

flag = true;

for (int j = 0; j < node[i].to.size(); j++) {

node[node[i].to[j]].in--;

}

break;

}

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

cout << res[i];

if (i != res.size()-1) {

cout << " ";

}

cout << endl;

}

return 0;

}

拓扑排序相关，还不怎么会，绕了好多弯路，要好好学习总结下嗯-_-#

HDU 1710 Binary Tree Traversals

January 18, 20152015-01-18hahaschoolOne 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 <stack>

using namespace std;

int dlr[1005],ldr[1005],cnt,vis[1005];
stack<int> lrd;

int finddlr(int target){
    for (int i = 0; i < cnt; i++) if (dlr[i] == target) return i;
    return 0;
}

int findldr(int target){
    for (int i = 0; i < cnt; i++) if (ldr[i] == target) return i;
    return -1;
}

int findlen(bool right,int pos){
    //true for right false for left
    if (right) {
        for (int i = pos+1; i < cnt; i++) if (vis[i]) return i-pos-1;
        return cnt-pos-1;
    }else{
        for (int i = pos-1; i >= 0;i--) if (vis[i]) return pos-i-1;
        return pos;
    }

}
void genlrd(int root){
    lrd.push(root);
    int a = finddlr(root);
    int b = findldr(root);
    vis[b] = true;
    int ltlen = findlen(false,b);
    int rtlen = findlen(true,b);
    int ltroot = dlr[a+1];
    int rtroot = dlr[a+ltlen+1];
    if (rtlen) genlrd(rtroot);
    if (ltlen) genlrd(ltroot);
}

int main(int argc, char *argv[]){
    while (cin >> cnt) {
        memset(dlr, 0, sizeof(dlr));
        memset(ldr, 0, sizeof(ldr));
        memset(vis, 0, sizeof(vis));
        while (!lrd.empty()) lrd.pop();
        for (int i = 0; i < cnt; i++) cin >> dlr[i];
        for (int i = 0; i < cnt; i++) cin >> ldr[i];
        genlrd(dlr[0]);
        while (!lrd.empty()) {
            cout << lrd.top();
            if (lrd.size() != 1) cout << " ";
            lrd.pop();
        }
        cout << 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;

int dlr[1005],ldr[1005],cnt,vis[1005];

stack<int> lrd;

int finddlr(int target){

for (int i = 0; i < cnt; i++) if (dlr[i] == target) return i;

return 0;

}

int findldr(int target){

for (int i = 0; i < cnt; i++) if (ldr[i] == target) return i;

return -1;

}

int findlen(bool right,int pos){

//true for right false for left

if (right) {

for (int i = pos+1; i < cnt; i++) if (vis[i]) return i-pos-1;

return cnt-pos-1;

}else{

for (int i = pos-1; i >= 0;i--) if (vis[i]) return pos-i-1;

return pos;

}

void genlrd(int root){

lrd.push(root);

int a = finddlr(root);

int b = findldr(root);

vis[b] = true;

int ltlen = findlen(false,b);

int rtlen = findlen(true,b);

int ltroot = dlr[a+1];

int rtroot = dlr[a+ltlen+1];

if (rtlen) genlrd(rtroot);

if (ltlen) genlrd(ltroot);

}

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

while (cin >> cnt) {

memset(dlr, 0, sizeof(dlr));

memset(ldr, 0, sizeof(ldr));

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

while (!lrd.empty()) lrd.pop();

for (int i = 0; i < cnt; i++) cin >> dlr[i];

for (int i = 0; i < cnt; i++) cin >> ldr[i];

genlrd(dlr[0]);

while (!lrd.empty()) {

cout << lrd.top();

if (lrd.size() != 1) cout << " ";

lrd.pop();

}

cout << endl;

}

return 0;

}

这道题是已知DLR和LDR，求LRD。

DLR（先序）具有的特点是根节点一定在它连接的子树的左边，子树的根节点一定在子树的子树的左边，LDR的特点是投影，就是下面这个图：

接下来就拿样例举例子：

这个的DLR是1 2 4 7 3 5 8 9 6
这个可以分段看，首先是 1/247/35869，然后可以发现1是root，247又可以分成2/47/～三段（～表示没有节点），在这里2是这个子树的根，35896又可以分为3/589/6在这里3是右边子树的根，589是左半部分，6是右半部分，就这样一直分下去就可以发现DLR的特点了，而这种特点正是因为DLR是DFS生成的。

然后看LDR，4 7 2 1 8 5 9 3 6
这个也是分段，首先472/1/85936，你会发现如果知道根的话，那么这个根左边有什么右边有什么都是可以从LDR里看出来的。

所以我们这个题就可以先找到总根（DLR第一位），然后在LDR里找到根的位置，想办法确定左右肢的元素个数，然后回到DLR里找到左右肢的根，分别把它们当作总根递归下去，这样我们就能还原出树的全貌了，而这个题更简单一点，你只要以DRL的顺序这么递归，把每一次找到的根都压入stack里，最后再逐个弹出输出，正好就是LRD了。

如果已知LRD和LDR，是可以求出DLR的，方法和这个差不太多。但是如果知道DLR喝LRD，想求LDR做不到，LDR不止一个解。

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小练习

其实手写应该会很带感

Codeforces 501 B Misha and Changing Handles

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>

using namespace std;

int main(){
    map<string, string> id;

    int num = 0;
    cin >> num;
    while (num--) {
        string oldid,newid;
        cin >> oldid >> newid;
        bool flag = false;
        map<string,string>::iterator it;
        for (it = id.begin(); it != id.end(); it++) {
            if ((*it).second == oldid) {
                flag = true;
                (*it).second = newid;
                break;
            }
        }
        if (!flag) {
            id[oldid] = newid;
        }
    }
    cout << id.size() << endl;
    map<string,string>::iterator it;
    for (it = id.begin(); it != id.end(); it++) {
        cout << (*it).first << ' ' << (*it).second << 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 <map>

using namespace std;

int main(){

map<string, string> id;

int num = 0;

cin >> num;

while (num--) {

string oldid,newid;

cin >> oldid >> newid;

bool flag = false;

map<string,string>::iterator it;

for (it = id.begin(); it != id.end(); it++) {

if ((*it).second == oldid) {

flag = true;

(*it).second = newid;

break;

}

if (!flag) {

id[oldid] = newid;

}

cout << id.size() << endl;

map<string,string>::iterator it;

for (it = id.begin(); it != id.end(); it++) {

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

}

return 0;

}

STL小练习系列

POJ 1256 Anagram

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>

using namespace std;


char chain[52] = {'A','a','B','b','C','c','D','d','E','e','F','f','G','g','H','h','I','i','J','j','K','k','L','l','M','m','N','n','O','o','P','p','Q','q','R','r','S','s','T','t','U','u','V','v','W','w','X','x','Y','y','Z','z'};
bool cmp(char a,char b){
    if (a == b) {
        return false;
    }
    bool flag = false;
    for (int i = 0;i < 52;i++) {
        if (a == chain[i]) {
            flag = true;
            break;
        }
        if (b == chain[i]) {
            flag = false;
            break;
        }
    }
    return flag;
}

int main(){
    int cnt;
    cin >> cnt;
    while (cnt--) {
        string toProc;
        cin >> toProc;
        while (next_permutation(toProc.begin(), toProc.end(),cmp)) {

        }
        cout << toProc << endl;
        while (next_permutation(toProc.begin(), toProc.end(),cmp)) {
            cout << toProc << 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 <map>

using namespace std;

char chain[52] = {'A','a','B','b','C','c','D','d','E','e','F','f','G','g','H','h','I','i','J','j','K','k','L','l','M','m','N','n','O','o','P','p','Q','q','R','r','S','s','T','t','U','u','V','v','W','w','X','x','Y','y','Z','z'};

bool cmp(char a,char b){

if (a == b) {

return false;

}

bool flag = false;

for (int i = 0;i < 52;i++) {

if (a == chain[i]) {

flag = true;

break;

}

if (b == chain[i]) {

flag = false;

break;

}

return flag;

}

int main(){

int cnt;

cin >> cnt;

while (cnt--) {

string toProc;

cin >> toProc;

while (next_permutation(toProc.begin(), toProc.end(),cmp)) {

}

cout << toProc << endl;

while (next_permutation(toProc.begin(), toProc.end(),cmp)) {

cout << toProc << endl;

}

return 0;

}

next_permutation的返回bool值的含义是接下来还有没有可以用的排列。

然后要注意这个题的排序方式是特殊的，要自己构建排序函数。

排序函数返回值的意思是：如果返回true，则交换两个值，返回false，则不对两个值操作，所以如果a＝＝b一定要返回false，否则会死循环。

UVA 10420 List of Conquests

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>

using namespace std;

int main(){
    int cnt;
    cin >> cnt;
    map<string, set<string> > container;
    while (cnt--) {
        string country;
        cin >> country;
        string name;
        getchar();
        getline(cin, name);
        container[country].insert(name);
    }
    map<string, set<string> >::iterator it;
    for (it = container.begin(); it != container.end(); it++) {
        cout << (*it).first << ' ' << (*it).second.size() << 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 <map>

using namespace std;

int main(){

int cnt;

cin >> cnt;

map<string, set<string> > container;

while (cnt--) {

string country;

cin >> country;

string name;

getchar();

getline(cin, name);

container[country].insert(name);

}

map<string, set<string> >::iterator it;

for (it = container.begin(); it != container.end(); it++) {

cout << (*it).first << ' ' << (*it).second.size() << endl;

}

return 0;

}

STL的使用小练习