题解1203 div cf

[题目链接](https://www.luogu.com.cn/problem/P9445) 数据有点水啊，貌似矩阵大小最大只有 $500$，这导致一堆 bitset 乱搞或者暴力啥的无聊解法能过，这里就不多说了，快进到正题。 二维通配符匹配。 首先根据 Rabin Karp 给每种颜色随机一个权值 ......

## A. Dalton the Teacher 题意：给出一个排列，问使得排列变为1,2,...,n的最小的交换操作次数 ### Solution 统计a[i]!=i的个数，答案就是除以二向上取整 ```c++ void solve() { int n;cin>>n; int res=0; for ......

[洛谷链接](https://www.luogu.com.cn/problem/CF1359A)&[CF 链接](http://codeforces.com/problemset/problem/1359/A) ## 题目简述 共有 $T$ 组数据。 对于每组数据给出 $n,m,k$，表示 $k$ ......

[洛谷链接](https://www.luogu.com.cn/problem/CF1363A)&[CF 链接](http://codeforces.com/problemset/problem/1363/A) ## 题目简述 共有 $T$ 组数据。 对于每组数据，给定 $n,x$ 和 $n$ 个数 ......

[洛谷链接](https://www.luogu.com.cn/problem/CF1282A)&[CF 链接](http://codeforces.com/problemset/problem/1282/A) ## 题目简述 共有 $T$ 组数据。 有一条数轴，要从 $a$ 点跑到 $b$ 点，在 ......

[洛谷链接](https://www.luogu.com.cn/problem/CF479C)&[CF 链接](http://codeforces.com/problemset/problem/479/C) ## 题目简述 一个人想要安排期末考试的时间。 有 $n$ 场考试，每场考试有两个时间 $x ......

[洛谷链接](https://www.luogu.com.cn/problem/CF1468N)&[CF 链接](http://codeforces.com/problemset/problem/1468/N) ## 题目简述 共有 $T$ 组数据，对于每组数据： 有三个桶，五种垃圾，每个桶有固定的 ......

# Educational Codeforces Round 36 (Rated for Div. 2) https://codeforces.com/contest/915 浓浓ds味的一场edu ## A. Garden 找最大因子 ```CC #include using namespace ......

## 1.题意简述 某天小 $x$ 去食堂吃饭，手里有 $n$ 种饭票，面值分别为 $A_1～A_n$ ,数量分别为 $C_1～C_n$ 请你计算小 $x$ 的饭票能组成多少在 $[1,m]$ 区间内的面值。 ## 2.样例解释 ```cpp 3 10 1 2 4 2 1 1 ``` ```cpp ......

[Link](https://www.luogu.com.cn/problem/P2296) 很简单的一道图论题。 要在一个有向图上找一条 $s$ 到 $t$ 的最短路，要求这条路径上的所有点都满足：该点的所有出边所连点都能到达终点 $t$。 看上去很乱，我们简单分解一下，先在所有点中找到与终点有路 ......

题目传送门：[HDOJ 7329 [2023杭电多校] Touhou Red Red Blue](http://acm.hdu.edu.cn/showproblem.php?pid=7329) # 题意 有两个口袋（口袋容量为1，初始均为空），有若干个UFO按顺序来到你的面前，每个UFO有一个颜色（ ......

打的太 shaber 了，于是补补题。 ## D1T1 扫描线。 首先我们可以容斥一下，答案为被一种操作覆盖到的减去被两种操作覆盖到的加上被三种操作覆盖到的。 首先考虑只被一种操作覆盖到的，这很简单，直接上个区间颜色段推平就好了，顺便去了个重。 接下来是有被斜线覆盖到的，这样的点数为 $O(nk)$ ......

## Vika and Her Friends > 给定一张网格图，Vika 在 $(x, y)$ 处，她的 $k$ 个朋友分别在 $(x_{1 \sim k}, y_{1 \sim k})$ 处，每次所有人都必须移动到相邻各格子，询问 Vika 能否永远逃离她烦人的朋友 考虑对格子进行黑白染色，每 ......

## Escalator Conversations 判断两人台阶是否为 $k$ 的倍数且在 $(0, m)$ 内即可 ```c++ #include using namespace std; signed main() { int T; scanf("%d", &T); for (int n, m ......

## Desorting > 定义一次操作为选定一个 $i$ ，令 $a_{1 \sim i}$ 自增， $a_{i + 1 \sim n}$ ，自减，求使得整个序列无序的最小操作次数 若序列一开始就无序，输出 $0$ 否则找到相邻两数差值最小的位置，在这个位置不断使用操作，可以证明这是最优方案 ` ......

## Dalton the Teacher > 给定序列 $a_{1 \sim n}$ ，定义一次操作为交换序列中的某两个数，求使得 $\forall i, a_i \not = i$ 的最少操作次数 > > 对于所有数据，$n \leq 10^5$ 计算出 $a_i = i$ 的位置数量 $sum ......

[洛谷链接](https://www.luogu.com.cn/problem/CF1204A)&[CF 链接](http://codeforces.com/problemset/problem/1204/A) 本篇题解为此题**较简单做法**及**较少码量**，并且码风优良，请放心阅读。 ## 题 ......

看到官方题解是 $O(n^2)$ 的 dp。 提供一个 $O(n^2 \log_2 n)$ 的做法，考场思路，大概比较简单。 ## Description 给一个 $H$ 行 $W$ 列的网格，其中一些点被涂成黑色，求整个正方形内都未被涂黑的正方形的个数。 ## Solution 考场上首先想到的简 ......

## 题意 $t$组数据（$1 \le t \le 1000$），每组数据给一个整数 $n$（$1 \le n \le 10^{18}$），找出两个整数 $l$ 和 $r$（$ -10^{18}\le l #define int long long using namespace std; int ......

## 题意 $t$组数据（$1 \le t \le 10^{4} $），每组数据给一个偶数 $n$（$2 \le n \le 2 \cdot 10^{5}$），有 $n$ 个多米诺骨牌 ，每块多米诺骨牌包含两个整数 $a_{i}$ 和 $b_{i}$ （$1 \le a_{i},b_{i} \le ......

# CF526F Pudding Monsters ## 题意 给定一个 $n \times n$ 的棋盘，其中有 $n$ 个棋子，每行每列恰好有一个棋子。 求有多少个 $k \times k$ 的子棋盘中恰好有 $k$ 个棋子。 $n \le 3 \times 10^5$。 ## 题解 首先注意到 ......

由于 $k$ 够大，你可以随便在图上走环，不用担心不用走，那么你所担心的只有环长的 $\rm gcd$。 将所有强连通分量先求出，满足条件的点对必然在一个强连通分量里。我们以随便一个点为根，跑出强连通分量中的一棵dfs树，我们断言，如果 $dep_x-dep_y \equiv dep_y-dep_x ......

# Preface 经典秒完SB题然后开始坐牢1h，写了个E的假算法T在24个点就不管了打lol去了 妈的怎么稍微难点的题就是想不到呢 # A. Morning Sandwich 签到 ```cpp #include #include #include #include #include #incl ......

容易想到将所求差分，变为 $[1,r]$ 的答案减去 $[1,l-1]$ 的答案。 直觉告诉我们所谓的“实数 $y$”就是没事闲的，其实只需要整数就可以。然后这种酷似整除分块的结构提示我们很多 $y$ 的取值都是多余的，只需要保留所有是 $x_i$ 的倍数的取值就做到了不重不漏。 要求 $[1,k] ......

# [Codeforces Round 889 (Div. 2)](https://codeforces.com/contest/1855) ## T1 ​ 思路：我们将 $i \ne p_i$ 的数量记下来，再判断这个数的奇偶性，如果为偶，那么答案就为这个数 / 2，如果为奇，那么就是这个数 / ......

# A. Vika and Her Friends 看一下样例就可以发现，Vika 以及她的朋友都不能走对角线，在这种情况下 Vika 和朋友的距离为 **偶数**，且朋友一定追不上 Vika 所以直接判断 Vika 和朋友的距离是否都为偶数即可 # B. Vika and the Bridge 显 ......

# [Codeforces Round 887 (Div. 2)](https://codeforces.com/contest/1853) ## [A. Desorting](https://codeforces.com/contest/1853/problem/A) ### 题目大意 给出一个长 ......

# [Codeforces Round 885 (Div. 2)](https://codeforces.com/contest/1848) ## [A. Vika and Her Friends](https://codeforces.com/contest/1848/problem/A) ### ......

[problem](https://www.luogu.com.cn/problem/AT_arc089_b) & [blog](https://www.cnblogs.com/liangbowen/p/17599062.html)。 给一个比较暴躁的做法。 若要求 $(x,y)$ 的颜色为 Whi ......

# Codeforces Round 885 (Div. 2) ## A. Vika and Her Friends ​ 考虑 Vika 和其中一个朋友的距离，Vika 走一步，他们的距离要么加一要么减一；朋友也一样。那么每秒后他们的距离，要么不变，要么 ±2。那么与 Vika 距离为奇数的朋友，永 ......