A
—— 实现
题意
给定三个整数，需要判断在这三个数中是否存在两个数的和大于等于148。
解题思路
将三个数中两个最大的数相加，然后判断是否大于等于148即可。
代码
#include <iostream>
using namespace std;
void solve()
{
int a[3];
for (int i = 0; i < 3; i ++ ) cin >> a[i];
sort(a, a + 3);
if (a[1] + a[2] >= 148) cout << "YES" << endl;
else cout << "NO" << endl;
}
int main()
{
int t; cin >> t; while (t -- )
solve();
return 0;
}B
—— 思维，简单数论
题意
给定一个正整数 n ，需要找到两个正整数 $a, b(1 \le a < b \le n)$ ，使得 gcd(a, b) 尽可能大。只需要输出最大的 gcd(a, b)。
解题思路
一般来说，对于一个数 x ，他一定有因子 1 和 x，除此之外，他的最大可能因子就是 n / 2。
因为 a != b ，所以 gcd(a, b) 不可能取到 n ，我们就考虑取 n / 2 的情况。
- n 为偶数，那么gcd(n, n / 2) == n / 2
- n 为奇数，那么gcd(n - 1, n / 2) == n / 2
代码
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
void solve()
{
int n;
cin >> n;
if (n % 2 == 1) cout << __gcd(n - 1, n / 2) << endl;
else cout << __gcd(n, n / 2) << endl;
}
int main()
{
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int t; cin >> t; while (t -- )
solve();
return 0;
}C
—— 二分图匹配
题意
给定一个集合，现在需要选择一个元素最多的子集满足以下条件：对于子集中的任意两个元素 $a_i,a_j$ 均满足 $gcd(a_i,a_j)*gcd(a_i + 1, a_j + 1) \neq 1$ 。
解题思路
$gcd(a_i,a_j)*gcd(a_i + 1, a_j + 1)$ 我们分为三种情况：
- $a_i,aj$ 都是偶数，那么$gcd(a_i,a_j)$ 最小的可能值是 2，此时 $gcd(a_i,a_j)*gcd(a_i + 1, a_j + 1) \neq 1$
- $a_i,a_j$ 都是奇数，那么$gcd(a_i+1, a_j+1)$ 最小的可能值就是 2，此时 $gcd(a_i,a_j)*gcd(a_i + 1, a_j + 1) \neq 1$
- $a_i,a_j$ 奇偶性不同，此时就不一定满足条件。
可以发现，不满足条件的元素相对较少，也就是不在最大子集中的元素较少。
此时，我们将奇偶不同且不满足条件的元素看作点，连边。用匈牙利算法进行二分图匹配，结果就是 n - 二分图的最大匹配
代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
#define endl '\n'
typedef long long ll;
const int N = 510, M = 1e5 + 10;
int n, m;
ll a[N];
ll e[M], ne[M];
int h[N], idx;
int match[M];
bool st[M];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
bool find(int u)
{
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if (!st[j])
{
st[j] = true;
if (match[j] == 0 || find(match[j]))
{
match[j] = u;
return true;
}
}
}
return false;
}
int main()
{
memset(h, -1, sizeof h);
cin >> n;
for (int i = 1; i <= n; i ++ ) cin >> a[i];
for (int i = 1; i <= n; i ++ )
{
if (a[i] & 1) continue;
for (int j = 1; j <= n; j ++ )
{
if (!(a[j] & 1)) continue;
if (__gcd(a[i], a[j]) * __gcd(a[i] + 1, a[j] + 1) == 1)
add(i, j);
}
}
int cnt = 0;
for (int i = 1; i <= n; i ++ )
{
memset(st, false, sizeof st);
if (find(i)) cnt ++ ;
}
cout << n - cnt << endl;
return 0;
}D
题意
给定两个大小为 n 的数组 a 和 b。有一处 $a_i>b_i$ ，就是一个优雅值。现在给定一个整数 x ，需要判断通过重新排列 b 中的元素，使得优雅值正好是 $x$ 。 如果可能，需要输出一种 $b$ 的有效重排方式。
解题思路
贪心的想，让 b 中 最小的 x 个数与 a 中最大的 x 个数去比较；b 中最大的 n-x 个数与 a 中 最小的 n-x 个数去比较就可以。
需要注意的是输出排列后的 b 数组应该对应原来 a 数组的位置，因为 a 数组原则上是不能移动的。
代码
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define db double
#define pb push_back
typedef long long ll;
typedef pair<int,int> PII;
const int N = 2e5 + 10;
int n, m;
void solve()
{
int n, x;
cin >> n >> x;
vector<int> a(n + 1), b(n + 1);
for (int i = 1; i <= n; i ++ ) cin >> a[i];
for (int i = 1; i <= n; i ++ ) cin >> b[i];
//c存储下标，根据a的大小排序
vector<int> c(n + 1);
iota(c.begin(), c.end(), 0);
sort(c.begin(), c.end(), [&](int i, int j){
return a[i] < a[j];
});
sort(a.begin(), a.end());
sort(b.begin(), b.end());
//cnt存储满足条件的对数,f存储排序后(归为前)的新的b序列
int idx = 1, cnt = 0;
vector<int> f(n + 1);
for (int i = x + 1; i <= n; i ++ )
{
f[idx] = b[i];
if (a[idx ++ ] > b[i]) cnt ++ ;
}
for (int i = 1; i <= x; i ++ )
{
f[idx] = b[i];
if (a[idx ++ ] > b[i]) cnt ++ ;
}
//归位
vector<int> g(n + 1);
for (int i = 1; i <= n; i ++ )
{
//根据i找到对应a原来的下标，也就是c的作用
g[c[i]] = f[i];
}
//如果不能正好满足x个，就是不可以
if (cnt != x)
{
cout << "NO" << endl;
return;
}
cout << "YES" << endl;
//归为后的序列
for (int i = 1; i <= n; i ++ )
{
cout << g[i] << " ";
}
cout << endl;
}
int main()
{
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int t; cin >> t; while (t -- )
solve();
return 0;
}
E
—— 贪心，排序
题意
有 n 个硬币，现在要拿一部分硬币。
需要保证：哪的硬币数量最少，且价值严格大于其余硬币的价值总和。
解题思路
将所有硬币根据价值排序，然后从最大价值开始拿，直到拿的价值严格大于剩余硬币价值即可。
代码
#include <iostream>
using namespace std;
const int N = 1e6 + 10;
int n, m;
int a[N];
void solve()
{
int n;
cin >> n;
int sum = 0;
for (int i = 0; i < n; i ++ )
{
cin >> a[i];
sum += a[i];
}
sort(a, a + n, greater<int>());
int now = 0;
int cnt = 0;
for (int i = 0; i < n; i ++ )
{
cnt ++ ;
now += a[i];
sum -= a[i];
if (now > sum) break;
}
cout << cnt << endl;
}
int main()
{
solve();
return 0;
}F
—— 数据结构 区间维护
题意
给定一个数组 a ，其中的每个元素都是 1 或 2。
然后有 q 次询问，询问分为两种：
- “1 s”：判断是否存在 a 的连续子数组，总和等于 s
- “2 i v” ：将 $a_i$ 改为 v
解题思路
首先数组 a 只有四种状态：
- $[1…1]$
- $[1…2]$
- $[2…1]$
- $[2…2]$
我们将 a 数组的和定为 sum，那么我们一定可以得到 sum - 2 的值。也就是说，如果 sum 和要查询的和 s 的差值 sum - s 为偶数，那么 s 就一定存在。如果是奇数，那么我们只需要删掉一个 1 ，就可以使得 sum - s 变为偶数，变为第一种状态。
最理想的做法就是，尽可能删掉最小的数，来使得 sum - s 变为偶数，也就是删掉头部的第一个 1，或者删掉尾部的第一个 1。因为这两个 1 之前的数都是 2 ，所以我们可以得到删掉的值。
采用 set 来维护 1 的位置。
代码
#include <iostream>
#include <set>
using namespace std;
#define endl '\n'
const int N = 1e5 + 10;
int n, m;
int a[N];
void solve()
{
cin >> n >> m;
//st维护1出现的下标
set<int> st;
int sum = 0;
for (int i = 1; i <= n; i ++ )
{
cin >> a[i];
if (a[i] == 1) st.insert(i);
sum += a[i];
}
while (m -- )
{
int op;
cin >> op;
if (op == 1)
{
int s;
cin >> s;
if (sum == s) cout << "YES" << endl;
else if (sum < s) cout << "NO" << endl;
//sum > s的一般情况：
else
{
//z为差值
int z = sum - s;
//如果差值为偶数，那么一定存在
if (!(z&1)) cout << "YES" << endl;
else if (!st.empty())
{
//删掉头尾1区间的元素，因为1头尾的1之前全是2，所以我们可以找到删除的值
if (z >= (min(*st.begin() - 1, n - *st.rbegin()) << 1) + 1) cout << "YES" << endl;
else cout << "NO" << endl;
}
else cout << "NO" << endl;
}
}
else
{
//更新维护st和sum
int idx, v;
cin >> idx >> v;
if (a[idx] == 1) st.erase(idx);
sum -= a[idx];
a[idx] = v;
sum += a[idx];
if (a[idx] == 1) st.insert(idx);
}
}
}
int main()
{
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int t; cin >> t; while (t -- )
solve();
return 0;
}G
—— 简单博弈
题意
出示给定一个整数 n ，两个玩家轮流操作。
操作为：使当前整数加上 1 或减去 1。如果玩家一操作后整数能被 3 整除，那么他获胜。如果两名玩家共进行10步操作后，玩家一没能获胜，那么玩家二获胜。
解题思路
玩家一的操作分为两种：
- n + 1
- n - 1
无论玩家一如何操作，只要玩家二反着操作，那么就可能保证 n 的范围控制在 $[n - 1, n + 1]$ 。
因为当 n % 3 == 1 或者 n % 3 == 2 时，玩家一第一步操作就能获胜，所以只有满足初始时 n % 3 == 0，玩家二才可以获胜。
代码
#include <iostream>
using namespace std;
int n, m;
void solve()
{
cin >> n;
if (n % 3 != 0) cout << "First" << endl;
else cout << "Second" << endl;
}
int main()
{
int t; cin >> t; while (t -- )
solve();
return 0;
}H
—— 博弈论
题意
两个足够聪明的玩家轮流取石子。初始有 n 个石子，每人每次可以取走1 ~ k 颗石子，最后取完石子的一方获胜。
解题思路
一道很经典的博弈论。
我们可以初始情况分为两种：
- n 为 k + 1 的倍数。假设先手取 x 颗石子，那么后手只需要取 k + 1 - x 颗石子，就可以一直保持 n 为 k + 1 的倍数，此时后手必胜。
- n 不是 k + 1 的倍数。此时先手只需要将 n 变成 k + 1 的倍数，就可以复刻情况 1。变为先手必胜。
代码
#include <iostream>
using namespace std;
#define endl '\n'
void solve()
{
int n, k;
cin >> n >> k;
if (n % (k + 1) != 0) cout << 1 << endl;
else cout << 2 << endl;
}
int main()
{
solve();
return 0;
}
I
—— DP，预处理
题意
给定一个长度为 n 的仅由小写字母组成的字符串 s ，以及 q 次询问。
权值的定义：字符串 s 对于字符 c 的权值，定义为 s 中仅由 c 组成的最长连续子串的长度。
询问：询问形式为 $(m_i,c_i)$ ，表示字符串 s 最多更改$m_i$ 个位置的字符后得到的新字符串 s2 对于 $c_i$ 的最大权值。
解题思路
字符总共只有 26 种，也就是 26 个小写字母，且 $m_i$ 的取值范围也不大，所以我们可以采用预处理的方式，用DP预处出所有可能的询问，然后在 q 次询问中可以以 O(1) 的时间复杂度查询结果。
dp(i, j) 表示的是字母 i 在更改 j 个位置后所能得到的最大权值。预处理的时间复杂度为 O(26n^2) 。
代码
#include <iostream>
using namespace std;
#define endl '\n'
const int N = 1510;
//枚举每个数字，dp[k][cnt]表示字母k可以染色cnt次所能得到的最长连续字符串。
int n, m;
int a[N];
int dp[30][N];
void solve()
{
cin >> n;
string s;
cin >> s;
cin >> m;
for (int i = 0; i < n; i ++) a[i] = s[i] - 'a';
for (int i = 0; i < 26; i ++)
{
for (int j = 0; j < n; j ++)
{
int cnt = 0;
for (int k = j; k >= 0; k --)
{
if (a[k] != i) cnt ++ ;
dp[i][cnt] = max(dp[i][cnt], j - k + 1);
}
}
}
for (int i = 0; i < 26; i ++)
for (int j = 1; j <= n; j ++)
if (dp[i][j] == 0) dp[i][j] = dp[i][j - 1];
while (m --)
{
int x;
cin >> x;
char ch;
cin >> ch;
int y = ch - 'a';
cout << dp[y][x] << endl;
}
}
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
//int t; cin >> t; while (t -- )
solve();
return 0;
}J
—— 模拟
题意
给 n 头牛，编号 1 ~ n。没两头牛之间会有一场对决，有三种结果：没有牛被顶翻，一头牛被顶翻，两头牛都被顶翻。
用 n * n 的矩阵来记录对决的结果。每个结果的值用$A_{ij}$ 表示，$A_{ij}$ 有下面五种取值
- $A_{ij}=-1$ 无意义(不会和对决)
- $A_{ij}=0$ 两头牛都没有被对方顶翻
- $A_{ij}=1$ 牛 i 被顶翻了
- $A_{ij}=2$ 牛 j 被顶翻了
- $A_ij=3$ 牛 i 和牛 j 都被顶翻了
保证$A_ij$ 和 $A_ji$ 的结果对应，也就是两头牛之间只会进行一场对决。
没有被顶翻过的牛被认定为强牛，现在需要求出有多少强牛。
解题思路
一道模拟题。直接枚举n * n 矩阵，对于每一行，就是牛 i 的对决情况，如果没有被顶翻过，那就认定为强牛。
代码
#include <iostream>
#include <set>
using namespace std;
#define endl '\n'
void solve()
{
int n;
cin >> n;
set<int> st;
int cnt = 0;
for (int i = 1; i <= n; i ++ )
{
bool flag = true;
for (int j = 1; j <= n; j ++ )
{
int x;
cin >> x;
if (x == 1 || x == 3) flag = false;
}
if (flag) cnt ++ , st.insert(i);
}
cout << cnt << endl;
for (auto t : st)
cout << t << " ";
}
int main()
{
solve();
return 0;
}
