题解166b arc
AT_agc019_b 题解
洛谷链接&Atcoder 链接。 题目简述 给定一个字符串 \(A\),可以选择区间 \([i,j]\) 翻转一次,求能得到多少本质不同的字符串。(\(A\) 的长度不超过 \(2 \times 10^5\))。 思路 首先解释本质不同的含义,即不完全相等的两个字符串(可能 \(A\) 是 \(B\ ......
P1989 无向图三元环计数 题解
P1989 无向图三元环计数 题解 考虑对无向图的边定向:对于每一条无向边,度数小的点向度数大的点连边,如果读书相等则按编号大小确定。 这样枚举一个 \(u\),再枚举它的出点 \(v\),接着枚举 \(v\) 的出点 \(w\),如果存在一个 \(w\),\(u\) 向它连边,那么 \((u, v ......
SOJ1835 题解
题意 给出一个 \(1,\dots,n+1\) 的排列 \(v_{1},\dots,v_{n+1}\) 与两组权值 \(a_{1,\dots,n},b_{1,\dots,n}\)。满足 \(v_{n+1}=n+1\)。 构造一张 \(n+1\) 个点的有向图: 对于 \(i=1,\dots,n\), ......
LOJ 6479 [ICPC World Finals 2017] 小小水管工 Son of Pipe Stream 题解
更好的阅读体验 题意 原题链接 给出 \(n\) 个城市和 \(m\) 条双向管道,以及两个实数 \(v\) 和 \(a\)。有两种液体,分别是水和 Flubber(下面简写为 W 和 F)。\(1\) 号和 \(2\) 号城市分别生产 Flubber 和水,并通过管道流入 \(3\) 号城市。对于 ......
题解 [HEOI2016/TJOI2016] 排序
题目链接 看到这道题按照套路首先想到二分答案(即二分 \(q\) 位置上的数,记作 \(mid\))。 再按照套路将大于 \(mid\) 的数字设为 \(1\),将等于 \(mid\) 的数设为 \(2\),小于 \(mid\) 的数字设为 \(0\)。 那么对于区间 \([l,r,0]\) 操作, ......
题解 CF1873H【Mad City】
其他题解怎么又 Tarjan 又 Dijkstra 的,这是 div4H 的样子吗,来个简单好写的做法。 题面里的人名太复杂了,本题解中称为警察和小偷。 注意到,如果小偷成功到达了环上,那么一定不会被警察抓到。因为小偷知道警察下一步会走到哪里,他可以执行相同的操作(顺时针/逆时针/静止),使得他和警 ......
[ARC135C] XOR to All 题解
include <bits/stdc++.h> typedef long long valueType; typedef std::vector ValueVector; constexpr valueType MAXB = 31; int main() { std::ios::sync_with_ ......
[ARC124C] LCM of GCDs 题解
题面 给定 \(N\) 个正整数对 \((a_i, b_i)\) 和两个初始为空的集合 \(S, T\),你可以选择将每个数对的两个元素划分到两个不同的集合中。求 \[\max\operatorname{lcm}(\gcd\limits_{x \in S}x, \gcd\limits_{y \in ......
ARC
ARC——run Adaptive Rotated Convolution for Rotated Object Detection (ICCV 2023)运行过程 Introduction This is the official implementation of the paper, Adap ......
P4370 [Code+#4] 组合数问题2-题解-有关对数的小技巧
20230927 P4370 [Code+#4] 组合数问题2-sol Statement 传送门 给你两个数 \(n,k\) , 要求对于组合数 \(C_{a}^{b}\) 找到任何 \(k\) 个, 让他们的和最大, 且组合数各不相同, 当且仅当 \(a,b\) 不完全相同时,组合数不同。 So ......
CF364D Ghd 题解
CF364D Ghd 题解 题目大意 给定一个长度为 \(n\) 的序列 ,你需要从中选出一个元素个数不少于 \(\left\lceil{\frac{n}{2}}\right\rceil\) 的子序列,使得这个子序列中所有元素的 \(\gcd\) 最大。 分析 数据范围吓人。 \(10^6\),但是 ......
[题解] CF1882D - Tree XOR
CF1882D - Tree XOR 知识点:换根 DP 。 主要难点是要思考如何操作使得代价最小,这个过程是一个贪心的过程。想到怎么操作,计算答案的过程就是一个板子换根了。 题意 给定一颗 \(n\) 个节点的树,点 \(i\) 具有权值 \(a_i\) 。现在需要你不断执行以下操作,使得树上所有 ......
[ARC125B] Squares 题解
题意 给定正整数 \(N\),求满足如下条件的正整数对 \((x, y)\) 的数量: \(1 \le x, y \le N\) \(x^2 - y\) 为完全平方数(\(0\) 也是完全平方数) (\(1 \le N \le 10^{12}\))。 题解 因为 \(x^2 - y\) 为完全平方数 ......
[题解] Codeforces Round 900(Div.3) E~F
Codeforces Round 900(Div.3) E~F E. Iva & Pav 因为按位与的结果不会随着越多数字的增加而增加,因此我们可以利用这个性质二分出右端点,只需要一个可以查询区间的数据结构即可。 或者是按位考虑第 \(i\) 个数字的第 \(k\) 位,后缀最近的 \(0\) 的位 ......
ACAM 学习笔记 | 附 YbtOJ 全部题解
怎么有人现在才学 ACAM 呢。 好像比 SAM 简单挺多啊,也不记得当时是哪里看不懂。 AC 自动机(✔) 自动 AC 机(✘) 概述 ACAM(Aho–Corasick Automaton),是用来解决多模式串匹配的字符串算法。它的结构是个 DAG,其中点表示状态,边表示转移。这一点上各种自动机 ......
[题解]CF1878E Iva & Pav
CF 是没题考了吧,每场都出二进制拆位。 思路 首先我们可以二分 \(r\),因为 \(r\) 越大,按位与一定只会小于等于 \(r\) 小的情况。 那么,我们可以用 \(num_{i,j}\) 记录 \(a_j\) 第 \(i\) 位的二进制情况。 如果我们对 \(num_{i,j}\) 做一个前 ......
CF1878 A-G 题解
前言 赛时代码可能比较难看。 A 判定 \(a\) 中是否有 \(k\) 即可。 赛时代码 B 奇怪的构造题。 令 \(a_1=1,a_2=3\),其他项由上一项加一开始枚举判定可行性即可,可以简单证明时间复杂度为 \(O(n)\)。 赛时代码 C 容易发现当 \(x\in \left[\dfrac ......
luogu P4819 [中山市选] 杀人游戏 题解 【强连通分量+缩点】
目录题目链接思路分析代码 题目链接 P4819 思路分析 首先考虑这道题的连通性。容易发现这种类型的题目会容易产生环形的状态转移。假设我们知道了其中的一个点是否是黑白点,那么我们就可以知道所有点是否是黑白点。容易陷入一个误区:我们只能通过一个点知道他所相邻的最直接的点,如何确定相邻的点的状态?注意本 ......
ARC063F Snuke's Coloring 2
Day \(4!\)。 首先容易找到周长为 \(2(w+1)\) 和 \(2(h+1)\) 的矩形,所以答案下界是 \(2(\max(w,h)+1)\)。 考虑按照整个矩形中心坐标,将矩形分成 \(4\) 个子矩形,观察到若有矩形完全包含于其中一个子矩形,则其周长必不超过 \(2\max(w,h)\ ......
Codeforces Round 742 Div2 A-D题解
Codeforces Round 742 Div2 A-D题解 A. Domino Disaster 这题就是说给出一些2x1 tile,然后给出2xn的第一行构造,问第二行 这个刚开始想着是啥dp,一看那么多人过了果断改思路,发现这题就是个模拟题,就是把U换成D,D换成U,L和R不影响,然后输出就 ......
P6411 [COCI2008-2009#3] MATRICA 题解
水题。 发现根据限制 \(M_{i,j}=M_{j,i}\) 可以知道除了主对角线上的点,其他的点都是成对出现的。也就是说如果有一条要求的 \(a_i\) 为奇数,那么至少有一个 \(c_i\) 在主对角线上。 记 \(S=\sum\limits_{i=1}^{k} (a_i\equiv 1\pmo ......
CF1791G2 Teleporters (Hard Version) 题解
CF1791G2 Teleporters (Hard Version) 题解 题目大意 题意挺清楚的,给个传送门吧。 分析 比较简单的贪心题,很容易就能看出来是贪心,也很容易就能看出来贪什么。 我没做简单版(Teleporters (Easy Version)),但是我去看了一眼。那个也非常简单,不 ......
2023.09.26 联考总结&题解
T1 derby 你考虑直接贪心进行匹配即可,就是说对于每一个 \(1\) 去匹配最大的 \(0\) #include<bits/stdc++.h> using namespace std; int n,m; vector<int> A[2],B[2]; int main(){ freopen("d ......
arc120D - Bracket Score 2
D - Bracket Score 2 看了题解之后发现自己是弱智 如果能够猜到答案就是前n大-前n小,那么这题就解决了,直接用一个栈模拟匹配即可。 #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #inc ......
Anton and School - 2题解
2023-09-26 题目 难度&重要性(1~10): 题目来源 luogu 题目算法 组合数学 解题思路 前置知识 范德蒙德卷积公式:\(\sum\limits_{i=0}^kC_{n}^{i}\times C_{m}^{k-i}=C_{n+m}^k\)。 至于证明请看此篇文章。 Sol 我们这道 ......
P6344 [CCO2017] Vera 与现代艺术 题解
在 \(V\times V\) 的平面上,\(n\) 次修改,每次给定 \(x,y,v\),令 \(a,b\) 为不超过 \(x,y\) 的最大的 \(2\) 的整数次幂,则所有 \((x+pa,y+qb)(p,q为自然数)\) 都加上 \(v\),最后有 \(m\) 次单点询问一个位置的值。 \( ......
P9566 [SDCPC2023] K-Difficult Constructive Problem 题解
## _Description_
有一个长度为 $n$ 的 ```01```字符串 $s$,其中部分位置已给出,在 ```?```的位置处需填入一个 ```1```或 ```0```。
一个填充方案是好的,当且仅当存在 $m$ 个不同的 $i$ 满足 $1\le i ......
AGC049D Convex Sequence 题解
题意 若非负数列 \(A\) 中任意 \(i(2 \leq i \leq N-1)\) ,都有 \(2A_i \leq A_{i-1} + A_{i+1}\),则称 \(A\) 为凸数列。 问长为 \(N\) ,且数列中所有项的和为 \(M\) 的凸数列有多少个,答案对 \(10^9+7\) 取模。 ......
洛谷P8074 [COCI2009-2010#7] SVEMIR 题解
P8074 SVEMIR \(Solution\) : 这道题目乍一看感觉好难... 因为有绿色的加持,再加上一进题目就看见了头疼的三维坐标,不知道的还以为需要用到什么非常高大上的知识来解决这道题,其实只需要用到最小生成树就行了。 不会最小生成树的请出门左转:P3366 【模板】最小生成树 然后来仔 ......