2013-2014 ACM-ICPC Brazil Subregional Programming Contest 题解

这场比赛题面英文都好长... ...

模拟。

#include <bits/stdc++.h>

using namespace std;

int main() {

  int a,b,c;

  cin>>a>>b>>c;

  if(a != b && a!=c) {

    cout <<"A";

    return 0;

  }

  if(b != a && b!=c) {

    cout <<"B";

    return 0;

  }

  if(a != c && b!=c) {

    cout <<"C";

    return 0;

  }

  cout <<"*";

  return 0;

}

B - Balloon

找到每一条线段上面那条是什么，然后用并查集就可以求出来每个点最终会到哪里。

寻找每条线段上面那条，可以按照$y$进行排序，然后线段树区间覆盖进行操作。

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5 + 10;

int n, Q;

struct X {

  int x1, y1;

  int x2, y2;

}s[maxn];

int nx[maxn];

int f[maxn];

int root[maxn];

int Find(int x) {

  if(x != f[x]) f[x] = Find(f[x]);

  return f[x];

}

bool cmp(const X& a, const X& b) {

  if(a.y2 != b.y2) return a.y2 > b.y2;

  return a.y1 > b.y1;

}

int t[maxn * 40];

void pushDown(int rt) {

  if(t[rt] == 0) return;

  t[2 * rt] = t[rt];

  t[2 * rt + 1] = t[rt];

  t[rt] = 0;

}

void build(int l, int r, int rt) {

  t[rt] = -1;

  if(l == r) return;

  int mid = (l + r) / 2;

  build(l, mid, 2 * rt);

  build(mid + 1, r, 2 * rt + 1);

}

void update(int L, int R, int val, int l, int r, int rt) {

  if(L <= l && r <= R) {

    t[rt] = val;

    return;

  }

  pushDown(rt);

  int mid = (l + r) / 2;

  if(L <= mid) update(L, R, val, l, mid, 2 * rt);

  if(R > mid) update(L, R, val, mid + 1, r, 2 * rt + 1);

}

int get(int pos, int l, int r, int rt) {

  if(l == r) {

    return t[rt];

  }

  pushDown(rt);

  int mid = (l + r) / 2;

  if(pos <= mid) return get(pos, l, mid, 2 * rt);

  else return get(pos, mid + 1, r, 2 * rt + 1);

}

int main() {

  scanf("%d%d", &n, &Q);

  for(int i = 1; i <= n; i ++) {

    f[i] = i;

    root[i] = 0;

    scanf("%d%d", &s[i].x1, &s[i].y1);

    scanf("%d%d", &s[i].x2, &s[i].y2);

    if(s[i].y1 > s[i].y2) {

      swap(s[i].x1, s[i].x2);

      swap(s[i].y1, s[i].y2);

    }

  }

  sort(s + 1, s + 1 + n, cmp);

  for(int i = 1; i <= n; i ++) {

  //  printf("%d %d %d %d\n", s[i].x1, s[i].y1, s[i].x2, s[i].y2);

  }

  build(0, 1e6 + 10, 1);

  for(int i = 1; i <= n; i ++) {

    if(s[i].y1 == s[i].y2) {

      nx[i] = i;

    } else {

      nx[i] = get(s[i].x2, 0, 1e6 + 10, 1);

    }

    update(min(s[i].x1, s[i].x2), max(s[i].x1, s[i].x2), i, 0, 1e6 + 10, 1);

  }

  for(int i = 1; i <= n; i ++) {

    if(nx[i] == -1 || nx[nx[i]] == nx[i]) {

      root[i] = 1;

    }

  }

  for(int i = 1; i <= n; i ++) {

    if(root[i]) continue;

    f[i] = nx[i];

    Find(i);

    nx[i] = f[i];

  }

  for(int i = 1; i <= n; i ++) {

 //   printf("%d : %d\n", i, nx[i]);

  }

  while(Q --) {

    int x;

    scanf("%d", &x);

    int id = get(x, 0, 1e6 + 10, 1);

    if(id == -1) {

      printf("%d\n", x);

      continue;

    }

    if(nx[id] == id) {

      printf("%d %d\n", x, s[id].y1);

      continue;

    }

    int now = id, pre = -1;

  //  printf("!!! %d\n", now);

    while(1) {

      pre = now;

      now = nx[now];

      if(now == nx[now] || now == -1) break;

    }

    if(now == -1) {

      printf("%d\n", s[pre].x2);

    } else {

      printf("%d %d\n", s[pre].x2, s[now].y2);

    }

  }

  return 0;

}

