2017, X Samara Regional Intercollegiate Programming Contest 题解

【题目链接】

A - Streets of Working Lanterns - 2

首先将每一个括号匹配串进行一次缩减，即串内能匹配掉的就匹配掉，每个串会变成连续的$y$个右括号+连续$z$个左括号。

我们把缩减后的串分成四类：

第一类：只有左括号

第二类：左右括号都有，且$z$大于等于$y$

第三类：左右括号都有，且$z$小于$y$

第四类：只有右括号

类与类之间肯定是按第$1$，$2$，$3$，$4$类的顺序放置。

第一类内部和第四类内部可以随便放。第二类的放置顺序也很容易想。

问题出在第三类放置的顺序，按照$z$大的先放是正确方式，其余都能举出反例。

#include<bits/stdc++.h>

using namespace std;

const int maxn = 2e5 + 10;

struct X {

  int y, z;

  int id, tp;

}s[maxn];

int n;

char t[maxn];

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

  if(a.tp != b.tp) return a.tp < b.tp;

  if(a.tp == 2) {

    if(a.y != b.y) return a.y < b.y;

    return a.z > b.z;

  } else if(a.tp == 3) {

    return a.z > b.z;

  } else {

    return 0;

  }

}

int main() {

  scanf("%d", &n);

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

    scanf("%s", t);

    int z = 0, y = 0;

    for(int j = 0; t[j]; j ++) {

      if(t[j] == '(') z ++;

      else {

        if(z) z --;

        else y ++;

      }

    }

    s[i].y = y;

    s[i].z = z;

    s[i].id = i;

    /* ))) y个 ((( z个 */

    if(y + z == 0) s[i].tp = 0;

    else if(y == 0 && z != 0) s[i].tp = 1;

    else if(y != 0 && z == 0) s[i].tp = 4;

    else if(z - y >= 0) s[i].tp = 2;

    else s[i].tp = 3;

  }

  sort(s, s + n, cmp);

  int sum = 0;

  int fail = 0;

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

    sum = sum - s[i].y;

    if(sum < 0) {

      fail = 1;

      break;

    }

    sum = sum + s[i].z;

  }

  if(fail || sum != 0) {

    printf("NO\n");

  } else {

    printf("YES\n");

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

      printf("%d", s[i].id + 1);

      if(i < n - 1) printf(" ");

      else printf("\n");

    }

  }

  return 0;

}

/*

 4

 (((((

 )))))((

 ))(

 )

 y大的先放会无解

 4

 (((((

 ))))(

 )))((

 )

 */

B - Pursuing the Happiness

先找出有多少个区间是happiness，接下里分情况讨论：

如果没有：要注意交换后可能出现happiness。

如果有$1$个：那么可以有多少方式，例如交换第一个和第二个。

如果有$2$个：可以有多种方式，例如第一个区间的第一个字母和第二个区间的第二个字母交换。

如果大于等于$3$个：无解。

#include <bits/stdc++.h>

using namespace std;

const int N = 4e5 + 10;

char S[N], T[N] = "happiness";

int nx[N];

int slen, tlen;

vector<int > pos;

void getNext()

{

  int j, k;

  j = 0; k = -1; nx[0] = -1;

  while(j < tlen)

    if(k == -1 || T[j] == T[k])

      nx[++j] = ++k;

    else

      k = nx[k];

}

int KMP_Count()

{

  int ans = 0;

  int i, j = 0;

  if(slen == 1 && tlen == 1)

  {

    if(S[0] == T[0])

      return 1;

    else

      return 0;

  }

  getNext();

  for(i = 0; i < slen; i++)

  {

    while(j > 0 && S[i] != T[j])

      j = nx[j];

    if(S[i] == T[j])

      j++;

    if(j == tlen)

    {

      ans++;

      pos.push_back(i);

      j = nx[j];

    }

  }

  return ans;

}

