月度归档:2018年08月

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

链接:http://codeforces.com/gym/101889

题意

给定N个凸多边形\(1 \leq N \leq 14\),每个凸多边形有一条\(y=0\)和\(y=H\)的边。将这些多边形在\(0 \leq y \leq H\)的区域内排成一排,不允许重叠,求最小的总宽度。允许调换多边形的次序,但不能旋转。

题解

首先可以进行一些预处理:将每个多边形向右平移,直到最左边的端点在y轴上,然后将多边形的左半部分和右半部分分离开来。

原问题可以分为明显的两个部分:首先,两两枚举多边形,求出这两个多边形拼起来的收益(即它们各自宽度之和减去拼起来的宽度),然后,在一个完全图上求出最长哈密尔顿路即可。后一个问题用经典的状压dp即可解决,前一个问题则可以用扫描线解决。

注意到两个多边形的接触点必为其中某一个多边形的顶点。因此,只需要处理出两个多边形的所有顶点的y坐标,然后依次求出每个y坐标处可能得到的收益,并去最小值即可。

总复杂度为\(O(N^2K + N^2 2^N)\)。

代码

#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);
        dp[mask][i] = -1e15;
        rep (j, n) {
          if (j == i || ((1 << j) & mask) == 0) continue;
          dp[mask][i] = max(dp[mask][i], dp[mask ^ bit][j] + g[j][i]);
        }
        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 Multi-University Training Contest 10] C. Calculate

Link: http://acm.hdu.edu.cn/showproblem.php?pid=6428

Statement:

Given \(1 \leq A, B, C \leq 10^7\), compute

\[ \sum_{i=1}^A \sum_{j=1}^B \sum_{k=1}^C \phi(\gcd(i, j^2, k^3)) \]

no more than 10 test cases.

Solution:

Consider the number of triples (i, j, k) such that \( \gcd(i, j^2, k^3) = d\), denoted as \(f(d)\). By Mobius inversion,

\[ f(d) = \sum_{i} \mu(i) g(di) \]

where \(g(d)\) is the number of triples satisfying \( d | \gcd(i, j^2, k^3) \), and the answer should be

\[ \sum_{d=1}^A f(d) \phi(d) \]

Now we try to compute \(g(d)\):

\[ g(d) = \sum_{i = 1}^A [d | i] \sum_{j = 1}^B [d | j^2] \sum_{k = 1}^C [d | k^3] \]

Let \(d = \prod {p_i}^{a_i} \) denote the unique factorization of d. Note that \(d | k^n \) whenever \( \prod {p_i}^{\lceil a_i / n \rceil} | k \).

Let \( h_n(d) = \prod {p_i}^{\lceil a_i / n \rceil} \), which denotes the minimum positive integer whose nth power is divisible by d. Now \(g(d)\) could be rewritten as

\[ g(d) = \lfloor \frac{A}{d} \rfloor \lfloor \frac{B}{h_2(d)} \rfloor \lfloor \frac{C}{h_3(d)} \rfloor \]

Plug in answer:

\[ \sum_{d=1}^A f(d) \phi(d) = \sum_{d=1}^A \phi(d) \sum_{i} \mu(i) g(di) = \sum_{q = 1}^A g(q) \sum_{ij = q} \mu(i) \phi(j) \]

where the Dirichlet convolution \( (\mu * \phi)(q) = \sum_{ij = q} \mu(i) \phi(j) \) is multiplicative and thus could be effectively precomputed (along with \(h_2\), \(h_3\)) by the sieve of Euler in linear time. Hence each test case could be done in \(O(A)\) time.

Source Code:

#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;

namespace sieve {
  constexpr int MAXN = 10000007;
  bool p[MAXN];
  int prime[MAXN], sz;
  int pval[MAXN], pcnt[MAXN];
  unsigned h2[MAXN], h3[MAXN], phi[MAXN], muphi[MAXN];

  void exec(int N = 10000007) {
    p[0] = p[1] = 1;
    
    pval[1] = 1;
    pcnt[1] = 0;
    h2[1] = h3[1] = phi[1] = muphi[1] = 1;

    for (int i = 2; i < N; i++) {
      if (!p[i]) {
        prime[sz++] = i;
        for (LL j = i; j < N; j *= i) {
          int b = j / i;
          pval[j] = i * pval[b];
          pcnt[j] = pcnt[b] + 1;
          h2[j] = h2[b] * (pcnt[j] % 2 == 1 ? i : 1);
          h3[j] = h3[b] * (pcnt[j] % 3 == 1 ? i : 1);
          phi[j] = (i == j ? i-1 : phi[b] * i);
          muphi[j] = phi[j] - phi[b];
        }
      }
      for (int j = 0; i * prime[j] < N; j++) {
        int x = i * prime[j]; p[x] = 1;
        if (i % prime[j] == 0) {
          pval[x] = pval[i] * prime[j];
          pcnt[x] = pcnt[i] + 1;
        } else {
          pval[x] = prime[j];
          pcnt[x] = 1;
        }
        if (x != pval[x]) {
          int b = x / pval[x];
          h2[x] = h2[b] * h2[pval[x]];
          h3[x] = h3[b] * h3[pval[x]];
          muphi[x] = muphi[b] * muphi[pval[x]];
        }
        if (i % prime[j] == 0) break;
      }
    }
  }
}

