本文共 17089 字，大约阅读时间需要 56 分钟。

前言

第二场都快打了才补完题目发博客，最近事情真的太多了= =

A - Intelligent Warehouse（DP+数论优化），三种做法

题目大意

给出$n$个数，从中选择最多的数使得选出的集合任何两个数都是倍数关系。

解题思路

任何两个数都是倍数关系也就是说，从第一个数开始，后面的数都是前一个数的倍数即可。显然相同的数贡献就是其数量。那么就是一个简单的$DP$。

做法一：枚举倍数

这题真的无语，一开始就想到了离散化数组然后从小到大（或者从大到小）枚举每个数的倍数，赛时TLE到见鬼，赛后一发过。

//// Created by Happig on 2020/10/25//#include 
   
    #include 
    
     #include 
     
      using namespace std;#define fi first#define se second#define pb push_back#define ins insert#define Vector Point#define ENDL "\n"#define lowbit(x) (x&(-x))#define mkp(x, y) make_pair(x,y)#define mem(a, x) memset(a,x,sizeof a);typedef long long ll;typedef long double ld;typedef unsigned long long ull;typedef pair
      
        pii;typedef pair
       
         pll;typedef pair
        
          pdd;const double eps = 1e-8;const double pi = acos(-1.0);const int inf = 0x3f3f3f3f;const double dinf = 1e300;const ll INF = 1e18;const int Mod = 1e9 + 7;const int maxn = 1e7 + 10;const int maxm = 2e5 + 10;int a[maxm], num[maxn];int d[maxn];int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); //ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); int n; scanf("%d", &n);// clock_t beg = clock(); int Max = 0; for (int i = 0; i < n; i++) { scanf("%d", &a[i]); //a[i] = i + 1; num[a[i]]++; Max = max(Max, a[i]); } sort(a, a + n); int m = unique(a, a + n) - a; for (int i = m - 1; i >= 0; i--) { d[a[i]] = num[a[i]]; int res = 0; for (int j = 2 * a[i]; j <= Max; j += a[i]) { if (num[j]) res = max(res, d[j]); } d[a[i]] += res; //cout << d[a[i]] << endl; } int ans = 0; for (int i = 0; i < m; i++) { ans = max(ans, d[a[i]]); } printf("%d\n", ans);// clock_t ed = clock();// cout << ed - beg << endl; return 0;}
        
       
      
     
    
   

做法二：枚举范围内所有数的素数倍

据说这是题解给出的做法，因为所有数的范围只有$1e7$，那么我们枚举所有的数，只向其素数倍转移即可，时间复杂度我不会证明，据说是$O(w\log \log w)$。

//// Created by Happig on 2020/10/25//#include 
   
    #include 
    
     #include 
     
      using namespace std;#define fi first#define se second#define pb push_back#define ins insert#define Vector Point#define ENDL "\n"#define lowbit(x) (x&(-x))#define mkp(x, y) make_pair(x,y)#define mem(a, x) memset(a,x,sizeof a);typedef long long ll;typedef long double ld;typedef unsigned long long ull;typedef pair
      
        pii;typedef pair
       
         pll;typedef pair
        
          pdd;const double eps = 1e-8;const double pi = acos(-1.0);const int inf = 0x3f3f3f3f;const double dinf = 1e300;const ll INF = 1e18;const int Mod = 1e9 + 7;const int maxn = 1e7 + 10;const int maxm = 2e5 + 10;int prime[maxn / 2];bitset
         
           vis;int cnt;void euler() { cnt = 0; vis.reset(); for (int i = 2; i < maxn; i++) { if (!vis[i]) prime[++cnt] = i; for (int j = 1; j <= cnt && 1LL * i * prime[j] < maxn; j++) { vis[i * prime[j]] = 1; if (i % prime[j] == 0) break; } }}int d[maxn], num[maxn];int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); //ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0); euler(); int n, Max = 0; scanf("%d", &n); for (int i = 0, x; i < n; i++) { scanf("%d", &x); ++num[x], Max = max(Max, x); } int ans = 0, N = 1e7; for (int i = 1; i <= N; i++) { d[i] += num[i]; for (int j = 1; j <= cnt && 1LL * prime[j] * i <= Max; j++) { int k = prime[j] * i; d[k] = max(d[k], d[i]); } ans = max(ans, d[i]); } printf("%d\n", ans); return 0;}
         
        
       
      
     
    
   