int main() {

  srand(time(NULL));

  scanf("%s", S);

  slen = strlen(S);

  tlen = strlen(T);

  KMP_Count();

  if(slen < 9) {

    printf("YES\n");

    printf("1 2\n");

    return 0;

  }

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

    printf("YES\n");

    int x, y;

    while(1) {

      x = rand() % slen;

      y = rand() % slen;

      if(x == y) continue;

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

      pos.clear();

      KMP_Count();

      if(pos.size() == 0) break;

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

    }

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

  } else if(pos.size() == 1) {

    // [pos[0] - 8 ,pos[0]]

    printf("YES\n");

    int x = 0, y = 1;

    printf("%d %d\n", x + pos[0] - 8 + 1, y + pos[0] - 8 + 1);

  } else if(pos.size() == 2) {

    int x = 0, y = 1;

    printf("YES\n");

    printf("%d %d\n", x + pos[0] - 8 + 1, y + pos[1] - 8 + 1);

  } else {

    printf("NO\n");

  }

  return 0;

}

C - Urn with Balls

留。

#include<cstdio>

#include<algorithm>

#include<string.h>

using namespace std;

int main()

{

    long long a,b,c,n,m;

    while(~scanf("%lld%lld%lld",&a,&b,&c))

    {

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

        long long t1,t2;

        if(a+c<=n&&b<=m)t1=a+b+c;

        else if(n>=m)

        {

            if(a+c<=n&&b>m)

                t1=m;

            else if(a+c>n&&b>m)

                t1=m;

            else if(a+c>n&&b<=m)

                t1=n;

        }

        else

        {

            if(a+c<=n&&b>m)

                t1=m;

            else if(a+c>n&&b>m)

                t1=n;

            else if(a+c>n&&b<=m)

                t1=n;

        }

        if(a<=n&&b+c<=m)t2=a+b+c;

        else if(n>=m)

        {

            if(a<=n&&b+c>m)t2=m;

            else if(a>n&&b+c>m)t2=m;

            else if(a>n&&b+c<=m)t2=n;

        }

        else

        {

            if(a<=n&&b+c>m)t2=m;

            else if(a>n&&b+c>m)t2=n;

            else if(a>n&&b+c<=m)t2=n;

        }

        printf("%lld\n",min(t1,t2));

    }

    return 0;

}

D - Jumps

如果所有的数字的$gcd$是$x$的约数，则可行，否则不可行。

#include <bits/stdc++.h>

using namespace std;

const int maxn = 2e5 + 10;

int n, x;

int gcd(int a, int b) {

  if(b == 0) return a;

  return gcd(b, a % b);

}

int main() {

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

  int g;

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

    int y;

    scanf("%d", &y);

    if(i == 1) g = y;

    else g = gcd(g, y);

  }

  if(abs(x) % g) printf("NO\n");

  else printf("YES\n");

  return 0;

}

E - Bonuses and Teleports

宝石和跳跃机合起来排序，最左边跳跃机左边那些宝石必须来回走一次，最右边跳跃机右边的那些宝石必须来回走一次。

然后计算每相邻两个跳跃机之间的宝石怎么取费用最小，枚举一下哪个从宝石断开就可以了。

#include <bits/stdc++.h>

using namespace std;

const int maxn = 4e5 + 10;

struct X {

  int tp;

  long long x;

}s[maxn];

int n, m;

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

  if(a.x != b.x) return a.x < b.x;

  return a.tp > b.tp;

}

long long work(int L, int R) {

 // cout << L << " - " << R << endl;

  if(R - L < 2) return 0LL;

  long long res = s[R].x - s[L].x;

  for(int i = L; i <= R - 1; i ++) {

    long long sum = (s[i].x - s[L].x) * 2LL;

    sum += (s[R].x - s[i + 1].x) * 2LL;

    res = min(res, sum);

  }

  return res;

}

int main() {

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

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

    scanf("%lld", &s[i].x);

    s[i].tp = 0;

  }

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

    scanf("%lld", &s[i].x);

    s[i].tp = 1;

  }

 // cout << "debug" << endl;

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

  int pre = -1;

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

    if(s[i].tp == 0) {

      pre = i;

      break;

    }

  }

  long long ans = 0;

  ans = abs(s[pre].x - s[0].x) * 2LL;

  while(1) {

    int now = -1;

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

      if(s[i].tp == 0) {

        now = i;

        break;

      }

    }

    if(now == -1) {

      ans = ans + abs(s[n + m - 1].x - s[pre].x) * 2LL;

      break;

    }

    // [pre, now]

    ans = ans + work(pre, now);

    pre = now;

  }

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

  return 0;

}

