不熟练的模版集合

逆序对

#include<bits/stdc++.h>
using namespace std;
int n,a[1000010],b[1000010];
long long ans;
void merge(int l,int r)
{
	if(l>=r)return;
	int mid=(l+r)>>1;
	merge(l,mid);
	merge(mid+1,r);
	int i=l,k=l,j=mid+1;
	while(i<=mid&&j<=r)
	{
		if(a[i]<=a[j]) b[k++]=a[i++];
		else
		{
			b[k++]=a[j++];
			ans+=mid-i+1;
		}
	}
	while(i<=mid) b[k++]=a[i++];
	while(j<=r) b[k++]=a[j++];
	for(int i=l;i<=r;i++) a[i]=b[i];
}
int main()
{
	//freopen("deseq.in","r",stdin);
	//freopen("deseq.out","w",stdout);
	std::ios::sync_with_stdio(0);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	merge(1,n);
	cout<<ans;
	return 0;
}

固定终点最长路

#include<bits/stdc++.h>
using namespace std;
int n,m,end,e[1010][1010];
int f[1010],pth[1010];
bool vis[1010];
int dfs(int u)
{
	if(vis[u]) return f[u];
	vis[u]=1;
	for(int i=1;i<=n;i++)
	{
		if(e[i][u]!=-1)
		{
			if(f[u]<dfs(i)+e[i][u])
			{
				f[u]=dfs(i)+e[i][u];
				pth[u]=i;
			}
		}
	}
	return f[u];
}
void print_path(int u)
{
	printf("%d",u);
	while(pth[u]!=-1)
	{
		printf("->%d",pth[u]);
		u=pth[u];
	}
}
int main()
{
	scanf("%d%d%d",&n,&m,&end);
	memset(pth,-1,sizeof pth);
	memset(e,-1,sizeof e);
	for(int i=1;i<=m;i++)
	{
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		e[u][v]=w;
	}
	printf("%d\n",dfs(end));
	print_path(end);
	return 0;
}
/*
7 8 7
1 3 2
2 4 3
4 3 2
3 5 5
4 6 4
6 7 5
5 6 1
5 7 3
*/
/*
answer:
16
7->6->5->3->4->2
*/