首页 > 其他分享 >Atcoder Beginner Contest 271(A~G)

Atcoder Beginner Contest 271(A~G)

时间:2022-11-03 21:13:10浏览次数:72  
标签:Atcoder Beginner sum 路径 access 271 方格 小时 复杂度


省流:赛时 F 假了。


赛时

A 转进制;B 简单 vector。

C 简单贪心模拟,大概就是能走就走,不能走就先不走(较大)或者存起来(较小),最后走存起来的。挂了 3 发,自闭了。

D 第一眼看成了某年 NOI Online 的卡牌游戏,以为是原题,正准备写发现不对劲,揉了揉眼睛发现是个 shabby 题。\(O(nm)\) 的复杂度做个背包就行了。

E 给定了一个集合的路径,那么后面的路径只能从前面的路径搭过来,于是枚举集合内每一个路径进行转移作一个 dp 即可。有点类似于出题人给了一个序让你求最短路。

除了 FST 了三发,到这里一切都很顺利。

然后到 F 就像人降智了一样。看到小数据也没向搜索想,感觉拆位的 dp 可以做。具体来说,把每一个方格里的数按位拆开,对于每一位作个 dp 排除一些不合法路径,最后从合法路径进行方案数转移。排除合法路径的维护就类似于对于每一个方格封一个或两个不可能的转移方向。复杂度根本不用算,太优秀了!

可惜合法路径根本不是封若干方向就能维护的,例如两条在一个方格里交叉的路径,就无法通过这种形式精准找到。

于是调到本场结束,睡前才恍然大悟。


赛后

F 数据范围太小,但是如果暴力的话, \(O(2^{2n})\) 的复杂度又太高,稍微有点接受不了。

于是考虑异或的一个性质,如果路径异或和为 \(0\),则随意找一个切线切开路径就可以得到两条异或和相同的路径。

所以我们可以考虑一个叫作 meet int the middle 的 trick,将网格从右上到左下斜着切开,分别对于左上和右下到对角线作一遍 dfs。

具体来说,我们可以对于这条对角线的每一个方格开一个 map,将左上走到方格 \(p\) 的所有路径的异或和都存在方格 \(p\) 的 map 里。

从右下到左上搜的时候只需要从 map 中进行查询即可。时间复杂度 \(O(n2^n\log 2^n)\),常数好像不大。

G 一眼矩阵加速,但是补题的时候对于转移方程的构造想了好久。

注意到我们转移的时候其实只关注两点:当前所在的小时,以及当前 access 了几次。

所以我们不妨设 \(dp_{i,j}\) 表示当前 access 了 \(i\) 次,且最后一次 access 是在第 \(j\) 个小时进行的。而 \(i\) 这一维我们是要矩阵加速转移的,所以我们只需要考虑 \(j\) 这一维怎么转移。也就是,如果从第 \(i\) 个小时 access 之后,一直不 access,直到不知道多少天之后又在第 \(j\) 个小时 access 了的概率是多少。

我们不妨设 \(p_i\) 为第 \(i\) 个小时 access 的概率,\(s_{i,j}\) 为从第 \(i\) 个小时转移到第 \(j\) 个小时的概率,\(n\) 为过去的整数天数,\(sum_{i,j}\) 为从第 \(i\) 个小时到第 \(j\) 个小时都不 access 的概率。则有方程:

\[s_{i,j}=\sum_{n=0}^{+\infty}sum_{i+1,j-1}p_i\times sum_{1,24}^n \]

于是就是一个等比数列求和的形式,转化一下就是:

\[s_{i,j}=\dfrac{sum_{i+1,j-1}p_i}{1-sum_{1,n}} \]

于是把它扔进矩阵,套路矩阵加速即可。

H 没时间补了,先放着,感觉好像可做,但会有亿些细节。


启发

  1. 【解题】算法的选择一定要优先考虑数据范围,小数据范围+低时间复杂度的正常题目是很少的。小数据范围可以多考虑状态压缩以及高效搜索

  2. 【赛时】Think twice seriously,code once quickly.

  3. 【trick】有关“无限”的式子可以考虑通项公式(?

标签:Atcoder,Beginner,sum,路径,access,271,方格,小时,复杂度
From: https://www.cnblogs.com/ydtz/p/16855841.html

相关文章

  • AtCoder Regular Contest 065
    ARC064C,E都是简单题,D猜结论也没啥意思,就不写了。ARC065还是比较好的。D-Connectivity给定\(n\)个点的无向图,有两组连边,互相独立。询问每个点通过两组连边都......
  • AtCoder Regular Contest 136 D Without Carry
    AtCoder传送门洛谷传送门一眼。将\(a\)中每个数用前导零补到\(6\)位,题目相当于问所有\(i,j\),\(a_i\)的每一位加\(a_j\)的这一位都不超过\(9\)的\((i,j)\)......
  • ABC271 E~F
    E:按给出的顺序依次松弛每条边就好了。CodeF:折半搜索典题,双倍经验。CodeG:啥玩意啊不想做Ex:啥玩意啊不想做......
  • HDU - 2717
    大概是自己第一次在图之外用搜索吧(wwww要是早点做过的话可能蓝桥省赛的那个记忆化搜索就能a出来了hhhhttps://vjudge.net/problem/HDU-2717#author=shiyifan(这是hdu源链......
  • ATcoder F 做题记录
    ABC273F简要题意一个人要沿数轴从\(0\)处走到\(x\)处,数轴上有一些障碍,每个障碍有一把对应的锤子可以将其销毁,给定障碍和锤子的坐标及\(x\),求最短路长。简要题......
  • Atcoder Beginner Contest 273(A~E+G)
    E场上想麻烦了,调根号分治浪费了点时间;F涉及后缀数组,还没有系统学;G场上没来的及看,也沾点数学,估计场上也想不到(不好,不好。赛时A神笔数组求和;B迷你模拟;C分别找到奇......
  • D - Yet Another Recursive Function -- ATCODER
    D-YetAnotherRecursiveFunctionhttps://atcoder.jp/contests/abc275/tasks/abc275_d 思路动态规划问题。第一印象使用函数递归调用实现,但刚开始担心会爆栈,因为......
  • AtCoder Beginner Contest 275 D~F
    D-YetAnotherRecursiveFunction思路:直觉需要用到的数字大多数是重复的,所以记忆化了一下,测了一下1e18的数据,跑的飞快,直接交了,6ms。#include<bits/stdc++.h>#def......
  • C - Counting Squares -- ATCODER
    C-CountingSquareshttps://atcoder.jp/contests/abc275/tasks/abc275_c参考:https://atcoder.jp/contests/abc275/submissions/36103954 思路首先不能使用暴力穷......
  • 【atcoder 293 F - Erase Subarrays】【动态规划】
    importjava.io.BufferedReader;importjava.io.IOException;importjava.io.InputStreamReader;publicclassMain{publicstaticvoidmain(String[]args)......