Aising Programming Contest 2022（AtCoder Beginner Contest 255） - AtCoder

E - Lucky Numbers

题意: 给两个数组a,b，构成一个S数组，保证S[i]+S[i]+1==a[i],问S数组中出现的元素中，与b数组相同的最多有几个。

题解: 首先要知道，你确定了这个数组中的某一个值，那么其他的值也就确定了，所以，我们可以让最少有一个相同的，所以每个位置遍历b数组的几种数字。

首先我们构成一个第一位为0的S数组，然后可以发现，如果第一位+1,那么奇数位置都加一，偶数位置都减一，所以每次判断选择的数字和以0为开始的S数组的中你要替换的哪一项的差值，然后判断奇偶，记录一下即可。

#include
using namespace std;
typedef long long ll;
typedef pair pll;
const int N=2e5+5;
const ll inf=1e18;
const ll mod=998244353;
ll a[N],b[N],sum[N];
map mp;
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
ll n,m;cin>>n>>m;
for(ll i=1;i<=n-1;i++) cin>>a[i];
for(ll i=1;i<=m;i++) cin>>b[i];
for(ll i=2;i<=n;i++) sum[i]=a[i-1]-sum[i-1];
for(ll i=1;i<=n;i++)
for(ll j=1;j<=m;j++){
ll pt=sum[i]-b[j];//记录差值
if(i&1) pt*=-1;//判断奇偶
mp[pt]++;//存储
}
ll ans=-inf;
for(auto it:mp) ans=max(ans,it.second);
cout<<ans;
}

F - Pre-order and In-order

题意: 给出先序中序，判断能否构成一个根节点为1的树，能的话每个点的左右节点是多少

题解: 根据先序遍历找出对应元素在中序遍历的位置，对应的肯定是一个中点，然后分为左右两块遍历即可。

#include
using namespace std;
typedef long long ll;
typedef pair pll;
const int N=2e5+5;
const ll inf=1e18;
const ll mod=998244353;
ll f[N],mid[N];
ll cnt,idx[N];
ll ansl[N],ansr[N];
ll solve(ll l,ll r){
if(l>r) return 0;
cnt++;
ll p=f[cnt];ll pt=idx[p];
if(ptr){//判断是否越界
cout<<"-1";exit(0); } ansl[p]=solve(l,pt-1); ansr[p]=solve(pt+1,r); return p; } signed main(){ ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); ll n;cin>>n;
for(ll i=1;i<=n;i++) cin>>f[i];
for(ll i=1;i<=n;i++) { cin>>mid[i];idx[mid[i]]=i;}
if(f[1]!=1){
cout<<"-1";
return 0;
}
solve(1,n);
for(ll i=1;i<=n;i++){
cout<<ansl[i]<<" "<<ansr[i]<<endl;
}
}