2021-09-18 22:54 杭州师范大学 C++

关注

牛客多校第八场题解

Ares, Toilet Ares

https://ac.nowcoder.com/acm/contest/11259/A

A - Ares, Toilet Ares

题意：
厕所战神已经A了 $a$ 道题了，接下来要写'k'题，能上 $k$ 次测所，第 $i$ 次上厕所能获得 $x_i$ 行代码，所有 $x$ 相加就是最终的代码，但有每次获得的代码都有概率是错误的，问厕所战神最终能A出题目数量的期望。

思路：
阅读理解题，前期一直没开，开了之后联系下沈阳实际情况，立马就懂了，一开场就开或许能抢个一血？（雾）

特判下 $0$ 行代码即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define dbg(x...) do{ cerr << #x << " -> "; err(x);} while (0)
void err() { cerr << endl;}
template<class T, class... Ts> void err(const T& arg, const Ts&... args) { cerr << arg << " "; err(args...);}
const int N = 1e5 + 7;
const ll mod = 4933;

ll powmod(ll a, ll b) {
    ll res = 1;
    for (; b; b >>= 1) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
    }
    return res;
}

void run() {
    int n, m, k, a, l;
    scanf("%d%d%d%d%d", &n, &m, &k, &a, &l);
    ll res = 1;
    for (int i = 1, x, y, z; i <= k; ++i) {
        scanf("%d %d %d", &x, &y, &z);
        if (x == 0) continue;
        y = z - y;
        res = res * y % mod * powmod(z, mod - 2) % mod;
//        dbg(res);
    }
    res = (res + a) % mod;
    printf("%lld\n", res);
}

int main() {
    int t = 1;
//    scanf("%d", &t);
    while (t--) run();
    return 0;
}

D - OR

题意：
给定 $b$ 序列和 $c$ 序列，定义 $b_i = a_{i-1} | ai$ ， $c_i = a_{i-1} + a_i$ ，问存在多少个 $a$ 序列满足要求。

思路：
a $+ b = (a | b) + (a \& b)$ ，所以我们可以得到 $a_{i-1} \& a_i$ 的值。同时注意到，二进制下每位取 $0$ 或者 $1$ 的情况都是不会互相影响的，所以我们可以枚举 $a_1$ 的所有位数，每位分开来计算最终可能的 $01$ 取值。

