January 2015 – Page 2

HDU 2546 饭卡

January 26, 20152015-01-26hahaschoolLeave a comment

#include <iostream>
#include <sstream>
#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 <list>
#include <stack>

using namespace std;

int price[1005];
int dp[2][1100];

int main(){
    int n;
    while (cin >> n && n) {
        memset(price, 0, sizeof(price));
        for (int i = 1; i <= n; i++) {
            cin >> price[i];
        }
        int m;
        cin >> m;
        if (m < 5) {
            cout << m << endl;
            continue;//hehe
        }
        sort(price+1, price+1+n);
        memset(dp, 0xf3f3, sizeof(dp));
        dp[0][0] = 0;
        int res = 0;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= m-5; j++) {
                if(j-price[i]>=0)
                dp[i%2][j] = max(dp[(i-1)%2][j-price[i]]+price[i],dp[(i-1)%2][j]);
                else dp[i%2][j] = dp[(i-1)%2][j];
                res = max(res,dp[i%2][j]);
            }
        }
        cout << m-(res+price[n])  << endl;
    }

    return 0;
}

#include <iostream>

#include <sstream>

#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 <list>

#include <stack>

using namespace std;

int price[1005];

int dp[2][1100];

int main(){

int n;

while (cin >> n && n) {

memset(price, 0, sizeof(price));

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

cin >> price[i];

}

int m;

cin >> m;

if (m < 5) {

cout << m << endl;

continue;//hehe

}

sort(price+1, price+1+n);

memset(dp, 0xf3f3, sizeof(dp));

dp[0][0] = 0;

int res = 0;

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

for (int j = 0; j <= m-5; j++) {

if(j-price[i]>=0)

dp[i%2][j] = max(dp[(i-1)%2][j-price[i]]+price[i],dp[(i-1)%2][j]);

else dp[i%2][j] = dp[(i-1)%2][j];

res = max(res,dp[i%2][j]);

}

cout << m-(res+price[n]) << endl;

}

return 0;

}

这道题给我玩惨了，原因就是“hehe”那里没有加，后果是啥大家都知道。。。

其实是一个包装过了的01背包问题，既然>=5块时都能随便花，那么我就把最贵的那个留下，然后尽量把饭卡刷到还剩5块钱的程度（不一定是五块，但尽量靠近五块），然后再去买那个最贵的，一次性刷爆。（虽然还是有可能刷不爆的，但余额尽量小是真的），“尽量把饭卡刷到还剩5块钱的程度”，这个就可以转化为重量限定m－5，每个物品重量与价值相等情况下的01背包问题。

就这样。

POJ 3624 Charm Bracelet 顺便讲一下01背包

January 26, 20152015-01-26hahaschoolLeave a comment

#include <iostream>
#include <sstream>
#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 <list>
#include <stack>

using namespace std;

struct nodeType{
    int w,d;
    nodeType(int iw,int id){
        w = iw;
        d = id;
    }
};

int dp[2][13000];

int main(){
    int n = 0, m = 0;
    while (cin >> n >> m) {
        vector<nodeType> node;
        for (int i = 1; i <= n; i++) {
            int iw = 0,id = 0;
            cin >> iw >> id;
            node.push_back(nodeType(iw,id));
        }
        memset(dp, 0, sizeof(dp));
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                if (j-node[i-1].w >= 0) {
                    dp[i%2][j] = max(dp[(i-1)%2][j-node[i-1].w]+node[i-1].d, dp[(i-1)%2][j]);
                }else{
                    dp[i%2][j] = dp[(i-1)%2][j];
                }
            }
        }
        cout << dp[node.size()%2][m] << endl;
    }

    return 0;
}

#include <iostream>

#include <sstream>

#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 <list>

#include <stack>

using namespace std;

struct nodeType{

int w,d;

nodeType(int iw,int id){

w = iw;

d = id;

}

};

int dp[2][13000];

int main(){

int n = 0, m = 0;

while (cin >> n >> m) {

vector<nodeType> node;

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

int iw = 0,id = 0;

cin >> iw >> id;

node.push_back(nodeType(iw,id));

}

memset(dp, 0, sizeof(dp));

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

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

if (j-node[i-1].w >= 0) {

dp[i%2][j] = max(dp[(i-1)%2][j-node[i-1].w]+node[i-1].d, dp[(i-1)%2][j]);

}else{

dp[i%2][j] = dp[(i-1)%2][j];

}

cout << dp[node.size()%2][m] << endl;

}

return 0;

}

裸的01背包问题，是DP的基础题型了，没有太多好说的。

简要说一下01背包问题的状态转移特点：按两个基准纪录数据，第一个基准是我们从0～a号物品中选，第二个基准是选择的物品已经有了多少重量b，这样组成了dp数组dp[a][b]，这个数组存储的是当前状态的价值是多少。接下来我们开始dp，对于每一个当前状态（最多选择到第n个物品，已经占用了w重量），我们是从两种先前状态中导出的：1.最多选择到n－1个物品（就是当前物品还没有考虑呢），占用重量w－x（x是第n个物品重量），在这个状态上，我们添加上第n个物品。2.最多选择到n－1个物品，占用重量w，在这个状态上，我们什么也不做，直接把他当成当前状态。

