算法竞赛 – AnshanSniper's blog

由数据范围反推时间复杂度及算法内容

2020年3月16日2020年3月16日由 AnshanSniper

一般题目的时间限制为1s / 2s，在这种情况下C++代码中的操作次数控制在1e7为最佳。
下面给出在不同数据范围下所反推出的对应时间复杂度及算法内容：

n≤30 => 指数级别 => dfs+剪枝，状压dp
n≤1e2 => O(n^3) => floyd，dp
n≤1e3 => O(n^2) / O(n^2logn) => dp，二分
n≤1e4 => O(n∗√n) => 块状链表
n≤1e5 => O(nlogn) => 各种sort，线段树、树状数组、set/map、heap、dijkstra+heap、spfa、求凸包、求半平面交、二分
n≤1e6 => O(n) / 常数较小的 O(nlogn) => hash、双指针扫描、kmp、AC自动机、sort、树状数组、heap、dijkstra、spfa
n≤1e7 => O(n) => 双指针扫描、kmp、AC自动机、线性筛素数
n≤1e9 => O(√n) => 判断质数
n≤1e18 => O(logn) => 最大公约数

最小费用最大流

2020年3月16日2020年3月15日由 AnshanSniper

bool spfa(int s, int t)
{
	queue<int> q;
	for (int i = 0; i < N; i++) 
	{
		dis[i] = INF; 
		vis[i] = false;  
		pre[i] = -1; 
	}  
	dis[s] = 0; 
	vis[s] = true; 
	q.push(s);  
	while (!q.empty())
	{
		int u = q.front(); 
		q.pop(); 
		vis[u] = false;  
		for (int i = head[u]; i != -1; i = edge[i].next)
		{
			int v = edge[i].to;    
			if (edge[i].cap > edge[i].flow && dis[v] > dis[u] + edge[i].cost)
			{ 
				dis[v] = dis[u] + edge[i].cost;      
				pre[v] = i;    
				if (!vis[v])
				{
					vis[v] = true;    
					q.push(v);
				}
			}
		}
	}  
	if (pre[t] == -1)   
		return false; 
	else  
		return true;
}

int minCostMaxflow(int s, int t, int &cost) //返回的是⼤大流，cost 存的是⼩小费⽤用 
{ 
	int flow = 0;  
	cost = 0;  
	while (spfa(s, t))
	{    
		int Min = INF;  
		for (int i = pre[t]; i != -1; i = pre[edge[i ^ 1].to]) 
		{  
			if (Min > edge[i].cap - edge[i].flow) 
				Min = edge[i].cap - edge[i].flow;  
		}   
		for (int i = pre[t]; i != -1; i = pre[edge[i ^ 1].to])
		{       
			edge[i].flow += Min;    
			edge[i ^ 1].flow -= Min;   
			cost += edge[i].cost * Min; 
		}  
		flow += Min; 
	} 
	return flow; 
}

最小表示法

2020年3月16日2020年3月15日由 AnshanSniper

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;

const int maxn = 1000010;
char a[maxn];

int Getmin(char a[])
{
	int n = strlen(a);
	int i = 0, j = 1, k = 0, t;
	while (i < n&&j < n&&k < n)
	{
		t = a[(i + k) % n] - a[(j + k) % n];
		if (!t)
			k++;
		else
		{
			if (t > 0)
				i += k + 1;
			else
				j += k + 1;
			if (i == j)
				j++;
			k = 0;
		}
	}
	return min(i, j);
}

int main()
{
	int n;
	cin >> n;
	for (int i = 0; i < n; ++i)
	{
		cin >> a[i];
	}
	cout << Getmin(a);
	return 0;
}

最大流

2020年3月16日2020年3月15日由 AnshanSniper

const int MAXN = 2010;//点数的最大值
const int MAXM = 1200010;//边数的最大值
const int INF = 0x3f3f3f3f;

struct Edge
{
	int to, next, cap, flow;
}edge[MAXM];

int tol;
int head[MAXN];

void init()
{
	tol = 2;
	memset(head, -1, sizeof(head));
}

