cf 945 div.2 5/6

比赛地址：Dashboard - Codeforces Round 945 (Div. 2) - Codeforces

A

题意：三个人下棋，两两下棋，胜者2分负者0分，平局两人各得1分。现在告诉三人最终得分 $p_1\leq p_2\leq p_3$，求最多下了多少局。

首先 $p_1+p_2+p_3$ 要是一个偶数。

若 $p_3\geq p_1+p_2$ ，答案是 $p_1+p_2$ ，即前尽量多的平局。
否则，答案为 $p_3+(p_1+p_2-p_3)/2$ ，也是尽量多平局。

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        if((a+b+c)%2==1)
        {
            cout<<-1<<endl;
            continue;
        }
        if(a+b<=c)
        {
            cout<<a+b<<endl;
            continue;
        }
        cout<<c+(a+b-c)/2<<endl;
    }
}

B

题意：给一个长度为 $n$ 的数组 $a$ ，求最小的 $k$ 使得任意 $k$ 个连续元素的或操作结果相等。

考虑每一位。

若某一位全是0，那么这一位不予考虑。否则，求出所有元素这一位上最大的两个1之间的间隔更新答案。注意边界细节。

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        int a[n+2];
        for(int i=1;i<=n;i++)cin>>a[i];
        int ans=0;
        for(int p=0;p<20;p++)
        {
            int pre=0;
            int now=0;
            for(int i=1;i<=n;i++)
            {
                if( (a[i]>>p) & 1 )
                {
                    now=i;

                    ans=max(ans,now-pre);
                    // cout<<p<<" "<<i<<" "<<now<<" "<<pre<<endl;
                    pre=now;
                }
                
            }
            if(pre)
            {
                ans=max(ans,n+1-pre);
                // cout<<11<<" "<<ans<<endl;
            }
        }

        cout<<(ans==0?1:ans)<<endl;
    }
}

位运算

C

题意：给出一个长度为 $n$ 的全排列 $p$ ，长度为偶数，现在需要构造另一个长度为 $n$ 的全排列 $q$ ，并令数组 $a_i=p_i+q_i$ ，使数组 $a$ 中满足 $a_i>a_{i-1},a_i>a_{i+1},1<i<n$ 的元素最多。

即要么使奇数位上的值更大或者使偶数位上的值最大，最大的个数为 $n/2-1$ 。

注意到只能使不含1的奇数或偶数位上最大，具体操作为：先给目标位安排 $n/2\sim n$ ，小的对应大的，再给非目标位安排 $1\sim n/2-1$ 。这样可以使得目标位上最小的 $a_i=2+n$ ，而非目标位上的最大值为 $n+1$ ，满足了所有目标位都大于非目标位。

#include<bits/stdc++.h>
using namespace std;

int n,a[100005],cnt=0,ans[100005];

struct node
{
	int val,id;
}b[100005];

bool cmp(node x,node y)
{
	return x.val<y.val;
}
void solve()
{
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	bool f=0;
	for(int i=1;i<=n;i+=2)
    {
		if(a[i]==1)
        {//有1
			f=1;
			break;
		}
	}

	if(f)
    {//偶数位
		cnt=0;
		for(int i=2;i<=n;i+=2)
        {//满足条件
			cnt++;
			b[cnt].val=a[i];
			b[cnt].id=i;
		}
		sort(b+1,b+1+cnt,cmp);//排序
		int tot=n;
		for(int i=1;i<=cnt;i++)
        {//填数
			ans[b[i].id]=tot;
			tot--;//自减
		}
		cnt=0;
		for(int i=1;i<=n;i+=2)
        {//剩下的数
			cnt++;
			b[cnt].val=a[i];
			b[cnt].id=i;
		}
		sort(b+1,b+1+cnt,cmp);//排序
		for(int i=1;i<=cnt;i++)
        {//填数
			ans[b[i].id]=tot;
			tot--;//自减
		}
	}
    
    else
    {//奇数位，过程同上
		cnt=0;
		for(int i=1;i<=n;i+=2)
        {
			cnt++;
			b[cnt].val=a[i];
			b[cnt].id=i;
		}
		sort(b+1,b+1+cnt,cmp);
		int tot=n;
		for(int i=1;i<=cnt;i++)
        {
			ans[b[i].id]=tot;
			tot--;
		}
		cnt=0;
		for(int i=2;i<=n;i+=2)
        {
			cnt++;
			b[cnt].val=a[i];
			b[cnt].id=i;
		}
		sort(b+1,b+1+cnt,cmp);
		for(int i=1;i<=cnt;i++)
        {
			ans[b[i].id]=tot;
			tot--;
		}
	}
	for(int i=1;i<=n;i++) cout<<ans[i]<<' ';//输出
	puts("");
}
int main(){
	int t;
	cin>>t;
	while(t--) solve();
    return 0;
}

