6月2日上午思维训练题解

好好反思一下，自己在学什么，自己怎么在做训练赛的，真有这么难吗 ？？？？？

A - Need More Arrays 题解

想尽可能多的拆出新数组的个数，只需要从原本的数组中提取出最长的一段上升序列即可。
让这个序列内的数字都满足 前一项+1<当前项 统计答案就行了

#include<bits/stdc++.h>
using namespace std;
int A[200005];
int main(){//抄代码者立马开除int t;cin>>t;while(t--){int n;cin>>n;for(int i=1;i<=n;i++){cin>>A[i];}int cnt=1;int pre=A[1];for(int i=2;i<=n;i++){while(pre+1>=A[i]&&i<=n){i++;}//结束的时候说明  pre+1<A[i] 或者结束了if(i<=n){cnt++;pre=A[i];} }cout<<cnt<<'\n';}return 0;
} 

B - Not Quite a Palindromic String

这是一个构造题，如何思考呢？不难发现其实是要构造一段回文字符串再拼一些不能回文的地方。
我们可以思考一下，假设$S$是整个最终字符串的某一段，且$S$恰好是$K$对回文索引构成的。那么你要把原本剩余的所有符号，拿去继续拼字符串且不能出现任何回文，只能是01，01 一对一对地抵消。

所以，这个题，我们需要$N/2-K$ 对 多余的0，1来完成“不回文的构造”，剩余的所有0，1的对数，只需要恰好是K对就行了 。

