The 12th Zhejiang Provincial Collegiate Programming Contest

上面的是现场过题的情况.

这个是同步赛过题的情况. 水题偏多, 基本上每题都有人过, 虽然现场F题没有人过. E题原本是作为压轴的智商题的, 过的人还是有不少的.

Problem A Ace of Aces

给出$n$个数, 找出出现次数最多的那个数.

数据规模: $1 \le n, a_i \le 1000$

应该没有人不会做.

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

int main() {
  int T; scanf("%d", &T);
  for (int _ = 0; _ < T; ++ _) {
    vector<int> cnt(1001, 0);
    int n; scanf("%d", &n);
    for (int i = 0; i < n; ++ i) {
      int x; scanf("%d", &x); cnt[x] ++;
    }
    int ret = max_element(cnt.begin(), cnt.end()) - cnt.begin();
    for (int i = 0; i <= 1000; ++ i) {
      if (cnt[i] == cnt[ret] && ret != i) {
        ret = -1; break;
      }
    }
    if (ret == -1) puts("Nobody");
    else printf("%d\n", ret);
  }
  return 0;
}

Problem B Team Formation

给出$n$个数$a_1,a_2,\dots,a_n$, 问有多少对$(i,j)$满足$a_i \oplus a_j > \max\{a_i,a_j\}$.

数据规模: $1 \le n \le 10^5, 1 \le a_i \le 10^9$

枚举第几位开始变大即可. 用trie树或者数组维护都可.

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int SZ = 4000000 + 10;
struct Node {
  Node *ch[2];
  int sz;
} pool[SZ], *rt, *null, *pt;

Node *newNode() {
  pt->ch[0] = pt->ch[1] = null;
  pt->sz = 0; return pt ++;
}
void ins(int x) {
  Node *p = rt; p->sz ++;
  for (int i = 31; i >= 0; -- i) {
    int o = (x >> i) & 1;
    if (p->ch[o] == null) p->ch[o] = newNode();
    p = p->ch[o]; p->sz ++;
  }
}
int cnt(int x) {
  Node *p = rt; int ret = 0;
  for (int i = 31; i >= 0; -- i) {
    int o = (x >> i) & 1;
    if (o == 0) ret += p->ch[1]->sz;
    p = p->ch[0];
  }
  return ret;
}

int A[SZ], N;

int main() {
  int T; scanf("%d", &T);
  for (int _ = 0; _ < T; ++ _) {
    pt = pool; null = newNode();
    null->ch[0] = null->ch[1] = null;
    rt = newNode();
    scanf("%d", &N); LL ret = 0;
    for (int i = 0; i < N; ++ i) scanf("%d", A + i);
    sort(A, A + N);
    for (int i = 0; i < N; ++ i) {
      ret += cnt(A[i]); ins(A[i]);
    }
    printf("%lld\n", ret);
  }
  return 0;
}

Problem C Convex Hull

给出$n$个点, 任意三点不共线. 求出所有可能凸包的面积和的两倍.

数据规模: $1 \le n \le 1000, |x_i|, |y_i| \le 10^9$

做过GCJ2015 Round 1A的应该都会做. 没做过的应该想想就可以搞出来.

回忆凸包面积的公式, 只需要考虑每条边对答案的贡献即可.

然后枚举一个端点, 另一个端点极角排序, 就可以很快统计出答案.

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXN = 2000, MOD = 998244353;

inline int sgn(LL x) {return x < 0 ? -1 : x > 0;}
inline LL sqr(LL x) {return x * x;}

struct Point {
  int x, y;
  Point() {}
  Point(int x, int y): x(x), y(y) {}
  Point operator + (const Point &rhs) const {
    return Point(x + rhs.x, y + rhs.y);
  }
  Point operator - (const Point &rhs) const {
    return Point(x - rhs.x, y - rhs.y);
  }
  LL dot(const Point &rhs) const {
    return (LL)x * rhs.x + (LL)y * rhs.y;
  }
  LL det(const Point &rhs) const {
    return (LL)x * rhs.y - (LL)y * rhs.x;
  }
  LL len2() const {
    return (LL)x * x + (LL)y * y;
  }
};


