2019-01-10发表2020-05-05更新C++算法5 分钟读完 (大约815个字)

Cpp算法-大整数类

#include<string>
#include<iostream>
#include<iosfwd>
#include<cmath>
#include<cstring>
#include<stdlib.h>
#include<stdio.h>
#include<cstring>
using namespace std;

const int maxl = 5000;
#define max(a, b) a>b ? a : b
#define min(a, b) a<b ? a : b

class BigInteger
{
	public:
		int len, s[maxl];
		
		BigInteger();
		BigInteger(const char*);
		BigInteger(int);
		bool sign;
		string toStr() const;
		friend istream& operator>>(istream&, BigInteger&);
		friend ostream& operator<<(ostream&, BigInteger&);

		BigInteger operator=(const char*);
		BigInteger operator=(int);
		BigInteger operator=(const string);

		bool operator>(const BigInteger&) const;
		bool operator>=(const BigInteger&) const;
		bool operator>(const BigInteger&) const;
		bool operator>=(const BigInteger&) const;
		bool operator==(const BigInteger&) const;
		bool operator!=(const BigInteger&) const;

		BigInteger operator+(const BigInteger&) const;
		BigInteger operator++();
		BigInteger operator++(int);
		BigInteger operator+=(const BigInteger&);
		BigInteger operator-(const BigInteger&) const;
		BigInteger operator--();
		BigInteger operator--(int);
		BigInteger operator-=(const BigInteger&);
		BigInteger operator*(const BigInteger&) const;
		BigInteger operator*(const int num) const;
		BigInteger operator*=(const BigInteger&);
		BigInteger operator/(const BigInteger&) const;
		BigInteger operator/=(const BigInteger&);

		BigInteger operator%(const BigInteger&) const;
		BigInteger factorial() const;
		BigInteger Sqrt() const;
		BigInteger Pow(const BigInteger&) const;

		void clean();
		~BigInteger;
};


BigInteger::BigInteger()
{
	memset(s, 0, sizeof(s));
	len = 1;
	sign = 1;
}

BigInteger::BigInteger(const char *num)
{
	*this = num;
}

BigInteger::BigInteger(int num)
{
	*this = num;
}

string BigInteger::toStr() const
{
	string res;
	res = "";
	for (int i = 0; i < len; ++i)
		res = (char)(s[i] + '0') + res;
	if (res == "") res = "0";
	if (!sign && res != "0") res = "-" + res;
	return res;
}

istream& operator>>(istream& in, BigInteger& num)
{
	string str;
	in>>str;
	num = str;
	return in;
}

ostream& operator<<(ostream& out, BigInteger& num)
{
	out<<num.toStr();
	return out;
}

BigInteger BigInteger::operator=(const char* num)
{
	memset(s, 0, sizeof(s));
	char a[maxl] = "";
	if (num[0] != "-")
		strcpy(a, num);
	else
		for (int i = 1; i < strlen(num); ++i)
			a[i - 1] = num[i];
	sign = !(num[0] == "-");
	len = strlen(a);
	for (int i = 0; i < strlen(a); ++i)
		s[i] = a[len - i - 1] - 48;
	return *this;
}

BigInteger BigInteger::operator=(int num)
{
	if (num < 0)
		sign = 0, num = -num;
	else
		sign = 1;
	char temp[MAX_L];
	sprintf(temp, "%d", num);
	*this = temp;
	return *this;
}

BigInteger BigInteger::operator=(const string num)
{
	const char* tmp;
	tmp = num.c_str();
	*this = tmp;
	return *this;
}

bool BigInteger::operator<(const BigInteger& num) const
{
	if (sign^num.sign)
		return num.sign;
	if (len != num.len)
		return len < num.len;
	for (int i = len - 1; i >= 0; --i)
		if (s[i] != num.s[i])
			return sign ? (s[i] < num.s[i]) : (s[i] > num.s[i])
	return !sign;
}

