CF每日4题（1300-1400）

我的思路和dalao很像

void solve(){int n;cin>>n;vector<int>a(n+1);forr(i,1,n)cin>>a[i];int fg=(n&1),ans;if(fg){ans=1e18+10;forr(i,1,n){//枚举把一个数去掉，其他两两组合int tmp=1,j=1;while (j<=n){if(j==i)j++;int pre=a[j++];if(j==i)j++;if(j>n)break;int now=a[j++];if(j==i)j++;tmp=max(now-pre,tmp);}ans=min(ans,tmp);}cout<<ans<<endl;}else{ans=0;for(int i=2;i<=n;i+=2){ans=max(a[i]-a[i-1],ans);}cout<<ans<<endl;}
}

题意：

• 原始数列两两调换位置，让每个数满足$p_i=i,p_{p_i}=i$
• 就是下标$i$指向下标$p_i$，形成自己指自己、两个互指

思路：把题意抽象成环

• 交换就是改变一对儿边的指向，一个有x点的环要形成$\lceil \frac{x}{2}\rceil =\frac{x+1}{2}$个小环，需要变$\frac{x+1}{2}-1$条边

const int N=1e6+10;
//并查集
int fa[N],cnt[N];
int find(int x){if(fa[x]==x)return x;return fa[x]=find(fa[x]);
}
void merge(int x,int y){int fx=find(x),fy=find(y);if(fx==fy)return;if(x!=y)cnt[fx]+=cnt[fy],fa[fy]=fx;
}
void solve()
{int n;cin>>n;forr(i,1,n)fa[i]=i,cnt[i]=1;vector<int>p(n+1);forr(i,1,n){cin>>p[i];merge(i,p[i]);//建环}int ans=0;forr(i,1,n){if(fa[i]==i){ans+=(cnt[i]-1)/2;}}cout<<ans<<endl;}

注意找子串是在全串中匹配，一开始犯傻以为是从字符串首开始匹配的…

• 向后加0/1（加到厌倦），直到不是子串
• 不匹配后向前拓展，就得到了目标字符串

int query(string s){cout<<"? "<<s<<endl;cout.flush();int ans;cin>>ans;return ans;
}
void solve()
{int n;cin>>n;int len=0;string s="";//向后找while (len<n){if(query(s+'0')){s+='0';len++;continue;}if(query(s+'1')){s+='1';len++;continue;}else{break;//添1添0都不是子串 向后加的加完了}}//向前加while (len<n){if(query('0'+s)){s='0'+s;len++;continue;}s='1'+s;len++;}cout<<"! "<<s<<endl;
}

思路：最大化最小值，然后分配
最大化最小值怎么操作很犯难，于是看了题解

void solve()
{int n,k;cin>>n>>k;vector<int>a(n+1);forr(i,1,n)cin>>a[i];sort(a.begin()+1,a.end());int sum=0,rg,wst;forr(i,1,n){sum+=a[i];if(a[i]*i-sum<=k)rg=i,wst=a[i]*i-sum;}k-=wst;int div=k/rg;//剩下的再均分int rst=k%rg;//均分后剩下的int minn=a[rg]+div;//最大化的最小值 多个较少的值平均后相等// cout<<"!!!"<<endl;// forr(i,1,rg)cout<<minn<<' ';// forr(i,rg+1,n)cout<<a[i]<<' ';cout<<endl;// cout<<(minn-1)*n+1<<endl;//较少的值排列组合的贡献 末尾的一组只能贡献1个// cout<<n-rg<<endl;//较大的值剩下的// cout<<rst<<endl;//k分配完后剩下的// cout<<endl;cout<<(minn-1)*n+1+(n-rg+rst)<<endl;
}