atcoder做题记录

F题#

小范围暴力,大范围二分判定

G题#

查询区间内每个数的个数

莫队板子题,只进行区间查询不进行修改

H题待补#

F题#

被教育了二分(考虑二分的值然后去推一下式子)

G#

题教育树上利用dfs序压成一维然后再利用数据结构进行维护,,,,

H题为容斥原理,,,容斥原理的实现方式一般为dfs#

D题#

寻找区间内所有数都出现偶次数,,,,考虑把每个数都处理成一个二进制位这样当他们异或起来如果是偶次那么异或和为0,因此预处理异或和,统计次数然后枚举端点即可( 哈希异或 前缀和)

E题#

神秘的一个期望公式 (高中数学没学好属于是)暴力枚举然后算贡献,

F题#

数位dp思想变成前缀和相减然后 在这个区间上暴力枚举就可以了(注意前导0)

G题#

并查集,图上连通块合并,,直接find就好了为什么要弱智的去找到子节点然后接到这个连通块上呢

H题待补#

D题#

暴力发现题目给到m的最大是1e12 因此因子最大不会超过1e6所以只要暴力枚举因子记好了(多看看数据范围想想为什么是1e12)

E题#

(看出了跑环但是不会实现)因此学习了tarjan算法求强连通分量基本思想就是打时间戳然后跑dfs树看看是不是反祖边然后回溯连块

F题#

(只看出了如果有两个数字相同一定是YES因为我可以通过交换让最后只剩下两组不同,然后再让他们交换即可) 而这题还考虑到了逆序对考虑逆序对的奇偶是否相同(以前见过类似题判断奇数码的两个局面能否移动到)如果数组中元素两两不同，则每次交换一定会改变两个数组中逆序对的奇偶性

G题#

计算几何 首先如何判断一个点是否在一个多边形内部题目给出的逆时针的向量因此考虑一个点与逆时针向量的关系如果一个点在所有逆时针向量的左侧那么这个向量就是在这个多边形的内部对于本题因为是凸多边形可以判断两条即可 可以用叉积来考虑如果叉积为正说明在左侧（右手定则）为0说明共线 共线时再用数量级判断是否在线段上 本题只需要把所有点sort一下然后扫描线扫过去更新上边界和下边界然后判断即可**(叉积可以判断点在向量的那侧)**

H题待补#

E题#

暴力跑就好了当时似乎弱智了

F题#

暴力枚举边,枚举这个长方形的边长 然后容斥去算在这个长方形的概率(卡容斥了)

G题#