struct AngleCmp {
  bool operator() (const Point &A, const Point &B) {
    int sa(sgn(A.y)), sb(sgn(B.y));
    if (A.y == 0 && A.x < 0) return false;
    if (B.y == 0 && B.x < 0) return true;
    return sa != sb ? sa < sb : A.det(B) > 0;
  }
};

Point P[MAXN], Q[MAXN];
LL pw[MAXN];
int N, M;

int main() {
  pw[0] = 1;
  for (int i = 1; i < MAXN; ++ i) pw[i] = pw[i - 1] * 2 % MOD;
  int T; scanf("%d", &T);
  for (int _ = 0; _ < T; ++ _) {
    scanf("%d", &N);
    for (int i = 0; i < N; ++ i) {
      scanf("%d%d", &P[i].x, &P[i].y);
    }
    int ret = 0;
    for (int i = 0; i < N; ++ i) {
      for (int j = (M = 0); j < N; ++ j) if (i != j) {
        Q[M ++] = P[j] - P[i];
      }
      sort(Q, Q + M, AngleCmp());
      for (int j = 0, k = 0, cnt = 0; j < M; ++ j) {
        if (j == k) k = (k + 1) % M;
        for (; k != j && Q[j].det(Q[k]) > 0; k = (k + 1) % M) ++ cnt;
        ret = (ret + P[i].det(P[i] + Q[j]) % MOD * (pw[cnt] - 1)) % MOD;
        ret = (ret + MOD) % MOD; if (cnt) -- cnt;
      }
    }
    printf("%d\n", ret);
  }
  return 0;
}

Problem D Beauty of Array

给出$n$个数$a_1,a_2,\dots,a_n$, 对于所有连续子序列, 求出本质不同数的和.

数据规模: $1 \le n \le 10^5, 1 \le a_i \le 10^6$

考虑每个数字对答案的贡献.

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef vector<int> VI;
const int MAXN = 100000 + 10;
map<int, VI> mp;

int main() {
  int T; scanf("%d", &T);
  for (int _ = 0; _ < T; ++ _) {
    int n; scanf("%d", &n); mp.clear();
    for (int i = 1; i <= n; ++ i) {
      int v; scanf("%d", &v);
      mp[v].push_back(i);
    }
    LL ret = 0;
    for (auto &x : mp) {
      VI &v = x.second;
      int pv = 0;
      for (size_t i = 0; i < v.size(); ++ i) {
        ret += (LL)x.first * (n - v[i] + 1) * (v[i] - pv);
        pv = v[i];
      }
    }
    printf("%lld\n", ret);
  }
  return 0;
}

Problem E Floor Function

给定$a,b,c,d$, 满足$bc > ad$, 求使得$cn-d \lfloor \frac{a}{b}n\rfloor$最小的最小的$n$.

数据规模: $1 \le a, b, c, d \le 10^{18}$

令$y = \lfloor \frac{a}{b}x\rfloor, x = \lceil \frac{by}{a} \rceil$, 原问题等价于求$cx-dy$的最小值, $ax \ge by, x \ge 1, y \ge 0$.

分两种情况考虑

1. $a \ge b$

令$k = \lfloor \frac{a}{b}\rfloor, y \ge kx, c > ad / b \ge kd$

令$a^\prime=a-kb, c^\prime=c-kd,y^\prime=y-kx$, 此时原问题的约数条件任然满足, 问题可以缩小规模.

原问题的解$(x,y)$对应现在的解$(x,kx+y^\prime)$

显然若$a^\prime=0$, 我们可以得到$(x,y^\prime)=(1,0)$

2. $a < b$

