20250808组题总结

A - A

Pak Chanek 有一个包含 $n$ 个正整数的数组$a$。由于他正在学习如何计算两个数字的向下取整平均值，他希望在他的数组 $a$ 上进行练习。当数组 $a$ 至少有两个元素时，Pak Chanek 将执行以下三步操作：

$\bullet$选择两个不同的索引 $i$ 和 $j(1\le i,j\le \mid a\mid ;i\ne j)$，注意 $\mid a\mid$ 表示数组 $a$ 的当前大小。

$\bullet$将 $\lfloor \frac{2a_i+a_j}{2}\rfloor$∗ 附加到数组的末尾。

$\bullet$从数组中移除元素 $a_i$ 和 $a_j$并连接数组的剩余部分。

例如，假设 $a=[5,4,3,2,1,1]$ 。如果我们选择 $i=1$ 和 $j=5$ ，则结果数组将是 $a=[4,3,2,1,3]$ 。如果我们选择 $i=4$ 和 $j=3$ ，则结果数组将是 $a=[5,4,1,1,2]$。

在所有操作完成后，数组将只包含一个元素 $x$。如果 Pak Chanek 进行最佳操作，找出 $x$ 的最大可能值。

∗ $\lfloor x\rfloor$ 表示 $x$ 的向下取整函数，即小于或等于 $x$ 的最大整数。例如，$\lfloor 6\rfloor =6、\lfloor 2.5\rfloor =2、\lfloor -3.6\rfloor =-4$ 和 $\lfloor \pi \rfloor =3$

找规律，可以通过打表发现，只要每次把两个最小的元素合并起来，就能使最终的答案最大化。

那怎么找到最小的两个值呢？怎么把合并的值放到末尾呢？怎么删除选中的两个值呢？这里我们可以偷个懒，因为要合并$n-1$次，我们就循坏$n-1$次，每次先把$a$数组排一遍升序，我们就锁定了两个最小值。

现在是最关键的时刻，虽然题目说每次会把合并之后的结果放在数组的末尾，但下一次循环我们还是会排序，所以先把它放在$a[1]$，由于每次操作$a$数组的最后一项都会蹿到前面去，所以我们就先把它放在$a[2]$。

这样我们就完美的删除了选中的两个数，并保留了$a$数组的其余项和选中的两个数合并之后的结果。

#include<bits/stdc++.h>//献上代码
using namespace std;
int a[55],t,n; //数据水是我时间复杂度的证明，O(n log n)
int main(){
    cin>>t;
    while(t--){
        cin>>n;
        for(int i=1;i<=n;i++)cin>>a[i];
        for(int i=1;i<n;i++){
            sort(a+1,a+1+n-i+1); //注意，我们在a数组里删除了值
            a[1]=(a[1]+a[2])/2,a[2]=a[n];
        }
        cout<<a[1]<<endl;//最后a数组只剩1个值了，于是输出a[1]
    }
    return 0;
} 

B - B

给定一个由互不相同的整数组成的数组$a$。每次操作中，你可以选择：

$\bullet$选取数组的某个非空前缀$\ast$，并将其替换为该前缀的最小值；
$\bullet$选取数组的某个非空后缀$†$，并将其替换为该后缀的最大值。

注意：你可以选择整个数组$a$作为操作对象。

对于每个元素$a_i$，判断是否存在一系列操作能将数组$a$转化为$a_i$——即最终数组$a$仅包含该元素$a_i$ 。

请输出一个长度为$n$的二进制字符串，其中第$i$个字符为$1$表示存在这样的操作序列，否则为$0$。

$\ast$数组的前缀是指由前$k$个元素组成的子数组（$k$为任意整数）。
$†$数组的后缀是指由后$k$个元素组成的子数组（$k$为任意整数）。

首先我们可以证明如果一个数是某个前缀的最小值，或是某个后缀的最大值，就一定可以保留下来。

因为如果这个数是某个前缀的最小值，就可以先进行一次前缀操作，后面不管是什么数就都能经过几次后缀操作压缩成一个数，最后再进行一次前缀或后缀操作就能保留该数。

例如，$a=${$5,6,3,1,7$}，此时我们想要判断$a_3$能不能保留下来，就先判断它是不是某个前缀的最小值，结果是的，就先进行一次前缀操作，$a=${$3,1,7$}，接着进行一次后缀操作，$a=${$3,7$}，最后再进行一次前缀操作，$a_3$就保留了下来。

注意，最后一次操作要根据情况判断是进行前缀操作还是进行后缀操作。

C - C

Nene 发明了一种基于递增整数序列 $a_1,a_2,\dots ,a_k$ 的新游戏。

在这个游戏中，最初有 $n$ 名玩家排成一行。在每一轮游戏中，发生以下情况：

