2015 ACM Amman Collegiate Programming Contest 题解

2024-03-20 12:48:28

【题目链接】

A - Who Is The Winner

模拟。

#include <bits/stdc++.h>

using namespace std;

int T;

int n;

struct X {

  string name;

  int num;

  int ti;

}s[10010];

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

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

  return a.ti < b.ti;

}

int main() {

  scanf("%d", &T);

  while(T--) {

    scanf("%d",&n);

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

      cin>>s[i].name;

      cin>>s[i].num;

      cin>>s[i].ti;

     // cout << i << endl;

    }

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

      //cout << s[i].name << " " << s[i].num << " " << s[i].ti << endl;

    }

    sort(s, s+n, cmp);

    cout << s[0].name<<endl;

  }

  return 0;

}

/*

 2

 3

 tourist 13 567

 petr 13 600

 endagorion 144 19

 2

 tourist 7 512

 bayashout ​7 477

 */

B - Rock-Paper-Scissors

枚举 $x$ 和 $y$，确定z，然后区间和算一下就能算出来谁赢了。

#include <bits/stdc++.h>

using namespace std;

int T;

int n;

char s[1010];

int sum[1010][3];

int Get(int L, int R, int num) {

  if(R < L) return 0;

  return sum[R][num] - sum[L-1][num];

}

int check(int x, int y, int z) {

  //[1,x]  R

  //[x+1,x+y]  P

  //[x+y+1,x+y+z]  S

  int point1 = Get(1,x,1);

  int pin1 = Get(1,x,0);

  int point2 = Get(x+1,x+y,0);

  int pin2 = Get(x+1,x+y,2);

  int point3 = Get(x+y+1,x+y+z,2);

  int pin3 = Get(x+y+1,x+y+z,1);

 // cout << point1 << " "<< point2 << " " << point3 << endl;

  int point_first = point1+point2+point3;

  int point_second = n - point_first - pin1 - pin2-pin3;

  if(point_first > point_second) return 1;

  return 0;

}

int main() {

  scanf("%d", &T);

  while(T--) {

    scanf("%d", &n);

    scanf("%s", s);

    memset(sum, 0, sizeof sum);

    for(int i = 0; s[i]; i ++) {

      sum[i+1][0] = sum[i][0];

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

      sum[i+1][2] = sum[i][2];

      if(s[i] == 'R') sum[i+1][0] ++;

      if(s[i] == 'S') sum[i+1][1] ++;

      if(s[i] == 'P') sum[i+1][2] ++;

    }

    int ans = 0;

    int len = strlen(s);

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

      for(int y = 0; y <= len; y ++) {

        if(x + y > len) continue;

        int z = len - x - y;

        ans = ans + check(x, y, z);

      }

    }

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

  }

  return 0;

}

C - Street Lamps

先把照亮的都确定一下，然后看连续的没被照亮的有几个，算一下就好了。

#include <bits/stdc++.h>

using namespace std;

int T,n;

char s[100010];

int cal(int x) {

  if(x == 0) return 0;

  int res = x / 3;

  if(x % 3) res ++;

  return res;

}

int main() {

  scanf("%d",&T);

  while(T--) {

    scanf("%d",&n);

    scanf("%s",s);

    int ans = 0;

    int len = strlen(s);

    for(int i = 0; s[i]; i++) {

      if(s[i] == '*') {

        if(i - 1 >= 0 && s[i-1] == '.') s[i -1] = '0';

        if(i + 1 < len && s[i+1] == '.') s[i+1] = '0';

      }

    }

    int num = 0;

    for(int i = 0; s[i]; i ++) {

      if(s[i] != '.') {

        ans = ans + cal(num);

        num = 0;

      } else {

        num ++;

      }

    }

    ans = ans + cal(num);

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

  }

  return 0;

}

D - Alternating Strings

$dp_i$ 表示前缀需要分割成几段，枚举上一次断开的位置即可。

#include <bits/stdc++.h>

using namespace std;

int T;

int n, k, len;

char s[1010];

int dp[1010];

int jiao[1010][1010];

int Get(int x) {

  if(x == -1) return 0;

  return dp[x];

}

