[数据结构与算法]Codeforces Round #737 (Div. 2)部分题解

A

点击此处查看对应的题目.
??这题要求将一个序列分为a与b两个序列，求出 $(f(a)+f(b){)}_{max}$，所以我们只要分出一个最大值成为序列$f(a)$，再写出$f(b)$的表示相加就是答案，最后记得保留九位小数。

时间复杂度 $O(n)$

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10,INF=1e9;
int a[N];

void solve()
{
    int n;
    cin>>n;

    for(int i=0;i<n;i++) cin>>a[i];
    int maxn=-INF;ll sum=0;

    for(int i=0;i<n;i++) {
        maxn=max(maxn,a[i]);
        sum+=a[i];
    }
    sum-=maxn;

    printf("%.9lf\n",(double)((double)sum/(n-1)+maxn));
}
int main()
{
    int t;
    cin>>t;

    while(t--){
        solve();
    }
    return 0;

}

B

点击此处查看对应的题目.
??本题涉及算法：二分+排序
??本题我一度交了两次WA：第一次WA是我以为只要判断出现递减区间的次数与k的关系就可以出结论，但后来发现即便出现递减区间的次数小于等于k也有可能出现序列中的其他元素大小在该递减区间中间从而无法排序，所以不能仅仅用递减区间的次数与k比较，应该用子序列的个数，即统计子序列的个数cnt。

??第二次WA是因为我忽略了即便出现以上状况也不至于无法排序，只要k足够大就不影响，只需要将子序列数量值++即可。

??解题思路：先判断子序列数量与k的关系，如果k够用，则继续判断是否出现序列中的其他元素大小在该递减区间中间的情况，有则子序列数量值++。最后再次进行第一步的判断。

时间复杂度 $O(nlogn)$

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10,INF=1e9;
int a[N],t[N];

void solve()
{
    int n,k;
    cin>>n>>k;

    int cnt=1;
    for(int i=0;i<n;i++) cin>>a[i];
    t[0]=a[0];
    if(n==k) {puts("Yes");return;}

    for(int i=1;i<n;i++){
        if(a[i] < a[i-1]) cnt++;
        t[i]=a[i];
    }
    sort(t,t+n);
  
    if(cnt > k) puts("No");
    else {
        for(int i=1;i<n;i++){
            if(a[i] > a[i-1]){
                int j=upper_bound(t,t+n,a[i-1])-t;
                if(t[j] < a[i]) cnt++;
            }
        }
        if(cnt > k) puts("No");
        else puts("Yes");
    }
}
int main()
{
    int t;
    cin>>t;

    while(t--){
        solve();
    }

    return 0;
}

C

点击此处查看对应的题目.
??本题涉及算法：快速幂+组合数学

我们规定，左式是&，右式是^，想要满足本题条件，做事必须大于等于右式。本题涉及位运算的知识，主要是看n是偶数还是奇数。

if(如果n是奇数)，考虑两种情况:

① ?左式为0 ：此时右式为0。n为奇数（左式为0），在n个里面选偶数个为1，得到异或结果为0
（$C_n^0+C_n^2+C_n^4+??????+C_n^{n?1}=2^{n?1}$）

② ?左式为1：此时右式为1。只有一种情况，就是序列全为1（左式为1）

两种情况相加得：$2^{n?1}+1$（注意）

else if(如果n是偶数)，考虑两种情况:

① ?左式等于右式 ：n为偶数（左式为0），在n个里面选偶数个为1，得到异或结果为0，全选的话左式大于右式
（$C_n^0+C_n^2+C_n^4+??????+C_n^{n?2}=2^{n?1}?C_n^n$）（注意）

② ?左式大于右式：固定前i个（前i个数相等），并让第i个为1，i后面的随便选
(${\sum }_{i=1}^k(2^{n?1}?1{)}^{i?1}?(2^n{)}^{k?i}$)

时间复杂度 $O(n(logn{)}^2)$

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+10,INF=1e9,mod=1e9+7;
int a[N];

ll qmi(int a,int b,int p)
{
    ll res = 1 % p;
    while(b){
        if(b & 1) res = res * a % p;
        a = (ll)a * a % p;
        b >>= 1;
    }
    return res;
}
void solve()
{
    ll res=0;
    int n,k;
    cin >> n >> k;
    if(k == 0) {cout << 1 <<'\n'; return;}

    if(n & 1) res = qmi((qmi(2,n - 1,mod) + 1),k,mod);
    else {
        for(int i = 1;i <= k;i ++){
             res += qmi(qmi(2,n-1,mod)-1,i-1,mod)*qmi(qmi(2,n,mod),k-i,mod)%mod;
        }
        ll another_case = qmi(qmi(2,n - 1,mod) - 1,k,mod);
        res = (res + another_case) % mod;
    }
    cout << res <<'\n';
}
int main()
{
    int t;
    cin>>t;

    while(t--){
        solve();
    }

    return 0;
}