ARC
AT_arc113_c 题解
[洛谷链接](https://www.luogu.com.cn/problem/AT_arc113_c)&[Atcoder 链接](https://www.luogu.com.cn/remoteJudgeRedirect/atcoder/arc113_c) 本篇题解为此题**较简单做法**及**较少 ......
Atcoder ARC060D Digit Sum
看到 $n\le 10^{11}$，考虑按根号分为两部分处理。 对于 $b\le \sqrt{n}$，考虑直接暴力算 $\operatorname{f}(b, n)$ 判断是否等于 $s$，这部分的计算量是 $O(\sqrt{n})$ 级别的。 对于 $\sqrt{n} n$，这个时候 $\oper ......
[ARC143B] Counting Grids 题解
[Counting Grids](https://www.luogu.com.cn/problem/AT_arc143_b) ### 题目大意 将 $1\sim n^2$ 填入 $n\times n$ 的网格 $A$ 中，对于每个格子满足以下条件之一： - 该列中存在大于它的数。 - 该行中存在小于 ......
AT_arc041_b 题解
[洛谷链接](https://www.luogu.com.cn/problem/AT_arc041_b)&[Atcoder 链接](https://www.luogu.com.cn/remoteJudgeRedirect/atcoder/arc041_b) 本篇题解为此题较**简单做法**及**较少 ......
AT_arc149_a 题解
[洛谷链接](https://www.luogu.com.cn/problem/AT_arc149_a)&[Atcoder 链接](https://atcoder.jp/contests/arc149/tasks/arc149_a) 本篇题解为此题较**简单做法**及**较少码量**，并且码风优良， ......
AT_arc154_b 题解
[洛谷链接](https://www.luogu.com.cn/problem/AT_arc154_b)&[Atcoder 链接](https://www.luogu.com.cn/remoteJudgeRedirect/atcoder/arc154_b) 本篇题解为此题较**简单做法**及**较少 ......
AT_arc157_a 题解
## 思路 看数据范围时能发现，这 $N$ 啥用也没有，因为 $A+B+C+D=N-1$。 首先，$B$，$D$ 为 $0$ 且 $A$，$C$ 为 $0$ 的情况是不可能有的，因为既然有 `XX` 和 `YY` 字符串，那么一定会至少组成一个 `XY` 或 `YX`，输出 `No`； 然后，$\l ......
[ARC150F] Constant Sum Subsequence
Problem StatementWe have a sequence of positive integers of length $N^2$, $A=(A_1,\ A_2,\ \dots,\ A_{N^2})$, and a positive integer $S$. For this sequ ......
Atcoder ARC058E Iroha and Haiku
题目中的式子转化一下即存在一位 $i$ 使得到 $i$ 时的后缀和存在 $X + Y + Z, Y + Z, Z$，再发现 $X + Y + Z\le 17$，考虑状压。 设 $f_{i, j}$ 为填了 $i$ 个数当前后缀和中存在的数的状态为 $j$（只存 $0\sim X + Y + Z$ 的 ......
ARC134F Flipping Coins
pb 讲课没讲的题，感觉很牛逼啊！但不是牛逼在多项式，因为多项式大家应该都会。 考虑从前往后扫的过程，只要有正面就翻成反面，所以最后只有可能是当 $p_i #define int long long using namespace std; namespace vbzIO { char ibuf[( ......
Atcoder ARC058B Iroha and a Grid
考虑从第 $b$ 列与第 $b + 1$ 之间分开这个矩阵，钦定 $(i, b)$ 下一步必须走到 $(i, b + 1)$，可以发现这样是不会漏算或算重的。 于是就可以用乘法原理算出这个 $i$ 的贡献：$\binom{(i - 1) + (b - 1)}{i - 1}\times \binom{ ......
ARC125F Tree Degree Subset Sum
感觉挺不错的一道题，不过课上 pb 好像没有讲。 显然树的具体形态对题目影响不大，那么我们知道 $\sum\limits_{i=1}^nd_i=2n-2$ 即可扔掉树的条件。即： > 给定 $n$ 个 $d_i$，和为 $2n-2$，求 $(x,y)$ 满足 $0\le x\le n$ 且 $\ex ......
AT_arc101_d [ARC101F] Robots and Exits 题解--zhengjun
思路不错。 首先考虑把每个机器人转化为 $(a_i,b_i)$ 两个参数。 表示向左 $a_i$ 步会进入左边的出口，向右 $b_i$ 会进入右边的出口。 > 注：此时其他只能进入唯一的出口的机器人不影响答案，不考虑。 记 $c_i=0/1$ 表示 $i$ 号机器人是进入左边还是右边出口。 然后考虑 ......
ARC163D Sum of SCC
### Description 给定 $N,M$，求对于所有 $N$ 个点的，满足恰有 $M$ 条从小连向大的边，即 $\sum\limits_{(u,v)\in E}[u 给竞赛图每个 SCC （强连通分量）缩点后，剩下的是由一条**极长**的链与某些前向边组成的图。 于是 SCC 的数量能够转换 ......
ARC098D Donation
捐钱太亏了，我们倒序考虑，于是就变成了抢钱。 于是对于一个点的限制 $(a_u,b_u)$，令 $c_u=\max\{0,a_u-b_u\}$，表示到这个点之前你至少拥有的钱数，并且到了这个点之后会抢到 $b_u$ 的钱。 考虑建立 $\text{Kruskal}$ 重构树使得树上每条边 $fa_u ......
[ARC104E] Random LIS 题解
# [ARC104E] Random LIS 题解 [Link](https://atcoder.jp/contests/arc104/tasks/arc104_e) 吐了，一下午就写了这一个题……主要是题解都说的很草率。然后上课的时候貌似讲的方法不是很能做（也许是我太菜了），总之我得写篇题解整理整 ......
ARC154
[[ARC154A] Swap Digit](https://www.luogu.com.cn/problem/AT_arc154_a) 和一定差小积大，竟可能的使两个数差大即可。 复杂度 $O(n)$。 ```cpp #include using namespace std; typedef lo ......
ARC153
[[ARC153A] AABCDDEFE](https://www.luogu.com.cn/problem/AT_arc153_a) 第一眼看上去让人以为是数位 DP，但看一眼样例 2 就知道直接枚举就行了。 六层循环暴力枚举。 复杂度 $O(10^6)$。 [[ARC153B] Grid Rot ......
题解 [ARC153B] Grid Rotations
[[ARC153B] Grid Rotations](https://www.luogu.com.cn/problem/AT_arc153_a) 有思维含量的一题。 我们横纵坐标分开考虑，对于每一个矩形，每次操作会使其内部元素的横坐标上下对调。 纵坐标也同理，左右对调。 而这种反转操作我们显然可以直 ......
题解 AT3726 [ARC087B] FT Robot
首先可以观察到一个非常重要的性质：对于一次前进的操作，如果前面有奇数次转向，则走上下，否则走左右。（当然如果一开始就前进就只能走右） 于是我们可以将其拆成许多的“块”，并分成两类，即前进方向为左右还是上下。  [洛谷：[ARC162D] Smallest Vertices ......
ARC090E
果然自己想出来和看题解做出来是完全不同的感觉…… 首先考虑没有不相遇的限制条件怎么做。发现这个问题就是 P1144 再加上乘法原理。 然后思考如何处理相遇的情况。容易想到枚举相遇的点和边。首先从 $s$ 和 $t$ 开始各跑一遍最短路，$dis_{u,0/1},cnt_{u,0/1}$ 分别为点 $ ......
ARC126F Affine Sort
[题面传送门](https://www.luogu.com.cn/problem/AT_arc126_f) 感觉这种带个极限的题目都非常奇怪。 首先三个变量不好做，设 $g(k)$ 表示 $c=k$ 的情况下 $a,b$ 的值，那么我们要求的东西可以看成 $\lim\limits_{K\to \in ......
ARC147-做题记录
title: ARC147 做题记录 feature: false mathjax: true date: 2022-09-06 07:42:47 tags: - 贪心 - 计数 categories: 做题记录 cover: https://pic.imgdb.cn/item/6316994d16 ......
ARC133F FWT 做法
看见网上题解都是“二维生成函数”，就来传一下这个做法（ 问题可以转化为：$n$ 枚硬币，每次随机翻一枚，求最后正面朝上硬币个数的期望。 把这个过程看作 XOR 卷积，并且需要卷积的两个数组有特性：在 popcount 相同的位置值相同。 这样只要对这种特殊的数组能做 fwt 就做完了。 于是现在要解 ......
arc164_a Ternary Decomposition 题解
# [Ternary Decomposition](https://www.luogu.com.cn/problem/AT_arc164_a) ## 题意 共 $T$ 组数据，对于每组数据，给出两个整数 $n$ 和 $k$，问是否存在一个长度为 $k$ 的非负整数序列 $a$，使得 $\sum\li ......
ARC164 F
先进行一些转化。 每个点被翻转的次数固定，为其深度。（这里规定根节点的深度为 $0$） 所以每个人放颜色可以看做放什么得什么，而不需要考虑翻转。 先手选偶数层和后手选奇数层都会使得先手得分，反之不得分。所以先手和后手其实是一样的策略：尽可能选偶数层，而不选奇数层。 对于能够放颜色的点，一定是叶子，所 ......
[ARC164E] Segment-Tree Optimization
# [ARC164E] Segment-Tree Optimization 题目大意是让你构造一棵广义线段树，给定若干个询问使得询问出的区间最大深度最小并且最大神帝的个数最少。感官上，我们认为满二叉树很优美，所以可以朝着这个方向思考。 首先，不难看出有一些区间中所有数在所有询问中被绑在了一起，即要么 ......