令$k = \lfloor \frac{b-1}{a}\rfloor, x > ky$

令$b^\prime=b-ka, d^\prime=d-k*c, x^\prime=x-ky$

类似的, 原问题的约数条件任然满足, 问题可以缩小规模.

显然若$d^\prime \le 0$, 我们可以得到$(x^\prime,y)=(1,0)$

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

void solve(LL a, LL b, LL c, LL d, LL &x, LL &y) {
  if (a == 0 || d <= 0) {x = 1, y = 0; return;}
  if (a >= b) {
    LL k = a / b;
    solve(a - k * b, b, c - k * d, d, x, y);
    y += k * x;
  }
  else {
    LL k = (b - 1) / a;
    if (d / c < k) x = 1, y = 0;
    else solve(a, b - k * a, c, d - k * c, x, y);
    x += k * y;
  }
}

int main() {
  int T; scanf("%d", &T);
  for (int _ = 0; _ < T; ++ _) {
    LL a, b, c, d; scanf("%lld%lld%lld%lld", &a, &b, &c, &d);
    LL x, y; solve(a, b, c, d, x, y);
    printf("%lld\n", x);
  }
  return 0;
}

Problem F Permutation Graph

给一个算法：

输入：$1 \sim n$的排列$a_1, a_2,\dots, a_n$

中间处理：对每个逆序对$(a_i, a_j)$连一条无向边，$i < j, a_i > a_j$ ($a_i$和$a_j$连一条边).

输出：无向图的联通分量。

现在给出这个算法的输出，问有多少个输入对应这个输出。 即给出某个无向图的联通分量，问有多少排列满足上述算法。

数据规模: $1 \le n \le 10^5$

有个显然的结论, 每个联通分量里面数字的标号是连续的. 于是可以先判断下给定的联通块是否合法, 如果不合法输出0. 假设某个联通块的点标号在$l$和$r$之间, 那么这些点在排列中的位置貌似也只能在$l$和$r$之间(即只能填在$p_l,p_{l+1},\dots,p_r$上)

显然答案只和$r-l+1$的大小有关, 不妨令$n=r-l+1$, $f(n)$表示长度为$n$的答案. 

很容易得到公式: $f(n) = n! - \displaystyle\sum_{k=1}^{n-1}(n-k)!f(k)$

解释一下: 枚举1所在联通分量的大小为$k$, 根据标号连续这一点, 我们可以知道肯定是排列中前$k$个数, 后面$n-k$个数随便排列, 于是方案数为$f(k) \cdot (n - k)!$

直接递推是$n^2$的, 观察可以发现公式右边部分有一个卷积, 我们可以使用ntt优化(由于$786433=3 \times 2^{18}+1$, 原根是10).

有两种优化方法, 分块优化和cdq分治优化. 会的人应该就明白了, 不会的慢慢研究标程.

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXN = 400000 + 10, SZ = 100000 + 10;
const int P = 786433, g = 10;
LL f[MAXN], h[MAXN];
LL pm(LL a, LL n, LL m) {
  LL r=1;
  for (;n;n>>=1,a=a*a%m) if (n&1) r=r*a%m;
  return r;
}
void NTT(LL a[], int n, bool inv=false) {
  LL w=1,d=pm(g,(P-1)/n,P),t; int i,j,c,s;
  if (inv) {
    for (i=1,j=n-1;i<j;swap(a[i++],a[j--]));
    for (t=pm(n,P-2,P),i=0;i<n;++i) a[i]=a[i]*t%P;
  }
  for (s=n>>1;s;s>>=w=1,d=d*d%P) {
    for (c=0;c<s;++c,w=w*d%P) {
      for (i=c;i<n;i+=s<<1) {
        a[i|s]=(a[i]+P-(t=a[i|s]))*w%P;
        a[i]=(a[i]+t)%P;
      }
    }
  }
  for (i=1;i<n;++i) {
    for (j=0,s=i,c=n>>1;c;c>>=1,s>>=1) j=j<<1|s&1;
    if (i<j) swap(a[i],a[j]);
  }
}