int main() {

  scanf("%d", &T);

  while(T--) {

    memset(jiao,0,sizeof jiao);

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

    scanf("%s",s);

    len = strlen(s);

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

      if(i + 1 < len) {

        if(s[i] != s[i + 1]) jiao[i][i + 1] = 1;

      }

      for(int j = i + 2; j < len; j ++) {

        if(s[j] != s[j - 1] && jiao[i][j - 1]) jiao[i][j] = 1;

      }

    }

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

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

      //  cout << i << " " << j << " " << jiao[i][j] << endl;

      }

    }

    dp[0] = 1;

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

      dp[i] = 100000;

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

        // [j+1, i]

        if(i - j > k) continue;

        if(jiao[j+1][i]) continue;

        dp[i] = min(dp[i], Get(j) + 1);

      }

    }

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

  }

  return 0;

}

E - Epic Professor

模拟。

#include <bits/stdc++.h>

using namespace std;

int T;

int n;

int x[100010];

int main() {

  scanf("%d", &T);

  while(T--) {

    scanf("%d",&n);

    int ans = 0;

    int cha = 1000;

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

      cin>>x[i];

      cha = min(cha, 100 - x[i]);

    }

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

      if(x[i] + cha >= 50) ans ++;

    }

    cout << ans << endl;

  }

  return 0;

}

F - Travelling Salesman

克鲁斯卡尔执行过程中，最小生成树上最大的边权就是答案。

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5+10;

int T;

int n,m;

struct Edge {

  int u, v;

  int c;

}e[maxn];

int f[maxn];

int Find(int x) {

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

  return f[x];

}

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

  return a.c<b.c;

}

int main() {

  scanf("%d", &T);

  while(T--) {

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

    for(int i=1;i<=n;i++)f[i]=i;

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

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

    }

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

    int ans = 0;

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

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

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

      if(fu==fv)continue;

      f[fu]=fv;

      ans=e[i].c;

    }

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

  }

  return 0;

}

/*

 2

 6 7

 1 2 3

 2 3 3

 3 1 5

 3 4 4

 4 5 4

 4 6 3

 6 5 5

 3 3

 1 2 1

 2 3 2

 3 1 3

 */

G - Heavy Coins

状压一下，某个状态是否可行，只要看看扔掉任意一个，是否都是不可行的。

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5+10;

int T;

int n;

int s;

int dp[1200];

int sum[1200];

int a[20];

int lowbit(int x) {

  return x & (-x);

}

int main() {

  scanf("%d",&T);

  while(T--) {

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

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

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

    }

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

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

        if((1 << j) & i) {

          sum[i] = sum[i ^ (1 << j)] + a[j];

        }

      }

    }

    int ans = 0;

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

      if(sum[i] < s) continue;

      int ok = 1;

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

        if((1 << j) & i) {

          if(sum[i ^ (1 << j)] >= s) ok = 0;

        }

      }

      if(ok == 0) continue;

      int tmp = 0;

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

        if((1 << j) & i) tmp ++;

      }

      ans = max(ans, tmp);

    }

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

  }

  return 0;

}

H - Bridges

求出割边，去掉割边，每个连通块缩点，会形成一棵树，看看树的直径，最优策略就是在直径两端添加边。

#include <bits/stdc++.h>

using namespace std;

const int N  = 2e5 + 10;

int dfn[N],low[N],dfs_clock;

int n, m;

int h[N], to[N], nx[N], sz;

int bridge[N];

int belong[N];

int block;

int p1, p2;

int dis1, dis2;

int f[N];

vector<int> g[N];

void add(int a, int b) {

  to[sz] = b;

  nx[sz] = h[a];

  h[a] = sz ++;

}

void tarjan(int u, int fa)

{

  dfn[u] = low[u] = ++dfs_clock;

  bool flag = false;

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

  {

    int v = to[i];

    if(v==fa && !flag)//如果有重边，那么边(u,v)被存了两次，所以，如果第二次访问，就让他通过

    {

      flag = true;

      continue;

    }

    if(dfn[v] == 0)

      tarjan(v,u);

    low[u] = min(low[u],low[v]);

    if(low[v] > dfn[u]) {

      //cntCut++;

      bridge[i] = 1;

    }

  }

}

