A
核心思路
也是一个观察性质的过程，但是这个性质比较简单。我们可以发现两个数相等的时候比较好构造。并且我们取另外一个数为1就好了。
// Problem: A. The Third Three Number Problem
// Contest: Codeforces - Codeforces Round #804 (Div. 2)
// URL: https://codeforces.com/contest/1699/problem/A
// Memory Limit: 256 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define NO {puts("NO") ; return ;}
#define YES {puts("YES") ; return ;}
#define endl "\n"
#define int long long
void solve()
{
int n;
cin>>n;
if(n%2)
{
cout<<-1<<endl;
return;
}
int t=(n/2)^1;
cout<<t<<" "<<t<<" "<<1<<endl;
}
signed main()
{
int T;
cin>>T;
while(T--)
{
solve();
}
}
B
这里的性质就是
0 1 1 0
1 0 0 1
我们会发现n和m都必须得是偶数。
这个性质还是从2*2的矩阵里面发现的。
但是这题我们需要立两个flag一样的东西。
// Problem: A. The Third Three Number Problem
// Contest: Codeforces - Codeforces Round #804 (Div. 2)
// URL: https://codeforces.com/contest/1699/problem/A
// Memory Limit: 256 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define NO {puts("NO") ; return ;}
#define YES {puts("YES") ; return ;}
#define endl "\n"
#define int long long
void solve()
{
int n;
cin>>n;
if(n%2)
{
cout<<-1<<endl;
return;
}
int t=(n/2)^1;
cout<<t<<" "<<t<<" "<<1<<endl;
}
signed main()
{
int T;
cin>>T;
while(T--)
{
solve();
}
}
C
核心思路
这里就需要挖掘mex的性质了。首先我们如果需要一段序列的mex的值是x，那么这段序列里面[0,x-1]这里面的数肯定都出现过。
把这个性质挖掘出来了，问题也就解决了大半了。所以我们可以统计每个数出现的左右区间。
比如我们需要放入一个4
0 1 2 - - - 3
所以这个区间长度减去我们已经出现的数就好了：len-i
[0,i-1]的区间长度是i哦。
所以我们枚举[0,n-1]的区间端点就好了。
mex函数其实博弈论里面是使用了的。这里有点不一样的是，我们是采取了直接一个一个的找的方式。时间复杂度比较高
// Problem: C. The Third Problem
// Contest: Codeforces - Codeforces Round #804 (Div. 2)
// URL: https://codeforces.com/contest/1699/problem/C
// Memory Limit: 256 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define NO {puts("NO") ; return ;}
#define YES {puts("YES") ; return ;}
#define endl "\n"
#define int long long
int mod=1e9+7;
const int N=1e6+10,INF=0x3f3f3f3f;
int a[N],pos[N];
void solve()
{
int n;
cin>>n;
int ans=1;
for(int i=1;i<=n;i++)
{
cin>>a[i];
pos[a[i]]=i;
}
int L=INF,R=-INF;
for(int i=0;i<n;i++)
{
if(L<=pos[i]&&pos[i]<=R)
{
ans*=(R-L+1-i);
ans%=mod;
}
L=min(L,pos[i]);
R=max(R,pos[i]);
}
cout<<ans<<endl;
return;
}
signed main()
{
int T;
cin>>T;
while(T--)
{
solve();
}
}
D
核心思路
首先我们从最简单的1 2 3 4 5 1，也就是想要把左右端点合为相同的需要些什么性质呢。性质1：必须得区间长度为偶数，
性质2就是某个数出现的最大的次数不可以是len/2,不然就删不掉。.这个性质其实可以很好理解因为我们最多也是需要一一配对才可以消掉。还是举一个例子吧，也就是1 1 1 2 3 1 。注意我们这里是求哪个区间可以完全删掉。
于是我们可以先预处理出来哪个左右区间可以当我们左右端点相同的时候左右端点合并，向上面的就是合为1 1.然后就是dp了。
集合定义：\(dp[i]为1\sim i这个区间的最大长度\)
集合划分：我们只需要找到i前面的一个点j，看是否区间[I+1,j-1]是可以删除的。
状态转移方程：\(dp[i]=max(dp[i],dp[j]+1)\).
// Problem: D. Almost Triple Deletions
// Contest: Codeforces - Codeforces Round #804 (Div. 2)
// URL: https://codeforces.com/contest/1699/problem/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define NO {puts("NO") ; return ;}
#define YES {puts("YES") ; return ;}
#define endl "\n"
//#define int long long
const int N=5e3+10;
int f[N][N],dp[N];
int a[N];
int n;
bool ok(int L,int R)//一定要清楚我们ok函数的含义，他是表示这段序列可不可以删除。
{
if(R-L+1<=0)//长度为0以及更加小肯定是可以删除的。
return 1;
else
return (R-L+1)%2==0&&f[L][R];
}
void solve()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for(int i=1;i<=n;i++)//f[L,R]表示这段区间是否可以删，但是他没有像ok那么具体。
{
int mx=0;
vector<int> cnt(n+1,0);
for(int j=i;j<=n;j++)
{
mx=max(mx,++cnt[a[j]]);
f[i][j]=(2*mx<=(j-i+1));
}
}
//dp的初始化。
memset(dp,-0x3f,sizeof dp);
for(int i=1;i<=n;i++)
{
if(ok(1,i-1))
dp[i]=1;//因为i-1的全都可以删除。
}
for(int j=1;j<=n;j++)
{
for(int i=j-1;i>=1;i--)
{
if(ok(i+1,j-1)&&a[i]==a[j])
{
dp[j]=max(dp[j],dp[i]+1);
}
}
}
int ans=0;
for(int j=1;j<=n;j++)
{
if(ok(j+1,n))//如果后面一段可以删除的话，那答案就是dp[j].
ans=max(ans,dp[j]);
}
cout<<ans<<endl;
return ;
}
signed main()
{
int T;
cin>>T;
while(T--)
{
solve();
}
}