AT_abc

AT_abc325_f Sensor Optimization Dilemma 题解 Date 20231025：修复手滑公式 \(\min\)、\(\max\) 写反了。 动态规划。类似背包问题。 朴素算法 记 \((x,y)\) 表示使用 \(x\) 个 (1) 传感器、\(y\) 个 (2) ......

AT_abc326_e Revenge of "The Salary of AtCoder Inc." 题解 一道简单的概率论+动态规划题目（然而我赛时没看这道题 题意 有一个长度为 \(n\) 的序列 \(A\)、一个 \(n\) 面骰子，掷若干次骰子，如果这一次掷骰子的点数小于等于上一次的点数， ......

好久没打 abc 了，久违的 rated 一场比赛，结果被 D 创飞了。 \(9\) 分钟把 ABC 题切掉，然后看 D 题，觉得是个简单的模拟，错了 \(5\) 次，直接把我人整懵了，一看题目 字符a,b,c只出现一次，我以为是 字符a,b,c至少出现一次，妈妈生的。 E 求期望，有个很显然的东西 ......

给出 n 对点 ai ,bi ，在[1,m] 之间取一段区间。 当每一对点都有一个点在这个区间内时，这个区间合法。 求出不同长度的合法区间分别有多少个。 枚举 l, 右边r有个最小值R(l)， 而 (l, j) j>r 之后的点都是合法点, 后面就是区间加，用差分维护 考虑这个 R (l) ， 可以 ......

目录题目翻译题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1样例 #2样例输入 #2样例输出 #2样例 #3样例输入 #3样例输出 #3题目简化题目思路AC代码 题目翻译 【题目描述】 你决定用素数定理来做一个调查. 众所周知, 素数又被称为质数，其含义就是除了数字一和本身之外不能被其 ......

