总结

再次爆零，自闭了。只有一道模拟题差点写出来，赛后发现是除法写的有问题，改了就A了（再次自闭）。

Road To The 3rd Building

题目描述

原题传送门：点我直达

人话翻译：现在给出若干个数，每次只能选择若干个连续的且顺序不变的数字。求数字之和平均值的数学总期望。

分析

这题直接一个个组合的计算平均值不现实，也不方便分类计算。因此想到了按照选择数字的个数对情况进行分类。例如，现在给出10个数，那么长度为1的情况就有10种，长度为2的情况就有9种......以此类推，长度的固定也方便了后面进行除法的运算。同时发现，对于每种长度对应的平均值计算公式分子，分子的计算遵循了长度每递增一，则下标从n-i+1到i-1这个范围的项均多加一倍。
计算出每种长度的分子后，先对各种长度的分子进行一次逆元计算再求和。最后对求出的和再计算一次逆元就是结果。

AC代码

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long ll;
const int maxn = 2e5 + 10;
const int mod = 1e9 + 7;
ll sum[maxn], fz[maxn];
int a[maxn];

inline bool read(int &num) {
    //quick read
    char in;
    bool IsN = false;
    in = getchar();
    if (in == EOF) return false;
    while (in != '-' && (in < '0' || in > '9')) in = getchar();
    if (in == '-') {
        IsN = true;
        num = 0;
    } else num = in - '0';
    while (in = getchar(), in >= '0' && in <= '9') { num *= 10, num += in - '0'; }
    if (IsN) num = -num;
    return true;
}

ll qpow(ll a, ll b) {
    ll ans = 1;
    a %= mod;
    while (b) {
        if (b & 1) ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}

void solve() {
    int n;
    read(n);
    for (int i = 1; i <= n; i++) {
        read(a[i]);
        sum[i] = (sum[i - 1] + a[i]) % mod; //预处理前缀和
    }
    fz[1] = sum[n];
    for (int i = 2; i <= n / 2; i++)
        fz[i] = (fz[i - 1] + sum[n - i + 1] - sum[i - 1] + mod) % mod; //每加一层k 就将n-i+1 i-1加一次
    fz[n] = sum[n];
    if (n & 1) { //区分奇数偶数
        fz[n / 2 + 1] = (fz[n / 2] + a[n / 2 + 1]) % mod;
        for (int i = n - 1; i >= n / 2 + 2; i--)
            fz[i] = (fz[i + 1] + sum[i] - sum[n - i] + mod) % mod;
    } else {
        for (int i = n - 1; i >= n / 2 + 1; i--)
            fz[i] = (fz[i + 1] + sum[i] - sum[n - i] + mod) % mod;
    }
    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        ans = (ans + fz[i] * qpow(i, mod - 2) % mod) % mod;
        //逆元计算 等同于(fz/i)%mod == fz*i^(mod-2)%mod
    }
    ans = ((ans * 2 % mod) * qpow(1LL * n * (n + 1), mod - 2) % mod);
    //关于1LL：将int转换为long long，使用时直接对int乘以1LL即可
    printf("%lld\n", ans);
}

int main() {
    int T;
    for (cin >> T; T--;) solve();
    return 0;
}

Little Rabbit's Equation

题目描述

原题传送门：点我直达

人话翻译：就是现在给出若干个有指定格式的算式（格式：数字 操作符 数字 等于号 数字），要求写出算法识别算式中数字的进制，并且保证在这个进制下该算式能够成立。

分析

这题分两步，第一步为拆分算式，将数字和操作符分别提取，也就是一个字符串操作。
又发现题目给出的数据范围实际上很小（一共一个算式最多15个字符），那么直接暴力就完事了。从所有数字最大的那个数字+1开始，一致遍历到16进制，分别尝试在当前进制下算是是否成立。能够成立就输出成立的进制，最后都没有成立的情况就输出-1。

AC代码

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <sstream>
#include <queue>
#include <map>

using namespace std;
typedef long long ll;

const ll inf = 1e15;
const int maxn = 20 + 10;
char s[maxn];
ll nums[5];
bool is16[5] = {false};
map<char, int> mp;
map<char, string> mp2;
queue<string> sNum;
string sNums[5];

ll trans(ll old, ll base) {
    ll res = 0, nn = 1;
    while (old != 0) {
        res += (old % 10) * nn;
        old /= 10;
        nn *= base;
    }
    return res;
}

ll trans2(int r, string ss) {
    ll len = 0, ans = 0;
    while (ss.length() != len) {
        ans = ans * r;
        if (ss[len] >= 'A' && ss[len] <= 'Z')
            ans = ans + ss[len] - 'A' + 10;
        else
            ans = ans + ss[len] - '0';
        len++;
    }
    return ans;
}

