Gym 101845（2018 ACM-ICPC, Universidad Nacional de Colombia Programming Contest）

Problem A

Problem B

分析：

暴力查找，由操作 $1$ ，我们可以知道原串的第一位可以匹配结果串的每一位，所以 $mathcal{O}(n)$ 枚举对齐判断就好；由操作 $2$ ，对于每一个对齐好的原串，我们要花最少次数变成答案串，我们可以确定一个位置，然后进行变换，这里有三种情况：

变选定位置和它的后一个位置
变选定位置和它的前一个位置
变选定位置和它的后一个位置，再变选定位置和它的前一个位置，即选定位置变了两次
接着根据递推关系把原串变了，在最后一次变换后判断可不可行，不同对齐的情况取 $ext{min}$ 就好。

整体时间复杂度 $mathcal{O}(n^2)$

代码：

Code

Problem C

题意：

给你两个串 $str1$ 和 $str2$ 以及 $m$ 种操作，对于第 $i$ 操作你可以花费 $cost_i$ 元，将字符 $c_i$ 编程字符 $v_i$ 。现在问你将 $str1$ 转化为 $str2$ 的最小花费。

分析：

考虑将这 $m$ 种操作的关系连边，并形成一个关系图。要想使得 $str1$ 转化成 $str2$ 的花费最少，显然是对于 $str1$ 中的每一个跟 $str2$ 不同的字符，我们要在关系图中找最小的花费。

因此这显然是一个多元最短路的问题，我们用 $ext{Floyd}$ 即可。

代码：

Code

Problem D

题意：

给你一个有 $n$ 个顶点的多边形，现在有 $m$ 个点对 $(x,y)$ ，现在让你求出这 $m$ 个点对中， $x$ 和 $y$ 所夹的最大的突变型的面积。

分析：

首先，对于一个 $n$ 边形，如果要求出他的面积，则我们可以把他划分成 $n-1$ 个三角形，之后我们只需要用叉积的形式求出这 $n-1$ 个三角形的面积即可。

而现在这个题目中，需要我们求 $m$ 个由点对 $(x,y)$ 围城的多边形，如果我们用上面的做法去做时间复杂度显然会达到 $mathcal{O}(nm)$ 。

但是我们发现，在我们求一个 $n$ 边形的面积的时候，我们是采用将面积累加的形式，而由此，我们可以采用前缀和去优化。

我们设 $ext{sum[i]}$ 为前 $i$ 个点所围成的多边形的面积，我们画一下图之后可以发现，点对 $(x,y)$ 所围成的面积即为： $ext{sum[y-1]-sum[x]-(p[x] ^ ~p[y]) }$ 。

代码：

Code

Problem E

题意：

给你一个边长为 $n$ 的正三角形，正三角形的每条边都有 $n-1$ 条线跟对应的边平行，且这 $n-1$ 条线都是平分线。

现在问你，在这样的一个三角形中，有多少个点对 $(x,y)$ ，使得由他们组成的线段 $xy$ 中，包含着点 $c$ ，使得点 $c$ 也是这个三角形的顶点。

分析：

因为 $n$ 比较小，因此我们可以打表。显然我们可以把这个边长为 $n$ 的 $frac{(1+n)*n}{2}$ 个顶点的坐标都表示出来，其次我们可以首先枚举线段的两个顶点 $x,y$ ，再枚举第三个点 $z$ ，判断是否存在一个点 $z$ 在线段 $x,y$ 中。

之后打表获取答案即可，打表的时间复杂度为 $mathcal{O}(n^5)$ ，鉴于 $n$ 还是比较小，还是可以在比较快的时间内得出答案的。

而这题也有时间复杂度为 $mathcal{O}(n^2)$ 的优秀算法，有时间再更新。

Problem F

题意：

有 $n$ 支队伍，每个队伍有 $3$ 个队员，每个队伍都有一个或多个擅长的领域（分别为A到Z）。而一个队伍最擅长的领域取决于他们中出现次数最多的（如果有多个则都是）。

现在规定，每个领域最多只能有 $k$ 个队伍擅长，现在问你，最多有多少个队伍符合条件。

分析：

网络流的裸题。

我们考虑先让每个队伍跟他符合条件的领域连边。

因为每个领域最多只能有 $k$ 个队伍擅长，因此，我们只需要对每个领域向超级汇点连接一条大小为 $k$ 的边限流即可。

最后把超级源点都给每个队伍连一条大小为 $1$ 的边作为流量，最后对这张图跑最大流即可。

代码：

Code

Problem G

分析：

先把每个字母的取和不取的概率算出来，要用到乘法逆元；接着进行 $dp$ ， $dp[i][j]$ 表示到长度i时猜中到第 $j$ 个的概率，最后将所有猜中到第 $m$ 个的概率加起来就是答案。
复杂度 $mathcal{O}(n*m)$

代码：

Code

Problem H

温暖的签到题，只需要知道平年每过一年星期数+1，如果是闰年，过一年后星期数+2即可。

Code

Problem I

貌似是一个温暖的签到题，可能因为没有外榜大家都没有很快的 $AC$ 。

实质上只需要模拟一下二进制循环移位的过程就结束了。

Code

Problem J

题意：

有 $n$ 个点， $m$ 条边。对于第 $i$ 条边，你可以从 $u_i$ 走到 $v_i$ ，花费 $c_i$ 元，花费 $t_i$ 时间。同时，你只能在时间 $s_i$ 时候进行移动，且你只能在每 $s_i+f_i 、s_i+2*f_i dots s_i+n*f_i$ 时刻进行移动。现在问你从 $1$ 号结点走到 $n$ 号结点的最少时间以及在此基础下的最小的花费。

分析：

虽然多了一个移动时间的限制，但是本质上还是一个最短路径的问题。

我们发现等待的过程可以分为两种：

当前的时间 $curleq s_i$
当前的时间 $cur > s_i$

对于第一种情况，我们显然只能等待到 $s_i$ 时候后，再花费 $t_i$ 的时间，故对于情况 $1$ ，此时需要花费的累计的时间为 $cur=s_i+t_i$

而对于第二种情况，要使的花费时间最小，我们必然想要等到一个最近的发车点，因此我们只需要获取需要等待的时间间隔 $frac{cur-s_i}{f_i}+1$ ，并用这个间隔算出最终所需的时间。

而倘若解决了上诉时间问题，之后我们只需要利用所算出的时间进行松弛操作即可。

代码：

Code

Problem K

Problem L

分析：

构造题，对于一个边长为 $N=2^n$ 的矩阵，我们可以每次对它一分为 $4$ ，类似“田”字，然后查找哪个子矩阵有一个点被占用，即有被填过或为一开始的 $(x,y)$ ，然后在四个矩阵的交界处，填上一个 $L$ ，这个 $L$ 经过另外三个矩阵，这时候四个子矩阵都有一个点被占用了，接下来我们对子矩阵再进行同样的操作，直到矩阵不可再分。

最后填色，对你填 $L$ 过程中的 $L$ 打标记，最后 $\%26$ 填字母就行，要说正确性，题目中 $2^n$ 的矩阵， $n$ 最大才 $11$ ，你递归过程中，按顺序来，碰撞概率是极低的吧
复杂度 $mathcal{O}(N*N)$

代码：

Code

Problem M

分析：

一个比较简单的概率的问题……

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a,b,k;
int main(){
    cin>>a>>b>>k;
    double ans=0;
    ll res=b-k+1;
    if (k>b) ans=1.0*b/k;
    else  ans=1.0*((k-1)+1.0*res/(res+a))/k;
    printf("%.7f
",ans);
    return 0;
}