传送门
题意：给出n个字符串，如果一个字符串的最后两个字母和另一个（或它自身）的前两个字母相同，就可以将它们连接起来，最后可能会形成环。求环的平均字符串长度的最大值。
思路：可以把两个字母看成一个点，则最多26^2个点，一个字符串相当于一条权值为它的...
18-7-22 690 views
阅读全文 0
传送门
题意：对于每组数据，判断是否存在负环
思路：SPFA找负环，此题数据非常强大。根据信息学奥赛一本通·提高篇中所述，DFS-SPFA找负环速度很快，实际上并不是这样，直接TLE。
之前用的普通BFS-SPFA模版也一样TLE，在题解区发现有一种新写法，更新时用cnt[v]=c...
18-7-22 665 views
阅读全文 0
传送门
一只青蛙要过河，河里原来有n个石头，河的宽度为m，青蛙一次最多跳l长。在河里加一些石头帮助青蛙过河，同时青蛙想尽可能跳的次数少，你想让它尽可能跳的次数多。问最多跳几次。
思路：参考https://blog.csdn.net/qq_35781950/article/details/75207937
最...
18-6-17 577 views
阅读全文 0
传送门
给N个点，M条边，问有多少个包含S个点的集合，集合中的点两两直接相连。
思路：直接暴力dfs，用一个数组表示当前集合里的点，如果当前枚举的点与这些点都有边，就可以加进去进入下一层dfs，直到枚举的size==S。
为了防止重复，在加边时统一由编号小的点指...
18-6-02 638 views
阅读全文 0
传送门
题目大意：给n个珠子涂成目标颜色。每次可以涂相邻的一些珠子，花费是这些珠子中颜色种数k的平方。求最小花费。
思路：双向链表优化dp。dp[i]表示涂完前i个所花的最小代价，显然有dp[i]=min{dp[j]+num(j+1,i)^2},其中1<=j<i，num(j+1,i)表示区间[j+...
18-5-08 706 views
阅读全文 0
传送门
马走日， 象走田，车走直路炮翻山，小艾同学发明了新玩法，只用炮来布阵棋盘，在一个N*M 的棋盘上，你要放置若干个炮兵，可以是0个，但是不能让炮打到彼此，有多少种方案？
思路：按行dp，思考一下可以发现只需要知道有几列是已经有1个炮，有几列已经有两...
18-5-06 654 views
阅读全文 0
传送门
题目大意：给定n个点m条边的无向图，每个点作为初始位置的概率相同，在每个点时走向相连每个点的概率相同。一共走d步，问从不经过每个点的概率。
思路：概率dp，定义dp[u][i][j]：经过了j步之后落在i点且从来不经过u点的概率。最后对于各个点，从不经过它...
18-5-05 633 views
阅读全文 0
传送门
这是找树的重心的经典题目。
题目大意：在一棵树中找一个点，删掉以后使所有子树中最大的节点数最少，问应该删哪个点以及最大子树的节点数。
思路：树形dp，f[u]保存以u为根节点的子树的节点数，那么只要比较答案和f[v]+1和n-f[u]-1的关系就可以了。
dfs一...
18-4-10 589 views
阅读全文 0
真的挺好看的。
推荐 ANK-Raws BDrip 1920×1080 HEVC-YUV420P10 FLAC
https://share.dmhy.org/topics/view/483658_Mmch_sub_ANK-Raws_No_Game_No_Life_Zero_BDrip_1920x1080_HEVC-YUV420P10_FLAC.html
18-3-29 2,953 views
真的挺好看的。
推荐 ANK-Raws BDrip 1920×1080 HEVC-YUV420P10 FLAC
https://share.dmhy.org/topics/view/483658_Mmch_sub_ANK-Raws_No_Game_No_Life_...
