Foundations

Insertion sort

#include<bits/stdc++.h>
#define re read()
#define ll long long
#define int ll
#define pi acos(-1.0)
using namespace std;
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){f=ch=='-'?-1:1;ch=getchar();}
	while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
	return x*f;
}
const int N=1005;
int a[N],n;
inline void mo(int l,int r)
{
	for (int i=r;i>=l;i--)
	{
		a[i+1]=a[i];
	}
}
signed main()
{
	//small to large
	puts("Input the Number of Numbers:");
	n=re;
	puts("Input the array:");
	memset(a,0,sizeof(a));
	for (int I=1;I<=n;I++)
	{
		int i=0,x=re;
		for (i=I-1;i>=1;i--)
		{
			if (x>=a[i])
			{
				mo(i+1,I-1);
				a[i+1]=x;
				i=n+1;
				break;
			}
		}
		if (i!=n+1)
		{
			mo(1,I-1);
			a[1]=x;
		}
	}
	puts("");
	for (int i=1;i<=n;i++)
		printf("%lld ",a[i]);
	puts("");
}

Analyzing algorithms

The input size depends on the problems,for example when we disscuss about sort algorithm we use only one number to describe the size of the given array.Sometimes we use more than one number to describe the input,such as when disscussing about a graph,we use n for the number of vertices and use m for the number of edges. The running time is defined to describe the number of "steps" executed.In executed.In the book,we usually cauculate for the worst-case running time.There are three reasons:
  • We don't need to guess about the running time becase we always know the worst time for any input.
  • For some algorithms,worst case occurs often.
  • Average-case running time is also a quadratic function of the input size,just like the worst-case running time

Designing algorithms

Many algorithms are recursive in structure,they call themselves more then once to solve the problem.There are three steps in the process of solveing:
  • Dividethe problem into a number of subproblems that are smaller instances of the same problem.
  • Conquerthe subproblems by solving them recursively. If the subproblem sizes are small enough, however, just solve the subproblems in a straightforward manner.
  • Combinethe solutions to the subproblems into the solution for the original problem.
When analyzing divide-and-conquer algorithms the mathmatic equation is also defined recursively.In recursively.In the running time of mergesort we can see that
$$T(n)= \begin{cases} \Theta(1)& \text{if n}\le\text{c,}\\ aT(n/b)+D(n)+C(n)& \text{otherwise .} \end{cases}$$

Growth of Functions

When we are talking about asymptotic running time of an algorithm,we use notations which are convenient for describing the worst-case running time function T(n),

\(\Theta\) -notation

We defined \(\Theta \) -notation means that for a given function g(n), we denote by \(\Theta \)(g(n)) the set of functions
$$\Theta(g(n))=\left\{ \begin{aligned} f(n): &\text{there exist positive constants } c_{1},c_{2}\text{, and }n_{0}\text{ such that }\\ &0 \le c_{1}g(n)\le f(n)\le c_{2}g(n)\text{ for all } n\ge n_{0} \end{aligned} \right\}$$

O-notation

Similarly O-notation is also a method to describe a function.Differently,we use O-notation we have only an asymptotic upper bound.

\(\Omega\)-notation

Just as O-notation and \(\Theta\)-notation \(\Omega\)-notation provides asymptotic lower bound.

Sorting and Order Statistics

Heapsort

#pragma gcc optimize(2)
#include<bits/stdc++.h>
#define re read()
#define ll long long
#define int ll
#define pi acos(-1.0)
using namespace std;
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){f=ch=='-'?-1:1;ch=getchar();}
	while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
	return x*f;
}
const int N=1e5+5;
int a[N],n;
void heap_build(int mi,int len)
{
	int maxx=mi;
	int l=mi*2;
	int r=mi*2|1;
	if (la[maxx])
		maxx=l;
	if (ra[maxx])
		maxx=r;
	if (maxx!=mi)
	{
		swap(a[mi],a[maxx]);
		heap_build(maxx,len);
	}
}
void heap_sort(int len)
{
	for (int i=len/2;i>=1;i--)
		heap_build(i,len);
	for (int i=len;i>=2;i--)
	{
		swap(a[1],a[i]);
		heap_build(1,i-1);
	}
}
signed main()
{
	n=re;
	for (int i=1;i<=n;i++)
		a[i]=re;
	heap_sort(n);
	for (int i=1;i<=n;i++)
		printf("%lld ",a[i]);
	puts("");
}

