A. Tales of a Sort
题意：给出一个长为n的数组a，每次操作可以使得所有的数-1，最小不会小于0，问至少需要多少次操作才能使得a变得有序。
Solution
把数组a排序，从大到小遍历，如果当前的\(a[i]\)不是原来的话，那么要想让它有序，必须进行当前的\(a[i]\)次操作，这样才能使得它有序
void solve()
{
int n;cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)b[i]=a[i];
sort(b+1,b+1+n);
int flag=1;
int maxx=0;
for(int i=1;i<n;i++)
{
maxx=max(a[i],maxx);
if(a[i+1]<a[i])
{
flag=0;
break;
}
}
if(flag)
{
cout<<"0\n";
return;
}
maxx=max(maxx,a[n]);
for(int i=n;i>=1;i--)
{
if(a[i]!=b[i])
{
cout<<b[i]<<"\n";
return;
}
}
}
B. Good Arrays
题意：给出一个长为n的正整数数组a，定义一个长为n的正整数数组b为好数组有以下的条件：
1.\(a_i \neq b_i(1\leq i \leq n)\)
2.\(\sum_{i=1}^{n}a_i = \sum_{i=1}^{n}b_i\)
问这样的数组是否存在
Solution
我们可以考虑把原来的数组中所有大于1的数变为1，所有等于1的数变为2，这样可以满足第一个条件，然后再给2加数看是否能满足第二个条件即可。
void solve()
{
int n;cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
if(n==1)
{
cout<<"NO\n";
return;
}
int cnt0=0,cnt1=0;
for(int i=1;i<=n;i++)
{
if(a[i]==1)cnt1++;
else cnt0+=a[i]-1;
}
if(cnt0<cnt1)cout<<"NO\n";
else cout<<"YES\n";
}
C. To Become Max
题意：给出一个长为n的数组a，每次可以进行以下操作：
选定一个\(i\)，满足\(a_i \leq a_{i+1}(1\leq i \leq n-1)\)，然后给\(a_i\)+1
问最多进行k次操作后的数组中的最大值
Solution
二分+枚举区间
假设我们可以进行无限次操作，那么每个数最后会有一个最大值，先预处理出来，然后我们可以发现，要想让\(a_i\)变为某个最大值\(x\)，后面的数至少也得是\(x-1\)，所以在枚举区间的时候判断当前区间后面那个值是否大于等于\((x-区间长度)\)即可
bool check(int x)
{
//cout<<x<<"\n";
for(int i=1;i<=n;i++)
{
int sum=0,flag=1;
int temp=x;
for(int j=i;j<n;j++)
{
if(b[j]<temp)
{
flag=0;
}else
{
sum+=temp-a[j];
temp--;
}
//cout<<j<<" "<<sum<<"\n";
if(flag&&sum<=k&&(temp<=a[j+1]))return true;
else if(sum>k||!flag)break;
}
//if(flag&&sum<=k)return true;
}
return false;
}
void solve()
{
cin>>n>>k;
for(int i=1;i<=n;i++)cin>>a[i];
int maxx=0;
for(int i=1;i<=n;i++)
{
maxx=max(maxx,a[i]);
}
b[n]=a[n];
for(int i=n-1;i>=1;i--)
{
if(b[i+1]>=a[i])b[i]=b[i+1]+1;
else b[i]=a[i];
}
//for(int i=1;i<n;i++)cout<<b[i]<<" \n"[i==n-1];
int l=maxx,r=maxx+k;
while(l<r)
{
int mid=(l+r+1)>>1;
if(check(mid))l=mid;
else r=mid-1;
}
cout<<l<<"\n";
}
D. More Wrong
题意：交互题，有一个长度为 \(n\) 的排列，每次可以进行查询，查询会选定一个区间\([l,r]\)，返回其中的逆序对个数，花费为\((r-l)^2\)，在花费不超过\(5n^2\)的情况下找到 \(n\) 的位置
Solution
考虑查询区间\([l,r]\)和\([l,r+1]\)，得到的逆序对个数为\(cnt1\)和\(cnt2\)
如果有\(cnt1<cnt2\)，说明\(a[l]>a[r+1]\)
所以我们可以分治法找最大值
int ask(int l,int r)
{
cout<<"? "<<l<<" "<<r<<endl;
int x;cin>>x;
return x;
}
int getmax(int l,int r)
{
if(l==r)return l;
int mid=(l+r)>>1;
int mx1=getmax(l,mid),mx2=getmax(mid+1,r);
int x,y;
if(mx1==mx2-1)x=0;
else x=ask(mx1,mx2-1);
y=ask(mx1,mx2);
if(x<y)return mx1;
else return mx2;
}
void solve()
{
int n;cin>>n;
int ans=getmax(1,n);
cout<<"! "<<ans<<endl;
}
E1. PermuTree (easy version)
题意：给一颗以\(1\)为根节点的树，在上面摆放\(1,2,...,n\)，问满足\(a_u \le a_{lca(u,v)} \le a_v\)的\((u,v)\)对数最大是多少
Solution
考虑到题目条件，对于一颗树的贡献，我们发现最好的情况是其子树要么全放比根节点大的，要么全放小的，它的贡献即为(小的子树大小之和)与(大的子树大小之和)的乘积，要最大化这个乘积，就必须使得这两个数尽可能大小相同，这就是一个树上01背包问题，假设子树大小之和为\(n\)，那么答案要尽可能向\(n/2\)靠近，以最大化乘积
vector<int>e[N];
int dp[N];
int ans=0;
void dfs(int x,int pre)
{
dp[x]=1;
vector<int>v;
for(auto it:e[x])
{
if(it==pre)continue;
dfs(it,x);
dp[x]+=dp[it];
v.push_back(dp[it]);
}
if(v.size()==1)return;
sort(v.begin(),v.end());
int sum=0;
int res=0;
int tar=(dp[x]-1)/2;
vector<int>f(tar+1);
for(int i=0;i<v.size();i++)
{
for(int j=tar;j>=v[i];j--)
{
f[j]=max(f[j],f[j-v[i]]+v[i]);
}
}
for(int i=0;i<=tar;i++)res=max(res,f[i]*(dp[x]-1-f[i]));
ans+=res;
}
void solve()
{
int n;cin>>n;
for(int i=1;i<n;i++)
{
int x;cin>>x;
e[x].push_back(i+1);
//e[i+1].push_back(x);
}
dfs(1,0);
cout<<ans<<"\n";
}