NCPC 2006 I - Honeycomb Walk
perm_identity  query_builder
listACM之路,文章  comment评论

回来水文了
本来一道好好的DP大水题 训练赛活活做成找规律 结果最后一个半小时AFK

NCPC 2006 I - Honeycomb Walk
Kattis - honey
POJ 3036 - Honeycomb Walk

1.png

大致题意是有只小蜜蜂 飞在花丛中:)
蜜蜂会走N步(1<=N<=14) 在N步之后蜜蜂会回到初始的起点 求当蜜蜂可以走N步的时候 有多少种走法

首先蜂巢是典型的六边形排列
使用数组模拟蜂巢的排列(取一点的左,左上,上,右,右下,下六个点模拟 bug大佬想到了结构体建边2333333暴力搜索打表)
之后对于点(x,y)在第k步可以走到的走法基于上一步周围六个点的状态
可以推出F(x,y,k)=F(x-1,y,k-1)+F(x-1,y-1,k-1)+F(x,y-1,k-1)+F(x+1,y,k-1)+F(x+1,y+1,k-1)+F(x,y+1,k-1)
直接打个表就过了 一道大水题QwQ 如果比赛真出这种题踩坑了怕不是要后悔一辈子

Accept 2/2 C++ 2ms 3MB:

/**
 * @author    Moe_Sakiya        i@tun.moe
 * @date    2018-04-25 14:34:47
 *
 */

#include <iostream>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <queue>

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>

using namespace std;

int t, n;

//对于点x,y来说在第n步的最大路径数
int dparr[30][30][15];

void calDP(void) {
    int i, j, k;
    //init
    dparr[15][15][0] = 1;
    for(k = 1; k <= 14; k++)
        for(i = 1; i <= 29; i++)
            for(j = 1; j <= 29; j++)
                dparr[i][j][k] = dparr[i][j - 1][k - 1] + dparr[i - 1][j - 1][k - 1] + dparr[i-1][j][k - 1] + dparr[i][j + 1][k - 1] + dparr[i + 1][j + 1][k - 1] + dparr[i + 1][j][k - 1];
    return;
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    calDP();
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        printf("%d\n", dparr[15][15][n]);
    }
    return 0;
}

POJ 1273 - Drainage Ditches
perm_identity  query_builder
listACM之路,文章  comment评论

一道网络流
今天实在是无聊...只能拿以前的代码水博客玩...

不得不吐槽这次的蓝桥杯,自己真成送财童子了.
QwQ 我反正以后不会再打蓝桥杯这种东西了.

1.png

Accept G++ 0ms 1104kB:

/**
 * @author    Moe_Sakiya        i@tun.moe
 * @date        2018-04-02 17:55:58
 *
 */

#include <iostream>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <queue>
#include <deque>

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>

using namespace std;

#define INF 233333333

int n, m;
int graph[300][300], layer[300];
bool vis[300];

bool isExistLayer(void) {
    int i, curr;
    deque<int> que;
    //init
    memset(layer, 0xff, sizeof(layer));
    //BFS
    layer[1] = 0;
    que.push_back(1);
    while (!que.empty()) {
        curr = que.front();
        que.pop_front();
        //遍历数组
        for (i = 1; i <= m; i++)
            if (graph[curr][i] > 0 && layer[i] == -1) {
                layer[i] = layer[curr] + 1;
                if (i == m) {
                    //搜到汇点
                    return true;
                }
                else {
                    //加入队列 继续BFS
                    que.push_back(i);
                }
            }
    }
    //未找到汇点 算法停止
    return false;
}

