算法 – Page 2 – hahaschool

HDU 4920 Matrix Multiplication

February 23, 20152015-02-23hahaschoolLeave a comment

#include <string.h>
#include <stdio.h>

int MATSIZE = 801;
int mata[810][810];
int matb[810][810];
int matc[810][810];
int main(){
    while (scanf("%d",&MATSIZE) != EOF) {
        int i,j,k;
        for (i = 0;i < MATSIZE; i++) {
            for (j = 0; j < MATSIZE; j++) {
                scanf("%d",&mata[i][j]);
                mata[i][j] %= 3;
            }
        }
        for (i = 0;i < MATSIZE; i++) {
            for (j = 0; j < MATSIZE; j++) {
                scanf("%d",&matb[i][j]);
                matb[i][j] %= 3;
            }
        }
        memset(matc, 0, sizeof(matc));
        for(i = 0;i < MATSIZE;i++){
            for(j = 0;j < MATSIZE;j++){
                if (matb[i][j] == 0) {
                    continue;
                }
                for(k = 0;k < MATSIZE;k++){
                    matc[k][j] += mata[k][i] * matb[i][j];
                }
            }
        }
        for (i = 0;i < MATSIZE; i++) {
            for (j = 0; j < MATSIZE-1; j++) {
                printf("%d ",(matc[i][j]+3)%3);
            }
            printf("%dn",(matc[i][MATSIZE-1]+3)%3);
        }
    }
    return 0;
}

#include <string.h>

#include <stdio.h>

int MATSIZE = 801;

int mata[810][810];

int matb[810][810];

int matc[810][810];