Nene 找到第 $a_1、a_2、\dots$和 $a_k$名玩家，他们会同时被踢出游戏。如果第 $i$ 名玩家应该被踢出，但排成一行的玩家少于 $i$ 名，则跳过该玩家。

一旦在某一轮中没有人被踢出游戏，所有仍在游戏中的玩家将被宣布为胜利者。

例如，考虑有$a=[3,5]$ 和 $n=5$ 名玩家的游戏。假设玩家按顺序被命名为玩家 A、玩家 B、
…、玩家 E。

那么，在第一轮之前，玩家排成 ABCDE。Nene 找到第 $3$ 和第 $5$ 名玩家。这些是玩家 C 和 E。他们在第一轮被踢出。现在玩家排成 ABD。

Nene 找到第 $3$ 和第 $5$ 名玩家。第 $3$ 名玩家是玩家 D，而排成一行中没有第 $5$ 名玩家。因此，只有玩家 D 在第二轮被踢出。

在第三轮中，没有人被踢出游戏，因此游戏在这一轮结束。玩家 A 和 B 被宣布为胜利者。

Nene 尚未决定最初有多少人会加入游戏。Nene 给了你 $q$ 个整数 $n_1,n_2,\dots ,n_q$​ ，你应该独立回答以下问题：

如果游戏最初有 $n_i$ 名玩家，最终会有多少人被宣布为胜利者？

先找出$n$数组的最小值，然后对于每次询问只要输出$(a_i)+1$%$mn+1$。怎么证明？

如图，在$3$下标之后包括$3$下标的元素都被删除了，最后只剩下两个元素，如果还是不信邪的话，自己造几个样例试试吧！

D - D

给定两个长度为n的排列$a$和$b$。排列是指包含$n$个从$1$到$n$不重复元素的数组。例如数组$[2,1,3]$是排列，但$[0,1]$和$[1,3,1]$不是。

你可以（不限次数）选择两个下标$i$和$j$，然后同时交换$a_i$ 与$a_j$​ 以及$b_i$与$b_j$。

你需要最小化两个排列中的逆序对总数。排列p中的逆序对是指满足$i<j$且$p_i>p_j$的下标对$(i,j)$。例如当$p=[3,1,4,2,5]$时，共有$3$个逆序对（具体为$(1,2)、(1,4)$和$(3,4)$）。

首先用一个结构体接入a,b数组，然后按a数组排序，最后输出就行了。

#include<bits/stdc++.h>
using namespace std;
struct tt{
	int a,b;
}c[200005];
bool cmp(tt x,tt y){
	return x.a<y.a;
}
int main(){
	int t;
	cin>>t;
	while(t--){
		int n;
		cin>>n;
		for(int i=1;i<=n;i++)cin>>c[i].a;
		for(int i=1;i<=n;i++)cin>>c[i].b;
		sort(c+1,c+1+n,cmp);
		for(int i=1;i<=n;i++)cout<<c[i].a<<" ";
		cout<<endl;
		for(int i=1;i<=n;i++)cout<<c[i].b<<" ";
		cout<<endl;		
	}
    return 0;
}

E - E

你有一个数组 $a_1,a_2,\dots ,a_n$。回答 q 个以下形式的查询：

如果我们将数组的 $a_l,a_{l+1},\dots ,a_r$​ 范围内的所有元素改为$k$，整个数组的和会是奇数吗？

注意，查询是独立的，不会影响后续的查询。

前缀和数组来存储区间总和。注意1，因为我们只需要判断总和是不是奇数，所以我们可以%2。注意2，把一个区间的值都改成k等于把一个区间的值都加上k，当然，仅在本题生效。
为什么呢？当然是通过打表找规律发现的，想知道为什么的自己试几组数据吧！

#include<bits/stdc++.h>
using namespace std;
long long a[200005],s[200005];
int main(){
    int t;
    cin>>t;
    while(t--){
        memset(s,0,sizeof s);
        memset(a,0,sizeof a);
        long long n,q,cs=0;//cs数组总和
        cin>>n>>q;
        for(int i=1;i<=n;i++)cin>>a[i],cs+=a[i]%2,s[i]=a[i]%2+s[i-1];
        while(q--){
            long long l,r,k,css=cs;
            cin>>l>>r>>k;
            css+=(r-l+1)*k%2-(s[r]-s[l-1])%2;
            if(css%2==1){
                cout<<"YES"<<endl;
            }else{
                cout<<"NO"<<endl;
            }
        }
    }
    return 0;
} 

F - F

体面过于复杂，链接F - F

这题很显然每次要合并最长的一条路径才是最优操作，然而每次进行这种操作都会删除2个叶子节点，所以先找出有多少个叶子节点，答案就是$\frac{\lceil 叶子节点数\rceil }{2}$。