思路：
1.当序列为已排序状态.则无论怎么操作都是有序的.
2.序列是无序的存在一个 三元组$i<j<k$
满足$a_i >a_j<a_k$
或者$a_i < a_j > a_k$
显然选择$[1,i]$或者$[1,j]$即满足题目要求.
因此答案就是判断原序列是否非降序即可.
AC Code：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>PII;
typedef unsigned long long ull;
const int M=2010;
const ll llINF=0x3f3f3f3f3f3f3f3f;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const int N=2e6+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
void solve()
{
int n;cin>>n;
vector<int>a(n+1);
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=2;i<=n;i++)
{
if(a[i]<a[i-1])
{
cout<<"Yes"<<endl;
return;
}
}
cout<<"No"<<endl;
return ;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// freopen("test.in","r",stdin);
int t;cin>>t;
while(t--)solve();
return 0;
}
时间复杂度$O(n)$
B. MEX and Array
思路:
通过观察可以发现每次分隔的时候将每一个数自己构成一个区间就是最优的.
因此只需要计算每一个数对于$ans$的贡献是多少然后累加即可.
AC Code：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>PII;
typedef unsigned long long ull;
const int M=2010;
const ll llINF=0x3f3f3f3f3f3f3f3f;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const int N=2e6+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
void solve()
{
int n;cin>>n;
vector<int>a(n+1);
for(int i=1;i<=n;i++)cin>>a[i];
int ans=0;//n^2-> (1+(x!=0))*n^2
for(int i=1;i<=n;i++)
{
int len1=max(0,i-1);
int len2=max(0,n-i);
ans+=(1+(a[i]==0))*(len1+1)*(len2+1);
}//n n-1 n-3 .....
// 1 2 2
cout<<ans<<endl;
return ;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// freopen("test.in","r",stdin);
int t;cin>>t;
while(t--)solve();
return 0;
}
C. Andrew and Stones
思路:
1.首先手写下样例可以发现无论中间构成是什么样的基本上都可以实现操作
2.因此只需要考虑特殊的不能实现的样例即可
分别是全1的：这样每一个数都不能帮助其他的数.
或 长度为3,且中间是奇数:这样中间的数也无法被其他数帮助到.
AC Code:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>PII;
typedef unsigned long long ull;
const int M=2010;
const ll llINF=0x3f3f3f3f3f3f3f3f;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const int N=2e6+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
void solve()
{
int n;cin>>n;
vector<ll>a(n+1);
for(int i=1;i<=n;i++)cin>>a[i];
bool flag1=false;
for(int i=2;i<=n-1;i++)
if(a[i]!=1)flag1=true;
if(n==3&&a[2]%2!=0||!flag1)
{
cout<<"-1"<<endl;
return;
}else
{
for(int i=1;i<=n;i++)a[i]++;
ll ans=0;
for(int i=2;i<=n-1;i++)ans+=a[i]/2;
cout<<ans<<endl;
}
return ;
}//1 5 7 5 1
// 2 3 8 5 1
// 3 1 8 6 1
// 4 2 6 6 1
//
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// freopen("test.in","r",stdin);
int t;cin>>t;
while(t--)solve();
return 0;
}
D. Yet Another Minimization Problem
思路:
首先肯定化简式子,暴力来莽肯定不行$2^{100}$显然是不行的
解释下为什么要化简,尝试了一下不化简硬莽,发现有大问题。
最开始想用状态机 直接记录是否 交换。交换的话回传一下影响就行了。
但发现第i次决策的时候完全是无法确定其交换后的影响应该回传给谁。
因为每次决策是有后效性的。因此不拆分式子用状态机显然是不行的
以$a$数组为例,由于$a,b$数组式子是一样的化简一个就行了.
$\sum_{i=1}^{n} \sum_{j=i + 1}^{n} (a_i + a_j)^2 = \sum_{i=1}^{n} \sum_{j=i + 1}^{n} (a_i^2 + a_j^2 + 2a_i a_j)$
$cost = (n - 1) \cdot \sum_{i=1}^{n} a_i^2 + \sum_{i=1}^n (a_i \cdot (s - a_i)) = (n - 1) \cdot \sum_{i=1}^{n} a_i^2 + s^2 - \sum_{i=1}^{n} a_i^2 = (n - 2) \cdot \sum_{i=1}^{n} a_i^2 + (\sum_{i=1}^n a_i)^2$
化简完合并下$a,b$两个式子.放在一起观察$ans$
$(n - 2) \cdot \sum_{i=1}^{n} (a_i^2 + b_i^2) + (\sum_{i=1}^n a_i)^2 + (\sum_{i=1}^n b_i)^2$
这里很明显的可以发现除去前缀的平方和,另外那个式子是否交换位置是无影响的.可以看成常数。
因此最后我们就变成了找到下面这个式子的最小值:
$(\sum_{i=1}^n a_i)^2 + (\sum_{i=1}^n b_i)^2$
前面说过了,状态机肯定不行有后效性.
因此考虑记录下所有$a$数组前缀的所有可能值即可。
得到$a$的所有可能镜象的考虑b用下式子可以得到$ans$了.
具体的类似分组背包看代码就行了.
$DP[i][j]$表示的是前缀$S_i$值为j是否可能。
转移就一定是$DP[i][j]=DP[i-1][j-a[i]]|DP[i-1][j-b[i]]$
因为前缀只可能由前一个位置递推过来不可能说直接由前面其他的位置跳过来,那样的话从该位置到$i$中间的数值必须是0,而因为$a[i]\geq 1$因此该转移是没问题的
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>PII;
typedef unsigned long long ull;
const int M=2010;
const ll llINF=0x3f3f3f3f3f3f3f3f;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const int N=2e6+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
bool dp[110][10010];//dp[i][j]表示对a数组而言从前i个数中选能否构成前缀和为j的方案
void solve()
{
memset(dp,false,sizeof dp);
int n;cin>>n;
vector<int>a(n+1);
vector<int>b(n+1);
int sum=0;
int cnt=0;
for(int i=1;i<=n;i++)cin>>a[i],sum+=a[i],cnt+=a[i]*a[i];
for(int i=1;i<=n;i++)cin>>b[i],sum+=b[i],cnt+=b[i]*b[i];
if(n==1)
{
cout<<0<<endl;
return;
}
dp[1][a[1]]=true;
dp[1][b[1]]=true;//初始化
for(int i=2;i<=n;i++)
{
for(int j=i;j<=sum;j++)
{
if(j-a[i]>=1)dp[i][j]|=dp[i-1][j-a[i]];
if(j-b[i]>=1)dp[i][j]|=dp[i-1][j-b[i]];//两种可能
}
}//得到a的前缀所有可能方案后对称的就可以直接O(1)的得到b的方案
/* for(int i=1;i<=n;i++)
{
for(int j=i;j<=sum;j++)
if(dp[i][j])cout<<"dp["<<i<<"]"<<"["<<j<<"]"<<endl;
}*/
int ans=INF;
/* cout<<cnt<<endl;
cout<<(n-2)*cnt+(18*18)+17*17<<endl;*/
// cout<<sum<<endl;
for(int i=n;i<=sum;i++)
{
if(!dp[n][i])continue;
int sa=i,sb=sum-i;//dpn][i]方案存在
int res=(n-2)*cnt+sa*sa+sb*sb;
ans=min(res,ans);
}
cout<<ans<<endl;
return ;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
freopen("test.in","r",stdin);
int t;cin>>t;
while(t--)solve();
return 0;
}