F - Circuits

这是我做的第一个交互题。我是随机做法，交了很多次，有一次是通过的，其余全是答案错误。

具体想法是这样的：

假设我们知道其中一个可用的是哪个，那么我们就可以找出所有可用的。

然后我就去猜哪个是可用的，然后验证看看是不是满足条件。验证的时候就是看不可用的数量是否严格小于一半。

因为题目要求在$4n$次出解，因此我们至少可以猜$4$次，中一次就可以了，而且每次猜对的概率约等于$1/2$，再加一点剪枝，可以使得猜的次数增加，具体可以看代码。

#include <bits/stdc++.h>

using namespace std;

const int maxn = 100010;

int n;

vector<int> ans;

int f[maxn];

char s1[maxn], s2[maxn];

int main() {

  srand(time(NULL));

  scanf("%d", &n);

  int h = (n - 1) / 2;

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

    ans.clear();

    int x;

    int y = rand() % (n - t) + 1;

    int num = 0;

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

      if(f[i]) continue;

      num ++;

      if(num == y) {

        x = i;

        break;

      }

    }

    f[x] = 1;

    int fail = 0;

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

      if(i == x) {

        ans.push_back(i);

        continue;

      }

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

      fflush(stdout);

      scanf("%s%s", s1, s2);

      if(s1[0] == '+' && s2[0] == '+') {

        ans.push_back(i);

      }

      if(i - ans.size() > h) {

        fail = 1;

        break;

      }

    }

    if(n - ans.size() > h) fail = 1;

    if(fail == 0) break;

  }

  printf("! %d", ans.size());

  sort(ans.begin(), ans.end());

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

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

  }

  printf("\n");

  fflush(stdout);

  return 0;

}

G - I love Codeforces

模拟一下就可以了。

#include <bits/stdc++.h>

using namespace std;

const int maxn = 2e5 + 10;

string name[maxn];

int n, m;

int p[maxn], q[maxn];

int main() {

  scanf("%d", &n);

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

    cin >> name[i];

    q[i] = i;

  }

  int m;

  scanf("%d", &m);

  int x, y;

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

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

    p[x] = p[y] + 1;

    q[x] = q[y];

  }

  while(p[1]) {

    printf("I_love_");

    p[1] --;

  }

  cout << name[q[1]] << endl;

  return 0;

}

H - Perfect Ban

找到一个最大值的位置，最大值的位置一定要被删掉，不然留下个最值不会让答案更优，接下来有三种策略：

第一种：删掉最大值所在行和列。

第二种：删掉最大值所在的行，再删除剩余矩阵最大值所在的列。

第三种：删掉最大值所在的列，再删除剩余矩阵最大值所在的行。

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1010;

int n, m;

int a[maxn][maxn];

vector<int> mx;

vector<int> r;

vector<int> c;

int work(int x, int y) {

  int res = 0;

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

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

      if(i == x || j == y) continue;

      res = max(res, a[i][j]);

    }

  }

  return res;

}

int main() {

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

  int mr = 1, mc = 1, Max = a[1][1];

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

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

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

      if(a[i][j] > Max) {

        Max = a[i][j];

        mr = i;

        mc = j;

      }

    }

  }

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

    mx.push_back(0);

    r.push_back(0);

    c.push_back(0);

  }

  // 删最大值所在行列

  r[0] = mr;

  c[0] = mc;

  mx[0] = work(mr, mc);

  r[1] = mr;

  // 先删最大值所在行，再删最大值所在列

  int kk = work(mr, 0);

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

    if(i == mr) continue;

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

      if(a[i][j] == kk) {

        c[1] = j;

      }

    }

  }

  mx[1] = work(r[1], c[1]);

  c[2] = mc;

  // 先删最大值所在列，再删最大值所在行

  int qq = work(0, mc);

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

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

      if(j == mc) continue;

      if(a[i][j] == qq) {

        r[2] = i;

      }

    }

  }

  mx[2] = work(r[2], c[2]);

  int ans = 1e9 + 7;

  int idx = 0;

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

    if(mx[i] < ans) {

      ans = mx[i];

      idx = i;

    }

  }

  printf("%d %d\n", r[idx], c[idx]);

  return 0;

}