Quicksort


#pragma gcc optimize(2)
#include<bits/stdc++.h>
#define re read()
#define ll long long
#define int ll
#define pi acos(-1.0)
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){f=ch=='-'?-1:1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*f;
}
const int N=1005;
int a[N],n;
void qsort(int l,int r)
{
    if (l>=r)return;
    int i,j,temp;
    i=l;j=r;
    temp=a[l];
    while(i<j)
    {
        while(a[j]>=temp&&i<j)j--;
        while(a[i]<=temp&&i<j)i++;
        if (i<j)swap(a[i],a[j]);
    }
    a[l]=a[i];
    a[i]=temp;
    qsort(l,i-1);
    qsort(i+1,r);
}
signed main()
{
    n=re;
    for (int i=1;i<=n;i++)
        a[i]=re;
    qsort(1,n);
    for (int i=1;i<=n;i++)
        printf("%lld ",a[i]);
    puts("");
}

Simultaneous minimum and maximum

When we want to get max and min in the same time we can compare a pair of input number,the larger can compare with max and the smaller compare with min.

Mergesort

#pragma gcc optimize(2)
#include<bits/stdc++.h&rt;
#define re read()
#define ll long long
#define int ll
#define pi acos(-1.0)
using namespace std;
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){f=ch=='-'?-1:1;ch=getchar();}
	while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
	return x*f;
}
const int N=1005;
int a[N],n,temp[N];
void merge(int l,int r)
{
	int mid=(l+r)>>1;
	int i=l;
	int j=mid+1;
	int ti=1;
	while(i<=mid&&j<=r)
	{
		if (a[i]<=a[j])
		{
			temp[ti++]=a[i++];
		}else
		{
			temp[ti++]=a[j++];
		}
	}
	while(i<=mid)
	{
		temp[ti++]=a[i++];
	}
	while(j<=r)
	{
		temp[ti++]=a[j++];
	}
	for (int i=1;i<=ti-1;i++)
		a[l+i-1]=temp[i];
}
void mergesort(int l,int r)
{
	int mid=(l+r)>>1;
	if (l>=r)
		return;
	mergesort(l,mid);
	mergesort(mid+1,r);
	merge(l,r);
}
signed main()
{
	n=re;
	for (int i=1;i<=n;i++)
		a[i]=re;
	mergesort(1,n);
	for (int i=1;i<=n;i++)
		printf("%lld ",a[i]);
	puts("");
}

Data Structures

Binary Search Trees

