Codeforces Round #660 https://codeforces.com/contest/1388 E 题意 平面上有一些线段，将他们投影到$x$轴上，使得彼此不想交(但是可以挨着)，设最左边的点和最右边的点的横坐标分别是$x_l, x_r$， 求$min{x_r-x_l}$ Solution 首先对于两个线段$s_1, s_2$, 并且$s_1.y < s_2.y$, 交叉连接他们的左右端点，得到一个向量集合$bound$，对投影向量限制限制。 因此先两两枚举，得到投影向量的可行的取值。 而且最优的投影向量，是集合$bound$中的某一项 因此，对剩下的可行的投影向量, 假设当前枚举的方向是$k_i$，计算 $$ max{x_j+y_jKi}-min{x_j+y_jk_i} $$ 计算这个式子可以用Convex hull trick, 然后不断更新ans #include <cstdio> #include <stack> #include <set> #include <cmath> #include <map> #include <time.h> #include <vector> #include <iostream> #include <string> #include <cstring> #include <algorithm> #include <memory.h> #include <cstdlib> #include <queue> #include <iomanip> #include <bitset> #include <unordered_map> #include <assert.h> #include <list> #define P pair<int, int> #define LL long long #define LD long double #define PLL pair<LL, LL> #define mset(a, b) memset(a, b, sizeof(a)) #define rep(i, a, b) for (int i = a; i < b; i++) #define PI acos(-1....

nowcoder 2020 多校 第三场 E Two Matchings 题意 可以简化题意为，每个点有个权重$w$，两个点$i,j$相连的代价$abs(w_i-w_j)$,找两个没有重叠的匹配使得代价最小 Solution 其实就是在将数字用长度为偶数的环连起来，求最小代价。进一步可以发现，环用长度为4或6，长度更长的环可以被分解达到更小的代价 LL n; LL a[MAX]; LL dp[MAX][2]; LL four(const vector<LL> &a){ return 2LL * (a[3]-a[0]); } LL six(const vector<LL> &a){ return 2LL * (a[5]-a[0]); } int main(){ #ifdef DEBUG freopen("in", "r", stdin); #endif int T; scanf("%d", &T); while (T--) { cin >> n; for(int i = 0; i < n; i++) cin >> a[i]; sort(a, a+n); for(LL i = 0; i <= n; i++ ) dp[i][0] = dp[i][1] = __64inf; dp[3][0] = 2LL * (a[3]-a[0]); dp[5][0] = 2LL * (a[5]-a[0]); dp[7][0] = 2LL * (a[7]-a[4] + a[3] - a[0]); for(LL i = 9; i < n; i+=2){ dp[i][0] = min(dp[i-4][0], dp[i-4][1]) + four(vector<LL>({a[i-3], a[i-2], a[i-1], a[i]})); dp[i][1] = min(dp[i-6][0], dp[i-6][1]) + six(vector<LL>({a[i-5], a[i-4], a[i-3], a[i-2], a[i-1], a[i]})); } printf("%d\n", min(dp[n-1][0], dp[n-1][1])); } } F Fraction Construction Problem 题意...

nowcoder 2020 多校 第五场 https://ac.nowcoder.com/acm/contest/5670 B Graph tire树，最小生成树 题意： 给一个带有边权的树，可以删除或添加边，但要保证： 图联通 环上边权异或为0 Solution 不管怎么操作，两点路径上边权的异或值是固定的，于是问题就转化成一个最小生成树问题。每次选出不联通的点集$S_1$, $S_2$, 将他们联通的代价是 $$ \min\limits_{u\in S_1 v\in S_2} {\mathord{dis}(u,v)} $$ 可以通过tire树实现这个过程，就是tire树合并子节点，复杂度为$O(n\log n)$ #include <cstdio> #include <stack> #include <set> #include <cmath> #include <map> #include <time.h> #include <vector> #include <iostream> #include <string> #include <cstring> #include <algorithm> #include <memory.h> #include <cstdlib> #include <queue> #include <iomanip> #include <bitset> #include <unordered_map> #include <assert.h> #define P pair<int, int> #define LL long long #define LD long double #define PLL pair<LL, LL> #define mset(a, b) memset(a, b, sizeof(a)) #define rep(i, a, b) for (int i = a; i < b; i++) #define PI acos(-1....

POJ 3376 tire + manacher 题意 http://poj.org/problem?id=3376 给$n$个串，两两连接，一共$n^2$种，求其中有多少是回文， 字符串的长度和小于$2e6$ Solution 在考虑第$i$个串$t$和多少个串$s$拼接是回文时，计算$s+t$是回文的数量，将所有数量累加就是最终的回文数。 首先考虑什么情况下，两个串拼接会是一个回文串。 case 1： s=reverse(t) $$ \begin{cases} s = a_0\dots a_{n-1} \newline t = a_{n-1}\dots a_0 \end{cases} $$ case 2 $$ \begin{cases} \begin{matrix} &\mathrm{palindrome} \newline s = a_0\dots a_i &\overbrace{a_{i+1}\dots a_{n-1}} \end{matrix} \newline \newline t = a_i\dots a_0 \end{cases} $$ 以及对称的情况 $$ \begin{cases} s = a_{n-1}\dots a_i \newline \begin{matrix} \ \ \ \ \ \mathrm{palindrome} &\newline t = \overbrace{a_0\dots a_{i-1}} &a_i\dots a_{n-1} \end{matrix} \end{cases} $$...

nowcoder 2020 多校 第二场 https://ac.nowcoder.com/acm/contest/5667 A All with Pairs 题意 给$n$个串，定义$f(s,t)$为$s$前缀和$t$后缀最长的长度，求$\sum_i\sum_j f(s_i, s_j)^2$ Solution 先把每个串的后缀hash的值存下来，对每个串$s_i$,求$\sum_j f(s_i, s_j)^2$。对于$s_i$的每个前缀都可以查询hash求出 对应多少后缀，但是有可能一对$s_i, s_j$会有多个贡献，因此要用next数组去重 const unsigned long long base = 131; // vector<string> str; string str[MAX]; unordered_map<unsigned long long, int> mp; int nex[MAX]; int cnt[MAX]; void get_hash(const string &s){ unsigned long long res = 0; unsigned long long p = 1; for(int i = s.size()-1; i >= 0; i--){ // unsigned long long x = s[i] - 'a'+1; res += (s[i]-'a'+1) * p; p *= base; mp[res]++; } } void get_next(const string &t){ nex[0] = -1; int k = -1; for(int i = 1; i < t....