void dfs(int x) {

  belong[x] = block;

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

    if(bridge[i]) continue;

    if(belong[to[i]]) continue;

    dfs(to[i]);

  }

}

void dfs1(int x, int y) {

  f[x] = 1;

  if(y > dis1) {

    dis1 = y;

    p1 = x;

  }

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

    if(f[g[x][i]]) continue;

    dfs1(g[x][i], y + 1);

  }

}

void dfs2(int x, int y) {

  f[x] = 1;

  if(y > dis2) {

    dis2 = y;

    p2 = x;

  }

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

    if(f[g[x][i]]) continue;

    dfs2(g[x][i], y + 1);

  }

}

int main()

{

  int T;

  scanf("%d", &T);

  while(T--) {

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

    sz = 0;

    dfs_clock = 0;

    memset(dfn, 0, sizeof dfn);

    memset(low,0,sizeof low);

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

      h[i] = -1;

    }

    for(int i=0; i<m; ++i)

    {

      int a, b;

      scanf("%d%d",&a,&b);

      add(a, b);

      add(b, a);

    }

    memset(bridge, 0, sizeof bridge);

    tarjan(1, -1);

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

      if(bridge[i]) bridge[i ^ 1] = 1;

    }

    /*

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

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

        if(bridge[i])

          printf("%d - %d\n", from, to[i]);

      }

    }

     */

    memset(belong,0,sizeof belong);

    block = 0;

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

      if(belong[i] == 0) {

        block ++;

        dfs(i);

      }

    }

    /*

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

      cout << i << " " << belong[i] << endl;

    }

     */

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

      g[i].clear();

    }

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

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

        if(bridge[i]) {

       //   cout << belong[from] << " " << belong[to[i]] << endl;

          g[belong[from]].push_back(belong[to[i]]);

          g[belong[to[i]]].push_back(belong[from]);

        }

      }

    }

    memset(f,0,sizeof f);

    p1 = 0;

    dis1 = 0;

    dfs1(1, 0);

    memset(f,0,sizeof f);

    p2 = 0;

    dis2 = 0;

    dfs2(p1,0);

    printf("%d\n", block - 1 - dis2);

  }

  return 0;

}

I - Bahosain and Digits

枚举答案，以及枚举最终变到哪个数字，然后验证一下是否可行。

#include <bits/stdc++.h>

using namespace std;

int T;

char s[500];

int f[500], t[500], ci[500], sum[500];

int len;

int Get(int x) {

  if(x < 0) return 0;

  return sum[x];

}

int Sum(int L, int R) {

  return (Get(R) - Get(L - 1) + 10) % 10;

}

bool check(int x, int y) {

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

    t[i] = f[i];

    ci[i] = 0;

    sum[i] = 0;

  }

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

    ci[i] = 0;

    t[i] = (t[i] + Sum(i-x+1,i-1)) % 10;

    while(t[i] != y) {

      t[i] = (t[i] + 1) % 10;

      ci[i] ++;

    }

    sum[i] = (Get(i - 1) + ci[i]) % 10;

  }

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

    ci[i] = 0;

    t[i] = (t[i] + Sum(i-x+1,i-1)) % 10;

   // cout << i << " " << i-x+1 << " " << i-1 << endl;

    sum[i] = (Get(i - 1) + ci[i]) % 10;

  }

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

    if(t[i] != t[0]) return 0;

  }

  return 1;

}

int main() {

  scanf("%d", &T);

  while (T--) {

    scanf("%s", s);

    len = strlen(s);

    for(int i = 0; s[i]; i ++) {

      f[i] = s[i] - '0';

    }

    int ans = 1;

    int ok = 0;

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

      for(int limit = 0; limit <= 9; limit ++) {

        if(check(i, limit)) {

          ans = i;

          ok = 1;

          break;

        }

      }

      if(ok) break;

    }

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

  }

  return 0;

}

J - Candy

贪心。人按年龄排序，糖果按个数排序，贪心拿就好了。

#include <bits/stdc++.h>

using namespace std;

int T;

int n, m;

int age[100010];

int tang[100010];

struct X {

  int x, y;

}s[100010], t[100010];

int sz1, sz2;

