牛客小白月赛39【解题报告】

A 憧憬

分析

直接暴力 O(n2)O(n^2)O(n2) 做

代码实现

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

template <typename T>
inline void read(T& x)
{
    x = 0; int f = 1; char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
    while(isdigit(ch))  {x = x * 10 + ch - '0', ch = getchar();}
    x *= f;
}

template <typename T>
void print(T x)
{
    if(x < 0) putchar('-'), x = -x;
    if(x > 9) print(x / 10);
    putchar(x % 10 + '0');
}

template <typename T>
void print(T x, char ch)
{
    print(x), putchar(ch);
}

typedef double db;
typedef long long ll;

const int M = (int)1e5;
const int N = (int)1e5;
const int inf = 0x3f3f3f3f;
const ll mod = (ll)1e9 + 7;

int n;
vector<pair<int, int>> v;

bool pall(int a, int b, int c)
{
    pair<int, int> ad = make_pair(v[a].first + v[b].first, v[a].second + v[b].second);
    return ad.first * v[c].second == ad.second * v[c].first;
}

void work()
{
    read(n);
    v.push_back(make_pair(-1, -1));
    for(int i = 1, a, b, c, d; i <= n + 1; ++i)
    {
        read(a), read(b), read(c), read(d);
        v.push_back(make_pair(c - a, d - b));
    }
    for(int i = 1; i <= n; ++i)
    {
        for(int j = i + 1; j <= n; ++j)
        {
            if(pall(i, j, n + 1))
            {
                printf("YES\n");
                return;
            }
        }
    }
    printf("NO\n");
}

int main()
{
//    ios::sync_with_stdio(0);
//    cin.tie(0); cout.tie(0);
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
//    int T; read(T);
//    for(int ca = 1; ca <= T; ++ca)
//    {
//        work();
//    }
    work();
//    cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
    return 0;
}

B 欢欣

分析

语法题QAQ

代码实现

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

template <typename T>
inline void read(T& x)
{
    x = 0; int f = 1; char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
    while(isdigit(ch))  {x = x * 10 + ch - '0', ch = getchar();}
    x *= f;
}

template <typename T>
void print(T x)
{
    if(x < 0) putchar('-'), x = -x;
    if(x > 9) print(x / 10);
    putchar(x % 10 + '0');
}

template <typename T>
void print(T x, char ch)
{
    print(x), putchar(ch);
}

typedef double db;
typedef long long ll;

const int M = (int)1e5;
const int N = (int)1e5;
const int inf = 0x3f3f3f3f;
const ll mod = (ll)1e9 + 7;

void work()
{
   string s; cin >> s;
   cout << s.find("QAQ") + 1 << "\n";
}

int main()
{
//    ios::sync_with_stdio(0);
//    cin.tie(0); cout.tie(0);
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
//    int T; read(T);
//    for(int ca = 1; ca <= T; ++ca)
//    {
//        work();
//    }
    work();
//    cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
    return 0;
}

D 绝望

分析

因为一个非 111 数 xxx 乘以另一个非 111 的数字 yyy 之后，乘积 xyxyxy 一定不是质数.

所以势能线段树即可.

代码实现

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

template <typename T>
inline void read(T& x)
{
    x = 0; int f = 1; char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
    while(isdigit(ch))  {x = x * 10 + ch - '0', ch = getchar();}
    x *= f;
}

template <typename T>
void print(T x)
{
    if(x < 0) putchar('-'), x = -x;
    if(x > 9) print(x / 10);
    putchar(x % 10 + '0');
}

template <typename T>
void print(T x, char ch)
{
    print(x), putchar(ch);
}

typedef double db;
typedef long long ll;

const int M = (int)2e5;
const int N = (int)5e5;
const int inf = 0x3f3f3f3f;
const ll mod = (ll)1e9 + 7;

bool is_prime[N + 5];
int prime[N + 5], cnt;
int v[N + 5];

void init()
{
    memset(is_prime, 1, sizeof(is_prime));
    is_prime[0] = is_prime[1] = 0;
    for(int i = 2; i <= N; ++i)
    {
        if(is_prime[i])
        {
            prime[++cnt] = i;
            v[i] = i;
        }
        for(int j = 1; j <= cnt && i * prime[j] <= N; ++j)
        {
            is_prime[i * prime[j]] = 0;
            v[i * prime[j]] = prime[j];
            if(i % prime[j] == 0)
            {
                break;
            }
        }
    }
}

