【题解】牛客IOI周赛21-普及组
牛牛的签到奖励
第一题定位的是 签到题
对于如何判断某年某月有多少天？
可以先使用 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表），前缀和，搜索
后话
这是我们第一次举办比赛，如果对比赛有什么建议，请您不吝赐教
美团开奖239人在聊