付诺の小站

Red Playing Cards题目大意 有$2n$的数组成一个序列，其中$1$到$n$每个数都会出现两次。你可以执行以下操作： 选择两个端点相同的区间，删去这个区间，同时获得$区间长度 \times 区间端点数$的分数。 求所能获得的最大分数为多少。 解题思路 考虑线性$DP$，$f[i]$表示只考虑前$i$个数所能获得的最大分数，思考状态转移： 当$[1, i - 1]$中没有数与$a[i]$相同，$f[i] = f[i - 1]$； 当$[1, i - 1]$中有数与$a[i]$相同，假设其下标为$l$，那么状态转移为$f[i] = f[l - 1] + g[l][i] + (i - l + 1)\cdot a[i]$，其中$g[i][j]$表示这段区间最多能获得的分数比单纯用两端点删掉$[l, r]$这一区间所获得的分数要大多少； 注意到引入了新的状态，说明这种想法不太可行，但同时$g[i][j]$也启发我们，只有在区间$[i + 1, j - 1]$中有两端点大于$a[i]$的可操作区间，$g[i][j]$才有值，而如果存在多个这样的可操作区间，就考 ...

Floor Tiles题目大意 你有两种类型的地砖： 上面一种类型为$A$，下面一种类型为$B$，现在一个$n \times m(1 \le n,m \le800)$的矩阵，最初会在某一格上放置一个$A$或$B$类型的地砖，你需要填满剩下$n \times m - 1$格，问是否有一种摆放方式使得恰好能使其显示$k(1 \le k \le 2 \cdot nm)$条曲线，若有，请输出$Yes$，并给出摆放方案，否则，输出$No$。 共有$T(1 \le T \le 10 ^ 5)$次询问。 解题思路 注意到无论 $N, M$ 是多少，矩阵的结构如何，从整个二维矩阵边缘进入 的曲线最终一定会从整个二维矩阵边缘出去，不可能进入其内部的任何 一个环； 边缘的“线头”一共有 $2(N + M)$ 个，所以这样的曲线数目为 $2(N+M) 2 = N + M$ 个; 对于一个大小为 $N \times M$ 的平面，其曲线总数为 $N + M+ 平面结构 内部环的数目$。 接下来考虑如何造环，可以发现仅有$A ~ B \ B ~ A$的情况才会构成一个环， 当矩阵左上角为$A$时 ...

A Bit More Common题目大意 给定两个整数$n$和$m(1 \le n,m \le 5000)$，在所有长度为$n$且元素取值范围为$[0, 2 ^ m)$的序列中，计算存在两个合法子序列的序列个数。其中，合法子序列是指子序列中所有元素按位与的结果为$1$。 由于答案可能很大，请将其对$q(1 \le q \le 10^9)$取模。 解题思路 首先考虑至少存在一个合法子序列的序列个数，对于合法子序列中的元素，第$0$位必须全为$1$，其余位上至少有一个$0$，对于剩下的其他元素，第$0$位必须全为$0$，其余位任选。我们对序列长度进行枚举，最终得到： $\sum_{i = 1}^{n}C_{n}^{i}(2 ^ {i} - 1)^{m - 1}2^{(m - 1)(n-i)}$ $①$ 题目要求我们求至少存在两个合法子序列的序列个数，那么接下来只需要求恰好只有一个合法子序列的情况，最后用至少$1$个的方案数减去恰好$1$个的方案数即为所求结果。 考虑这样一种按位与为$1$的子序列，去掉其中任何一个元素，他们的按位与都会变得不为$1$。首先这些元素的第$0$ ...

Mirror Maze题目大意 给定一个$n \times m(1 \le n,m \le 1000)$大小的矩阵，每个格子上都有一面镜子，镜子共有以下$4$种类型： “$-$” 反射来自上方和下方的光，来自左边和右边的光将平行穿过； “$|$” 反射来自左边和右边的光，来自上方和下方的光将平行穿过； “$\setminus$” 将来自上、下、左、右方向的光反射成朝向分别为右、左、下、上的光； “$/$” 将来自上、下、左、右方向的光反射成朝向分别为左、右、上、下的光； 共有$q(1 \le q \le 10^5)$次询问，每次给出光源的位置和方向，问每个光源的光最终会反射多少枚不同的镜子。 解题思路 由于$n \times m$的大小的$10^6$，算上每格所包含的4种不同状态数量级依然为$10^6$，那么总共是$4 \times 10 ^ 6$个点，可以想到遍历预处理。 继续思考每个每个点之间的关系，发现每个点只能唯一地转移到下一个点，所以光的运动轨迹要么是个环，要么是一条链，环与链都是各自独立的，并且链的两端一定对应矩形的边界。换句话说，光一定是从外界进入到矩阵，再 ...