struct segT
{
    int one[M * 4 + 5];
    int s[M * 4 + 5], val[M * 4 + 5];

    inline int lc(int k) {return k<<1;}
    inline int rc(int k) {return k<<1|1;}
    inline void push_up(int k) {s[k] = s[lc(k)] + s[rc(k)], one[k] = one[lc(k)]|one[rc(k)];}

    void build(int k, int l, int r)
    {
        if(l == r)
        {
            read(val[k]);
            one[k] = (val[k] == 1);
            s[k] = is_prime[val[k]];
            return;
        }
        int mid = (l + r) >> 1;
        build(lc(k), l, mid);
        build(rc(k), mid + 1, r);
        push_up(k);
    }

    void update(int k, int l, int r, int a, int b, int c)
    {
        if(one[k] == 0 && s[k] == 0) return;
        if(l == r)
        {
            if(l == 1) return;
            if(one[k] == 1 && c == 1 && is_prime[l])
            {
                one[k] = 0, s[k] = 1;
            }
            else
            one[k] = s[k] = 0;
            //printf("k=%d l=%d r=%d a=%d b=%d c=%d s=%d\n", k, l, r, a, b, c, s[k]);
            return;
        }
        int mid = (l + r) >> 1;
        if(a <= mid) update(lc(k), l, mid, a, b, c);
        if(mid < b)  update(rc(k), mid + 1, r, a, b, c);
        push_up(k);
        //printf("k=%d l=%d r=%d s=%d\n", k, l, r, s[k]);
    }

    int query(int k, int l, int r, int a, int b)
    {
        if(l >= a && r <= b) return s[k];
        int mid = (l + r) >> 1, s = 0;
        if(a <= mid) s += query(lc(k), l, mid, a, b);
        if(mid < b)  s += query(rc(k), mid + 1, r, a, b);
        return s;
    }
} tr;

void work()
{
    init();
    int n, m; read(n), read(m);
    tr.build(1, 1, n);
    for(int i = 1, op, l, r, x; i <= m; ++i)
    {
        read(op);
        if(op == 1)
        {
            read(l), read(r), read(x);
            if(x) tr.update(1, 1, n, l, r, x);
            print(tr.query(1, 1, n, l, r), '\n');
        }
        else if(op == 2)
        {
            read(l), read(r);
            print(tr.query(1, 1, n, l, r), '\n');
        }
    }
}

int main()
{
//    ios::sync_with_stdio(0);
//    cin.tie(0); cout.tie(0);
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
//    int T; read(T);
//    for(int ca = 1; ca <= T; ++ca)
//    {
//        work();
//    }
    work();
//    cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
    return 0;
}

E 迷惘

分析

就模拟呗

代码实现

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

template <typename T>
inline void read(T& x)
{
    x = 0; int f = 1; char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
    while(isdigit(ch))  {x = x * 10 + ch - '0', ch = getchar();}
    x *= f;
}

template <typename T>
void print(T x)
{
    if(x < 0) putchar('-'), x = -x;
    if(x > 9) print(x / 10);
    putchar(x % 10 + '0');
}

template <typename T>
void print(T x, char ch)
{
    print(x), putchar(ch);
}

typedef double db;
typedef long long ll;

const int M = (int)1e5;
const int N = (int)1e5;
const int inf = 0x3f3f3f3f;
const ll mod = (ll)1e9 + 7;

int n;

int cal(int x)
{
    if(x == 0) return 0;
    vector<int> v;
    while(x)
    {
        v.push_back(x & 1);
        x >>= 1;
    }
    int p = 0; while(v[p] == 0) ++p; int s = 0;
    for(int i = p; i < (int)v.size(); ++i) s = s * 2 + v[i];
    return s;
}

void work()
{
    read(n);
    ll s = 0;
    for(int i = 1, a; i <= n; ++i)
    {
        read(a);
        s += cal(a);
    }
    print(s, '\n');
}

