传送门
题意：给定n个整数，问是否能生成一棵BST（二分查找树，左子树都比它小，右子树都比它大），并且有边相连的点权的gcd>1。
思路：区间dp，dp[l][r][1/0]表示区间[l,r]是否可以是一棵合法的左/右子树。
关键：若[l,r]是左子树，它的父节点必定是r+1，若是...
18-9-02 883 views
阅读全文 0
传送门
题意：有n个宿舍，每个宿舍住4个人，给定去年n个宿舍的人员构成，今年n个4人组合的情况，求最少几个人需要搬寝室。
思路：转化为最小费用最大流解决的二分图问题，对每个去年的宿舍，向每个今年的组合连一条边，权值为1费用为需要搬的人数（4-相同的人数）...
18-8-02 1,209 views
阅读全文 1
传送门
题意：有一个容量为n的箱子，和无限多的两种珠宝，体积和价值分别是s1,v1,s2,v2，求能装下的最大价值。
思路：直接暴力枚举会TLE，先计算s1 s2的LCM，分两种情况讨论。
1.n<lcm 直接枚举
2.n>=lcm 先求r=n%lcm，将n分为两部分，n-r-lcm和r+lcm，第一...
18-7-29 570 views
阅读全文 0
传送门
题意：有n个字符串，每个字符串仅包含'(‘和’)’，可以按某种方法将这n个字符串连接起来，求最后字符串能完全匹配的子串的长度。
思路：就是求连接后最多有几对括号能匹配。将预处理后的字符串分成3组，1.仅含'(‘ 2.先’)̵...
18-7-25 1,426 views
阅读全文 0
传送门
题意：有n个城市，m条双向边，给定起点和终点。求最佳路径的种数。（最佳路径指时间和费用不同时比其他某条线路大，相同时间费用算同一种）
思路：设二维数组dp[i][j]表示在第i个城市已经花费j元的最小时间。跑一遍BFS-SPFA即可。
很明显当前不是最佳的情...
18-7-22 728 views
阅读全文 0
传送门
题意：给出n个字符串，如果一个字符串的最后两个字母和另一个（或它自身）的前两个字母相同，就可以将它们连接起来，最后可能会形成环。求环的平均字符串长度的最大值。
思路：可以把两个字母看成一个点，则最多26^2个点，一个字符串相当于一条权值为它的...
18-7-22 684 views
阅读全文 0
传送门
题意：对于每组数据，判断是否存在负环
思路：SPFA找负环，此题数据非常强大。根据信息学奥赛一本通·提高篇中所述，DFS-SPFA找负环速度很快，实际上并不是这样，直接TLE。
之前用的普通BFS-SPFA模版也一样TLE，在题解区发现有一种新写法，更新时用cnt[v]=c...
18-7-22 652 views
阅读全文 0
传送门
一只青蛙要过河，河里原来有n个石头，河的宽度为m，青蛙一次最多跳l长。在河里加一些石头帮助青蛙过河，同时青蛙想尽可能跳的次数少，你想让它尽可能跳的次数多。问最多跳几次。
思路：参考https://blog.csdn.net/qq_35781950/article/details/75207937
最...
18-6-17 567 views
阅读全文 0
传送门
给N个点，M条边，问有多少个包含S个点的集合，集合中的点两两直接相连。
思路：直接暴力dfs，用一个数组表示当前集合里的点，如果当前枚举的点与这些点都有边，就可以加进去进入下一层dfs，直到枚举的size==S。
为了防止重复，在加边时统一由编号小的点指...
18-6-02 632 views
阅读全文 0