E - Nearest Black Vertex 题目链接 题意 给你一个$n$点$m$边的无向图，每个点需要染成黑色或白色，有$k$个限制$(p_i, d_i)$为距离$p_i$点最近的黑点距离为$d_i$，求是否存在这样的图，若有多种方案输出任意一种即可。 数据范围：$2\le n\le 2000,\ n - 1\le m\le \min\lbrace \frac{n\times (n−1)}{2},2000\rbrace, 0\le k\le n$ 思路 注释都写在代码上了，这里想写的原因是，如果边权为1的话…
题意 AcWing4261.孤独的照片 - acwing.com 给出一个只包含'H'以及'G'的字符串，认为至少长度为3的子串，且'H'或者'G'有一个是单个的，这代表这张照片是孤独的需要丢弃，求需要丢弃多少张这样的照片。 思路 我写的比较复杂... 首先看单H的情况存在，枚举如果遇到s[i]=='H'则进行计算贡献： 需要找到这样的GGGGHGGG H(pre)左边的个数是L=pre-l+1个 H(pre)右边边的个数是R=r-pre+1个 那么首先能得到的包含H的子串个数是$L\times R$（原因是左侧有…
今天写牛客小白月赛的时候，做完前三题看到第四题是一个模拟，就没有写了，直接去看做的人数较多的F，做法直接让我大开眼界... 题目链接：牛客小白月赛F-困难卷积 题意： 给出两个序列$a_i,b_i$，求出： $$ \sum_{i=1}^{n} \sum_{j=1}^{n}\left \lfloor \sqrt{\left|a_{i}-b_{j}\right|} \right \rfloor $$ 范围是： $1\le n\le 10^6, 0\le a_i,b_i \le 3\times 10^6, \Sigma …
题目链接：M. Moving Both Hands 题意 给你一个$n$点$m$边的带权有向图，一开始双手放在点$1$以及其他点，每次可以移动一只手，花费是边权，求两只手到一个点的最短时间。一共有$n-1$次询问，分别是点$1$到其他$n-1$个点的最小花费。 最短时间是：1->2->4 ｜ 4
题目链接：H. Hot Black Hot White 题意： 给你$n$个数，你需要平均分成两份，分别有$\frac{n}{2}$个，如果两个数满足下面等式，则会发生冲突，那么就需要在同一类才不会发生冲突： $$ {\rm concat}(A_i,A_j)\times {\rm concat}(A_j,A_i)+A_iA_j \equiv Z \quad {\rm mod} \ 3 $$ 思路： 举个例子${\rm concat}(123,456)=123456$，那么其实就是$123\times 10^3+45…
题意 题目链接Codeforces Round #813 (Div. 2) - D. Empty Graph 给你一个长度为$n$的序列，以及一个整数k，这是一个无向完全图，两点(l,r)之间的路径长度为 $$ dis(l,r)\ =\ min\lbrace a[l],a[l+1],\cdots,a[r-1],a[r]\rbrace $$ 你可以将一个点的权值求改为小于等于1e9的任意值，可以修改最多k个点。 求图的直径的最大值。 图的直径：任意两点(u,v)之间最短距离的最大值 思路 先来看任意两个点(i,j)之…
题目链接：ABC262D 题意： 给出$n$个正整数，选出若干个数字，求这若干个数字的平均值是正整数的方案数，答案对998244353取模。 思路： 一开始想着的是dp[i][j][k]表示前i个数选择j个数其中和为k的方案数。 k会很大，所以需要考虑取模，存储和对j取模。 不选a[i]的转移方程有dp[i][j][k] = dp[i-1][j][k]，但是如果选a[i]的时候有些难办，现在sum=k那上一个状态如何得来？(sum-a[i])%(j-1)=?这个不好办。所以这个$O(n^3)$方法不太行。 定义dp…
题意 题目链接： AcWing 2984.线段 POJ寄了 在二维平面内有 $n$ 条线段，请你编写一个程序，判断是否存在一条直线满足将这 $n$ 条线段投影到该直线上后，所有的投影线段至少具有一个公共点。 数据范围 $1≤T≤100, 1≤n≤100, −10^9≤x1,y1,x2,y2≤10^9$ 思路 先来看看题意，题目给出若干线段，需要找到一条线段，线段的投影在直线上需要有交点，也就是下图三条线段，需要找一条直线往其做投影，需要找到至少一个公共点。 那么如何来找到这样的直线呢？这样按照题意十分复杂，所以需要…
题意 题目链接： 2318 -- TOYS (poj.org) 2983. 玩具 - AcWing题库 约翰总是乱丢玩具，母亲给他准备了一个收纳盒，并且将收纳盒用若干的纸板分离开来，约翰每次会将玩具放在收纳盒中的一个地方，请问每一个收纳盒放了多少个玩具。收纳盒如下图： 给出$n,m,x_1,y_1,x_2,y_2$表示有$n$个纸板，$m$个玩具，有一个左上角坐标为$(x_1,y_1)$以及右下角坐标为$(x_2,y_2)$的收纳盒。 接下来$n$行每行有两个整数$U_i,L_i$表示第$i$个纸板的两端点坐标分别…
