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

Cpp算法-图论-欧拉回路

邻接矩阵

说明

G[][]邻接矩阵

deg[]度

ans[]欧拉回路

n, e点数、边数

实现

int G[maxn][maxn], deg[maxn], ans[maxn];
int n, e, x, y, ansi, s;

void Euler(int i)
{
	for (int j = 1; j <= n; ++j)
	{
		if (G[i][j])
		{
			G[i][j] = G[j][i] = 0;
			Euler(j);
		}
	}
	ans[++ansi] = i;
}

int main()
{
	scanf("%d %d", &n, &e);
	for (int i = 1; i <= e; ++i)
	{
		scanf("%d %d", &x, &y);
		G[x][y] = G[y][x] = 1;
		deg[x]++;
		deg[y]++;
	}
	s = 1;
	for (int i = 1; i <= n; ++i)
		if (deg[i] % 2 == 1)
			s = i;
	Euler(s);
	for (int i = 1; i <= ansi; ++i)
		printf("%d ", ans[i]);
	printf("\n");
	return 0;
}

链式前向星

说明

n, m点数、边数

head, edge[]链式前向星

ans[], ansi路径、数组大小

vis[]记录

make()建图

实现

int head[maxn];
struct Node
{
	int to, next;
}edge[maxm];

void make()
{
	scanf("%d %d", &n, &m);
	for (int k = 1; k <= m; ++k)
	{
		int i, j;
		scanf("%d %d", &i, &j);
		edge[k].to = i;
		edge[k].next = head[i];
		head[i] = k;
	}
	return;
}

int ans[maxm];
int ansi = 0;
bool vis[2 * maxm];

void dfs(int now)
{
    for (int k = head[now]; k != 0; k = edge[k].next)
	{
        if (!vis[k])
        {
            vis[k] = true;
            vis[k ^ 1] = true;
            dfs(edge[k].to);
            ans[ansi++] = k;
        }
	}
}

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

Cpp算法-动态规划

待完成

多阶段过程决策的最优化问题

graph LR
    A --5--> B1
    A --3--> B2
    B1 --1--> C1
    B1 --6--> C2
    B1 --3--> C3
    B2 --8--> C2
    B2 --4--> C4
    C1 --5--> D1
    C1 --6--> D2
    C2 --5--> D1
    C3 --8--> D3
    C4 --3--> D3
    D1 --3--> E
    D2 --4--> E
    D3 --3--> E

!!! tldr “题目及注解”
求上图从 $A$ 到 $E$ 的最短距离

$K$: 阶段

$D(X_I, (X+1)_J)$: 从 $X_I$ 到 $(X+1)_J$ 的距离

$F_K(X_I)$: $K$ 阶段下 $X_I$ 到终点 $E$ 的最短距离

倒推:
$$
K=4\qquad F_4(D_1)=3\qquad F_4(D_2)=4\qquad F_4(D_3)=3
$$
$$
K=5\qquad F_3(C_1)=min(D(C_1,D_1)+F_4(D_1),D(C_1,D_2)+F_4(D_2))=min(5+3,6+4)=8
F_3(C_2)
$$

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

Cpp算法-图论-Dijkstra

说明

n, m点数、边数

G[][]邻接矩阵存图

dist[]路径长度

pre[]路径

make()建图

实现

const int maxn = 10010;
int n, m, G[maxn][maxn], dist[maxn], pre[maxn], s;

void make()
{
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            G[i][j] = INT_MAX;
    for (int i = 1; i <= n; ++i) G[i][i] = 0;
    for (int i = 1; i <= m; ++i)
    {
        int from, to, w;
        scanf("%d %d %d", &from, &to, &w);
        G[from][to] = w;
    }
    return;
}

void Dijkstra()
{
    int k, min;
    bool p[maxn];
    for (int i = 1; i <= n; ++i)
    {
        p[i] = false;
        if (i != s)
        {
            dist[i] = G[s][i];
            pre[i]  = s;
        }
    }
    dist[s] = 0; p[s] = true;
    for (int i = 1; i <= n - 1; ++i)
    {
        min = INT_MAX; k = 0;
        for (int j = 1; j <= n; ++j)
        {
            if (!p[j] && dist[j] < min)
            {
                min = dist[j];
                k = j;
            }
        }
        if (k == 0) return;
        p[k] = true;
        for (int j = 1; j <= n; ++j)
        {
            if (!p[j] && G[k][j] != INT_MAX && dist[j] > dist[k] + G[k][j])
            {
                dist[j] = dist[k] + G[k][j];
                pre[j] = k;
            }
        }
    }
    return;
}

堆优化(链式前向星)

struct Edge
{
    int to, nxt, t;
}edge[maxm << 1];
int head[maxn], cnt;
void add(int a, int b, int t)
{
    edge[++cnt].to  = b;
    edge[cnt].nxt = head[a];
    edge[cnt].t   = t;
    head[a]       = cnt;
}

struct heap
{
    int u, d;
    bool operator < (const heap& a) const
    {
        return d > a.d;
    }
};

void Dijkstra()
{
    priority_queue<heap> q;
    for (int i = 0; i <= n; ++i) dist[i] = INF;
    dist[1] = 0;
    q.push((heap){1, 0});
    while (!q.empty())
    {
        heap top = q.top();
        q.pop();
        int tx = top.u;
        int td = top.d;
        if (td != dist[tx]) continue;
        for (int i = head[tx]; i; i = edge[i].nxt)
        {
            int v = edge[i].to;
            if (dist[v] > dist[tx] + edge[i].t)
            {
                dist[v] = dist[tx] + edge[i].t;
                dy[v] = i; 
                dx[v] = tx;    //记录路径
                q.push((heap){v, dist[v]});
            }
        }
    }
}

路径

int q = n, p[maxm];
while (q != 1)
{
    p[++tot] = dy[q];
    q = dx[q];
}

2019-01-10发表2020-05-05更新C++算法几秒读完 (大约95个字)

Cpp算法-树状数组

树状数组

模板：洛谷P3374

说明

tree[]树状数组

lowbit(int)神奇的函数

add(int x, int k)第 $x$ 个数加上 $k$

sum(int x)前 $x$ 个数的和

实现

int tree[2000010];

int lowbit(int k)
{
    return k & -k;
}

void add(int x, int k)
{
    while (x <= n)
    {
        tree[x] += k;
        x += lowbit(x);
    }
}

int sum(int x)
{
    int ans = 0;
    while (x != 0)
    {
        ans += tree[x];
        x -= lowbit(x);
    }
    return ans;
}

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