题解p9580 round game

## 题意 给定一个长度为 $n$ 的字符串 $s$ 和一个正整数 $k$，每次可以进行如下两种操作当中的一种（字符串下标从 $1$ 开始标号）： - 选择 $i \in \left[1, n - 2\right]$ 并交换 $s_i$ 和 $s_{i + 2}$； - 选择 $i \in \lef ......

#### A Moolistar 有一张长长的纸条，上面打满了黑黑的小点。上面有 $n＝2^k(k\le 30)$ 个均匀分布的点，编号从左到右、从 $0$ 到 $n-1$。Moolistar 开始将这条纸带对折，他把纸带右半边折到了左半边的下面，重复折叠 $k$ 次后，纸带变成了 $n$ 层的纸片 ......

# P4216 [SCOI2015] 情报传递 题解 来一篇常数不大的[最优解](https://www.luogu.com.cn/record/list?pid=P4216&orderBy=1&status=&page=1)题解。 ## Link [洛谷题目](https://www.luogu. ......

题目链接：https://codeforces.com/contest/1841/problem/E 题意： 有一个nxn的正方形网格； 现在对每一列进行约束，对第 i 列 从上往下，将 a[ i ] 个格子涂成黑色； 给正整数m，你要在网格内填上 1 ~ m 个数，有以下限制： 1： 数字只能填在 ......

题目链接：https://codeforces.com/problemset/problem/1848/D 题意： 给定正整数s和k； 你需要维护一个计数器C，并且进行k次操作，每次操作是一下俩种之一： 1：C = C + s； 2：s = s + s % 10； 输出k次后C的最大值，一开始C = ......

题目链接：https://codeforces.com/contest/1682/problem/D 题意： 给n个点，围成一个圈，你可以添加 n - 1条边使他成为一棵树，限制条件如下： 1：给长度为n的字符串，字符集为 0 和 1，对于 第i个字符，如果是1，表示第i个点的度数为奇数，反之为偶数 ......

题目链接：https://codeforces.com/contest/1834/problem/E 题意： 有长度为n的序列，问最小的正整数 x ，对于任意连续的子区间，区间的数的最小公倍数 都不等于 x； 分析： 首先来分析一下答案的范围是多少； 我们可以知道，对于长度 为n 的序列，前 n + ......

题目链接：https://codeforces.com/contest/1832/problem/E 题意： 当然这是化简后的题意，原题面和这个差距还是有点大的； 分析： 因为组合数有公式： 所以： 嗯，然后就没有了； 时间复杂度：O（n*k）； 代码： #include<bits/stdc++.h ......