Mad City题目大意 给定一个$n$个点，$n$条边的连通图。$A$从$a$点开始追赶处在$b$点的$B$，两人同时开始移动，并且$B$能准确预料到$A$下一步会去哪，并据此采取行动。问在两人都以最优策略开始移动的情况下，$A$是否永远都追不上$B$。 解题思路 $n$个点和$n$条边，意味着有且只有一个环。很明显$B$只要在走到环之前不被$A$截住的话就成功。分成以下几种情况： $a==b$，直接输出$NO$; $b$为环上的点，输出$YES$; $b$不在环上，那么求一下环上离$B$最近的点到$A$，$B$的距离$dista$，$distb$，如果$dista<=distb$，说明$A$能在$B$赶到环上之前截住他，输出$NO$;反之，输出$YES$。 思路理清了，接下来考虑如何实现。 首先是判环，可以开一个$f$数组记录每个点的的前一个节点，初始化为$0$，然后进行$dfs$，在遍历到与当前点$x$相连的所有点时，如果碰到某个点$u$的$f[u]$不为$0$，则意味着碰到环了，使$f[u]=x$，然后就可以借助$f$数组求出 ...

Trader Problem题目大意 你有$n$个物品，第$i$-th个物品价值为$a_i$，商人有$m$个物品，第$i$-th个物品价值为$b_i$，你可以将自己的某个物品，假设价值为$a_i$，与商人手中价值不超过$a_i+k$的物品交换。现在有$q$次询问，每次给定一个$k$值，求能通过以上操作能使手中物品价值之和到达的最大值。 解题思路 将物品价值从大到小排序后进行合并。相邻插值小于$k$即可进行合并。同时拿并查集维护可选数。可以对需要查询的$k$进行排序，减小复杂度。具体实现看代码。 参考代码1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253#include <bits/stdc++.h>#define maxn 400100#define int long longtypedef __int128_t int128;using namespace std;const double eps=1e-8;int f[maxn] ...

Promising String (hard version)题目大意 给定一个只含$+$和$-$两种字符的字符串，可以进行以下操作： 选定两个相邻的$-$，使其变为$+$。 求通过任意次操作后，$+$和$-$数量相等的子串数量。 解题思路 前缀和的思想，$+$加$1$，$-$减$1$，当前值为$0$意味着符合要求。然后有一个简单的性质，如果当前值为负数且为$3$的倍数也可以通过操作使其合法。那么，问题就是求满足： $\left{\begin{aligned}&0≤l<r≤n\&a_r≤a_l\&a_l≡a_r(mod\ 3)\end{aligned}\right.$ 同余分组后求逆序对数即可。 注意树状数组中下标不能为负数，所以可以开两倍空间。然后倒序求逆序对。 参考代码123456789101112131415161718192021222324252627282930313233343536373839#include <bits/stdc++.h>#define maxn 400100#define lowbit(x) x& ...

Passable Paths (hard version)题目大意 给定一颗大小为$n$的树，$q$次询问，每次给出一个大小为$k$的点集，判断树上是否有一条简单路径能将点集中的所有点全部覆盖。 解题思路 假设简单路径存在，那么端点一定是点集中的点。一个比较简单的性质是：其中一个端点$x$是深度最深的点，另一个是距这个点最远的点$y$。深度最深的点只需要$dfs$预处理一下即可，其他点与这个点的距离只需要借助$LCA$即可求出：$$dis=dep[x]+dep[y]-dep[lca(x,y)]$$ 接下来只需要判断其余点是否在这两个端点的简单路径上即可，分以下几种情况： $dep[i]<dep[lca(x,y)]$，不可行； $lca(x,i)==i||lca(y,i)==i$，可行； 其余情况均不可行。 参考代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585 ...

Another Bus Route Problem题目大意 给定一棵树以及$m$条巴士路线，对于每条路线可以在起点和终点上车，在路线上任意点下车。求从节点$1$出发，到每个点所需乘坐的最少巴士数量，如果不能到达则输出$-1$。 树以如下方式给出： 第一行包括两个整数$n$和$m$，分别表示点的数量和巴士路线的数量。接下来一行共有$n-1$个数，第$i$个数$p[i]$表示$i+1$和$p[i]$连有一条边，且$p[i]<=i$。 解题思路 裸的$bfs$。把$m$条巴士路线看成$m$条边，从节点$1$开始$bfs$，遍历到的每个点都更新一下原图中它的所有父节点的答案。碰到已经被赋值过的父节点就停止。因为已经被赋值过表示在之前某条巴士路线就已经经过这个点，并且由于是从节点$1$进行$bfs$，所以从$1$到这一点的路径一定是走过的。 题中特殊的建树方式，可以看成是每个$i+1$的父节点即为$p[i]$。 参考代码12345678910111213141516171819202122232425262728293031323334353637383940414243#inc ...

Sum of XOR Functions题目大意 给定一个长度为$n$的$a$数组，求$\sum_{l=1}^n\sum_{r=l}^nf(l,r)⋅(r-l+1)$的值 ，其中$f(l,r)$表示区间$[l,r]$的异或值。 解题思路 拆位是位运算题目的常用套路，这题也不例外。先用类似前缀和的思想求一下以$1$为起始位置的每一段的异或值$pre$。 然后对二进制下的每一位进行计算，假设当前$pre[i]=(100010)$，那么对于每一位，只有当之前某个$pre$在这一位上与其异或为$1$，则对答案有贡献。 可以遍历$a$数组，并在过程中累加$1$和$0$的数量即可进行计算。 参考代码1234567891011121314151617181920212223242526272829303132#include <bits/stdc++.h>#define maxn 300100#define int long longtypedef __int128_t int128;using namespace std;const double eps= ...