A~E题

A题

先找到>=l的最小x的倍数再判断是否<=r

或者先找到<=r的最大x的倍数再判断是否>=l都可以

void solved()
{
	int l,r,x;
	cin>>l>>r>>x;
	int mi=(l+x-1)/x*x;//>=l的最小x的倍数
	cout<<(mi<=r?mi:-1);
	
// 	int ma=r/x*x;//<=r的最大x的倍数 
// 	cout<<(ma>=l?ma:-1);
}

B题

满足条件的最短长度区间[x,n*x]往左右两边扩

左边右边均最多扩x-1长度

注意需要开longlong

void solved()
{
    int n,k,x;
    cin>>n>>k>>x;
    
    int len=(n-1)*x+1;//满足条件的最短长度区间[x,n*x] 
    if(k>=len && k<=len+2*(x-1))
    {
    	if(k<=len+x-1)cout<<x-(k-len)<<' '<<n*x<<'\n';//仅扩展左边 
    	else cout<<x-(k-len-(x-1))<<' '<<n*x+x-1<<'\n';//左右都扩展 
	}
	else cout<<-1<<'\n';
}

C题：构造

无解情况：因为是n个数的排列，所以前n个数一定是排列，故最后一个字符必须为'1'，否则就无解

考虑其他情况：一种构造方法是先构造数组a=1,2,3,...n的排列，然后对于每个'1'左边如果存在0子串，则与前面0子串最左边的0交换a值，其他情况a值不变即可

void solved()
{
    int n;cin>>n;
    string s;cin>>s;s=" "+s;
    
    if(s[n]=='0')//答案不存在 
    {
    	cout<<-1;
    	return ;
	}
    
    vector<int> a(n+1);
    for(int i=1;i<=n;i++)a[i]=i;//初值
    
    int pre0=0;//当前位置左边0子串的最左边0的下标（pre0=0表示左边不存在0子串） 
    for(int i=1;i<=n;i++)
    {
        if(pre0==0 && s[i]=='0')pre0=i;
        if(s[i]=='1' && pre0)swap(a[i],a[pre0]),pre0=0; 
    }
    for(int i=1;i<=n;i++)cout<<a[i]<<' ';
}

D题：双指针（滑动窗口）

  1. 设当前区间为[l,r]，区间中的01子序列为x个
  2. 考虑相邻区间[l,r+1]，区间中01子序列一定>=x个
  3. 考虑相邻区间[l+1,r]，区间中01子序列一定<=x个

根据相邻区间答案具有单调性我们使用滑动窗口来实现

当前区间01子序列数x<k时就向右扩展右端点使x变大，看是否能使x==k，x>k就退出

当前区间01子序列数x>k时就向右扩展左端点使x变小，看是否能使x==k，x<k就退出

建议这种滑动窗口的题用队列实现，而不用原始的双指针实现，这样会简单很多不容易出错，其本质都是一样的

void solved()
{
	int n,k;cin>>n>>k;
	string s;cin>>s;s=" "+s;
	
	queue<int> q;
	int cnt0=0,cnt1=0,x=0;//x为当前01子序列数 
	for(int i=1;i<=n;i++)
	{
	    q.push(i);//加入队列 
	    if(s[i]=='1')x+=cnt0,cnt1++;
	    else cnt0++;
	    
	    while(q.size() && x>k)
	    {
	        int x=q.front();q.pop();
	        if(s[x]=='0')sum-=cnt1,cnt0--;
	        else cnt1--;
	    }
	    
	    if(sum==k) 
	    {
	        cout<<q.front()<<' '<<q.back();//输出左端点和右端点 
	        return ;
	    }
	}
    cout<<-1;
}

E题：01背包

赛时没注意，以为不能有重边，百分之八十多一直没调出来QAQ

  1. 设度数之和为sum
  2. sum==2*边数：所以度数之和不能为奇数
  3. sum为偶数情况下，二分图必须满足左边点度数和==右边点度数和==sum/2，可以理解为sum/2条边来连接两边

所以问题就变成了n个点中能否挑一些出来度数和为sum/2（剩下的点度数也为sum/2）

思路过程：跑01背包-->跟踪一种解-->暴力连边**

void solved()
{
    int n;cin>>n;
    vector<int> d(n+1);
    
    int sum=0;
    for(int i=1;i<=n;i++)cin>>d[i],sum+=d[i];
    
    if(sum&1)//特判:度数之和不能为奇数
    {
        cout<<-1;
        return ;
    }
    
    //定义状态f[i][j]:前i个中选,度数和恰好为j的最多个数 (最少个数也行)
    //ff数组用来跟踪解，ff[i][j]:当前的f[i][j]是否选了第i个数(0表示没选,1表示选了)
    vector<vector<int>> f(n+1,vector<int> (sum/2+1,-1e9));
    vector<vector<int>> ff(n+1,vector<int> (sum/2+1,0));
    for(int i=0;i<=n;i++)f[i][0]=0;//注意初值
    
    for(int i=1;i<=n;i++)//跑01背包
        for(int j=1;j<=sum/2;j++)
        {
            if(j>=d[i] && f[i-1][j]<=f[i-1][j-d[i]]+1)f[i][j]=f[i-1][j-d[i]]+1,ff[i][j]=1;//选
            else f[i][j]=f[i-1][j];//不选
        }
    
    int cnt=0;
    vector<int> l,r;
    if(f[n][sum/2]<=0)//无解：找不到一种组合使得度数和为sum/2
    {
        cout<<-1;
        return ;
    }
    else//有解
    {
        int now=sum/2;
        for(int i=n;i>=1;i--)//跟踪解
        {
            if(ff[i][now])l.push_back(i),now-=d[i],cnt+=d[i];//选了放左边
            else r.push_back(i);//没选放右边
        }
    }
    
    cout<<cnt<<'\n';
    for(int lx:l)//已知左边点集l和右边点集r情况下直接暴力连边即可
        for(int rx:r)
        {
            int z=min(d[lx],d[rx]);
            d[lx]-=z,d[rx]-=z;
            while(z--)cout<<lx<<' '<<rx<<'\n';
        }
}