[**FZQOJ**](https://qoj.fzoi.top/problem/607) [Luogu](https://www.luogu.com.cn/problem/P7199) ## 前言 ​ 节假日在家 ~~闲来无事~~ ，那就 ~~水~~ 写一篇题解吧。 ## 题目描述 ​ 前面一大堆 ......

# 「USACO3.2」Magic Squarest题解 **** 建议优先阅读题目后再看题解: [FZQOJ](https://qoj.fzoi.top/problem/422) [luogu](https://www.luogu.com.cn/problem/P2730) ## -题目大意 给定 ......

[fzqoj](https://qoj.fzoi.top/problem/1873) [luogu](https://www.luogu.com.cn/problem/P4878) # 题意 ##### 分别给出$ml$和$md$对，关于n头奶牛位置的关系，求1号到n号奶牛的最大距离是多少 每一对m ......

[洛谷链接](https://www.luogu.com.cn/problem/P1003) [FZQOJ](https://qoj.fzoi.top/problem/167) ##First 这一题的题面看似很长， 但是实际上归纳下来可以总结为： (1)：告诉你有i张地毯 (2)：第2行~第i+1 ......

看了大佬的wp做出来的；  首先是个游戏，对这个没有什么想法，看了大佬的博客，说是会有个sign，然后 ......

首先这是一道很明显的换根 dp。 首先注意到要拼接数，所以我们可以先处理出 $num_i=10^{x}$，使得 $10^x > a_i > 10^{x-1}$，这样方便我们后面算贡献。 我们以这棵树为例子来推状态转移方程。 ![](https://cdn.luogu.com.cn/upload/im ......

赛场上思路出来了但是代码没调出来。 首先考虑右端点，很明显，要让操作后的序列字典序尽量地大，那么就要使操作后的序列第一个数尽量地大，考虑 $n$ 或 $n-1$，如果 $n$ 在原序列的第一个位置，那么此时无论怎么调整都无法使得它在新序列的第一个位置，此时就要考虑让 $n-1$ 在新序列的第一个位置 ......

### 题意 给定一个无向图，其中至多有 $50$ 个结点，求是否有欧拉回路。 ### 题解 很明显就是一个无向图求欧拉回路的板子，我们用 $\tt{Hierholzer}$，先说存图，要明确的一个点是这个无向图里是有可能有重边的，所以我们要注意记录的时候不应是单独地记录某一条边是否存在，而是要记录 ......

首先把式子拆一下，可以知道 $x-i \ge |y-j|$ 等价于 $x-y \ge i-j$ 和 $x+y \ge i+j$，注意到每次操作 $(i,j)$，影响到的点 $(x,y)$ 均要满足 $x>i$，那么我们每次就必须要按照从上往下的顺序进行，否则上面的点无法影响到，即从第一行开始操作。 ......

对于第二种操作，很容易想到只有 $1$ 或 $2$ 两种答案，若该区间内存在 $01$ 这个子序列，那么答案为 $2$ 反之为 $1$.可以通过对该 $01$ 串做一个前缀和，若出现 $01$ 这个子序列就累加，最后判断左右端点是否相等即可，时间复杂度 $O(n)$. 对于第一种操作，$\text{ ......

注意到交换操作，无法改变下标的奇偶性，因此只能通过考虑翻转操作改变。注意到如果 $i$ 是奇数，那么要令 $i+k-1$ 为偶数的话 $k$ 必须为偶数，若 $i$ 是偶数，要令 $i+k-1$ 是奇数的话，$k$ 也应为偶数，而 $k$ 为奇数的情况翻转了也无法改变奇偶性。 因此通过 $k$ 的奇 ......

### 总述 此题用区间 dp 解决，二维前缀和优化。 ### 朴素做法 **阶段**：自上而下数每一层。 **状态**：$dp_{i,l,r}$ 表示自上而下数第 $i$ 行中在 $[l,r]$ 摆积木的方案数。 **状态转移方程**：根据题意可知，若要在 $[l,r]$ 中摆积木，那么 $[l, ......

先注意到我们娱乐值损耗的多少只与最后一场电影有关系，所以假设最后一场电影看的下标为 $k$，那么最后就要减去 $d \times k$。 得出这个性质之后开个小根堆反悔贪心即可，首先 $a_i0$ 的，如果还没到 $m$ 场电影，我们就直接往里塞就可以，如果到了，我们就进行反悔操作，取出已选的贡献最 ......

首先考虑无解的情况，很明显 $a_n$ 必须为 $0$，否则没有解，因为如果最后一位为 $1$ 那么必须有 $n$ 这个数存在于 $b$ 序列中，而这种情况时不符合题意的。 然后考虑如何求解，先考虑一种比较特殊的情况，就是若干个 $1$ 后面接着一个 $0$，这里假设 $1$ 的数量有 $k$ 个， ......

设 $check_i$ 为 $1\sim n$ 中满足题意的数的数量。 显然答案为 $check_j-check_{i-1}$。 注意到 $check$ 能直接暴力求出来。 那么就可以先把 $10^6$ 范围内的所有质数求出来，然后所有数跑一遍，每个数都去旋转得出所有数后判断是否均为质数，记录下来。 ......

- 给定 $n$，求： $$\sum_{i=1}^n\sum_{j=1}^n\frac{i+j}{\gcd(i,j)}$$ - 思路分析： 先化式子： $$\begin{aligned} \sum_{i=1}^n\sum_{j=1}^n\frac{i+j}{\gcd(i,j)}&= \sum_{d= ......

今天终于是4题了 这场似乎是手速场 A直接枚举一下就行，懒得想了 B暴力放 C怎么又是二分 D刚开始没什么思路，想着写个暴力，发现还挺快的 但是遇到相差很大就会寄 但是中间都是大的减小的 a-bk=x 只要检查这些是否成立即可 复杂度跟求gcd一样 ```cpp #include #include ......

链接：https://ac.nowcoder.com/acm/contest/63869/C来源：牛客网 题目描述 小美定义一个 01 串的权值为：每次操作选择一位取反，使得相邻字符都不相等的最小操作次数。 例如，"10001"的权值是 1，因为只需要修改一次：对第三个字符取反即可。 现在小美拿到了 ......

## A 考虑在所有 $0$ 前添加正号，在 $1$ 前轮流添加正负号即可。 ## B 首先根据抽屉原理，我们可以取出最多的颜色，个数记为 $mx$，然后其余颜色可以填在 $mx$ 的两两中间，最少要有 $(mx-1)(k-1)$ 个空位。 但是只是必要的，而不是充分的。考虑有多个最大值的情况，发现 ......

[problem](https://www.luogu.com.cn/problem/P3888) & [blog](https://www.cnblogs.com/liangbowen/p/17664121.html)。 这怎么评到紫上去的啊？差不多就个上位绿吧 /qd。 首先出题人非常 low。 ......

[洛谷传送门](https://www.luogu.com.cn/problem/CF1864E "洛谷传送门") [CF 传送门](https://codeforces.com/problemset/problem/1864/E "CF 传送门") 感觉是很费脑子的题，可能是因为我没有脑子。 因为 ......

#### **[原题传送门](https://atcoder.jp/contests/arc080/tasks/arc080_c)** 题意：给定一个 $n$ 的排列 $a$ 和一个初始为空的序列 $b$。你每次需要在 $a$ 中选择一对相邻的数，把它们从 $a$ 中拿出来，并按原先的相对顺序插到 ......