好像还有好多没写的
A. Mortis
赛时思路是正解，但有一个判断想了但出锅了。。。
\(n\) 个数的序列 \(n-1\) 次肯定能换完，一次操作最多贡献 2，找出贡献2的操作个数减去即可
有一次操作匹配两个，两次操作匹配三个，三个操作匹配四个，三种情况，记个数都跑一遍即可
点击查看代码
#include<bits/stdc++.h>
const int maxn=2e5+10;
using namespace std;
int n,a[maxn],l[10],r[10],cnt[10][10],sum[10],ans,x,z;
int main()
{
// freopen("sample.in","r",stdin);
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
sum[a[i]]++;
}
for(int i=1;i<=4;i++)
{
if(sum[i])
{
l[i]=r[i-1]+1;
r[i]=l[i]+sum[i]-1;
}
else
{
r[i]=r[i-1];
l[i]=r[i]+1;
}
}
// cout<<r[4]<<endl;
for(int i=1;i<=4;i++)
{
for(int j=l[i];j<=r[i];j++)
{
if(sum[i])cnt[i][a[j]]++;
}
}
// int c=0;
// for(int i=1;i<=4;i++)
// for(int j=i;j<=4;j++)c+=cnt[i][j];
// cout<<c<<endl;
int o=0;
ans=n-1;
for(int i=1;i<=4;i++)x+=cnt[i][i];
for(int i=1;i<=4;i++)
{
for(int j=i;j<=4;j++)
{
if(sum[i]>0&&sum[j]>0)
{
int f=min(cnt[i][j],cnt[j][i]);
o+=f;
ans-=f;
cnt[i][j]-=f;
if(i!=j)cnt[j][i]-=f;
// cout<<cnt[i][j]<<" "<<cnt[j][i]<<endl;
}
}
}
// for(int i=1;i<=4;i++)
// for(int j=1;j<=4;j++)
// cout<<cnt[i][j]<<" ";
for(int i=1;i<=4;i++)
{
for(int j=1;j<=4;j++)
{
for(int k=1;k<=4;k++)
{
int f=min(min(cnt[i][j],cnt[j][k]),cnt[k][i]);
ans-=f;
z+=f;
cnt[i][j]-=f;
cnt[j][k]-=f;
cnt[k][i]-=f;
}
}
}
int u=0;
for(int i=1;i<=4;i++)
for(int j=1;j<=4;j++)
for(int k=1;k<=4;k++)
for(int e=1;e<=4;e++)
{
int f=min(min(cnt[i][j],cnt[j][k]),min(cnt[k][e],cnt[e][i]));
ans-=f;
u+=f;
cnt[i][j]-=f;
cnt[j][k]-=f;
cnt[k][e]-=f;
cnt[e][i]-=f;
}
// for(int i=1;i<=4;i++)
// for(int j=1;j<=4;j++)
// cout<<cnt[i][j]<<" ";
// cout<<n<<" "<<ans<<" "<<z<<" "<<o<<endl;
// cout<<(n+u-1-x-ans)*2+x+z<<endl;
if((n+u-1-x-ans)*2+x+z==n)ans++;
cout<<ans;
return 0;
}
/*
13
3 3 1 1 1 3 3 3 4 2 4 2 2
*/
C. 嘉然今天吃什么
我感觉我现在急需一个数据结构大佬来传授一下代码能力。。
赛事我打完暴力，开始考虑最大值的贡献，发现只需要找一个链上的最大值即可，然后我就开始想如何 \(log n\) 内求出
最大值，但我只会 \(n^2\) 的。。。很恼，讲 \(trie\) 树时基本没听，根本没想起来有这玩意。。。
用 \(0,1,trie\) 树，每次把除了这个点子树之外的点都插入 \(trie\) 树，倒着遍历可以使每个点只插一次，直接查即可
点击查看代码
#include<bits/stdc++.h>
#define ll long long
const int maxn=5e5+10;
using namespace std;
int n,head[maxn],to[maxn],nxt[maxn],tot,cnt;
int t[maxn*65][2],fa[maxn];
ll a[maxn],now,ans[maxn];
inline void add(int x,int y)
{
to[++tot]=y;
nxt[tot]=head[x];
head[x]=tot;
}
void insert(ll x)
{
int p=0;
for(int i=63;i>=0;i--)
{
int c=x>>i&1;
if(!t[p][c])t[p][c]=++cnt;
p=t[p][c];
}
}
ll query(ll x)
{
ll res=0,p=0;
for(int i=63;i>=0;i--)
{
int c=x>>i&1;
if(t[p][c^1])res=res*2+1,p=t[p][c^1];
else res=res*2,p=t[p][c];
}
if(res>now)now=res;
return res;
}
inline void lsx(int x)
{
insert(a[x]);
query(a[x]);
for(int i=head[x];i;i=nxt[i])
{
int y=to[i];
lsx(y);
}
}
void dfs(int u,int p)
{
if(!u)return ;
dfs(fa[u],u);
// cout<<u<<" "<<now<<"!"<<endl;
ans[u]=now;
insert(a[u]);
query(a[u]);
for(int i=head[u];i;i=nxt[i])
{
int y=to[i];
if(y!=p)lsx(y);
}
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n;
fill(ans+1,ans+1+n,-1);
for(int i=1;i<n;i++)
{
int x;
cin>>x;
fa[i+1]=x;
add(x,i+1);
}
for(int i=1;i<=n;i++)cin>>a[i],insert(a[i]);
ll x=0,y=0,res=0;
for(int i=1;i<=n;i++)
{
ll temp=query(a[i]);
if (temp>res)
{
res=temp;
x=a[i],y=temp^a[i];
}
}
ll xx=0,yy=0;
for(int i=1;i<=n;i++)
if(a[i]==x) xx=i;
else if(a[i]==y) yy=i;
memset(t,0,sizeof t),cnt=0,now=0;
dfs(xx,0);
memset(t,0,sizeof t),cnt=0,now=0;
dfs(yy,0);
for(int i=1;i<=n;i++)
cout<<(ans[i]>=0?ans[i]:res)<<'\n';
return 0;
}