Windless
订阅/Feed
稗田千秋(i@wind.moe)

「数论篇」矩阵快速幂

荒废了好久的算法,写几篇关于算法的复习笔记找找手感,在测试 Mathjax 的矩阵时有感而发,便写写矩阵快速幂吧。

幂运算即指数运算,用于表示某数自乘数次,因此易得最基本计算的方法复杂度为 O(N),

快速幂全称快速幂取模,可以在 O(log₂N) 得出结果,用于快速计算某个数的n次幂,此处的n一般很大而导致 O(N) 复杂度超时,而且题目通常会给出一个额外要求使结果对数k取模。

稗田千秋
Dec.24 2016 algorithm

hihoCoder 1291 - Building in Sandbox 题解

描述

Little Hi is playing a sandbox voxel game. In the game the whole world is constructed by massive 1x1x1 cubes. The edges of cubes are parallel to the coordinate axes and the coordinates (x, y, z) of the center of each cube are integers.

At the beginning there is nothing but plane ground in the world. The ground consists of all the cubes of z=0. Little Hi needs to build everything by placing cubes one by one following the rules:

  1. The newly placed cube must be adjacent to the ground or a previously placed cube. Two cubes are adjacent if and only if they share a same face.

  2. The newly placed cube must be accessible from outside which means by moving in 6 directions(up, down, left, right, forward, backward) there is a path from a very far place - say (1000, 1000, 1000) in this problem - to this cube without passing through ground or other cubes.

Given a sequence of cubes Little Hi wants to know if he can build the world by placing the cubes in such order.

稗田千秋
Apr.10 2016 algorithm

Flood Fill

Flood Fill(洪水填充)是计算机图形学的一种填充算法,用于将一个区域中连通的同色点染成相同颜色,原理很简单,非常像搜索,即从一个点向周围寻找符合条件的点填充遍历,最常见的有四路填充法(4-Way Recursive Method),八路填充法(8-Way Recursive Method)和基于扫描线的填充法(Recursive Scanline),根据实现又能分为基于递归和基于栈。笔者不是图形学方向的,这里仅涉及可能使用到的四路填充法。

基于递归的四路填充算法实现

代码很简单,就是在深度搜索的基础上加个标记,取一个种子像素点,向其四个邻域拓展,满足条件时则对其进行染色,不断重复这个行为,但也容易由于递归导致栈溢出。

void floodFill4(int x, int y, int newColor, int oldColor){
  if (x >= 0 && x < w && y >= 0 && y < h && screenBuffer[y][x][y] == oldColor && screenBuffer[x] != newColor){
    screenBuffer[y][x] = newColor;
    floodFill4(x + 1, y, newColor, oldColor);
    floodFill4(x - 1, y, newColor, oldColor);
    floodFill4(x, y + 1, newColor, oldColor);
    floodFill4(x, y - 1, newColor, oldColor);
  }
}

部分题解

QDUOJ 7 - GZS与小公园

某天GZS漫步在学校新建的小公园,他发现那里建成了一些水池和小河道。我们暂且把它们统一看成水池。假设公园旁有一张小公园的地图,上面仅标识了此处是否是水池,你能帮GZS计算出该地图中一共有几个水池吗。

 #include <cstdio>
#include <cstring>
#define bool int
#define true 1
#define false 0
#define MEM(x,y) memset(x,y,sizeof(x))
using namespace std;
int poor[105][105];
int t, m, n, color;
int direction[4][2] = { 0,1,1,0,-1,0,0,-1 };
bool valid(int x, int y, int oldColor) {
    if (x < 0 || y < 0 || x >= m || y >= n || poor[x][y] != oldColor)
        return false;
    return true;
}
void floodfill(int x,int y,int oldColor,int newColor) {
    if (!valid(x, y, oldColor))
        return;
    poor[x][y] = newColor;
    for (int i = 0; i < 4; i++)
        floodfill(x+direction[i][0], y+direction[i][1], oldColor, newColor);
}
int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%d %d", &m, &n);
        color = 0;
        MEM(poor, 0);
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                scanf("%d", &poor[i][j]);
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if(valid(i, j, 1))
                    color++,floodfill(i, j, 1, 0);
        printf("%d\n", color);
    }
}
稗田千秋
Apr.09 2016 algorithm