bool verify(int base, int sign) {
    for (int i = 1; i <= 3; i++) nums[i] = trans2(base, sNums[i]);
    //cout << nums[1] << " " << nums[2] << " " << nums[3] << endl;
    bool res = false;
    switch (sign) {
        case 1: {
            if (nums[1] + nums[2] == nums[3]) res = true;
        }
            break;
        case 2: {
            if (nums[1] - nums[2] == nums[3]) res = true;
        }
            break;
        case 3: {
            if (nums[1] * nums[2] == nums[3]) res = true;
        }
            break;
        case 4: {
            if (nums[1] / nums[2] == nums[3] && nums[1] % nums[2] == 0) res = true;
        }
            break;
    }
    return res;
}

void solve() {
    while (cin >> s) {
        int ft = 1, sign = 0;//sign:1 + ,2 - ,3 * ,4 /
        int maxNum = -1;
        bool zeros = true;//表示有前导零
        memset(is16, false, sizeof(is16));
        string num;
        for (int i = 0; i < strlen(s); i++) {
            if ((s[i] == '+' || s[i] == '-' || s[i] == '*' || s[i] == '/' || s[i] == '=') && zeros) { //处理全是0的情况
                num += '0';
            } else {
                if (s[0] != '0' && i == 0) zeros = false;
                if (zeros) {
                    if (s[i] == '0') continue;
                    else zeros = false;
                }
            }
            char ope = s[i];
            if (s[i] == '+' || s[i] == '-' || s[i] == '*' || s[i] == '/') {
                zeros = true;
                sign = mp[ope];
                sNum.push(num);
                ft++;
                num = "";
            } else if (s[i] == '=') {
                zeros = true;
                sNum.push(num);
                ft++;
                num = "";
            } else {
                if (s[i] <= 'F' && s[i] >= 'A') {
                    maxNum = max(maxNum, s[i] - 'A' + 10);
                    is16[ft] = true;
                } else maxNum = max(maxNum, s[i] - '0');
                num += s[i];
            }
        }
        if (zeros) sNum.push("0");
        else sNum.push(num);
        if (maxNum <= 1) maxNum = 1;
        bool flag2 = false;
        int ls = 1;
        while (!sNum.empty()) {
            sNums[ls] = sNum.front();
            sNum.pop();
            ls++;
        }
        //cout << sNums[1] << " " << sNums[2] << " " << sNums[3] << endl;
        for (int i = maxNum + 1; i <= 16; i++) {
            if (verify(i, sign)) {
                cout << i << endl;
                flag2 = true;
                break;
            }
        }
        if (!flag2) cout << "-1" << endl;
    }
}

int main() {
    mp['+'] = 1, mp['-'] = 2, mp['*'] = 3, mp['/'] = 4;
    mp2['A'] = "10", mp2['B'] = "11", mp2['C'] = "12", mp2['D'] = "13", mp2['E'] = "14", mp2['F'] = "15";
    solve();
    return 0;
}

A Very Easy Graph Problem

题目描述

原题传送门：点我直达

人话翻译：简单个p，题目骗我 这题说的是给出若干个点和若干条边。每个点都有一个要么是1要么是0的权值（可以理解为黑点和白点），现在要求计算任意两点（保证一个为1一个为0）的最短路距离之和。

分析

这题算是一个最小生成树+dfs的综合题。首先为了计算最短路，先使用类似Kruskal的算法思路计算。得到最短路后，从任意一点开始进行dfs遍历，获得每一个点的dfs序（也就是通过dfs访问点所产生的一个顺序）。这里的顺序包含一个入和一个出，也就是每一个点都会被访问两次（一次是第一次搜索到的时候，第二次是回溯的时候）。而对于同一个点来说，第二次和第一次访问中间所相差的时间差（假设每一个单位时间会访问一个点），就是第一次与第二次访问该点的时间差中所遍历到点的数量的两倍，也可以称为“区间内的点数量的两倍”。
至于怎么计算这个最短路距离之和：对于任意一条题目给出的边，边的权值都是单调递增的（这一点题目说了）。又易知，对于第i条边之前的所有边的权值之和，和的大小都不会大于第i条边的权值（2的i次方是真的猛，想验算的自己去拿等比数列公式算）。因此就有一个结论：只要按照边的权值从小到大的顺序访问，那么对于需要经过这条边的两点，该边就是这两点最短路的一部分，不会存在比这条路更短的路。实在不知道咋回事的可以看看最小生成树是怎么画的。
那么现在要做的就只有，遍历边，计算边的左端点之前和右端点之后的所有1和0数量，然后（左边1数量x右边0数量+左边0数量x右边1数量）x边的权值 就是一条边的总贡献，最后对所有边的总贡献求和就是结果。

代码

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <cmath>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define de(x)   cout << "-----debug----  " << #x << " == " << x << endl;
#define rep(i, a, n)    for(int i = a; i <= n; ++ i)
#define per(i, n, a)    for(int i = n; i >= a; -- i)
#define ms(arr, x)      memset(arr, x, sizeof(arr))
#define MP  make_pair
#define fi  first
#define se  second
const ll mod = 1e9 + 10;
const int inf = 0x3f3f3f3f;
const int maxn = 100000 + 7;
const int maxm = 2e6 + 7;
vector<int> G[maxn];
pii vec[maxn];
ll cup[maxn], res;
int dad[maxn], id[maxn], deg[maxn];
int n, m, in[maxn], out[maxn], tot, Num = 0;
int Trie[maxn << 1];

