- 总结：菜就多练。还是要少刷水题，多学知识才好成长，水题写多了只有签到的速度快了，但上限依旧低。
A
800 —— 思维，简单博弈
题意
两人游戏。给定一个整数 n。操作为给整数+1或者-1，如果操作后的整数能被 3 整除，那么操作的人获胜。
解题思路
一眼题。除非开始就能被 3 整除，否则先手必胜。因为余 1，余 2 的情况先手都只需要操作一步即可。
(感觉自己越来越会蒙了？上手全凭直觉。唉唉… 赛事用了两分钟，然后开始坐牢)
代码
#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 = 1e6 + 10;
int n, m;
void solve()
{
cin >> n;
if (n % 3 != 0) cout << "First" << endl;
else cout << "Second" << endl;
}
int main()
{
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int t; cin >> t; while (t -- )
solve();
return 0;
}
B
1100 —— 暴力枚举？预处理
题意
给定 n 个箱子，以及每个箱子的重量。需要将箱子转到卡车上，保证每个卡车上都正好放 k 个箱子，k的取值1 ~ n。
问任意两辆卡车总重量的最大差值
解题思路
直接暴力肯定是超时的了。所以我们预处理出 n 的所有因子，然后开始暴力()。
对于每个因子 t ，也就是可以把 n 个箱子装到 n / t 辆卡车上，次数，我们把所有的重量存入，然后排序。就可以求出对于因子 t 的最大差值。对于每一个因子求最大差值，最后结果也就是最大差值。
悲报，以为初始箱子可以排序，样例一测，错了}。(赛事28分钟过的，难道我真的这么菜？沃趣，真的这么菜。)
代码
#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 = 150010;
int n, m;
ll a[N];
ll s[N];
void solve()
{
cin >> n;
for (int i = 1; i <= n; i ++ ) cin >> a[i];
//预处理前缀和
for (int i = 1; i <= n; i ++ ) s[i] = a[i] + s[i - 1];
//预处理因子
vector<int> c;
c.pb(1); c.pb(n);
for (int i = 2; i <= n / i; i ++ )
{
if (n % i == 0)
{
c.pb(i);
if (i * i != n) c.pb(n / i);
}
}
//遍历每一个因子
ll mx = 0;
for (auto t : c)
{
//每个因子下的每个卡车的重量
vector<ll> f;
for (int i = t; i <= n; i += t)
{
ll x = abs(s[i] - s[i - t]);
f.pb(x);
}
if (t == n) continue;
//排序，然后取最大差值
sort(f.begin(), f.end());
ll now = f.back() - f.front();
//更新最大值
mx = max(mx, now);
}
cout << mx << endl;
}
int main()
{
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int t; cin >> t; while (t -- )
solve();
return 0;
}
C
1100 —— 简单DP
题意
给定 n 个元素组成的数组 a，需要求出非空子数组最大值。要求子数组种不能有相邻的数拥有相同的奇偶性。
解题思路
都说是一眼题，简单DP。但我是DP低手？不，我是DP无能选手。DP方面真的跟小白一样，或许本身就是小白。唉，唉唉。
我是怎么想的呢，预处理出来每个断点，也就是相邻数相同奇偶性的点。然后预处理出来每个负数的点。可现实总是残酷的。如何考虑覆盖多少负数，如果每次在区间内的每个负数都要考虑覆盖，那无疑就太麻烦了。而这是B，或许说应该是比较好想的才对。然后，remake了。
DP的表示就是 以 i 为结尾的子序列的最大和，状态转移方程为：$dp[i] = max(a[i], dp[i - 1] + a[i])$ ，也就是要么继续连续，要么就重新连续。只需要加特判可不可以连续即可。
D了多久呢，赛事1时18分，从思路错误到转写dp，坐牢50分钟，而且还不是自己做出来的。唉，唉唉。DP低手。该练练了。(一个DP每开出过)
代码
#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;
int a[N];
//dp[i]是以i结尾子序列的最大和
int dp[N];
void solve()
{
cin >> n;
int flag = false;
//先处理出来单个数的最大值
int mx = -0x3f3f3f3f;
for (int i = 1; i <= n; i ++ )
{
cin >> a[i];
mx = max(a[i], mx);
if (a[i] > 0) flag = true;
}
//如果全是负数，那就直接输出最大值即可。
if (flag == false)
{
cout << mx << endl;
return ;
}
//初始化dp[1] = (0, a[1])
dp[1] = max(0, a[1]);
for (int i = 2; i <= n; i ++ )
{
//如果不能连续，那就考虑重新连续。
if (abs(a[i]) % 2 == abs(a[i - 1]) % 2) dp[i] = max(0, a[i]);
//状态转移
else dp[i] = max(a[i], dp[i - 1] + a[i]);
//更新最大值
mx = max(mx, dp[i]);
}
cout << mx << endl;
}
int main()
{
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int t; cin >> t; while (t -- )
solve();
return 0;
}
D
1300 —— 数论？思维？白给！
题意
总结下来，就是有 n 个音符，给出每个音符代表的数字 $a_i$ ，那么音符 i 就是 $b_i = 2^{a_i}$ ，现在要求有多少对音符$b_i,b_j (i<j)$ ，组合($b_i, b_j$) = ($b_j,b_i$)，组合($b_i,b_j$) = $b_i^{b_j}$。找到有多少对这样的音符。
解题思路
感觉题面很牛马… 写一下就可以发现只有 i,j = 1,2的时候是特殊条件，其他情况下只有 i == j，才满足组合条件。
怎么说呢，题有一，错误有二()，第一个错误是计算错了，导致一直以为不止一个特殊条件，然后陷入自我怀疑? 第二个错误是没有看见 j < i，然后怀疑起了样例？迷之自信。唉，唉唉。(靠外力赛事1时58分，坐牢40分钟，其实这种题能想这么久，也是一种能力？)
代码
#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;
int a[N];
void solve()
{
cin >> n;
map<int,int> mp;
for (int i = 0; i < n; i ++ )
{
cin >> a[i];
mp[a[i]] ++ ;
}
ll sum = 0;
//因为i < j,所以......
for (int i = 0; i < n; i ++ )
{
mp[a[i]] -- ;
if (a[i] == 1 || a[i] == 2)
{
sum += mp[1] + mp[2];
}
else sum += 1ll * mp[a[i]];
}
cout << sum << endl;
}
int main()
{
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int t; cin >> t; while (t -- )
solve();
return 0;
}
E
1300—— 贪心？
题意
一个由 n 个数组成的数组 a，需要通过操作变成升序排列。
每次操作：将第一个元素放入末尾，然后将这个元素与前一个元素对调，直到他严格大于前一个元素。
需要找出最小操作次数
解题思路
如果操作最小的数，那么操作就会无效，因为对原数组没有影响。
所以需要保证最小的数后面的序列是升序排列，才可能完成整个数组的排序。而最小的操作次数，也就是最小的数前面的数每个数都操作一次即可。
怎么评价呢，赛后写的，感觉比BCD简单多了……，可能直觉? 给我带来迷之自信。
代码
#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;
int a[N];
void solve()
{
cin >> n;
//idx表示第一个最小值下标
int mi = 0x3f3f3f3f, idx = 0;
for (int i = 0; i < n; i ++ )
{
cin >> a[i];
if (a[i] < mi) mi = a[i], idx = i;
}
//判断最小值后面的数是不是升序排列
bool flag = true;
for (int i = idx; i < n - 1; i ++ )
if (a[i + 1] < a[i]) flag = false;
if (flag == false)
{
cout << -1 << endl;
return ;
}
cout << idx << endl;
}
int main()
{
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int t; cin >> t; while (t -- )
solve();
return 0;
}
F
1600 —— 构造
题意
给定一个 n 个顶点的树，有n - 1条边。树中的两个顶点的距离是两个顶点所经过的边数。
有 q 天，每一天会选择一个距离 d，需要保证这一天有两个距离正好为 d 的叶子。
为了保证每一天都有那个距离，给定一个操作：选择三个点 $u,v_1,v_2$，需要保证 $u,v_1$ 有一条边，$u,v_2$ ，没有边。操作就是删除 $u,v_1$，的边，连接 $u, v_2$ 的边。
保证满足条件的树和操作序列总是存在的。
解题思路
先不谈正解，这个破样例就看了半天。然后样例也不懂，就润了。但不得不说，构造的方法很妙，但感觉有点经典。可我又想不到……
正解：初始将所有点连成一条链，每次操作去改变节点 1 的位置，然后记录节点 1 所连的节点，长度记录为节点 1 到 最后一个点的位置。对于每次询问，我们只需要去改变节点 1 的位置，或者不改变，就可以满足长度 d。
感觉记录节点 1 到所连接的节点位置 i 比较好理解，长度就是 i - 1，画个图就明白了。可这样有点bug，所以倒着来，记录节点 1 到尾节点的位置就不会有bug。
代码
#include <bits/stdc++.h>
using namespace std;
void solve()
{
int n, m;
cin >> n >> m;
for (int i = 1; i < n; i ++ ) cout << i << " " << i + 1 << endl;
//初始连接的节点2
int v = 2;
while (m -- )
{
int x;
cin >> x;
int len = (n - v) + 1;
if (len == x)
{
cout << "-1 -1 -1\n";
continue;
}
else cout << 1 << " " << v << " " << n - x + 1 << endl;
v = n - x + 1;
}
}
int main()
{
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int t; cin >> t; while (t -- )
solve();
return 0;
}