做法三：质因数分解

这是赛时想到的毒瘤做法，只是比较耗空间，在$Pollard-Rho$质因数分解那里提到的时间复杂度只有$O(n^{0.25})$，而且递归搜索所有因数也是常数时间复杂度，因此我们考虑质因数分解，我本地测试，分解$2e5$个$1e7$范围的数，耗时$380ms$，实际上证明了这种因数分解的做法是跑的飞快的。那么在做法一中，我们改为枚举所有数的因数倍，这样成功卡过赛时的辣鸡评测机。

//// Created by Happig on 2020/10/25//#include 
   
    #include 
    
     #include 
     
      using namespace std;#define fi first#define se second#define pb push_back#define ins insert#define Vector Point#define ENDL "\n"#define lowbit(x) (x&(-x))#define mkp(x, y) make_pair(x,y)#define mem(a, x) memset(a,x,sizeof a);typedef long long ll;typedef long double ld;typedef unsigned long long ull;typedef pair
      
        pii;typedef pair
       
         pll;typedef pair
        
          pdd;const double eps = 1e-8;const double pi = acos(-1.0);const int inf = 0x3f3f3f3f;const double dinf = 1e300;const ll INF = 1e18;const int Mod = 1e9 + 7;const int maxn = 1e7 + 10;const int maxm = 2e5 + 10;int prime[maxn / 2], p[maxn], num[1005], pfac[1005];int cnt1, cnt2, tot;void euler() { cnt1 = 0; for (int i = 1; i < maxn; i++) p[i] = i; for (int i = 2; i < maxn; i++) { if (p[i] == i) prime[++cnt1] = i; for (int j = 1; j <= cnt1 && 1LL * i * prime[j] < maxn; j++) { p[i * prime[j]] = prime[j]; if (i % prime[j] == 0) break; } }}void divide(int n) { cnt2 = 0; while (n != 1) { pfac[++cnt2] = p[n]; n /= p[n]; } sort(pfac + 1, pfac + 1 + cnt2); tot = 1, num[tot] = 1; for (int i = 2; i <= cnt2; i++) { if (pfac[i] == pfac[i - 1]) { num[tot]++; } else { num[++tot] = 1; pfac[tot] = pfac[i]; } }}vector
         
           fac[maxm];int pos;void dfs(int d, ll cur = 1) { if (d == tot + 1) { fac[pos].push_back(cur); return; } for (int i = 0; i <= num[d]; i++) { dfs(d + 1, cur); cur *= pfac[d]; }}int a[maxm], vis[maxn], d[maxn];int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); //ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);// clock_t beg = clock(); euler(); int n; scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d", &a[i]); vis[a[i]]++; } sort(a, a + n); int m = unique(a, a + n) - a; for (int i = 0; i < m; i++) { divide(a[i]); pos = i; dfs(1, 1); } int ans = 0; for (int i = 0; i < m; i++) { d[a[i]] = vis[a[i]]; int res = 0; for (auto j:fac[i]) { if (vis[j] && j != a[i]) res = max(res, d[j]); } d[a[i]] += res; //cout << a[i] << " " << d[a[i]] << endl; ans = max(ans, d[a[i]]); } printf("%d\n", ans); return 0;}
         
        
       
      
     
    
   

B - Intelligent Robot（计算几何+最短路）

题目大意

在表格中给出起点和终点，但是在路径上可能分布着很多墙，墙用线段表示，墙不能穿过但是可以紧贴，问从起点到终点的最短路径的长度是多少。

解题思路

这题一看就特别眼熟，原来在kuangbin的计算几何基础专题中有道非常相似的$POJ1556$，当时做那道题收获就很大所以还记得做法。这个做法的前提是证明当墙挡住路的时候，无论如何从墙的端点处绕路总是最优的。那么我们将所有点存起来，所有线段存起来，枚举任意两点和所有线段判断是否相交，如果相交两点距离设为$inf$，这样就能建一张图，最后对图跑最短路算法即可，因为点数很少，直接上$Floyd$是最快的。

