牛客周赛Round93
C题
这道题我没有想到什么更简单的做法，因为本题只是一个二维矩阵，而且分析可得，本题满足条件的情况很特殊，于是我直接把两人所有可能在的位置中成立的条件枚举了出来，剩下的直接输出NO,分析如下：
代码
#include<bits/stdc++.h>
using namespace std;
int main(){int n;cin>>n;int x1,y1,x2,y2;cin>>x1>>y1;cin>>x2>>y2;//两人初始位置相同if((x1==x2)&&(y1==y2)){cout<<"YES"<<endl;return 0;}//对角相邻不满足情况特判//因为下面对角相邻情况已经包含了这种不满足的情况，所以需要在对角相邻情况之前特判if((x1==1&&y1==n-2&&x2==2&&y2==n-1)||(x2==1&&y2==n-2&&x1==2&&y1==n-1)){cout<<"NO"<<endl;return 0;}//对角相邻且排除和终点重合的情况if(abs(x1-x2)==1&&abs(y1-y2)==1&&y1!=n&&y1!=(n-1)){cout<<"YES"<<endl;return 0;}//特判y1或y2=n和n-1时，成立的条件if((x1==1&&y1==n&&x2==2&&y2==n-1)||(x1==2&&y1==n-1&&x2==1&&y2==n)){cout<<"YES";return 0;}//上述条件均不满足cout<<"NO";return 0;
}这个代码确实有点麻烦，因为两个人的位置情况太多了，但是我们可以固定一下他们所在的行，这样也能减少很多步骤，代码如下
#include<bits/stdc++.h>
using namespace std;
int main(){int n,x1,y1,x2,y2;cin>>n;cin>>x1>>y1;cin>>x2>>y2;if(x1>x2){swap(x1,x2);//保证x1在第一行，x2在第二行swap(y1,y2);//虽然也交换了，但是仍不能保证y1和y2哪个更大}if(x1!=x2){if((y1+1==y2&&y2<n-1)||y2+1==y1){cout<<"YES";}else{cout<<"NO";}}else{if(y1==y2){cout<<"YES";}else{cout<<"NO";}}return 0;
}D题
本题要求最大化数组 a的字典序，根据题目“对于数组 s和数组 t，从第一个元素开始逐个比较，直到找到第一个不同的元素，较大元素所在的数组的字典序较大。如果比较到其中一个数组的结尾时依旧全部相同，则较短的数组字典序更小。”因此我们的目标时让元素大的尽可能靠前，且数组尽可能的短，最多操作k次那我们就操作K次，而且题目所给的两种操作，实际上可以看成一种，都是把a加到b上，删除a,这样我们只需考虑让元素大的尽可能靠前即可，毫无疑问，用贪心来解决，我第一次分析的结果有点难以实现，于是反过来就很容易操作了，如下：
核心思想
-
最大化第一个元素：通过将数组中最大的 k 个元素加到第一个元素上，最大化第一个元素的值，从而最大化数组的字典序。
-
优先队列（堆）：用于快速获取当前最大值。使用优先队列存储数组元素及其索引，方便每次快速取出当前最大值。默认情况下，
priority_queue按照元素从大到小排序。如果需要改变排序方式，可以通过自定义比较函数实现优先队列按照元素从小到大排序。priority_queue<int, vector<int>, greater<int>> pq; -
贪心算法：每次选择当前最大的元素进行操作，以最大化第一个元素的值。
- pair:
pair是一个模板类，用于将两个不同类型（或相同类型）的值组合成一个单一的单元。对于pair类型，优先队列会先比较first，再比较second，默认也是从大到小排序。pair的定义如下：
pair<Type1, Type2> variable_name;代码：
#include<bits/stdc++.h>
using namespace std;
const int N=200005;
long long a[N];
#define PII pair<int,int>
int main(){int t,n,k;cin>>t;while(t--){cin>>n>>k;priority_queue<PII>q;//优先队列 q，存储数组元素及其索引for(int i=0;i<n;i++){cin>>a[i];if(i!=0){q.push({a[i],i});}}while(k--){a[0]+=q.top().first;//取出当前最大值a[q.top().second]=0;q.pop();//移除该元素}for(int i=0;i<n;i++){if(a[i]){if(i==0) cout<<a[i];else cout<<" "<<a[i];}}cout<<endl;}return 0;
}E题
分析可知，本题考查统计子序列数量，虽然给的条件有点麻烦，需要找到最大值，最小值，还有Mex，但是本质上是考查组合数学，因为分析可知，只有两种情况可以符合题目要求，第一种是只有一个元素的子序列，第二种是数值连续的子序列，除此之外，均不合法，例如，出现断裂的子区间（如缺少某个数 m），则 Mex(S) ≤ m，而 Max(S)-Min(S) ≥ m，此时 Mex(S) ≤ Max(S)-Min(S)，不满足条件，因此，断裂情况无需处理，只有单元素和连续从 0 开始的子序列合法。此外，为避免计算过程中数值溢出，变量类型用long long，代码中的2ll 表示一个长长整型（long long 类型）常量，ll 是 long long 的缩写
核心思想
-
分类统计：
-
单元素子序列：所有单元素子序列均满足条件（Mex ≥ 0，Max - Min = 0）。
-
连续数值区间子序列：
若子序列包含连续数值
0, 1, 2, ..., k，则：
-
Mex(S) = k+1（因为 0~k 都存在）
Max(S) - Min(S) = k - 0 = k
条件 k+1 ≥ k 恒成立，因此这些子序列均合法。
-
组合数学：
-
对于数值 i，若有
cnt[i]次出现，其非空子序列数目为 2^cnt[i]−1。 -
通过前缀积s计算连续区间的组合数，维护从
0到当前i的所有数值的组合数的乘积，累加所有合法情况。
-
算法知识点
-
快速幂取模：高效计算大指数幂取模。
-
组合计数：利用乘法原理统计子序列组合数。
-
前缀积：动态维护连续区间的组合数。
-
模运算：防止数值溢出，确保结果在模数范围内。
子序列和子集的区别如下：
代码：
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
//快速幂函数 ksm(计算a的b次方mod p使用快速幂算法以降低时间复杂度)
long long ksm(int a,int b,int p){long long ans=1;a%=p;while(b){if(b&1) ans=(ans*a)%p;b>>=1;a=(a*a)%p;}return ans%p;
}
int main(){long long n,ans=0;cin>>n;vector<long long>cnt(n+1);int x;for(int i=1;i<=n;i++){cin>>x;cnt[x]++;}//处理连续数值区间long long s=1;//s为前缀积，表示当前连续区间的子序列组合数(当前数值至少选一个)for(int i=0;i<=n;i++){if(cnt[i]==0) break;s*=ksm(2ll,cnt[i],mod)-1+mod;s%=mod;ans+=s;ans%=mod;}//处理单元素子序列for(int i=1;i<=n;i++){ans+=ksm(2ll,cnt[i],mod)-1+mod;ans%=mod;}cout<<ans;return 0;
}