#include<bits/stdc++.h>
using namespace std;
char A[200005];
int main(){int t;cin>>t;while(t--){int n,k;cin>>n>>k;cin>>A+1;int a=0,b=0;for(int i=1;i<=n;i++){if(A[i]=='0')a++;else b++;}a=a-(n/2-k);b=b-(n/2-k);	//  n/2-k 匹配不相等if(a>=0&&b>=0&&a/2+b/2==k){cout<<"YES"<<'\n';} else{cout<<"NO"<<'\n';}}return 0;
}

C - Square Year

枚举就行了，注意给定的年份是四位数，所以至多枚举a从0到100，b从0到100 求出一个解就行了

当然还有一种思路，能构成出来一定是平方数，我们设置为$(0+算术平方根{)}^2$ 就行了 相当于检查年份是不是一个 平方数

有同学可能会问，输入进来0001 明明是字符串呀，实际上这个东西按整数类型输入进来就是1 前导0是没多大意义的

如何检查年份是不是平方数？ 只需要对年份开根号之后，向上，向下取整，如果结果一样 那就是平方数

#include<bits/stdc++.h>
using namespace std;
int main(){int t;cin>>t;while(t--){int n;cin>>n;double q=sqrt(n);if(ceil(q)==floor(q)){cout<<0<<" "<<q<<'\n';}else{cout<<-1<<'\n';}}return 0;
}

D - Fashionable Array

直接双重循环，一个枚举左边，一个枚举右边，检查他们加起来是不是偶数就行了。如何是偶数，保存一下答案。

当然，同学们，思考一下，如果这个题N变得比较大$10^5$该怎么做？？指不定李老师下次就出题来考考大家了

#include<bits/stdc++.h>
using namespace std;
int A[200005];
int main(){int t;cin>>t;while(t--){int n;cin>>n;for(int i=1;i<=n;i++){cin>>A[i];}sort(A+1,A+1+n);int ans=9999;for(int i=1;i<=n;i++){for(int j=n;j>=i;j--){if((A[i]+A[j])%2==0){ans=min(ans,i-1+n-j);}}}	cout<<ans<<'\n';}return 0;
}

E - Down with Brackets

找找规律我们会发现，如果整个字符串的括号序列是完全由最外面一个括号包含的，那么无解，大家可以自己草稿上画一下，观察一下

必须出现两个及以上，独立的最外层括号，才能是YES，对着样例自己理解一下吧

如何检查这个括号呢？我们定义L 来记录当前左括号的数量，当然遇到右括号的时候肯定要抵消一个左括号

如果当我们的左括号个数被抵消的时候，且被抵消为0 了，说明一个最外层大括号 被消灭了。如果后续还会有左括号被扫进来 ，那么说明这是另外一个独立的括号

#include<bits/stdc++.h>
using namespace std;
char A[200005];
int main(){int t;cin>>t;while(t--){cin>>A+1;int len=strlen(A+1);int L=0;int R=0;bool ok=false;bool can=false;for(int i=1;i<=len;i++){if(A[i]=='('){if(can==true)ok=true;L++;}else{L--;if(L==0)can=true;}}	if(ok==true){cout<<"YES"<<'\n';}else{cout<<"NO"<<'\n';}}return 0;
}//(()(()())
//((((()))))

F - It’s Time To Duel

其实，只有两种情况在撒谎。要么所有人都赢了；要么有相邻的人都输了。肯定是矛盾的。

在这里插入代码片#include<bits/stdc++.h>
using namespace std;
int A[200005];
int main(){int t;cin>>t;while(t--){int n;cin>>n;int s=0;for(int i=1;i<=n;i++){cin>>A[i];s=s+A[i];}if(s==n){cout<<"YES"<<'\n';continue;}bool ok=false;for(int i=1;i<=n-1;i++){if(A[i]==0&&A[i+1]==0){ok=true;break;}}if(ok)cout<<"YES"<<'\n';else cout<<"NO"<<'\n';}return 0;
}//(()(()())
//((((()))))

G - Slice to Survive

很明显的思路，一个人想尽可能多，一个人想尽可能少，你自己做个博弈游戏玩玩就知道了。想避免被对手压缩生存空间，每次把怪兽放到当前活动空间的中心位置就行了，因为哪怕一分为二，也是能尽快可能多保障自己游戏次数。

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
ll T;
ll N,M,a,b;
void solve() {ll ans=N+M;ll n=N;ll m=M;n-=max(a-1,N-a);ll sum=0;while(n!=1) {sum++;n=(n+1)/2;}while(m!=1) {sum++;m=(m+1)/2;}ans=min(ans,sum);sum=0;n=N;m=M;m-=max(b-1,M-b);while(n!=1) {sum++;n=(n+1)/2;}while(m!=1) {sum++;m=(m+1)/2;}ans=min(ans,sum);ans++; printf("%lld\n",ans);}
int main() {cin>>T;for(ll t=0; t<T; t++) {scanf("%lld%lld%lld%lld",&N,&M,&a,&b);solve();}return 0;
}

H - Permutation Warm-Up

对于一个$P_i=i$的排列，我们可以通过不断交换两个位置的数把它变成任意的排列。发现每次交换两个数增加的值是偶数，那么值只会是偶数。所有偶数都可以拿到。那么求出最大的值看有多少偶数。

#include<bits/stdc++.h>
using namespace std;int main(){int t,n;cin>>t;while(t--){cin>>n;cout<<n*n/4+1<<'\n';}return 0;
}

I - LRC and VIP

直接把最大的数，放在一个序列；其余所有值放在另一个序列
他们所产生的最大公约数一定不相等，除非整个数组一开始全一样

纯思维题

J - Apples in Boxes

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
constexpr int N=1e5+7;
int a[N],n,k;
inline bool solve()
{cin>>n>>k;ll mx1=0,mx2=0,mn=1.2e18;ll s=0;for(int i=1;i<=n;i++){cin>>a[i];if(a[i]>mx1) mx1=a[i];else if(a[i]>mx2) mx2=a[i];if(a[i]<mn) mn=a[i];s=(s+a[i])%2;}mx1--;if((max(mx1,mx2)-mn)>k) return 0;  if(s%2==1) return 1;else return 0;
}
int main()
{int T;cin>>T;while(T--) puts(solve()?"Tom":"Jerry");	return 0;
}

K - Dr. TC

这题不会做吗？？？答案就是原本的串里面$1$的个数乘N倍，再枚举一遍看看哪些位置被反转了，可能要加上或者减去

L - St. Chroma

#include <bits/stdc++.h>
using namespace std;
int main() {int t = 1;cin >> t;while (t--) {int n, x;cin >> n >> x;if (x == 0) {for (int i = 1; i < n; i++) {cout << i << " ";}cout << 0 << "\n";return;}if (x == n) {for (int i = 0; i < n; i++) {cout << i << " \n"[i == n - 1];}return;}for (int i = 0; i < x; i++) {cout << i << " ";}for (int i = x + 1; i < n; i++) {cout << i << " ";}cout << x << "\n";}return 0;
}

M - Cherry Bomb

#include<bits/stdc++.h>using namespace std;
int a[200005],b[200005];
int main(){int T;cin>>T;while(T--){int n,k;cin>>n>>k;for(int i=1;i<=n;i++){cin>>a[i];}bool flag=1;for(int i=1;i<=n;i++){cin>>b[i];if(b[i]!=-1) flag=0;}if(flag==1){int maxn=0,minn=1e9;for(int i=1;i<=n;i++){maxn=max(maxn,a[i]);minn=min(minn,a[i]);}if(maxn-minn>k) cout<<"0\n";else cout<<k-(maxn-minn)+1<<"\n";}else{bool f=1;int s=0;for(int i=1;i<=n;i++){if(b[i]!=-1){s=a[i]+b[i];break;}}for(int i=1;i<=n;i++){if(s-a[i]<0){f=0;break;}if(b[i]!=-1&&a[i]+b[i]!=s){f=0;break;}if(b[i]==-1){if(s-a[i]>k){f=0;break;}}}if(f==1) cout<<"1\n";else cout<<"0\n";}}return 0;
}