牛牛的签到奖励

第一题定位的是 签到题
对于如何判断某年某月有多少天？
可以先使用 if 判断是否是闰年
如下

if((n%4==0&&n%100!=0)||n%400==0) return 是闰年;
else return 不是闰年;

判断了某年是否是闰年，我们只需要打表判断某月有多少天
再依次枚举此月的 1 日是星期几，进行计算取最小值即可

#include <bits/stdc++.h>
using namespace std;
int n, y, r;
int rn[20] = { 0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
int frn[20] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
int get() {
    if ((n % 4 == 0 && n % 100 != 0) || n % 400 == 0)
        return (rn[y]);
    else
        return (frn[y]);
}


int a[10], ans = INT_MAX;
int b[50];
int cale(int k) {
    int ans = 0;

    for (int i = 1; i <= r; i++) {
        if (b[i])
            ans += a[k];

        k = (k + 1) % 7;
    }

    return (ans);
}


int main() {
    cin >> n >> y;
    r = get();

    for (int i = 0; i < 7; i++)
        cin >> a[i];

    for (int i = 1; i <= r; i++)
        cin >> b[i];

    for (int i = 0; i < 7; i++)
        ans = min(ans, cale(i));

    cout << ans << "\n";
    return (0);
}

还有一种更优的解法，我们没有必要判断某年某月有多少天，当读入某天是否签到时，我们可以用以下方式读入
while(scanf("%d",&c[n])!=EOF) n++;
这样就可以不用判断某年某月有多少天，完整代码如下

#include <bits/stdc++.h>
using namespace std;
int a, b, n = 1;
int h[10], c[50];
int main() {
    scanf("%d%d", &a, &b);

    for (int i = 0; i < 7; i++)
        scanf("%d", &h[i]);

    while (scanf("%d", &c[n]) != EOF)
        n++;

    n--;
    int ans = 1e9;

    for (int i = 0; i < 7; i++) {
        int now = i, rem = 0;

        for (int j = 1; j <= n; j++, now = (now + 1) % 7)
            rem += c[j] * h[now];

        ans = min(ans, rem);
    }

    printf("%d\n", ans);
    return (0);
}

牛牛的期末考试

这是一道二分题，这个𝑖𝑑𝑒𝑎呢，是因为上一次的普及考了二分，但是太简单了，所以就有了这道题。
30%：
这个部分分很好拿，直接暴力即可。
50%:
发现这20%的点中的范围就 750，所以我们可以用一个桶来装下每个班级不同分数的人数，再遍历即可。
100%:
因为我们要求的是比第名分数大的人的个数，所以我们可以在排好序后二分。
可以从小到大排序，这样就可以直接利用来求出答案。
从大到小的话，就需要手动打二分。
复杂度就是 。

#include <bits/stdc++.h>
using namespace std;
const int   N = 1005;
int     n, q;
int     a[N][N];
int main() {
    scanf("%d", &n);

    for (int i = 1; i <= n; ++i) {
        int tot;
        scanf("%d", &tot);
        a[i][0] = tot;

        for (int j = 1; j <= tot; ++j)
            scanf("%d", &a[i][j]);

        sort(a[i] + 1, a[i] + 1 + tot);
    }

    scanf("%d", &q);

    while (q--) {
        int l, r, k, p;
        scanf("%d%d%d%d", &l, &r, &k, &p);
        int res = 0;

        for (int i = l; i <= r; ++i) {
            int pos = upper_bound(a[i] + 1, a[i] + 1 + a[i][0], a[k][a[k][0] - p + 1]) - a[i];
            res += (a[i][0] - pos + 1);
        }

        res += 1;
        printf("%d\n", res);
    }

    return (0);
}

牛牛的数列

本题考了前缀和，RMQ，贪心。
30：
暴力模拟即可，对于每一个询问扫一遍 u 到 v。
100：
先考虑 u 到 v 的异或和，明显的发现可以用前缀和来做，这样我们就在𝑂(1)的时间里求出这个值。
然后考虑求最大差值，我们只需要求出那个的点的值就可以了，所以可以想到用 ST 表来求，用𝑂(𝑛𝑙𝑜𝑔𝑛)预处理。
然后𝑂(1)查询。
此时我们已经求出了𝑆，然后考虑𝑊，我们可以进行一波贪心，枚举𝑊的二进制，从 30 到 1，设当前枚举位为𝑖，如果加上1 ≪ 𝑖大于了𝑤，那么不可取。
如果当前位为 1，然后𝑆当前位也为 1，那么也不可取，因为我们是异或，要求一个最大值。把符合条件的位置赋为 1，然后与𝑆结合算出答案即可。

#include <bits/stdc++.h>
using namespace std;
const int   N = 1e6 + 50;
int     n, q;
int     w, s;
int     a[N];
int     sum[N];
int     f[N][20];
void ST() {
    int len = log2(n);

    for (int i = 1; i <= n; ++i)
        f[i][0] = a[i];

    for (int j = 1; j <= len; ++j)
        for (int i = 1; i + (1 << j) - 1 <= n; ++i)
            f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);

    return;
}


