总结
T1
考场上有思路，并且把它码出来了，没有什么大问题。
T2
题二，考场上想到了一个分类讨论，但是没有用到并查集的一个做法。挂成了十分。主要是没有想到他在某一种情况继续要反转又不需要翻转即无解的情况。
T3
T3考场上去想查分去了，但是由于题目上面。发现差分会更具有普遍性，强于题目。这个时候我们就要去想一些更有针对性的做法。
题解
T1
我们会发现个位是最有可能会成为最优解的。因为它的变化速度是最快的。那么此时如果说我们的左边和右边差距超过了10。那么各位就已经完成了一次周期。那么此时的答案就一定是9。
如果说两个之间的差距小于九，那么直接枚举就可以了。
代码
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3f
#define int long long
#define endl '\n'
using namespace std;
const int maxn=2e5+5;
int f(int x)
{int ans=-1;while(x) ans=max(ans,x%10),x/=10;return ans;
}
signed main()
{freopen("digit.in","r",stdin);freopen("digit.out","w",stdout);ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);int t;cin>>t;while(t--){int l1,r1,l2,r2;cin>>l1>>r1>>l2>>r2;if(r1-l1+1>=10||r2-l2+1>=10) cout<<9<<endl;else{int ans=0;for(int i=l1;i<=r1;i++) for(int j=l2;j<=r2;j++) ans=max(ans,f(i+j));cout<<ans<<endl;}}return 0;
}
T2
我们发现最后每一列都至多是一，那么此时我们就可以发现。当前，这一列与它对称的这一列两个的两列的一的个数加起来，如果说大于二就一定不可能。
这里需要特判一下，如果说他对称的那一列就是他自己，那么等于二也不可以。
此时我们就看如果说当前当前这一行所对应的值所在的列。上还有一行的，这一列上也有值。那么他们俩就一定是要么一个翻转，一个不翻转。
如果说当年这一行所对应的值所在的列对称的那一个列上还有一行，这一列上也有值，那么这个时候一定是同时翻转或者同时不反转。（此时特判一下当前这一个还有的值是不是自己）
然后我们用种类并查集存他是否反转。如果说他翻转和不翻转在同一个集合内就不可以。否则我们设连通贯个数为 \(2k\)，那么答案就是 \(2^k\)。
代码
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3f
#define int long long
#define endl '\n'
using namespace std;
const long long maxn=1e6+5,mod=1e9+7;
int fa[maxn],cnt[maxn];
int kasumi(int a,int b)
{if(b<0) return 0;int ans=1;while(b){if(b&1) ans=ans*a%mod;a=a*a%mod;b>>=1;}return ans;
}
void init(int n)
{for(int i=1;i<=n*2;i++) fa[i]=i;
}
int get(int x)
{return fa[x]==x?x:fa[x]=get(fa[x]);
}
void merge(int u,int v)
{u=get(u),v=get(v);if(u!=v) fa[v]=u;
}
signed main()
{freopen("reverse.in","r",stdin);freopen("reverse.out","w",stdout);ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);int t;cin>>t;while(t--){int n,m;cin>>n>>m;init(n);for(int i=1;i<=m;i++) cnt[i]=0;int ans=n;vector<vector<int> > a(n+2);for(int i=1;i<=n;i++){a[i].resize(m+2);for(int j=1;j<=m;j++){char c;cin>>c;a[i][j]=c-'0';cnt[j]+=a[i][j];}}int f=1;if(m%2==1&&cnt[m/2+1]>=2) f=0;for(int j=1;j<=m/2;j++){if(cnt[j]>2) f=0;int x=0,y=0;for(int i=1;i<=n;i++){if(a[i][j]){if(x) y=i;else x=i;}}for(int i=1;i<=n;i++){if(a[i][m-j+1]){if(x) y=i;else x=i;}}if(!x||!y) continue;if(x==y) continue;if(a[x][j]==a[y][j]) merge(x,y+n),merge(x+n,y);else merge(x,y),merge(x+n,y+n);}int cnt=0;for(int i=1;i<=n*2;i++){if(i<=n&&get(i+n)==get(i)) f=0;if(fa[i]==i) cnt++;}cout<<f*kasumi(2,cnt/2)<<endl;}return 0;
}
T3
题目上有一个很重要且极具迷惑性的条件。\(a_i-a_{i-1}=1\)
这个条件是肯定是相当重要的。但是呢，我们会发现差分在这里就太强了。会导致我们这个代码更难写。我们发现他希望相邻的两个只差一，那么我们对每一个 \(a_i\) 减去 \(i\) 就可以了。
这样题目就被转化成每一次可以对一个值加一或者减一。最多做 \(k\) 次之后。最长相同的字段长度是多少？
这个值是可以双指针做的。那么我知道了一个区间如何快速计算它至少要操作多少次呢？
不难发现，我们每次都希望把这个区间内的值全部都变成这个区间内的中位数。那么我们用一个对顶堆求出中位数，然后再用区间内所有的数和减去这个中位数乘个数就可以了。
代码
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3f
#define int long long
#define endl '\n'
using namespace std;
const int maxn=2e5+5;
int a[maxn];
signed main()
{freopen("subarray.in","r",stdin);freopen("subarray.out","w",stdout);ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);int t;cin>>t;while(t--){int n,k;cin>>n>>k;multiset<int> q2;multiset<int,greater<int> > q1;for(int i=1;i<=n;i++) cin>>a[i],a[i]-=i;// for(int i=1;i<=n;i++) cout<<a[i]<<' ';// cout<<endl;int sum1=0,sum2=0,ans=0;for(int l=1,r=1;r<=n;r++){q1.insert(a[r]);sum1+=a[r];while(q1.size()>q2.size()) q2.insert(*q1.begin()),sum1-=*q1.begin(),sum2+=*q1.begin(),q1.erase(q1.begin());while(q1.size()<q2.size()) q1.insert(*q2.begin()),sum2-=*q2.begin(),sum1+=*q2.begin(),q2.erase(q2.begin());int cnt=sum2-q2.size()*(*q1.begin())+q1.size()*(*q1.begin())-sum1;while(cnt>k&&l<r){if(q1.find(a[l])!=q1.end()) q1.erase(q1.find(a[l])),sum1-=a[l];else q2.erase(q2.find(a[l])),sum2-=a[l];while(q1.size()>q2.size()) q2.insert(*q1.begin()),sum1-=*q1.begin(),sum2+=*q1.begin(),q1.erase(q1.begin());while(q1.size()<q2.size()) q1.insert(*q2.begin()),sum2-=*q2.begin(),sum1+=*q2.begin(),q2.erase(q2.begin());cnt=sum2-q2.size()*(*q1.begin())+q1.size()*(*q1.begin())-sum1;l++;// cout<<l<<' '<<r<<':'<<cnt<<endl;// cout<<*q1.begin()<<':'<<q1.size()<<' '<<sum1<<'|'<<q2.size()<<' '<<sum2<<endl;}ans=max(ans,r-l+1);// cout<<"sss"<<endl;}cout<<ans<<endl;// cout<<endl;}return 0;
}