在这两种先前状态中选择最好的那个（有时候因为某些原因，只能选择一个，那就选唯一的那个就好），保存下来决定为当前状态，再供以后使用。

这样我们只要读取dp[i][j]的值，就是“选择1～i中的物品，重量限定为j，最高价值是？”这个问题的答案。（没有用滚动数组的话）

HDU 1874 畅通工程续

January 25, 20152015-01-25hahaschoolLeave a comment

#include <cmath>
#include <iostream>
#include <cstring>
#include <string>
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <vector>
#include <queue>
#define MAXN 0x3f3f3f3f
//Dijasktra
using namespace std;
int roadmap[205][205];
bool vis[205];
int sr[205];
int main(){
    int n = 0,m = 0;

    while (cin >> n >> m && m+n) {
        memset(roadmap, 0x3f3f, sizeof(roadmap));
        memset(sr, 0x3f3f, sizeof(sr));
        memset(vis, 0, sizeof(vis));
        for (int i = 0; i < n; i++) {
            roadmap[i][i] = 0;
        }
        for (int i = 1; i <= m; i++) {
            int a = 0,b = 0,c = 0;
            cin >> a >> b >> c;
            if (roadmap[a][b] > c){
            roadmap[a][b] = c;
            roadmap[b][a] = c;
            }
        }
        int s = 0,t = 0;
        cin >> s >> t;
        sr[s] = 0;
        while (true) {
            int i = -1;
            for (int q = 0; q < n; q++) {
                if (!vis[q]) {
                    if (i == -1 || sr[q] < sr[i]) {
                        i = q;
                    }
                }
            }
            if (i == -1) break;
            for (int q = 0; q < n; q++){
                sr[q] = min(sr[i]+roadmap[i][q],sr[q]);
            }
            vis[i] = true;
        }
        if (sr[t] == MAXN) {
            sr[t] = -1;
        }
        cout << sr[t] << endl;


    }
    return 0;
}

#include <cmath>

#include <iostream>

#include <cstring>

#include <string>

#include <stdio.h>

#include <string.h>

#include <ctype.h>

#include <vector>

#include <queue>

#define MAXN 0x3f3f3f3f

//Dijasktra

using namespace std;

int roadmap[205][205];

bool vis[205];

int sr[205];

