day6

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#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这里写图片描述
这个题是最难的
其实是一个贪心,很简单的贪心,但很难想
别人讲也听不懂,我就没搞懂
因为已经读过的书必须放到上面,所以搬后面的书时,必须搬之前看过的书
不如把你下一次要看的书放倒最前面,这样就能搬最小代价的书了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#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是子节点
因此可以枚举一个最小的点,当做父节点,找以他为最小值能有多少种方案,还要记得不能重复
有权值相同的点,所以有可能统计两次,又因为是从小到大枚举的,之前在小的结点时已经搜到,只要父节点的编号>子节点就不会重复了;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#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);
}
最近的文章

关于二维偏序的题

简单的逆序对可以用树状数组搞就是插入时,找前面比他大的和插入时弄一个桶,记下有多少个数然后对后面的进行区间求和,这个可以用树状数组搞最后求一个总和1234567891011121314151617181920212223242526272829303132#include&lt;iostream&g …

于  二维偏序 继续阅读
更早的文章

day5

exam简单的贪心注意细节,long long就可以ac了123456789101112131415161718192021222324252627282930313233343536373839#include&lt;cstdio&gt;#include&lt;iostream&gt;#inclu …

于  2017 继续阅读