int main()
{
//    ios::sync_with_stdio(0);
//    cin.tie(0); cout.tie(0);
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
//    int T; read(T);
//    for(int ca = 1; ca <= T; ++ca)
//    {
//        work();
//    }
    work();
//    cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
    return 0;
}

G 冷静

分析

预处理3e6内所有数的最小质因子，离线所有询问，树状数组维护答案.

代码实现

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

template <typename T>
inline void read(T& x)
{
    x = 0; int f = 1; char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
    while(isdigit(ch))  {x = x * 10 + ch - '0', ch = getchar();}
    x *= f;
}

template <typename T>
void print(T x)
{
    if(x < 0) putchar('-'), x = -x;
    if(x > 9) print(x / 10);
    putchar(x % 10 + '0');
}

template <typename T>
void print(T x, char ch)
{
    print(x), putchar(ch);
}

typedef double db;
typedef long long ll;

const int M = (int)3e6;
const int N = (int)1e5;
const int inf = 0x3f3f3f3f;
const ll mod = (ll)1e9 + 7;

bool is_prime[M + 5];
int prime[M + 5], cnt;
int v[M + 5];

void init()
{
    memset(is_prime, 1, sizeof(is_prime));
    is_prime[0] = is_prime[1] = 0;
    for(int i = 2; i <= M; ++i)
    {
        if(is_prime[i])
        {
            prime[++cnt] = i;
            v[i] = i;
        }
        for(int j = 1; j <= cnt && i * prime[j] <= M; ++j)
        {
            is_prime[i * prime[j]] = 0;
            v[i * prime[j]] = prime[j];
            if(i % prime[j] == 0)
            {
                break;
            }
        }
    }
}

struct TA
{
    int n; ll tree[M + 5];
    void init(int _n) {n = _n; for(int i = 0; i <= n; ++i) tree[i] = 0;}
    inline int lowbit(int n) {return n&-n;}
    void add(int a, ll b) {for(int i = a; i <= n; i += lowbit(i)) tree[i] += b;}
    ll ask(int r) {ll s = 0; for(int i = r; i; i -= lowbit(i)) s += tree[i]; return s;}
    ll ask(int l, int r) {return ask(r) - ask(l - 1);}
} tr;

struct node
{
    int n, k, id;
    bool operator<(const node& b) const
    {
        return n < b.n;
    }
} s[M + 5];

int ans[M + 5];

void work()
{
    init();
    int q; read(q);
    for(int i = 1; i <= q; ++i)
    {
        read(s[i].n), read(s[i].k), s[i].id = i;
    }
    sort(s + 1, s + q + 1);
    tr.init(M);
    for(int i = 1, p = 1; i <= q; ++i)
    {
        while(p + 1 <= s[i].n) tr.add(v[++p], 1);
        ans[s[i].id] = tr.ask(M) - tr.ask(s[i].k - 1);
    }
    for(int i = 1; i <= q; ++i) print(ans[i], '\n');
}

int main()
{
//    ios::sync_with_stdio(0);
//    cin.tie(0); cout.tie(0);
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
//    int T; read(T);
//    for(int ca = 1; ca <= T; ++ca)
//    {
//        work();
//    }
    work();
//    cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
    return 0;
}

H 终别

分析

因为魔法只能使用一次，所以枚举魔法的释放位置，这样原序列就被分成了一个前缀和一个后缀，O(n)O(n)O(n) 预处理出前缀和后缀的花费即可.

代码实现

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

template <typename T>
inline void read(T& x)
{
    x = 0; int f = 1; char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
    while(isdigit(ch))  {x = x * 10 + ch - '0', ch = getchar();}
    x *= f;
}

template <typename T>
void print(T x)
{
    if(x < 0) putchar('-'), x = -x;
    if(x > 9) print(x / 10);
    putchar(x % 10 + '0');
}

template <typename T>
void print(T x, char ch)
{
    print(x), putchar(ch);
}

typedef double db;
typedef long long ll;

const int M = (int)1e6;
const int N = (int)1e5;
const int inf = 0x3f3f3f3f;
const ll mod = (ll)1e9 + 7;

int n, a[M + 5], b[M + 5];
ll pre[M + 5], suf[M + 5];

