先给出比赛链接：
https://ac.nowcoder.com/acm/contest/91452
下面说一下难度分层：(同一难度下按字典序排序)
Easy(简单): B, F
Medium(中等): A, E, H
Hard(困难): C, G
Anti-AK(防AK): D, I
cin.tie(nullptr)->sync_with_stdio(false); / /加速输入输出的
A 游游的整数翻转
将所给数前k位进行翻转即可，注意要去掉前导0
我的做法是根据k切片，前一块转成int类型自动去前导0（只有数字小到能够用int表示才能这样）
Show Code A
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
string s;
int k;
cin >> s >> k;
string s1 = s.substr(0, k), s2 = s.substr(k); // 切片，详见ACM notes博客
reverse(s1.begin(), s1.end()); // 翻转字符串
int ans1 = stoi(s1); // stoi可以把string转成int，此处用于int自动去前导零
cout << ans1 << s2 << "\n";
}
B 困难数学题
先介绍一下异或的性质
异或及其性质
异或在C++中的运算符是 ^ (Shift + 6)
异或可以理解为按位不进位加法
1.异或的逆运算就是异或本身 如果 a $ \otimes $ b = c ，那么 c $ \otimes $ b = a
2.异或满足交换律 即 a $ \otimes $ b == b $ \otimes $ a
3.异或满足结合律 即 (a $ \otimes $ b) $ \otimes $ c == a $ \otimes $ (b $ \otimes $ c)
4.异或满足分配律 即 a $ \otimes $ (b & c) == (a $ \otimes $ b) & (a $ \otimes $ c)
对于普通加法可以用高斯定律 sn = (1 + n) * n / 2 快速计算1~n的值
对于异或运算来说也有快速计算1~n各数的异或和的方法，即：
异或前缀和
\( s(n)为1到n的数的异或和 \)
\( s(n) = \begin{cases} 1 , ~~~ n \% 4 == 1 \\ 0 , ~~~ n \% 4 == 3 \\ n , ~~~ n \% 4 == 0 \\ n + 1 , ~~~ n \% 4 == 2 \\ \end{cases} \)
代码实现如下：
auto xorprefix = [&](ll n) {
int flag = n % 4;
if (flag == 0) {
return n;
} else if (flag == 1) {
return 1;
} else if (flag == 2) {
return n + 1;
} else if (flag == 3) {
return 0;
}
};
根据异或的性质，我们可以知道 a xor a = 0
那么 a xor a xor a xor a = 0
所以直接输出0即可
Show Code B
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
cout << 0 << "\n";
}
C
用二分找到第一个比x小的完全平方数，由于x只能+2或者-2，根据x和二分到的完全平方数的奇偶性得到与x最接近的完全平方数再求值即可
Show Code C
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
ll n;
cin >> n;
auto check = [&](ll x) {
if (x * x >= n) {
return 1;
} else {
return 0;
}
};
ll l = 1, r = 2000000;
while (l <= r) {
ll mid = (l + r) >> 1;
if (check(mid)) {
r = mid - 1;
} else {
l = mid + 1;
}
}
ll ans = inf, cur;
if (r % 2 != n % 2) r--;
cur = abs(r * r - n) / 2ll;
ans = min(ans, cur);
r += 2;
cur = abs(r * r - n) / 2ll;
ans = min(ans, cur);
cout << ans << "\n";
}
E
输出1到n之间所有的回文数
直接暴力遍历，对每个数判断是否是回文数即可
复杂度 $ O(nlg(n)) $
Show Code E
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n;
cin >> n;
for (int i = 1; i <= n; ++ i) {
string cur = to_string(i);
string recur = cur;
reverse(recur.begin(), recur.end());
if (cur == recur) {
cout << cur << "\n";
}
}
}
F
把六个数加起来输出即可
Show Code F
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n = 6;
int ans = 0;
for (int i = 1; i <= n; ++ i) {
int cur;
cin >> cur;
ans += cur;
}
cout << ans << "\n";
}
G
打表可以发现答案只可能是0.5
下证充分性：
根据古典概型
总共有 $ (n + 1) * (n + 2) $ 种情况
总共有小红正面多的情况有 $ (n + 1) * (n + 2) / 2 $ 种
除一下可知答案恒定为0.5
Show Code G
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
cout << "0.500000" << "\n";
}
H
根据题目模拟即可
注意到当 a 和 k 都是偶数的时候，所有项都是偶数
当 k 是偶数的时候，所有项都和a的奇偶性相同
当 k 是奇数的时候，根据 a 和 区间的长度 len 就能知道哪种数多了
Show Code H
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
ll a, k, q;
cin >> a >> k >> q;
if (k & 1) {
while (q--) {
ll l, r;
cin >> l >> r;
ll len = r - l + 1ll;
if (len & 1) {
// 注意下面的if里面直接算由于数字太大会爆ll，所以除2取模只计算奇偶性
if ((a % 2 + (l - 1ll) % 2 * k % 2) & 1) {
cout << 1 << "\n";
} else {
cout << -1 << "\n";
}
} else {
cout << 0 << "\n";
}
}
} else {
if (a & 1) {
while (q--) cout << 1 << "\n";
} else {
while (q--) cout << -1 << "\n";
}
}
}
I
数论整除分块板子题（新生别看）
标签：ZZJC,新生训练,int,题解,ll,cin,异或,tie,otimes From： https://www.cnblogs.com/Proaes/p/18436495