/*

 4 4

 0 1 3 3

 1 5 6 5

 5 3 2 4

 7 4 10 2

 2

 5

 8

 6

 4 3

 1 3 4 2

 10 3 7 4

 2 3 8 3

 3 5 5 4

 4

 9

 8

 */

C - Boss

模拟，数据范围很少，平方的效率就可以了。

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1000;

int n, m, q;

vector<int> g[maxn];

int belong[maxn];

int fac[maxn];

int age[maxn];

int ans;

int f[maxn];

void dfs(int x, int y) {

  if(f[x]) return;

 // printf("debug %d\n", fac[x]);

  f[x] = 1;

  if(x != y) ans = min(ans, age[fac[x]]);

  for(int i = 0; i < g[x].size(); i ++) {

    dfs(g[x][i], y);

  }

}

int main() {

  scanf("%d%d%d", &n, &m, &q);

  for(int i = 1; i <= n; i ++) {

    belong[i] = i;

    fac[i] = i;

    scanf("%d", &age[i]);

  }

  while(m --) {

    int u, v;

    scanf("%d%d", &u, &v);

    g[v].push_back(u);

  }

  while(q --) {

    char op[10];

    scanf("%s", op);

    if(op[0] == 'T') {

      int x, y;

      scanf("%d%d", &x, &y);

      swap(belong[x], belong[y]);

      for(int i = 1; i <= n; i ++) {

        fac[belong[i]] = i;

      }

    } else {

      int x;

      scanf("%d", &x);

      ans = 200;

      for(int i = 1; i <= n; i ++) {

        f[i] = 0;

      }

      dfs(belong[x], belong[x]);

      if(ans == 200) printf("*\n");

      else printf("%d\n", ans);

    }

  }

  return 0;

}

/*

 7 8 9

 21 33 33 18 42 22 26

 1 2

 1 3

 2 5

 3 5

 3 6

 4 6

 4 7

 6 7

 P 7

 T 4 2

 P 7

 P 5

 T 1 4

 P 7

 T 4 7

 P 2

 P 6

 6 5 6

 10 20 30 40 50 60

 1 5

 1 4

 3 6

 2 5

 4 5

 P 1

 P 5

 P 6

 T 1 6

 P 1

 P 4

 */

D - Folding Machine

爆搜，用序列的hash值进行剪枝。

#include <bits/stdc++.h>

using namespace std;

const long long mod = 1e9 + 7;

const long long base = 131LL;

const int maxn = 20;

int n, m;

int a[maxn], b[maxn];

int ans;

int to[maxn];

map<long long, int> ha;

long long Get(int x) {

  long long res = 0;

  for(int i = 1; i <= x; i ++) {

    res = res * base % mod;

    res = res + to[i];

    res = res % mod;

  }

  return res;

}

void dfs(int x) {

  if(x < m) return;

  if(x == m) {

    int fail = 0;

    for(int i = 1; i <= m; i ++) {

      if(a[i] != b[i]) fail = 1;

    }

    if(fail == 0) ans = 1;

   // return;

  }

  int tmp[maxn];

  for(int i = 1; i <= x; i ++) {

    tmp[i] = a[i];

  }

  for(int i = 0; i < x; i ++) {

    int left = i;

    int right = x - left;

    if(max(left, right) < m) continue;

    int len = max(left, right);

    memset(to, 0, sizeof to);

    if(left > right) {

      for(int i = 1; i <= left; i ++) {

        to[i] = tmp[i];

      }

      int p = n;

      for(int i = left - right + 1; i <= left; i ++) {

        to[i] += tmp[p];

        p --;

      }

    } else {

      int p = x;

      for(int i = 1; i <= right; i ++) {

        to[i] = tmp[p];

        p --;

      }

      p = left;

      for(int i = right; p; i --) {

        to[i] += tmp[p];

        p --;

      }

    }

    long long to_ha = Get(len);

    if(ha[to_ha]) continue;

    ha[to_ha] = 1;

    for(int i = 1; i <= len; i ++) {

      a[i] = to[i];

    }

    dfs(len);

    if(ans == 1) return;

  }

  for(int i = 1; i <= x; i ++) {

    a[i] = tmp[i];

  }

}