TRIE 树

字典树(TRIE树,前缀树)是一种树形结构,核心思想是以空间换时间,常用于在相对较低的复杂度内统计和排序大量的字符串。

基本性质

与二叉查找树不同,字典树的键不是直接保存在节点中,而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀,也就是这个节点对应的字符串,而根节点对应空字符串。一般情况下,不是所有的节点都有对应的值,只有叶子节点和部分内部节点所对应的键才有相关的值。

结构体结构

如果用数组来存储,当是稀疏数组时无疑浪费了大量空间,于是使用链表来压缩存储空间,其中children是一个指针数组,存放指向各个子节点的指针。

typedef struct node{
    int count;  //统计前缀次数
    struct node *children[TREE_WIDTH];  //指向子节点
    int flag;  //按需使用
}

代码实现

下面给出一种C语言前缀查询的代码,代码大同小异,需要时仅需稍作改动即可食用。

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

#define ARRAY_SIZE(a) sizeof(a) / sizeof(a[0])
#define CHAR_TO_INDEX(c) c - 'a'
#define MEM(x,y) memset(x,y,sizeof(x))
#define TREE_WIDTH 256

typedef struct node{
    int count;
    struct node *children[TREE_WIDTH];
}TrieNode, *Trie;

TrieNode* create(){
    TrieNode* node = (TrieNode *)malloc(sizeof(TrieNode));
    node->count = 0;
    MEM(node->children, 0);
    return node;
}

void insert(Trie root, char* word){
    Trie node = root;
    char *p = word;
    while (*p){
        if (node->children[CHAR_TO_INDEX(*p)] == NULL)
            node->children[CHAR_TO_INDEX(*p)] = create();
        node = node->children[CHAR_TO_INDEX(*p++)];
        node->count += 1;
    }
}

int search(Trie root, char* word) {
    Trie node = root;
    char *p = word;
    while (*p){
        node = node->children[CHAR_TO_INDEX(*p++)];
        if (node == NULL)
            return 0;
    }
    return node->count;
}

int main() {
    Trie root = create();
    char words[][10] = { "hieda", "no", "chiaki", "handsome", "char", "int", "bool", "double", "not", "doubt" };
    for (int i = 0; i < ARRAY_SIZE(words); i++)
        insert(root, words[i]);
    printf("%d\n", search(root, "c"));
    printf("%d\n", search(root, "chiaki"));
    printf("%d\n", search(root, "result"));
}

下期自动机见w

稗田千秋
Mar.26 2016 algorithm

开源 OnlineJudge

qduoj 是 青岛大学开源的一个 OnlineJudge,GitHub 地址https://github.com/QingdaoU/OnlineJudge

acmer 常用的 oj 是 hduoj 、 poj 等等,但是有些不是很满意的地方。

首先是界面,国内的前辈 oj 大多数都很丑很丑, 10 多年前的风格,可能因为 oj 就是 10 多年前写的吧。

用起来也有些不是很方便的地方,比如提交题目要新开页面,要再选择题号,再手动刷新看结果。自己内部比赛有些规则也没办法去设置,自己没法去添加题目去查看测试用例等等。

当然,qduoj 的定位不仅仅是 ACM 训练,还有学校平时教学的作业考试等也可以在上面进行。 老师作为普通管理员可以创建小组,相当于一个班级,内部举办比赛,创建修改题目,外人不可见,超级管理员才可以管理公开的题目和比赛。

oj 后端涉及到的技术有 Python 、 Django 、 Docker 、 MySQL 、 Redis 、 Celery 等,后台的前端是一个 SPA 页面,使用 avalon js 。

欢迎感兴趣的小伙伴搭建试用~

不擅软文某千秋
Feb.04 2016 algorithm
  • play_arrow

About this site

version:1.02 Alpha
博客主题: Lime
联系方式: i@wind.moe
写作语言: zh_CN & en_US
博客遵循 CC BY-NC-SA 4.0许可进行创作

此外,本博客会基于访客的Request Headers记录部分匿名数据用于统计(Logger的源码见Github),包含Referer, User-Agent & IP Address.个人绝不会主动将数据泄露给第三方