void addedge(int u, int v, int w, int rw = 0)
{
	edge[tol].to = v;
	edge[tol].cap = w;
	edge[tol].flow = 0;
	edge[tol].next = head[u];
	head[u] = tol++;
	edge[tol].to = u;
	edge[tol].cap = rw;
	edge[tol].flow = 0;
	edge[tol].next = head[v];
	head[v] = tol++;
}

int Q[MAXN];
int dep[MAXN], cur[MAXN], sta[MAXN];

bool bfs(int s, int t, int n)
{
	int front = 0, tail = 0;
	memset(dep, -1, sizeof(dep[0]) * (n + 1));
	dep[s] = 0;
	Q[tail++] = s;
	while (front < tail)
	{
		int u = Q[front++];
		for (int i = head[u]; i != -1; i = edge[i].next)
		{
			int v = edge[i].to;
			if (edge[i].cap > edge[i].flow && dep[v] == -1)
			{
				dep[v] = dep[u] + 1; 
				if (v == t) 
					return true; 
				Q[tail++] = v;
			}
		}
	}   
	return false;
}

int dinic(int s, int t, int n)
{
	int maxflow = 0; 
	while (bfs(s, t, n))
	{
		for (int i = 0; i < n; i++) 
			cur[i] = head[i]; 
		int u = s, tail = 0; 
		while (cur[s] != -1) 
		{
			if (u == t)
			{
				int tp = INF; 
				for (int i = tail - 1; i >= 0; i--)   
					tp = min(tp, edge[sta[i]].cap - edge[sta[i]].flow);  
				maxflow += tp; 
				for (int i = tail - 1; i >= 0; i--)
				{
					edge[sta[i]].flow += tp;    
					edge[sta[i] ^ 1].flow -= tp;    
					if (edge[sta[i]].cap - edge[sta[i]].flow == 0)
						tail = i; 
				}
				u = edge[sta[tail] ^ 1].to;
			}
			else if (cur[u] != -1 && edge[cur[u]].cap > edge[cur[u]].flow && dep[u] + 1 == dep[edge[cur[u]].to])
			{
				sta[tail++] = cur[u]; 
				u = edge[cur[u]].to; 
			}
			else 
			{
				while (u != s && cur[u] == -1) 
					u = edge[sta[--tail] ^ 1].to;   
				cur[u] = edge[cur[u]].next;
			}
		}
	}
	return maxflow;
}

线段树

2020年3月16日2020年3月15日由 AnshanSniper

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;

const int MAX_N = 10010;
int s[4 * MAX_N], col[4 * MAX_N];

void up(int p) 
{
	s[p] = s[p * 2] + s[p * 2 + 1];
}

void down(int p, int l, int r) 
{
	if (col[p]) 
	{
		int mid = (l + r) / 2;
		s[p * 2] += col[p] * (mid - l + 1);
		s[p * 2 + 1] += col[p] * (r - mid);
		col[p * 2] += col[p];
		col[p * 2 + 1] += col[p];
		col[p] = 0;
	}
}

void modify(int p, int l, int r, int x, int c) 
{
	if (l == r) 
	{
		s[p] += c;
		return;
	}
	int mid = (l + r) / 2;
	if (x <= mid) 
		modify(p * 2, l, mid, x, c);
	else 
		modify(p * 2 + 1, mid + 1, r, x, c);
	up(p);
}

void modify(int p, int l, int r, int x, int y, int c) 
{
	if (x <= l && r <= y) 
	{
		s[p] += (r - l + 1) * c;
		col[p] += c;
		return;
	}
	down(p, l, r);
	int mid = (l + r) / 2;
	if (x <= mid) 
		modify(p * 2, l, mid, x, y, c);
	if (y > mid) 
		modify(p * 2 + 1, mid + 1, r, x, y, c);
	up(p);
}

int query(int p, int l, int r, int x, int y) 
{
	if (x <= l && r <= y)
		return s[p];
	down(p, l, r);
	int mid = (l + r) / 2, res = 0;
	if (x <= mid)
		res += query(p * 2, l, mid, x, y);
	if (y > mid)
		res += query(p * 2 + 1, mid + 1, r, x, y);
	return res;
}

void init()
{
	memset(s, 0, sizeof(s));
	memset(col, 0, sizeof(col));
}

