[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

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

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

2017-2018 问题求解(四)上机考试题解

Day1

A 差异度

题意:给\(n (1 \leq n \leq 10^5)\)个20位的01串,求两两之间hamming距离的最小值。

解法:此题解法甚多。下面列举3个常见的解法:

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

B 工作安排

题意:某人有\(T (0 \leq T \leq 100)\)时间,\(N (0 \leq N \leq 100)\)组工作。每组工作有3种类型:至多选一个做,至少选一个做,无限制。每组工作中最多有100个工作,每个工作有完成的时间和所能得到的收益值。求所能获得的最大收益。

题解:较为复杂的背包问题。用常规的dp就可以解决。对于每组工作的附加限制,在更新dp值的时候需要特殊处理。

Day2

A 矩阵分割游戏

题面:NOI1999 棋盘分割

题意:给一个8*8的矩阵,每次可以横着或竖着掰成两半并舍弃一块,最后得到\(n\)块子矩阵。求子矩阵数字和的标准差的最小值。

题解:由gay率论相关知识,要使标准差取得最小值,只要让平方和最小即可(因为和是固定的)。然后dp或者记忆化爆搜即可。

B 旅行箱

题意:有\(n \leq 42\)个数,取出它的一个子集,使得子集和在不超过\(W\)的前提下,使得子集和最大。(简单背包问题)

题解:用meet-in-the-middle思想。将集合分成两部分,预处理出每部分的所有子集和。然后将这些子集和排序,对于一部分的某个子集和\(S\),在另一部分中找出不超过\(W-S\)的最大子集和,然后取最大值即可。复杂度\(O(n2^{n/2})\)。

2018 ACM-ICPC China Jiangsu Provincial Programming Contest

A. 签到题

B. 滚动数组DP

C. ???

D. \( \frac{(\sum_{i=1}^n U[i])!}{\prod_{i=1}^n U[i]!} \)

E. Catalan数?

F. 预处理dfs序,按照F的值的顺序更新树状数组求方案数

G. 每M个数分为一组,组内求出所有前缀积和后缀积。每个window就可以拆成一个前缀积和一个后缀积的乘积。

H. Berlekamp-Massey模板题

I. 将矩阵乘法的定义中,乘法改为加法,加法改为max,然后求个矩乘快速幂

J. 高精度

K. 求出最短路图中除起点外所有点的入度之积

2018江苏省大学生程序设计竞赛(JSCPC)总结

题面:JSCPC2018 (1)

因为能拿到官方题解,我自己就不在写题解了(逃…

官方题解:analysis(1)

终榜:

开场后,扫了一眼发现A是水题加原题,然后我直接上去写,WA。重新读题,发现看错题意了,重写过了(14′)。这时,上机队列已经满了。Calabash_boy告诉我F题是个排序题,我上去写了个带比较器的sort,WA。仔细一查是爆ull了,换了一种写法过了(28′)。Roundgod把K题改对(30′)后,Calabash_boy又告诉我G题是个水题,我上去乱写一通交上去过了(35′),并且拿到了一血。这时队列已经空了,并且由于开场过题太猛,升到了榜首,无法跟榜,不知道开哪题。卡了近半小时后,Roundgod写了个B的二分,1A(62′)。随后开始长时间掉线,Roundgod开了D题发现推不出公式,又说J题是神仙题。我发现I题可能可做,就开始想I。看榜发现有队过C,Calabash_boy想了个两个log的做法,感觉有点虚。由于机时空出来了,Calabash_boy就开始敲二分主席树(我:这是啥?(懵逼脸))。刷榜发现J题有过,再一看J并不是神仙题,直接preemptive multitasking双开JC。J写完后发现WA,然后切C在写。J题改了又交,时间片切了快10次,还是不过,已经6发罚时了,心态有点崩。我查了一下代码,发现有个地方ans没取模,加上去后J题就过了(172′)。随后,C题也写出来了,交上去也过(186′)(葫芦爷真是太强辣)。又开始卡题了,发现I已经有人过了,我就接着想I。I题想了个算法,感觉有点难实现,然后抱着反正没人要机时,不用白不用的想法上去敲。敲了一个多小时,发现答案总是不对,一查发现之前想的算法全是假的。这时已经封榜了。Calabash_boy说E可以尝试一下,然后4:52写出来了,交上去T了。怀疑被卡常数,加了点剪枝还是T。发现剪枝是假的,我就帮着玄学卡常,但到比赛结束都没有做出来。最终7题Rank7(去掉打星队Rank6),特等奖。

总的来说,前期切水题比较快,积累了一些罚时优势,但由于中档题还不是很熟练,并没有什么卵用,最后还是掉下去了。以后还是要加强中档题和中等偏上难度题的训练。