eat12ac

分类

未归档(8) 题解(4)

/ 注册

全部文章（共12篇）

E - Enigmatic Partition

E 时间复杂度计算 + 暴力题意设为满足的方案数，其中要求：有次询问，每次询问给出一个 , 保证，请求出：思路先枚举出 : for (int i = M; i < N; ++i) { // p > r 的情况 for (int ...

2020-08-04

0 726

K - K-Bag

K 思维思路一个 Part-K-Bag 一定是由 "零个或多个 K-Bag" + "不含 K-Bag 的 Part-K-Bag" 组成。为方便起见，下称 "零个或多个 K-Bag" 为 K-Bags, "不含 K-Bag 的 Part-K-Bag" 为 Exclude-K-Bag。 1、我们先...

2020-07-31

0 638

H - Harmony Pairs

数位DP 题意给你一个数，问你符合以下条件的有序对有几个：1、其中代表在十进制下的数位和2、思路数位DP基本操作：1、先写一个按数位的暴力 DFS (不要使用全局状态变量) // pos: 当前要处理的位 // digitA: A数字当前位的取值范围 [0, digitA...

2020-07-30

0 497

D - Points Construction Problem

D 构造题意有一个无限大的白色网格，要求你涂黑 n 个点，构造 m 个异色点对，求这个点序列。思路我们将黑点想象成黑色正方形，异色点对数想象成边长。那么这个图可以看成由多个 ”黑色正方形“ 构成的黑色多边形组成。先考虑上界：由于一个黑色正方形最多有 4 条边，因此 m >= 4n...

2020-07-30

0 628

J - Easy Integration

J 高数签到题思路令，有，换元得由华莱士公式：于是：

2020-07-30

0 489

I - 1 or 2

I 一般图最大匹配思路一看就是个匹配问题，不过属于多重匹配。我们可以通过拆点，拆成一般匹配。留意到很小，可以直接把点拆成个点，这些点记为为了保留匹配关系，还需要拆边。对于边：1、先建立两个中介点2、将所有点和连接 (无向边)3、将所有点和连接 (无向边)4、连接...

2020-07-30

0 554

H - Minimum-cost Flow

H 有趣的网络流题意费用网络中每条边的容量均为u/v，输入大小为1的流，问最小费用是多少。多次询问不同的u/v。思路先特判容量为0，输出NaN。考虑转化网络，容量为u/v的边可以看作容量为1(F)的边（F为单位），那么输入大小为1的流相当于输入大小为 v/u (F) 的流由于费用流容量...

2020-07-30

0 469

F - Infinite String Comparision

F 暴力莽签到题题意两个串s, t, 试比较和的大小关系思路根据Periodicity Lemma可知，若在范围内没有适配，那么和相等，否则按照字典序关系比较。代码 #include <algorithm> #include <iostream> #inclu...

2020-07-30

0 572

E - Counting Spanning Trees

E 猜结论题意给一个特殊的二分图，要求你算出它生成树的个数，其中顶点数思路如果图的定点数小于，可以用矩阵树定理爆算，复杂度但是，这个图很大，尝试猜结论... 首先，从小图开始猜，比如样例3的基尔霍夫矩阵： [ 1, 0, 0,-1, 0, 0 ], [ 0, 2, 0,-1,-1...

2020-07-30

0 457

D - Quadratic Form

D 凸优化题意给出正定的实对称矩阵和向量,向量满足约束：，试求思路构造拉格朗日函数，，其中，那么首先对求偏导，得：得到取最大值时，有：由拉格朗日对偶性，可得：再对求偏导，得：得到：，联立，可得，取最大值时：同样地，取最大值时：，故：高斯消元求逆即可，时间复杂度...

2020-07-30

0 511