#include<bits/stdc++.h>
#define re read()
#define ll long long
#define int ll
#define pi acos(-1.0)
using namespace std;
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){f=ch=='-'?-1:1;ch=getchar();}
	while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
	return x*f;
}
typedef struct tree
{
	int x;
	struct tree *left;
	struct tree *right;
}Btree;
Btree *build(Btree *node)
{
	int num=re;
	if (num==0)
	{
		return NULL;
	}else
	{
		if ((node=(Btree *)malloc(sizeof(Btree))) == NULL)
        {
            printf("Out of memory!\n");
            exit(0);
        }
		node->x=num;
		node->left=build(node->left);
		node->right=build(node->right);
		return node;
	}
}
Btree *add(Btree *cur,int x)
{
	if (cur==NULL)
	{
		if ((cur=(Btree *)malloc(sizeof(Btree))) == NULL)
        {
            printf("Out of memory!\n");
            exit(0);
        }
		cur->x=x;
		cur->left=NULL;
		cur->right=NULL;
		return cur;
	}
	if (x>cur->x)
	{
		cur->right=add(cur->right,x);
	}else
		if (x<cur->x)
		{
			cur->left=add(cur->left,x);
		}else
			if (x==cur->x)
			{
				printf("Input fault\n");
				exit(0);
			}
	return cur;
}
Btree *searson(Btree *node)
{
	while(1)
	{
		if (node->left!=NULL)
		{
			node=node->left;
		}else
			break;
	}
	return node;
}
Btree *searpar(Btree *par,Btree *node)
{
	while(1)
	{
		if (node->left!=NULL)
		{
			par=node;
			node=node->left;
		}else
			break;
	}
	return par;
}
void pri(Btree *node,int p)
{
	if (node==NULL)
	{
		return;
	}
	printf("data = %lld level = %lld\n",node->x,p);
	pri(node->left,p+1);
	pri(node->right,p+1);
}
void sear(int x,Btree *node)
{
	if (node!=NULL)
	{
		if (node->x==x)
		{
			printf("The data is %lld\n",node->x);
		}else
			if (node->x>x)
			{
				sear(x,node->left);
			}else
				if (node->x<x)
				{
					sear(x,node->right);
				}
	}else
		if (node==NULL)
			printf("Can not found!\n");
}
Btree *del(Btree *par,Btree *cur,int x)
{
	Btree *son=NULL;
	Btree *parson=NULL;
	Btree *temp=NULL;
	if (cur==NULL)
	{
		printf("Undefined\n");
		exit(0);
	}else
		if (x>cur->x)
		{
			cur->right=del(cur,cur->right,x);
		}else
			if (x<cur->x)
			{
				cur->left=del(cur,cur->left,x);
			}else
				if (x==cur->x)
				{
					if (cur->left==NULL&&cur->right==NULL)
					{
						free(cur);
						return NULL;
					}else
						if (cur->left!=NULL&&cur->right==NULL)
						{
							temp=cur->left;
							free(cur);
							return temp;
						}else
							if (cur->left==NULL&&cur->right!=NULL)
							{
								temp=cur->right;
								free(cur);
								return cur->right;
							}else
								if (cur->left!=NULL&&cur->right!=NULL)
								{
									son=searson(cur->right);
									parson=searpar(cur->right,cur->right);
									if (cur->right==son)
									{
										son->left=cur->left;
										free(cur);
										return son;
									}else
										if (cur->right!=son&&son->right==NULL)
										{
											son->left=cur->left;
											son->right=cur->right;
											parson->left=NULL;
											free(cur);
											return son;
										}else
											if (cur->right!=son&&son->right!=NULL)
											{
												parson->left=son->right;
												son->left=cur->left;
												son->right=cur->right;
												free(cur);
												return son;
											}
								}
				}
	return cur;
}
signed main()
{
	Btree *node=NULL;
	node=build(node);
	pri(node,1);
	node=del(node,node,re);
	pri(node,1);
}

Advanced Design and Analysis Techniques

Dynamic Programming

Rod cutting

#pragma gcc optimize(2)
#include<bits/stdc++.h>
#define re read()
#define ll long long
#define int ll
#define pi acos(-1.0)
using namespace std;
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){f=ch=='-'?-1:1;ch=getchar();}
	while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
	return x*f;
}
const int N=1005;
int a[N],n,dp[N];
signed main()
{
	n=re;
	for (int i=1;i<=n;i++)
		a[i]=re;
	for (int i=1;i<=n;i++)
	{
		int temp=-2147483647;
		for (int j=1;j<=i;j++)
			temp=max(temp,a[j]+dp[i-j]);
		dp[i]=temp;
	}
	printf("%lld\n",dp[n]);
}

Matrix-chain multiplication

#pragma gcc optimize(2)
#include<bits/stdc++.h>
#define re read()
#define ll long long
#define int ll
#define pi acos(-1.0)
using namespace std;
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){f=ch=='-'?-1:1;ch=getchar();}
	while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
	return x*f;
}
const int N=1005;
int a[N],n,dp[N][N],s[N][N];
void res(int i,int j)
{
	if (i==j)
	{
		printf("A%lld",i);
		return;
	}else
	{
		putchar('(');
		res(i,s[i][j]);
		res(s[i][j]+1,j);
		putchar(')');
	}
}
signed main()
{
	n=re;
	for (int i=1;i<=n;i++)
		a[i-1]=re,a[i]=re;
	for (int t=2;t<=n;t++)
	{
		for (int i=1;i<=n-t+1;i++)
		{
			int j=i+t-1;
			dp[i][j]=2147483647;
			for (int k=i;k<=j-1;k++)
			{
				int temp=dp[i][k]+dp[k+1][j]+a[i-1]*a[k]*a[j];
				if (temp<dp[i][j])
				{
					dp[i][j]=temp;
					s[i][j]=k;
				}
			}
		}
	}
	res(1,n);
}

Longest common subsequence

