前言

大概今天能把积压的文章更完了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;
}