day6

xiaoxiao2021-02-28  23

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); }
转载请注明原文地址: https://www.6miu.com/read-850352.html

最新回复(0)