int main() 
{
	int n;
	cin >> n;
	for (int i = 1; i <= n; ++i) 
	{
		int d;
		cin >> d;
		modify(1, 1, n, i, i, d);
	}
	int q;
	cin >> q;
	while (q--)
	{
		int d, x, y, c;
		cin >> d >> x >> y;
		if (d == 0) 
		{
			cin >> c;
			modify(1, 1, n, x, y, c);
		}
		else
			cout<< query(1, 1, n, x, y);
	}
	return 0;
}

树状数组

2020年3月16日2020年3月15日由 AnshanSniper

#include<iostream>
#include<string> 
#include<algorithm>
using namespace std;

const int MAX_N = 10010;
int C[MAX_N];
int n;

int lowbit(int x)
{
	return x & (-x);
}
int getsum(int x)
{
	int res = 0;
	for (; x; x -= lowbit(x))
	{
		res += C[x];
	}
	return res;
}

void change(int x, int c)
{
	for (; x <= n; x += lowbit(x))
	{
		C[x] += c;
	}
}

int main()
{
	cin >> n;
	for (int i = 1; i <= n; ++i)
	{
		int d;
		cin >> d;
		change(i, d);
	}
	for (int i = 1; i <= n; ++i)
	{
		cout << getsum(i) << " ";
	}
	return 0;
}

欧拉筛

2020年3月16日2020年3月15日由 AnshanSniper

求最小质因数

const int LIM = 1e6+10;
int miniFactor[LIM],prime[LIM / 3];
int primepos;

void euler() {
    int tmp;
    for (int i = 2; i < LIM; i++) {
        if (!miniFactor[i]) prime[primepos++] = i, miniFactor[i] = i;
        for (int j = 0; (tmp = i * prime[j]) < LIM; j++) {
            miniFactor[tmp] = prime[j];
            if (!(i % prime[j])) break;
        }
    }
}

void solve(){
    int n;
    scanf("%d", &n);
    printf("%d\n", miniFactor[n]);
};

int main(){
    euler();
    int t;
    cin>>t;
    while(t--)
        solve();
    return 0;
}

快速读入

2020年3月16日2020年3月15日由 AnshanSniper

inline int read(){
    int s = 0, w = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9'){
        if(ch == '-')
            w = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
        s = s * 10 + ch - '0', ch = getchar();
    return s * w;
}

矩阵快速幂

2020年3月16日2020年3月15日由 AnshanSniper

const int mod = 1e9 + 7;
struct mat
{
	ll m[3][3];
	mat()
	{
		for (int i = 0; i < 3; i++)
			for (int j = 0; j < 3; j++)
				m[i][j] = 0;
	}
};

mat mul(mat a, mat b)
{
	mat temp;
	for (int i = 0; i < 3; i++)
		for (int j = 0; j < 3; j++)
			for (int k = 0; k < 3; k++)
				temp.m[i][j] = (temp.m[i][j] + a.m[i][k] * b.m[k][j]) % mod;
	return temp;
}

mat qp(mat a, ll b)
{
	mat ans;
	for (int i = 0; i < 3; i++)
		ans.m[i][i] = 1;
	while (b)
	{
		if (b & 1)
			ans = mul(ans, a);
		a = mul(a, a);
		b >>= 1;
	}
	return ans;
}

进制转换

2020年3月16日2020年3月15日由 AnshanSniper

const int MAXN = 1e4+10;

char hashch[MAXN];
int hashnum[MAXN];

void init()
{
    char ch;
    for(int i=0;i<62;i++){
        if(i<10)                ch=i+'0';
        else if(i>=10&&i<36)    ch='A'+i-10;
        else                    ch='a'+i-36;
        hashch[i]=ch;
        hashnum[ch]=i;
    }
}

string change(int m,int n,string str)
{
    bool flag;
    string ans="";
    int tmp,quotient,remainder;
    while(true)
    {
        flag=false;
        remainder=0;
        string div="";
        int len=str.length();
        for(int i=0;i<len;i++){
            tmp=remainder*m+hashnum[str[i]];
            quotient=tmp/n;
            remainder=tmp%n;
            if(flag){
                div+=hashch[quotient];
            }
            else{
                if(quotient!=0){
                    flag=true;
                    div+=hashch[quotient];
                }
            }
        }
        ans=hashch[remainder]+ans;
        str=div;
        if(flag==false) break;
    }
    return ans;
}