- 总结一下,秒了A,然后BC连续WA。然后就做不下去了|,VP还是差点感觉。
A
800 —— 思维
题意
给定一个长度为 n 的序列 a。给定操作:从$[2, n-1]$ 中选择一个下标 i ,需要保证选择的数严格大于两边的数字,然后交换$a_i和a_{i+1}$ 。问能否在有限次的操作后使得每一个$a_i=i$ 。
解题思路
可能我就是800高手(❌), 可以看出,只要保证第一个数$a_1=1$ 即可,其他的数可以通过操作实现归位。
代码
#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;
int a[N];
void solve()
{
int n;
cin >> n;
for (int i = 1; i <= n; i ++ )
{
cin >> a[i];
}
if (a[1] == 1) cout << "YES" << endl;
else cout << "NO" << endl;
}
int main()
{
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int t; cin >> t; while (t -- )
solve();
return 0;
}
B
900 —— 贪心,字符串
题意
给定一个由 A 和 B 组成的字符串。给定一个操作:选择一个索引 i ,保证 $s_i=A,s_{i+1}=B$ ,然后交换 $s_i$ 和 $s_{i+1}$ 。每个索引只能选择一次。求最多可以操作的次数
解题思路
最开始,我想的是每个B前有多少个A,就是可以操作多少次,没有考虑到每个下标只能操作一次。然后wa2,然后想不出,就去开 c 了。
正解?:找到最左边的A,和最右边的B。然后差值就是最大可操作的次数。证明?不懂怎么证明,贪心不都是靠猜嘛( )
代码
#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;
ll n, m;
void solve()
{
cin >> n;
string s;
cin >> s;
int idx1 = -1, idx2 = -1;
for (int i = 0; i < s.size(); i ++ )
{
if (s[i] == 'A')
{
idx1 = i;
break;
}
}
for (int i = 0; i < s.size(); i ++ )
{
if (s[i] == 'B')
{
idx2 = i;
}
}
//如果全是A或者全是B
if (idx1 == -1 || idx2 == -1) cout << 0 << endl;
//注意不能取负值,最小操作次数是0
else cout << max(idx2 - idx1, 0) << endl;
}
int main()
{
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int t; cin >> t; while (t -- )
solve();
return 0;
}
C
1400 —— 贪心,排序
- 开不出B,那我开C,笑死,C也wa2
题意
给定两个大小为 n 的数组 a 和 b。有一处 $a_i>b_i$ ,就是一个妙处。现在给定一个整数 x ,需要判断通过重新排列 b 中的元素,使得正好有 x 个妙处。 如果可能,需要输出一种 b 的有效重排方式。
解题思路
贪心的想,让 b 中 最小的 x 个数与 a 中最大的 x 个数去比较;b 中最大的 n-x 个数与 a 中 最小的 n-x 个数去比较就可以。
但我犯了一个错误:因为比较需要,a数组也进行了排列,可实际上输出排列后的 b 数组应该对应原来 a 数组的位置,因为a 数组原则上是不能排列的。其实只需要再开一个下标数组根据 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;
}
D
1700 —— 区间维护?
- 理所应当?的没有看到连续子区间,然后以为很简单,最终样例都没过
题意
给定一个长度为 n 由 1 和 2 组成的数组 a。查询 q 次,有两种查询:1 s,检查有没有子数组总和等于 s;2 i v,将 $a_i$ 的值改为 v。
解题思路
发现是要求连续子区间后,就无从下手了。可实际上并不难 111111。
状态只有四种:
- $[1…1]$
- [1…2]
- [2…1]
- [2…2]
假定现在和为 sum,那么我们一定可以得到 sum - 2 的值,也就是只要现在的和 sum 和查询的和 s 的差值为偶数,那么一定存在。如果是奇数,我们只需要删掉一个 1,就可以得到第一种状态。所以我们需要维护的就是头部的第一个 1 的位置,和尾部的第一个 1 的位置就可以。因为 1 之前的数都是 2,所以我们可以知道去掉的值是多少 (感觉这一步比较关键,写的时候也都想到了,但没有想到第一个 1 之前全是 2,所以没想通如何维护) 。
采用 set 来维护
代码
#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 = 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;
}
E
2100 —— 数据结构,树状数组
扔一个题目链接。总的来说用树状数组维护单点修改和实现区间查询。没学过树状数组,然后看了很久。大概明白了题解的含义,可也只是大概了。等之后学了再来补档。写了3天,vp了三场,学到了很多,也充分了解到自己的不足。刷题的同时,还是不能扔下学习了。没有基础的奠定,不能上分,向下补题会很难。
代码
#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;
int a[N], ans[N], c[N << 1];
void add(int x, int k)
{
for (; x <= n << 1; x += x & -x) c[x] += k;
}
int ask(int x)
{
int ans = 0;
for (; x; x -= x & -x) ans += c[x];
return ans;
}
//利用树状数组维护单点修改和实现区间查询
//将数组拆环。
void solve()
{
cin >> n;
memset(c, 0, sizeof(int) * n << 1);
vector<PII> e;
for (int i = 1; i <= n; i ++ )
{
cin >> a[i];
if (i <= a[i])
{
e.pb({i, a[i]});
e.pb({i + n, a[i] + n});
}
else e.pb({i, a[i] + n});
}
sort(e.begin(), e.end(), greater<PII>());
for (auto [l,r] : e)
{
if (l <= n) ans[a[l]] = r - l - ask(r) + ask(l - 1);
add(r, 1);
}
for (int i = 1; i <= n; i ++ ) cout << ans[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;
}