inline bool read(int &num) {
    //quick read
    char in;
    bool IsN = false;
    in = getchar();
    if (in == EOF) return false;
    while (in != '-' && (in < '0' || in > '9')) in = getchar();
    if (in == '-') {
        IsN = true;
        num = 0;
    } else num = in - '0';
    while (in = getchar(), in >= '0' && in <= '9') { num *= 10, num += in - '0'; }
    if (IsN) num = -num;
    return true;
}

int seek(int x) {
    return x == dad[x] ? x : dad[x] = seek(dad[x]);
}

inline int lowbit(int x) {
    return x & (-x);
}

inline ll qpow(ll x, ll n, ll m) {
    ll res = 1;
    while (n) {
        if (n & 1) {
            res = res * x % m;
        }
        n >>= 1;
        x = x * x % m;
    }
    return res % m;
}

// DFS序记录时间戳
void build(int rt, int fa) {
    in[rt] = ++tot;
    for (int i = 0; i < G[rt].size(); ++i) {
        int v = G[rt][i];
        if (v != fa) {
            build(v, rt);
        }
    }
    out[rt] = ++tot;
}

void updata(int x) {
    while (x <= n * 2) {
        Trie[x]++;
        x += lowbit(x);
    }
}

int query(int x) {
    int sum = 0;
    while (x >= 1) {
        sum += Trie[x];
        x -= lowbit(x);
    }
    return sum;
}

void Solve(int &kase) {
    ms(Trie, 0);
    Num = 0;
    // 总共0的个数  1的个数
    int nn0 = 0, nn1 = 0;
    read(n), read(m);
    for (int i = 1; i <= n; ++i) {
        deg[i] = 0;
        dad[i] = i;
        G[i].clear();
        read(id[i]);
        nn0 += (id[i] == 0);
        nn1 += (id[i] == 1);
    }
    for (int i = 1; i <= m; ++i) {
        int u, v;
        read(u);
        read(v);
        // 建立最小生成树
        if (seek(u) != seek(v)) {
            // 记录边
            vec[++Num] = MP(u, v);
            ++deg[u];
            ++deg[v];
            dad[seek(u)] = seek(v);
            ll w = qpow(2, i, mod);
            cup[Num] = w;
            G[u].emplace_back(v);
            G[v].emplace_back(u);
        }
    }
    res = 0;
    tot = 0;
    // DFS序
    for (int i = 1; i <= n; ++i) {
        if (deg[i] == 1) {
            build(i, 0);
            break;
        }
    }
    // 初始化
    for (int i = 1; i <= n; ++i) {
        if (id[i] == 1) {
            updata(in[i]);
        }
    }
    for (int i = 1; i <= n - 1; ++i) {
        int u = vec[i].fi, v = vec[i].se;
        // 方便起见  把u换到左边（时间戳小的地方）
        if (in[u] > in[v]) {
            swap(u, v);
        }
        // 区间内所有的数的个数
        int cnt = (out[v] - in[v] + 1) / 2;
        // 区间内1的个数
        int right1 = query(out[v]) - query(in[v] - 1);
        // 区间内0的个数
        int right0 = cnt - right1;
        //  区间外面0和1的个数  就是直接总数减区间内的
        int left0 = nn0 - right0;
        int left1 = nn1 - right1;
        // 左0右1的贡献
        res += (ll) (left0 * right1) % mod * cup[i] % mod;
        res %= mod;
        // 左1右0的贡献
        res += (ll) (left1 * right0) % mod * cup[i] % mod;
        res %= mod;
    }
    printf("%lld\n", res % mod);
}

int main() {
    int Test, kase = 0;
    for (read(Test); Test--;) {
        ++kase;
        Solve(kase);
    }
    return 0;
}

Divisibility

题目描述

原题传送门：点我直达

人话翻译：还是直接看原题吧emmmm。

分析

看到答案后，啊这。判断一下b mod x等不等于1就完事了。

AC代码

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;
typedef long long ll;

const ll inf = 1e15;
const int maxn = 100000 + 10;
ll T, n, k = 1;

inline bool read(ll &num) {
    //quick read
    char in;
    bool IsN = false;
    in = getchar();
    if (in == EOF) return false;
    while (in != '-' && (in < '0' || in > '9')) in = getchar();
    if (in == '-') {
        IsN = true;
        num = 0;
    } else num = in - '0';
    while (in = getchar(), in >= '0' && in <= '9') { num *= 10, num += in - '0'; }
    if (IsN) num = -num;
    return true;
}

void solve() {
    ll b, x;
    read(b);
    read(x);
    cout << (b % x == 1 ? "T" : "F") << endl;
}

int main() {
    for (cin >> T; T--;) solve();
    return 0;
}