void work()
{
    read(n); for(int i = 1; i <= n; ++i) read(a[i]);
    memcpy(b, a, sizeof(a));
    pre[0] = 0;
    for(int i = 1; i <= n; ++i)
    {
        if(b[i] >= 0) pre[i] = pre[i - 1] + b[i], b[i + 2] -= b[i], b[i + 1] -= b[i], b[i] -= b[i];
        else pre[i] = pre[i - 1];
    }
    memcpy(b, a, sizeof(a));
    suf[n + 1] = 0;
    for(int i = n; i >= 1; --i)
    {
        if(b[i] >= 0) suf[i] = suf[i + 1] + b[i], b[i - 2] -= b[i], b[i - 1] -= b[i], b[i] -= b[i];
        else suf[i] = suf[i + 1];
    }
    ll mi = (ll)1e18;
    for(int i = 2; i <= n; ++i)
    {
        mi = min(mi, pre[i - 2] + suf[i + 1]);
    }
    print(mi, '\n');
}

int main()
{
//    ios::sync_with_stdio(0);
//    cin.tie(0); cout.tie(0);
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
//    int T; read(T);
//    for(int ca = 1; ca <= T; ++ca)
//    {
//        work();
//    }
    work();
//    cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
    return 0;
}
全部评论

相关推荐

头像
他说你很帅
04-24 16:56
海康威视_硬件_硬件产品研发中心(实习员工)
点赞 评论 收藏
转发
头像
不想打工的里根很勇敢
昨天 15:43
语音/视频/图形开发
Zoom要求员工重返办公室，这是不是有点好笑
由于疫情的消退，视频会议市场似乎正在回归平淡。Zoom迫使员工回到办公室的决定，很可能会导致该公司业务乃至这个细分市场再次陷入困境。Zoom是领先的视频会议平台，也是最成功的远程工具之一。当这家业界闻名的远程工作软件开发商要求自己的员工放弃远程工作而重返办公室时，无疑向客户发出了令人质疑并且错误的信号。Zoom公开表示，该公司员工不再适用远程工作的模式，表明远程模式替代不了办公室办公。这种做法就像一家汽车公司要求员工不要开车而是乘坐公共交通工具一样可笑。鉴于近年来疫情加剧的远程办公推动了视频会议平台的销售增长，Zoom的做法可能会显著地减少其市场份额，同时也波及整个细分行业。
投递ZOOM等公司7个岗位 >
点赞 评论 收藏
转发
头像 头像
26加瓦鼠鼠
04-09 09:31
莆田学院 计算机类
点赞 评论 收藏
转发
头像
Yoshikitties
04-06 22:52
东南大学 计算机类
点赞 评论 收藏
转发
头像
五四好青年Mingz
04-25 18:52
门头沟学院 电子信息类
点赞 评论 收藏
转发
1 收藏 评论
分享

全站热榜

正在热议
# 牛友的五一计划 #
28788次浏览 497人参与
# 市场营销面经 #
1891次浏览 82人参与
# 牛客帮帮团来啦！有问必答 #
426482次浏览 8085人参与
# 许愿池 #
67568次浏览 1489人参与
# 晒一晒我的offer #
2877510次浏览 50301人参与
# 2022届毕业生现状 #
287887次浏览 4123人参与
# 实习好累，可以辞职全力准备秋招吗 #
2878次浏览 61人参与
# 你的秋招进展怎么样了 #
451571次浏览 13001人参与
# 如何看待offer收割机的行为 #
199885次浏览 3044人参与
# 互联网公司评价 #
64398次浏览 913人参与
# 非技术岗薪资爆料 #
11585次浏览 225人参与
# 硬件人的春招flag #
14832次浏览 204人参与
# 双非本科求职如何逆袭 #
176621次浏览 2647人参与
# 找工作，你会甘心进小厂还是猛冲大厂 #
26292次浏览 262人参与
# 23届的你们都什么时候入职？ #
77618次浏览 692人参与
# 产品实习，你更倾向大公司or小公司 #
31796次浏览 500人参与
# 秋招开了，你想投哪些公司呢 #
102975次浏览 3136人参与
# 浅聊一下我实习的辛苦费 #
71939次浏览 656人参与
# 提前批真的不会影响正式批吗 #
18419次浏览 233人参与
# 在国企工作的人，躺平了吗？ #
75027次浏览 922人参与
牛客网
牛客企业服务