bool BigInteger::operator>(const BigInteger& num) const
{
	return num < *this;
}

bool BigInteger::operator<=(const BigInteger& num) const
{
	return !(*this > num);
}

bool BigInteger::operator>=(const BigInteger& num) const
{
	return !(*this < num);
}

bool BigInteger::operator!=(const BigInteger& num) const
{
	return *this > num || *this < num;
}

bool BigInteger::operator==(const BigInteger& num) const
{
	return !(num != *this);
}

BigInteger BigInteger::operator+(const BigInteger& num) const
{
	 if (sign^num.sign)
	 {
		 BigInteger tmp = sign ? num : *this;
		 tmp.sign = 1;
		 return sign ? *this - tmp : num - tmp;
	 }
	 BigInteger result;
	 result.len = 0;
	 int temp = 0;
	 for (int i = 0; temp || i < (max(len, num.len)); i++)
	 {
		 int t = s[i] + num.s[i] + temp;
		 result.s[result.len++] = t % 10;
		 temp = t / 10;
	 }
	 result.sign = sign;
	 return result;
}

BigInteger BigInteger::operator++()
{
	*this = *this + 1;
	return *this;
}

BigInteger BigInteger::operator++(int)
{
	BigInteger old = *this;
	++(*this);
	return old;
}

BigInteger BigInteger::operator+=(const BigInteger& num)
{
	*this = *this + num;
	return *this;
}

BigInteger BigInteger::operator-(const BigInteger& num) const
{
	 BigInteger b = num, a = *this;
	 if (!num.sign && !sign)
	 {
		 b.sign = 1;
		 a.sign = 1;
		 return b - a;
	 }
	 if (!b.sign)
	 {
		 b.sign = 1;
		 return a + b;
	 }
	 if (!a.sign)
	 {
		 a.sign = 1;
		 b = BigInteger(0) - (a + b);
		 return b;
	 }
	 if (a < b)
	 {
		 BigInteger c = (b - a);
		 c.sign = false;
		 return c;
	 }
	 BigInteger result;
	 result.len = 0;
	 for (int i = 0, g = 0; i < a.len; i++)
	 {
		 int x = a.s[i] - g;
		 if (i < b.len) x -= b.s[i];
		 if (x >= 0) g = 0;
		 else
		 {
			 g = 1;
			 x += 10;
		 }
		 result.s[result.len++] = x;
	 }
	 result.clean();
	 return result;
}

BigInteger BigInteger::operator--()
{
	*this = *this - 1;
	return *this;
}

BigInteger BigInteger::operator--(int)
{
	BigInteger old = *this;
	--(*this);
	return old;
}

BigInteger BigInteger::operator-=(const BigInteger& num)
{
	*this = *this - num;
	return *this;
}

BigInteger BigInteger::operator*(const BigInteger& num) const
{
	BigInteger result;
	result.len = len + num.len;
	for (int i = 0; i < len; i++)
		for (int j = 0; j < num.len; j++)
			result.s[i + j] += s[i] * num.s[j];
	for (int i = 0; i < result.len; i++)
	{
		 result.s[i + 1] += result.s[i] / 10;
		 result.s[i] %= 10;
	}
	result.clean();
	result.sign = !(sign^num.sign);
	return result;
}

BigInteger BigInteger::operator*(const int num) const
{
	BigInteger x = num;
	BigInteger z = *this;
	return *this;
}

