前言
本场VP深感自己的弱小与史队的强大。
又一次被史队全方位暴打。
来做一个简要的总结。
正文
A. One and Two
A题日常的愚蠢。
考虑到原序列只含有质因子2。我们将质因子2平分给左右两边即可。当2的个数为奇数时即判断为无解。
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int t,n,a[N];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>t;
while(t--)
{
cin>>n;
int num=0;
for(int i=1;i<=n;i++)
{
cin>>a[i];
num+=(a[i]==2);
}
int s=0;
bool f=0;
for(int i=1;i<=n;i++)
{
s+=(a[i]==2);
if(s*2==num)
{
f=1;
cout<<i<<endl;
break;
}
}
if(f==0)
{
cout<<-1<<endl;
}
}
return 0;
}
B. Sum of Two Numbers
B题是煞笔题，被罚了2次，也是习惯了。
考虑到原问题关于数字和，我们考虑拆数。接着将数字和平分给两个数即可。
需要注意前缀0的细节问题。
代码：
#include<bits/stdc++.h>
using namespace std;
int t,n,a[11];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>t;
while(t--)
{
cin>>n;
int s=0,sum=0;
while(n!=0)
{
a[++s]=n%10;
sum+=a[s];
n/=10;
}
int k=sum/2;
if(sum%2==1)
k++;
for(int i=s;i>=1;i--)
{
if(k>=a[i])
{
k-=a[i];
cout<<a[i];
a[i]=0;
}
else
{
a[i]-=k;
cout<<k;
k=0;
}
}
cout<<" ";
bool f=0;
for(int i=s;i>=1;i--)
{
if(a[i]!=0||f==1)
{
f=1;
cout<<a[i];
}
}
if(f==0)
{
cout<<0;
}
cout<<endl;
}
return 0;
}
C. Matching Numbers
C题是一道简单的构造题，数感好的话一下就看出来了。
不过这里还是严谨的证明一下。
首先，不难发现原题是想让我们用 \([1,2n]\) 两两配对求和成一个公差唯一的等差数列。对于该等差数列而言，它的平均数为 \(\frac{2n(2n+1)}{2n}=2n+1\) 。这是个奇数，因此，显然只有当 \(n\) 为奇数时有解。
接着我们考虑构造，为了使结果相对的均衡，我们希望让结果呈现一个 \([1,n]\) 与 \([n+1,2n]\) 一一映射的局面。由于奇数与偶数本质不同，因此我们将他们分开讨论，且当 \(n\) 为奇数时，显然奇数多于偶数。因此我们用与 \([1,n]\) 中的奇数配对的答案表示答案序列中不小于 \(2n+1\) 的部分。偶数凡是。考虑到奇数偶数增长的速度都是2，想要构造公差为1的序列，朴素的方式是除以2来考虑。
代码：
#include<bits/stdc++.h>
using namespace std;
int t,n;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>t;
while(t--)
{
cin>>n;
if(n%2==0)
{
cout<<"NO"<<endl;
continue;
}
cout<<"YES"<<endl;
for(int i=1;i<=n;i++)
{
cout<<i<<" ";
int x=i/2;
if(i%2==1)
{
x++;
cout<<n*2-x+1;
}
else
{
int s=n/2;
cout<<n+(s-x+1);
}
cout<<endl;
}
}
return 0;
}
D. Moving Dots
再次无缘场切D题。
D是不擅长的计数，我发现我总是把计数题考虑得过于宏观。但其实本题的计数题套路非常常见。
我们考虑两个点在答案中产生贡献，当且仅当他们中间的点没有被选且他们异侧的点距离他们更远。
因此我们只需要枚举产生贡献的两个点，移除掉会影响他们的点，统计方案即可。若最终除他们外还剩 \(k\) 个点，贡献即为 \(2^k\)。
代码注意二分边界，以及lowerbound和upperbound的用法，最近总是搞错，警钟长鸣。
代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+100;
const int mod=1e9+7;
int n,a[N],pw[N],ans;
signed main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
a[n+1]=INT_MAX;
a[0]=INT_MIN;
pw[0]=1;
for(int i=1;i<=n;i++)
{
pw[i]=pw[i-1]*2;
pw[i]%=mod;
}
for(int i=1;i<n;i++)
{
for(int j=i+1;j<=n;j++)
{
int l=lower_bound(a+0,a+i+1,a[i]-(a[j]-a[i]))-a;
l--;
int r=lower_bound(a+j,a+2+n,a[j]+(a[j]-a[i]))-a;
ans+=(pw[l]*pw[n+1-r])%mod;
ans%=mod;
}
}
cout<<ans<<endl;
return 0;
}
E. Sum Over Zero
考虑本题的暴力dp做法，我们令 \(dp[i]\) 为前缀 \(i\) 的最大结果，令 \(sum[i]\) 表示前缀 \(i\) 的前缀和。对于 \(\forall j>i\)。若 \(sum[j]>=sum[i]\) 显然 \(dp[j]=max(dp[j],dp[i]+j-i)\) 显然我们只需要维护最大的 \(dp[i]-i\) 即可，这个显然可以用平衡树。反之，\(dp[j]=max(dp[j],dp[i])\) 这个可以暴力维护。
代码给出FHQ平衡数的写法：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+100;
int n,a[N],cnt,sum,ans,dp[N],root;
struct node{
int val,key,ls,rs,ts,mx;
}tree[N];
int nn(int x,int y)
{
tree[++cnt].key=rand();
tree[cnt].val=x;
tree[cnt].mx=tree[cnt].ts=y;
return cnt;
}
void update(int x)
{
tree[x].mx=max(tree[tree[x].ls].mx,tree[tree[x].rs].mx);
tree[x].mx=max(tree[x].mx,tree[x].ts);
return;
}
void split(int now,int val,int &x,int &y)
{
if(now==0)
x=y=0;
else
{
if(tree[now].val<=val)
{
x=now;
split(tree[now].rs,val,tree[now].rs,y);
}
else
{
y=now;
split(tree[now].ls,val,x,tree[now].ls);
}
update(now);
}
return;
}
int merge(int x,int y)
{
if(x==0||y==0)
return x+y;
if(tree[x].key<tree[y].key)
{
tree[x].rs=merge(tree[x].rs,y);
update(x);
return x;
}
else
{
tree[y].ls=merge(x,tree[y].ls);
update(y);
return y;
}
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n;
tree[0].mx=-1e9;
root=nn(0,0);
for(int i=1;i<=n;i++)
{
cin>>a[i];
sum+=a[i];
dp[i]=ans;
int x,y;
split(root,sum,x,y);
dp[i]=max(dp[i],i+tree[x].mx);
root=merge(merge(x,nn(sum,dp[i]-i)),y);
ans=max(ans,dp[i]);
}
cout<<dp[n];
return 0;
}