2017-07-28 • 于 2017 阅读

day6

cyclic
这个题直接模拟，先把k%一下防止过大
然后直接做就行了

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#define ll long long
using namespace std;
char a[19999],A[19999];
int n;
int main()
{
	freopen("cyclic.in","r",stdin);
	freopen("cyclic.out","w",stdout);
	cin>>a;
	scanf("%d",&n);
	while(n--)
	{
		int k,x,y;
		scanf("%d%d%d",&x,&y,&k);
		k%=y-x+1;
		for(int i=x-1;i<=y-1;i++)
		A[i]=a[((i-k)>=(x-1))?(i-k):(i-k+y-x+1)]; 
		for(int i=x-1;i<=y-1;i++)
		a[i]=A[i];
	}
	cout<<a;
}

book 这里写图片描述
这个题是最难的
其实是一个贪心，很简单的贪心，但很难想
别人讲也听不懂，我就没搞懂
因为已经读过的书必须放到上面，所以搬后面的书时，必须搬之前看过的书
不如把你下一次要看的书放倒最前面，这样就能搬最小代价的书了。

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#define ll long long
using namespace std;
int v[19999],w[19999],vis[1999],f[19999],s,ans,t,j;
int n,m;
int main()
{
	freopen("book.in","r",stdin);
	freopen("book.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	scanf("%d",&w[i]);
	for(int i=1;i<=m;i++)
	scanf("%d",&v[i]);
	for(int i=1;i<=m;i++)
	{
		if(!vis[v[i]])
		{
			f[++t]=v[i];
			vis[v[i]]=1;
		}
	}
	for(int i=1;i<=m;i++)
	{
		j=1;s=0;
		while(v[i]!=f[j])
		{
			s+=w[f[j]];
			j++;
		}
		ans+=s;
		int z=f[j];
		for(int k=j;k>=2;k--)
		f[k]=f[k-1];
		f[1]=z;
	}
	printf("%d",ans);
}

set
这里写图片描述
这是一个树形dp题
很容易得出
一个父节点的方案数可以由子节点组合出来出,而子节点的方案数为，选子节点f[j]，不选子节点 1
总数就是f[j]+1
即 f[fa]=(f[j]+1) (f[j]+1) (f[j]+1) 。。。。(f[j]+1) j是子节点
因此可以枚举一个最小的点，当做父节点，找以他为最小值能有多少种方案，还要记得不能重复
有权值相同的点，所以有可能统计两次，又因为是从小到大枚举的，之前在小的结点时已经搜到，只要父节点的编号>子节点就不会重复了；

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#define p 1000000007
#define ll long long
using namespace std;
int D,n,l,r,t;
int v[2999],w[2999];
ll dp[19999],ans; 
int head[2999],nex[199999],tot,to[199999];
int add(int x,int y)
{
	tot++;
	nex[tot]=head[x];
	to[tot]=y;
	head[x]=tot;
}
int dfs(int x,int fa){
	dp[x]=1;
	for(int i=head[x];i;i=nex[i])
	{
		int tmp=to[i];
		if(t>tmp&&v[tmp]==l) continue;
		if((tmp!=fa&&v[tmp]>=l&&v[tmp]<=r))
		{
			dfs(tmp,x);
		dp[x]=1ll*dp[x]*(dp[tmp]+1)%p;
		}
	}
}
int main()
{
	scanf("%d%d",&D,&n);
	for(int i=1;i<=n;i++)
	scanf("%d",&v[i]);
	for(int i=1;i<n;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		add(x,y);
		add(y,x);
	}
	for(int i=1;i<=n;i++)
	{
		l=v[i];
		r=v[i]+D;
		t=i;
		dfs(i,i);
		(ans+=dp[i])%=p;
	}
	printf("%lld",ans);
}

wspl09876

day6

关于二维偏序的题

day5