题解atcoder agc 004

首先可以想到有组合数的方法： 令起点为 $(x1, y1)$，终点为 $(x2, y2)$，则路径方案数就为 $\binom{x2 + y2 - x1 - y1}{x2 - x1}$，这样设有 $k$ 个相同颜色的点，时间复杂度就为 $O(k^2)$。 再考虑到还有 $\text{DP}$ 方法： ......

[洛谷链接](https://www.luogu.com.cn/problem/AT_arc113_c)&[Atcoder 链接](https://www.luogu.com.cn/remoteJudgeRedirect/atcoder/arc113_c) 本篇题解为此题**较简单做法**及**较少 ......

[洛谷链接](https://www.luogu.com.cn/problem/AT_abc182_d)&[Atcoder 链接](https://www.luogu.com.cn/remoteJudgeRedirect/atcoder/abc182_d) 本篇题解为此题**较简单做法**及**较少 ......

[重建](https://www.luogu.com.cn/problem/P3317) ### 题目大意 给定一张无向图，第 $i$ 条边存在的概率为 $p_i$，求这个无向图是一颗树的概率。 ### 思路分析 所求即为： $$\sum_{T}\Bigg(\prod_{e\in T}p_e\Big ......

[Lucky Array](https://www.luogu.com.cn/problem/CF121E) ### 题目大意 维护一个序列，支持以下操作： - 区间加一个大于 $0$ 的数。 - 区间查询有多少个数位上只包含 $4$ 或 $7$ 的数。 ### 思路分析 看起来很不可做，但考虑到题 ......

## 1.题目大意 有一个复杂的虎穴包括了 $N$ 个节点(编号为 $0$ 至 $N-1$ )和 $M$ 条无向的通道 其中通道 $i（0 \leq i $指定一个权值$f(X,Y)$，注意，$f(X,Y)$ 不等于 $f(Y,X)$； 在一个节点，小强选择未被封锁的权值最小的通道逃生，直到到达出口 ......

## Description 给定正整数 $N$，和两个长为 $N$ 的 $01$ 序列 $a$ 和 $b$。定义一次操作为： 1. 将 $b$ 序列中的一个值翻转（即 $0$ 变成 $1$，$1$ 变成 $0$，下同）。 2. 对于 $b$ 序列中每个值为 $1$ 的位置，将 $a$ 序列中对应位 ......

[TOC] # 题目链接 [CF938G](https://www.luogu.com.cn/problem/CF938G "CF938G") 洛谷挂了 只能交CF # 题目分析 本题有以下几个关键点： ## 为什么使用生成树建树 首先 根据 $WC2011$ 我们发现可以使用 $dfs$ 序来保存 ......

UVA10702 Travelling Salesman 题解 题面： 有个旅行的商人，他每到一个的新城市，便卖掉所有东西再购买新东西，从而获得利润。从某城市 A 到某城市 B 有固定利润（B 到 A 的利润可能不同）。已知城市可以重复到达，从 S 点出发，经过 T 个城市，有 E 个城市能作为终点 ......

# 前言 还是一道神仙题 很难想 # 题面 luogu上copy的 样例解释懒得翻，我觉得应该都看得懂样例吧。 ## 题面翻译 现有一棵 $n$ 个点的形态未知的树，给定其长度为 $2n-1$ 的欧拉序的一部分 请根据给出的残缺的欧拉序还原出一个完整的欧拉序或判断不存在这样的树 输入中用非零数字表示 ......

一、题目描述： 用 $f_i$ 表示斐波那契数列的第 $i$ 项，那么有： $ f_0=0,f_1=1;f_n=f_{n-1}+f_{n-2},n\ge2 $ 现在有一个 $n$ 行 $m$ 列的数字表格，第 $i$ 行第 $j$ 列的数字是 $f_{\gcd(i,j)}$ 。 求这个表格所有数的乘 ......

看到 $n\le 10^{11}$，考虑按根号分为两部分处理。 对于 $b\le \sqrt{n}$，考虑直接暴力算 $\operatorname{f}(b, n)$ 判断是否等于 $s$，这部分的计算量是 $O(\sqrt{n})$ 级别的。 对于 $\sqrt{n} n$，这个时候 $\oper ......

题目传送门：[luogu P2324 [SCOI2005] 骑士精神](https://www.luogu.com.cn/problem/P2324) # 题意  # 分析 数据范围比较小，适合搜索 ......

[Minimum Xor Pair Query](https://www.luogu.com.cn/problem/AT_abc308_g) ### 题目大意 维护一个序列，支持动态插入，删除，查询最小异或对。 ### 思路分析 看到查询最小异或对首先想到 01Trie，但 01Trie 不支持删除 ......

[Counting Grids](https://www.luogu.com.cn/problem/AT_arc143_b) ### 题目大意 将 $1\sim n^2$ 填入 $n\times n$ 的网格 $A$ 中，对于每个格子满足以下条件之一： - 该列中存在大于它的数。 - 该行中存在小于 ......

[toc] # 网络流24题 顺序主观决定 ## [太空飞行计划](https://www.luogu.com.cn/problem/P2762) 教训：(开始想费用流，搞半天出不来) **网络流解决最大/小费用问题，要么最小割最大流，要么最小费用流** **最小费用流的前提是最大流**，所以在** ......

[洛谷链接](https://www.luogu.com.cn/problem/AT_abc178_d)&[Atcoder 链接](https://www.luogu.com.cn/remoteJudgeRedirect/atcoder/abc178_d) 本篇题解为此题较**简单做法**及**较少 ......

[传送门](https://www.luogu.com.cn/problem/P5369) ### 题目大意 给定一个序列，求任意重排 $n!$ 中情况所以的最大非空前缀和的和。模 $998244353$。 $n\e 20$，$\sum |a_i| \le 10^9$ ### 题目解析 考虑最大前缀 ......

[洛谷链接](https://www.luogu.com.cn/problem/AT_arc041_b)&[Atcoder 链接](https://www.luogu.com.cn/remoteJudgeRedirect/atcoder/arc041_b) 本篇题解为此题较**简单做法**及**较少 ......

1. SpringBoot整合JSP 参考：SpringBoot | 稀客大大 (heyige.cn) 导入依赖 <!--JSP核心引擎依赖--> <dependency> <groupId>org.apache.tomcat.embed</groupId> <artifactId>tomcat-e ......

[洛谷传送门](https://www.luogu.com.cn/problem/P8161) ## 1.题意简述： 一个学期有 $N$ 天 $N*M$ 节课，每天的第 $i$ 节课可以选择效果 $a_i$ 的学习与 $b_i$ 的自习。问应如何安排每节课，使所有功课最小值最大？ ## 2.思路： ......

原题：[P9474 [yLOI2022] 长安幻世绘](https://www.luogu.com.cn/problem/P9474 "P9474 [yLOI2022] 长安幻世绘") 看到很多大佬的题解直接讲了做法，本蒟蒻看得不是很懂，调了很久才把这题做出来，于是写了这篇比较详细的题解谈一下我做这 ......

[洛谷链接](https://www.luogu.com.cn/problem/AT_agc017_b)&[Atcoder 链接](https://atcoder.jp/contests/agc017/tasks/agc017_b) 本篇题解为此题较**简单做法**，请放心阅读。 ## 题目简述 一 ......

[洛谷链接](https://www.luogu.com.cn/problem/AT_arc149_a)&[Atcoder 链接](https://atcoder.jp/contests/arc149/tasks/arc149_a) 本篇题解为此题较**简单做法**及**较少码量**，并且码风优良， ......

[洛谷链接](https://www.luogu.com.cn/problem/AT_arc154_b)&[Atcoder 链接](https://www.luogu.com.cn/remoteJudgeRedirect/atcoder/arc154_b) 本篇题解为此题较**简单做法**及**较少 ......

题目链接 P2894 [USACO08FEB] Hotel G - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 分析 考虑用线段树维护区间信息 维护sum（最大连续空房间数） 如何合并？ sum1为max（sum2，sum3）（1的两个子区间） 但我们发现若区间为100 001（0 ......

[题目链接](https://www.luogu.com.cn/problem/P9450) 这年 WF 较为简单的一道了，直接模拟即可。首先可以预处理出它顺时针螺旋轨迹的移动步数，方便过会算距离直接查表。我偷懒直接用 map 记录的距离表，这样不用处理复数下标的问题。注意到 $X$ 的数量不会超过 ......

Problem StatementYou are given a set $S$ of strings consisting of 0 and 1, and an integer $K$. Find the longest string that is a subsequence of $K$ or ......

# 前言 这是一道神仙题 我翻阅的很多分题解，包括Atcoder官方题解 都没有看懂，应该是因为我比较菜 然后我看懂了这篇(地址放在文末) 方法可能和主流略有不同 但我觉得这个办法更好理解 # 题面 ## 题面大意 定义一个单独的节点为一棵Uninity 0的树。 将$x(x \geq 0)$棵Un ......

赛时过了 A-E，然后就开摆了，为什么感觉 C 那么无厘头[发怒][发怒] 排名：25th ## A.Game with Board ### 题目描述： Alice 和 Bob 玩游戏，他们有一块黑板。最初，有 $n$ 个整数 $1$。Alice 和 Bob 轮流操作，Alice 先手。 轮到时，玩 ......