int main(){

int n = 0,m = 0;

while (cin >> n >> m && m+n) {

memset(roadmap, 0x3f3f, sizeof(roadmap));

memset(sr, 0x3f3f, sizeof(sr));

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

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

roadmap[i][i] = 0;

}

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

int a = 0,b = 0,c = 0;

cin >> a >> b >> c;

if (roadmap[a][b] > c){

roadmap[a][b] = c;

roadmap[b][a] = c;

}

int s = 0,t = 0;

cin >> s >> t;

sr[s] = 0;

while (true) {

int i = -1;

for (int q = 0; q < n; q++) {

if (!vis[q]) {

if (i == -1 || sr[q] < sr[i]) {

i = q;

}

if (i == -1) break;

for (int q = 0; q < n; q++){

sr[q] = min(sr[i]+roadmap[i][q],sr[q]);

}

vis[i] = true;

}

if (sr[t] == MAXN) {

sr[t] = -1;

}

cout << sr[t] << endl;

}

return 0;

}

这是个裸的最短路问题，随便怎么搞都行。

这里用的是没有堆优化的dijkstra。

POJ 1062 昂贵的聘礼

January 25, 20152015-01-25hahaschoolLeave a comment

 #include <iostream>
 #include <sstream>
 #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 <list>
 #include <stack>

 using namespace std;

#define MAXN 0x3f3f3f3f

struct edgeType{
    int to;
    int cost;
    edgeType(int ito,int icost){
        to = ito;
        cost = icost;
    }
};

struct vertexType{
    vector<edgeType> edge;
    int cost;
    int level;
    vertexType(int icost,int ilevel){
        edge.clear();
        cost = icost;
        level = ilevel;
    }
};

int main(){
    int m = 0,n = 0;
    while (cin >> m >> n) {
        vector<vertexType> vertex;
        for (int i = 0; i < n; i++) {
            int vcost,vlevel,vsub;
            cin >> vcost >> vlevel >> vsub;
            vertexType now(vcost,vlevel);
            while (vsub--) {
                int to,cost;
                cin >> to >> cost;
                edgeType tmp(to-1,cost);
                now.edge.push_back(tmp);
            }
            vertex.push_back(now);
        }

        int maxlv = vertex[0].level,minlv = vertex[0].level;
        bool vis[105];
        int dis[105];
        memset(vis, 0, sizeof(vis));
        memset(dis, 0x3f3f, sizeof(dis));
        dis[0] = vertex[0].cost;
        while (true) {
            int cur = -1;
            int mindis = MAXN;
            for (int i = 0; i < vertex.size(); i++) {
                if (vis[i]) {
                    continue;
                }
                if (dis[i] < mindis) {
                    mindis = dis[i];
                    cur = i;
                }
            }
            if (cur == -1) break;

            vertexType nowvertex = vertex[cur];
            vis[cur] = true;
            maxlv = max(nowvertex.level,maxlv);
            minlv = min(nowvertex.level,minlv);
            //int nowlv = nowvertex.level;
            for (int i = 0; i < vertex[cur].edge.size(); i++) {
                edgeType nextedge = vertex[cur].edge[i];
                vertexType nextvertex = vertex[nextedge.to];
                if (max(abs(maxlv-nextvertex.level),abs(minlv-nextvertex.level)) > m) {
                    continue;
                }
                int newcost = dis[cur] - nowvertex.cost + nextedge.cost + nextvertex.cost;
                if (newcost < dis[nextedge.to]) {
                    dis[nextedge.to] = newcost;
                }
            }
        }
        int res = MAXN;
        for (int i = 0; i < n; i++) {
            res = min(dis[i], res);
        }
        cout << res << endl;
    }

    return 0;
}

100

101

102

103

104

#include <iostream>

#include <sstream>

#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 <list>

#include <stack>

using namespace std;

#define MAXN 0x3f3f3f3f

struct edgeType{

int to;

int cost;

edgeType(int ito,int icost){

to = ito;

cost = icost;

}

};

struct vertexType{

vector<edgeType> edge;

int cost;

int level;

vertexType(int icost,int ilevel){

edge.clear();

cost = icost;

level = ilevel;

}

};

int main(){

int m = 0,n = 0;

while (cin >> m >> n) {

vector<vertexType> vertex;

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

int vcost,vlevel,vsub;

cin >> vcost >> vlevel >> vsub;

vertexType now(vcost,vlevel);

while (vsub--) {

int to,cost;

cin >> to >> cost;

edgeType tmp(to-1,cost);

now.edge.push_back(tmp);

}

vertex.push_back(now);

}

int maxlv = vertex[0].level,minlv = vertex[0].level;

bool vis[105];

int dis[105];

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

memset(dis, 0x3f3f, sizeof(dis));

dis[0] = vertex[0].cost;

while (true) {

int cur = -1;

int mindis = MAXN;

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

if (vis[i]) {

continue;

}

if (dis[i] < mindis) {

mindis = dis[i];

cur = i;

}

if (cur == -1) break;

vertexType nowvertex = vertex[cur];

vis[cur] = true;

maxlv = max(nowvertex.level,maxlv);

minlv = min(nowvertex.level,minlv);

//int nowlv = nowvertex.level;

for (int i = 0; i < vertex[cur].edge.size(); i++) {

edgeType nextedge = vertex[cur].edge[i];

vertexType nextvertex = vertex[nextedge.to];

if (max(abs(maxlv-nextvertex.level),abs(minlv-nextvertex.level)) > m) {

continue;

}

int newcost = dis[cur] - nowvertex.cost + nextedge.cost + nextvertex.cost;

if (newcost < dis[nextedge.to]) {

dis[nextedge.to] = newcost;

}

int res = MAXN;

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

res = min(dis[i], res);

}

cout << res << endl;

}

return 0;

}

这个题是一个比较基准有些多的最短路（和之前那个Dirt挺像）。

（这里的cost就是dijkstra算法里面的dis值）每一次更新下一节点时，下一节点的cost值为（当前cost值－当前点权＋下一边边权＋下一点点权）；每一次到达节点后，都根据当前抽出的节点的地位值，更新当前走过节点的地位的最大最小值，等接下来更新临接节点时，如果下一节点的地位与当前最大最小值中任意一个只差绝对值>m就要抛弃。以这两个为基准，进行正常的dijkstra，然后从头到尾的扫一遍cost数组，把最小值输出来就是答案。

POJ 1135 Domino Effect

January 25, 20152015-01-25hahaschoolLeave a comment

#include <iostream>
#include <sstream>
#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 <list>
#include <stack>

using namespace std;

#define MAXN 0x3f3f3f3f

struct edgeType{
    int to;
    int cost;
    edgeType(int ito,int icost){
        to = ito;
        cost = icost;
    }
};

struct vertexType{
    vector<edgeType> edge;
    int dis;
    vertexType(){
        edge.clear();
        dis = MAXN;
    }
};
vector<vertexType> vertex;

struct cmp{
    bool operator () (int a,int b){
        return vertex[a].dis > vertex[b].dis;
    }
};

int main(){
    int n = 0,m = 0;
    int casecnt = 0;
    while (cin >> n >> m) {
        if (m == 0 && n == 0) {
            break;
        }
        casecnt++;
        vertex.clear();
        for (int i = 0; i <= n; i++) {
            vertex.push_back(vertexType());
        }
        for (int i = 0; i < m; i++) {
            int a = 0,b = 0,c = 0;
            cin >> a >> b >> c;
            vertex[a].edge.push_back(edgeType(b,c));
            vertex[b].edge.push_back(edgeType(a,c));
        }
        bool vis[502];
        memset(vis, 0, sizeof(vis));
        vertex[1].dis = 0;
        priority_queue<int,vector<int>,cmp> q;
        q.push(1);
        while (!q.empty()) {
            int cur = q.top();
            q.pop();
            vis[cur] = true;
            for (int i = 0; i < vertex[cur].edge.size(); i++) {
                edgeType nextedge = vertex[cur].edge[i];
                if (vis[nextedge.to]) {
                    continue;
                }
                if (vertex[nextedge.to].dis > vertex[cur].dis + nextedge.cost) {
                    vertex[nextedge.to].dis = vertex[cur].dis + nextedge.cost;
                    q.push(nextedge.to);
                }
            }
        }
        double res = 0;
        int pt1 = 1,pt2 = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < vertex[i].edge.size(); j++) {
                double terpos = ((double)vertex[i].dis + (double)vertex[vertex[i].edge[j].to].dis + (double)vertex[i].edge[j].cost)/2;
                double judge = max(terpos,max((double)vertex[i].dis,(double)vertex[vertex[i].edge[j].to].dis));
                if (judge > res) {
                    if (judge != vertex[i].dis && judge != vertex[vertex[i].edge[j].to].dis) {
                        res = judge;
                        pt1 = min(i,vertex[i].edge[j].to);
                        pt2 = max(i,vertex[i].edge[j].to);
                    }else if(judge == (double)vertex[i].dis){
                        res = vertex[i].dis;
                        pt1 = i,pt2 = i;
                    }else{
                        res = vertex[vertex[i].edge[j].to].dis;
                        pt1 = vertex[i].edge[j].to,pt2 = vertex[i].edge[j].to;
                    }
                }
            }
        }
        cout << "System #" << casecnt << endl;
        cout.setf(ios::fixed);
        cout << "The last domino falls after " << setprecision(1) << res << " seconds, ";
        cout.unsetf(ios::fixed);
        if (pt1 != pt2) {
            cout << "between key dominoes " << pt1 << " and " << pt2 << '.' << endl;
        }else{
            cout << "at key domino " << pt1 << '.' << endl;
        }
        cout << endl;
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

#include <iostream>

#include <sstream>

#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 <list>

#include <stack>

using namespace std;

#define MAXN 0x3f3f3f3f

struct edgeType{

int to;

int cost;

edgeType(int ito,int icost){

to = ito;

cost = icost;

}

};

struct vertexType{

vector<edgeType> edge;

int dis;

vertexType(){

edge.clear();

dis = MAXN;

}

};

vector<vertexType> vertex;

struct cmp{

bool operator () (int a,int b){

return vertex[a].dis > vertex[b].dis;

}

};

int main(){

int n = 0,m = 0;

int casecnt = 0;

while (cin >> n >> m) {

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

break;

}

casecnt++;

vertex.clear();

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

vertex.push_back(vertexType());

}

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

int a = 0,b = 0,c = 0;

cin >> a >> b >> c;

vertex[a].edge.push_back(edgeType(b,c));

vertex[b].edge.push_back(edgeType(a,c));

}

