2021牛客多校第八场复盘

前言

大概今天能把积压的文章更完了QAQ

复盘

A - Ares, Toilet Ares

阅读理解题,第一次看的时候以为自己看错了,怎么好像这么多变量都没用。

实际上确实没用

简单来说就是:

有$a$​道未被替换的简单题可以被做出来,而对于下一道比较困难的题,需要获取到长度为$l$的代码才能完成。你有$k$次机会去厕所获取代码,第$k$次获取长度为$x_i$的代码的失败概率为$\frac{y_i}{z_i}$,保证$\sum x_i=l$​。请你求出最后他们能过完成的期望总题数。

实际上,所求答案就是:$a + \sum (\frac{z_i-y_i}{z_i} * [x_i > 0])$

题目所给的数据都比较小,且$4933$是货真价实的素数,直接求逆元计算即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
/* vegetable1024 | liushan.site | Maybe Lovely? */

#include <bits/stdc++.h>
#define maxn 800005
#define int long long
using namespace std;

clock_t START_TIME, END_TIME;

//DEBUG TEMPLATE
template<typename T>
void Print(T value){
std::cout << value << '\n';
}
template<typename Head, typename... Rail>
void Print(Head head, Rail... rail){
std::cout << head << ", ";
Print(rail...);
}

int read(){
int x = 0; char ch = getchar();
while(ch < '0' || ch > '9') ch = getchar();
while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
return x;
}
int n, m, k, a, l;
int qpow(int a, int b, int p){
if(b == 0) return 1;
int tmp = qpow(a, b / 2, p);
tmp = (tmp * tmp) % p;
if(b & 1) tmp = (tmp * a) % p;
return tmp;
}
int inv(int val, int mod){
return qpow(val, mod - 2, mod);
}
signed main(void)
{
START_TIME = clock();
n = read(); m = read(); k = read(); a = read(); l = read();
int ans = a, res = 1;
for(int i = 1; i <= k; i++)
{
int xi = read(), yi = read(), zi = read();
if(xi) res = (res * (zi - yi) * inv(zi, 4933)) % 4933;
}
ans = (ans + res) % 4933;
printf("%lld\n", ans);
END_TIME = clock();
//printf("%.5lf ms\n", (double)(END_TIME - START_TIME) / CLOCKS_PER_SEC * 1000);
return 0;
}

D - OR

这题主要是有个$trick$,即$a+b=a | b + a \& b$​,据说在$CF$上是比较常见的?

打完多校后没多久有个$CF$的交互题就出了这个,直接秒了

在本题中,给出了两个序列$b_i=a_i \ or \ a_{i-1},c_i=a_i \ + \ a_{i-1}$,问有多少种可能的$a_i$。

我们取$d_i = c_i - b_i$,可以得到$d_i= a_i \ and \ a_{i-1}$。

也就是说,对于序列中的每一个数中的第$k$位,我们只需要枚举$a_1$的第$k$位的取值,就能够从$b_i$和$d_i$唯一的推导出序列$a_i$中每个数的第$k$位的一组可行解,或推导出当$a_1$的第$k$位取$X$时,是不存在可行方案的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
/* vegetable1024 | liushan.site | Maybe Lovely? */

#include <bits/stdc++.h>
#define maxn 800005
#define int long long
using namespace std;

clock_t START_TIME, END_TIME;

//DEBUG TEMPLATE
template<typename T>
void Print(T value){
std::cout << value << '\n';
}
template<typename Head, typename... Rail>
void Print(Head head, Rail... rail){
std::cout << head << ", ";
Print(rail...);
}

int read(){
int x = 0; char ch = getchar();
while(ch < '0' || ch > '9') ch = getchar();
while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
return x;
}

int n, b[maxn], c[maxn], d[maxn];