博弈论(补前狠狠恶补了一下https://blog.csdn.net/strangedbly/article/details/51137432) sg函数简单应用打表找规律记好了

H题待补#

F题#

(神秘题)一直想不到nlog做法简单的思路就是预处理好每行每列的和然后枚举每一行然后去找最大的列(而在这里就会产生问题在这个点重复算的问题) 因此把这n个点单独拎出来就是行列的焦点有值的情况直接暴力更新答案(On)然后我们枚举每行可以把每列的总和扔到set里然后从后遍历如果枚举这个列和行的焦点有值就跳过,遇到第一个没值就更新答案break然后下一行所以最多只会跳过N次所以时间复杂度是nlogn(所以为什么对操作有影响的点不单独拿出来算呢)

G题#

看到数据量感觉记忆化dfs能过 (传五个参数上边界下边界左边界右边界和切几刀)很明显下一个状态就是横切一刀或者纵切一刀这时候枚举两块切的刀数，dfs返回的是块里的最大值很显然我们应该每次状态一直取min最大的最小，然后枚举每一小块dfs跑一遍包含这块的的方案里M的最小值然后一直更新答案就好了（注意有0所以初始化的时候记忆数组不要赋为0，会T一个点 nnd找了半天才找到）

H题待补#

F题(DP)#

首先要考虑一个问题就是如何不重复的拿,建一个next[ i ] [ j ]表示在第i个位置到最后一个j+'a'字母第一次出现的地方 当后面没有这个字符则值为无穷大,然后我们取子序列第一个T(p1 p2 p3...pn)的字符时p1取next[1] [j] (j为从0枚举到26)然后p2取next[p1] [j] 以此类推 第一个子序列T(q1 q2 q3...qn) q1取next[pn] [p1]以此类推 这样可以保证每次取出来的字符串不会重复.接下来我们要怎么算所有的子序列串 定义dp[i] [j]状态为以s[i]为pn s[j]为qn的方案数 容易得到状态转移方程f[next[i+1] [c]] [next[j+1] [c]]=f[next[i+1] [c]] [next[j+1] [c]]+f[i] [j]. 首先枚举pn的位置,然后把p1 q1初始化(即在范围内 p1<=i &&q1<=n)就可以

G题#

单调栈只要当前元素比栈顶元素小切栈顶元素后面还会再出现就pop

H题待补#

E题#

注意扔到1一直是一样的对与一个数n来说 n=1/6(n,n2,n3,n4,n5,n6) 化简 n=1/5(n 2,n 3,n 4,n 5,n 6)所以转移的时候直接去掉1就可以了然后记忆化搜索或者dp即可解决

F题#

首先显然的是去掉的x应该是连续的而且肯定是在第一个循环的串里,所以枚举开始去掉x的位置然后计算一下o的长度一直更新就好了

G题,#

打表可以得100以内的质数只有25个,如果暴力枚举这个p个质数的值数为多少以最大范围可以看出为2e9这是会tle了那么需要更加高效的搜索方式(折半搜索)(开两个数组,一个数组存一些质数的指数相乘的结果,另一个存剩下的注意控制两个数组的长度应差不多)那么很显然最终的结果可以由两数组相乘得到,所以排序一下二分即可直接计算答案

(折半搜索样例https://zhuanlan.zhihu.com/p/112563549);#

H题 ....#

F题#

做法<算贡献> 首先直接算没有这个类型的很难算,因此转化为总的方案数-这个类型的数量,DDoS 里面的DD是不好算因此先反转字符串算SoDD

遍历枚举每个位置如果当前位置是小写字母或者问号

记总的问号数量为tot;

当目前遍历到位置出现了So算完即可直接退出(由下面计算贡献的方式可以看出)

(1)So的种类 如果当前位置的前一个开始的大写字母后面都没有出现小写字母则形式是rrrrrRRRRR

记当前的?数量为now 记第一次出现大写字母和最后一次出现小写字母(除当前位置)之间的的问号数量为k(当目前还没有出现大写字母时候k为当前位置前一个到 最后一次出现小写字母的问号数量)

显然填充的方案是当前位置是小写字母,最后一次小写字母之前都填小写字母,第一次大写字母之后都填大写字母,之间的部分也填写成rrrRRR的形式

因此当已经出现过大写字母的方案数为 未出现大写字母的方案数为 (2)DD的种类

1)如果后面已经出现了两个相同的字母则 方案数为 2)我们直接算的话很难算 同样考虑用总的方案去减掉不合法的

记后缀中大写字母未出现的种类有d种

我们要的是不合法的,所以后面的问号只能填小写字母或者这d个字母出现一次

我们可以枚举后面问号中 出现d中几个大写字母,其他填小写字母

​ 所以 不合法的方案数为 因此DD的方案数为

G题#

做法暴力枚举, 先拿到每个点对所产生的直线(除两点x相等),然后处理一下每条直线会有多少点在上面,再枚举两条直线的交点如果交点(x<0)然后就在这个点上加上贡献,遍历所有的点更新答案即可

H题 无#

F题 Merge Set#

有两个相同元素的集合可以合并，就是两个集合之间有边，因此本题相当于就是建边然后从包含1的集合开始bfs跑到包含n的集合

G题 Sort from 1 to 4#

置换环,与平时排列的不同这里有重复数字不同所以环的大小方案也有很多,因为要交换次数最少显然我们应该先把环长最少的先用掉,这题只有1到4 所以环长最多为4 直接枚举计算即可

F题#

由于不知道回合数所以可以考虑倒着来，即从H<0 的前一天开始考虑很显然这一天应该考虑用d最大的

然后倒二天应该用两天内产生伤害最大的，直到H减小到0，这种对于时间我们可以先按时间排序，然后维护一个后缀的d最大值，来得到当前时间使用那个造成的伤害最大

G题#

区间DP可以先从爆搜开始想转移方程，DP的定义是在当前区间先手产生的价值为X后手为Y，X-Y的最大值，然后用ST表加快一下就可以了

F题#

我们可以先对第一位考虑一下期望，首先期望公式$E(x)=\sum_{i=1}^{k}P_{i}*a_{i}$ 其中$k$ 是包含这个位置所有区间数

因此可以得到期望就是这个数乘以是这个数的概率

也就是说先拿到所有包含这个位置的操作 这个操作对这一位的期望的贡献就是这一位选他后面的操作都不选他的概率 乘以$x$

那么期望的式子就等价于每次操作$E(i)=E(i)*\frac{len-1}{len}+x*\frac{1}{len}$

那么我们现在来考虑整体，也就是说每次操作我们需要一个区间乘和区间加操作，这不是经典线段树

所以使用线段树维护一下，最后把tag都下传一下就是答案了

D题 Synchronized Players#

如果不是两个点一起移动，对两个点同时做bfs即可，一起移动我们依旧考虑bfs，把两个的坐标当作状态一起bfs即可