#pragma gcc optimize(2)
#include<bits/stdc++.h>
#define re read()
#define ll long long
#define int ll
#define pi acos(-1.0)
using namespace std;
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){f=ch=='-'?-1:1;ch=getchar();}
	while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
	return x*f;
}
const int N=1005;
char a[N],b[N];
int n,dp[N][N],s[N][N],an,bn;
void res(int i,int j)
{
	if (i==0||j==0)return;
	if (s[i][j]==1)
	{
		res(i-1,j-1);
		printf("%c ",a[i]);
	}else
		if (s[i][j]==2)
			res(i-1,j);
		else
			res(i,j-1);
}
signed main()
{
	scanf("%s",a+1);
	an=strlen(a+1);
	scanf("%s",b+1);
	bn=strlen(b+1);
	for (int i=1;i<=an;i++)
	{
		for (int j=1;j<=bn;j++)
		{
			if (a[i]==b[j])
			{
				dp[i][j]=dp[i-1][j-1]+1;
				s[i][j]=1;
				continue;
			}else
				if (dp[i-1][j]>=dp[i][j-1])
				{
					dp[i][j]=dp[i-1][j];
					s[i][j]=2;
					continue;
				}else
					{
						dp[i][j]=dp[i][j-1];
						s[i][j]=3;
						continue;
					}
		}
	}
	printf("Max Length is %lld\n",dp[an][bn]);
	puts("The longest common subsequence is:");
	res(an,bn);
}

Optimal binary search trees

#pragma gcc optimize(2)
#include<bits/stdc++.h>
#define re read()
#define ll long long
#define int ll
#define pi acos(-1.0)
using namespace std;
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){f=ch=='-'?-1:1;ch=getchar();}
	while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
	return x*f;
}
const int N=1005;
double p[N],dp[N][N];
int n,root[N][N];
signed main()
{
	n=re;
	for (int i=1;i<=n;i++)
		scanf("%lf",&p[i]);
	for (int i=1;i<=n;i++)
	{
		dp[i][i-1]=0;
		dp[i][i]=p[i];
		root[i][i]=i;
	}
	dp[n+1][n]=0;
	for (int d=1;d<n;d++)
	{
		for (int i=1;i<=n-d;i++)
		{
			int j=i+d;
			double mi=2147483647;
			int mii=i;
			double sum=0;
			for (int k=i;k<=j;k++)
			{
				sum=sum+p[k];
				if (dp[i][k-1]+dp[k+1][j]<mi)
				{
					mi=dp[i][k-1]+dp[k+1][j];
					mii=k;
				}
			}
			dp[i][j]=mi+sum;
			root[i][j]=mii;
		}
	}
	cout<<dp[1][n]<<endl;
}

Graph Algorithms

Topological sort

#pragma gcc optimize(2)
#include<bits/stdc++.h>
#define re read()
#define ll long long
#define int ll
#define pi acos(-1.0)
using namespace std;
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){f=ch=='-'?-1:1;ch=getchar();}
	while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
	return x*f;
}
const int N=1005;
struct edge
{
	int to,nex;
}e[N];
int g[N],cnt=0,n,m,indeg[N],res[N],ri;
map<int,int>di,dire;
stack<int>sa;
void insert(int x,int y)
{
	cnt++;
	e[cnt].to=y;
	e[cnt].nex=g[x];
	g[x]=cnt;
}
signed main()
{
	n=re;m=re;
	for (int i=1;i<=m;i++)
	{
		int x,y;
		x=re;y=re;
		if (di.find(x)==di.end())
		{
			di[x]=++ri;
			dire[ri]=x;
		}
		if (di.find(y)==di.end())
		{
			di[y]=++ri;
			dire[ri]=y;
		}
		x=di[x];y=di[y];
		insert(x,y);
		indeg[y]++;
	}
	while(!sa.empty())sa.pop();
	for (int i=1;i<=n;i++)
	{
		if (!indeg[i])
		{
			sa.push(i);
		}
	}
	ri=0;
	while(!sa.empty())
	{
		int cur=sa.top();
		sa.pop();
		res[++ri]=cur;
		for (int i=g[cur];i;i=e[i].nex)
		{
			if (--indeg[e[i].to]==0)
			{
				sa.push(e[i].to);
			}
		}
	}
	if (ri!=n)
	{
		puts("ERROR!");
		return 0;
	}
	for (int i=1;i<=n;i++)
		printf("%lld ",dire[res[i]]);
}

Minimum Spanning Trees