int dinic(void) {
    int i, curr, minTransfer, minTransfer_s, u, v;
    int maxFlow = 0;
    deque<int> que;
    //BFS 是否可以探寻到汇点
    while (isExistLayer()) {
        //init
        memset(vis, 0, sizeof(vis));
        vis[1] = true;
        //DFS
        que.push_back(1);
        while (!que.empty()) {
            curr = que.back();
            if (curr != m) {
                //不是汇点 继续DFS下一层
                for (i = 1; i <= m; i++)
                    if (graph[curr][i] > 0 && layer[curr] + 1 == layer[i] && vis[i] == false) {
                        vis[i] = true;
                        que.push_back(i);
                        break;
                    }
                //寻找不到有效点 出栈回溯
                if (i > m)
                    que.pop_back();
            } else {
                //是汇点 计算最大流
                //寻找当前流中的最小边
                minTransfer = INF;
                for (i = 1; i < (int)que.size(); i++) {
                    u = que[i - 1];
                    v = que[i];
                    if (graph[u][v] > 0 && graph[u][v] < minTransfer) {
                        //更新最小边
                        minTransfer = graph[u][v];
                        minTransfer_s = u;
                    }
                }
                //将最小值加入流中
                maxFlow += minTransfer;
                //增广扩边
                for (i = 1; i < (int)que.size(); i++) {
                    u = que[i - 1];
                    v = que[i];
                    //减少当前边 增加反向边
                    graph[u][v] -= minTransfer;
                    graph[v][u] += minTransfer;
                }
                //回溯到最小点 继续DFS
                while(!que.empty()&&que.back()!=minTransfer_s){
                    vis[que.back()]=false;
                    que.pop_back();
                }
            }
        }
    }
    return maxFlow;
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int i;
    int s, e, c;
    while (~scanf("%d %d", &n, &m)) {
        //init
        memset(graph, 0, sizeof(graph));
        //建图
        for (i = 0; i < n; i++) {
            scanf("%d %d %d", &s, &e, &c);
            graph[s][e] += c;
        }
        //solve
        printf("%d\n", dinic());
    }
    return 0;
}

HDU 2222 - Keywords Search
perm_identity  query_builder
listACM之路,文章  comment评论

emmmm....
一道裸着的AC自动机

纯动态指针实现的...觉得拿来教学感觉不错
不得不说靠着理解敲代码...还是有点难受的

以后会考虑出算法专题的....虽然我是个蒟蒻,但是有着一条变咸鱼的心啊

1.png

Accept G++ 811ms 57224kB:

/**
 * @author    Moe_Sakiya        i@tun.moe
 * @date        2018-04-02 19:02:12
 *
 */

#include <iostream>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <queue>

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>

using namespace std;

int t, n;
char keyWord[51];
char mainWord[1000001];

//定义结构体
struct TrieNode {
    //匹配失败指针
    TrieNode * failPtr;
    //子节点指针
    TrieNode * nextPtr[26];
    //判断是否是单词的结尾 是为1 不是为0
    int cnt;
} root;

//初始化Trie树节点
void initTrieNode(TrieNode * nowPtr) {
    nowPtr->failPtr = NULL;
    memset(nowPtr->nextPtr, 0, sizeof(nowPtr->nextPtr));
    nowPtr->cnt = 0;
    return;
}

//插入关键词
void insertWord(char * str) {
    int i, len;
    TrieNode * nowPtr = &root;
    len = strlen(str);
    for (i = 0; i < len; i++) {
        if (nowPtr->nextPtr[str[i] - 'a'] == NULL) {
            nowPtr->nextPtr[str[i] - 'a'] = (TrieNode *)malloc(sizeof(struct TrieNode));
            initTrieNode(nowPtr->nextPtr[str[i] - 'a']);
        }
        nowPtr = nowPtr->nextPtr[str[i] - 'a'];
    }
    //当前单词已经结尾
    nowPtr->cnt++;
    return;
}