//// Created by Happig on 2020/10/25//#include 
   
    #include 
    
     #include 
     
      using namespace std;#define fi first#define se second#define pb push_back#define ins insert#define Vector Point#define Seg Line#define ENDL "\n"#define lowbit(x) (x&(-x))#define mkp(x, y) make_pair(x,y)#define mem(a, x) memset(a,x,sizeof a);typedef long long ll;typedef long double ld;typedef unsigned long long ull;typedef pair
      
        pii;typedef pair
       
         pll;typedef pair
        
          pdd;const double eps = 1e-8;const double pi = acos(-1.0);const int inf = 0x3f3f3f3f;const double dinf = 1e300;const ll INF = 1e18;const int Mod = 1e9 + 7;const int maxn = 1e7 + 10;const int maxm = 2e5 + 10;int dcmp(double d) { if (fabs(d) < eps) return 0; if (d < 0) return -1; return 1;}struct Point { double x, y; Point(double a = 0, double b = 0) { x = a, y = b; } Point operator+(Point p) { return Point(x + p.x, y + p.y); } Point operator-(Point p) { return Point(x - p.x, y - p.y); } Point operator*(double d) { return Point(x * d, y * d); } double operator*(Point p) { return x * p.x + y * p.y; } Point operator/(double d) { return Point(x / d, y / d); } double operator^(Point p) { return x * p.y - y * p.x; } bool operator==(const Point &p) const { return x == p.x && y == p.y; } void print() { printf("(%.2lf,%.2lf)\n", x, y); }};struct Line { Point p, q; Vector v; Line() { } Line(Point a, Point b) { p = a, q = b, v = b - a; } Point point(double t) { return p + v * t; }};double dis(Point a, Point b) { return sqrt((b - a) * (b - a));}bool isSegInter(Seg a, Seg b) { double c1 = a.v ^b.p - a.p, c2 = a.v ^b.q - a.p; double c3 = b.v ^a.p - b.p, c4 = b.v ^a.q - b.p; return (dcmp(c1) * dcmp(c2) < 0 && dcmp(c3) * dcmp(c4) < 0);}bool vis[610][610]; //判断两点之间是否能直接相连double G[615][615]; //存两点间的距离，初始根据vis数组初始化为两点间距离Point P[1005]; //保存所有点Line walls[305];int Path[610][610];void Print(int u, int v) { if (u == v) { printf("%d\n", v); return; } printf("%d ", u); Print(Path[u][v], v);}int main() { double a, b, c, d; int n, m, K; scanf("%d%d%d", &n, &m, &K); for (int i = 1; i <= K; i++) { scanf("%lf%lf%lf%lf", &a, &b, &c, &d); P[i] = Point(a, b), P[K + i] = Point(c, d); walls[i] = Line(P[i], P[K + i]); } scanf("%lf%lf%lf%lf", &a, &b, &c, &d); P[0] = Point(a, b), P[2 * K + 1] = Point(c, d); //起点终点 memset(vis, 0, sizeof(vis)); for (int i = 0; i <= 2 * K + 1; i++) { for (int j = 0; j <= 2 * K + 1; j++) { int flag = 1; if (i == j) { G[i][j] = 0; continue; } //这里初始化到本身距离为0 for (int h = 1; h <= K; h++) { if (isSegInter(Line(P[i], P[j]), walls[h])) { flag = 0; break; } } if (flag) vis[i][j] = 1; } } //对于能相连的点调用距离公式，否则为INF for (int i = 0; i <= 2 * K + 1; i++) { for (int j = 0; j <= 2 * K + 1; j++) { Path[i][j] = j; if (vis[i][j]) G[i][j] = dis(P[i], P[j]); else G[i][j] = INF;// printf("%.1lf ", G[i][j]);// printf("%d", vis[i][j]); }// printf("\n"); } for (int k = 0; k <= 2 * K + 1; k++) { for (int i = 0; i <= 2 * K + 1; i++) { for (int j = 0; j <= 2 * K + 1; j++) { if (G[i][k] + G[k][j] < G[i][j]) { G[i][j] = G[i][k] + G[k][j]; Path[i][j] = Path[i][k]; } } } } printf("%.4lf\n", G[0][2 * K + 1]);// Print(0, 2 * K + 1); return 0;}
        
       
      
     
    
   

C - Smart Browser（签到）

代码就不放了，毕竟有手就行（逃

D - Router Mesh（Tarjan）

图论队友赛时当场学习，结果WA了无数发过不了。补上代码：