赛时没搞出来这个，直接模拟去写，还是比较麻烦的 $QAQ$

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define dbg(x...) do{ cerr << #x << " -> "; err(x);} while (0)
void err() { cerr << endl;}
template<class T, class... Ts> void err(const T& arg, const Ts&... args) { cerr << arg << " "; err(args...);}
const int N = 1e5 + 7;
int b[N], c[N];
int n;

void run() {
    scanf("%d", &n);
    for (int i = 2; i <= n; ++i) {
        scanf("%d", &b[i]);
    }
    for (int i = 2; i <= n; ++i) {
        scanf("%d", &c[i]);
    }
    for (int i = 2; i <= n; ++i) {
        c[i] -= b[i];
    }
    ll ans = 1;
    for (int i = 0; i < 31; ++i) {
        bool ok0 = true, ok1 = true;
        for (int j = 2; j <= n; ++j) {
            int bb = b[j] >> i & 1, bc = c[j] >> i & 1;
            if (bb && bc) ok0 = false; // or 和 and 都有，只有双1合法
            else if (!bb && !bc) ok1 = false; // 都没有，只有双0合法
            else if (bb && !bc) swap(ok0, ok1); // or 有 and 没有，要看前一位的情况
            else ok0 = ok1 = false; // or 有 and 没有，非法
        }
        ans *= ok0 + ok1;
    }
    printf("%lld\n", ans);
}

int main() {
    int t = 1;
//    scanf("%d", &t);
    while (t--) run();
    return 0;
}

E - Rise of Shadows

题意： 给出一个年份，问年份是否为闰年并且为素数

题解： 直接输出no即可

#include<bits/stdc++.h>
using namespace std;

#define dbg(x...) do { cout << #x << " -> "; err(x); } while (0)
void err () {   cout << endl;}
template <class T, class... Ts>
void err(const T& arg, const Ts&... args) { cout << arg << ' '; err(args...);}

#define ll long long
#define ull unsigned long long
#define LL __int128
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define pii pair<int, int>
#define PII pair<ll, ll>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define em emplace
#define mp(a,b) make_pair(a,b)
#define all(x) (x).begin(), (x).end()
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define PAUSE system("pause");
const double Pi = acos(-1.0);
const double eps = 1e-6;
const int maxn = 2e6 + 10;
const int maxm = 1e5 + 10;
const int mod = 1e9 + 7;

inline ll rd() {
    ll f = 0; ll x = 0; char ch = getchar();
    for (; !isdigit(ch); ch = getchar()) f |= (ch == '-');
    for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';
    if (f) x = -x;
    return x;
}
void out(ll a) {if(a<0)putchar('-'),a=-a;if(a>=10)out(a/10);putchar(a%10+'0');}
#define pt(x) out(x),puts("")
inline void swap(ll &a, ll &b){ll t = a; a = b; b = t;}
inline void swap(int &a, int &b){int t = a; a = b; b = t;}
inline ll min(ll a, ll b){return a < b ? a : b;}
inline ll max(ll a, ll b){return a > b ? a : b;}
ll qpow(ll n,ll k,ll mod) {ll ans=1;while(k){if(k&1)ans=ans*n%mod;n=n*n%mod;k>>=1;}return ans%mod;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int n;

void solve(){
    scanf("%d", &n);
    puts("no");
}

int main() {
//    freopen("in.txt","r",stdin);
//    freopen("out.txt", "w", stdout);
    int t = 1;
    // t = rd();
    scanf("%d", &t);
    // cin >> t;
    while(t--)
        solve();
    return 0;
}

F - Robots

题意：
有三种机器人，第一种只能向下走，第二种只能向右走，第三种两个方向都能走。二维网格中有些网格不能走，每次给你机器人的类型，起始点和终点，问你能否到达。

思路：
和 $HDU$ 的那道有点像，但是这道题网格范围小，并且是多组询问，考虑离线的做法。

翻了下大家赛时的码，发现基本都是暴力做的。大概就是每个点都开一个 $500 \times 500$ 的 $bitset$ ，代表这个点能走到的所有点的情况，然后从前往后或者从后往前推，进行转移，并且查看这个点相关的询问，就能直接冲过去了。

题解给的做法是分治。首先我们应该先有上面的想法，才能想到分治的做法。上面的做法要维护一个 $500 \times 500$ 的 $bitset$ ，考虑如何降低时间复杂度。如果一个点向左上走能到达一个点，向右下走能到达另一个点，那么左上的点就能到达右下的点。不能直接做的原因是我们无法确定这个中转站在哪里，但是能确定中转站所在的行列一定在它的到达的两个点的中间，所以考虑分治，每次将询问两点所在行都在左边的点和都在右边的点进行分治，对横跨的点进行处理，维护一个长度 $500$ 的 $bitset$ 。对于在 $mid$ 左边的点来说，代表它能到 $mid$ 行的哪些点；对于 $mid$ 右边的点来说，代表 $mid$ 行的哪些点能到它。

注意预处理下同行同列和一些非法的询问，这些在分治的时候可能会比较麻烦。

#include <bits/stdc++.h>

using namespace std;

#define endl "\n"
#define dbg(x...)             \
    do {                      \
        cout << #x << " -> ";\
        err(x);               \
    } while (0)

void err() {
    cout << endl;
}

template <class T, class... Ts>
void err(const T& arg, const Ts&... args) {
    cout << arg << ' '; err(args...);
}

inline int rd() {
    int f = 0; int x = 0; char ch = getchar();
    for (; !isdigit(ch); ch = getchar()) f |= (ch == '-');
    for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';
    if (f) x = -x;
    return x;
}

typedef long long ll;

const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
bitset<505 * 505> dp[2][505];
string s[505];
int n, m, ans[500005];
vector< pair<int, int> > qry[505 * 505];
void solve() {
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        cin >> s[i];
    }
    int q;
    cin >> q;
    int op, px, py, sx, sy;
    for (int i = 1; i <= q; ++i) {
        cin >> op >> px >> py >> sx >> sy;
        px--, py--, sx--, sy--;
        if (op == 1 && (py != sy || px > sx)) continue;
        if (op == 2 && (px != sx || py > sy)) continue;
        qry[px * m + py].push_back({i, sx * m + sy});
    }
    for (int i = n - 1; i >= 0; --i) {
        for (int j = m - 1; j >= 0; --j) {
            // 滚动一下降低空间复杂度
            if (s[i][j] == '1') dp[i & 1][j] = 0; // 直接赋0
            else { // 转移
                dp[i & 1][j] = dp[i & 1 ^ 1][j] | dp[i & 1][j + 1];
                dp[i & 1][j][i * m + j] = 1;
            }
            for (auto p : qry[i * m + j]) { // 询问
                ans[p.first] = dp[i & 1][j][p.second];
            }
        }
    }
    for (int i = 1; i <= q; ++i) {
        cout << (ans[i]? "yes" : "no") << '\n';
    }
}

int main() {
#ifndef LOCAL
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    cout << fixed << setprecision(20);
#endif
    int t = 1;
    //cin >> t;
    while (t--) solve();
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

#define endl "\n"

inline int rd() {
    int f = 0; int x = 0; char ch = getchar();
    for (; !isdigit(ch); ch = getchar()) f |= (ch == '-');
    for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';
    if (f) x = -x;
    return x;
}

typedef long long ll;

const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
bitset<505> dp[505][505];
string s[505];
int n, m, ans[500005];

struct Q {
    int id, lx, ly, rx, ry; 
};

void dfs(vector<Q> v, int l, int r) {
    if (v.empty() || l == r) return;
    vector<Q> L, R, now;
    int mid = l + r >> 1;
    for (auto q : v) {
        if (q.rx <= mid) L.push_back(q);
        else if (q.lx > mid) R.push_back(q);
        else now.push_back(q);
    }
    dfs(L, l, mid);
    dfs(R, mid + 1, r);
    for (int i = mid; i >= l; --i) {
        for (int j = m - 1; j >= 0; --j) {
            if (s[i][j] == '1') {
                dp[i][j].reset();
                continue;
            }
            // 因为在mid行上的可以直接赋值，所以先考虑列转移
            if (j < m - 1) dp[i][j] = dp[i][j + 1];
            else dp[i][j].reset();
            if (i < mid) dp[i][j] |= dp[i + 1][j];
            else dp[i][j][j] = 1;
        }
    }

    for (int i = mid + 1; i <= r; ++i) {
        for (int j = 0; j < m; ++j) {
            if (s[i][j] == '1') {
                dp[i][j].reset();
                continue;
            }
            if (j) dp[i][j] = dp[i][j - 1];
            else dp[i][j].reset();
            if (i > mid + 1) dp[i][j] |= dp[i - 1][j];
            else dp[i][j][j] = 1;
        }
    }

    for (auto q : now) {
        ans[q.id] = (dp[q.lx][q.ly] & dp[q.rx][q.ry]).count() > 0;
    }
}

void solve() {
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        cin >> s[i];
    }
    int q;
    cin >> q;
    int op, lx, ly, rx, ry;
    vector<Q> qry;
    for (int i = 1; i <= q; ++i) {
        cin >> op >> lx >> ly >> rx >> ry;
        lx--, ly--, rx--, ry--;
        if (op == 1 && (ly != ry || lx > rx)) continue;
        if (op == 2 && (lx != rx || ly > ry)) continue;
        if (lx == rx) {
            if (ly <= ry) {
                while (ly <= ry) {
                    if (s[lx][ly] == '1') break;
                    ly++;
                }
                ans[i] = ly > ry;
            }
        } else if (ly == ry) {
            if (lx <= rx) {
                while (lx <= rx) {
                    if (s[lx][ly] == '1') break;
                    lx++;
                }
                ans[i] = lx > rx;
            }
        } else {
            qry.push_back({i, lx, ly, rx, ry});
        }
    }
    dfs(qry, 0, n - 1);
    for (int i = 1; i <= q; ++i) {
        cout << (ans[i]? "yes" : "no") << '\n';
    }
}

int main() {
#ifndef LOCAL
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    cout << fixed << setprecision(20);
#endif
    int t = 1;
    //cin >> t;
    while (t--) solve();
    return 0;
}

J - Tree

题意：
两人在一棵树上进行博弈，轮流走，每次可以走到一个相邻的点，然后将自己在的上一个点的所有边删去，当两个人都不能走的时候，游戏结束。问第一个人走的距离减去第二个人走的距离的结果。

思路：
因为在树上，所以只有在点 $u$ 通往点 $v$ 的路上走，才会对对方有影响。在这条路径上，我们可以求出两个人从每个点离开时，能走的最长距离，那么我们就可以枚举一个人从哪个点离开，区间求最大值获得另一个人能走的距离，第一个人取差值 $max$ ，第二个人取 $min$ ，就能得到答案了。

注意这个枚举，因为后决策点能覆盖前面的点，但是如果前面的点覆盖掉后面的点就是错误的，所以应该从里面向外面枚举，并且要注意每次求距离的区间，要把之前的影响提前算进去。比如两点之间的路径为1->2->3->4->5，我们正着推一下，最后求的是第二个人从点 $4$ 离开，第一个人从点 $3$ 离开的距离差；然后是求第一个人从点 $2$ 离开，第二个人从点 $3$ 或点 $4$ 离开的距离差，以此类推，第一次求的就是第一个人从点 $1$ 离开，第二个人从点 $2$ 到点 $5$ 之间的一个点离开的距离差。

其实就是推到下一步的时候，如果这步要推的话，上一个人一定要在它们之间的路径上走才是合法的。然后两个人一个取 $max$ ，一个取 $min$ ，是会互相影响的，所以从前往后推会有点问题。比如我第一个人取完 $max$ 是 $-12$ ，第二个人下一步求得答案是 $-8$ ，不会进行更新，但第一个人的下一步是 $1$ ，那么最终我求得的答案就会变成 $1$ ，但实际上应该是 $-8$ 。

这里的区间求 $max$ 我是用 $RMQ$ 实现的。这题比较特殊，从后往前推的时候可以一路取 $max$ ，也能获得当前区间最大值。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int N = 5e5 + 7;

int n, s, t;
int path[N], rp[N], dis[N], mx[2][N][20];
vector<int> G[N];

bool dfs(int u, int fa) {
    if (u == t) return true;
    for (auto v : G[u]) {
        if (v == fa) continue;
        rp[v] = u;
        path[u] = v;
        if (dfs(v, u)) return true;
        rp[v] = 0;
        path[u] = 0;
    }
    return false;
}

void dfsDis(int u, int fa, int pre) {
    dis[u] = pre;
    for (auto v : G[u]) {
        if (v == fa || v == path[u] || path[v] == u) continue;
        dfsDis(v, u, pre + 1);
        dis[u] = max(dis[u], dis[v]);
    }
}

void st(int n) {
    for(int l=1;(1<<l)<=n;l++){
        for(int i=1;i+(1<<l)-1<=n;i++){
            for (int o = 0; o < 2; ++o) {
                mx[o][i][l]=max(mx[o][i][l-1],mx[o][i+(1<<(l-1))][l-1]);
            }
        }
    }
}

int RMQ(int l, int r, int o) {
    int k = __lg(r - l + 1);
    int ans;
    ans = max(mx[o][l][k], mx[o][r-(1<<k)+1][k]);
    return ans;
}

void solve() {
    cin >> n >> s >> t;
    for (int i = 1, u, v; i < n; ++i) {
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(s, 0);
    int now = s;
    int len = 0;
    while (now) {
        now = path[now];
        len++;
    }
    int tot = 0;
    now = s;
    while (now) {
        dfsDis(now, 0, 0);
        tot++;
        mx[0][tot][0] = dis[now] + tot - 1;
        mx[1][tot][0] = dis[now] + len - tot;
        now = path[now];
    }
    st(tot);
    int hid = (tot + 1) / 2, rid = hid + 1;
    int step = 0;
    int ans = RMQ(hid, hid, 0) - RMQ(rid, rid, 1);
    while (hid > 1) {
        if (hid > tot - rid + 1) {
            hid--;
            ans = max(ans, RMQ(hid, hid, 0) - RMQ(hid + 1, rid, 1));
        } else {
            rid++;
            ans = min(ans, RMQ(hid, rid - 1, 0) - RMQ(rid, rid, 1));
        }
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    cout << fixed << setprecision(20);
    int t = 1;
    while (t--) solve();
    return 0;
}

/*
9 1 4
1 2
1 3
3 4
4 5
1 8
3 6
7 6
4 9
*/

K - Yet Another Problem About Pi

题意： 给出一个网格图，我们知道每个网格的宽和高，要求画一条不中断的长度为 $\pi$ 的线，使得走过的网格数最多

题解： 通过分析，我们得出结论，只走两种边是最优的，一种是宽和高中较短的那条，一种是网格的对角线。

我们考虑先走横着的边，每一条边都会提供 $2$ 的贡献，然后考虑最后剩下来的边长，将它们补到前面横着里面看能凑出多少条斜着的边
我们再考虑先走斜着的边，每一条边都会提供 $3$ 的贡献，然后考虑最后剩下来的边长，有两种选择，一种是这个长度比横着的边长，那答案就直接加 $2$ ；否则看这条边加上一条斜着的边能不能凑成两条横着的边

上面两种方法的选择我们通过比较斜边和横着的边的长度关系，因为斜着的能提供 $3$ 的贡献，横着的能提供 $2$ 的贡献，讨论两倍的斜边长和三倍的横着的边的长度的大小关系即可

#include<bits/stdc++.h>
using namespace std;

#define dbg(x...) do { cout << #x << " -> "; err(x); } while (0)
void err () {   cout << endl;}
template <class T, class... Ts>
void err(const T& arg, const Ts&... args) { cout << arg << ' '; err(args...);}

#define ll long long
#define ull unsigned long long
#define LL __int128
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define pii pair<int, int>
#define PII pair<ll, ll>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define em emplace
#define mp(a,b) make_pair(a,b)
#define all(x) (x).begin(), (x).end()
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define PAUSE system("pause");
#define double long double
const double Pi = acos(-1.0);
const double eps = 1e-11;
const int maxn = 2e6 + 10;
const int maxm = 1e5 + 10;
const int mod = 1e9 + 7;

inline ll rd() {
    ll f = 0; ll x = 0; char ch = getchar();
    for (; !isdigit(ch); ch = getchar()) f |= (ch == '-');
    for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';
    if (f) x = -x;
    return x;
}
void out(ll a) {if(a<0)putchar('-'),a=-a;if(a>=10)out(a/10);putchar(a%10+'0');}
#define pt(x) out(x),puts("")
inline void swap(ll &a, ll &b){ll t = a; a = b; b = t;}
inline void swap(int &a, int &b){int t = a; a = b; b = t;}
inline ll min(ll a, ll b){return a < b ? a : b;}
inline ll max(ll a, ll b){return a > b ? a : b;}
ll qpow(ll n,ll k,ll mod) {ll ans=1;while(k){if(k&1)ans=ans*n%mod;n=n*n%mod;k>>=1;}return ans%mod;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

double w, d;

void solve(){
    scanf("%Lf %Lf", &w, &d);
    double minn = min(w, d);
    ll tmp = Pi / minn;
    ll ans = 4;
    double l = sqrt(w * w + d * d);
    if(l * 2 - minn * 3 > eps) {
        double last;
        ans += tmp * 2;
        if(tmp) {
            last = Pi - tmp * minn;
            double cost = l - minn;
            ans += (last / cost);
            // if(last - l > eps) ans++;
        }    
        printf("%lld\n", ans);        
    }
    else{
        tmp = Pi / l;
        ans += tmp * 3;
        double last = Pi - tmp * l;
        if(last - minn > eps) ans += 2 * (last / minn);
        else{
            if(tmp) {
                last = Pi - (tmp - 1) * l;
                if(last - 2 * minn > eps) ans++;                
            }
        }
        printf("%lld\n", ans);
    }
}

int main() {
//    freopen("in.txt","r",stdin);
//    freopen("out.txt", "w", stdout);
    int t = 1;
    // t = rd();
    scanf("%d", &t);
    // cin >> t;
    while(t--)
        solve();
    return 0;
}
// 7 7.14143