2021牛客多校第三场

E.Math

标签：打表，找规律

解法：打表，观察到满足条件的为(f(i), f(i) * k * k - f(i - 1))，其中k可以为任意正整数。

代码

#include <bits/stdc++.h>
using namespace std;
using ULL = unsigned long long;

vector<ULL> v;

int main() {
    v.push_back(1);
    for (ULL i = 2; i <= 1000000; ++i) {
        v.push_back(i * i * i);
        ULL last = i;
        ULL ans = i * i * i;
        while (ans <= (ULL)1000000000000000000) {
            auto tmp = last;
            last = ans;
            if ((((ULL)1000000000000000000 + tmp) / i + 1) / i + 1 >= ans)
                ans = ans * i * i - tmp;
            else
                break;
            v.push_back(ans);
        }
    }
    int t;
    cin >> t;
    sort(v.begin(), v.end());
    while (t--) {
        ULL n;
        cin >> n;
        cout << upper_bound(v.begin(), v.end(), n) - v.begin() << endl;
    }
}

F.24dian

标签：DFS

代码

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int n, m;
int anss;
bool work(int x, double a[], int t, bool &fraction) {
    if (x == 0) {
        if (abs(a[1] - m) < 1e-6) {
            if (t == 1)
                return true;
            else {
                fraction = true;
                return false;
            }
        } else
            return false;
    }
    double b[5];
    int cnt;
    bool ans = false;
    for (int i = 1; i <= x; i++)
        for (int j = i + 1; j <= x + 1; j++) //从a里选出两个数
        {
            cnt = 0;
            for (int k = 1; k <= x + 1; k++)
                if (k != i && k != j)
                    b[++cnt] = a[k];
            b[++cnt] = a[i] + a[j];
            ans |= work(x - 1, b, t, fraction);
            b[cnt] = a[i] - a[j];
            ans |= work(x - 1, b, t, fraction);
            b[cnt] = a[i] * a[j];
            ans |= work(x - 1, b, t, fraction);
            b[cnt] = a[j] - a[i];
            ans |= work(x - 1, b, t, fraction);
            if (a[j] != 0) {
                if (abs((a[i] / a[j]) - round(a[i] / a[j])) < 1e-6)
                    b[cnt] = a[i] / a[j], ans |= work(x - 1, b, t, fraction);
                else
                    b[cnt] = a[i] / a[j], ans |= work(x - 1, b, 1, fraction);
            }
            if (a[i] != 0) {
                if (abs((a[j] / a[i]) - round(a[j] / a[i])) < 1e-6)
                    b[cnt] = a[j] / a[i], ans |= work(x - 1, b, t, fraction);
                else
                    b[cnt] = a[j] / a[i], ans |= work(x - 1, b, 1, fraction);
            }
        }
    return fraction ? false : ans;
}
double card[5];
int key[5][29000];
void dfs(int x) {
    if (x == n + 1) {
        bool t = false;
        if (work(n - 1, card, 0, t)) {
            ++anss;
            for (int i = 1; i <= n; i++)
                key[i][anss] = card[i];
        }
        return;
    }
    for (int i = card[x - 1]; i <= 13; i++) //保证递增,避免重复枚举
    {
        card[x] = i;
        dfs(x + 1);
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    card[0] = 1;
    dfs(1);
    cout << anss << '\n';
    for (int i = 1; i <= anss; i++) {
        for (int j = 1; j <= n; j++)
            cout << key[j][i] << ' ';
        cout << endl;
    }
    return 0;
}

J.Counting Triangles

标签：思维

解法：考虑任意一个点以及与其相连的两条边，只需考虑两条边颜色不同的情况，在矩阵中条件为异或。

代码

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

namespace GenHelper {
unsigned z1, z2, z3, z4, b, u;
unsigned get() {
    b = ((z1 << 6) ^ z1) >> 13;
    z1 = ((z1 & 4294967294U) << 18) ^ b;
    b = ((z2 << 2) ^ z2) >> 27;
    z2 = ((z2 & 4294967288U) << 2) ^ b;
    b = ((z3 << 13) ^ z3) >> 21;
    z3 = ((z3 & 4294967280U) << 7) ^ b;
    b = ((z4 << 3) ^ z4) >> 12;
    z4 = ((z4 & 4294967168U) << 13) ^ b;
    return (z1 ^ z2 ^ z3 ^ z4);
}
bool read() {
    while (!u)
        u = get();
    bool res = u & 1;
    u >>= 1;
    return res;
}
void srand(int x) {
    z1 = x;
    z2 = (~x) ^ 0x233333333U;
    z3 = x ^ 0x1234598766U;
    z4 = (~x) + 51;
    u = 0;
}
} // namespace GenHelper

bool edge[8005][8005];
int sum[8005][2];

int main() {
    int n, seed;
    cin >> n >> seed;
    GenHelper::srand(seed);
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            edge[j][i] = edge[i][j] = GenHelper::read();
        }
    }
    for (int i = 0; i < n; ++i) {
        int cnt0 = 0, cnt1 = 0;
        for (int j = 0; j < i; ++j) {
            if (edge[i][j]) {
                ++cnt1;
            } else {
                ++cnt0;
            }
        }
        for (int j = i + 1; j < n; ++j) {
            if (edge[i][j]) {
                ++cnt1;
            } else {
                ++cnt0;
            }
        }
        sum[i][0] = cnt0;
        sum[i][1] = cnt1;
    }
    long long ans = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            ans += sum[j][edge[i][j] ^ 1];
        }
        for (int j = i + 1; j < n; ++j) {
            ans += sum[j][edge[i][j] ^ 1];
        }
    }
    ans >>= 2;
    ans = (long long)n * (n - 1) * (n - 2) / 6 - ans;
    cout << ans << '\n';
    return 0;
}