bool check(int pos, int val){
int bit = (val == 1);
for(int i = 1; i <= n - 1; i++)
{
int _and = (d[i] & (1LL << pos)), _or = (b[i] & (1LL << pos));
if(_and && _or && bit == 0)
return false;
else if(_and && _or == 0)
return false;
else if(_and == 0 && _or)
bit ^= 1;
else if(_and == 0 && _or == 0 && bit)
return false;
}
return true;
}
signed main(void)
{
n = read();
for(int i = 1; i <= n - 1; i++) b[i] = read();
for(int i = 1; i <= n - 1; i++) c[i] = read();
for(int i = 1; i <= n - 1; i++) d[i] = c[i] - b[i];
int ans = 1;
for(int i = 0; i <= 31; i++)
{
int now = 0;
if(check(i, 0)) now++;
if(check(i, 1)) now++;
if(now == 0)
{
ans = 0;
break;
}
ans = (ans * now);
}
printf("%lld\n", ans);
//START_TIME = clock();


//END_TIME = clock();
//printf("%.5lf ms\n", (double)(END_TIME - START_TIME) / CLOCKS_PER_SEC * 1000);
return 0;
}

E - Rise of Shadows

签到题。

其实多想一想根本不可能输出YES,直接输出NO就行了,写这么长干什么

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
/* vegetable1024 | liushan.site | Maybe Lovely? */

#include <bits/stdc++.h>
#define maxn 800005
#define int long long
using namespace std;

clock_t START_TIME, END_TIME;

//DEBUG TEMPLATE
template<typename T>
void Print(T value){
std::cout << value << '\n';
}
template<typename Head, typename... Rail>
void Print(Head head, Rail... rail){
std::cout << head << ", ";
Print(rail...);
}

int read(){
int x = 0; char ch = getchar();
while(ch < '0' || ch > '9') ch = getchar();
while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
return x;
}
int t, n;
bool ck1(int x){
return (x % 4 == 0 && x % 100 != 0) || (x % 400 == 0);
}
bool ck2(int val){
for(int i = 2; i * i <= val; i++)
if(val % i == 0)
return false;
return true;
}
signed main(void)
{

START_TIME = clock();
t = read();
while(t--)
{
n = read();
printf(ck1(n) && ck2(n) ? "yes\n" : "no\n");
}

END_TIME = clock();
//printf("%.5lf ms\n", (double)(END_TIME - START_TIME) / CLOCKS_PER_SEC * 1000);
return 0;
}

F - Robots

正解是$bitset$​​优化加滚动数组或离线分治(前面一种可以卡过去)。

(PS:明明想到了开四维bitset优化却不会离线操作转为滚动数组,麻了)

最开始的时候想着冲一波并查集,然后凉了,普通的并查集不能支持第三种机器人的操作,不能够限制方向。后面想再加一个权值,使得并查集具有方向性(大概会变成奇怪的树上问题,理论上那样做也是可以的,实际上好像很复杂搞不定)。

后面考虑,跟前面的题一样,试着利用$bitset$优化,使复杂度大约变为$O(\frac{n^4}{\omega})$​​​,理论上应该是跑不过去的,实际上好像牛客的机子非常快然后过了…

如果写离线分治,复杂度是$O(\frac{n^3log n}{\omega})$​,会稳很多。

考虑开一个$bitset \langle 500 * 500 \rangle b[500][500]$的数组,其中$b[i][j]$内存储从点$(i,j)$出发,能够到达的点有哪些。

由于第三个机器人只能够往右或者往下行走,因此,$b[i][j]$可以直接或上$b[i+1][j]$和$b[i][j+1]$。

这样子做时间复杂度是允许的,但是空间上存不下这么多的数字。因此考虑使用滚动数组。

由于转移只依赖于$b[i+1][j]$和$b[i][j+1]$​,因此我们可以将询问按照行列排序,从末行末列的询问开始处理,并设置滚动数组优化空间,就能通过该题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
/* vegetable1024 | liushan.site | Maybe Lovely? */

#include <bits/stdc++.h>
#define maxn 505
#define int long long
using namespace std;

clock_t START_TIME, END_TIME;

//DEBUG TEMPLATE
template<typename T>
void Print(T value){
std::cout << value << '\n';
}
template<typename Head, typename... Rail>
void Print(Head head, Rail... rail){
std::cout << head << ", ";
Print(rail...);
}