I - Matrix God

一开始的做法：检查每一行的和是否相同，每一列的和是否相同，然后随机选择$n$个点看是否相同，但是一直答案错误。后来意识到一个问题，假设数据是$1000*1000$的矩阵，$C$矩阵和$A*B$矩阵的差别仅仅是其中的一个$2*2$子矩阵，这时候，可以构造出数据使得每一行每一列的和都相同，随机选择$n$个点大概率也是相同的，所以检测不出来。

后来我检测了每一行的$hash$值，即和字符串$hash$做法一样，每一行当做一个字符串，$A*B$矩阵每一行的hash值是可以$O(n^2)$得到的，这样就AC了。

看到大佬都是随机构造一个$1*n$的$X$矩阵做的，只要检查$X*A*B$是否等于$X*C$即可，膜。

#include <bits/stdc++.h>

using namespace std;

long long mod = 1e9 + 7;

const int maxn = 1100;

long long a[3][maxn][maxn];

long long r[3][maxn][maxn];

long long base = 131LL;

int n;

int main() {

  scanf("%d", &n);

  for(int t = 0; t < 3; t ++) {

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

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

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

        r[t][i][j] = (r[t][i][j - 1] * base % mod + a[t][i][j]) % mod;

      }

    }

  }

  int fail = 0;

  // 检查每一行的 hash 值

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

    long long A = 0;

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

      long long B = a[0][i][k] * r[1][k][n] % mod;

      A = (A + B) % mod;

    }

    if(A != r[2][i][n]) fail = 1;

  }

  if(fail) printf("NO\n");

  else printf("YES\n");

  return 0;

}

J - Catch the Monster

还在做。

K - Competitions

区间按右端点排序，然后就可以$dp$了，中间要二分一个位置$p$，只有位置$[1,p]$是可以转移到位置$i$的状态的。

#include <bits/stdc++.h>

using namespace std;

const int maxn = 2e5 + 10;

struct X {

  int id;

  int L, R;

  long long c;

}s[maxn];

int n;

int pre[maxn];

int wei[maxn];

long long fen[maxn];

long long tim[maxn];

vector<int> use;

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

  return a.R < b.R;

}

void up(long long x, long long y, int idx) {

  if(x > fen[idx - 1] || (x == fen[idx - 1] && y < tim[idx - 1])) {

    fen[idx] = x;

    tim[idx] = y;

    wei[idx] = idx;

  } else {

    fen[idx] = fen[idx - 1];

    tim[idx] = tim[idx - 1];

    wei[idx] = wei[idx - 1];

  }

}

int main() {

  scanf("%d", &n);

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

    pre[i] = -1;

    scanf("%d%d%lld", &s[i].L, &s[i].R, &s[i].c);

    s[i].id = i;

  }

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

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

    int L = 1, R = i - 1, pos = -1;

    while(L <= R) {

      int mid = (L + R) / 2;

      if(s[mid].R > s[i].L) R = mid - 1;

      else pos = mid, L = mid + 1;

    }

    if(pos == -1) {

      long long now_fen = s[i].c;

      long long now_tim = s[i].R - s[i].L;

      if(i == 1) {

        wei[i] = 1;

        fen[i] = now_fen;

        tim[i] = now_tim;

      } else {

        up(now_fen, now_tim, i);

      }

    } else {

      long long now_fen = s[i].c + fen[pos];

      long long now_tim = s[i].R - s[i].L + tim[pos];

      pre[i] = wei[pos];

      up(now_fen, now_tim, i);

    }

  }

  long long ans_fen = 0;

  long long ans_tim = 0;

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

    if(fen[i] > ans_fen) {

      ans_fen = fen[i];

      ans_tim = tim[i];

    } else if(fen[i] == ans_fen) {

      ans_tim = min(ans_tim, tim[i]);

    }

  }

  int last = -1;

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

    if(fen[i] == ans_fen && tim[i] == ans_tim) {

      last = i;

      break;

    }

  }

  while(last != -1) {

    use.push_back(last);

    last = pre[last];

  }

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

    use[i] = s[use[i]].id;

  }

  sort(use.begin(), use.end());

  printf("%d %lld %lld\n", use.size(), ans_fen, ans_tim);

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

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

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

    else printf("\n");

  }

  return 0;

}

