小白月赛115题解
小白月赛115
出题人钝评：
由于一些深刻的原因变成了七题场。
这场 A-C 可能稍微难了一些。D-F就比较送 (原本都是C-D的位置) ，G 还算是正常小白月赛的 F 难度吧，但是大家数据结构水平都好像很高。
题目平均难度低了一点，但毕竟要做七个题，整体难度应该还算正常(确信)。
赛后update:
小爆炸了，贪心和分讨导致的。应该多一点偏模板的题。
A 过马路
考察分类讨论。
题解
我们可以发现，合法的状态只有 红-> 黄 -> 绿，绿 -> 黄 -> 红，黄-> 红 -> 黄，黄-> 绿 -> 黄。
直接进行分类讨论即可。
代码
#include<bits/stdc++.h>
using namespace std;
int main()
{
int a,b,c;
cin>>a>>b>>c;
if(!a&&(!b||c)){
cout<<"NO"<<endl;
}
else if(a&&(b||a+c!=0)){
cout<<"NO"<<endl;
}
else{
cout<<"YES"<<endl;
}
}
B 一道签到题
考察模拟。
题解
首先记录每个难度的题目有多少道，我们依次判断每个难度的题作为签到题的合法性，如果不低于当前难度 的题的数量大于等于
个，那么我们才能保证选出的题的最低难度是
。
接下来计算当前难度题目作为签到题的最大数量即可。注意答案的上界是 。
代码
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n,m;cin>>n>>m;
map<int,int>mp;
for(int i=1;i<=n;i++){
int x;cin>>x;
mp[x]++;
}
int ans=0,sum=n;
for(auto [a,b]: mp){
if(sum>=m){
ans=max(ans,min(b,m));
}
sum-=b;
}
cout<<ans<<endl;
}
C 命运之弹（Easy Version）
考察暴力，枚举。
题解
由于值域只要有 ，
，所以是支持
的写法通过的。
可以开一个 的数组，我们对
暴力计算后面比他大的数有多少个，即变成它后还需要多少次操作。对于
以前的数，我们只需要记录比初始幸运值大的子弹数。二者相加便是选择当前位置进行变化的所需操作数。取所有位置的最小值即为答案。
代码
#include<bits/stdc++.h>
using namespace std;
int n, m, k, ans, cnt = 1;
const int M = 3e5+10;
int as[M],bs[M];
int vis[110];
int main()
{
cin>>n;
for (int i = 1; i <= n; i++)cin>>as[i];
cin>>m;
while (m--){
int x;cin>>x;
int z=0;
ans=1e9;
for(int i=1;i<=n;i++){
bs[i]=z;
if(as[i]>x)z++;
}
for(int i=n;i>0;i--){
vis[as[i]]++;
int tp=0;
for(int j=as[i]+1;j<=100;j++){
tp+=vis[j];
}
ans=min(ans,tp+bs[i]);
}
cout<<ans<<endl;
}
}
D 操作字符串
考查了数学与贪心。
题解
容易想到，两个字符串之间存在最小公倍字符串的条件是两个字符串存在完全相同的循环节。
所有字符串间都有最小公倍字符串代表这些字符串存在一个相同的循环节，每个字符串的长度是循环节长度的整数倍。
可以发现合法的循环节长度 就是所有字符串长度的最大公约数及它的因子。
最优的循环节长度就是所有字符串长度的最大公约数，易证选择其因子一定是不会更优的。
那么我们可以遍历字符串，得出对于循环节的某一项，此时最多出现的字符的数量。该循环节项所需要修改的最小次数为 “该位总数- 该位目前出现次数最多的字符数量” ，最小总操作数为所有循环节项的最小操作数之和。
标程时间复杂度约：
代码
#include <bits/stdc++.h>
using namespace std;
const int M = 3e5 + 10;
string s[M];
int freq[M][26];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
for (int i = 0; i < n; i++) cin >> s[i];
int len = s[0].size();
for (int i = 0; i < n; i++) len = __gcd(len, (int)s[i].size());
for (int i = 0; i < n; i++) {
for (int j = 0; j < s[i].size(); j++) {
freq[j % len][s[i][j] - 'a']++;
}
}
int ans = 0;
for (int i = 0; i < len; i++) {
int sum = 0, mx = 0;
for (int j = 0; j < 26; j++) {
sum += freq[i][j];
mx = max(mx, freq[i][j]);
}
ans += (sum - mx);
}
cout << ans << endl;
}
E 魔法卷轴
考察思维，贪心。
题解
原本位置比较靠前。但是想不到标程的时候似乎有点过难了。内测和正赛很多选手写了复杂讨论和反悔贪心。
首先，如果两名魔法师最终的关键时间一致，则无解。
由于对魔法师第一次使用卷轴时，关键时间会发生变化。我们可以先判断能否使得关键时间各不相同。同时，尽量使得关键时间节点延后以提供更多的时间进行操作。
可以按时间点从大到小枚举，并贪心地将关键点优先设置为 ,其次才是
。
将关键时间节点贪心分配后，剩下的限制只有操作次数，我们不需要知道每个时间节点进行什么操作，只要到达关键节点时的空余操作数足够即可。
从小到大地枚举时间点需要考虑在当前剩余时间足够时将关键时间设置为 ，否则后面容易使得关键时间点冲突，需要提前考虑空余操作数足够的影响。
标程时间复杂度：
代码
#include <bits/stdc++.h>
#define endl '\n'
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
int main()
{
IOS;
int t;
cin >> t;
while (t--)
{
int n; cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) cin >> a[i];
sort(a.begin(), a.end());
map<int, int> mp;
int flag = 1;
for(int i = n-1; i >= 0; i--) {
int x = a[i]-1;
int y = a[i]+1;
if(mp.find(y)==mp.end()){
mp[y] = 1;
}
else if(mp.find(x)==mp.end()){
mp[x] = 1;
}
else {
flag = 0;
break;
}
}
int sum = 0, now = 0;
for(auto [x,y]: mp) {
sum += x - now;
now = x;
sum -= 2;
if(sum < 0) {
flag = 0;
break;
}
}
cout<< (flag ? "YES" : "NO") << endl;
}
}
F 游戏高手
考点：分类讨论，博弈，图论基础，诈骗
题解
省流版思路：
由于图一定会被选完，总入度出度恒定，所以直接把点的权值设置为 出度 - 入度 接着轮流贪心从大到小选就完了。这个做法适用于简单图。
分类讨论思路：
最后形成的图将会是由若干条链、若干环、若干孤立点组成。
显然，孤立点没有任何克制关系，无论谁选了这个点对答案贡献恒为 。
类似的，我们可以发现无论怎么选择环上的点，它对双方的贡献同样为 。
对于一条链来说，我们可以把链的组成表示为一个字符串，字符串首位为根节点，当字符串形如 这样首字符与尾字符不同时，对于首字符代表玩家的贡献将是
，尾字符代表玩家的贡献将是
。而当字符串形如
这样首字符与尾字符相同时，对双方的贡献为
。即在链中起决定作用的只有首个点与最后一个点，其他点同样可以视为对答案没有影响的孤立点，其中选取了首个点的玩家将占优。可以把链的首节点的权值视为
,把链的尾节点的权值视为
，其他点的权值视为
。本质是一致的。 这三类的点的入度出度关系不相同，可以用记录度数代替图的遍历。
因此，对双方最优的博弈过程是两个玩家按权值从大到小选点。
当链的条数为偶数时，答案只会是 ，先后手选择的点本质一致。
当链的条数为奇数时，答案和先后手选择的 和
点数量有关。
综上，我们可以统计完点的度数后，进行模拟或者分类讨论皆可。
标程时间复杂度
fun fact:
谔谔，这题一开始的版本奇形怪状的，不太能用度数做所以压根没考虑，一开始分类去想的，包括给定图的形态比较特别也是因为这个。
不过相较一般的简单图，目前这个版本迷惑性反而更强，做法更多。硬分奇偶环、孤点数、奇偶链然后开始手玩分讨也是能过的。
现在变得有些诈骗的味道了，看着像是引导选手想复杂，这不是出题人本意。
代码
#include <bits/stdc++.h>
#define ll long long
#define endl '\n'
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
ll n, m, k;
const ll M = 3e5 + 10;
ll du[M];
int main()
{
IOS;
ll t;
cin >> t;
while (t--)
{
cin >> n >> m;
for (ll i = 1; i <= n; i++) du[i] = 0;
for (ll i = 1; i <= m; i++){
ll x, y;
cin >> x >> y;
du[x]++;
du[y]--;
}
ll a=0, b=0;
for (ll i = 1; i <= n; i++){
if(!du[i]){
b++;
}
else if(du[i]==1){
a++;
}
}
if((a%2)&&(b%2==0)){
cout<<1<<endl;
}else{
cout<<0<<endl;
}
}
}
G 命运之弹（hard Version）
考点：数据结构，离线化，双指针，二分
题解
把使用操作二的前后作为两个部分看，变成一个点需要的总操作次数为变成它前需要的操作一次数+变成它之后需要的操作一次数。
tips1:对于所有位置，使用了操作二之后需要操作一的次数是固定的，我们是可以 地进行预处理的。
可以直接使用高深数据结构把所有的位置进行处理，得到变成它之后还需要进行几次操作一。
当然，我们也可以观察发现，对于满足
有
的关键点
才值得我们使用操作二，由于我们变为
后只需要考虑大于
的子弹，而关键点的特性是前面没有比他大的的点，因此我们可以将数组排序后二分或双指针处理大于
的数有多少个即可。
tips2:
现在需要得到对于不同的询问值，变成关键点前需要的操作一次数。
考虑对于所有要询问的值离线，排序后保证其单调性，那么可以对于预处理的点构建线段树等结构记录区间最小值，线段树每个叶子节点代表选择这个关键点变化所需要的总操作次数，叶子节点初始化值为该点使用操作二后需要使用的操作一次数。
对于所有子弹的危险值降序排序，随着询问值的递减，我们可以在线段树上进行区间加法操作，对于要处理的子弹 ，其影响的范围为线段树上对应原数组位置在它之后的关键点，需要进行操作的区间可以通过二分/双指针得出，对区间值
，即这些关键点的所需次数
。
对于每次询问，我们处理到所有危险值大于目前询问值的子弹，处理完成后，对于该次询问，答案为整个线段树的最小值。
标程采取只处理关键点，进行区间加。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
const int MAXN = 2e5 + 10;
struct Node {
int l, r, mn;
ll add = 0;
};
int n, q;
ll as[MAXN];
int vis[MAXN];
pii ask[MAXN];
ll ans[MAXN];
Node tree[MAXN << 2];
vector<pii> poz;
void build(int p, int l, int r) {
tree[p].l = l;
tree[p].r = r;
if (l == r) {
tree[p].mn = poz[l - 1].second;
return;
}
int mid = (l + r) >> 1;
build(p << 1, l, mid);
build(p << 1 | 1, mid + 1, r);
tree[p].mn = min(tree[p << 1].mn, tree[p << 1 | 1].mn);
}
void pushdown(int p) {
if (tree[p].add) {
tree[p << 1].mn += tree[p].add;
tree[p << 1 | 1].mn += tree[p].add;
tree[p << 1].add += tree[p].add;
tree[p << 1 | 1].add += tree[p].add;
tree[p].add = 0;
}
}
void update(int p, int l, int r, ll x) {
if (tree[p].l >= l && tree[p].r <= r) {
tree[p].mn += x;
tree[p].add += x;
return;
}
pushdown(p);
int mid = (tree[p].l + tree[p].r) >> 1;
if (l <= mid) update(p << 1, l, r, x);
if (r > mid) update(p << 1 | 1, l, r, x);
tree[p].mn = min(tree[p << 1].mn, tree[p << 1 | 1].mn);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> as[i];
}
ll mx = 0;
int tot = 1;
for (int i = 1; i <= n; ++i) {
if (as[i] > mx) {
mx = as[i];
poz.push_back({i, 0});
vis[i] = tot++;
}
}
vector<ll> ned(as + 1, as + n + 1);
vector<pii> ned2;
for (int i = 1; i <= n; ++i) {
ned2.push_back({as[i], i});
}
sort(ned.begin(), ned.end());
sort(ned2.begin(), ned2.end());
for (int i = 0; i < poz.size(); ++i) {
ll num = as[poz[i].first];
int d = upper_bound(ned.begin(), ned.end(), num) - ned.begin();
poz[i].second = ned.size() - d;
}
build(1, 1, poz.size());
cin >> q;
for (int i = 1; i <= q; ++i) {
cin >> ask[i].first;
ask[i].second = i;
}
sort(ask + 1, ask + q + 1);
int sz = ned2.size() - 1;
multiset<ll> st;
for (auto [a, b] : poz) {
st.insert(a);
}
for (int i = q; i >= 1; --i) {
auto [a, b] = ask[i];
while (sz >= 0 && ned2[sz].first > a) {
ll val = ned2[sz].second;
auto x = st.upper_bound(val);
if (x != st.end()) {
int pos = vis[*x];
update(1, pos, tot - 1, 1);
}
--sz;
}
ans[b] = tree[1].mn;
}
for (int i = 1; i <= q; ++i) {
cout << ans[i] << '\n';
}
return 0;
}