int main() {

  int suma=0,sumb=0;

  scanf("%d", &n);

  for(int i = 1; i <= n; i ++) scanf("%d", &a[i]), suma += a[i];

  scanf("%d", &m);

  for(int i = 1; i <= m; i ++) scanf("%d", &b[i]), sumb += b[i];

  if(suma == sumb && n >= m)

  dfs(n);

  if(ans) printf("S\n");

  else printf("N\n");

  return 0;

}

/*

 7

 5 6 23 8 19 7 10

 4

 5 16 30 27

 7

 1 2 3 4 5 6 7

 5

 7 6 5 5 5

 4

 1 2 3 4

 1

 10

 6

 19 23 3 51 2 0

 2

 34 64

 6

 1 2 3 4 5 6

 6

 1 2 3 4 5 6

 */

E - Dangerous Dive

模拟。

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5 + 10;

int f[maxn];

vector<int> ans;

int main() {

  int n, r;

  scanf("%d%d", &n, &r);

  for(int i = 1; i <= r; i ++) {

    int x;

    cin >> x;

    f[x] = 1;

  }

  for(int i = 1; i <= n; i ++) {

    if(f[i]) continue;

    ans.push_back(i);

  }

  if(ans.size() == 0) {

    printf("*");

  } else {

    for(int i = 0; i < ans.size(); i ++) {

      printf("%d", ans[i]);

      if(i < ans.size() - 1) printf(" ");

      else printf("\n");

    }

  }

  return 0;

}

F - Triangles

枚举起点，然后二分两个中间点。

#include <bits/stdc++.h>

using namespace std;

const int maxn = 5e5 + 10;

long long a[maxn];

long long sum[maxn];

int main() {

  int n;

  scanf("%d", &n);

  int ans = 0;

  for(int i = 1; i <= n; i ++) {

    scanf("%lld", &a[i]);

    a[i + n] = a[i];

  }

  for(int i = 1; i <= 2 * n; i ++) {

    sum[i] = sum[i - 1] + a[i];

  }

  if(sum[n] % 3) {

    printf("%d\n", 0);

    return 0;

  }

  for(int i = 1; i <= n; i ++) {

    int L, R, p;

    L = i, R = i + n - 1, p = -1;

    while(L <= R) {

      int mid = (L + R) / 2;

      long long num = sum[mid] - sum[i - 1];

      if(num == sum[n] / 3) {

        p = mid;

        break;

      } else if(num < sum[n] / 3) {

        L = mid + 1;

      } else {

        R = mid - 1;

      }

    }

    if(p == -1) continue;

    int tmp = p;

    L = p + 1, R = i + n - 1, p = -1;

    while(L <= R) {

      int mid = (L + R) / 2;

      long long num = sum[mid] - sum[tmp];

      if(num == sum[n] / 3) {

        p = mid;

        break;

      } else if(num < sum[n] / 3) {

        L = mid + 1;

      } else {

        R = mid - 1;

      }

    }

    if(p == -1) continue;

    //printf("debug : %d\n", i);

    ans ++;

  }

  printf("%d\n", ans / 3);

  return 0;

}

/*

 8

 4 2 4 2 2 6 2 2

 6

 3 4 2 1 5 3

 */

G - Lines of Containers

可以发现，行列是独立的。即我们可以抓出每行的最小值，按最小值进行行调整。然后随便抓一行，按这一行的列上的值进行调整，这一行调整完毕之后检查其余行。

#include <bits/stdc++.h>

using namespace std;

int a[500][500];

int mn[500];

int tmp[500];

int n, m;

int ans;

void swapR(int x, int y) {

  for(int j = 1; j <= m; j ++) {

    swap(a[x][j], a[y][j]);

  }

}

void swapC(int x, int y) {

  for(int i = 1; i <= n; i ++) {

    swap(a[i][x], a[i][y]);

  }

}