简述题意 这什么破翻译，看了 AtCoder 的英文才看懂。 给定一个长度为 \(n\) 序列 \(a\)，要求构造一个数列 \(b\)，使得对于任意 \(i\)，满足： \(1 \le i \le n\) 将 \(b\) 序列下标为 \(i\) 的倍数的值相加使得这个总和模 2 等于 \(a_i\ ......

AT_abc301_h [ABC301Ex] Difference of Distance 更好的阅读体验 一道基础图论，很好口胡，但是实现不太简单。 考虑离线，把询问挂在边上，按边权从小到大处理。 处理到一个边权时，把边权小于它的边的两端用并查集合并，对于等于这个边权的边在并查集上建图，跑一边 t ......

01bfs 跑完d1 ,d2 ( 单源最短路 枚举 中间点（去掉的点 #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <map> using namespace std; con ......

思路 定义 \(dp_i\) 表示将前 \(i\) 个分为若干段的价值总和。容易得到状态转移方程： \[dp_i = \sum_{j = 1}^{i - 1}{dp_j \times (\max_{k = j + 1}^{i}\{a_k\} - \min_{k = j + 1}^{i}\{a_k\} ......

思路 定义 \(dp_i\) 表示将前 \(i\) 个分为若干段的价值总和。容易得到状态转移方程： \[dp_i = \sum_{j = 1}^{i - 1}{dp_j \times (\max_{k = j + 1}^{i}\{a_k\} - \min_{k = j + 1}^{i}\{a_k\} ......

# 思路 简单动态规划，$dp_i$ 指当前操作后取和为 $i$ 的球的方案数，每次输出 $dp_K$ 即可。 需要注意的是对于每次 `+ x` 操作，计算 $dp$ 数组时要倒着循环。 时间复杂度：$O(QK)$。 # 代码 ```cpp#include<bits/stdc++.h>using n ......

题解 \(dp[i]\) 表示长度为i的格子的合法涂色数，考虑第 \(i\) 个怎么放 第 \(i\) 个前面 \(k-1\) 个位置有2种颜色，则第 \(i\) 个位置只能放这两种颜色中的一种 用合法方案减只有一种的方法，即得两种颜色的方案数 而只有一种颜色的方案数，等于 \(f[i-k+1]\) ......

思路 题目要求的是 \(\max_{a = 1}^{n}\{\sum_{i = 1}^{a}\sum_{j = 1}^{a}{A_j}\}\)，所以我们将 \(\sum_{i = 1}^{a}\sum_{j = 1}^{a}{A_j}\) 化简一下，得： \[i \times A_1 + (i - ......

思路 首先我们可以发现，在任意一个节点数量大于 \(1\) 的强连通分量中的点都满足条件。 所以，我们可以对这张图跑一边 TarJan。 但是这样是错的，因为我们还需要考虑节点数量为 \(1\) 的强连通分量。 如果这种连通分量能够到达任意一个节点数量大于 \(1\) 的强连通分量，那么，这个连通分 ......

打篇题解巩固一下。 题意 给你两个集合 \(A\) 和 \(B\)，对于任意 \(A\) 集合中的元素，我们可以进行 \(2\) 种操作：\(a_i\gets \left\lfloor\frac{a_i}{2}\right\rfloor\) 或 \(a_i\gets 2\times a_i\)。问最 ......

好题，考场上想到做法了，没写出来，被薄纱了，记录一下。 主要是做的比较顺一下就想到了。 我们先转换一下 \(f\) 函数 \(f(S,a,b)=\sum\limits_{i=1}^k S_i\times (a^{k-i}-b^{k-i})\) 我们可以发现对于位数 \(>2\) 的，一定满足 \(a ......

目录题目翻译题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1样例 #2样例输入 #2样例输出 #2样例 #3样例输入 #3样例输出 #3题目简化题目思路AC代码 题目翻译 【题目描述】 你决定用素数定理来做一个调查. 众所周知, 素数又被称为质数，其含义就是除了数字一和本身之外不能被其 ......

神仙题 看到没人交题解，我来交一发。 \(Part\ 0:\)我瞎扯扯 我做这题时想着先把耗费魔法值为负的做掉，然后最后再做一段魔法值为正的，但是不好做，做不了。 这个东西也贪心不了，因为你魔法值和伤害这两个东西拆不开，然后就什么都做不了了。 本篇题解中没有什么心路历程，又不能分析出什么动机，因为笔 ......

这个题其实和之前 \(NFLS\) 一道题很像，但是还是没做出来，因为当时漏了一个点没注意到，这次赛时就暴毙了。 首先很显然的是拆贡献，寻找每个连通块构成的可能贡献。 期望不好算，我们转成概率乘价值，再转成 \(\frac {\text{方案数}}{\text{总方案数}}\times value\ ......

AT_abc321_f [ABC321F] #(subset sum = K) with Add and Erase 题解 题目大意 现在有一个空箱子。给你两个数 \(Q, K\)，然后给你 \(Q\) 行，每一行代表一个操作： \(+ x\)，即向箱子里加一个权值为 \(x\) 的小球。 \(- ......

一、题目描述： 给你四个整数 $N,A_1,A_2,A_3$。求满足以下条件的正整数三元组 $(X_1,X_2,X_3)$ 的数量。 对于 $i\in [1,3],A_i\mid X_i$ 且 $X_1\oplus X_2\oplus X_3=0$。答案对 $998244353$ 取模。 数据范围： ......

一、题目描述： 有 $n$ 个人，第 $i$ 个人一开始有 $a_i$ 个球。每个人都有一个自己的传球目标。 有一个正整数 $k$，从 $1\sim k$ 中随机选择一个数作为游戏的进行轮数。 在游戏的每一轮，所有人同时都把自己手上的球全部传给自己的传球目标。 求游戏结束之后，每个人手上的期望球的数 ......

# AT_abc318_e Sandwiches 题解 ## Links [洛谷](https://www.luogu.com.cn/problem/AT_abc318_e) [AtCoder](https://atcoder.jp/contests/abc318/tasks/abc318_e) # ......

# AT_abc318_d General Weighted Max Matching 题解 ## Links [洛谷](https://www.luogu.com.cn/problem/AT_abc318_d) [AtCoder](https://atcoder.jp/contests/abc31 ......

# AT_abc318_c Blue Spring 题解 ## Links [洛谷](https://www.luogu.com.cn/problem/AT_abc318_c) [AtCoder](https://atcoder.jp/contests/abc318/tasks/abc318_c) ......

## Part I Preface - [原题目$\text{(Luogu)}$](https://www.luogu.com.cn/problem/AT_abc106_c) - [原题目$\text{(AtCoder)}$](https://www.luogu.com.cn/remoteJudge ......

## Part I Preface - [原题目$\text{(Luogu)}$](https://www.luogu.com.cn/problem/AT_abc106_c) - [原题目$\text{(AtCoder)}$](https://www.luogu.com.cn/remoteJudge ......

## Part I Preface - [原题目$\text{(Luogu)}$](https://www.luogu.com.cn/problem/AT_abc106_b) - [原题目$\text{(AtCoder)}$](https://www.luogu.com.cn/remoteJudge ......

## Part I Preface - [原题目$\text{(Luogu)}$](https://www.luogu.com.cn/problem/AT_abc106_a) - [原题目$\text{(AtCoder)}$](https://www.luogu.com.cn/remoteJudge ......

#### [题目链接](https://www.luogu.com.cn/problem/AT_abc182_e) ## 思路 说实话，这道题其实算模拟，还是挺简单的那种。我们可以定一个 int 类型的二维数组，表示网格。通过不同的数字来表示该方格内不同的类型。然后，使用枚举法模拟网格内灯泡从**上 ......