CF1741
张恒灿
·
·
个人记录
比赛
T1（AC）
分情况讨论。
#include<iostream>
#include<cstdio>
#include<string>
typedef long long ll;
using namespace std;
int t;
string a,b;
int la,lb;
int main(){
cin>>t;
while(t--){
cin>>a>>b;
if(a==b){
cout<<"="<<endl;
continue;
}
la=a.size();
lb=b.size();
if(a[la-1]>b[lb-1]){//小
cout<<"<"<<endl;
}
else if(a[la-1]<b[lb-1]){//大
cout<<">"<<endl;
}
else{//最后一位相等
if(a[la-1]=='L' && la>lb || a[la-1]=='S' && la<lb){
cout<<">"<<endl;
}
else if(a[la-1]=='L' && la<lb || a[la-1]=='S' && la>lb){
cout<<"<"<<endl;
}
else{
cout<<"="<<endl;
}
}
}
return 0;
}
T2（AC）
偶数个就直接输出。
除 $3$ 外的奇数个数，涉及到中间数重复问题。先输出 $n$ 和 $n-1$，然后从小到大输出 $1$ 到 $(n-2)$ 的值。
```cpp
#include<iostream>
#include<cstdio>
typedef long long ll;
using namespace std;
int t;
int n;
int main(){
cin>>t;
while(t--){
cin>>n;
if(n%2==0){
for(int i=n;i>=1;i--){
cout<<i<<' ';
}
cout<<endl;
}
else if(n==3){
cout<<-1<<endl;
}
else{
cout<<n<<' '<<n-1<<' ';
for(int i=1;i<=n-2;i++){
cout<<i<<' ';
}
cout<<endl;
}
}
return 0;
}
```
## [T3](https://www.luogu.com.cn/problem/CF1741C)（瞄了一眼题解）
维护 $a$ 数组的前缀和，每次按前 $i$ 个的和遍历，枚举。
```cpp
#include<iostream>
#include<cstdio>
typedef long long ll;
using namespace std;
const int maxn=2e3+5;
int t;
ll n,a[maxn],pre[maxn];
int main(){
scanf("%d",&t);
while(t--){
scanf("%lld",&n);
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
pre[i]=pre[i-1]+a[i];
}
ll minmax=0x3f3f3f3f;
for(int i=1;i<=n;i++){//和
ll maxx=0;
bool flag=true;
ll sumt=0,cnt=0;
for(int j=1;j<=n;j++){
sumt+=a[j];
cnt++;
// cout<<i<<' '<<sumt<<'#'<<cnt<<endl;
if(sumt==pre[i]){
maxx=max(maxx,cnt);
sumt=0;
cnt=0;
continue;
}
if(sumt>pre[i]){
flag=false;
break;
}
}
if((sumt==pre[i] || sumt==0) && flag){
maxx=max(maxx,cnt);
minmax=min(minmax,maxx);
}
}
cout<<minmax<<endl;
}
return 0;
}
```
## [T4](https://www.luogu.com.cn/problem/CF1741D)（赛后改对）
判断是否合法问题：如果这一段中最大值和最小值的差等于左右端点的差就暂时合法，进入下一层递归继续判断。如果两者不相等，那么一定不合法，将 $flag$ 标记为 $false$。
```cpp
#include<iostream>
#include<cstdio>
#include<set>
typedef long long ll;
using namespace std;
const int maxm=262150;
int m,a[maxm];
bool flag=true;
int tsort(int l,int r){//数列左端点、右端点之间排序所需步数
if(flag==false) return 0;//随便返回
if(l+1==r){//两个相邻的点
if(a[l]+1==a[r]) return 0;//顺序对
else if(a[l]-1==a[r]) return 1;//顺序不对，一次交换
else{//不符合条件
flag=false;
return 0;//随便返回
}
}
int maxx=0,minn=0x3f3f3f3f;
for(int i=l;i<=r;i++){
maxx=max(maxx,a[i]);
minn=min(minn,a[i]);
}
if(maxx-minn!=r-l){
flag=false;
return 0;
}
int mid=(l+r)>>1;
int now;//此次需要交换的次数
if(a[l]<a[r]) now=0;
else now=1;
return tsort(l,mid)+tsort(mid+1,r)+now;
}
int main(){
int t;
cin>>t;
while(t--){
flag=true;
cin>>m;
for(int i=1;i<=m;i++){
cin>>a[i];
}
if(m==1){
cout<<0<<endl;
continue;
}
int ans=tsort(1,m);
// cout<<ans<<endl;
if(flag==false){
cout<<-1<<endl;
}
else{
cout<<ans<<endl;
}
}
return 0;
}
```