int main() {

  scanf("%d%d", &n, &m);

  for(int i = 1; i <= n; i ++) {

    mn[i] = 1000000;

    for(int j = 1; j <= m; j ++) {

      scanf("%d", &a[i][j]);

      mn[i] = min(mn[i], a[i][j]);

    }

  }

  int fail = 0;

  for(int i = 1; i <= n; i ++) {

    tmp[i] = mn[i];

  }

  sort(tmp + 1, tmp + n + 1);

  for(int i = 1; i <= n; i ++) {

    if(tmp[i] == mn[i]) continue;

    int pos;

    for(int j = 1; j <= n; j ++) {

      if(mn[j] == tmp[i]) pos = j;

    }

    ans ++;

    swap(mn[i], mn[pos]);

    swapR(i, pos);

  }

  for(int j = 1; j <= m; j ++) {

    tmp[j] = mn[j] = a[1][j];

  }

  sort(tmp + 1, tmp + m + 1);

  for(int j = 1; j <= m; j ++) {

    if(tmp[j] == mn[j]) continue;

    int pos;

    for(int i = 1; i <= m; i ++) {

      if(mn[i] == tmp[j]) pos = i;

    }

    ans ++;

    swap(mn[j], mn[pos]);

    swapC(j, pos);

  }

  int num = 1;

  for(int i = 1; i <= n; i ++) {

    for(int j = 1; j <= m; j ++) {

      if(a[i][j] != num) fail = 1;

      num ++;

    }

  }

  if(fail) {

    printf("*");

  } else {

    printf("%d\n", ans);

  }

  return 0;

}

/*

 2 2

 3 4

 1 2

 3 3

 9 2 4

 5 8 7

 6 1 3

 5 4

 13 15 14 16

 5 7 6 8

 9 11 10 12

 1 3 2 4

 17 19 18 20

 */

H - Buses

斐波那契数列变了一下，方案数${f_i} = L \times {f_{i - 2}} + K \times {f_{i - 1}}$矩阵快速幂加速即可

#include <bits/stdc++.h>

using namespace std;

const long long mod = 1e6;

long long n, K, L;

struct Matrix

{

  long long A[4][4];

  int R, C;

  Matrix operator*(Matrix b);

};

Matrix Matrix::operator*(Matrix b)

{

  Matrix c;

  memset(c.A,0,sizeof(c.A));

  int i,j,k;

  for(i=1; i<=R; i++)

    for(j=1; j<=b.C; j++)

      for(k=1; k<=C; k++)

        c.A[i][j]=((A[i][k]*b.A[k][j])%mod+c.A[i][j])%mod;

  c.R=R; c.C=b.C;

  return c;

}

Matrix X, Y, Z;

long long init(long long a, long long b, long long c)

{

  b = b % mod;

  c = c % mod;

  memset(X.A,0,sizeof X.A);

  memset(Y.A,0,sizeof Y.A);

  memset(Z.A,0,sizeof Z.A);

  Z.A[1][1] = 1;

  Z.A[1][2] = b;

  Z.R = 1; Z.C = 2;

  for(int i=1;i<=2;i++) Y.A[i][i]=1;

  Y.R = 2; Y.C = 2;

  X.A[1][1] = 0; X.A[1][2] = c;

  X.A[2][1] = 1; X.A[2][2] = b;

  X.R = 2; X.C = 2;

  while (a)

  {

    if (a % 2 == 1) Y = Y*X;

    a = a >> 1;

    X = X*X;

  }

  Z = Z*Y;

  return Z.A[1][1];

}

int main() {

  cin >> n >> K >> L;

  n /= 5;

  printf("%06lld\n", init(n, K, L));

  return 0;

}

I - Patches

$dp[i]$表示修补到$i$个洞为止的最小花费。

感觉这题可以加强一下，因为轮子是一个环，再加上一个枚举起点也不算过分吧...

#include <bits/stdc++.h>

using namespace std;

const int maxn = 2000;

int n;

int a[maxn];

int dp[maxn];

int t1, t2;

int C;

int main() {

  scanf("%d%d%d%d", &n, &C, &t1, &t2);

  for(int i = 1; i <= n; i ++) {

    scanf("%d", &a[i]);

  }

  sort(a + 1, a + 1 + n);

  for(int i = 1; i <= n; i ++) {

    dp[i] = dp[i - 1] + min(t1, t2);

    int pos1 = -1, pos2 = -1;

    for(int j = i - 1; j >= 1; j --) {

      if(a[i] - a[j] <= t1) pos1 = j;

      if(a[i] - a[j] <= t2) pos2 = j;

    }

    if(pos1 != -1) {

      dp[i] = min(dp[i], dp[pos1 - 1] + t1);

    }

    if(pos2 != -1) {

      dp[i] = min(dp[i], dp[pos2 - 1] + t2);

    }

  }

  printf("%d\n", dp[n]);

  return 0;

}

/*

 5 20 2 3

 2 5 8 11 15

 4 20 12 9

 1 2 3 13

 */