int main() {
  using namespace sieve;
  exec();
  int T; scanf("%d", &T);
  while (T--) {
    unsigned a, b, c; scanf("%d%d%d", &a, &b, &c);
    unsigned res = 0;
    for (unsigned i = 1; i <= a; i++) 
      res += muphi[i] * (a / i) * (b / h2[i]) * (c / h3[i]); 
    printf("%d\n", res & 0x3fffffff);
  }
  return 0;
}

 

[2017 ACM-ICPC WF] Airport Construction

题意:

给定一个简单多边形(不一定凸),求完全位于该简单多边形边界及内部的最长线段的长度。点数200,坐标为整数且绝对值不超过1e6。

题解:

可以证明存在一条最优的的线段经过多边形的两个顶点。假设最优线段不经过顶点,则总可以向某一方向平移最优线段使得其长度不减少,直到碰到某一个顶点。然后绕着该顶点旋转,总有一个旋转方向使得线段的长度不会减小,直到线段碰到另一个顶点为止。

然后算法就很显然了:枚举多边形的两个顶点并将其延长,并用多边形将直线打散成若干条线段,删去在多边形外的线段,并将多边形内的连续线段合并,取最大的即可。枚举多边形两个顶点是\(O(n^2)\)的,打散成线段是\(O(n)\)的,判断线段是否在多边形内可以取中点,转化为点是否在多边形内,复杂度为\(O(n)\)。总复杂度为\(O(n^4)\),写的时候代码过于粗糙T了一发 QAQ

本题复杂度可以降到\(O(n^3)\),但具体做法还没仔细研究…

#pragma GCC optimize(3)
#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)

typedef complex<double> pt, vec;
typedef pair<pt, pt> seg;

const double EPS = 1e-8;
int fcmp(double a, double b = 0.0) {
  if (fabs(a - b) < EPS) return 0;
  return a < b ? -1 : 1;
}

double operator * (pt a, pt b) {
  return a.real() * b.imag() - a.imag() * b.real();
}

double operator , (pt a, pt b) {
  return a.real() * b.real() + a.imag() * b.imag();
}

inline bool ptOnSeg(pt p, seg s){
    vec v1 = s.first - p, v2 = s.second - p;
    return fcmp((v1, v2)) <= 0 && fcmp(v1 * v2) == 0;
}

inline pt getIntersection(pt P, vec v, pt Q, vec w) {
    return P + v * (w*(P-Q)/(v*w));
}

// -1 outside the polygon
// 0  on the border of the polygon
// 1  inside the polygon
int ptOnPoly(pt p, pt* poly, int n){
//  fprintf(stderr, "(%.7f, %.7f)\n", p);
    int wn = 0;
    for (int i = 0; i < n; i++){
        if (ptOnSeg(p, {poly[i], poly[i+1]})) return 0;
        int d1 = fcmp(poly[i].imag() - p.imag()), 
            d2 = fcmp(poly[i+1].imag() - p.imag()),
            k = fcmp((poly[i+1] - poly[i])*(p - poly[i]));
        if (k > 0 && d1 <= 0 && d2 > 0) wn++;
        if (k < 0 && d2 <= 0 && d1 > 0) wn--;
    }
    return wn ? 1 : -1;
}

istream& operator >> (istream& lhs, pt& rhs){
  double x, y;
  lhs >> x >> y;
  rhs = {x, y};
  return lhs;
}

int n;
vector<pt> poly;
double ans = 0.0;

void attempt(pt a, pt b) {
  vector<pt> points;
  rep (i, n) 
    if (fcmp((b-a)*(poly[i]-a)) * fcmp((b-a)*(poly[i+1]-a)) <= 0) {
      auto vec1 = b-a, vec2 = poly[i+1] - poly[i];
      if (fcmp(vec1 * vec2) == 0) {
        points.push_back(poly[i]);
        points.push_back(poly[i+1]);
      } else {
        points.push_back(getIntersection(a, b-a, poly[i], poly[i+1]-poly[i]));
      }
    }
  sort(range(points), [] (pt a, pt b) {
        return make_pair(a.real(), a.imag()) < make_pair(b.real(), b.imag());
      });
  points.resize(unique(range(points), [] (pt a, pt b) {
          return fcmp(a.real(), b.real()) == 0 && fcmp(a.imag(), b.imag()) == 0;
        }) - points.begin());
  double cur = 0.0;
  assert(points.size() > 1);
  for (int i = 1; i < points.size(); i++) {
    if (ptOnPoly((points[i]+points[i-1]) / 2.0, poly.data(), n) >= 0) {
      cur += abs(points[i] - points[i-1]);
    } else {
      cur = 0.0;
      if (abs(points.back() - points[i]) <= ans) return;
    }
    ans = max(ans, cur);
  }
}

int main() {
  cin >> n; poly.resize(n);
  rep (i, n) cin >> poly[i];
  poly.push_back(poly[0]);
  rep (i, n) {
    rep (j, i) {
      attempt(poly[i], poly[j]);
    }
  }
  printf("%.8f\n", ans);
  return 0;
}