题目传送门：E - Warp (atcoder.jp) 题意 / Problem 在二维平面中，从原点(0, 0)出发，进行N次移动，每次移动可以选择3个方向，分别是从\((x, y)\)移动到\((x + A, y + B)、(x + C, y + D)、(x + E, y + F)\)，只在整数点上运动。 有M个障碍点是不能走的。问N次移动后一共可以有多少种运动轨迹。 思路 / Thought […]

题目传送门：E - Blackout 2 (atcoder.jp) 题目 / Problem 有N个城市和M个发电厂，有E条边，第 i 条边连接两个点（可能是城市也可能是发电厂），现在有Q个项目，每个项目会摧毁第x条边，问每个项目之后有多少个城市可以到达发电厂。 思路 / Thought 因为M个发电厂都是等价的，所有可以把这M个发电厂都看作0号点。为了维护“是否可达”这个属性，可以用并查集，但是 […]

题目传送门：F - Tournament (atcoder.jp) 题意 / Problem 有\(2^N\)个人，从\(1 ~ N\)进行编号，进行N轮操作，每轮操作将第\(2i-1\)和第\(2i\)个人进行对战，每次对战都有一个人胜出，失败的人淘汰。 编号为i的人如果赢了j次，那么就可以获得\(C[i][j]\)的奖励。求所有人获得的最大的奖励之和。 思路 / Thought 显然是一颗完美 […]

题目传送门：E - Sugoroku 3 (atcoder.jp) 题目大意 / Problem 有N个点（位置），其中从1到N - 1个点上各有一个骰子，在第i个点上可以投掷第i个骰子，假设在x位置上投到y，下一步就走到y上。保证下一个位置不会大于N。 问从位置1到位置N的步数期望，对998244353。 思路 / Thought 之前有写过期望的题《[LightOJ]Race to 1 Aga […]

题目链接：E - Many Operations (atcoder.jp) 题目 / Problem 给定N个操作，每个操作有3种模式，与运算、或运算、异或运算，数字x初始化为C，到第i层操作的时候将x按顺序执行一遍[1, i]的所有操作，问每次完成一层后x的值。 思路 / Thought 可以将数字x的每一个二进制位都维护一个函数f[i][0 / 1]，表示初始为0 / 1的二进制位上的数字经过 […]

比赛链接：AtCoder Beginner Contest 254 - AtCoder 各题题目请看原题链接。 A - Last Two Digits 代码 / Code B - Practical Computing  代码 / Code C - K Swap 因为每次只能交换间隔为K的，其实就可以将整个数组分为K个类（组），每个类都是“对K取模相等”的。 比如N = 7，K = 3， […]

传送门：B - At Most 3 (Judge ver.) (atcoder.jp) 题目大意 给定一个长度为N的数组（N <= 300），每次从中取出至多3个数字，问所有可能的且小于等于W的和(sum)有多少种。 思路 dfs，一共3层，每层可能的结果为a[1 ~ N]或0（不选）。 为了防止重复选择，用vis数组防止重复，还可以用k（循环开始位置）来剪枝。 第二个剪枝就是当sum &g […]

题目传送门：F - Cards (atcoder.jp) 题目大意 给定N张牌，每张牌有两个数字Pi和Qi，所有的牌中P和Q构成两个[1, N]的排列。现在从N张牌中选出任意张牌，请问有多少种选法，使得选出的牌拥有所有[1, N]的数字。 思路 这题看视频吧，有点繁琐不好写。 [AtCoder Beginner Contest 247]简单易懂 A - F算法竞赛刷题记录_哔哩哔哩_bilibil […]

题目传送门：E - Max Min (atcoder.jp) 题目大意 给定N，X，Y和一个长度为N的序列。 求该序列中最大值为X，最小值为Y的连续子序列的数量。 PS：以下所讲的子序列均指连续子序列。 思路 一开始没想到是容斥原理，看了Jinagly大佬的代码才豁然开朗。 函数getRangeOf(X, Y)返回最小值大于等于Y，最大值小于等于X的子序列的数量。 那么根据容斥原理，我们要得到最小 […]

题目传送门：E - Σ[k=0..10^100]floor(X／10^k) (atcoder.jp) 题目大意 顾名思义，求这么一坨东西。 思路 看到这个数据肯定要想用高精度。 而且不能用暴力算法去算这个东西，要想一个O(N)复杂度可以解决的，这就要去找规律了。 我们将所有要加起来的东西竖着写，会得到一个“阵”，暂且叫数阵吧。 这个数阵是沿着副对角线对称的，而每一位上（比如个位，十位）的和，是有递 […]