最优分解定理

#include <bits/stdc++.h>
#define sc(x) scanf("%lld", &(x))
#define pr(x) printf("%lld\n", x)
#define mem(x, y) memset(x, y, sizeof(x))
#define For(i, j, k) for (int i = (int)(j); i <= (int)(k); i++)
#define Rep(i, j, k) for (int i = (int)(j); i >= (int)(k); i--)
using namespace std;
typedef long long ll;
const int N = 1e5 + 7;
const ll mod = 1e9 + 7;
const double PI = acos(-1);
const int INF = 0x3f3f3f3f;
bool vis[N];
int main() {
    int T;
    sc(T);
    while (T--) {
        mem(vis, 0);
        int n;
        sc(n);
        int num = 0;
        if (n == 1) {
            printf("%.9lf\n", log(1));
            return 0;
        } else if (n == 2) {
            printf("%.9lf\n", log(2));
            return 0;
        } else if (n == 3) {
            printf("%.9lf\n", log(3));
            return 0;
        } else if (n == 4) {
            printf("%.9lf\n", log(4));
            return 0;
        }
        int rear = 2;
        for (int i = 2; n != 0; ++i) {
            if (!vis[i] && n >= i) {
                vis[i] = 1;
                n -= i;
                num++;
                continue;
            }
            if (n >= num) {
                vis[rear++] = 0;
                n -= num;
                vis[i] = 1;
                continue;
            }
            vis[i - n] = 0;
            vis[i] = 1;
            break;
        }
        double ans = 0.0;
        int sum = 1;
        for (int i = 2, cnt = 0; cnt < num; ++i) {
            if (vis[i])
                ans += log(i), sum *= i, cnt++;
        }
        cout << sum << " ";
        cout << ans << endl;
    }

    return 0;
}

A - Krypton

2020 China Collegiate Programming Contest Changchun Site
暴力枚举

法向量

给n维超平面上n个点，判断n个点是否在n-1维超平面上