刚打完ABC,本来以为10点半开打，结果10点就开始了，只是一个疲惫。
A:
只要将数组的最大值排第一，最小值排第二就ok了，所以答案就是（n-1）*（max-min);
AC代码：
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=2e5+10,mod=1e9+7;
void solve() {int n;cin>>n;vector<int> a(n+1);for(int i=1;i<=n;i++){cin>>a[i];}sort(a.begin()+1,a.begin()+n+1);cout<<(n-1)*(a[n]-a[1])<<endl;
}
signed main() {ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);int t;cin >> t;while (t--)solve();return 0;
}
B:
赛时第一眼没看题，直接看样例，然后交了一发WA，其实只要s[0]='1',其余都为0就ok了，f(t)是 t的非空子序列 中只包含 0的个数， g(t)是 t的非空子序列中至少包含一个 1的个数。
只要s[0]='1',其余都为0，这样f(t)就始终会比g(t)小1。这样是最优的。
AC代码：
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=2e5+10,mod=1e9+7;
void solve() {int n;cin>>n;cout<<1;for(int i=1;i<n;i++){cout<<0;}cout<<endl;
}
signed main() {ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);int t;cin >> t;while (t--)solve();return 0;
}
C:
首先，我想只要出现了11这样，无论如何，Alice都能胜利，其次如果两边只要有一个是1，Alice就能获胜。
AC代码：
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=2e5+10,mod=1e9+7;
void solve() {int n;cin>>n;string s;cin>>s;for(int i=0;i<s.size()-1;i++){if(s[i]=='1'&&s[i+1]=='1'){cout<<"Yes"<<endl;return;}}if(s[0]=='1'||s[s.size()-1]=='1'){cout<<"Yes"<<endl;}else cout<<"No"<<endl;
}
signed main() {ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);int t;cin >> t;while (t--)solve();return 0;
}
D:
可以想一下，怎么才不能构成上升排列？
只要字符串出现LR,在L左边的数最多只能到达L的位置，不能再往右走了，所以只要左边存在a[i]>=L+1(该点必须到达L的右边)，与此同时，R的右边也会存在相应的点需要到R左边来的，但我的AC代码中还傻傻的加了这个多余的判断，没什么必要。
明白上面之后，要怎么去实现呢，就维护一下从1~i的最大值，再去找符合条件的LR,然后统计一下符合条件的LR的个数num,只要num>0，就肯定不能构成上升排列，
然后，每次查询修改字符串的时候，看他会不会影响num数量的改变。这样就行了。
AC代码：
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=2e5+10,mod=1e9+7;
void solve() {int n, q;cin >> n >> q;vector<int> a(n + 1);vector<int> mx1(n + 1, 0);vector<int> mx2(n + 1, 1e18);//这个其实是没有什么必要的，mx2是多余的，后面也都可以删掉for (int i = 1; i <= n; i++) {cin >> a[i];}mx1[1]=a[1];mx2[n]=a[n];for (int i = 2; i <= n; i++) {mx1[i] = max(mx1[i-1], a[i]);}for (int i = n-1; i >= 1; i--) {mx2[i] = min(mx2[i+1], a[i]);}string s;cin >> s;s = " " + s;int num = 0;for (int i = 1; i <= n; i++) {if (s[i] == 'L' && s[i + 1] == 'R') {if (mx1[i] >= i + 1 && mx2[i + 1] <= i) {num++;}}}while (q--) {int x;cin >> x;if (s[x] == 'L') {if (s[x + 1] == 'R') {if (mx1[x] >= x + 1 && mx2[x + 1] <= x) {num--;}}if (s[x - 1] == 'L') {if (mx1[x - 1] >= x && mx2[x] <= x - 1) {num++;}}s[x] = 'R';} else {if (s[x - 1] == 'L') {if (mx1[x - 1] >= x && mx2[x] <= x - 1) {num--;}}if (s[x + 1] == 'R') {if (mx1[x] >= x + 1 && mx2[x + 1] <= x) {num++;}}s[x] = 'L';}
// for(auto k:s) cout<<k;
// cout<<endl;if (num) cout << "NO" << endl;else cout << "YES" << endl;}
}
signed main() {ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);int t;cin >> t;while (t--)solve();return 0;
}
哎，今天ABC和CF的总结终于写完了，也是累了。