//// Created by Visors on 2020/10/25.//// 题目名：TODO// 题目来源：TODO// 题目链接：TODO// 算法：D.cpp// 用途：TODO// 时间复杂度：O(TODO)//#include 
   
    using namespace std;int block = 0;struct Tarjan {       struct Edge {           int to, next;        Edge() = default;        Edge(int to, int next) : to(to), next(next) {   }    };    int vertexNum{   }, edgeNum{   };    int cnt{   };              // 当前时间戳    int root{   };             // 保存当前搜索树根    vector
    
      edges;    vector
     
       heads;    vector
      
        dfn;        // 时间戳    vector
       
         low;        // 最早追溯时间    vector
        
          isCut; // 割点 vector
         
           branches; // 分支数// set
          
            cuts; // 割点编号集 void init(int n, int m) { cnt = 0; vertexNum = n; edgeNum = m; heads.resize(vertexNum); fill(heads.begin(), heads.end(), -1); dfn.resize(vertexNum); low.resize(vertexNum); isCut.resize(vertexNum); branches.resize(vertexNum); } void addEdge(int u, int v) { edges.emplace_back(v, heads[u]); heads[u] = edges.size() - 1; } void dfs(int u) { dfn[u] = low[u] = ++cnt; int tot = 0; for (int i = heads[u]; ~i; i = edges[i].next) { int &v = edges[i].to; if (!dfn[v]) { // branches[u]++; dfs(v); low[u] = min(low[u], low[v]); if (low[v] >= dfn[u]) { tot++; if (u != root || tot > 1) isCut[u] = true; // 对树根特判 } } else low[u] = min(low[u], dfn[v]); } if (u != root) tot++; branches[u] = tot; } void run() { for (int i = 0; i < vertexNum; i++) if (!dfn[i]) { root = i; block++; dfs(i); } }} tarjan;int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr); int n, m; cin >> n >> m; tarjan.init(n, m); for (int i = 1, u, v; i <= m; i++) { cin >> u >> v; u--, v--; tarjan.addEdge(u, v); tarjan.addEdge(v, u); } tarjan.run(); bool first = true; for (int i = 0; i < n; i++) { // cout << endl << tarjan.branches[i] << endl; if (first) { cout << block + tarjan.branches[i] - 1; first = false; } else cout << ' ' << block + tarjan.branches[i] - 1; } cout << endl; return 0;}
          
         
        
       
      
     
    
   

F- Design Problemset（二分答案）

这题队友补的，我就没看了，只放下代码

#include
   
    using namespace std;typedef long long ll;const int maxn=1e5+5;ll a[maxn],l[maxn],r[maxn];ll k,L,R;bool check(double mid){       //cout<<"mid "<
    
     <
     
      a[i])            return 0;        ll num=a[i]/mid;//讲第i种问题分成mid组，每组的数量是多少        num=min(r[i],num);//第i种问题最多可以取的数量,        //如果该种问题取的是r【i】，即使还有平分后剩余也不能再用        if(num!=r[i])            res+=a[i]-num*mid;        tot+=num;    }    tot+=res/mid;    if(tot>=L)        return true;    return false;}int main(){           cin>>k>>L>>R;    for(int i=1;i<=k;i++)           cin>>a[i];    for(int i=1;i<=k;i++)        cin>>l[i]>>r[i];    ll cntl=0,cntr=0;    for(int i=1;i<=k;i++)        cntl+=l[i],cntr+=r[i];    if(cntl>R || cntr
      
       0)    {           ll mid=(rt+lt+1)>>1;        if(check(mid))             lt=mid;        else rt=mid-1;    }    cout<
       
        <<'\n';    return 0;}
       
      
     
    
   

I - Walking Machine（搜索）

这题应该也是签到，队友写的