bool vis[502];

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

vertex[1].dis = 0;

priority_queue<int,vector<int>,cmp> q;

q.push(1);

while (!q.empty()) {

int cur = q.top();

q.pop();

vis[cur] = true;

for (int i = 0; i < vertex[cur].edge.size(); i++) {

edgeType nextedge = vertex[cur].edge[i];

if (vis[nextedge.to]) {

continue;

}

if (vertex[nextedge.to].dis > vertex[cur].dis + nextedge.cost) {

vertex[nextedge.to].dis = vertex[cur].dis + nextedge.cost;

q.push(nextedge.to);

}

double res = 0;

int pt1 = 1,pt2 = 1;

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

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

double terpos = ((double)vertex[i].dis + (double)vertex[vertex[i].edge[j].to].dis + (double)vertex[i].edge[j].cost)/2;

double judge = max(terpos,max((double)vertex[i].dis,(double)vertex[vertex[i].edge[j].to].dis));

if (judge > res) {

if (judge != vertex[i].dis && judge != vertex[vertex[i].edge[j].to].dis) {

res = judge;

pt1 = min(i,vertex[i].edge[j].to);

pt2 = max(i,vertex[i].edge[j].to);

}else if(judge == (double)vertex[i].dis){

res = vertex[i].dis;

pt1 = i,pt2 = i;

}else{

res = vertex[vertex[i].edge[j].to].dis;

pt1 = vertex[i].edge[j].to,pt2 = vertex[i].edge[j].to;

}

cout << "System #" << casecnt << endl;

cout.setf(ios::fixed);

cout << "The last domino falls after " << setprecision(1) << res << " seconds, ";

cout.unsetf(ios::fixed);

if (pt1 != pt2) {

cout << "between key dominoes " << pt1 << " and " << pt2 << '.' << endl;

}else{

cout << "at key domino " << pt1 << '.' << endl;

}

cout << endl;

}

return 0;

}

题我就没读懂。。。

其实是这样，把每一个key domino当做节点，他们之间的骨牌数目当作边权，用dijkstra处理一下得到的就是骨牌倒道该节点的最短时间，接下来我们要考虑在中间倒完的情况。

如果在两个节点中间倒完的话，也就意味着从起点经过两个key domino到终点，左右两边走过的时间是一样的，所以我们可以用(dis[a]+dis[b]+edge.cost)/2这个就可以求出在两点之间倒完需要多少时间，我们把每条边都这样过一遍，如果求出来的这个值比左右两边节点的dis都大，说明倒在中间，如果正好等于某一个节点的dis值，就把那个节点当作终点，把所有的边都这样过完之后，找到最大的(dis[a]+dis[b]+edge.cost)/2对应的终止情形，就是答案。

如何给priority_queue写比较函数

January 25, 20152015-01-25hahaschoolLeave a comment

struct cmp{
    bool operator () (int a,int b){
        return vertex[a].dis > vertex[b].dis;
    }
};


priority_queue<int,vector<int>,cmp> q;

struct cmp{

bool operator () (int a,int b){

return vertex[a].dis > vertex[b].dis;

}

};

priority_queue<int,vector<int>,cmp> q;

下面是转的：

注：

less<class T>这是大顶堆，按值大的优先，值大的在最上面。greater<class T>这是小顶堆，按值小的优先，值小的在最上面。

自定义cmp如果还有不明白的看这里：

struct cmp
{
    bool operator()（const int &a,const int &b）//这里的&是引用
    {
        return a>b;//最大堆
        return a<b;//最小堆
    }
};
priority_queue< int, vector<int>, cmp >

struct cmp

{

bool operator()（const int &a,const int &b）//这里的&是引用

{

return a>b;//最大堆

return a<b;//最小堆

}

};

priority_queue< int, vector<int>, cmp >

还是自定义cmp函数，注意，一般ACM中用结构体内含“bool operator()（const int &a,const int &b）”。这其实等价于Class cmp，不过更省事，当然也不规范（不需要规范）。
return就是希望如何排列为true。如果希望由大到小，就将大到小的情况return；反则亦然。和sort的自定义cmp是一样的。

HDU 3023 Dirt

January 25, 20152015-01-25hahaschoolLeave a comment

#include <iostream>
#include <sstream>
#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 <list>
#include <stack>

using namespace std;

#define MAXDEP 10000000

int dir[8][2] = {{1,1},{1,-1},{-1,1},{-1,-1},{1,0},{0,1},{-1,0},{0,-1}};
char board[1005][1005];
bool vis[1005][1005];
int m = 0,n = 0,cx = 0,cy = 0,rx = 0,ry = 0;

struct factorType{
    int shoe;
    int step;
    void fillmax(){
        shoe = MAXDEP,step = MAXDEP;
    }
} factor[1001][1001];
struct nodeType{
    int x;
    int y;
    bool operator < (nodeType b) const{
        if(factor[y][x].shoe == factor[b.y][b.x].shoe){
            return factor[y][x].step > factor[b.y][b.x].step;
        }
        return factor[y][x].shoe > factor[b.y][b.x].shoe;
    }
};


bool dijkstra(){
    nodeType init;
    priority_queue<nodeType> q;
    init.y = cy,init.x = cx;
    factor[cy][cx].shoe = 0;
    factor[cy][cx].step = 0;
    q.push(init);
    while (!q.empty()) {
        nodeType now;
        now = q.top();
        q.pop();
        if (now.y == ry && now.x == rx) return true;
        if(vis[now.y][now.x])continue;
        vis[now.y][now.x] = true;
        for (int i = 0; i < 8; i++) {
            nodeType tmp;
            tmp.y = now.y + dir[i][0];
            tmp.x = now.x + dir[i][1];
            if (tmp.x < 1 ||
                tmp.y < 1 ||
                tmp.x > n ||
                tmp.y > m ||
                vis[tmp.y][tmp.x]||
                board[tmp.y][tmp.x] == 0) {
                    continue;
                }
            if (factor[tmp.y][tmp.x].shoe > factor[now.y][now.x].shoe + (board[now.y][now.x] != board[tmp.y][tmp.x])) {
                factor[tmp.y][tmp.x].shoe = factor[now.y][now.x].shoe + (board[now.y][now.x] != board[tmp.y][tmp.x]);
                factor[tmp.y][tmp.x].step = factor[now.y][now.x].step+1;
                q.push(tmp);
            }else if(factor[tmp.y][tmp.x].shoe == factor[now.y][now.x].shoe + (board[now.y][now.x] != board[tmp.y][tmp.x])
                     && (factor[tmp.y][tmp.x].step > factor[now.y][now.x].step+1)){
                factor[tmp.y][tmp.x].step = factor[now.y][now.x].step+1;
                q.push(tmp);
            }

        }
    }
    return false;
}

int main(){
    while (cin >> m >> n >> cy >> cx >> ry >> rx) {
        for (int i = 1; i <= m; i++) {//y dir
            getchar();
            for (int j = 1; j <= n; j++) {//x dir
                factor[i][j].fillmax();
                board[i][j] = getchar() - '0';
                vis[i][j] = false;
            }
        }

        if (dijkstra()) {
            cout << factor[ry][rx].step+1 << ' ' << factor[ry][rx].shoe << endl;
        }else{
            cout << 0 << ' ' << 0 << endl;
        }

    }
    return 0;
}

100

101

102

103

104

105

106

#include <iostream>

#include <sstream>

#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 <list>

#include <stack>

using namespace std;

#define MAXDEP 10000000

int dir[8][2] = {{1,1},{1,-1},{-1,1},{-1,-1},{1,0},{0,1},{-1,0},{0,-1}};

char board[1005][1005];

bool vis[1005][1005];

int m = 0,n = 0,cx = 0,cy = 0,rx = 0,ry = 0;

struct factorType{

int shoe;

int step;

void fillmax(){

shoe = MAXDEP,step = MAXDEP;

}

} factor[1001][1001];

struct nodeType{

int x;

int y;

bool operator < (nodeType b) const{

if(factor[y][x].shoe == factor[b.y][b.x].shoe){

return factor[y][x].step > factor[b.y][b.x].step;

}

return factor[y][x].shoe > factor[b.y][b.x].shoe;

}

};

bool dijkstra(){

nodeType init;

priority_queue<nodeType> q;

init.y = cy,init.x = cx;

factor[cy][cx].shoe = 0;

factor[cy][cx].step = 0;

q.push(init);

while (!q.empty()) {

nodeType now;

now = q.top();

q.pop();

if (now.y == ry && now.x == rx) return true;

if(vis[now.y][now.x])continue;

vis[now.y][now.x] = true;

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

nodeType tmp;

tmp.y = now.y + dir[i][0];

tmp.x = now.x + dir[i][1];

if (tmp.x < 1 ||

tmp.y < 1 ||

tmp.x > n ||

tmp.y > m ||

vis[tmp.y][tmp.x]||

board[tmp.y][tmp.x] == 0) {

continue;

}

if (factor[tmp.y][tmp.x].shoe > factor[now.y][now.x].shoe + (board[now.y][now.x] != board[tmp.y][tmp.x])) {

factor[tmp.y][tmp.x].shoe = factor[now.y][now.x].shoe + (board[now.y][now.x] != board[tmp.y][tmp.x]);

factor[tmp.y][tmp.x].step = factor[now.y][now.x].step+1;

q.push(tmp);

}else if(factor[tmp.y][tmp.x].shoe == factor[now.y][now.x].shoe + (board[now.y][now.x] != board[tmp.y][tmp.x])

&& (factor[tmp.y][tmp.x].step > factor[now.y][now.x].step+1)){

factor[tmp.y][tmp.x].step = factor[now.y][now.x].step+1;

q.push(tmp);

}

return false;

}

int main(){

while (cin >> m >> n >> cy >> cx >> ry >> rx) {

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

getchar();

for (int j = 1; j <= n; j++) {//x dir

factor[i][j].fillmax();

board[i][j] = getchar() - '0';

vis[i][j] = false;

}

if (dijkstra()) {

cout << factor[ry][rx].step+1 << ' ' << factor[ry][rx].shoe << endl;

}else{

cout << 0 << ' ' << 0 << endl;

}

return 0;

}

经过了极其艰辛（～3天）的过程终于把这个题肝出来了。

基本题型是最短路，采用dijkstra，利用优先队列做堆优化，之所以老不过是因为松弛写错了，当时错误地认为下一节点一定会换鞋，实际上应该判断一下是不是要换鞋，换鞋和不换鞋的松弛操作要分开进行。

HDU 1557 权利指数

January 25, 20152015-01-25hahaschoolLeave a comment

#include <iostream>
#include <sstream>
#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 <list>
#include <stack>

using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    int casecnt;
    cin >> casecnt;
    while (casecnt--) {
        int n;
        cin >> n;
        vector<int> vote;
        int sumvote = 0;
        for (int i = 1; i <= n; i++) {
            int tmp;
            cin >> tmp;
            sumvote += tmp;
            vote.push_back(tmp);
        }
        //make maxn
        unsigned int maxn = 1;
        for (int i = 1; i < n; i++) {
            maxn <<= 1;
            maxn++;
        }

        int res[22];
        memset(res, 0, sizeof(res));
        for (int k = 1;k <= maxn; k++) {
            int curvote = 0,ck = k;
            for (int l = 0; l < n; l++) {
                if (ck&1) {
                    curvote+=vote[l];
                }
                ck >>= 1;
            }
            if (curvote > sumvote/2) {
                //effective team desu!
                for (int i = 1; i <= n; i++) {
                    //make mask
                    unsigned int mask = 1;
                    mask <<= i-1; //done
                    if (k&mask) {
                        //in the team
                        if (curvote - vote[i-1] <= sumvote/2) {
                            res[i]++;
                        }
                    }

                }
            }

        }

        /*
        vector<int> res;
        //Calculation Proccess
        for (int i = 1; i <= n; i++) {
            //make mask
            unsigned int mask = 1;
            mask <<= i-1; //done
            int cnt = 0;
            for (int k = 1;k <= maxn; k++) {
                if(!(k&mask)) continue;
                unsigned int build = k & ~mask; //block i
                unsigned curvote = 0;
                for (int l = 0; l < n; l++) {
                    if (build&1) {
                        curvote+=vote[l];
                    }
                    build >>= 1;
                }
                if (curvote <= sumvote/2 && curvote+vote[i-1] > sumvote/2) {
                    cnt++;
                }
            }
            res.push_back(cnt);
        }*/

        for (int i = 1; i <= n; i++) {
            cout << res[i];
            if (i != n) {
                cout << ' ';
            }
        }cout << 'n';

    }


}

100

101

102

103

104

105

#include <iostream>

#include <sstream>

#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 <list>

#include <stack>

using namespace std;

int main(){

ios_base::sync_with_stdio(false);

int casecnt;

cin >> casecnt;

while (casecnt--) {

int n;

cin >> n;

vector<int> vote;

int sumvote = 0;

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

int tmp;

cin >> tmp;

sumvote += tmp;

vote.push_back(tmp);

}

//make maxn

unsigned int maxn = 1;

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

maxn <<= 1;

maxn++;

}

int res[22];

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

for (int k = 1;k <= maxn; k++) {

int curvote = 0,ck = k;

for (int l = 0; l < n; l++) {

if (ck&1) {

curvote+=vote[l];

}

ck >>= 1;

}

if (curvote > sumvote/2) {

//effective team desu!

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

//make mask

unsigned int mask = 1;

mask <<= i-1; //done

if (k&mask) {

//in the team

if (curvote - vote[i-1] <= sumvote/2) {

res[i]++;

}

vector<int> res;

//Calculation Proccess

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

//make mask

unsigned int mask = 1;

mask <<= i-1; //done

int cnt = 0;

for (int k = 1;k <= maxn; k++) {

if(!(k&mask)) continue;

unsigned int build = k & ~mask; //block i

unsigned curvote = 0;

for (int l = 0; l < n; l++) {

if (build&1) {

curvote+=vote[l];

}

build >>= 1;

}

if (curvote <= sumvote/2 && curvote+vote[i-1] > sumvote/2) {

cnt++;

}

res.push_back(cnt);

}*/

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

cout << res[i];

if (i != n) {

cout << ' ';

}

}cout << 'n';

}

这个题二进制枚举，但是姿势要正确，如果是先枚举每个人，然后根据这个人找到所有符合要求的情况，一个人一个人地出解，这样就太慢了。

好的姿势是直接枚举所有情况，对于每种情况，分别枚举把其中的一个人干掉之后是不是会小于总票数一半，符合要求的话就给那个人的计数器＋1，最后输出结果，这个姿势就快多了。

CodeForces 244B Undoubtedly Lucky Numbers

January 25, 20152015-01-25hahaschoolLeave a comment

#include <iostream>
#include <sstream>
#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 <list>
#include <stack>

using namespace std;

#define MAXN 1000000000

vector<long long> super;

void gen(long long num,long long seed1,long long seed2,bool sp){
    if (num > MAXN) {
        return;
    }
    if (sp) {
        gen(seed1*10+seed1, seed1, 0, false);
        gen(seed1*10, seed1, 0, false);
    }else{
        //cout << num << endl;
        super.push_back(num);
        gen(num*10+seed1,seed1,seed2,false);
        gen(num*10+seed2,seed1,seed2,false);
    }
}

int main(){
    for (int i = 1; i <= 9; i++) {
        for (int j = i+1;j <= 9; j++) {
            gen(0, i, j, false);
        }
    }
    for (int i = 1; i <= 9; i++) {
        gen(0, i, 0,true);
    }

    sort(super.begin(), super.end());
    super.erase(unique(super.begin(), super.end()),super.end());
    //cout << super.size() << endl;
    long long n = 0;
    while (cin >> n) {
        int res = 0;
        for (int i = 1; i < super.size(); i++) {
            if (super[i] <= n) {
                res++;
            }
        }
        cout << res << endl;
    }
}

#include <iostream>

#include <sstream>

#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 <list>

#include <stack>

using namespace std;

#define MAXN 1000000000

vector<long long> super;

void gen(long long num,long long seed1,long long seed2,bool sp){

if (num > MAXN) {

return;

}

if (sp) {

gen(seed1*10+seed1, seed1, 0, false);

gen(seed1*10, seed1, 0, false);

}else{

//cout << num << endl;

super.push_back(num);

gen(num*10+seed1,seed1,seed2,false);

gen(num*10+seed2,seed1,seed2,false);

}

int main(){

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

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

gen(0, i, j, false);

}

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

gen(0, i, 0,true);

}

sort(super.begin(), super.end());

super.erase(unique(super.begin(), super.end()),super.end());

//cout << super.size() << endl;

long long n = 0;

while (cin >> n) {

int res = 0;

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

if (super[i] <= n) {

res++;

}

cout << res << endl;

}

把那些lucky numbers预先生成出来打进一个表里（预处理），接收到输入的时候然后只要查表就可以了。

HDU 5012 Dice

January 25, 20152015-01-25hahaschoolLeave a comment

#include <iostream>
#include <sstream>
#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 <list>
#include <stack>

using namespace std;

struct diceType{
    int dice[6];
    int cnt;
    diceType(int *a,int count){
        memcpy(dice, a, sizeof(dice));
        cnt = count;

    }
};

void roll_left(int *dice){
    int a = dice[0];
    int b = dice[1];
    int c = dice[2];
    int d = dice[3];
    int e = dice[4];
    int f = dice[5];

    dice[0] = d;
    dice[1] = c;
    dice[2] = a;
    dice[3] = b;
    dice[4] = e;
    dice[5] = f;
}

void roll_right(int *dice){
    int a = dice[0];
    int b = dice[1];
    int c = dice[2];
    int d = dice[3];
    int e = dice[4];
    int f = dice[5];

    dice[0] = c;
    dice[1] = d;
    dice[2] = b;
    dice[3] = a;
    dice[4] = e;
    dice[5] = f;
}

void roll_front(int *dice){
    int a = dice[0];
    int b = dice[1];
    int c = dice[2];
    int d = dice[3];
    int e = dice[4];
    int f = dice[5];

    dice[0] = f;
    dice[1] = e;
    dice[2] = c;
    dice[3] = d;
    dice[4] = a;
    dice[5] = b;
}

void roll_back(int *dice){
    int a = dice[0];
    int b = dice[1];
    int c = dice[2];
    int d = dice[3];
    int e = dice[4];
    int f = dice[5];

    dice[0] = e;
    dice[1] = f;
    dice[2] = c;
    dice[3] = d;
    dice[4] = b;
    dice[5] = a;
}

bool compare_dice(int *a,int *b){
    for (int i = 0; i < 6; i++) {
        if (a[i] != b[i]) {
            return false;
        }
    }
    return true;
}

int main(){
    int orig[6],goal[6];
    while (cin >> orig[0]) {
        for (int i = 1; i < 6; i++) {
            cin >> orig[i];
        }
        for (int i = 0; i < 6; i++) {
            cin >> goal[i];
        }

    diceType init(orig,0);
    queue<diceType> q;
    q.push(init);
    int res = -1;
    while (!q.empty()) {
        diceType now = q.front();
        q.pop();
        if (now.cnt >= 5) {
            continue;
        }
        if (compare_dice(goal, now.dice)) {
            res = now.cnt;
            break;
        }
        now.cnt++;
        roll_left(now.dice);
        q.push(now);
         roll_right(now.dice);

        roll_right(now.dice);
        q.push(now);
        roll_left(now.dice);

        roll_front(now.dice);
        q.push(now);
        roll_back(now.dice);

        roll_back(now.dice);
        q.push(now);
        roll_front(now.dice);
    }
    cout << res << endl;

    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

#include <iostream>

#include <sstream>

#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 <list>

#include <stack>

using namespace std;

struct diceType{

int dice[6];

int cnt;

diceType(int *a,int count){

memcpy(dice, a, sizeof(dice));

cnt = count;

}

};

void roll_left(int *dice){

int a = dice[0];

int b = dice[1];

int c = dice[2];

int d = dice[3];

int e = dice[4];

int f = dice[5];

dice[0] = d;

dice[1] = c;

dice[2] = a;

dice[3] = b;

dice[4] = e;

dice[5] = f;

}

void roll_right(int *dice){

int a = dice[0];

int b = dice[1];

int c = dice[2];

int d = dice[3];

int e = dice[4];

int f = dice[5];

dice[0] = c;

dice[1] = d;

dice[2] = b;

dice[3] = a;

dice[4] = e;

dice[5] = f;

}

void roll_front(int *dice){

int a = dice[0];

int b = dice[1];

int c = dice[2];

int d = dice[3];

int e = dice[4];

int f = dice[5];

dice[0] = f;

dice[1] = e;

dice[2] = c;

dice[3] = d;

dice[4] = a;

dice[5] = b;

}

void roll_back(int *dice){

int a = dice[0];

int b = dice[1];

int c = dice[2];

int d = dice[3];

int e = dice[4];

int f = dice[5];

dice[0] = e;

dice[1] = f;

dice[2] = c;

dice[3] = d;

dice[4] = b;

dice[5] = a;

}

bool compare_dice(int *a,int *b){

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

if (a[i] != b[i]) {

return false;

}

return true;

}

int main(){

int orig[6],goal[6];

while (cin >> orig[0]) {

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

cin >> orig[i];

}

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

cin >> goal[i];

}

diceType init(orig,0);

queue<diceType> q;

q.push(init);

int res = -1;

while (!q.empty()) {

diceType now = q.front();

q.pop();

if (now.cnt >= 5) {

continue;

}

if (compare_dice(goal, now.dice)) {

res = now.cnt;

break;

}

now.cnt++;

roll_left(now.dice);

q.push(now);

roll_right(now.dice);

q.push(now);

roll_left(now.dice);

roll_front(now.dice);

q.push(now);

roll_back(now.dice);

q.push(now);

roll_front(now.dice);

}

cout << res << endl;

}

return 0;

}

不科学的剪枝，当深度到5就放弃当前节点，然后居然过了，可见数据水了。

科学的做法是把骰子的6个面的状态连一起当成整数，开个标记数组，就跟hash一样。