void solve(int l, int r) {
  if (r - l == 1) {
    h[l] = (f[l] - h[l]) % P;
    h[l] = (h[l] + P) % P;
    return;
  }
  int m = (l + r) >> 1;
  solve(l, m);
  static LL A[MAXN], B[MAXN];
  int s = 1, n = m - l + 1;
  while (s < n * 2) s <<= 1;
  for (int i = 1; i < s; ++ i) A[i] = i < n ? h[i + l - 1] : 0;
  for (int i = 1; i < s; ++ i) B[i] = f[i]; A[0] = B[0] = 0;
  NTT(A, s); NTT(B, s);
  for (int i = 0; i < s; ++ i) A[i] = A[i] * B[i] % P;
  NTT(A, s, true);
  for (int i = m; i < r; ++ i) h[i] += A[i - l + 1];
  solve(m, r);
}

int main() {
  f[0] = 1;
  for (int i = 1; i < SZ; ++ i) f[i] = f[i - 1] * i % P;
  solve(1, SZ);
  int T; scanf("%d", &T);
  for (int _ = 0; _ < T; ++ _) {
    int n, m; scanf("%d%d", &n, &m);
    LL ret = 1;
    for (int i = 0; i < m; ++ i) {
      int c; scanf("%d", &c);
      int l = n, r = 0; ret = ret * h[c] % P;
      for (int j = 0; j < c; ++ j) {
        int x; scanf("%d", &x);
        l = min(l, x); r = max(r, x);
      }
      if (r - l + 1 != c) ret = 0;
    }
    printf("%lld\n", ret);
  }
  return 0;
}

Problem G Lunch Time

应该没有人不会这题..

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, string> PIS;
int main() {
  int T; cin >> T;
  for (int _ = 0; _ < T; ++ _) {
    int s, m, d; cin >> s >> m >> d;
    vector<PIS> S(s), M(m), D(d);
    for (int i = 0; i < s; ++ i) cin >> S[i].second >> S[i].first;
    for (int i = 0; i < m; ++ i) cin >> M[i].second >> M[i].first;
    for (int i = 0; i < d; ++ i) cin >> D[i].second >> D[i].first;
    sort(S.begin(), S.end());
    sort(M.begin(), M.end());
    sort(D.begin(), D.end());
    cout << S[s / 2].first + M[m / 2].first + D[d / 2].first << " ";
    cout << S[s / 2].second << " " << M[m / 2].second << " " << D[d / 2].second << endl;
  }
  return 0;
}

Problem H May Day Holiday

计算某年的5月1日是星期几.

应该没有人不会这题

#include <bits/stdc++.h>
using namespace std;
int toWeek(int y, int m, int d) {
  int tm = m >= 3 ? m - 2 : m + 10;
  int ty = m >= 3 ? y : y - 1;
  return (ty + ty / 4 - ty / 100 + ty / 400 + (int)(2.6 * tm - 0.2) + d) % 7;
}

int main() {
  int T; scanf("%d", &T);
  for (int _ = 0; _ < T; ++ _) {
    int y; scanf("%d", &y); 
    const int a[] = {6, 9, 6, 5, 5, 5, 5};
    printf("%d\n", a[toWeek(y, 5, 1)]);
  }
  return 0;
}

Problem I Earthstone Keeper

有一个$n \times m$的格子, 有障碍物, 有陷阱, 有怪物, 保证怪物不相邻. 人只要和怪物相邻就需要杀死怪物, 怪物死了之后就消失. 人走到陷阱上会触发陷阱, 陷阱不会消失. 杀死怪物以及触发陷阱都会掉一定量的血.

给出起点和终点, 在掉血量最小的前提下花最少的时间.

数据规模: $1 \le n, m \le 500$

