P4910 帕秋莉的手环

首先你需要明白每一段都可以拼接，因此只需要找到存在“金”的序列个数即可

设 dp 方程 f[i][j]f[i][j] 表示第 ii 个位置有 jj 个“金” 的方案数，发现转移有点重复，于是设 f[i][1/0]f[i][1/0] 表示第 ii 个位置是“金”/"木"的合法方案数目，转移很显然

f[i][0]=f[i−1][1]f[i][1]=f[i−1][0]+f[i−1][1]f[i−1][0]=f[i−2][1]f[i][1]=f[i−1][1]+f[i−2][1]\begin{aligned} f[i][0]&=f[i-1][1]\\ f[i][1]&= f[i-1][0]+f[i-1][1]\\ f[i-1][0]&=f[i-2][1]\\ f[i][1]&=f[i-1][1]+f[i-2][1]\\ \end{aligned}

因此可以看出来是一个求斐波那契

那就好办了,然后考虑这个环的性质

首先能够贡献答案的有两种情况，一种是两段都是“金”（记做 AA ），另外的是一端是“金”(记做 BB )，答案就是 A+2∗BA+2*B 因为我们只算了右边是 “金” 的合法情况，左边是金的是等价的，但是我们没算用 dp 算进去

代码就用一个矩阵快速幂就行了

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include<stdio.h>
#include<iostream>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>

#define int long long

using namespace std;

const int modp=1e9+7;

int n;
int f[5]={0,1,1,2,3};

struct mat{
	int a[3][3];
	mat (int aa=0,int bb=0,int cc=0,int dd=0)
	{
		a[1][1]=aa;
		a[1][2]=bb;
		a[2][1]=cc;
		a[2][2]=dd;
		return ;
	}
};

mat operator *(mat a,mat b)
{
	mat ans;
	int i,j,k;
	for(i=1;i<=2;i++)
	for(j=1;j<=2;j++)
	for(k=1;k<=2;k++)
	{
		ans.a[i][j]=(ans.a[i][j]+a.a[i][k]*b.a[k][j])%modp;
	}
	return ans;
}

int fib(int y)
{
	mat bas=mat(1,1,1,0);
	mat ans=mat(1,0,0,1);
	mat looker=mat(1,0,1,0);
	if(y<=1) return f[y];
	y--;
	while(y)
	{
		if(y&1) ans=ans*bas;
		bas=bas*bas;
		y>>=1;
	}
	looker=looker*ans;
	return looker.a[1][1];
}

signed main()
{
	ios::sync_with_stdio(false);
	register int i,j;
	int t;
	cin>>t;
	while(t--)
	{
		cin>>n;
		cout<<(fib(n)+fib(n-1)*2)%modp<<"\n"; 
	}

	return 0;
}

P4933 大师

题意就是求等差数列的个数

刚开始拿到这道题发现用 f[i][j]f[i][j] 表示以 第 ii 个数结尾差值为 jj 的方案数，然后显然的推出来式子

f[i][j]=∑k=1i−1f[k][a[i]−a[k]]f[i][j]=\sum\limits_{k=1}^{i-1}f[k][a[i]-a[k]]

然后发现有负数，不好处理，用了个map来存

然后调试半个多小时，发现连样例都过不了，输出了一下步骤发现多算了一些值，ans只加增量就过了…就过了

感觉是个恶评题目？

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
#include<stdio.h>
#include<iostream>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>

using namespace std;

const int maxn=20020;
const int modp=998244353;

map <int,int> f[1020];
int a[1020],ans;
int n,m;