int read(){
int x = 0; char ch = getchar();
while(ch < '0' || ch > '9') ch = getchar();
while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
return x;
}
char cread(){
char ch = getchar();
while(ch != '0' && ch != '1') ch = getchar();
return ch;
}

int n, m, q;
int sumx[maxn][maxn], sumy[maxn][maxn];
char board[maxn][maxn];
bitset<maxn * maxn> dp[2][maxn];

const int qsize = 5e5 + 5;
struct Node{
int sx, sy, tx, ty, id, typ, ans;
bool operator < (const Node &A){
return sx == A.sx ? sy < A.sy : sx < A.sx;
}
} Q[qsize];
int calc(int x, int y){
return (x - 1) * m + y;
}
signed main(void)
{
n = read(); m = read();
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
board[i][j] = cread();
sumx[i][j] = sumx[i - 1][j] + (board[i][j] == '1');
sumy[i][j] = sumy[i][j - 1] + (board[i][j] == '1');
}
}
q = read();
for(int i = 1; i <= q; i++)
{
int t = read();
int sx = read(), sy = read(), tx = read(), ty = read();
Q[i] = (Node){sx, sy, tx, ty, i, t, -1};
}
sort(Q + 1, Q + q + 1);
int flag = 1, pos = q;
for(int i = n; i >= 1; i--)
{
for(int j = m; j >= 1; j--) dp[flag][j].reset();
for(int j = m; j >= 1; j--)
{
if(board[i][j] == '0')
dp[flag][j].set(calc(i, j));
if(board[i][j + 1] == '0')
dp[flag][j] |= dp[flag][j + 1];
if(board[i + 1][j] == '0')
dp[flag][j] |= dp[flag ^ 1][j];

while(Q[pos].sx == i && Q[pos].sy == j)
Q[pos].ans = (dp[flag][j][calc(Q[pos].tx, Q[pos].ty)] == 1), pos--;
}
flag ^= 1;
}
sort(Q + 1, Q + q + 1, [&](const Node &A, const Node &B){return A.id < B.id;});
for(int i = 1; i <= q; i++)
{
int t = Q[i].typ;
int sx = Q[i].sx, sy = Q[i].sy, tx = Q[i].tx, ty = Q[i].ty;
if(t == 1)
printf(tx >= sx && ty == sy && sumx[tx][ty] - sumx[sx - 1][sy] == 0 ? "yes\n" : "no\n");
if(t == 2)
printf(ty >= sy && tx == sx && sumy[tx][ty] - sumy[sx][sy - 1] == 0 ? "yes\n" : "no\n");
if(t == 3)
printf(Q[i].ans ? "yes\n" : "no\n");
}
//START_TIME = clock();


//END_TIME = clock();
//printf("%.5lf ms\n", (double)(END_TIME - START_TIME) / CLOCKS_PER_SEC * 1000);
return 0;
}

而分治处理的方法,主要是每次枚举一行专门统计跨这行的询问

image-20210905163827557

可以参考这篇文章和它的代码,写的很好:

2021牛客暑期多校训练营8 F-Robots - LaiAng80586的小屋 (idonggua.net)

标程:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include<bits/stdc++.h>
#define N 510
#define M 600010
using namespace std;
int n, m, q;
char ch[N][N];

struct node
{
int _x1, _y1, _x2, _y2, id;
}a[M];
vector < node > vec;
int ans[M];
bitset < N > f[N][N], g[N][N];

inline int Get()
{
char c;
while(c = getchar(), c < '0' || '9' < c);
int s = c - '0';
while(c = getchar(), '0' <= c && c <= '9')
s = s * 10 + c - '0';
return s;
}