math

D

题意：交互题。定义 $f(l,r)=(r-l+1)\times max_l^ra_i$ 有一个长度为 $n$ 的隐藏数组，每个元素不超过 $n$ 每次询问 $?\ l\ x$ ，表示查询最小的 $r$ 使得 $f(l,r)=x$ ，若不存在则返回 $n+1$ 。最多询问 $2n$ 次。给定 $k$ ，要求将数组 $a$ 分成 $k$ 段后每一段的 $f$ 都相等，在询问后求出这个最小的 $f$ 。

观察到每一段的答案一定是隐藏数组中最大值的倍数。因此第一步是查找数组中最大的数。使用 $n$ 次查询：每次查询 $?\ 1\ i\times n$ 。
找到最大的值 $mx$ 之后，可以得到若答案为 $mx\times i$ ，那么一定有 $i\times k\leq n$ ，即答案有范围：$ans\leq mx\times \lfloor n/k\rfloor$ 。那么就可以在 $n$ 次内询问出答案。

#include <bits/stdc++.h>
using namespace std;

 
void answer(int x) {
    cout<<"! "<<x<<'\n'; cout.flush(); cin>>x;
}
 
void solve() {
 
    int n,k; cin>>n>>k;
    int mx=0;
    for(int i=1; i<=n; ++i) {
        cout<<"? 1 "<<i*n<<'\n'; cout.flush();
        int x; cin>>x;
        if (x==n) {
            mx=i; break;
        }
    }
    for(int c=mx*(n/k); ; c-=mx) {
        if (!c) {
            answer(-1); return;
        }
        int l=0;
        int bad=0;
        for(int it=0;it<k;it++) {
            if (l>=n) {bad=1; break;}
            cout<<"? "<<l+1<<' '<<c<<'\n'; cout.flush();
            int x; cin>>x;
            l=x;
        }
        if (bad) continue;
        if (l!=n) continue;
        answer(c); return;
    }
 
}
 
int32_t main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int t=1; 
    cin>>t;
    while (t--) solve();
    return 0;
}

E

题意：给定一个 $n$ 全排列，现在要使其递增，每次只能交换两个元素，且需满足：$l\leq a_i+a_j\leq r$，其中 $1\leq l\leq r\leq 2n$ 。求 $l,r$ 有多少种组合。

首先考虑特殊情况 $l=r$ 。只用需要调换的元素和全都一样时才会有 $l=r$ 。

一般情况下，首先找出所有 $a_i!=i$ 的元素，可以得到必要条件 $l\leq min\ a+n,r\geq max\ a+1$ 。其实这也是充分条件。

$proof$ ：对于任意不等于 $n$ 的 $x$ ，可以找到满足 $l\leq y<r$ 的 $y$ ，构造 $tx=y-x$ ，可以通过分别交换 $x\ tx,\ tx\ x+1,\ tx\ x$ 实现将 $x$ 与 $x+1$ 交换位置，且其他元素不变，且满足 $l,r$ 条件。

因为一定可以通过交换 $x$ 与 $x-1$ 来使得数列有序（找第一个 $a_i!=i$ 的元素，将其与 $a_i-1$ 交换，循环），所以最后的条件就是 $l\leq min\ a+n,r\geq max\ a+1$ ，接下来统计答案即可。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,t,a[100005];
signed main() 
{
    cin>>t;
    while(t--)
    {
		cin >> n;
		int l = -1,r = -1,ans = 0,flag = 0;
		for(int i = 1;i <= n;i++) cin >> a[i];
		for(int i = 1;i <= n;i++) 
			if(a[i] != i) 
            {
				if(flag == -1) break;
				if(flag == 0) flag = a[i] + i;
				else if(flag != a[i] + i) flag = -1;
			} 


		for(int i = 1;i <= n;i++) if(a[i] != i) r = i;
		for(int i = n;i >= 1;i--) if(a[i] != i) l = i;

		if(l == -1) l = 2 * n,r = 1;
		else l = l + n,r = r + 1;

		for(int i = r;i <= 2 * n;i++)
			ans += min(i - 1,l);

		if(flag == 0) ans += 2 * n;
		if(flag > 0) ans += 1;
		cout << ans << endl; 
	}
	return 0;
}

math