int query(int l, int r) {
    int k = log2(r - l + 1);
    return (max(f[l][k], f[r - (1 << k) + 1][k]));
}


int main() {
    scanf("%d%d%d%d", &n, &q, &s, &w);

    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
        sum[i] = sum[i - 1] ^ a[i];
    }

    for (int i = 1; i <= n; ++i)
        a[i] ^= s;

    ST();

    while (q--) {
        int l, r;
        scanf("%d%d", &l, &r);
        int ans = 0;
        int res = sum[r] ^ sum[l - 1] ^ query(l, r) ^ s;

        for (int i = 30; i >= 0; --i) {
            if ((ans | (1 << i)) > w)
                continue;

            if (res & (1 << i))
                continue;

            ans |= (1 << i);
        }

        printf("%d\n", res | ans);
    }

    return (0);
}

瞎位移群岛

此题做为本套试卷的压轴题，有一定的难度。
我们在乎在某一个时间牛牛是否可以到达某一个岛，并不在乎牛牛是如何到达这个岛的。
于是我们定义数组 flag[i]代表牛牛是否可以到达编号为 i 的岛，若 flag[i]==1 代表牛牛可以到达 i 岛，flag[i]==0 反之
我们考虑对于每秒的位移后，flag 数组会产生什么变化。
当一个岛位移成功后，我们扫秒此岛的 4 个方向，查看是否有其他岛变得和此岛联通
如果发现了有岛与此岛联通，我们记这两个岛为 a 和 b
如果 flag[a]==0&& flag[b]==0 此次位移不会对 flag 数组造成影响，2 个岛都无法到达，不会对 flag 造成影响
如果 flag[a]==1&& flag[b]==1 此次位移不会对 flag 数组造成影响，2 个岛都可以到达，之前已经更新过，不需要再次更新
如果 flag[a]==1&& flag[b]==0 此次位移会对 flag 数组造成影响，对 a 连通的岛跑 bfs，并标记
如果 flag[a]==0&& flag[b]==1 此次位移会对 flag 数组造成影响，对 b 连通的岛跑 bfs，并标记
复杂度分析：
近似于 O(T)，由于被 flag 数组标记后就可以不进行广搜，广搜的总共时间复杂度近似 O(k)可以忽略不考虑。
参考代码

#include <bits/stdc++.h>
using namespace std;
int Map[1005][1005];
int x[1005], y[1005];
bool    flag[1005];
int n, m, k, s, t, T;
int kx[7] = { 0, 0, 0, -1, 1 };
int ky[7] = { 0, 1, -1, 0, 0 };
/*上 下 左 右 */
queue< int >    v;
queue< int >    q;
void bfs(int xx, int yy) {
    flag[Map[xx][yy]] = 1;
    v.push(xx);
    q.push(yy);

    while (v.size()) {
        int x   = v.front();
        int y   = q.front();
        v.pop();
        q.pop();

        for (int i = 1; i <= 4; ++i) {
            int tx  = x + kx[i];
            int ty  = y + ky[i];

            if (Map[tx][ty] && !flag[Map[tx][ty]]) {
                flag[Map[tx][ty]] = 1;
                v.push(tx);
                q.push(ty);
            }
        }
    }
}


int main() {
    cin >> n >> m >> k >> s >> t;

    for (int i = 1; i <= k; ++i) {
        scanf("%d%d", &x[i], &y[i]);
        Map[x[i]][y[i]] = i;
    }

    bfs(x[s], y[s]);

    if (flag[t]) {
        puts("0");
        return (0);
    }

    cin >> T;

    for (int now = 1; now <= T; now++) {
        int d, p;
        scanf("%d%d", &d, &p);
        int tx  = x[d] + kx[p];
        int ty  = y[d] + ky[p];

        if (tx > 0 && tx <= n && ty > 0 && ty <= m && !Map[tx][ty]) {
            Map[x[d]][y[d]] = 0;
            Map[tx][ty] = d;
            x[d]        = tx;
            y[d]        = ty;

            for (int i = 1; i <= 4; ++i) {
                int xx  = tx + kx[i];
                int yy  = ty + ky[i];

                if (Map[xx][yy] && (flag[d] ^ flag[Map[xx][yy]]))
                    bfs(xx, yy);
            }
        }

        if (flag[t]) {
            printf("%d\n", now);
            return (0);
        }
    }

    puts("-1");
    return (0);
}

总结

这次考试包含的知识点如下:
模拟和枚举，二分，异或性质，ST表（可以用线段树代替，但是线段树时间复杂度大于ST表），前缀和，搜索

后话

这是我们第一次举办比赛，如果对比赛有什么建议，请您不吝赐教