Codeforces Round 1064 (Div. 2)

A. Same Difference

https://codeforces.com/contest/2166/problem/A
题目给定字符串，期望将字符串的字母全变成同一种，求最少的操作次数，每一次操作可以将Si改变为Si+1处的字母，所以关键观察，字符串末尾的字符不会改变
那么我们可以从后往前遍历一遍，记录与末尾字符不同的字符数量即可

#include<iostream>
#include<string>
using namespace std;
void solve(){int n,ans=0;string x;cin>>n>>x;for(int i=x.size()-1;i-1>=0;i--){if(x[i-1]!=x[i]){ans++;x[i-1]=x[i];}}cout<<ans<<"\n";
}
int main(){std::ios::sync_with_stdio(false);cin.tie(0);int t;cin>>t;while(t--){solve();}return 0;
}

B. Tab Closing

https://codeforces.com/contest/2166/problem/B
这道题其实也很简单但是，我没有全部考虑，浪费了一些时间，就是关闭网页，可以把网页分为两种状态挤压和未挤压，未挤压就把鼠标放在最左边，挤压就把鼠标放在最右边，关键观察答案只有两种情况，
一开始我没注意到，模拟做的，超时了，然后又想麻烦了一点点，不过最后Ac了，但是这其实很简单；

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
void solve(){double a,b,now_l=0;int n,ans=0;cin>>a>>b>>n;if(b>=a){cout<<1<<"\n";return;}else{cout<<2<<"\n";return;}return ;
}
int main(){std::ios::sync_with_stdio(false);cin.tie(0);int t;cin>>t;while(t--){solve();}return 0;
}

C. Cyclic Merging
https://codeforces.com/contest/2166/problem/C
这个题一开始没做出来，也就是没想明白，先大体回忆一下题目大意，给你一串数字，头尾相连，相邻两个可以进行消除操作，消耗两个中较大数字的体力，求最后只剩下1个数字时消耗体力的最小值，一开始我想到了合并果子（也就是哈夫曼树），但是想了一下，是错误的。我们可以这样想一下，最终剩下的一定是最大的那个才可以使代价最小，并且要用最小的数字和他附近大于他的最小数字进行合并，答案是最小的，其实题目原本的意图是想让参赛者进行模拟，但是有一种数学方法可以很快的解决这个问题：

还有一种可以理解的方法：

数学方法的代码如下：

//cf题解
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 5;
ll a[N];
int main()
{int t, n, m, i;ll k;scanf("%d", &t);while(t--){scanf("%d", &n);m = 0;for(i = 0; i < n; i++){scanf("%lld", a + i);if(a[i] > a[m])m = i;}a[n] = a[0];k = -a[m];for(i = 0; i < n; i++)k += max(a[i], a[i + 1]);printf("%lld\n", k);}return 0;
}

模拟做法如下：

//cf题解
#include <bits/stdc++.h>
using namespace std;
int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int t;cin >> t;while (t--) {int n;cin >> n;list<int> alive;int a[n];list<int>::iterator w[n];auto c_next = [&alive](const list<int>::iterator& it) {return next(it) == alive.end() ? alive.begin() : next(it);};auto c_prev = [&alive](const list<int>::iterator& it) {return it == alive.begin() ? --alive.end() : prev(it);};auto hole = [&](const list<int>::iterator& it) {return a[*it] <= min(a[*c_next(it)], a[*c_prev(it)]);};for (int i = 0; i < n; ++i) {cin >> a[i];w[i] = alive.insert(alive.end(), i);}queue<int> q;{int i = 0;for (auto it = alive.begin(); it != alive.end(); ++it, ++i)if (hole(it))q.push(i);}long long ans = 0;bool mark[n] = {};while (alive.size() > 1) {auto i = q.front();q.pop();if (mark[i])continue;mark[i] = true;auto it = w[i];ans += min(a[*c_next(it)], a[*c_prev(it)]);auto jt = c_next(it);alive.erase(it);it = jt;if (hole(it))q.push(*it);it = c_prev(it);if (hole(it))q.push(*it);}cout << ans << '\n';}
}