题解1359a cf
LCM Sum (CF E ) (正男则反, 二维数点/二维偏序, 大胆的抽象化简数学式子, 打表找规律)
思路: CF1712 E1/E2 LCM Sum (easy/hard version) 二维数点/二维偏序: 二维前缀和+扫描线+树状数组+ 离线处理 应用: 求 Q次询问, L-R内 x-y的 点的数量(矩形内点的数量) 直接用二维前缀和, 时间复杂度, 一定不允许, 发现 二维前缀和是由 4个 ......
CF724G Xor-matic Number of the Graph
[题目链接](https://codeforces.com/problemset/problem/724/G) 不妨先看一道更为基础的题:[CF845G](https://codeforces.com/problemset/problem/845/G)以及[它的题解](https://www.cnb ......
CF444C DZY Loves Colors
## [$DZY$ $Loves$ $Colors$](https://codeforces.com/problemset/problem/444/C) ### 一、题面翻译 有一个 $n$ 个元素组成的序列,每个元素有两个属性:颜色 $c_i$ 和权值$w_i$。$c_i$ 初始为$i$,$w_i ......
洛谷P3038 [USACO11DEC] Grass Planting G 题解 树链剖分
题目链接:[https://www.luogu.com.cn/problem/P3038](https://www.luogu.com.cn/problem/P3038) 题目大意: 一棵树维护两种操作: 1. 一条路径上每条边边权 $+1$; 2. 查询路径上的边权和。 解题思路: 树链剖分模板题 ......
P2292 [HNOI2004] L 语言 题解 AC自动机 + 状态压缩 + dp
题目链接:[https://www.luogu.com.cn/problem/P2292](https://www.luogu.com.cn/problem/P2292) 题目大意: 给定 $n(\le 20)$ 个模式串 $s_i(|s_i| \le 20)$,有 $m(\le 50)$ 次询问, ......
Memory题解(线段树优化DP)
[传送门](https://www.luogu.com.cn/problem/P9594) 简要题意: 给定 $m$ 条线段,每条线段由四个正整数参数 $l_i,r_i,c_i,w_i$ 描述,其中 $l_i,r_i$ 是这条线段的端点,$c_i$ 是这条线段的种类,$w_i$ 是这条线段的权值。 ......
CF1860D 题解
在 Codeforces 上看到了这题的 $\mathcal{O}(n ^ 4 / \omega)$ 做法,和大家分享一下。 [原版 Solution 链接](https://codeforces.com/blog/entry/119504?#comment-1060285) 记 $d$ 为原字符串 ......
【题解】CF1852D Miriany and Matchstick
考虑 `dp`,设 $f_{i,0/1}$ 表示考虑到前 $i$ 位,且第 $i$ 位填入 A/B 可能的答案集合,显然地朴素转移时间复杂度 $O(n^2)$。 试分析 `dp` 性质,观察发现所有 `dp` 中得到的集合为区间内抠去至多一个点。 > > 证明 > 我们首先来观察转移过程是怎样的。第 ......
$9.6$ 短学期题解
## $a$ ```cpp int a[N]; void solve(){ int n=read(); for(int i=1;i=5?"Penta Kill":"Shut Down"); //puts(ans>0?"Yes":"No"); } ``` ## $b$ 想了很久,感觉没有不用最短路算法 ......
2023短学期0905场题解
1.挖地雷 Description 在一个地图上有N个地窖(N 点击查看代码 ``` #include using namespace std; const int N = 20; int connect[N][N], mark[N], a[N], n;//mark用于标记该地窖是被访问过 int ......
Iksevi 题解
### 题目大意 $n$ 次询问,每次给定一个点 $(x,y),x\ge 0, y\ge 0$,问有多少种对角线长为偶数的正方形使得在用该正方形正密铺第一象限的情况下该点位于正方形顶点上。 **正密铺第一象限** 指将第一个正方形的角与 $x$ 轴和 $y$ 轴接触。此后的正方形都与至少一个已放置的 ......
【题解】CF1852C Ina of the Mountain
我们先从题目的一部分入手。 如果说,我们没有当一个数为 $0$ 时,让这个数变成 $k$ 的性质,我们如何求答案呢? 很简单,在图上就是: 绿色线段的长度加起来即为答案(本图中是 $6$) 我们考虑很显然地,将一个数从 $0$ 变为 $k$ 即为将一个数一开始加上 $k$ 我们如果要让第 $i$ 列 ......
2023短学期0905场题解
1.挖地雷 Description 在一个地图上有N个地窖(N 点击查看代码 ``` #include using namespace std; const int N = 20; int connect[N][N], mark[N], a[N], n;//mark用于标记该地窖是被访问过 int ......
AT_abc310_g 题解
一、题目描述: 有 $n$ 个人,第 $i$ 个人一开始有 $a_i$ 个球。每个人都有一个自己的传球目标。 有一个正整数 $k$,从 $1\sim k$ 中随机选择一个数作为游戏的进行轮数。 在游戏的每一轮,所有人同时都把自己手上的球全部传给自己的传球目标。 求游戏结束之后,每个人手上的期望球的数 ......
CF1695D2 Tree Queries (Hard Version)
[原题](https://codeforces.com/problemset/problem/1695/D2) [翻译](https://www.luogu.com.cn/problem/CF1695D2) $$ \large{\color{#ff0000}{\text{被xjk搏杀了,wtcl}} ......
CF845G Shortest Path Problem?
[原题链接](https://codeforces.com/problemset/problem/845/G) 不妨先了解几个前置知识/引理: 异或的抵消性质: * $a\oplus a=0$ * $\forall b[b\not= a],a\oplus b\not=0$ * $(a\oplus b ......
【题解】CF1852B Imbalanced Arrays
我们假设当前出长度为 $len$,那么我们在序列中一定有一个 $len/0$,因为一定有一个绝对值最大的数,如果这个数是正数在原序列中就是 $len$,是负数在原序列中即为 $0$。 由上文,我们可以得到,一定不能有 $len$ 和 $0$ 同时出现的情况,也一定不能有 $len$ 和 $now$ ......
【题解】Educational Codeforces Round 145(CF1809)
## A.Garland ### 题目描述: 有 $4$ 只灯泡,第 $i$ 只灯泡的颜色为 $s_i$ 。 一开始,所有灯泡都是关着的,你需要把它们都打开。你可以进行数次操作,每次操作改变一个灯泡的状态,即打开原本关着的灯泡或关上原本亮着的灯泡。第一次操作可选择任何灯泡,此后每一次被操作的灯泡的颜 ......
【题解】ABC318
## [AtCoder-ABC318A Full Moon](https://atcoder.jp/contests/abc318/tasks/abc318_a) 暴力枚举判断。 提交记录:[Submission - AtCoder](https://atcoder.jp/contests/abc3 ......
题解 [BJOI2014] 大融合
[题目链接](https://www.luogu.com.cn/problem/P4219) 可以发现,一条边 $(x,y)$ 的答案,就是 $x$ 不经过该边可达的点的数量(记作 $cnt_x$) $\times$ $y$ 不经过该边可达的点的数量(记作 $cnt_y$)。 尝试将这个式子转化,若 ......
[CF1768F]Wonderful Jump
[Wonderful Jump](https://www.luogu.com.cn/problem/CF1768F) 题目看错了,以为能往回跳...... 暴力转移式 $$ dp_i=min(dp_i,dp_j+\min_{k=j}^ia_k\times(i-j)^2) $$ 你会发现这个没啥单调性 ......
[ABC318E] Sandwiches 题解
# [ABC318E] Sandwiches 题解 ## 题意简述 给定包含 $n$ 个整数的序列 $a$,其中任意元素的值 $a_i \in [1,n]$,统计包含三个元素的满足以下条件有序三元组数量:满足下标严格递增;满足第一个和最后一个元素相等,而中间的元素和两端的元素不相等。 记录三元组 $ ......
CF1854 题解
# CF1854 题解 ### A 首先考虑只有非负的情况,次数完全可以接受 $19$ 次,所以直接用 $19$ 次做一次前缀和就可以保证单调不降了。 现在有了负数,考虑将负数变成正数,选出正数当中的最大值,然后用 $a_i + a_i \to a_i$ 这样自增的方式让它的绝对值大于负数最大值,因 ......
CF1852 题解
# CF1852 题解 ## A Ntarsis' Set ### 题意 有一个集合,初始状态里面有数字 $1$、$2$、$3$、$4$、$5$、......、$10^{1000}$。 现在给你一个长度为 $n$ 数组 $a (1\leq a_i \leq 10^9 )$,要进行 $k$ 次操作,每 ......
$9.5$ 短学期题解
## $a$ 一个简单的坐标转换,原来的 $a[i][j]$ 会变为 $b[j][n-i+1]$ ```cpp int b[N][N]; void solve(){ int n=read(),m=read(); for(int i=1;i0?"YES":"NO"); //puts(ans>0?"Ye ......
【题解】CF1852A Ntarsis' Set
考虑我们先手模一下样例: $$ \begin{cases} 1&3&5&6&7\\ 2&8&10&11&12\\ 4&13&15&16&17 \end{cases} $$ ???一脸疑惑,有什么规律吗?真有,但是很难看出来捏。 正难则反,我们考虑如果知道操作一次后一个数的位置,我们可以很容易推出,操 ......
【题解】NOIP2022
怎么看 T3 也不是那么难,可是为啥赛时就是被卡死了[难过] 不补 $B$ 题了,ad-hoc。 ## A.种花 ### 题目描述: 小 C 决定在他的花园里种出 $\texttt{CCF}$ 字样的图案,因此他想知道 $\texttt C$ 和 $\texttt F$ 两个字母各自有多少种种花的方 ......
AT318 A-G 题解
### A 枚举 $1\sim n$ 的每个数,判断是否有 $i-M\equiv 0\pmod P$ 即可。 [赛时代码](https://atcoder.jp/contests/abc318/submissions/45128240) ### B 暴力覆盖即可,注意 $x,y$ 均是左开右闭。 [ ......
湖北省选模拟 2023 部分题解
质量不错。 为什么湖北会有这么 hard 的省选啊 /fn。 ### [D1T1](https://www.luogu.com.cn/problem/P9542) $\color{Gold}\bigstar$ 第一题就不会是我没想到的。 考虑一下简单情况,一条链咋做,每次操作相当于把一个空隙的大小减 ......