赛时出了四题，感觉和队里大佬差距还是很大啊，但是反过来想，还是有很大提升空间的（）
1009临渊羡鱼
就是最大值和最小值差值+1，直接写就好
#include <bits/stdc++.h>
using namespace std;
/**/
#define ll long long
#define double long double
#define pii pair<ll,ll>
void sol() {int n;cin>>n;vector<int> a(n);for(int i=0;i<n;i++) cin>>a[i];cout<<*max_element(a.begin(),a.end())-*min_element(a.begin(),a.end())+1<<'\n';
}int main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t--) {sol();}return 0;
}
1007最大三段和
因为中间的只有一个点，我们可以在\(k\in[3,n-2]\)范围上枚举中间点，答案=\(max\{pre_{k-2}+a_k+suf_{k+2}\}\)，其中\(pre_i,suf_i\)分别表示\(i\)位置之前的最大子段和以及\(i\)位置之后的最大子段和。我们可以先算出强制选每一个点的前缀最大子段和和后缀最大子段和，即\(pre_i=max\{pre_{i-1},0\}+a_i\)和\(suf_i=max\{suf_{i+1},0\}+a_i\)，然后再求出\(i\)位置之前的最大子段和以及\(i\)位置之后的最大子段和，即\(pre_i=max\{pre_i,pre_{i-1}\}\)和\(suf_i=max\{suf_i,suf_{i+1}\}\)。
#include <bits/stdc++.h>
using namespace std;
/**/
#define ll long long
#define double long double
#define pii pair<ll,ll>// int gcd(int a,int b){
// return b?gcd(b%a,a):a;
// }void sol() {int n;cin>>n;vector<ll> a(n+1,0),pre(n+1,0),suf(n+1,0);for(int i=1;i<=n;i++) cin>>a[i];pre[1]=a[1],suf[n]=a[n];for(int i=2;i<=n;i++) pre[i]=max(pre[i-1],0ll)+a[i];for(int i=n-1;i>=1;i--) suf[i]=max(suf[i+1],0ll)+a[i];for(int i=2;i<=n;i++) pre[i]=max(pre[i],pre[i-1]);for(int i=n-1;i>=1;i--) suf[i]=max(suf[i],suf[i+1]);ll ans=INT64_MIN;for(int i=3;i<=n-2;i++){ans=max(ans,a[i]+pre[i-2]+suf[i+2]);}cout<<ans<<'\n';
}int main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t--) {sol();}return 0;
}
1001最大的公约数
自己在这道题上卡了很久，最开始尝试从\(gcd(a,n-a)\)出发但是做不下去，写了1007之后有了点灵感。
对于这种和数论有关的题，可以从质因数分解或者分解成最大公因数和一个因子的角度出发。从比较自然的角度解释就是，我们希望找出\(gcd\)的最大值，可以找找\(gcd\)满足哪些公式和数量关系，然后进行转化。
那么容易知道\(a=k_1*g,b=k_2*g\),其中\(k_1>k_2\ge 1\)，这里我们把\(gcd\)简写成\(g\)。然后我们还知道\(a+b=(k_1+k_2)*g=n \iff g= \frac{n}{k_1+k_2}\)，由此可见，我们只需要找出不为\(n\)的最大的\(n\)的因数就可以，注意这里\(k_1+k_2>2\)，所以说\(g=\frac{n}{2}\)这个因子是不能放进去的。按照上述条件我们收集所有符合条件的因数并从大到小排序就可以。
代码
#include <bits/stdc++.h>
using namespace std;
/**/
#define ll long long
#define double long double
#define pii pair<ll,ll>void sol() {int n;cin>>n;vector<int> ans;ans.push_back(1);for(int i=2;i*i<=n;i++){if(n%i==0){if(i==2) ans.push_back(2);else{ans.push_back(i);ans.push_back(n/i);}}}sort(ans.begin(),ans.end(),greater<int>());cout<<ans[0]<<'\n';}int main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t--) {sol();}return 0;
}
1003 杂草蔓延
这道题想了好久，首先我们令\(a=min(n,m),b=max(n,m)\)，然后变成一个横向长度为\(a\)，纵向长度为\(b\)的长方形，方便讨论。当\(a=1\)的时候，显然隔一个放一个是最优解。当\(a \ge 2\)的时候，因为一个\(2*2\)的格子我们可以通过放对角线进行构造。那么如果是\(3*3\)及更大的正方形，我们也可以采用在对角线上放草这种做法进行构造，那么正方形放完了，还剩下\(b-a\)长度，显然我们隔一个放一个就可以。
不是很好想，但是代码就寥寥几行...
代码
#include <bits/stdc++.h>
using namespace std;
/**/
#define ll long long
#define double long double
#define pii pair<ll,ll>void sol() {int n,m;cin>>n>>m;int a=min(n,m),b=max(n,m);if(a==1){cout<<b/2+1<<'\n';}else{cout<<a+(b-a+1)/2<<'\n';}
}int main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t--) {sol();}return 0;
}
1002 雪蜜冰城柠檬茶的神秘成分魔法
自己这道题写了俩小时没写出来，写的太史了。自己赛时的想法是对每个权值维护一个并查集，然后记录下每个权值的并查集的头的编号，以及并查集的头的编号的权值。然后直接进行模拟，比赛的时候因为少写了一行代码就WA了...
(这段时间学Web开发追求变量命名规范意义明确然后在这段代码里面采用了驼峰式命名，但还是改变不了屎山代码的本质...)
代码（史）
#include <bits/stdc++.h>
using namespace std;
/*对每一个点维护一个并查集然后map存并查集的头部搞两个map存一下映射吧...*/
#define ll long long
#define double long double
#define pii pair<ll,ll>struct DSU{int n;//第一个是值到并查集头，第二个是并查集头到值map<int,int> ValToHead,HeadToVal;vector<int> siz,fa,a;// DSU(int n_):n(n_),siz(n+1,1),fa(n+1),a(n+1){// for(int i=1;i<=n;i++) fa[i]=i;// }DSU(int n_):n(n_),siz(1,1),fa(1,1),a(1,1){}void add(int i){siz.push_back(1),fa.push_back(i);auto it=ValToHead.find(a[i]);if(it==ValToHead.end()){ValToHead[a[i]]=fa[i];HeadToVal[fa[i]]=a[i];}else{siz[it->second]++;fa[i]=it->second;}}int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}void change(int x,int y){// if(x==y) return ;auto check=ValToHead.find(x);int fx;if(check==ValToHead.end()) return ;else fx=check->second;auto it=ValToHead.find(y);if(it==ValToHead.end()){ValToHead[y]=fx;HeadToVal[fx]=y;ValToHead.erase(x);}else{int fy=it->second;siz[fy]+=siz[fx];fa[fx]=fy;ValToHead.erase(x);HeadToVal.erase(fx);}}void clear(int x){auto it=ValToHead.find(x);if(it==ValToHead.end()) return ;else{int fx=it->second;HeadToVal.erase(fx); ValToHead.erase(x);}}};void sol() {int n,m;cin>>n;DSU dsu(n);for(int i=1;i<=n;i++){int x;cin>>x;dsu.a.push_back(x);dsu.add(i);}// for(int i=1;i<=n;i++){// int fx=dsu.find(i);// cout<<dsu.HeadToVal[fx]<<" ";// }cin>>m;int sum=n;while(m--){int op;cin>>op;if(op==1){int x,y;cin>>x>>y;dsu.change(x,y);}else if(op==2){int x;cin>>x;sum++;dsu.a.push_back(x);dsu.add(sum);}else{int x;cin>>x;dsu.clear(x);}// for(int i=1;i<=sum;i++){// int fi=dsu.find(i);// auto it=dsu.HeadToVal.find(fi);// if(it!=dsu.HeadToVal.end()) cout<<it->second<<" ";// }// cout<<'\n';}for(int i=1;i<=sum;i++){int fi=dsu.find(i);auto it=dsu.HeadToVal.find(fi);if(it!=dsu.HeadToVal.end()) cout<<it->second<<" ";}cout<<'\n';
}int main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t--) {sol();}return 0;
}
已经好久没有这么高强度的训练了，确实有一种赛场的紧张感。
这场比赛的知识上的经验就是对数论这种问题如果想不出来可以尝试质因数分解，分解最大公因数等方法，然后尝试去找答案和已知的数量关系进行建模。
以及，菜就多练...