# 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]);
}
}
for (unsigned mask = 1; mask < (1 << n); mask++) {
if (mask & (mask - 1)) {
unsigned rem = mask;
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 {
int i = __builtin_ctz(mask);
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 旅行箱

# 2016 China Collegiate Programming Contest Final 题解

（更新中）

### Problem A. The Third Cup is Free

#include<bits/stdc++.h>
#define MAXN 100005
#define INF 1000000000
#define MOD 1000000007
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
int t,n,a[MAXN];
int main()
{
scanf("%d",&t);
int kase=0;
while(t--)
{
kase++;
printf("Case #%d: ",kase);
scanf("%d",&n);
int sum=0;
for(int i=0;i<n;i++)
{
scanf("%d", &a[i]);
sum += a[i];
}
sort(a,a+n);
for(int i=n-3;i>=0;i-=3)
sum-=a[i];
printf("%d\n",sum);
}
return 0;
}

### Problem B. Wash

#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;

#ifdef __LOCAL_DEBUG__
# define _debug(fmt, ...) fprintf(stderr, "\033[94m%s: " fmt "\n\033[0m", \
__func__, ##__VA_ARGS__)
#else
# define _debug(...) (void(0))
#endif

#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) (x).begin(), (x).end()
typedef long long LL;
typedef unsigned long long ull;

int l, n, m;
LL w[100006], d[100006];
LL t1[1000006], t2[1000006];

typedef pair<LL, int> p;

int main() {
int T; scanf("%d", &T);
Rep (t, T) {
priority_queue<p, vector<p>, greater<p> > q1, q2;
scanf("%d%d%d", &l, &n, &m);
rep (i, n) {
int a; scanf("%d", &a);
w[i] = a;
q1.push({w[i], i});
}
rep (i, m) {
int a; scanf("%d", &a);
d[i] = a;
q2.push({d[i], i});
}
rep (i, l) {
LL val; int id;
tie(val, id) = q1.top(); q1.pop();
_debug("i=%d, val=%lld, id=%lld, l-1-i=%d", i, val, id, l-1-i);
t1[i] = val;
q1.push({val+w[id], id});
}
rep (i, l) {
LL val; int id;
tie(val, id) = q2.top(); q2.pop();
_debug("i=%d, val=%lld, id=%lld, l-1-i=%d", i, val, id, l-1-i);
t2[l-1-i] = val;
q2.push({val+d[id], id});
}
LL ans = 0;
rep (i, l) {
ans = max(ans, t1[i] + t2[i]);
}
cout << "Case #" << t << ": " << ans << endl;
}
return 0;
}

### Problem G. Pandaland

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

#ifdef __LOCAL_DEBUG__
# define _debug(fmt, ...) fprintf(stderr, "\033[94m%s: " fmt "\n\033[0m", \
__func__, ##__VA_ARGS__)
#else
# define _debug(...) ((void) 0)
#endif
#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) (x).begin(), (x).end()
typedef long long LL;
typedef unsigned long long ULL;

#define int LL
#undef INT_MAX
#define INT_MAX LLONG_MAX

typedef pair<int, int> pt;

struct Sol {
int n = 0;
map<pt, int> mp;
vector<pair<int, int>> edges;

int getID(int x, int y) {
auto ptr = mp.find({x, y});
if (ptr != mp.end()) return ptr->second;
mp[{x, y}] = n;
return n++;
}

int ans = INT_MAX / 2;
int d[10000];
bool done[10000];

void dijkstra(int src) {
priority_queue<pt, vector<pt>, greater<pt>> q;

fill(d, d+n, INT_MAX / 2);
d[src] = 0;
fill(done, done+n, false);
q.push({0, src});
while (q.size()) {
int u = q.top().second; q.pop();
if (done[u]) continue;
done[u] = 1;
for (int id : adj[u]) {
int v, w; tie(v, w) = edges[id];
if (d[v] > d[u] + w) {
d[v] = d[u] + w;
if (d[v] < ans) q.push({d[v], v});
}
}
}
}

Sol(int t) {
int m; cin >> m;
edges.resize(m+m);
rep (i, m) {
int x1, y1, x2, y2, w;
int id1, id2;
cin >> x1 >> y1 >> x2 >> y2 >> w;
id1 = getID(x1, y1); id2 = getID(x2, y2);
edges[i<<1] = {id2, w};
edges[i<<1|1] = {id1, w};
}
rep (u, n) {
for (int id : adj[u]) {
int v, w;
tie(v, w) = edges[id];
edges[id].second = edges[id^1].second = INT_MAX / 2;
dijkstra(u);
ans = min(ans, d[v] + w);
edges[id].second = edges[id^1].second = w;
}
}
if (ans >= INT_MAX / 2) ans = 0;
cout << "Case #" << t << ": " << ans << endl;
}
};

int32_t main() {
int T; cin >> T;
Rep (t, T) {
Sol sol(t);
}
return 0;
}



### Problem I. Mr. Panda and Crystal

#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;

#ifdef __LOCAL_DEBUG__
# define _debug(fmt, ...) fprintf(stderr, "\033[94m%s: " fmt "\n\033[0m", \
__func__, ##__VA_ARGS__)
#else
# define _debug(...) (void(0))
#endif

#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) (x).begin(), (x).end()
typedef long long LL;
typedef unsigned long long ull;

int m, n, k;
LL c[256], v[256];

vector<int> dep[205];
//   id                id  cnt
pair<int, vector<pair<int, int>>> formula[205];

bool flag = false;

void update(int i) {
LL tot = 0;
int id = formula[i].first;
for (auto& item : formula[i].second) {
tot += c[item.first] * item.second;
}
if (tot < c[id]) {
_debug("update %d!", formula[i].first);
c[formula[i].first] = tot;
flag = true;
}
}

LL dp[10005];

int main() {
int T; scanf("%d", &T);
Rep (t, T) {
scanf("%d%d%d", &m, &n, &k);
Rep (i, n) {
int tp; scanf("%d", &tp);
int co = INT_MAX, va = 0;
if (tp == 0) {
scanf("%d", &va);
} else {
scanf("%d%d", &co, &va);
}
c[i] = co;
v[i] = va;
}
_debug("!");
rep (i, k) {
int x, y;
scanf("%d%d", &x, &y);
formula[i].first = x;
formula[i].second.resize(y);
rep (j, y) {
int u, v;
scanf("%d%d", &u, &v);
formula[i].second[j] = {u, v};
}
}
_debug("!");
do { // bellman-ford
flag =  false;
rep (i, k) update(i);
} while (flag);
memset(dp, 0, sizeof dp);
Rep (i, n) {
for (int w = c[i]; w <= m; w++) {
dp[w] = max(dp[w], dp[w - c[i]] + v[i]);
}
}
printf("Case #%d: %d\n", t, int(dp[m]));
}
return 0;
}

### Problem L. Daylight Saving Time

#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;

#ifdef __LOCAL_DEBUG__
# define _debug(fmt, ...) fprintf(stderr, "\033[94m%s: " fmt "\n\033[0m", \
__func__, ##__VA_ARGS__)
#else
# define _debug(...) (void(0))
#endif

#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) (x).begin(), (x).end()
typedef long long ll;
typedef unsigned long long ull;

enum {
A, B, C, D
};

const int  mday[13] = { 0,
31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31
};

int type = A;
int yy = 2007, mm = 1, dd = 1;
int wday = 1;

bool isleap(int y) {
if (y % 4 == 0  && y != 2100) return true;
return false;
}

yy++;
}

mm++;
if (mm > 12) {
mm = 1;
}
}

dd++;
wday ++;
if (wday > 7) wday = 1;
int mmday = mday[mm];
if (mm == 2 && isleap(yy)) mmday++;
if (dd > mmday) {
dd = 1;
}
if (mm == 3 && wday == 7 && dd > 7 && dd <= 14) {
type = C;
return B;
}
if (mm == 11 && wday == 7 && dd <= 7) {
type = A;
return D;
}
return type;
}

string genstr() {
char buf[100];
sprintf(buf, "%04d-%02d-%02d", yy, mm, dd);
return string(buf);
}

map<string, int> m;

void prep() {
m[genstr()] = type;
do {
int tp = advan();
m[genstr()] = tp;

} while (yy <= 2100);
}

int main() {
prep();
string str;
char tim[20];
int hh;
int T;
cin >> T;
Rep(t, T) {
cin >> str >> tim;
sscanf(tim, "%d", &hh);
switch (m[str]) {
case A:
printf("Case #%d: PST\n", t);
break;
case B:
if (hh < 2) {
printf("Case #%d: PST\n", t);
} else if (hh >= 3) {
printf("Case #%d: PDT\n", t);
} else {
printf("Case #%d: Neither\n", t);
}
break;
case C:
printf("Case #%d: PDT\n", t);
break;
case D:
if (hh < 1) {
printf("Case #%d: PDT\n", t);
} else if (hh >= 2) {
printf("Case #%d: PST\n", t);
} else {
printf("Case #%d: Both\n", t);
}
break;
}
}
return 0;
}