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 绝望

分析

因为一个非 111xxx 乘以另一个非 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;
}