好好反思一下，自己在学什么，自己怎么在做训练赛的，真有这么难吗 ？？？？？
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 S是整个最终字符串的某一段，且 S S S恰好是 K K K对回文索引构成的。那么你要把原本剩余的所有符号，拿去继续拼字符串且不能出现任何回文，只能是01，01 一对一对地抵消。
所以，这个题，我们需要 N / 2 − K N/2-K 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 (0+算术平方根)^2 (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 10^5 105该怎么做？？指不定李老师下次就出题来考考大家了
#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 P_i=i Pi=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 1 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;
}