# Nordic Collegiate Programming Contest 2018 [NCPC2018] 题解

unsolved

### B. Baby Bites

solved (0:08, +1)

solved (0:17)

solved (4:55)

solved (3:23)

unsolved

unsolved

solved (0:34)

solved (1:00 +1)

solved (1:57 +2)

solved (3:07)

# [2017-2018 ACM-ICPC Latin American Regional Programming Contest] A. Arranging tiles

### 代码

#include <bits/stdc++.h>
using namespace std;

#define rep(i, n) for (int i = 0; i < (n); i++)
#define Rep(i, n) for (int i = 1; i <=(n); i++)
#define range(x) begin(x), end(x)

constexpr double EPS = 1e-8;

int fcmp(double x, double y = 0.0) {
if (fabs(x - y) < EPS) return 0;
return x < y ? -1 : 1;
}

typedef double T;
typedef struct pt {
T x, y;
T operator,(pt a) { return x * a.x + y * a.y; }  // inner product
T operator*(pt a) { return x * a.y - y * a.x; }  // outer product
pt operator+(pt a) { return {x + a.x, y + a.y}; }
pt operator-(pt a) { return {x - a.x, y - a.y}; }

pt operator*(T k) { return {x * k, y * k}; }
pt operator-() { return {-x, -y}; }
} vec;

typedef pair<pt, pt> seg;

int n;
int height;

struct polygon {
int width;
vector<pair<int, int>> lpart, rpart;

void init(vector<pair<int, int>>& pts) {
int minx = INT_MAX, maxx = INT_MIN;
for (auto& p : pts) {
height = max(height, p.second);
minx = min(minx, p.first);
maxx = max(maxx, p.first);
}
width = maxx - minx;
for (auto& p : pts) p.first -= minx;
int i = 1;
while (pts[i].second < height) rpart.push_back(pts[i++]);
rpart.push_back(pts[i++]);
while (i < pts.size()) lpart.push_back(pts[i++]);
lpart.push_back(pts[0]);
reverse(range(lpart));
}
} poly[16];

pt getMidPoint(pair<int, int> pt1, pair<int, int> pt2, double y) {
pt a { (double) pt1.first, (double) pt1.second },
b { (double) pt2.first, (double) pt2.second };
vec v = (b - a) * (1.0 / (b.y - a.y));
return a + v * (y - a.y);
}

double max_overlap(polygon& polyl, polygon& polyr) {
vector<pair<int, int>> &lpts = polyl.rpart, &rpts = polyr.lpart;
int ln = lpts.size(), rn = rpts.size(), yn;
vector<int> ys;
{
vector<int> yl(ln), yr(rn);
rep (i, ln) yl[i] = lpts[i].second;
rep (i, rn) yr[i] = rpts[i].second;
set_union(range(yl), range(yr), back_inserter(ys));
yn = ys.size();
}
int lptr = 0, rptr = 0;
double min_dif = 0.0;
rep (i, yn) {
pt lp = getMidPoint(lpts[lptr], lpts[lptr+1], ys[i]),
rp = getMidPoint(rpts[rptr], rpts[rptr+1], ys[i]);
min_dif = max(min_dif, lp.x - rp.x);
while (lptr < ln-1 && lpts[lptr+1].second <= ys[i]) lptr++;
while (rptr < rn-1 && rpts[rptr+1].second <= ys[i]) rptr++;
}
return polyl.width - min_dif;
}

double g[16][16];
double dp[1 << 14][16];

int main() {
scanf("%d", &n);
rep (i, n) {
int k; scanf("%d", &k);
vector<pair<int, int>> pts;
rep (j, k) {
int x, y; scanf("%d%d", &x, &y);
pts.emplace_back(x, y);
}
poly[i].init(pts);
}
rep (i, n) {
rep (j, n) {
if (i == j) continue;
g[i][j] = max_overlap(poly[i], poly[j]);
}
}
while (rem) {
unsigned bit = rem & -rem;
int i = __builtin_ctz(bit);
rep (j, n) {
if (j == i || ((1 << j) & mask) == 0) continue;
}
rem -= bit;
}
} else {
rep (j, n) dp[mask][j] = (j == i ? 0.0 : -1e15);
}
}
double ans = *max_element(range(dp[(1<<n)-1]));
double tot = 0.0;
rep (i, n) tot += poly[i].width;
printf("%.3f\n", tot - ans);
return 0;
}


# 2018牛客暑期ACM多校训练营（第一场）题解

### A. Monotonic Matrix

• $a_{i,j} \in \{0, 1, 2\}$
• 每一行从左到右和每一列从上到下单调不减

### F. Sum of Maximum

$\sum_{x_1=1}^{a_1} \sum_{x_2=1}^{a_1} \cdots \sum_{x_n=1}^{a_n} \max\{x_1, x_2, \cdots, x_n\}$

# 2017-2018 问题求解（四）上机考试题解

## Day1

#### A 差异度

1. 注意到当$n$很大时，最终答案不会太大（考虑一个01串hamming距离为$d$的邻域大小随$d$是指数增长的，然后用鸽巢原理即可）。所以，从小到大枚举答案$d$，并在每个串的$d$-邻域内搜索即可。
2. 建图。将所有20位的01串视为顶点，相差1位的两个串连边。问题就变成了：给定一个顶点子集，求这个子集中两两距离的最小值。这用多线程bfs就可以解决。时间复杂度为$2^{20}*20$。
3. 用FWT处理出所有可能的异或值，取popcount最小的那个即可。（FWT课内没学，用了感觉有点犯规，但写起来方便是真的

B 旅行箱