本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-12-09 15:46:52

题意

给你 $4$ 个六位数，分别判断这四个日期代表的月份属于的季节。

题解

通过阅读题意我们不难发现，对于每一个输入的日期，日期之间相互没有影响，并且判断季节S仅与月份有关，与年份无关。

所以我们只需要关心每个日期的月份。根据题意，对于每一个输入，它的月份为它的后两位。那么获取月份就变成了获取这个六位数的后两位

那么如何获取一个数字的后两位呢？

我们知道一个数字的后两位相当于这个数字除以 $100$ 的余数，即一个数字对 $100$ 取模 (% $100$) 的结果。我们通过将一个数字对 $100$ 取模可以取到这个数字的后两位，所以对于每个输入的数字，我们使用一个变量记录这个数字对 $100$ 取模的结果，然后根据题意使用 if 及 else if 判断即可。

代码

#include<bits\/stdc++.h>
using namespace std;
int main()
{
	int n;
	for(int i = 1;i <= 4;i++)
	{
		cin >> n; \/\/输入 
		int date = n % 100; \/\/取日期的后两位 月份 
		if(date == 0 || date > 12) \/\/判断日期是否合法 
		{
			cout << "error" << endl;
			continue;
		}
		if(date >= 9 && date <= 11) \/\/秋天 
		{
			cout << "autumn" << endl;
		}
		else if(date >= 3 && date <= 5) \/\/春天 
		{
			cout << "spring" << endl;
		}
		else if(date >= 6 && date <= 8) \/\/夏天 
		{
			cout << "summer" << endl;
		}
		else \/\/冬天 
		{
			cout << "winter" << endl;
		}
	}
	return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-02-12 14:32:32

题解 P3523 - 复杂度（常数）优化

如果你被卡了 TLE 或者代码非常慢，请看过来！！！

题目描述

题目 P3523 要求我们在一棵树上选择若干个节点，使得每个关键点到最近选择的节点的距离不超过某个值。

简述做法

本题思路其他题解都已经基本讲的非常清楚，就是外层二分出距离并通过 DP 去 check 可行性。

但是相信很多大佬都面临了 TLE 的问题。 呜呜呜。

耗费了一中午卡常，最终在我将 vector 邻接表存图 改为 链式前向星存图 之后，终于过了！而且快了不止一点好像并不多。

两种方法提交记录

vector 邻接表

链式前向星

难道这就是最优办法了吗？？？——显然不是的。

****那么接下来****

进入正题

在经过 @KSCD_ 及 @ryp 大神指点后，我们发现，vector做法之所以会被卡，很多的时间都花费在了 DFS 及 DP 时 vector 查找合并上面，所以我们考虑如何优化 DFS 及 DP 的过程。

我们可以先进行一遍 DFS，在图上跑出 DFN 序，随后我们在 DP 合并的时候就不需要递归的高时间消耗，转而变成了对数组元素的访问与修改，通过这种方法即可优化掉我们代码中 DFS 递归带来的常数。

此种做法从本质上来讲并没有和其他做法有什么区别，但是这种做法可以通过 减少递归 从而显著优化了树上问题的常数。这样的优化常数在树上进行 DP 的方法也值得研究学习。

这种做法即使使用 vector 并且 不卡常 也可以通过，并且跑得飞快。大部分的 树形 DP 也都可以考虑通过按照 DFN 方合并式来减小常数优化复杂度

代码解析

首先我们跑出图上的 DFN 序，并存储 DFN 对应节点编号。

void dfs(int u,int fat)\/\/fat表示父亲
{
	fa[u] = fat;
	p[++cnt] = u;
	for(int v : G[u])
	{
		if(v == fat) continue;
		dfs(v,u);
	}
}

随后我们就可以在数组里进行 DP。

我们先对 f 数组及 g 数组赋上初始值。

for(int i = 1;i <= n;i++)
  {
  	f[i] = (vis[i] ? 0 : -inf);\/\/f[i] 表示 以i为根的子树中最远的未被覆盖的关键点距离
  	g[i] = inf;\/\/g[i] 表示 以i为根的子树中最近的选择的节点距离
  }

然后就可以直接倒序枚举 DFN 序，即可从叶子向根进行 DP

for(int i = n;i >= 1;i--)
	{
		int u = p[i];
		if(f[u] + g[u] <= x) f[u] = -inf;
		if(f[u] == x)
		{
			ct++;
			f[u] = -inf;
			g[u] = 0;
		}
		f[fa[u]] = max(f[fa[u]],f[u] + 1);
		g[fa[u]] = min(g[fa[u]],g[u] + 1);
	}

最后是完整代码及提交记录（个人认为在加强数据之后算是跑的比较快的~）

AC记录

代码

#include<bits\/stdc++.h>
using namespace std;
#define endl '\n'
const int maxn = 3e5 + 10;
const int inf = 0x3f3f3f3f;
int vis[maxn],fa[maxn],f[maxn],g[maxn];
int n,k;
int p[maxn];
int cnt;
vector<int> G[maxn];
void dfs(int u,int fat)
{
	fa[u] = fat;
	p[++cnt] = u;
	for(int v : G[u])
	{
		if(v == fat) continue;
		dfs(v,u);
	}
}

bool check(int x)
{
	int ct = 0;
	for(int i = 1;i <= n;i++)
	{
		f[i] = (vis[i] ? 0 : -inf);
		g[i] = inf;
	}
	for(int i = n;i >= 1;i--)
	{
		int u = p[i];
		if(f[u] + g[u] <= x) f[u] = -inf;
		if(f[u] == x)
		{
			ct++;
			f[u] = -inf;
			g[u] = 0;
		}
		f[fa[u]] = max(f[fa[u]],f[u] + 1);
		g[fa[u]] = min(g[fa[u]],g[u] + 1);
	}
	if(f[1] >= 0) ct++;
	return (ct <= k);
}
int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> k;
	for(int i = 1;i <= n;i++)
	{
		cin >> vis[i];
	}
	for(int i = 1;i < n;i++)
	{
		int u,v;
		cin >> u >> v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dfs(1,0);
	int l = 0,r = n;
	int ans = n;
	while(l <= r)
	{
		int mid = (l + r) >> 1;
		if(check(mid)) ans = mid,r = mid - 1;
		else l = mid + 1;
	}
	cout << ans << endl;
	return 0;
}

总结

通过使用链式前向星和 DFN 序，我们成功优化了树形 DP 的常数，使得算法能够在更短的时间内通过本题。这种方法不仅适用于本题，还可以推广到其他树形 DP 问题中。

感谢观看！！！蒟蒻的第一篇题解，希望对你有所帮助~~~

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-02-13 15:30:21

树形DP常用优化

主要是通过利用 DFN 序的一些巧妙性质及利用，从而实现优化常数甚至是优化复杂度。

1.树形背包

例如 P2014 [CTSC1997] 选课

我们在正常进行树形背包时，需要进行 $3$ 层循环，时间复杂度为 $O(n^3)$ 。

code

for(int i = 0;i < G[u].size();i++)
	{
		int v = G[u][i];
		for(int j = m;j >= 1;j--)
		{
			for(int k = 0;k < j;k++)
			{
				dp[u][j] = max(dp[u][j],dp[u][j-k] + dp[v][k]);
			}
		}
	}

但我们可以考虑将以 $u$ 为根的子树拍扁,这样我们就相当于是在子树内进行了一次 $0/1$ 背包，由于最终答案都是由子树合并来，而子树之间的数量关系也不会相互影响，所以我们直接将其拍扁，这样进行树形背包的复杂度是 $O(n^2)$ 的。

code

for(int i = 1;i <= n + 1;i++)
	{
		int u = d[i];
		for(int j = 0;j <= m;j++)
		{
			f[i][j] = f[i - size[u]][j];
			if(j) f[i][j] = max(f[i][j],f[i-1][j-1] + s[u]);
		}
	}

2.$DFN$ 优化递归常数

同样的，我们这种利用 $DFN$ 而避免使用递归合并 $dp$ 数组的方法可以极大的优化递归常数。

例如P3523 [POI 2011] DYN-Dynamite

我们在由子树向根合并 $dp$ 值的时候，通过 $DFN$ 避免了使用 $dfs$ 递归带来的大常数，在一些极端数据下可以使我们的代码跑的飞快。

详见分析

3.通过减少合并次数降低复杂度

常见的，我们可以通过树的链剖分以及树上 lca ，使得子树或一条链内的所有节点都合并到链头的位置，从而可以优化合并的复杂度。

未完待续。

• | 这里写第一页幻灯片的 Markdown
• | 这里写第二页幻灯片的 Markdown
• | 这里写第三页幻灯片的 Markdown
• children:
  • | 哇咔咔竖着第一页
  • | 哇咔咔竖着第二页

information

• date：2025.7.5
• OJ:WyOJ
• contest:CSP真题模拟赛
• score：100--100--100--8--24

$C$ 括号树

赛事一开始 $A$ 没思路，$B$ 看错题了，$C$ 有点思路所以先开的C。

但是 $C$ 细节很多，调了半天炸了好多次，调了大约 $2h$。

$B$ 加工零件

看了看总算看出来读错题了，第一遍写成dfs了，最后 $0.5h$ 过 $B$。

$A$ 纪念品

想出 $O(TNM)$ 的做法了，但是复杂度算错了，大约 $5min$ 才看出来，差点忘了完全背包怎么写，$20min$ 过。

$E$ 划分 and $D$ Emiya 家今天的饭

写的时候只剩 $20min$ 了，迅速看了一下题面（有点长，看的时候有点晕，但还好），把暴力打了一下，$D$ 打了 $n=2$ 的骗分，$8pts$;$E$ 打了 $O(2^n)$ 然后剪枝优化了一下，$24pts$。

总结

$C$ 题耗时太多了，但是好歹最后调出来了。

开始有点困，没静下来想题，想了一会 T1，发现了每天可以全部卖出去再买回来的转化。考虑 dp，写完发现挂了，于是去开了 T2。

T2观察了一会发现可以根据奇偶性去做，写了 bfs，只记录了奇偶的可行性，样例挂了发现需要研究 $l$ 和距离之间的关系，但没想到要计算距离。想到用 topu 和环长特判但感觉太麻烦了，于是去看其他的题。

T3 观察了一会，发现贡献是一条链，考虑怎么从父亲转移过来，但是还有不到一小时，于是先去调了 T1，最后发现把完全背包想成了 01 背包，枚举顺序错了所以挂了，心态不稳了，后面暴力看出来了也没有再争，研究了一会 T3 做法，没时间了。

应该注意时间的分配，同时多提高自己的思维能力，提高想题的速度和正确率，注意心态的调整。