晚间测试 2

T1 : 装饰

题解

• 看到数据范围发现这道题不是那么的可做，显然是一道结论题或是性质题。
• 首先发现，答案最多不超过(frac{a + b + c}{3})，然后再发现如果一种类型的是其他两种类型的两倍，答案就是另外两种加起来，即((a + b + c) - max(a, b, c))，如果达不到，那么就是(frac{a + b + c}{3})，两个取min即可，我是直接排序然后做的。

code

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define max(a, b) (a) > (b) ? (a) : (b)
inline int read () {
    int k = 0, f = 1; char ch = getchar();
    for (; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
    for (; isdigit(ch); ch = getchar()) k = k * 10 + ch - '0';
    return k * f;
}
int ans = 0;
void dfs(int numa, int numb, int numc, int num) {
    if ((numa == 0 && numb == 0) || (numa == 0 && numc == 0) || (numb == 0 && numc == 0) || (numa + numb + numc < 3)) {
        if (ans < num) ans = num;
        return;
    }
    if (numa && numb && numc) dfs(numa - 1, numb - 1, numc - 1, num + 1);
    if (numa >= 2 && numb) dfs(numa - 2, numb - 1, numc, num + 1);
    if (numa >= 2 && numc) dfs(numa - 2, numb, numc - 1, num + 1);
    if (numb >= 2 && numa) dfs(numa - 1, numb - 2, numc, num + 1);
    if (numb >= 2 && numc) dfs(numa, numb - 2, numc - 1, num + 1);
    if (numc >= 2 && numa) dfs(numa - 1, numb, numc - 2, num + 1);
    if (numc >= 2 && numb) dfs(numa, numb - 1, numc - 2, num + 1);
}
signed main() {
#ifdef local
    //freopen("in", "r", stdin);
#else
    freopen("decorate.in", "r", stdin);
    freopen("decorate.out", "w", stdout);
#endif
    int n = read();
    while (n--) {
        int a = read(), b = read(), c = read();
        if (a <= 5 && b <= 5 && c <= 5) {
            ans = 0;
            dfs(a, b, c, 0);
            printf("%lld
", ans);
        } else {
            if ((a == 0 && b == 0) || (a == 0 && c == 0) || (b == 0 && c == 0)) { puts("0"); continue; }
            if (a + b + c < 3) { puts("0"); continue; } 
            if (a == b && b == c) { printf("%lld
", a); continue; }
            if (a > b) swap(a, b);
            if (a > c) swap(a, c);
            if (b > c) swap(b, c);
            if (c / (a + b) >= 2) printf("%lld
", (a + b));
            else printf("%lld
", (a + b + c) / 3);
        }
    }
}

T2 : 凉宫春日的消失

题解