牛客周赛 Round 70 A~G

Preface

感觉要比难呢,应该是没太多人做了,导致大家没去开吧。

又是斗志颓废的一集,最近该忙期末考试了。

我会在代码一些有必要的地方加上注释,签到题可能一般就不会写了.

以下是代码火车头:

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <set>
#include <queue>
#include <map>
#include <unordered_map>
#include <iomanip>
#define endl '\n'
#define int long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define rep2(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;

template<typename T>
void cc(const vector<T> &tem) {
    for (const auto &x: tem) cout << x << ' ';
    cout << endl;
}

template<typename T>
void cc(const T &a) { cout << a << endl; }

template<typename T1, typename T2>
void cc(const T1 &a, const T2 &b) { cout << a << ' ' << b << endl; }

template<typename T1, typename T2, typename T3>
void cc(const T1 &a, const T2 &b, const T3 &c) { cout << a << ' ' << b << ' ' << c << endl; }

void cc(const string &s) { cout << s << endl; }

void fileRead() {
#ifdef LOCALL
    freopen("D:\\AADVISE\\Clioncode\\untitled1\\in.txt", "r", stdin);
    freopen("D:\\AADVISE\\Clioncode\\untitled1\\out.txt", "w", stdout);
#endif
}

void kuaidu() { ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); }

inline int max(int a, int b) {
    if (a < b) return b;
    return a;
}

inline double max(double a, double b) {
    if (a < b) return b;
    return a;
}

inline int min(int a, int b) {
    if (a < b) return a;
    return b;
}

inline double min(double a, double b) {
    if (a < b) return a;
    return b;
}

void cmax(int &a, const int &b) { if (b > a) a = b; }
void cmin(int &a, const int &b) { if (b < a) a = b; }
void cmin(double &a, const double &b) { if (b < a) a = b; }
void cmax(double &a, const double &b) { if (b > a) a = b; }
using PII = pair<int, int>;
using i128 = __int128;
using vec_int = std::vector<int>;
using vec_char = std::vector<char>;
using vec_double = std::vector<double>;
using vec_int2 = std::vector<std::vector<int> >;
using que_int = std::queue<int>;

Problem A. 小苯晨跑

没什么好说的,直接上代码

//--------------------------------------------------------------------------------
const int N = 1e5 + 10;
const int M = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 1e16;
int n, m, T;
 
//--------------------------------------------------------------------------------
//struct or namespace:
 
int A[N];
//--------------------------------------------------------------------------------
 
signed main() {
    fileRead();
    kuaidu();
    T = 1;
    cin >> T;
    while (T--) {
        rep(i, 1, 4) cin >> A[i];
        rep(i, 1, 4) {
            if (A[i] != A[1]) {
                cc("YES");
                goto Z;
            }
        }
        cc("NO");
    Z:;
 
    }
    return 0;
}
/*
 
 
*/

Problem B. 小苯过马路

一开始读错题了,代码写的很丑...

//--------------------------------------------------------------------------------
const int N = 1e5 + 10;
const int M = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 1e16;
int n, m, T;
 
//--------------------------------------------------------------------------------
//struct or namespace:
 
//--------------------------------------------------------------------------------
 
signed main() {
    fileRead();
    kuaidu();
    T = 1;
    //cin >> T;
    while (T--) {
        int x, y, k, t;
        cin >> x >> y >> k >> t;
        char c; cin >> c;
        int ans = 0;
        if (c == 'R') {
            ans += k;
            ans += t;
            cc(ans);
            goto Z;
        }
        else {
            ans += k;
            if (t - k <= 0) {
                cc(t);
                goto Z;
            }
            ans += x;
            ans += t;
            cc(ans);
 
        }
 
 
    Z:;
 
    }
    return 0;
}
/*
 
 
*/

Problem C. 小苯的字符串染色

感觉很搞笑呢,次数不超过次,所以每一次直接选择长度为的就好了,这题是脑筋急转弯。

//--------------------------------------------------------------------------------
const int N = 1e5 + 10;
const int M = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 1e16;
int n, m, T;
 