int main(){

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

int i,j,k;

for (i = 0;i < MATSIZE; i++) {

for (j = 0; j < MATSIZE; j++) {

scanf("%d",&mata[i][j]);

mata[i][j] %= 3;

}

for (i = 0;i < MATSIZE; i++) {

for (j = 0; j < MATSIZE; j++) {

scanf("%d",&matb[i][j]);

matb[i][j] %= 3;

}

memset(matc, 0, sizeof(matc));

for(i = 0;i < MATSIZE;i++){

for(j = 0;j < MATSIZE;j++){

if (matb[i][j] == 0) {

continue;

}

for(k = 0;k < MATSIZE;k++){

matc[k][j] += mata[k][i] * matb[i][j];

}

for (i = 0;i < MATSIZE; i++) {

for (j = 0; j < MATSIZE-1; j++) {

printf("%d ",(matc[i][j]+3)%3);

}

printf("%dn",(matc[i][MATSIZE-1]+3)%3);

}

return 0;

}

#include <string.h>
#include <stdio.h>

int MATSIZE = 801;
int mata[810][810];
int matb[810][810];
int matc[810][810];
int main(){
    while (scanf("%d",&MATSIZE) != EOF) {
        int i,j,k;
        for (i = 0;i < MATSIZE; i++) {
            for (j = 0; j < MATSIZE; j++) {
                scanf("%d",&mata[i][j]);
                mata[i][j] %= 3;
            }
        }
        for (i = 0;i < MATSIZE; i++) {
            for (j = 0; j < MATSIZE; j++) {
                scanf("%d",&matb[i][j]);
                matb[i][j] %= 3;
            }
        }
        memset(matc, 0, sizeof(matc));
     for(k = 0;k < MATSIZE;k++){
        for(i = 0;i < MATSIZE;i++){
            for(j = 0;j < MATSIZE;j++){
                    matc[i][j] += mata[i][k] * matb[k][j];
                }
            }
        }
        for (i = 0;i < MATSIZE; i++) {
            for (j = 0; j < MATSIZE-1; j++) {
                printf("%d ",(matc[i][j]+3)%3);
            }
            printf("%dn",(matc[i][MATSIZE-1]+3)%3);
        }
    }
    return 0;
}

#include <string.h>

#include <stdio.h>

int MATSIZE = 801;

int mata[810][810];

int matb[810][810];

int matc[810][810];

int main(){

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

int i,j,k;

for (i = 0;i < MATSIZE; i++) {

for (j = 0; j < MATSIZE; j++) {

scanf("%d",&mata[i][j]);

mata[i][j] %= 3;

}

for (i = 0;i < MATSIZE; i++) {

for (j = 0; j < MATSIZE; j++) {

scanf("%d",&matb[i][j]);

matb[i][j] %= 3;

}

memset(matc, 0, sizeof(matc));

for(k = 0;k < MATSIZE;k++){

for(i = 0;i < MATSIZE;i++){

for(j = 0;j < MATSIZE;j++){

matc[i][j] += mata[i][k] * matb[k][j];

}

for (i = 0;i < MATSIZE; i++) {

for (j = 0; j < MATSIZE-1; j++) {

printf("%d ",(matc[i][j]+3)%3);

}

printf("%dn",(matc[i][MATSIZE-1]+3)%3);

}

return 0;

}

上面的T下面的过，开始我还以为是TMD被逗了，直到我看到了这个：

http://blog.csdn.net/a775700879/article/details/11750703

然后我就吓尿了。。。10倍的效率差距

上面的那个，是利用了乘法式子中可以通过调整固定一个值，如果这个值是0就可以剪枝不循环这次的第三重直接往下走了，但是收效甚微。

getchar()的输入挂。。。那货我伺候不来，感觉太玄了没有写。

而下面那个是把原来i，j，k循环中的k拿了出来做了第一重，这样带来的变化是原来第三重循环要跳k次行，现在的话第三重循环不再跳行。多维数组是线性存储的，CPU缓存比较小会经常更新，跳列的话，就很有可能无法利用CPU缓存的优势（注意缓存直连CPU，比内存还要快），因为当跳到下一行的时候，刚才那一行可能就被从CPU缓存中清除了，相当于第三重循环里面没有用到CPU缓存机能。

所以当疯狂访问数组的时候，时间卡的很丧病，就要看看是不把CPU缓存机能给浪费了。

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，最高价值是？”这个问题的答案。（没有用滚动数组的话）

求有向图强连通分量的Tarjan算法

January 18, 20152015-01-18hahaschoolLeave a comment

#include <iostream>
#include <algorithm>
#include <vector>
#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;
    }
}

#include <iostream>

#include <algorithm>

#include <vector>

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

}

-_-#上面的ccs应该是scc，名字叫错了跪。。。

关于Tarjan，https://www.byvoid.com/blog/scc-tarjan这个讲的挺好，一定要看看。然后我说下我自己咋想的。

首先初始化，对于每个节点都要分配一个dfn值和low值，开一个tim当作计时器，然后基本的流程就是：

～进入当前节点
～tim＋＋
～当前节点dfn＝low＝tim
～标记当前结点已经走过（注意图的遍历中节点只会走一次，也就是说标记不用撤销）
～把当前节点压入栈中（这个stack预先开好了）
～开始扫当前节点的分支，如果这个分支走过了，判断一下是不是这个分支是不是在栈里，如果在栈里的话就看看分支的dfn是不是比当前节点的low还小，小的话就把当前的low值调成那个dfn值；如果分支没走过，直接递归进到那个分支里去，等到递归出来之后，如果分支的low值比当前low值小，就令当前low值为分支low值（这步比较难懂）
～等到所有分支扫完，检查一下当前的dfn是不是等于low，如果不相等直接退出当前递归就好；相等的话，说明节点是scc的根，这个时候不断弹出栈，直到当前节点也被弹出，弹出的这些节点放在一起就是一组scc。

其实这个Tarjan的原理就是利用时间标记，进入栈的节点都是预定互相连通的，dfu值的意思就是当遍历到这个节点，是第几步（我把tim当作步来看），low的意思就是从当前节点可以走到的尽量在时间上先走到的栈内节点对应的dfu，就是最优解的对应标号，这个low肯定是越小越好，因为low越小我们的连通回路就越大。如果low＝dfu，那就是当前个点已经没有办法和栈里的既有的点连通了，所以当尝试了全部的走法之后还是没有找到一个栈里的节点来和当前点连通，就说明这个连通回路闭合了，这个时候只要把整个连通回路统统从栈里弹出来，就能得到整个连通回路，也就是scc的一个。每步中接下来要走的节点有三种情况：有的节点访问过但是不在栈里，这样的点不用考虑，因为它已经被弹出了，相当于这个节点已经和我们没关系了；有的点访问过而且在栈里，这样的节点有可能就是当前连通回路的终点了，所以我们要比较一下当前low值是不是比它的dfu大，如果大的话说明这个点可以连通过去，如果小的话说明我们已经有一种连通方式可以包括和它连通了，这个不是最优解，我们就忽略好了；有的节点没访问过，这样的点我们要递归进去处理一下，递归完之后这个节点就有了它在当前情形下该有的dfu和low了，因为这个点和当前点连通，所以这个点要是有一个比当前更好的连通方案，我们用它的就好。

基本就是这么搞，这种时间流逝标记的方法很重要（虽然我还不知道到底有多重要。。。）。