//构建失败指针的同时构建跳转
void buildFailPtr(void) {
    //初始化队列 用于存放节点的指针 方便BFS
    queue<TrieNode *> que;
    TrieNode * nowPtr = &root;
    int i;
    //初始化根节点的失败指针
    root.failPtr = &root;
    //构建根节点的子节点的失败指针(匹配跳转指针)
    for (i = 0; i < 26; i++)
        if (root.nextPtr[i] == NULL)
            root.nextPtr[i] = &root;
        else {
            //先将子节点的失败指针指向根节点 加入队列 在BFS的时候更新
            root.nextPtr[i]->failPtr = &root;
            que.push(root.nextPtr[i]);
        }
    while (!que.empty()) {
        //取出队列前端元素
        nowPtr = que.front();
        que.pop();
        //遍历26个子节点 重复类似根节点的操作
        for (i = 0; i < 26; i++)
            if (nowPtr->nextPtr[i] == NULL) {
                //构建跳转 当下一节点为空时 将下一节点的指针指向失败指针下一节点
                nowPtr->nextPtr[i] = nowPtr->failPtr->nextPtr[i];
            } else {
                //当下一节点不为空时 构建失败指针
                nowPtr->nextPtr[i]->failPtr = nowPtr->failPtr->nextPtr[i];
                //加入队列 继续BFS
                que.push(nowPtr->nextPtr[i]);
            }
    }
    return;
}

//在主字符串中搜索关键词总共出现的次数
int searchKeyWord(void) {
    int len = strlen(mainWord);
    int i, ans = 0;
    TrieNode * nowPtr = &root;
    TrieNode * matchPtr;
    for (i = 0; i < len; i++) {
        //使当前指针向后移 如果匹配继续 否则自动跳转
        nowPtr = nowPtr->nextPtr[mainWord[i] - 'a'];
        //使匹配指针指向当前指针
        matchPtr = nowPtr;
        //匹配指针向后匹配 向所有的失败指针进行跳转 如果存在关键字 即ans+1 否则一直是ans+0 由于前面的构建 最后总是会跳转到根节点
        while (matchPtr != &root) {
            ans = ans + matchPtr->cnt;
            matchPtr->cnt = 0;
            matchPtr = matchPtr->failPtr;
        }
    }
    return ans;
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int i;
    scanf("%d", &t);
    while (t--) {
        initTrieNode(&root);
        scanf("%d", &n);
        getchar();
        for (i = 0; i < n; i++) {
            gets(keyWord);
            insertWord(keyWord);
        }
        gets(mainWord);
        buildFailPtr();
        printf("%d\n", searchKeyWord());
    }
    return 0;
}

emmmm...又要摸鱼了
perm_identity  query_builder
list日志  comment评论

校赛出线了...过两天应该要去参加天梯杯...
西安邀请赛的队伍也组好了,开始摸鱼了...

过两天可能会把这个根本没人看的博客前端重写一遍...
emmm...但是近期并不打算开源...但也说不定

不得不吐槽学校的"创青春"大赛...逼着我去学Android开发...QwQ宝宝心里苦


CodeForces 918B - Radio Station
perm_identity  query_builder
listACM之路,文章  comment2 条评论

前天CF排位赛的题
考验对STL的运用...

来源 Codeforces Round #459 (Div. 2)

1.png
2.png

Accept GNU G++14 6.2.0 15ms 2072kB

/**
 * @author    Moe_Sakiya        i@tun.moe
 * @date        2018-01-29 23:36:36
 *
 */

#include <iostream>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <queue>

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>

using namespace std;

string name[1000];
map<string, int> smap;

int main(void) {
    string command, ip;
    int i, n, m;
    cin >> n >> m;
    for (i = 0; i < n; i++) {
        cin >> command >> ip;
        name[i] = command;
        smap[ip] = i;
    }
    for (i = 0; i < m; i++) {
        cin >> command >> ip;
        ip.pop_back();
        cout << command << " " << ip << "; #" << name[smap[ip]] << endl;
    }
    return 0;
}

  1. 1
  2. 2
  3. 3
  4. 4
  5. 5
  6. 6
  7. ...
  8. 11