int main() {

  scanf("%d",&T);

  while(T--) {

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

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

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

    }

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

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

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

    }

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

    sz1 = 0, sz2 = 0;

    s[sz1].x = age[1];

    s[sz1].y = 1;

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

      if(age[i] != s[sz1].x) {

        sz1 ++;

        s[sz1].x = age[i];

        s[sz1].y = 1;

      } else {

        s[sz1].y ++;

      }

    }

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

    //  cout << s[i].x << " " << s[i].y << endl;

    }

    t[sz2].x = tang[1];

    t[sz2].y = 1;

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

      if(tang[i] != t[sz2].x) {

        sz2 ++;

        t[sz2].x = tang[i];

        t[sz2].y = 1;

      } else {

        t[sz2].y ++;

      }

    }

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

    //    cout << t[i].x << " " << t[i].y << endl;

    }

    int ok = 1;

    int p2 = 0;

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

      while(p2 <= sz2 && t[p2].y < s[i].y) {

        p2 ++;

      }

      if(p2 > sz2) {

        ok = 0;

        break;

      }

      p2 ++;

    }

    if(ok) printf("YES\n");

    else printf("NO\n");

  }

  return 0;

}

K - Runtime Error

枚举一下就好了，注意 $a_i$ 为 $0$ 的情况。

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5 + 10;

int T;

int f[maxn];

int a[maxn];

int n,k;

int main() {

  scanf("%d", &T);

  while(T--) {

    memset(f, 0, sizeof f);

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

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

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

      f[a[i]] ++;

    }

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

    int ok = 0;

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

      if(a[i] == 0) continue;

      if(k % a[i]) continue;

      if(a[i] != k / a[i]) {

        if(f[a[i]] && f[k / a[i]]) {

          printf("%d %d\n", a[i], k / a[i]);

          ok = 1;

          break;

        }

      } else {

        if(f[a[i]] >= 2) {

          printf("%d %d\n", a[i], k / a[i]);

          ok = 1;

          break;

        }

      }

    }

    if(ok == 0) printf("-1\n");

  }

  return 0;

}

L - Alternating Strings II

D题的加强版，可以发现能推到 $i$ 位置的是一段连续的区间，维护区间最小值即可。

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5 + 10;

int T, n, k;

char s[maxn];

int seg[maxn * 4];

int pre[maxn];

int dp[maxn];

int len;

void update(int pos, int val, int l, int r, int rt) {

  if(l == r) {

    seg[rt] = val;

    return;

  }

  int mid = (l + r) / 2;

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

  else update(pos, val, mid + 1, r, 2 * rt + 1);

  seg[rt] = min(seg[2 * rt],seg[2 * rt + 1]);

}

int get(int L, int R, int l, int r, int rt) {

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

    return seg[rt];

  }

  int left = 200000;

  int right = 200000;

  int mid = (l + r) / 2;

  if(L <= mid) left = get(L, R, l, mid, 2 * rt);

  if(R > mid) right = get(L, R, mid + 1, r, 2 * rt + 1);

  return min(left, right);

}

int Qu(int L, int R, int idx) {

  if(L < 0) return 0;

  return get(L, R, 0, len - 1, 1);

}

int main() {

  scanf("%d", &T);

  while(T--) {

    memset(pre, -1, sizeof pre);

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

    scanf("%s", s);

    len = strlen(s);

    pre[0] = 0;

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

      pre[i] = i;

      if(s[i] != s[i - 1]) pre[i] = pre[i - 1];

    }

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

   //   cout << i << " " << pre[i] << endl;

    }

    dp[0] = 1;

    update(0, dp[0], 0, len - 1, 1);

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

      dp[i] = dp[i - 1] + 1;

      if(i - pre[i] + 1 >= k) {

      } else {

        if(i - k >= -1) dp[i] = min(dp[i - 1], Qu(i - k, pre[i] - 2, i)) + 1;

        else if(pre[i] - 2 >= -1) dp[i] = 1;

        else dp[i] = dp[i - 1] + 1;

      }

      update(i, dp[i], 0, len - 1, 1);

    //  cout << i << " " << dp[i] << endl;

    }

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

  }

  return 0;

}
上一篇：【模块化编程】理解requireJS-实现一个简单的模块加载器


下一篇：经典的SQL面试题