int main()
{
	ios::sync_with_stdio(false);
	register int i,j;
	cin>>n;
	for(i=1;i<=n;i++) cin>>a[i];
	for(i=1;i<=n;i++)
	{
		//f[i][0]=1;
		ans++;	
		for(j=1;j<i;j++)
		{
			int looker=f[i][a[i]-a[j]];
			f[i][a[i]-a[j]]=(f[i][a[i]-a[j]]+f[j][(a[i]-a[j])]+1)%modp;
			ans=(ans+f[i][a[i]-a[j]]-looker)%modp;
			//if(f[j][(a[i]-a[j])]==0) ans--;
			//cout<<a[i]-a[j]<<" "<<f[j][(a[i]-a[j])]<<" "<<ans<<endl;
		}
		//c/out<<endl;
		
	}
	cout<<ans<<endl;
	return 0;
}

P5858 「SWTR-03」Golden Sword

比上面两个都更有难度

题意就很毒瘤，花了好多时间才理解

题目的意思一个容量最大为 ω\omega 的桶每次可以从中丢弃不多于 ss 件物品，并且定义物品 kk 的耐久度为 ∑i−1szsz×ak\sum\limits_{i-1}^{sz} sz \times a_k 问 这些总和的最大值

刚开始没看到有负数，心想不就是一个sb单调队列，然后第一个样例秒过，然后看到第二个样例，怀疑人生（

设 f[i][j]f[i][j] 表示为放进去第 ii 原料前锅内有 jj 个颜料的方案数

显然 f[i][j]=max⁡k=j−1j+s−1f[i−1][k]f[i][j]=\max\limits_{k=j-1}^{j+s-1} f[i-1][k] 单个转移是 O(s)O(s) 的

对每个 jj 和 ii 都要这样转移，复杂度O(nωk)O(n\omega k)

考虑优化，对每个 jj 都是一段长度为 ss 的序列并且端点位置变化只有1，那么很容易想到滑动窗口用单调队列优化

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
#include<stdio.h>
#include<iostream>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>

#define int long long

using namespace std;

const int maxn=5510;

int q[maxn*2];
int n,a[maxn]; 
int f[2][maxn];
int m,s;
int mmx[maxn];
int ans;

signed main()
{
	ios::sync_with_stdio(false);
	register int i,j;
	cin>>n>>m>>s;
	for(i=1;i<=n;i++) cin>>a[i];
	int l=1,r=0;
	memset(f,-0x3f,sizeof(f));
	f[0][0]=0;
	for(i=1;i<=n;i++)
	{
		memset(q,0,sizeof(q));
		for(j=0;j<=m;j++) f[i&1][j]=-0x3f3f3f3f3f3f3f3f;
		l=1,r=0;
		for(j=m+1;j;j--)
		{
			while(l<=r&&f[(i-1)&1][q[r]]<=f[(i-1)&1][j-1]) r--;
			while(q[l]>j+s-1&&l<=r) l++;
			q[++r]=j-1;
			f[i&1][j]=f[(i-1)&1][q[l]]+a[i]*j;
		}
	}
	ans=-0x3f3f3f3f3f3f3f3f;
	for(i=0;i<=m;i++) ans=max(ans,f[n&1][i]);
	cout<<ans<<endl;
	return 0;
}

P5664 Emiya 家今天的饭

首先这题要建模

烹饪方法各不相同，实际可以转化成每一行只能选一个

此时我们设出方程f[i][j][k]f[i][j][k] 表示到第 ii 行时候 pospos 位置用了 jj 个其余用了kk 个的方案数

同时，我们设g[i][j]g[i][j] 表示 到 ii 行时选了 jj 个的方案数

不难发现总方案数=到最后一行选了任何多个(不包括 00 )的方案数

以及 可行方案数=总方案数-∑j>kf[i][j][k]\sum\limits_{j>k}{f[i][j][k]}

上面的方程转移可以由三个方面，第一个是这一行没选，第二个是选了一个 pospos 位置的，第三个是选了一个其他位置的