由于怪物不相邻, 直接可以搞一个双关键字最短路. 注意伤害不要重复计算.

图建的不好的话spfa可能会超时, 建议使用dijkstra.

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500 + 10;
const int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};
typedef pair<int, int> PII;
typedef pair<PII, PII> Node;
struct Edge {
  int x, y, f, t, nx;
  Edge() {}
  Edge(int x, int y, int f, int t, int nx):
    x(x), y(y), f(f), t(t), nx(nx) {}
} E[MAXN * MAXN << 4];

char mp[MAXN][MAXN];
int G[MAXN][MAXN], sz;
int N, M, SR, SC, TR, TC;

PII operator + (const PII &a, const PII &b) {
  return PII(a.first + b.first, a.second + b.second);
}
bool fit(int x, int y) {
  return x >= 1 && x <= N && y >= 1 && y <= M && mp[x][y] != '#';
}
bool block(int x, int y) {
  return !fit(x, y) || isupper(mp[x][y]);
}
int trap(int x, int y) {
  return islower(mp[x][y]) ? mp[x][y] - 'a' + 1 : 0;
}
int monster(int x, int y) {
  return isupper(mp[x][y]) ? mp[x][y] - 'A' + 1 : 0;
}

int main() {
  int T; scanf("%d", &T);
  while (T --) {
    scanf("%d%d%d%d%d%d", &N, &M, &SR, &SC, &TR, &TC);
    for (int i = 1; i <= N; ++ i) scanf("%s", mp[i] + 1);
    memset(G, -1, sizeof(G)); sz = 0;
    for (int x = 1; x <= N; ++ x) {
      for (int y = 1; y <= M; ++ y) if (!block(x, y)) {
        for (int k = 0; k < 4; ++ k) {
          int x1 = x + dx[k], y1 = y + dy[k], ft = 0;
          if (block(x1, y1)) continue;
          for (int i = 0; i < 4; ++ i) {
            int x2 = x1 + dx[i], y2 = y1 + dy[i];
            if (fit(x2, y2)) ft += monster(x2, y2);
          }
          E[sz] = Edge(x1, y1, ft, 1, G[x][y]); G[x][y] = sz ++;
        }
      }
    }
    for (int x = 1; x <= N; ++ x) {
      for (int y = 1; y <= M; ++ y) if (monster(x, y)) {
        for (int i = 0; i < 4; ++ i) {
          int x1 = x + dx[i], y1 = y + dy[i];
          if (!fit(x1, y1)) continue;
          for (int j = 0; j < 4; ++ j) if (i != j) {
            int x2 = x + dx[j], y2 = y + dy[j], ft = 0;
            if (!fit(x2, y2)) continue;
            for (int k = 0; k < 4; ++ k) {
              int xx = x2 + dx[k], yy = y2 + dy[k];
              if (!fit(xx, yy) || abs(xx - x1) + abs(yy - y1) <= 1) continue;
              ft += monster(xx, yy);
            }
            E[sz] = Edge(x2, y2, ft, 2, G[x1][y1]); G[x1][y1] = sz ++;
          }
        }
      }
    }
    static PII dis[MAXN][MAXN];
    memset(dis, 0x7f, sizeof(dis));
    priority_queue<Node, vector<Node>, greater<Node> > Q;
    dis[SR][SC] = PII(0, 0); Q.push(Node(dis[SR][SC], PII(SR, SC)));
    while (!Q.empty()) {
      int x = Q.top().second.first, y = Q.top().second.second; Q.pop();
      if (x == TR && y == TC) break;
      for (int it = G[x][y]; ~it; it = E[it].nx) {
        int xx = E[it].x, yy = E[it].y;
        PII cost = PII(E[it].f + trap(xx, yy), E[it].t);
        if (dis[xx][yy] > dis[x][y] + cost) {
          dis[xx][yy] = dis[x][y] + cost;
          Q.push(Node(dis[xx][yy], PII(xx, yy)));
        }
      }
    }
    printf("%d %d\n", dis[TR][TC].first, dis[TR][TC].second);
  }
  return 0;
}