//--------------------------------------------------------------------------------
//struct or namespace:
 
//--------------------------------------------------------------------------------
 
signed main() {
    fileRead();
    kuaidu();
    T = 1;
    cin >> T;
    while (T--) {
        cin >> n;
        string s; cin >> s;
 
        vec_int ans;
        rep(i, 0, n - 1) {
            if (s[i] == '1') ans.push_back(i + 1);
        }
        cc(ans.size());
        for (auto& x : ans) cc(x, x);
    }
    return 0;
}
/*
 
 
*/

Problem D. 小苯的能量项链

又是读错题的一集,怎么老是读错题(bu

要注意去掉项链的珠子不算为保留的能量,能量最后只会剩下最多两个珠子。

可以枚举第个珠子是我们剩下的左边的珠子,那剩下的右边的珠子就是一个区间内的最大值。的时候,右边选择的区间就是,当自增的时候,右边的区间的左半部分也要自增。有个小注意的地方就是我们选择的区间不能包括,所以左半部分还要和取一个

维护区间直接了一个封装的线段树。

//--------------------------------------------------------------------------------
const int N = 5e5 + 10;
const int M = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 1e16;
int n, m, T;
 
//--------------------------------------------------------------------------------
//struct or namespace:
class SEG {
#define xl x+x
#define xr x+x+1
    //TODO 节点维护信息、apply函数、up函数
    struct info {
        int mmax = 0;
        void apply(int k) {
            // sum += siz * k;
            mmax += k;
        }
        friend info operator+(const info& q1, const info& q2) {
            info q;
            q.mmax = max(q1.mmax, q2.mmax);
            // q.siz = q1.siz + q2.siz;
            // q.sum = q1.sum + q2.sum;
            return q;
        }
    };
 
    int  L, R;
    info F[unsigned(N * 2.1)];
    void init(int x, int l, int r) {
        if (l == r) { F[x] = info(); return; }
        int mid = l + r >> 1;
        init(xl, l, mid), init(xr, mid + 1, r);
        F[x] = F[xl] + F[xr];
    }
    void add(int x, int l, int r, int l1, int r1, int k) {
        if (l1 > r1) return;
        if (l1 <= l and r <= r1) { F[x].apply(k); return; }
        int mid = l + r >> 1;
        if (r1 <= mid) add(xl, l, mid, l1, r1, k);
        else if (mid < l1) add(xr, mid + 1, r, l1, r1, k);
        else add(xl, l, mid, l1, mid, k), add(xr, mid + 1, r, mid + 1, r1, k);
        F[x] = F[xl] + F[xr];
    }
    info qry(int x, int l, int r, int l1, int r1) {
        if (l1 > r1) return info();
        if (l1 <= l and r <= r1)  return F[x];
        int mid = l + r >> 1;
        if (r1 <= mid) return qry(xl, l, mid, l1, r1);
        else if (mid < l1) return qry(xr, mid + 1, r, l1, r1);
        else { return qry(xl, l, mid, l1, mid) + qry(xr, mid + 1, r, mid + 1, r1); }
    }
#undef xl
#undef xr
public:
    void clear(int l, int r) { L = l, R = r; init(1, l, r); }
    void add(int l, int r, int k) { add(1, L, R, l, r, k); }
    info qry(int l, int r) { return qry(1, L, R, l, r); }
}seg;
int A[N];
//--------------------------------------------------------------------------------
 
signed main() {
    fileRead();
    kuaidu();
    T = 1;
    cin >> T;
    while (T--) {
        cin >> n >> m;
        seg.clear(1, n);
        rep(i, 1, n) {
            cin >> A[i];
            seg.add(i, i, A[i]);
        }
        int mmax = 0;
        if (m >= n - 2) {
            sort(A + 1, A + n + 1);
            cc(A[n] + A[n - 1]);
            continue;
        }
        rep(i, 1, m + 1) {
            cmax(mmax, A[i] + seg.qry(max(i + 1, n - m + i - 1), n).mmax);
        }
 
        cc(mmax);
 
    }
    return 0;
}
/*
 
 
*/

Problem E. 小苯的最短路

一看题就直接打表找规律了。

定义的意思是从的异或和

是奇数的时候,就直接是是偶数的时候就是

接下来只要知道函数怎么求就好了。

打表规律得,去掉的情况,剩下的存在循环节

依次是

能看出来第一项都是,第三项都是,第二项首项是,每次增,第四项每次都是第二项

所以写出来这个规律就好了。

//--------------------------------------------------------------------------------
const int N = 1e5 + 10;
const int M = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 1e16;
int n, m, T;
vector<PII> A[N];
int dis[N];
bool vis[N];
//--------------------------------------------------------------------------------
//struct or namespace:
struct node {
    int to;
    int val;
    bool operator<(const node& q1) const {
        return q1.val < val;
    }
};
//--------------------------------------------------------------------------------
 
int dfs(int x) {
    if (x == 1) return 0;
    if (x == 2) return 2;
    int y = (x - 3) % 4;
    if (y == 0) return 1;
    if (y == 2) return 0;
    int num = (x - 3) / 4 + 1;
    if (y == 1) {
        return (num * 4 + 1);
    }
    else {
        return (num * 4 + 2);
    }
 
 
 
}
 
signed main() {
    fileRead();
    kuaidu();
    T = 1;
    cin >> T;
    while (T--) {
        cin >> n;
        if (n % 2 == 1) {
            cc(dfs(n));
        }
        else {
            cc(dfs(n - 1) ^ (n + 1));
        }
 
 
    }
    return 0;
}
/*
 
 
*/

Problem F. 小苯的优雅好序列

看题解才过的。

首先能知道经典作差,不变的是两项的差,所以作差就好了。

然后发现找做差的因数。但是一开始是想的取所有相邻的数(找相邻的就可以推广到所有)的差的,但是之后却无从下手,因为枚举的因数代表的是加上后的数是多少,但是如果取了,就无法知道加上的是谁了。(我知道这里写的云里雾里,看一下样例就好了)。

所以我们可以找到第一对相邻的不一样的数,不需要再看别的了,因为需要保证所有的都满足,然后就枚举差值的因数,写一个函数正常的扫就好了。

函数就去判断相邻的数字是不是都是有倍数关系的。

时间复杂度是

//--------------------------------------------------------------------------------
const int N = 5e4 + 10;
const int M = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 1e16;
int n, m, T;
 
int A[N];
//--------------------------------------------------------------------------------
//struct or namespace:
namespace ms {
    namespace kuai {
        int kuai(int a, int b) {
            int l = 1;
            while (b) {
                if (b % 2) l = l * a % mod;
                b /= 2;
                a = a * a % mod;
            }
            return l;
        }
 
        int ni(int a) { return kuai(a, mod - 2); }
    }
 
    namespace ni {
        vector<int> fact, infact;
 
        void cal_ni() {
            fact.resize(N + 5);
            infact.resize(N + 5);
            fact[0] = infact[0] = 1;
            infact[1] = 1;
            for (int i = 1; i < N; i++) {
                fact[i] = fact[i - 1] * i % mod;
                if (i >= 2) infact[i] = (mod - mod / i) * infact[mod % i] % mod;
            }
        }
    }
 
    namespace pri {
        vector<int> pri;
        bool ispri[N], biao[N];
 
        void cal_pri() {
            for (int i = 2; i < N; i++) {
                if (biao[i]) continue;
                pri.push_back(i);
                for (int j = i; j < N; j += i) biao[j] = 1;
            }
            for (auto &x: pri) ispri[x] = 1;
        }
    }
 
    namespace gcd {
        int gcd(int a,int b) {
            if (!b) return a;
            return gcd(b, a % b);
        }
    }
}
 
int B[N];
//--------------------------------------------------------------------------------
 
bool check(int add) {
    if (add <= 0 or add > m) return 0;
 
    rep(i, 1, n) {
        B[i] = A[i] + add;
    }
    int fl = 1;
    rep(i, 2, n) {
        if (B[i] % B[i - 1] == 0 or B[i - 1] % B[i] == 0) {
        } else fl = 0;
    }
    return fl;
}
 
signed main() {
    fileRead();
    kuaidu();
    T = 1;
    cin >> T;
    while (T--) {
        cin >> n >> m;
        rep(i, 1, n) {
            cin >> A[i];
        }
        if (n == 1) {
            cc(m, m * (m + 1) / 2);
            continue;
        }
        using ms::gcd::gcd;
        int x = 0, y = 0;
        rep(i, 1, n-1) {
            if (A[i] != A[i + 1]) {
                x = i, y = i + 1;
                break;
            }
        }
        if (x == 0 and y == 0) {
            cc(m, m * (m + 1) / 2);
            continue;
        }
        if (A[x] > A[y]) swap(x, y);
        int t;
        t = A[y] - A[x];
        int ans = 0;
        int sum = 0;
        for (int i = 1; i * i <= t; i++) {
            if (t % i) continue;
            if (check(i - A[x])) ans++, sum += i - A[x];
            // ans += check(i);
            if (i != t / i and check(t / i - A[x])) ans++, sum += t / i - A[x];
        }
        cc(ans, sum);
    }
    return 0;
}
 
/*
 
 
*/

Problem G. 小苯的树上操作

其实和的难度应该是差距不大的,但是个人更擅长图上的题一些。

先定义代表以的子树内的最大的答案,数组代表着以为根的最大答案。

首先能知道根据这两个操作推出:

如果我们当前的点的权值是的,那么我们一定是子树的贡献的求和,即

如果小于的时候,那么我们要么是当前的点权加上子树之和,要么就是选择子树的一个最大值。

那么如何从推广到呢?

如果的点权大于等于,那么,如果小于呢?当是由子树最大值得出的,我们就需要判断出子树最大值是哪个子树,如果和我们当前的子树一样,那就需要用子树次大值推出来,如果不一样就可以用子树最大值推出来就好了。

详细的式子直接看函数就好了。

//--------------------------------------------------------------------------------
const int N = 2e5 + 10;
const int M = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 1e16;
int n, m, T;
vec_int A[N];
int to1[N], to2[N], val[N];
int dp[N], g[N];
//--------------------------------------------------------------------------------
//struct or namespace:
 
//--------------------------------------------------------------------------------
 
void dfs(int x,int pa) {
    // int mmax = 0, mmax2 = 0;
    dp[x] = val[x];
    for (auto &y: A[x]) {
        if (y == pa) continue;
        dfs(y, x);
        if (dp[y] >= dp[to1[x]]) to2[x] = to1[x], to1[x] = y;
        else if (dp[y] >= dp[to2[x]]) to2[x] = y;
        dp[x] += dp[y];
    }
    cmax(dp[x], dp[to1[x]]);
}
 
void dfs2(int x,int pa) {
    for (auto &y: A[x]) {
        if (y == pa) continue;
		g[y] = g[x];
        if (val[x] >= 0) g[y] = g[x];
        else {
            if (to1[x] == y) cmax(g[y], dp[y] + dp[to2[x]]);
            else cmax(g[y], dp[y] + dp[to1[x]]);
        }
        dfs2(y, x);
    }
}
 
signed main() {
    fileRead();
    kuaidu();
    T = 1;
    cin >> T;
    while (T--) {
        cin >> n;
        rep(i, 1, n) {
            A[i].clear();
            g[i] = to1[i] = to2[i] = 0;
        }
 
        rep(i, 1, n) cin >> val[i];
        rep(i, 1, n-1) {
            int a, b;
            cin >> a >> b;
            A[a].push_back(b);
            A[b].push_back(a);
        }
        dfs(1, 0);
        g[1] = dp[1];
        dfs2(1, 0);
        int ans = 0;
        rep(i, 1, n) cmax(ans, g[i]);
        // cc(dp[1]);
        cc(ans);
    }
    return 0;
}
 
/*
 
 
*/

PostScript

打算开始一下,还没有做过。

之前说好的打,到现在还没有开始打。。。

到现在分数都还是...