void solve(int L, int R, vector < node > v)
{
if(L > R) return;
int mid = L + R >> 1;

for(int i=mid; i>=L; --i)
for(int j=m; j; --j)
{
f[i][j].reset();
if(ch[i][j] == '1') continue;
if(i == mid) f[i][j][j] = 1;
else f[i][j] |= f[i+1][j];
f[i][j] |= f[i][j+1];
}

for(int i=mid; i<=R; ++i)
for(int j=1; j<=m; ++j)
{
g[i][j].reset();
if(ch[i][j] == '1') continue;
if(i == mid) g[i][j][j] = 1;
else g[i][j] |= g[i-1][j];
g[i][j] |= g[i][j-1];
}

vector < node > v1, v2;
for(int i=0; i<v.size(); ++i)
{
if(v[i]._x2 < mid) v1.push_back(v[i]);
else if(mid < v[i]._x1) v2.push_back(v[i]);
else ans[v[i].id] = (f[v[i]._x1][v[i]._y1] & g[v[i]._x2][v[i]._y2]).any();
}

solve(L, mid - 1, v1);
solve(mid + 1, R, v2);
}

int main()
{
n = Get(), m = Get();
for(int i=1; i<=n; ++i)
scanf("%s", ch[i] + 1);
q = Get();
for(int i=1; i<=q; ++i)
{
int o = Get();
a[i]._x1 = Get();
a[i]._y1 = Get();
a[i]._x2 = Get();
a[i]._y2 = Get();
a[i].id = i;
if(o == 1 && a[i]._y1 != a[i]._y2) continue;
if(o == 2 && a[i]._x1 != a[i]._x2) continue;
if(a[i]._x1 <= a[i]._x2 && a[i]._y1 <= a[i]._y2)
vec.push_back(a[i]);
}

solve(1, n, vec);
for(int i=1; i<=q; ++i) puts(ans[i] ? "yes" : "no");
}

K - Yet Another Problem About Pi

构造题。

首先我们考虑最大化能走到的格子数,贪心的我们需要直走或者沿着对角线走。

这里借用一下2021牛客暑期多校训练营8 K题: Yet Another Problem About Pi的图片:

image-20210905164553515

而后本题的一个关键是,证明存在最优解,直线的次数$x<3$或对角线的次数$y < 2$。

对此,我们设格子的长和宽分别为$w,d$,且$w \leq d$,有单条直线长度为$w$,对角线长度为$\sqrt{w^2+d^2}$。

若要使得解最优,就要有:

  • $x \ast w + y \ast \sqrt{w ^ 2 + d^2} \leq \pi$​
  • $2x + 3y$最大

为了达成这个条件,我们观察到,每走$3$次直线的贡献和走$2$次对角线的贡献是相同的。

因此,若$3 \ast w \leq 2 \ast \sqrt{w^2+d^2}$​,则应该尽可能地走直线,剩下的长度用于走$0,1$​次对角线。

反之,若$3 \ast w > 2 \ast \sqrt{w^2 + d^2}$​​,则应该尽可能走对角线,剩下的长度用于走$0,1,2$​​次直线。

剩余部分枚举即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
/* vegetable1024 | liushan.site | Maybe Lovely? */

#include <bits/stdc++.h>
#define maxn 800005
#define int long long
using namespace std;

const double PI = acos(-1.0);

//DEBUG TEMPLATE
template<typename T>
void Print(T value){
std::cout << value << '\n';
}
template<typename Head, typename... Rail>
void Print(Head head, Rail... rail){
std::cout << head << ", ";
Print(rail...);
}

int read(){
int x = 0; char ch = getchar();
while(ch < '0' || ch > '9') ch = getchar();
while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
return x;
}
int t;
double w, d;
void solve(double w, double d){
if(w < d) swap(w, d);
double s = sqrt(w * w + d * d);
int ans = 0;
for(int i = 0; i <= 3; i++)
{
if(i * d <= PI)
ans = max(ans, i * 2 + ((int)((PI - d * i) / s)) * 3);
if(i * s <= PI)
ans = max(ans, i * 3 + ((int)((PI - s * i) / d)) * 2);
}
printf("%lld\n", ans + 4);
}
signed main(void)
{
t = read();
while(t--)
{
scanf("%lf %lf", &w, &d);
solve(w, d);
}
return 0;
}
如果你觉得还不错,就请咕咕的作者喝杯咖啡吧QAQ