f[i][j][k]+={f[i−1][j][k]f[i−1][j−1][k]∗a[i][pos]f[i−1][j][k−1]∗(sum[i]−a[i][pos])f[i][j][k]+=\begin{cases}f[i-1][j][k] \\f[i-1][j-1][k]*a[i][pos]\\f[i-1][j][k-1]*(sum[i]-a[i][pos]) \end{cases}

容斥一下就行了，可是这个的复杂度是 O(n3m)O(n^3m) 要被卡

考虑性质，对答案有贡献的时候 j≥kj\geq k 那么我们似乎可以把差值一样的归到一个等价类里面去并且枚举差值，事实证明这样可以

(不过我代码里面的好像是 dp[i][k][j]dp[i][k][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
54
55
56
57
58
59
60
61
62
63
64
65
#include<stdio.h>
#include<iostream>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>

#define int long long

using namespace std;

const int maxn=2020;
const int modp=998244353;

//map <int,int> f[maxn];
int f[maxn][maxn*2];
int s[maxn][maxn];
int a[maxn][maxn];
int g[maxn][maxn];
int n,m,ans;

signed main()
{
	ios::sync_with_stdio(false);
	int i,j,delta;
	cin>>n>>m;
	for(i=1;i<=n;i++)
	for(j=1;j<=m;j++)
	{
		cin>>a[i][j];
		s[i][j]=a[i][j]+s[i][j-1];
		s[i][j]%=modp;
	}
	int looker=n;
	for(j=1;j<=m;j++)
	{
		f[0][0+n]=1;
		for(i=1;i<=n;i++)
		{
			for(delta=-i+n;delta<=i+n;delta++)
			{
				f[i][delta]=(f[i-1][delta]+1ll*f[i-1][delta-1]*a[i][j]%modp+1ll*f[i-1][delta+1]*(s[i][m]-a[i][j]+modp)%modp)%modp;
				if(delta-looker>0&&i==n) ans=(ans-f[i][delta]+modp)%modp;
				//cout<<"("<<i<<","<<delta<<" "<<f[i][delta]<<") ";
			}

		}
	}
	g[0][0]=1;
	for(i=1;i<=n;i++) g[i][0]=1;
	for(i=1;i<=n;i++)
	for(j=1;j<=n;j++)
	{
		g[i][j]=(g[i-1][j]+1ll*g[i-1][j-1]*(s[i][m]%modp))%modp;
		//cout<<g[i][j]<<" ";
		if(i==n) ans=(ans+g[i][j]+modp)%modp;
	}
	cout<<ans<<endl;
	//cout<<ans*(modp-1)%modp<<endl;
	return 0;
}

P2760 科技庄园

一个裸的二进制拆分背包，注意体力不能为 00 比较最小值的时候要 −1-1 然后似乎是我打的第一个多充背包？

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include<stdio.h>
#include<iostream>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>

#define int long long

using namespace std;

const int maxn=200010;

int a[maxn],aaa[maxn];
int deg[maxn];
int f[maxn];
int w[maxn];
int tot=0;
int n,m,aa,bb;
int ans=0;

map <pair<int,int>,int> mp;

signed main()
{
	ios::sync_with_stdio(false);
	register int i,j;
	cin>>n>>m>>aa>>bb;
	aa=min(aa,bb-1);
	for(i=1;i<=n;i++)
	for(j=1;j<=m;j++)
	{
		cin>>bb;
		if(bb) mp[make_pair(i,j)]=++tot,aaa[tot]=bb;
	}
	tot=0;
	for(i=1;i<=n;i++)
	for(j=1;j<=m;j++)
	{
		cin>>bb;
		if(mp[make_pair(i,j)])
		{
			int looker=mp[make_pair(i,j)];
			int k;
			for(k=1;k<=bb;k*=2)
			{
				bb-=k; //要注意减，不然总和可能会大于bb
				w[++tot]=(i+j)*2*k,a[tot]=aaa[looker]*k,deg[tot]=k;
			}
			if(bb) w[++tot]=(i+j)*2*(bb),a[tot]=aaa[looker]*(bb),deg[tot]=(bb);
		}
	}
	for(i=1;i<=tot;i++)
	for(j=aa;j>=w[i];j--)
	{
		f[j]=max(f[j-w[i]]+a[i],f[j]);
		ans=max(ans,f[j]);
	}
	cout<<ans<<endl;
	return 0;
	
}

P1799 数列

删除一些数，求最后剩下的数列中最多能有多少个数在自己的位置上，即 $ Ai=i$ 最多能有多少。

一个序列中贡献答案的一定单调上升，那就好办了，我们类似于求LIS的那种方法找到所有单调上升的序列来刷新答案就行了

注意负数和 ai≥ia_i\geq i 贡献不了答案

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
#include<stdio.h>
#include<iostream>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>

using namespace std;

const int maxn=1010;

int f[maxn];
int n,m,a[maxn],p[maxn];
int tot,ans;
int vis[maxn];

int main()
{
	ios::sync_with_stdio(false);
	register int i,j;
	cin>>n;
	int tmp;
	for(i=1;i<=n;i++) 
	{
		cin>>a[i];
		p[i]=i;
	}
	for(i=1;i<=n;i++)
	{
		if(!(a[i]>0&&a[i]<=i)) continue;
		for(j=0;j<i;j++)
		{
			if(a[i]>a[j]&&a[i]-a[j]<=p[i]-p[j]) f[i]=max(f[j]+1,f[i]);
		}
		ans=max(ans,f[i]);
	}
	cout<<ans<<endl;
	return 0;
}

P6419 [COCI2014-2015#1] Kamp

一个换根 dp\text{dp}

首先设

g[u]g[u] 表示 uu 为根的子树中送完所有人后会到 uu 的最小花费

l1[t],l2[u]l1[t],l2[u] uu 的最长链，次长链

id[t]id[t] 最长链开头的idid

然后我们考虑第一次 dfs\text{dfs}

如果 uu 的儿子 jj 的子树内有人的家，那就转移g[u]=∑v∈sonug[v]+val(eu,v)g[u]=\sum\limits_{v\in son_u}{g[v]+val(e_{u,v})}

否则不考虑

然后考虑第二次 dfs\text{dfs}

我们设 f[u]f[u] 表示以 uu 为根的整颗子树的最小花费

当子树内没有人的家时，f[v]=f[u]+2∗val(eu,v)f[v]=f[u]+2*val(e_{u,v})

当只有子树内有家时，f[u]=g[u]f[u]=g[u]

否则，无论以哪个点为根，我们都要经过这个点 f[t]=f[v]f[t]=f[v]

最后显然是不走回来更优，因此我们维护最长链

l1[u]+val(ei,j)≥l1[j],id[u]≠jl1[u]+val(e_{i,j})\geq l1[j] ,id[u]\neq j 更新

l1[u]+val(ei,j)≥l2[j],id[u]≠jl1[u]+val(e_{i,j})\geq l2[j] ,id[u]\neq j 更新

l2[u]+val(ei,j)≥l1[j]l2[u]+val(e_{i,j})\geq l1[j] 更新

l2[u]+val(ei,j)≥l2[j]l2[u]+val(e_{i,j})\geq l2[j] 更新

至于为什么是正确的，因为 id[u]=jid[u]=j 不可能同时对应 l1,l2l1,l2

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include<stdio.h>
#include<iostream>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>

#define int long long

using namespace std;

const int maxn=500500;
int sz[maxn],l1[maxn],l2[maxn],head[maxn],f[maxn],g[maxn];
int id[maxn],n,m,size;

struct edge{
	int next,to,dis;
}e[maxn*2];

inline void addedge(int next,int to,int dis)
{
	e[++size].to=to;
	e[size].dis=dis;
	e[size].next=head[next];
	head[next]=size;
}

void dfs1(int t,int fat)
{
	int i,j,k;
	for(i=head[t];i;i=e[i].next)
	{
		j=e[i].to;
		k=e[i].dis;
		if(j==fat) continue;
		dfs1(j,t);
		if(!sz[j]) continue;
		if(l1[t]<=l1[j]+k)
		{
			l2[t]=l1[t];
			l1[t]=l1[j]+k;
			id[t]=j;
		}
		else if(l2[t]<l1[j]+k) l2[t]=l1[j]+k;
		sz[t]+=sz[j];
		g[t]+=g[j]+k*2;
	}
}

void dfs2(int t,int fat)
{
	int i,j,k;
	for(i=head[t];i;i=e[i].next)
	{
		j=e[i].to;
		k=e[i].dis;
		if(j==fat) continue;
		if(!sz[j])
		{
			f[j]=f[t]+2*k;
			l1[j]=l1[t]+k;
			dfs2(j,t);
			continue;
		}
		if(sz[j]==m) 
		{
			f[j]=g[j];
			dfs2(j,t);
			continue;
		}
		if(l1[t]+k>l1[j]&&id[t]!=j) l2[j]=l1[j],l1[j]=l1[t]+k,id[j]=t;
		else if(l2[t]+k>l1[j]) l2[j]=l1[j],l1[j]=l2[t]+k,id[j]=0;
		else if(l1[t]+k>l2[j]&&id[t]!=j) l2[j]=l1[t]+k;
		else if(l2[t]+k>l2[j]) l2[j]=l2[t]+k;
		f[j]=f[t];
		dfs2(j,t);
	}
}

signed main()
{
	ios::sync_with_stdio(false);
	register int i,j;
	cin>>n>>m;
	int t1,t2,t3;
	for(i=1;i<n;i++) cin>>t1>>t2>>t3,addedge(t1,t2,t3),addedge(t2,t1,t3);
	for(i=1;i<=m;i++) cin>>t1,sz[t1]=1;
	dfs1(1,1);
	f[1]=g[1];
	dfs2(1,1);
	for(i=1;i<=n;i++) cout<<f[i]-l1[i]<<endl;
	return 0;
}

P1131 [ZJOI2007]时态同步

在摸机箱的时候突然想到：

设 f[u]f[u] 表示 uu 的子树满足时态同步的最小花费

显然一颗子树如果不满足时态同步那么就一直不满足了。

然后刚开始 dfsdfs 错地方以为做法假了，结果改了下直接A了

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include<stdio.h>
#include<iostream>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>

#define int long long 

using namespace std;

const int maxn=500500;

int f[maxn],head[maxn],size;
int n,m,st;
int dismmx[maxn];

struct edge{
	int next,to,dis;
}e[maxn*2];

inline void addedge(int next,int to,int dis)
{
	e[++size].to=to;
	e[size].dis=dis;
	e[size].next=head[next];
	head[next]=size;
}

void dfs1(int t,int fat)
{
	int emmx=0,i,j,k;
	for(i=head[t];i;i=e[i].next) 
	{
		j=e[i].to;
		k=e[i].dis;
		if(j==fat) continue;
		dfs1(j,t);
		emmx=max(dismmx[j]+k,emmx);
	}
	dismmx[t]=emmx;
	for(i=head[t];i;i=e[i].next)
	{
		j=e[i].to;
		k=e[i].dis;
		if(j==fat) continue;
		f[t]+=f[j]+dismmx[t]-(dismmx[j]+k);
	}
}

signed main()
{
	register int i,j;
	//cin>>n;
	scanf("%d",&n);
	//cin>>st;
	scanf("%d",&st);
	int t1,t2,t3;
	//for(i=1;i<n;i++) cin>>t1>>t2>>t3,addedge(t1,t2,t3),addedge(t2,t1,t3);
	for(i=1;i<n;i++) scanf("%d %d %d",&t1,&t2,&t3),addedge(t1,t2,t3),addedge(t2,t1,t3);
	dfs1(st,st);
	printf("%lld\n",f[st]);
	return 0;
}