Problem J Convert QWERTY to Dvorak

给出两种键盘布局, 转化一下.

应该没有人不会这题.

#include <bits/stdc++.h>
using namespace std;
char *qw = "~!@#$%^&*()_+`1234567890-=\tQWERTYUIOP{}|qwertyuiop[]\\ASDFGHJKL:\"\nasdfghjkl;'ZXCVBNM<>?zxcvbnm,./ ";
char *dv = "~!@#$%^&*(){}`1234567890[]\t\"<>PYFGCRL?+|',.pyfgcrl/=\\AOEUIDHTNS_\naoeuidhtns-:QJKXBMWVZ;qjkxbmwvz ";

int main() {
  map<char, char> mp;
  for (char *p = qw, *q = dv; *p; ++ p, ++ q) mp[*p] = *q;
  for (char c; c = getchar(), c != EOF;) putchar(mp[c]);
  return 0;
}

Problem K Capture the Flag

规则复杂, 不好描述.

看懂题目直接模拟.

#include <bits/stdc++.h>
using namespace std;
typedef double flt;
const int MAXN = 100 + 10, MAXQ = 20;
const flt eps = 1e-8;
bool ck[MAXQ][MAXN][MAXN];
int mt[MAXQ][MAXN], rk[MAXN];
flt score[MAXN];
int N, Q, S, C;

int main() {
  int T; cin >> T; //scanf("%d", &T);
  for (int _ = 0; _ < T; ++ _) {
    cin >> N >> Q >> S >> C; //scanf("%d%d%d%d", &N, &Q, &S, &C);
    for (int i = 1; i <= N; ++ i) score[i] = S;
    for (int c = 0; c < C; ++ c) {
      memset(ck, 0, sizeof(ck));
      int A; cin >> A; //scanf("%d", &A);
      for (int i = 0; i < A; ++ i) {
        int ak, df, sr; cin >> ak >> df >> sr; //scanf("%d%d%d", &ak, &df, &sr);
        ck[sr][df][ak] = true;
      }
      for (int i = 1; i <= Q; ++ i) {
        for (int j = 1; j <= N; ++ j) {
          cin >> mt[i][j]; //scanf("%d", &mt[i][j]);
        }
      }
      for (int sr = 1; sr <= Q; ++ sr) {
        int mt = 0;
        for (int i = 1; i <= N; ++ i) {
          int ak = 0; mt += ::mt[sr][i];
          for (int j = 1; j <= N; ++ j) ak += ck[sr][i][j];
          if (!ak) continue; score[i] -= N - 1;
          for (int j = 1; j <= N; ++ j) score[j] += ck[sr][i][j] * flt(N - 1) / ak;
        }
        for (int i = 1; i <= N; ++ i) {
          if (!::mt[sr][i]) score[i] -= N - 1;
          else score[i] += flt(N - 1) * (N - mt) / mt;
        }
      }
      for (int i = 1; i <= N; ++ i) {
        rk[i] = 1;
        for (int j = 1; j <= N; ++ j) if (i != j) {
          if (score[j] > score[i] + eps) ++ rk[i];
        }
      }
      int U; cin >> U; //scanf("%d", &U);
      for (int i = 0; i < U; ++ i) {
        int x; cin >> x; //scanf("%d", &x);
        printf("%.10f %d\n", score[x], rk[x]);
      }
    }
  }
  return 0;
}

Problem L Demacia of the Ancients

应该没有人不会这题.

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

int main() {
  int T; cin >> T;
  for (int _ = 0; _ < T; ++ _) {
    int n; scanf("%d", &n);
    for (int i = n; i >= 1; -- i) {
      int x; scanf("%d", &x); n -= x <= 6000;
    }
    printf("%d\n", n);
  }
  return 0;
}

• Relative Posts