A 智乃的博弈游戏

题意

有一堆$n$个石子，每次可以拿走$x$个石子，要求$x$是一个不大于$n$且与$n$互质的数，当面对$1$时选手获胜，询问智乃（先手玩家）能否获胜。

数据范围

• $1\leq n\leq 1e18$

思路

必胜点是剩余 1，则 2 是必败点，两个选手都不希望对手面对 1，都希望对手面对 2。

如果当前剩余$n$是奇数，则选手一定可以操作将剩余数量变成偶数（只拿一个）。面对偶数的选手，能选的互质的数一定是一个奇数，偶数减去奇数会变成奇数，下一轮回到奇数的情况，如果某一方保持偶数，一定会到剩余$2$的情况，也就是必败点。

A 一起奏响历史之音！

题意

中国传统五声调中包含 1、2、3、5、6，判断一个乐谱是否仅由全部或部分五声调铺成。

思路

按题意判断即可。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

void solve() {
  bool flag = true;
  set<ll> st = {1, 2, 3, 5, 6};
  ll x;
  while (cin >> x) {
    if (st.find(x) == st.end()) {
      flag = false;
    }
  }
  if (flag) {
    cout << "YES\n";
  } else {
    cout << "NO\n";
  }
}

B 能去你家蹭口饭吃吗

题意

给出一个数组$a$，找到一个整数，要求整数尽可能大，但是至少要比数组中一半数量的数小。

A 茕茕孑立之影

题意

找一个不超过$1e18$的数$x$，使得$x$既不是任何$a_i$的倍数，也不是任何$a_i$的因数。若没有输出$-1$。

数据范围

• $1\leq n\leq 1e5$
• $1\leq a_i\leq 1e9$

思路

观察到，如果数组中有$1$则不存在这样的数。

$1\leq a_i\leq 1e9$，而$1\leq x\leq 1e18$，有解时任意数=输出一个大于$1e9$的质数即可。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

void solve() {
  ll n;
  cin >> n;
  for (ll i = 1; i <= n; i++) {
    cin >> a[i];
  }
  sort(a + 1, a + 1 + n);
  if (a[1] == 1) {
    cout << "-1\n";
  } else {
    cout << "100000007\n";
  }
}

B 一气贯通之刃

题意

给一棵树，寻找一条简单路径，使之遍历树上所有的顶点，输出起点和终点。如果没有这样的解则输出$-1$。

A. Alyona and a Square Jigsaw Puzzle

题意

Alyona按照顺时针围绕第一个拼图放置拼图，Alyona每天会按顺序放置一定数量的拼图，如果一天结束时拼图的组装部分没有任何已开始但未完成的层，Alyona会感到开心。给出每天放置拼图的数量，询问Alyona感到快乐的天数。

数据范围

• $1\leq t\leq 500$
• $1\leq n\leq 100$
• $1\leq a_i\leq 100,a_1=1$

思路

检查每天完成添加拼图时的总拼图数是否恰好是一个奇数的平方数，若是则该天会感到快乐。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

void solve() {
  cin >> n;
  ll tot = 0, ans = 0;
  for (ll i = 1; i <= n; i++) {
    cin >> a[i];
    tot += a[i];
    ld t = sqrtl(tot);
    if ((ll)t & 1 && t == (ll)t) {
      ans++;
    }
  }
  cout << ans << '\n';
}

B. Replace Character

题意

在一个长度为$n$的字符串中，执行一次这样的操作：

• 选择两个索引$i,j(1\leq i,j\leq n)$，可以选择$i = j$。
• 进行赋值$s_i:=s_j$。

要求输出在进行该操作之后，字典序最小的那个字符串。

A. Profitable Interest Rate

题意

有两种储值方式——无利可图和盈利，“盈利”可以保证盈利，但是有最低储值要求，“无利可图”类型没有利息，但是可以让“盈利”的最低储值降低。在“无利可图”储值$x$元，可以让“盈利”的最低值要求降低$2\times x$元，最低储值不能低于$0$元，两种储值均不能取出。现在Alice拥有$a$元，并想使存入“盈利”的金额越多越好，求Alice最多存入多少“盈利”类型的金额。

G. Snake Move

题意

$n\times m$的网格中有一条长度为$k$的贪吃蛇，贪吃蛇支持上下左右移动 1 格的操作，以及缩短 1 个身体长度的操作。

设$f(i,j)$为从蛇头从初始位置到达网格中点$(i,j)$所需要的最少的操作数，网格中不可到达的格子操作数设为$0$，求解输出：