-
T1
看了这么多 T1，终于找到简单题了！！！
发现最后一个点无法更改，要使所有点都相等，也就是让 \(1 \sim n-1\) 的所有点都和 \(n\) 号点相等。
那么修改的次数就是 \(1 \sim n-1\) 中和 \(n\) 号点不同的点的数量。
代码：
#include<bits/stdc++.h>
using namespace std;
char s[105];
signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int _;cin >> _;while(_--){int n;cin >> n;cin >> s+1;int len = strlen(s+1);int num = 0;for(int i = 1;i<len;++i){if(s[i]!=s[len]){++num;}}cout << num << '\n';}return 0;
}
-
T2
不是出题人你 T3 < T2，非人哉！
出题人你有点良心吧，出题就把题面就说清楚啊！
唉，T2 其实不算难，但是比赛时由于脑抽加上题面不是很清导致跳了，去做了 T3，还好 T3 过了，不然我就完了。
注意：不能一边走一边点击（我就是这个原因加上脑抽没看懂样例）！！！！
思路其实不难，考虑观察样例，发现答案竟然没有一个超过 \(2\)，思考往日的 T2 一般都是数学题，很容易想到答案不超过 \(2\)，证明也很简单，因为由于 \(b\) 是常数，我们先不看，先假设 \(len = \frac{a}{m}\)，那么很容易发现，先花费一次移动移动到 \(a\)，然后疯狂点就行了，这样答案永远只是 \(1\)，但是别忘了我们舍去了 \(b\)，加上 \(b\)，\(len = \min(b,\frac{a}{m})\)，发现会出现更坏的情况，就是在 \(m\) 不断变小之后最后一个标签页不再是 \(a\) 了，这种情况也就是存在一个 \(m(1 \le m \le n)\) 使得 \(\frac{a}{m}>b\)，其实你发现 \(m = 1\) 时 \(\frac{a}{m}\) 最大，最有可能 \(>b\)，所以式子变成 \(\frac{a}{1}>b\)，也就是 \(a>b\)，但是还有一个情况，就算刚刚那个式子满足了，你会发现竟然还有一种情况让答案变成 \(1\)，就是对于所有的 \(m\) 第一个标签页的位置都是 \(b\)，也就是对于 \(\forall m(1 \le m \le n),\frac{a}{m}>b\)，化简这个东西，发现，其实是：
注意：第一种情况让答案变劣，第二种情况让答案重新变成 \(1\)。
这时，发现答案最坏也仅仅只是 \(2\)，证毕。此时发现，根据刚刚的答案为 \(2\) 的情况，显然就知道了答案为 \(1\) 的条件：
此时，已经无需思考即可得出代码。
十年 OI 一场空，不开 long long 见祖宗！！
代码：
#include<bits/stdc++.h>
using namespace std;signed main()
{ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);int _;cin >> _;while(_--){int a,b,n;cin >> a >> b >> n;cout << (b>=a||1ll*b*n<=a?1:2) << '\n';}return 0;
}
-
T3
有史以来最简单的 T3！！！！
简单贪心，因为贡献总是 \(\max(x,y)\)，所以我们在任意时刻尽量让合并的数越小越好，题目就变成了动态维护环上相邻点对的值的 \(\max\) 的最大值，然后合并为 \(\max(x,y)\)，做过这个 trick 的人很快就能秒掉，但很可惜，我没做过。不过考场时的我并没有放弃，经过努力思考，想出了一个 \(O(n \log n)\) 的做法，详细的说就是用一个 set 维护，一开始先将每个数向前驱和后继分别连一条不同权值的边，然后先初始化前驱后继数组（咋这么像链表），然后开始类似广度优先搜索的跑图（其实一点也不相似，只是结构有点像），然后每次取出最小的，合并后，更新前驱后继即可。当然带点 STL 的常数。
十年 OI 一场空，不开 long long 见祖宗！！
代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
int a[N];
int l[N];
int r[N];
int vis[N];
signed main()
{ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;cin >> t;while(t--){int n;cin >> n;for(int i = 0;i<n;++i){cin >> a[i];l[i] = (i-1+n)%n;r[i] = (i+1)%n;vis[i] = 0;}if(n == 1){cout << 0 << '\n';continue;}set<pair<int,int>>s;for(int i = 0;i<n;++i){s.insert({max(a[i],a[r[i]]),i});}long long sum = 0;int x = n;while(x>1){auto it = s.begin();int cnt = it->first;int i = it->second;s.erase(it);int j = r[i];if(vis[i]||vis[j]||r[i]!=j){continue;}sum+=cnt;if(a[i]>a[j]){vis[j] = 1;r[i] = r[j];l[r[j]] = i;s.erase({max(a[l[j]],a[j]),l[j]});s.erase({max(a[j],a[r[j]]),j});s.insert({max(a[i],a[r[i]]),i});s.insert({max(a[l[i]],a[i]),l[i]});}else{vis[i] = 1;l[j] = l[i];r[l[i]] = j;s.erase({max(a[l[i]],a[i]),l[i]});s.erase({max(a[i],a[r[i]]),i});s.insert({max(a[j],a[r[j]]),j});s.insert({max(a[l[j]],a[j]),l[j]});}--x;}cout << sum << '\n';}return 0;
}