[2017-2018 ACM-ICPC Latin American Regional Programming Contest] D. Daunting device

link: http://codeforces.com/gym/101889

Statement

Given an array of length \( 1 \leq L \leq 10^5 \), initially filled with 1. Define cnt[i] as the number of elements in the array that are equal to i. You should perform no more than \(10^5\) operations. Each operation is four integers \(P, X, A, B\), and let \(M_1 = (A + S^2) \bmod L, M_2 = (A + (S + B)^2) \bmod L\), where S = cnt[P], then assign all elements with indices in \([min(M_1, M_2), max(M_1, M_2)]\) with value X. After all operations performed, output the maximum cnt[i] over all possible values of i.

Solution

The main idea of the solution is just to simulate the operations in a reasonable time complexity. In fact, various possible solutions exist, including segment tree and square root decomposition. However, the fastest solution (at least theoretically) I know is employing balanced binary search trees.

We use the nodes of the balanced binary search tree to represent contiguous intervals of the array with same values. Additionally, we maintain an array “cnt”, which has the meaning as described in problem statement.

When updating an interval [l, r) to value X, we delete all nodes representing the interval [l, r), updating the array “cnt”. Note that this may split the nodes that across the boundaries of given interval. Finally, we inserting a new node which represents [l, r) with value X, and updating “cnt”.

Each operation can be done in amortized \( O(\log L) \) time, since in each operation, only constant number of nodes are inserted, though it is possible that a great number of nodes are deleted. Hence the total time complexity is \( O(n \log L) \).

Source Code

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;

#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, c, n;
int cnt[100005];

typedef tree<int, pair<int, int>, less<int>, rb_tree_tag> rbtree;

#define tree shuorgsrh
rbtree tree;

void update(int l, int r, int c) {
  rbtree mpart, rpart;

  tree.split(l - 1, mpart);
  int dif;
  if (tree.size() && 
      (dif = tree.rbegin()->first + tree.rbegin()->second.first - l) > 0) {
    tree.rbegin()->second.first -= dif;
    mpart.insert(make_pair(l, make_pair(dif, tree.rbegin()->second.second)));
  }
  mpart.split(r, rpart);

  if (mpart.size() && 
      (dif = mpart.rbegin()->first + mpart.rbegin()->second.first - r) > 0) {
    mpart.rbegin()->second.first -= dif;
    rpart.insert(make_pair(r, make_pair(dif, mpart.rbegin()->second.second)));
  } 
  for (auto& p : mpart) { 
    cnt[p.second.second] -= p.second.first;
  }
  cnt[c] += r - l;
  tree.insert(make_pair(l, make_pair(r - l, c)));
  tree.join(rpart);
}

int main() {
  scanf("%d%d%d", &l, &c, &n);
  cnt[1] = l;
  tree.insert(make_pair(0, make_pair(l, 1)));
  rep (i, n) {
    int p, x, a, b;
    scanf("%d%d%d%d", &p, &x, &a, &b);
    int m1 = (a + 1ll * cnt[p] * cnt[p]) % l;
    int m2 = (a + 1ll * (cnt[p] + b) * (cnt[p] + b)) % l;
    if (m1 > m2) swap(m1, m2); 
    m2++;
    update(m1, m2, x);
  }
  cout << *max_element(cnt+1, cnt+c+1) << endl;
  return 0;
}

 

 

[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;
}

2018牛客暑期ACM多校训练营(第一场)题解

A. Monotonic Matrix

给定\(1\leq m,n \leq 1000\),求满足下列条件的\(m \times n\)矩阵个数,使得

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

题解:考虑每一行大于等于1和大于等于2的位置,其实就是要求两个单调不减的数列\(\{a_i\}, \{b_i\}\)的个数,满足对于任意\(i\),有\(a_i \leq b_i\)。

B. Symmetric Matrix

给定\(1 \leq n \leq 10^5\),求满足每个元素为非负整数,主对角线全0,每一行和为2的\(n \times n\)的对称矩阵的数量。

题解:把矩阵想象成邻接矩阵,就是要求顶点带标号的所有不允许自环、但允许重边的2-正则图的数量。

C. Fluorescent 2

在模2域下,给定\(m \times n\)的01矩阵\(M\),\(1 \leq n \leq 50\),\(1 \leq m \leq 1000\),求对于每一个\(n\)维向量\(v\),\(Mv\)中0的个数的三次方的和。

D. Two Graphs

给定图\(G_1 = (V, E_1), G_2 = (V, E_2)\),求有多少\(E_1\)的子集\(E’\),使得\((V, E’)\)与\(G_2\)同构。点数不超过8。

题解:枚举所有的排列,如果构成子图,就把选出来的边用bitmap表示出来,最后去重即可。

E. Removal

给定\(1 \leq n \leq 10^5\)个数的序列,每个数为不超过\(k\)的正整数。问删掉\(m\)个数后,有多少种不同的子序列。\(k, m\)不超过10。

题解:用dp[i][j][k]表示前i个数删去j个数后,最后一个数为k的方案数。可以在\(O(1)\)时间内转移。

F. Sum of Maximum

给定数列\(a_1, a_2, \cdots, a_n\),求

\[\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\}\]

题解:把\(\max\{x_1, x_2, \cdots, x_n\}\)写为\(\sum_{m=1}^a [\exists i, x_i \geq m]\),进而改写为\(\sum_{m=1}^a 1-[\forall i, x_i < m]\)。将\(a_i\)排序后,从大到小分段计算,每一段都是\(x_i\)的一个前缀积乘以\(i^k\)的求和,后者可用Lagrange插值法快速计算。

G. Steiner Tree

H. Longest Path

I. Substring

给一个字符集为{a,b,c}的字符串,求在同构意义下的子串的等价类的数目。两个串同构当且仅当长度相等,并且存在字符集到字符集的双射f,使得一个串经过f变换后变成另一个串。

题解:将原串经过6种双射f后变成的6个串丢到SAM里,求出所有本质不同的子串。含有大于等于2种子串有6中不同的同构串,而只含有1种字符的串只有3中不同的同构串,分类讨论一下即可。

J. Different Integers

给一个序列,每次询问给出一个区间,求序列扣除这个区间后,有多少个不同数。

题解:在某次询问中,某数不出现当且仅当这个数第一次出现到最后一次出现包含于询问区间中即可。只要离线排序一下,按右端点的顺序处理即可。