时间复杂度$n^{4}$

F题 Product Equality#

对数字进行哈希，可能冲突使用双哈 时间复杂度为$n^{2}log$

G题 Alone#

首先这个询问区间个数问题，一般都是枚举一个边界，然后log去算另一个边界的贡献

我们枚举左边界，很显然的发现贡献其实是右边每个数字种类，第一次出现和第二次出现的区间大小

也就是说我们需要维护一个区间加+1，区间-1，然后查询区间中>0数的个数

对于这个来说正常做如果tag不传到底是不对的，所以复杂度不对

这里我们可以发现一个小性质就是数的值>=0 也就是说，我们只要维护区间最小值以及最小值的个数

然后就可以做了

G - Go Territory#

题意就是四联通, 然后和 $(−1,−1)$ 不联通的点的个数, 暴力的来说我们把每个点都使用并查集联通,然后判和 $(−1,−1)$ 是否在同一连通块即可, 但是这样的点数很多,考虑一行把连续白点缩成一个点, 这样点数是 $O(n)$ 的

具体实现的话可以用 $map$ 套 $vector$ ,这样把一行来缩点, 同时注意应该把上下两行都存下来,然后双指针并查集即可

F - Palindromic Expression#

考虑一下最终的答案的结构 让表示翻转后得到的数字

• $n$
• 表达式$x∗$ $(表达式)∗$rev(x)$

对于第二种可以发现我们可以暴力枚举 $n$ 内的因子来$check$是否有解

复杂度为$\sqrt{n} * n$ 的因子个数 但是大部分实际跑不满

因此只需要暴力搜就行

F - Maximum Composition#

首先考虑对于k个p如何排列比较优，类似于国王游戏，使用微扰法，尽交换两个其他不变，即$f_i f_j (x)$和$f_j f_i(x)$ 那个的值大，化简式子即可得到$\frac{a_i - 1}{b_i}$ 越大放在外面越优，所以先排序后，然后dp的去选k个即可

G - Lexicographically Smallest Permutation#

排列交换，容易发现这是一个置换环，那么在一个置换环内要让某一个位置排在第一个就会有一个限制

我们定义操作次数 $X$ 环长$L$ , 第$i$ 个点放第一个的条件就是 $X ≡ i\, (mod\, L)$

我们贪心的考虑肯定是从左到右的置换环 依次最优， 也就是说当前这个同余条件要和之前的同余方程有解，这个东西就是$exgcd$ 就可以判断， 然后利用中国剩余定理把同余方程合并起来， 但是一直取$lcm$ 会爆__int128,所以不能这么做， 有两种做法

做法1：不合并同余方程，考虑到不同的$L$ 至多只有 $\sqrt{n}$ 个所以暴力每个$check$ ， 复杂度是$n \sqrt{n} logn$

做法2：考虑中国剩余定理的过程

考虑两个同余方程

$X ≡ i\, (mod\, L_i)$

$X ≡ j\, (mod\, L_j)$

有解的条件是 $gcd(L_i, L_j)|(i-j)$ ,所以限制条件变成$i ≡ j\, (mod\, gcd(L_i, L_j))$

所以我们存下因数位置的限制 或者 $p^k, p \in Prim$ 位置的限制然后每次去check即可

F - Knapsack with Diminishing Values#

完全背包，但是每次选择有限制，朴素的方法是$n m^2$的复杂度，考虑到第三层循环枚举选的个数的时候是个类似调和级数的东西，也就是说如果每个物品的重量都不一样，那么复杂度就是$m^2 logm$ ，所以我们考虑把同一重量的物品一起考虑，那么我们就要考虑一个东西就是选择$k$个重量的物品的最大价值怎么计算，很显然直接贪心，每次记录一下增加价值和选了多少次，然后用优先队列就可以处理好了

E - Sensor Optimization Dilemma 2#

首先很自然想到二分答案，然后考虑如何check，也就是取到这个二分值的最少花费，一个很显然的贪心就是取性价比高的那个，假设$a_i * q_i \ge b_i * q_i$ 就是A物品的性价比比较高，那么B物品买的数量不会超过$lcm(a_i, \, b_i) / b_i$ 因为每多这些都可以用A物品来替换达到更低的花费，$lcm(a_i, \, b_i) / b_i$ 不会超过$100$ 所以暴力枚举B物品买了几个即可

E - Permute K times 2#

我们将 $i$ 和 $p_i$ 连边，那么 $i$ 出边的方向就是 $p_i$ 的值，对着样例画一下图可以发现，执行 $k$ 次操作，其实就是在环上走 $2^k$ 步，其实就是因为在你走的时候，你的下一个点的出边也走了所以每次是一个 $\times 2$ 的过程