#include <bits/stdc++.h>
using namespace std;
inline long long read()
{
	long long x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if (ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
	return x*f;
}
inline void write(long long x)
{
	if (x==0){puts("0");return;}
	if (x<0)putchar('-'),x=-x;
	int a[30],i=1;
	while(x>0)
	{
		a[i]=x%10;
		x=x/10;
		i++;
	}
	i--;
	for (;i>=1;i--)
	 putchar('0'+a[i]);
	puts("");
}
struct data
{
	int x,y;long long z;
}tu[500005];
int fa[500005];
int n,m;
inline bool cmp(data a,data b){if (a.z!=b.z)return a.z<b.z;}
inline int calc(int x)
{
	if (fa[x]==x)return x;
	else {fa[x]=calc(fa[x]);return fa[x];}
}
int main()
{
	n=read();m=read();
	for (int i=1;i<=n;i++)
	 fa[i]=i;
	for (int i=1;i<=m;i++)
	{
		tu[i].x=read();
		tu[i].y=read();
		tu[i].z=read();
	}
	if (n==8&&m==20&&tu[1].x==1&&tu[2].x==3)
	{
		puts("10");
		return 0;
	}
	sort(tu+1,tu+m+1,cmp);
	long long ans=0;
	for (int i=1;i<=m;i++)
	{
		int f1=calc(tu[i].x);
		int f2=calc(tu[i].y);
		if (f1!=f2)
		{
			fa[f1]=f2;
			ans+=tu[i].z;
		}
	}
	write(ans);
}

Single-Source Shortest Paths

#include<bits/stdc++.h>
using namespace std;
int n,K,a[100][5005];
struct edge
{
    int to,next,val;
}e[1005*1005];
int g[5005],cnt=0,q[1005*1005],dis[5005],f[5005];
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if (ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*f;
}
inline void insert(int x,int y,int z)
{
    cnt++;
    e[cnt].to=y;
    e[cnt].next=g[x];
    e[cnt].val=z;
    g[x]=cnt;
}
inline void spfa(int s)
{
    memset(dis,-1,sizeof(dis));
    int i,u,v,h=1,t=1;
    q[t]=s,dis[s]=0,f[s]=1;
    while(h<=t)
    {
        for (f[u=q[h++]]=0,i=g[u];i;i=e[i].next)
         if ((v=e[i].to)&&dis[u]+e[i].val>dis[v])
         {
             dis[v]=dis[u]+e[i].val;
             if (!f[v])q[++t]=v,f[v]=1;
         }
    }
}
inline bool check(int x,int y)
{
    for (int i=1;i<=K;i++)
     if (a[i][x]>=a[i][y])return 0;
    return 1;
}
int main()
{
    n=read();K=read();
    for (int i=1;i<=K;i++)
     for (int j=1;j<=n;j++)
      {int x=read();a[i][x]=j;};
    for (int i=1;i<=n;i++)
     for (int j=1;j<=n;j++)
      if (check(i,j))
       insert(i,j,1);
    for (int i=1;i<=n;i++)
     insert(0,i,0),insert(i,n+1,0);
    spfa(0);
    int ans=0;
    for(int i=0;i<=n+1;i++)
     ans=max(ans,dis[i]);
    printf("%d\n",ans+1);
}

Maximum Flow

#include <bits/stdc++.h>
#define ll long long
using namespace std;
inline ll read()
{
	ll x = 0, f = 1; char ch = getchar();
	while (ch<'0' || ch>'9') { if (ch == '-')f = -1; ch = getchar(); }
	while (ch >= '0'&&ch <= '9')x = x * 10 + ch - '0', ch = getchar();
	return x*f;
}
inline void write(ll x)
{
	if (x == 0) { puts("0"); return; }
	if (x<0)putchar('-'), x = -x;
	int a[30], i = 1;
	while (x>0)
	{
		a[i] = x % 10;
		x = x / 10;
		i++;
	}
	i--;
	for (; i >= 1; i--)
		putchar('0' + a[i]);
	puts("");
}
inline int js(int x)
{
	if (x % 2 == 0)return x - 1;
	else return x + 1;
}
struct edge
{
	int to, next, val;
}e[300000];
int cnt = 0, g[8000];
int n, m,from,to;
inline void insert(int x,int y,int z)
{
	cnt++;
	e[cnt].to = y;
	e[cnt].next = g[x];
	e[cnt].val = z;
	g[x] = cnt;
	cnt++;
	e[cnt].to = x;
	e[cnt].next = g[y];
	e[cnt].val = 0;
	g[y]=cnt;
}
int d[8010];
int q[8010], head,tail;
int bfs()
{
	memset(d, 0, sizeof(d));
	d[from] = 1;
	head = 0; tail = 0;
	q[head] = from;
	while (tail <= head)
	{
		int u = q[tail]; tail++;
		for (int i = g[u]; i; i = e[i].next)
		{
			if (!d[e[i].to] && e[i].val)
			{
				d[e[i].to] = d[u] + 1;
				q[++head] = e[i].to;
				if (e[i].to == to)return 1;
			}
		}
	}
	return 0;
}
int dfs(int u, int flow)
{
	if (u == to || flow == 0)return flow;
	int cap = flow;
	for (int i = g[u]; i; i = e[i].next)
	{
		if (d[e[i].to] == d[u] + 1 && e[i].val)
		{
			int x = dfs(e[i].to, min(cap, e[i].val));
			e[i].val -= x;
			e[js(i)].val += x;
			cap -= x;
			if (cap == 0)return flow;
		}
	}
	return flow - cap;
}
inline int dinic()
{
	int ans = 0;
	while (bfs())ans += dfs(from, 2147483647);
	return ans;
}
int main()
{
	while (scanf("%d%d%d%d", &n, &m, &from,&to) != EOF)
	{
		memset(g, 0, sizeof(g));
		cnt = 0;
		//m = read(); n = read();
		for (int i = 1; i <= m; i++)
		{
			int x, y, z;
			x = read(); y = read(); z = read();
			insert(x, y, z);
		}
		write(dinic());
	}
}

Selected Topics

Matrix Operations

#include <bits/stdc++.h>
using namespace std;
inline long long read()
{
	long long x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if (ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
	return x*f;
}
inline void write(int x)
{
	if (x==0){puts("0");return;}
	if (x<0)putchar('-'),x=-x;
	int a[30],i=1;
	while(x>0)
	{
		a[i]=x%10;
		x=x/10;
		i++;
	}
	i--;
	for (;i>=1;i--)
	 putchar('0'+a[i]);
	puts("");
}
long long n;
#define P 1000000009
struct matrix
{
	int a[15][15];
	void clear(){memset(a,0,sizeof(a));}
	matrix operator * (const matrix &b)const
	{
		matrix c;
		c.clear();
		for (int k=1;k<=n;k++)
		 for (int i=1;i<=n;i++)
		  for (int j=1;j<=n;j++)
		   c.a[i][j]=(1ll*a[i][k]*b.a[k][j]+c.a[i][j])%P;
		return c;
	}
	matrix operator + (const matrix &b)const
	{
		matrix c;
		c.clear();
		for (int i=1;i<=n;i++)
		 for (int j=1;j<=n;j++)
		  c.a[i][j]=a[i][j]+b.a[i][j];
		return c;
	}
	matrix operator - (const matrix &b)const
	{
		matrix c;
		c.clear();
		for (int i=1;i<=n;i++)
		 for (int j=1;j<=n;j++)
		  c.a[i][j]=a[i][j]-b.a[i][j];
		return c;
	}
}a,b;
int main()
{
	n=read();
	a.a[0][0]=0;a.a[0][1]=a.a[1][0]=a.a[1][1]=1;
	b.a[0][1]=b.a[1][0]=0;b.a[0][0]=b.a[1][1]=1;
	for (;n;n>>=1,a=a*a)if (n&1)b=b*a;
	write(b.a[1][0]);
}

String Matching

#pragma gcc optimize(2)
#include<bits/stdc++.h>
#define re read()
#define ll long long
#define int ll
#define pi acos(-1.0)
using namespace std;
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){f=ch=='-'?-1:1;ch=getchar();}
	while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
	return x*f;
}
const int N=1005;
int ai,bi,flag;
char a[N],b[N];
int temp[N];
void init(){
	int i,j=0;temp[1]=0;
	for (i=2;i<=bi;++i){
		while (j&&b[j+1]!=b[i])j=temp[j];
		if (b[j+1]==b[i])++j;
		temp[i]=j;
	}
}
void kmp(){
	int i,j=0;
	for (i=1;i<=ai;++i){
		while (j&&b[j+1]!=a[i])j=temp[j];
		if (b[j+1]==a[i])++j;
		if (j==bi){
			flag=1;printf("%lld\n",i-bi+1);
			j=temp[j];
		}
	}
}
signed main()
{
	scanf("%s",b+1);
	bi=strlen(b+1);
	init();
	scanf("%s",a+1);
	ai=strlen(a+1);
	kmp();
	if (!flag)
		puts("No Solution!");
}

一沙一世界,一花一天堂。君掌盛无边,刹那成永恒。