J - Trucks

先求出最大生成树，这个时候把必要的长度最长的边都保留下来了。

对于每一次的询问，就是求两点的路径上的最小权值，可以倍增处理。

#include <bits/stdc++.h>

using namespace std;

const int maxn = 2e5 + 10;

int n, m, Q;

struct Edge {

  int u, v, w;

}e[maxn];

int belong[maxn];

int h[maxn], to[maxn], cost[maxn], nx[maxn], cnt;

int f[maxn], dep[maxn], too[maxn][35], mn[maxn][35], idx[maxn][35];

void add(int u, int v, int c) {

  to[cnt] = v;

  nx[cnt] = h[u];

  cost[cnt] = c;

  h[u] = cnt ++;

}

int Find(int x) {

  if(x != belong[x]) return belong[x] = Find(belong[x]);

  return belong[x];

}

bool cmp(const Edge &a, const Edge &b) {

  return a.w > b.w;

}

void dfs(int fa,int x,int y,int eid)

{

  f[x]=fa; dep[x]=y;

  if(x==1)

  {

    too[x][0] = -1;

    mn[x][0] = 1e6;

  }

  else

  {

    too[x][0] = fa;

    mn[x][0] = cost[eid];

  }

  for(int j=1;j<=30;j++)

  {

    if((1<<j) > dep[x]-1) {

      too[x][j] = -1;

      mn[x][j] = 1e6;

    } else {

      too[x][j] = too[too[x][j-1]][j-1];

      mn[x][j] = min(mn[x][j-1], mn[too[x][j-1]][j-1]);

    }

  }

  for(int i = h[x]; i != -1; i = nx[i])

  {

    int v = to[i];

    if(v == fa) continue;

    if(f[v] != 0) continue;

    dfs(x, v, y + 1, i);

  }

}

int F(int a,int b)

{

  if(dep[a]<dep[b]) swap(a,b);

  int MN=1e6;

  if(dep[a]!=dep[b])

  {

    while(1)

    {

      int L=0,R=30,pos;

      while(L<=R)

      {

        int mid=(L+R)/2;

        if(too[a][mid]!=-1&&dep[too[a][mid]]>=dep[b]) L=mid+1,pos=mid;

        else R=mid-1;

      }

      if(mn[a][pos]<=MN) MN=mn[a][pos];

      a=too[a][pos];

      if(dep[a]==dep[b]) break;

    }

  }

  if(a==b) return MN;

  while(1)

  {

    if(f[a]==f[b])

    {

      if(mn[a][0]<=MN) MN=mn[a][0];

      if(mn[b][0]<=MN) MN=mn[b][0];

      break;

    }

    int L=0,R=30,pos;

    while(L<=R)

    {

      int mid=(L+R)/2;

      if(too[a][mid]!=too[b][mid]) L=mid+1,pos=mid;

      else R=mid-1;

    }

    if(mn[a][pos]<=MN) MN=mn[a][pos];

    if(mn[b][pos]<=MN) MN=mn[b][pos];

    a=too[a][pos];

    b=too[b][pos];

  }

  return MN;

}

int main() {

  scanf("%d%d%d", &n, &m, &Q);

  for(int i = 1; i <= n; i ++) {

    belong[i] = i;

    h[i] = -1;

  }

  for(int i = 1; i <= m; i ++) {

    scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);

  }

  sort(e + 1, e + 1 + m, cmp);

  for(int i = 1; i <= m; i ++) {

    int fa = Find(e[i].u);

    int fb = Find(e[i].v);

    if(fa == fb) continue;

    belong[fa] = fb;

  //  printf("debug %d %d %d\n", e[i].u, e[i].v, e[i].w);

    add(e[i].u, e[i].v, e[i].w);

    add(e[i].v, e[i].u, e[i].w);

  }

  dfs(-1, 1, 1, -1);

  while(Q --) {

    int x, y;

    scanf("%d%d", &x, &y);

    printf("%d\n", F(x, y));

  }

  return 0;

}

/*

 4 5 4

 1 2 9

 1 3 0

 2 3 8

 2 4 7

 3 4 4

 1 4

 2 1

 3 1

 4 3

 4 5 2

 1 2 30

 2 3 20

 3 4 10

 4 1 40

 2 4 50

 1 3

 1 2

 */

巴特西

2013-2014 ACM-ICPC Brazil Subregional Programming Contest 题解

最新文章

热门文章