L - High Probability Cast

区间按$L$排序，$L$相同的只保留$R$最大的那个。

然后一个一个区间加入，加入第$i$个区间的时候，比$Li$小的那些位置不需要考虑了，概率肯定是100%。

只需考虑比$Li$大的那些位置，画画图可以发现是在维护一个斜率递减的图形。

#include <bits/stdc++.h>

using namespace std;

const double height = 2e9;

const double eps = 1e-8;

const int maxn = 2e5 + 10;

struct X {

  double L, R;

  double nowL, nowR;

  int id;

}s[maxn];

stack<int> st;

vector<int> vec;

int n;

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

  if(fabs(a.L - b.L) < eps) return a.R > b.R;

  return a.L < b.L;

}

double work(double x, int id) {

  return (s[id].R - x) * height / (s[id].R - s[id].L);

}

int main() {

  scanf("%d", &n);

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

    scanf("%lf%lf", &s[i].L, &s[i].R);

    s[i].nowL = s[i].L;

    s[i].nowR = s[i].R;

    s[i].id = i + 1;

  }

  sort(s, s + n, cmp);

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

    if(st.empty()) {

      st.push(i);

      continue;

    }

    if(fabs(s[i].L - s[i - 1].L) < eps) {

      continue;

    }

    while(!st.empty()) {

      int id = st.top();

      double xL = max(s[id].nowL, s[i].nowL);

      double xR = min(s[id].nowR, s[i].nowR);

      if(xR < xL) {

        st.pop();

        continue;

      }

      if(work(xL, id) <= work(xL, i) + eps

         && work(xR, id) <= work(xR, i) + eps) {

        st.pop();

      } else {

        double left = xL, right = xR, pos;

        int limit = 50;

        while(limit --) {

          pos = (left + right) / 2;

          if(work(pos, id) < work(pos, i)) left = pos;

          else right = pos;

        }

        s[i].nowR = pos;

        s[id].nowL = pos;

        break;

      }

    }

    st.push(i);

  }

  while(!st.empty()) {

    vec.push_back(st.top());

    st.pop();

  }

  int Q;

  scanf("%d", &Q);

  while(Q --) {

    double x;

    scanf("%lf", &x);

    if(x <= s[vec[0]].nowL + eps) {

      printf("%d\n", s[vec[0]].id);

      continue;

    }

    int left = 0, right = vec.size() - 1, ans = -1;

    while(left <= right) {

      int mid = (left + right) / 2;

      if(x < s[vec[mid]].nowL) right = mid - 1;

      else ans = mid, left = mid + 1;

    }

    if(ans == -1) ans = 0;

    printf("%d\n", s[vec[ans]].id);

  }

  return 0;

}

M - Last Man Standing

每次让一个$a_i$为$0$的分配给一个$a_j$不为$0$的人，然后$a_j$就可以减去$1$，一直这样操作。

#include <bits/stdc++.h>

using namespace std;

const int maxn = 200000 + 10;

int n;

int a[maxn];

queue<int> q;

int ans[maxn];

int main() {

  scanf("%d", &n);

  int now = -1;

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

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

    if(a[i]) now = i;

    if(a[i] == 0) q.push(i);

  }

  if(now == -1) {

    printf("YES\n");

    return 0;

  }

  int fail = 0;

  while(now) {

    if(q.empty()) {

      fail = 1;

      break;

    }

    int f = q.front();

    q.pop();

    ans[f] = now;

    a[now] --;

    if(a[now] == 0) {

      q.push(now);

      now --;

    }

  }

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

    if(a[i]) fail = 1;

  }

  if(fail) printf("NO\n");

  else {

    printf("YES\n");

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

      if(ans[i])

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

    }

  }

  return 0;

}

巴特西

2017, X Samara Regional Intercollegiate Programming Contest 题解

最新文章

热门文章