//// Created by Visors on 2020/10/25.//// 题目名：TODO// 题目来源：TODO// 题目链接：TODO// 算法：I.cpp// 用途：TODO// 时间复杂度：O(TODO)//#include 
   
    using namespace std;typedef pair
    
      pii;const int N = 1005, M = 1005;char G[N][M];bool book[N][M];int n, m;int ans = 0;queue
     
       q;int dir[4][2] = {   {   0, 1},                 {   0, -1},                 {   1, 0},                 {   -1, 0}};char check[4] = {   'A', 'D', 'W', 'S'};int main() {       ios_base::sync_with_stdio(false);    cin.tie(nullptr), cout.tie(nullptr);    cin >> n >> m;    for (int i = 1; i <= n; i++)        for (int j = 1; j <= m; j++) {               cin >> G[i][j];            if (i == 1 || i == n || j == 1 || j == m) {                   if (i == 1) {                       if (j == 1 && (G[i][j] == 'A' || G[i][j] == 'W')) {                           q.emplace(i, j);                        book[i][j] = true;                        continue;                    }                    if (j == m && (G[i][j] == 'D' || G[i][j] == 'W')) {                           q.emplace(i, j);                        book[i][j] = true;                        continue;                    }                    if (G[i][j] == 'W') {                           q.emplace(i, j);                        book[i][j] = true;                    }                    continue;                }                if (i == n) {                       if (j == 1 && (G[i][j] == 'A' || G[i][j] == 'S')) {                           q.emplace(i, j);                        book[i][j] = true;                        continue;                    }                    if (j == m && (G[i][j] == 'D' || G[i][j] == 'S')) {                           q.emplace(i, j);                        book[i][j] = true;                        continue;                    }                    if (G[i][j] == 'S') {                           q.emplace(i, j);                        book[i][j] = true;                    }                    continue;                }                if (j == 1 && G[i][j] == 'A') {                       q.emplace(i, j);                    book[i][j] = true;                    continue;                }                if (j == m && G[i][j] == 'D') {                       q.emplace(i, j);                    book[i][j] = true;                }            }        }    pii tmp;    while (!q.empty()) {           tmp = q.front();        ans++;        int &x = tmp.first,                &y = tmp.second;        q.pop();        for (int i = 0, nx, ny; i < 4; i++) {               nx = x + dir[i][0];            ny = y + dir[i][1];            if (x > 0 && x <= n && y > 0 && y <= m && G[nx][ny] == check[i] && !book[nx][ny]) {                   q.emplace(nx, ny);                book[nx][ny] = true;            }        }    }    cout << ans << endl;    return 0;}
     
    
   

J - Matrix Subtraction（二维差分）

题目大意

给出一个矩阵，现在还有一个大小一定且可以在大矩阵内随意移动的子矩阵，每次可以对子矩阵内的所有数都减一，问大矩阵最后能否都减为$0$。

解题思路

不难想到如果最终都能减为$0$，无论从哪个位置出发开始减都是可以的，那么我们考虑从右上角出发，每次减去最小的元素，如果存在某个元素被减后小于$0$显然无法完成。这个过程明显是二维差分，时间复杂度$O(nm)$。

//// Created by Happig on 2020/10/27//#include 
   
    #include 
    
     #include 
     
      using namespace std;#define fi first#define se second#define pb push_back#define ins insert#define Vector Point#define ENDL "\n"#define lowbit(x) (x&(-x))#define mkp(x, y) make_pair(x,y)#define mem(a, x) memset(a,x,sizeof a);typedef long long ll;typedef long double ld;typedef unsigned long long ull;typedef pair
      
        pii;typedef pair
       
         pll;typedef pair
        
          pdd;const double eps = 1e-8;const double pi = acos(-1.0);const int inf = 0x3f3f3f3f;const double dinf = 1e300;const ll INF = 1e18;const int Mod = 1e9 + 7;const int maxn = 2e5 + 10;int p[1005][1005], d[1005][1005];int T, n, m, a, b;void add(int i, int j, int x, int y, int val) { d[i][j] += val, d[x + 1][y + 1] += val; d[x + 1][j] -= val, d[i][y + 1] -= val;}void print() { for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { cout << d[i][j] << " "; } cout << endl; }}int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); cin >> T; while (T--) { cin >> n >> m >> a >> b; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { cin >> p[i][j]; d[i][j] = p[i][j] - p[i - 1][j] - p[i][j - 1] + p[i - 1][j - 1]; } } for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { d[i][j] = d[i][j] + d[i - 1][j] + d[i][j - 1] - d[i - 1][j - 1]; if (d[i][j] < 0) { goto fail; } else if (d[i][j] > 0) { if (i + a - 1 > n || j + b - 1 > m) goto fail; else add(i, j, i + a - 1, j + b - 1, -d[i][j]); } } } cout << "^_^" << ENDL; continue; fail: cout << "QAQ" << ENDL; } return 0;}