BigInteger BigInteger::operator/(const BigInteger& num) const
{
	 BigInteger ans;
	 ans.len = len - num.len + 1;
	 if (ans.len < 0)
	 {
		 ans.len = 1;
		 return ans;
	 }
	 BigInteger divisor = *this, divid = num;
	 divisor.sign = divid.sign = 1;
	 int k = ans.len - 1;
	 int j = len - 1;
	 while (k >= 0)
	 {
		 while (divisor.s[j] == 0) j--;
		 if (k > j) k = j;
		 char z[MAX_L];
		 memset(z, 0, sizeof(z));
		 for (int i = j; i >= k; i--)
			 z[j - i] = divisor.s[i] + '0';
			 BigInteger dividend = z;
			 if (dividend < divid) { k--; continue; }
			 int key = 0;
			 while (divid*key <= dividend) key++;
			 key--;
			 ans.s[k] = key;
			 BigInteger temp = divid*key;
			 for (int i = 0; i < k; i++)
				 temp = temp * 10;
				 divisor = divisor - temp;
				 k--;
	 }
	 ans.clean();
	 ans.sign = !(sign^num.sign);
	 return ans;
}

BigInteger BigInteger::operator/=(const BigInteger& num)
{
	*this = *this / num;
	return *this;
}

BigInteger BigInteger::operator%(const BigInteger& num) const
{
	BigInteger a = *this, b = num;
	a.sign = b.sign = 1;
	BigInteger result, temp = a / b*b;
	result = a - temp;
	result.sign = sign;
	return result;
}

BigInteger BigInteger::Pow(const BigInteger& num) const
{
	BigInteger result = 1;
	for (BigInteger i = 0; i < num; i++)
		result = result * (*this);
		return result;
}

BigInteger BigInteger::factorial() const
{
	BigInteger result = 1;
	for (BigInteger i = 1; i <= *this; i++)
		result *= i;
	return result;
}

void BigInteger::clean()
{
	if (len == 0) len++;
	while (len > 1 && s[len - 1] == '\0')
		len--;
}

BigInteger BigInteger::Sqrt() const
{
	if(*this < 0) return - 1;
	if(*this <= 1)return *this;
	BigInteger l = 0, r = *this, mid;
	while(r - l > 1)
	{
		mid = (l + r) / 2;
		if(mid * mid > *this)
			r = mid;
		else
			l = mid;
	}
	return l;
}

BigInteger::~BigInteger()
{

}

2019-01-10发表2020-05-05更新C++算法4 分钟读完 (大约537个字)

Cpp算法-BFS

说明

本文实现只是框架，应当灵活运用，bfs()函数内部根据情况灵活更改
广搜算法基于树、队列实现，具体思路: 将当前点的子节点入队，当前点出队，如果子节点满足条件则记录并重复此过程

框架

数组模拟队列

void bfs()
{
    int head = 1, tail = 2;
    vis[start_x][start_y] = true;            //标记起始点
    que[head][0] = start_x; 
    que[head][1] = start_y;                  //起始点入队
    while(head < tail)                       //队不为空
    {
        int x = que[head][0], y = que[head][1]  //获取队首点
        for (int i = 0; i < 子节点数; ++i)
        {
            int x2 = x子节点, y2 = y子节点;
            if (x2, y2满足条件 && !vis[x2][y2])
            {
                记录结果;
                vis[x2][y2] = true;
                que[tail][0] = x2;
                que[tail][0] = y2;
                tail++;                         //入队
            }
        }
        head++;                                 //队首出队
    }
    return
}

STL-queue

struct Node
{
    int x, y;
}node, top;

queue<Node> que;

void bfs()
{
    vis[sx][sy] = true;
    node.x = sx;
    node.y = sy;
    que.push(node);
    ans[sx][sy] = 0;
    while(!que.empty())
    {
        top = que.front();
        for (int i = 0; i < 8; ++i)
        {
            int x2 = ..., y2 = ...;
            if (x2, y2满足条件 && !vis[x2][y2])
            {
                记录结果;
                vis[x2][y2] = true;
                node.x = x2;
                node.y = y2;
                que.push(node);
            }
        }
        que.pop();
    }
    return;
}

例

洛谷P1443

#include<bits/stdc++.h>
using namespace std;

