HDU – Page 3 – hahaschool

HDU 1114 Piggy-Bank

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 coinType{
    int w;
    int v;
    coinType(int iv,int iw){
        v = iv;
        w = iw;
    }
};

vector<coinType> coin;
int dp[10005];

int main(){
    int caseCnt;
    cin >> caseCnt;
    while (caseCnt--) {
        int e = 0,f = 0,n = 0;
        cin >> e >> f >> n;

        coin.clear();
        int iv = 0,iw = 0;
        for (int i = 0; i < n; i++) {
            cin >> iv >> iw;
            coin.push_back(coinType(iv,iw));
        }

        int w = f - e;
        memset(dp, 0x3f3f, sizeof(dp));
        dp[0] = 0;
        for (int i = 1; i <= w; i++) {
            for (int j = 0; j < n; j++) {
                if (i < coin[j].w) {
                    continue;
                }
                dp[i]  = min(dp[i-coin[j].w]+coin[j].v,dp[i]);
            }
        }

        if (dp[w] == 0x3f3f3f3f) {
            cout << "This is impossible." << endl;
        }else{
            cout << "The minimum amount of money in the piggy-bank is " << dp[w] << '.' << 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 coinType{

int w;

int v;

coinType(int iv,int iw){

v = iv;

w = iw;

}

};

vector<coinType> coin;

int dp[10005];

int main(){

int caseCnt;

cin >> caseCnt;

while (caseCnt--) {

int e = 0,f = 0,n = 0;

cin >> e >> f >> n;

coin.clear();

int iv = 0,iw = 0;

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

cin >> iv >> iw;

coin.push_back(coinType(iv,iw));

}

int w = f - e;

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

dp[0] = 0;

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

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

if (i < coin[j].w) {

continue;

}

dp[i] = min(dp[i-coin[j].w]+coin[j].v,dp[i]);

}

if (dp[w] == 0x3f3f3f3f) {

cout << "This is impossible." << endl;

}else{

cout << "The minimum amount of money in the piggy-bank is " << dp[w] << '.' << endl;

}

return 0;

}

这个基本上还是01背包嘛，但是这回我把状态的判定条件设置为在一定重量的情况下，尽量让硬币的总价值更少。

HDU 2191 悼念512汶川大地震遇难同胞――珍惜现在，感恩生活

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 coinType{
    int w;
    int v;
    coinType(int iv,int iw){
        v = iv;
        w = iw;
    }
};

vector<coinType> coin;
int dp[2][105];

int main(){
    int caseCnt;
    cin >> caseCnt;
    while (caseCnt--) {
        int m = 0,n = 0;
        cin >> m >> n;
        coin.clear();

        int maxm = 0;
        for (int i = 0; i < n; i++) {
            int iv = 0,iw = 0,num = 0;
            cin >> iw >> iv >> num;
            maxm += iw*num;
            int factor = 1;
            while (num) {
                if (num >= factor) {
                    num -= factor;
                    coin.push_back(coinType(iv*factor,iw*factor));
                    factor *= 2;
                }else{
                    coin.push_back(coinType(iv*num,iw*num));
                    num = 0;
                }
            }
        }
        memset(dp, 0, sizeof(dp));
        for(int i = 1;i <= coin.size();i++){
            for (int j = 0; j <= m; j++) {
                if(j-coin[i-1].w >= 0)
                dp[i%2][j] = max(dp[(i-1)%2][j-coin[i-1].w]+coin[i-1].v,dp[(i-1)%2][j]);
                else dp[i%2][j] = dp[(i-1)%2][j];
            }
        }
            cout << dp[coin.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 coinType{

int w;

int v;

coinType(int iv,int iw){

v = iv;

w = iw;

}

};

vector<coinType> coin;

int dp[2][105];

int main(){

int caseCnt;

cin >> caseCnt;

while (caseCnt--) {

int m = 0,n = 0;

cin >> m >> n;

coin.clear();

int maxm = 0;

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

int iv = 0,iw = 0,num = 0;

cin >> iw >> iv >> num;

maxm += iw*num;

int factor = 1;

while (num) {

if (num >= factor) {

num -= factor;

coin.push_back(coinType(iv*factor,iw*factor));

factor *= 2;

}else{

coin.push_back(coinType(iv*num,iw*num));

num = 0;

}

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

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

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

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

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

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

}

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

}

return 0;

}

这个是一个多重背包问题，其实多重背包就是01背包，举个例子（其实是扒的）：

¤像如果某件物品的重量为1，价值为2，数量为1000

¤我们就可以拆分成：

¤重量为1，价值为2的物品重量为2，价值为4的物品

¤重量为4，价值为8的物品 …

¤重量为256，价值为512的物品

¤重量为489，价值为489*2的物品

简要地说，就是先拿二进制拆，拆出来1，2，4，8，16，32。。。这样的，等到拆不动了（剩下的不够下一个2进制整幂了），就把剩下的单独拿出来当成一个新物品，这样就不会丢解了。拆分完之后不就变成01背包了嘛。

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背包问题。

就这样。

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。

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，最后输出结果，这个姿势就快多了。

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一样。

HDU 2553 N皇后问题

January 25, 20152015-01-25hahaschoolLeave a comment

//WARNING THIS CODE IS ONLY FOR MAKING TABLE

#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 120 //开小点，因为是打小表，打多少开多少

struct nodeType{
    bool board[MAXN+2][MAXN+2];
    int cnt;
    int xboundary;
    int yboundary;
    nodeType(){
        memset(board, true, sizeof(board));
        cnt = 0;
        xboundary = 0;
        yboundary = 0;
    }
    nodeType(decltype(board) a,int count,int yb,int xb){
        memcpy(board, a, sizeof(board));
        cnt = count;
        yboundary = yb;
        xboundary = xb;
    }

};
void place_queen(int y,int x,nodeType &now){
    for (int i = 1; i <= MAXN; i++) {
        now.board[i][x] = false;
        now.board[y][i] = false;
    }
    for (int i = 1; ; i++) {
        if (y + i > MAXN+1 || x + i > MAXN+1) {
            break;
        }
        now.board[y+i][x+i] = false;
    }for (int i = 1; ; i++) {
        if (y - i < 0 || x + i > MAXN+1) {
            break;
        }
        now.board[y-i][x+i] = false;
    }for (int i = 1; ; i++) {
        if (y + i > MAXN+1 || x - i < 0) {
            break;
        }
        now.board[y+i][x-i] = false;
    }for (int i = 1; ; i++) {
        if (y - i < 0 || x - i < 0) {
            break;
        }
        now.board[y-i][x-i] = false;
    }

}
long long res = 0;
void dfs(nodeType now,int n){
    if (now.cnt == n) {
        res++;
        return;
    }
    now.cnt++;
    for (int y = now.yboundary+1; y <= n; y++) {
        for (int x = 1; x <= n; x++) {
            if (!now.board[y][x]) {
                continue;
            }else{
                nodeType tmp(now.board,now.cnt,y,x);
                place_queen(y, x, tmp);
                dfs(tmp, n);
            }
        }
    }
}
int main(){
    int n = 0;
    while (cin >> n) {
        res = 0;
        nodeType init;
        dfs(init, n);
        cout << res << endl;
    }
}

//WARNING THIS CODE IS ONLY FOR MAKING TABLE

#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 120 //开小点，因为是打小表，打多少开多少

struct nodeType{

bool board[MAXN+2][MAXN+2];

int cnt;

int xboundary;

int yboundary;

nodeType(){

memset(board, true, sizeof(board));

cnt = 0;

xboundary = 0;

yboundary = 0;

}

nodeType(decltype(board) a,int count,int yb,int xb){

memcpy(board, a, sizeof(board));

cnt = count;

yboundary = yb;

xboundary = xb;

}

};

void place_queen(int y,int x,nodeType &now){

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

now.board[i][x] = false;

now.board[y][i] = false;

}

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

if (y + i > MAXN+1 || x + i > MAXN+1) {

break;

}

now.board[y+i][x+i] = false;

}for (int i = 1; ; i++) {

if (y - i < 0 || x + i > MAXN+1) {

break;

}

now.board[y-i][x+i] = false;

}for (int i = 1; ; i++) {

if (y + i > MAXN+1 || x - i < 0) {

break;

}

now.board[y+i][x-i] = false;

}for (int i = 1; ; i++) {

if (y - i < 0 || x - i < 0) {

break;

}

now.board[y-i][x-i] = false;

}

long long res = 0;

void dfs(nodeType now,int n){

if (now.cnt == n) {

res++;

return;

}

now.cnt++;

for (int y = now.yboundary+1; y <= n; y++) {

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

if (!now.board[y][x]) {

continue;

}else{

nodeType tmp(now.board,now.cnt,y,x);

place_queen(y, x, tmp);

dfs(tmp, n);

}

int main(){

int n = 0;

while (cin >> n) {

res = 0;

nodeType init;

dfs(init, n);

cout << res << endl;

}

C++作业不好好写的后果。。。

注意必须要用DFS来搜索，逐行搜。

#include <iostream>

using namespace std;

int res[11] = {0,1,0,0,2,10,4,40,92,352,724};

int main(){
int n;
while(cin >> n && n){
cout << res[n] << endl;
}

return 0;
}

#include <iostream>

using namespace std;

int res[11] = {0,1,0,0,2,10,4,40,92,352,724};

int main(){

int n;

while(cin >> n && n){

cout << res[n] << endl;

}

return 0;

}

HDU 1015 Safecracker

January 25, 20152015-01-25hahaschoolLeave 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 <list>
#include <stack>

using namespace std;

int main(){
    long long target;
    string toProc;
    while (cin >> target >> toProc) {
        if (target == 0 && toProc == "END") {
            break;
        }
        vector<bool> toru;
        for (int i = 1; i <= 5; i++) toru.push_back(true);
        for (int i = 1; i <= toProc.size()-5; i++) {
            toru.push_back(false);
        }
        sort(toru.begin(), toru.end());
        string res;
        do{
            string tmp;
            for (int i = 0; i < toProc.size();i++) {
                if (toru[i]) {
                    tmp += toProc[i];
                }
            }
            sort(tmp.begin(),tmp.end());
            do{
                long long judge = 0;
                judge += tmp[0]-'A'+1;
                judge += (tmp[1]-'A'+1)*(tmp[1]-'A'+1)*(-1);
                judge += (tmp[2]-'A'+1)*(tmp[2]-'A'+1)*(tmp[2]-'A'+1);
                judge += (tmp[3]-'A'+1)*(tmp[3]-'A'+1)*(tmp[3]-'A'+1)*(tmp[3]-'A'+1)*(-1);
                judge += (tmp[4]-'A'+1)*(tmp[4]-'A'+1)*(tmp[4]-'A'+1)*(tmp[4]-'A'+1)*(tmp[4]-'A'+1);
                if (judge == target) {
                    if (tmp > res) {
                        res = tmp;
                    }
                }

            }while (next_permutation(tmp.begin(), tmp.end())) ;
        }while (next_permutation(toru.begin(), toru.end()));
        if (!res.size()) {
            cout << "no solution" << endl;
            continue;
        }
        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 <map>

#include <list>

#include <stack>

using namespace std;

int main(){

long long target;

string toProc;

while (cin >> target >> toProc) {

if (target == 0 && toProc == "END") {

break;

}

vector<bool> toru;

for (int i = 1; i <= 5; i++) toru.push_back(true);

for (int i = 1; i <= toProc.size()-5; i++) {

toru.push_back(false);

}

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

string res;

do{

string tmp;

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

if (toru[i]) {

tmp += toProc[i];

}

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

do{

long long judge = 0;

judge += tmp[0]-'A'+1;

judge += (tmp[1]-'A'+1)*(tmp[1]-'A'+1)*(-1);

judge += (tmp[2]-'A'+1)*(tmp[2]-'A'+1)*(tmp[2]-'A'+1);

judge += (tmp[3]-'A'+1)*(tmp[3]-'A'+1)*(tmp[3]-'A'+1)*(tmp[3]-'A'+1)*(-1);

judge += (tmp[4]-'A'+1)*(tmp[4]-'A'+1)*(tmp[4]-'A'+1)*(tmp[4]-'A'+1)*(tmp[4]-'A'+1);

if (judge == target) {

if (tmp > res) {

res = tmp;

}

}while (next_permutation(tmp.begin(), tmp.end())) ;

}while (next_permutation(toru.begin(), toru.end()));

if (!res.size()) {

cout << "no solution" << endl;

continue;

}

cout << res << endl;

}

return 0;

}

用STL，next_permutation把所有可能性搞出来注意检验就可以爆过去了。

HDU 1166 敌兵布阵

January 21, 20152015-01-21hahaschool2 Comments

题意

求区间和，单点修改。

思路

典型的线段树问题，线段树的实现原理这里不再赘述。

代码

这份代码使用了zkw的非递归堆存储自底向上式线段树，实现难度较低。

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

#define MAXN 2097154

int tree[MAXN];
int M = 1;

void tree_init(int num){
    M = 1;
    for (; M <= num; M <<= 1);
    M <<= 1;
    memset(tree, 0, sizeof(int)*2*M+5);
    M--;
}

int tree_query(unsigned int from,unsigned int to){
    from--,to++;
    from += M,to += M;
    int res = 0;
    while (from^to^1) {
        //cout << "+" << from << "+" << to << '~' << endl;
        if (~from & 1) {//这里是按位取反，不是负号，也不能和0与那样的话肯定是0啊
            //from on left
            res += tree[from+1];
        }
        if (to & 1) {
            //to on right
            res += tree[to-1];
        }
        from >>= 1,to >>= 1;
    }
    return res;
}

void tree_update(unsigned int nodeNum,int delta){
    nodeNum += M;
    tree[nodeNum] += delta;
    while (nodeNum != 1) {
        nodeNum >>= 1;
        tree[nodeNum] = tree[nodeNum << 1] + tree[(nodeNum << 1) + 1];
    }
}

int main(){
    int casecnt;
    scanf(" %d",&casecnt);
    for (int k = 1; k <= casecnt; k++) {
        int n = 0;
        scanf(" %d",&n);
        tree_init(n);
        for (int i = 1; i <= n; i++) {
            int arg;
            scanf(" %d",&arg);
            tree_update(i+1, arg);
        }
        printf("Case %d:\n",k);
        while (true) {
            char cmd[6];
            memset(cmd, 0, sizeof(cmd));
            int arg1 = 0,arg2 = 0;
            scanf(" %s",cmd);
            if (cmd[0] == 'Q') {
                scanf(" %d %d",&arg1,&arg2);
                printf("%d\n",tree_query(arg1+1, arg2+1));
            }else if(cmd[0] == 'A') {
                scanf(" %d %d",&arg1,&arg2);
                tree_update(arg1+1, arg2);
            }else if(cmd[0] == 'S'){
                scanf(" %d %d",&arg1,&arg2);
                tree_update(arg1+1, arg2*-1);
            }else {
                break;
            }
        }
    }

    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;

#define MAXN 2097154

int tree[MAXN];

int M = 1;

void tree_init(int num){

M = 1;

for (; M <= num; M <<= 1);

M <<= 1;

memset(tree, 0, sizeof(int)*2*M+5);

M--;

}

int tree_query(unsigned int from,unsigned int to){

from--,to++;

from += M,to += M;

int res = 0;

while (from^to^1) {

//cout << "+" << from << "+" << to << '~' << endl;

if (~from & 1) {//这里是按位取反，不是负号，也不能和0与那样的话肯定是0啊

//from on left

res += tree[from+1];

}

if (to & 1) {

//to on right

res += tree[to-1];

}

from >>= 1,to >>= 1;

}

return res;

}

void tree_update(unsigned int nodeNum,int delta){

nodeNum += M;

tree[nodeNum] += delta;

while (nodeNum != 1) {

nodeNum >>= 1;

tree[nodeNum] = tree[nodeNum << 1] + tree[(nodeNum << 1) + 1];

}

int main(){

int casecnt;

scanf(" %d",&casecnt);

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

int n = 0;

scanf(" %d",&n);

tree_init(n);

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

int arg;

scanf(" %d",&arg);

tree_update(i+1, arg);

}

printf("Case %d:\n",k);

while (true) {

char cmd[6];

memset(cmd, 0, sizeof(cmd));

int arg1 = 0,arg2 = 0;

scanf(" %s",cmd);

if (cmd[0] == 'Q') {

scanf(" %d %d",&arg1,&arg2);

printf("%d\n",tree_query(arg1+1, arg2+1));

}else if(cmd[0] == 'A') {

scanf(" %d %d",&arg1,&arg2);

tree_update(arg1+1, arg2);

}else if(cmd[0] == 'S'){

scanf(" %d %d",&arg1,&arg2);

tree_update(arg1+1, arg2*-1);

}else {

break;

}

return 0;

}