题解

前言

本次比赛题目都比较基础，没有涉及什么算法，数据造的比较水，验题也只找了几个人验，可能题意有些有点歧义，给选手造成了不好的比赛体验先磕一个谢罪，以下是这次的题解。标程提供c++代码，其他语言应该也差不多，不会出现卡时间的情况（）难度预估（D,A<C,E,F<B）

A、Alice和Bob的第一次博弈

思路

很显然，我们贪心的想可以发现，只要Alice先将自己能得到的糖果全都往前放，就一定能保证结果最优（如果不能赢真的就没辙了），所以我们只要先计算偶数糖果总和再减去奇数糖果，结果如果是正就是可以，否则不行。

代码

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define fi first
#define sc second
using namespace std;
const int INF = 0x3f3f3f3f3f3f3f3f;
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
typedef pair<int, int> PII;
int n;
int a[N];
void solve() {
  cin >> n;
  int ss = 0;
  for (int i = 1; i <= n; i++) {
    int x;
    cin >> x;
    if (x % 2) {
      ss -= x;
    } else
      ss += x;
  }
  if (ss > 0)
    cout << "YES\n";
  else
    cout << "NO\n";
}

B、01博弈

思路

小学奥数题，想法很简单，我们可以发现，可以保证在一轮（两个人各取一次）操作后，石子共减少 $k + 1$ 个，于是，我们不难得出，假如给定的 $n$ 对 $k + 1$ 取模是0，则先手一定会输（后手永远取 $k + 1 - p$ 个）；反之，先手第一次取个，后手就必输。注意数据范围是需要开long long

代码

#include <iostream>
using namespace std;
int main() {
  long long a, b;
  cin >> a >> b;
  if (a % (b + 1))
    cout << "ALICE WIN\n";
  else
    cout << "BOB WIN\n";
}

C、音乐谜题

思路

我们可以先遍历一遍字符串，将所有可能出现的长度为2的子字符串全部存起来，最后直接看需要多少就可以了。

代码

#include <bits/stdc++.h>
using namespace std;
int main() {
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    string s;
    cin >> s;
    set<string> st;
    for (int i = 1; s[i]; i++) {
      string tmp;
      tmp = tmp + s[i - 1] + s[i];
      st.insert(tmp);
    }
    cout << st.size() << "\n";
  }
}

D、缪尔赛思的唇膏

思路

本来是想出一个给定起点终点的DFS/BFS搜索问题的，后来觉得难度可能略大改为了直接搜索目标，语法题，直接判断每次输入即可。

代码

#include <iostream>
using namespace std;
int main() {
  int n, m;
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      char x;
      cin >> x;
      if (x == 'D') cout << i << " " << j << "\n";
    }
  }
}

E、翻转括号

思路

一个经典判括号合法性问题的变种，相比于正常判断，再reverse判断一遍即可，可以拿stack写也可以不用直接记录"("的数量，然后保证其一直大于等于0即可。

代码

#include <bits/stdc++.h>
using namespace std;
int judge(string s) {
  int cnt = 0;
  for (char x : s) {
    if (x == '(')
      cnt++;
    else
      cnt--;
    if (cnt < 0) return 0;
  }
  if (cnt == 0)
    return 1;
  else
    return 0;
}
int main() {
  int T;
  cin >> T;
  while (T--) {
    int n;
    cin >> n;
    string s;
    cin >> s;
    int ok = 0;
    ok |= judge(s);
    for (char& x : s) {
      if (x == '(') {
        x = ')';
      } else {
        x = '(';
      }
    }
    ok |= judge(s);
    if (ok == 0) {
      cout << "NO\n";
    } else {
      cout << "YES\n";
    }
  }
  return 0;
}

F、操场排列

思路

不难发现，其实就是一个全排列问题，通过排列组合计数的方式，我们可以得到结果为，注意由于数据会很大，所以我们需要对该数进行取模（不用担心错误答案也能AC，对大质数取模相当于hash，能 AC全部测试样例只能说吃点好的吧）

代码

#include <iostream>
using namespace std;
int main() {
  int t;
  cin >> t;
  long long res = 1;
  for (int i = 1; i <= t; i++) {
    res = res * i % 1000000007;
  }
  cout << res << "\n";
}

题解

题解

前言