CF每日4题（1300-1400）

2026B 贪心 1300

我的思路和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;
	}
}

2033E 思维 贪心 1400

题意：

• 原始数列两两调换位置，让每个数满足$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;

}

2013C 交互题 思维 1400

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

• 向后加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;
}

1967A 思维 贪心 1400

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

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;
}