康复训练第二场，已经不会做题了。$B$题写的姿势就不对，$C$题也没搞出来。

C

给出$ n $根长度不一的木棍，第 $i$ 根棍子长度为 $a_i$ 。两根长度分别为 $a_b$ 和 $a_c$ 的木棍可以拼接成一根长度为 $a_b+a_c$的木棍，同理 $3$ 根， $4$ 根，甚至 $n$ 根都能拼接。

问：使用这 $n$ 根木棍作三角形的边（一根木棍至多使用一次，也可以不使用），能拼出的面积最大的三角形的面积。

题解

由于数据很小，直接二进制枚举三边的棍子组成情况，然后判断情况是否合法，合法的情况用海伦公式求面积即可, 或者DFS暴力深搜。复杂度$O((1<<n)^3)$。

#include <bits/stdc++.h>
#define N 10
using namespace std;
typedef long long ll;

ll arr[N];int n;
ll cal(int tem) {
    ll res = 0;
    for (int i = 0; i < n; i++) {
        if ((tem >> i) & 1)
            res += arr[i];
    }
    return res;
}

bool Judge(ll a, ll b, ll c) {
    if (a + b <= c || b + c <= a || a + c <= b)
        return 1;
    return 0;
}

int main() {
    scanf("%d", &n);
    double ans = -1;
    for (int i = 0; i < n; i++) {
        scanf("%lld", arr + i);
    }
    for (int i = 0; i < (1 << n); i++) {
        ll A = cal(i);
        for (int j = 0; j < (1 << n); j++) {
            if (i & j)
                continue;
            ll B = cal(j);
            for (int k = 0; k < (1 << n); k++) {
                if (i & k || j & k) {
                    continue;
                }
                ll C = cal(k);
                if (Judge(A, B, C))
                    continue;
                double p = (A + B + C) / 2.0;
                ans = max(ans, sqrt(p * (p - A) * (p - B) * (p - C)));
            }
        }
    }
    if (ans < 0)
        printf("-1\n");
    else
        printf("%.1f\n", ans);
    // system("pause");
    return 0;
}

D

https://ac.nowcoder.com/acm/contest/11220/D

给出一个长度为 $n$ 的数组 $A$，下标从 $1$ 开始，$A_1,A_2,\cdots,A_n$。定义一个区间$\left[l,r \right]$是“有趣的区间”，当且仅当结$A_l|A_{l+1}|A_{l+2}|\cdots|A_{r-1}|A_{r}$果为奇数。

求“有趣的区间”的个数，两个区间$[L_1,R_1],[L_2,R_2]$相同，当且仅当$L_1=L_2$且$R_1=R_2$

题解

一个区间或运算后是否为奇数，根据或运算的性质，只需要判断这个区间的是否存在一个元素的二进制下的最低位是 $1$ ，如果存在，这个区间或运算后是奇数，反之为偶数。
本题求的是或运算后是奇数的区间，因此 “有趣的区间”$=$ “总区间个数” $−$ “无趣的区间”

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

int main(){
    int n;scanf("%d",&n);
    ll sum=1ll*(n+1)*n/2;
    ll cnt=0;
    for(int i=0;i<n;i++){
        int num;scanf("%d",&num);
        if(num&1){
            sum-=1ll*(cnt+1)*cnt/2;
            cnt=0;
        }else{
            cnt++;
        }
    }
    sum-=1ll*(cnt+1)*cnt/2;
    printf("%lld\n",sum);
    // system("pause");
    return 0;
}

E

链接：https://ac.nowcoder.com/acm/contest/11220/E

有数字$1~9$，每个数字的个数分别为 $cnt_1,cnt_2,cnt_3,\cdots,cnt_9$。计算出“满意的集合“的个数。

"满意的集合" 定义：选出的数存在一种排列方式，其拼接起来后表示的十进制整数，能被$3$整除，例如集合 $\left\{3,3,6\right\}$(包含了 $2$个数字$3$,$1$个数字$6$ )，可以有排列$\left\{6,3,3\right\}$代表十进制下的整数 633，能被 3 整除。

两个集合相同，当且仅当集合元素个数相同，且排序后对应数字相同，例如$\left\{3,3,6\right\}$ 和 $\left\{3,6,3\right\}$ 是同样的集合. 空集合看作 0 ，是合法的，答案对$1e9+7$取模。

题解

#include <bits/stdc++.h>
#define ll long long
const int N=20,mod=1e9+7;
int cnt[N];
ll dp[N][3];
int main() {
    for (int i=1; i<=9; i++) scanf("%d",&cnt[i]);
    dp[0][0]=1;
    for (int i=1; i<=9; i++) {
        int mod1=1*i%3,mod2=2*i%3,mod3=3*i%3;
        ll sum1=(cnt[i]+2)/3,sum2=(cnt[i]+1)/3,sum3=cnt[i]/3+1;
        for (int MOD=0; MOD<3; MOD++) {
            dp[i][(mod1+MOD)%3]+=sum1*dp[i-1][MOD];
            dp[i][(mod2+MOD)%3]+=sum2*dp[i-1][MOD];
            dp[i][(mod3+MOD)%3]+=sum3*dp[i-1][MOD];
            dp[i][(mod1+MOD)%3]%=mod;
            dp[i][(mod2+MOD)%3]%=mod;
            dp[i][(mod3+MOD)%3]%=mod;
        }
    }
    printf("%lld\n",dp[9][0]);
    return 0;
}