竞赛讨论区 > 【题解】2021牛客寒假算法基础集训营 6

【题解】2021牛客寒假算法基础集训营 6

头像
Alan233
编辑于 2021-02-24 20:22:51 APP内打开
赞 18 | 收藏 2 | 回复9 | 浏览1881
  • 致歉

因为出题人的疏忽,T6 造了 n 不是 4 的倍数的数据。同时 T8 因为多次重造数据,被暴力碾过去了。真抱歉 qaq 。

T1 回文括号序列计数

记串为 ,由于回文所以 ,由于括号序列所以

因此不存在长度 的串。当 时存在一个空串。

T2 系数

做法一

,求的即为

这个就是个简单的组合数,易知是

做法二

赛时也有部分人打表来观察解出此题,这里给出一种比较简洁的打表观察做法:

将前一些数打印出来:

int dp[105][105];
int main() {
  dp[0][0] = 1;
  for (int i = 1; i <= 30; i++) {
    for (int j = 0; j <= 2 * i; j++) {
      dp[i][j] = (dp[i - 1][j] + (j >= 1 ? dp[i - 1][j - 1] : 0) + (j >= 2 ? dp[i - 1][j - 2] : 0)) % 3;
      if (!dp[i][j]) printf("   ");
      else printf(" %d ", dp[i][j]);
    }
    puts("");
  }
}

发现它满足分形规律,不难联想到组合数也是满足分形规律的。

将组合数也打印出来,发现 有值当且仅当 不为 (模 3 意义下),进而发现 1 和 2 的取值与 m 的奇偶性相关。

归纳可知 ,前者可以用 Lucas 定理 计算。

总时间复杂度

T3 末三位

枚举一下:1 5 25 125 625 125 625 ... 可以发现 125, 625 二个一循环。

注意需要特判 的情况,需要输出前导零。

T4 划数

由于题目保证 ,所以答案一定是唯一的。因为新加入的数一定 ,所以 一定是原来序列中的某个数。

可以发现,无论怎么操作,这些数的和模 11 的值不会变。

所以答案即为

注意特判 的情况。

时间复杂度

T5 grid

显然每个点在上下中选一个,左右中选一个。所以对于竖直的情况和水平的情况是相互独立的。

下面只考虑水平的情况:对于每一行,用 表示当前第 个数向左/右能得到的最大答案。

则不难有转移:

答案即为 ,每一行的答案相加即为水平方向上的贡献。

竖直方向同理。预处理一个数的 (二进制位 1 的个数)即可做到

T6 组合数问题

所以原式 ,用复数快速幂即可。

时间复杂度

T7 机器人

暴力是 的,直接全排列枚举即可。可通过 random_shuffle 乱搞,但应该被卡掉了。

首先,局部最优可以推得全局最优,所以 dp 正确性可以保证。

正解是状压dp,用 表示当前状态 st 可得到的最大值,答案即为

注意一些常数优化的技巧,时间复杂度

还有一种贪心的做法,设两个相邻的机器人为 ,一开始的数是

则满足 ,即

按此排序即可。

T8 动态最小生成树

这道题好像被暴力碾过去了...

如果每次暴力重构生成树,每次跑 ,复杂度是 的,预处理排序,则复杂度降为

考虑将上述流程放到线段树上,对于线段树的每个节点,开一个大小为 的数组,表示区间构成的生成树的边的集合。每次线段树上传,则是一个归并排序做生成树的过程。

时间复杂度

另外一种做法是带修莫队,用 动态维护最小生成树。由于其难度较大且代码不易实现,而且常数极大,所以这里不细讲了,时间复杂度

T9 贪吃蛇

为起点 ,到 的最短路乘以 进制转换)即为答案。

由于贪吃蛇不能吃自己,所以不会走走过的格子。而每个点显然是越早到越好,所以直接广搜是正确的。

时间复杂度

T10 天空之城

显然题目要求的是最小生成树。对于每个串,可以通过 std::map<string, int> 映射到一个数上,然后就转化成了 个点 条边求最小生成树的板子题。

时间复杂度

9条回帖

回帖
加载中...
话题 回帖

近期热帖

等你来战

查看全部

热门推荐