int n, m, sx, sy, vis[210][210], ans[210][210];
int gox[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
int goy[8] = {1, 2, 2, 1, -1, -2, -2, -1};

struct horse
{
    int x, y;
}node, top;

queue<horse> que;

void bfs()
{
    vis[sx][sy] = 1;
    node.x = sx;
    node.y = sy;
    que.push(node);
    ans[sx][sy] = 0;
    while(!que.empty())
    {
        top = que.front();
        for (int i = 0; i < 8; ++i)
        {
            int x2 = top.x + gox[i];
            int y2 = top.y + goy[i];
            if (x2 >= 1 && x2 <= n && y2 >= 1 && y2 <= m && !vis[x2][y2])
            {
                ans[x2][y2] = ans[top.x][top.y] + 1;
                vis[x2][y2] = 1;
                node.x = x2;
                node.y = y2;
                que.push(node);
            }
        }
        que.pop();
    }
    return;
}

int main()
{
    scanf("%d %d %d %d", &n, &m, &sx, &sy);
    memset(ans, -1, sizeof(ans));
    bfs();
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
            printf("%-5d", ans[i][j]);
        printf("\n");
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;

int n, m, sx, sy, vis[210][210], que[50000][2], ans[210][210];
int gox[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
int goy[8] = {1, 2, 2, 1, -1, -2, -2, -1};

void bfs()
{
    int head = 1, tail = 2;
    vis[sx][sy] = 1;
    que[head][0] = sx;
    que[head][1] = sy;
    ans[sx][sy] = 0;
    while (head < tail)
    {
        int x, x2, y, y2;
        x = que[head][0];
        y = que[head][1];
        for (int i = 0; i < 8; ++i)
        {
            x2 = x + gox[i];
            y2 = y + goy[i];
            if (x2 >= 1 && x2 <= n && y2 >= 1 && y2 <= m && !vis[x2][y2])
            {
                ans[x2][y2] = ans[x][y] + 1;
                vis[x2][y2] = 1;
                que[tail][0] = x2;
                que[tail][1] = y2;
                tail++;
            }
        }
        head++;
    }
    return;
}

int main()
{
    scanf("%d %d %d %d", &n, &m, &sx, &sy);
    memset(ans, -1, sizeof(ans));
    bfs();
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
            printf("%-5d", ans[i][j]);
        printf("\n");
    }
    return 0;
}

2019-01-10发表2020-05-05更新C++算法2 分钟读完 (大约227个字)

Cpp算法-DFS

说明

本文实现只是框架，应当灵活运用，dfs(…)函数返回值类型、参数列表根据情况灵活更改

框架

void dfs(参数列表)
{
    if (到达目的地) 输出结果;
    else
    {
        for (int i = 0; i < 行动方法数; ++i)
        {
            if (下一步可行)
            {
                记录此步;
                dfs(改动后的参数列表);
                取消记录此步;
            }
        }
    }
    return;
}

例

洛谷P1605

#include<bits/stdc++.h>
using namespace std;

int n, m, t, sx, sy, fx, fy, ans;
int mg[6][6], now[6][6];
int go[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

void dfs(int x, int y)
{
    int x2, y2;
    if (x == fx && y == fy) ans++;
    else
    {
        for (int i = 0; i < 4; ++i)
        {
            x2 = x + go[i][0];
            y2 = y + go[i][1];
            if (x2 > 0 && x2 <= n && y2 > 0 && y2 <= m && mg[x2][y2] == 0 && now[x2][y2] == 0)
                
            {
                now[x2][y2] = 1;
                dfs(x2, y2);
                now[x2][y2] = 0;
            }
        }
    }
    return;
}

int main()
{
    memset(mg, 0, sizeof(mg));
    scanf("%d %d %d", &n, &m, &t);
    scanf("%d %d %d %d", &sx, &sy, &fx, &fy);
    for (int i = 1; i <= t; ++i)
    {
        int x, y;
        scanf("%d %d", &x, &y);
        mg[x][y] = 1;
    }
    now[sx][sy] = 1;
    ans = 0;
    dfs(sx, sy);
    printf("%d", ans);
    return 0;
}

2019-01-09发表2020-05-05更新5 分钟读完 (大约713个字)

Linux美化方案

I. 初步系统优化

更改系统时间
安装python
sudo apt install python
安装git并添加ssh密钥
sudo apt install git
git config --global user.name "your_name"
git config --global user.email "you@example.com"
ssh-keygen -t rsa -C "your_email@youremail.com"一路回车
cat ~/.ssh/id_rsa.pub并复制粘贴到github上
ssh -T git@github.com测试
git clone https://github.com/Tony031218/Beautiful_Linux.git克隆下本仓库

添加语言

  settings -> Region&Language -> manage installed language -> install/remove languages
                              -> input sources

软件更新
sudo apt update
sudo apt upgrade
安装GDebi
sudo apt install gdebi
卸载libreoffice 安装 WPS(可选)
sudo apt remove libreoffice-common
从http://www.wps.cn/product/wpslinux/ 上下载WPS
sudo dpkg -i wps-office_10.1.0.6757_amd64.deb
卸载firefox 安装 Chrome(可选)
sudo apt remove firefox
wget https://dl.google.com/linux/direct/google-chrome-stable_current_amd64.deb
sudo dpkg -i google-chrome*
sudo apt -f install
更换更新源
左下角 -> all -> Software&Updates
sudo apt update
安装vim
sudo apt install vim
菜单栏位置
gsettings set com.canonical.Unity.Launcher launcher-position Bottom底部
gsettings set com.canonical.Unity.Launcher launcher-position Left左侧

II. 主题配置

安装 Unity-tweak-tool
sudo apt install unity-tweak-tool
如果出现报错需要安装缺失的包
安装 Flatabulous 主题
sudo add-apt-repository ppa:noobslab/themes
sudo apt update
sudo apt install flatabulous-theme主题
sudo add-apt-repository ppa:noobslab/icons
sudo apt update
sudo apt install ultra-flat-icons图标
unity-tweak-tool -> 主题/图标
字体
Monaco Powerline 也可以选择其他字体,但一定要支持Powerline的,否则后文会出现乱码

III. 终端Terminal美化

Terminal zsh
sudo apt install zsh
git clone https://github.com/robbyrussell/oh-my-zsh.git
cd oh-my-zsh/tools
./install.sh
更换默认shell
chsh按步骤来输入zsh地址
zsh插件
- 自动补全
  git clone https://github.com/zsh-users/zsh-autosuggestions $ZSH_CUSTOM/plugins/zsh-autosuggestions
- 快速跳转
  git clone https://github.com/joelthelion/autojump.git
  cd autojump
  ./install.py按要求把代码填写到~/.zshrc文件尾
- 配置
  vim ~/.zshrc
  修改60行左右的pluginsplugins=(git autojump zsh-suggestions)
- 修改皮肤
  ~/.zshrc中的ZSH_THEME="robbyrussell"更改

IV. vim美化

molokai
mkdir ~/.vim/colors
将本仓库中的molokai.vim复制到~/.vim/colors/下
Powerline
sudo apt install python-pip
pip install git+git://github.com/powerline/powerline
pip show powerline-status
按照具体位置更改~/.vimrc中的set rtp+=...一行(后文)
插件
- pathogen插件管理
  mkdir -p ~/.vim/autoload ~/.vim/bundle
  curl -LSso ~/.vim/autoload/pathogen.vim https://tpo.pe/pathogen.vim
- nerdtree文件浏览器
  cd ~/.vim/bundle
  git clone https://github.com/scrooloose/nerdtree.git
- taglist大纲界面
  taglist官网
  下载后解压到~/.vim/bundle/下
vimrc
将本仓库中的vimrc.txt复制到~/.vimrc中
内包含括号匹配,html标签匹配,powerline配置(可能需要改动),cpp.sh.java.py的文件头自动输入,插件的配置(F3打开nerdtree,F4打开taglist)