[Codeforces]Codeforces Round #489 (Div. 2)

Nastya and an Array

输出有几种不同的数字

#pragma comment(linker, "/STACK:102400000,102400000")

#ifndef ONLINE_JUDGE

#include "stdafx.h"

#else

#include<bits/stdc++.h>

#endif

using namespace std;

typedef long long lint;

typedef vector<int> VI;

typedef pair<int, int> PII;

typedef queue<int> QI;

typedef map<int, int> MII;

void makedata() {

    freopen("input.txt", "w", stdout);

    fclose(stdout);

}

int p[], q[];

int main() {

#ifndef ONLINE_JUDGE

    freopen("input.txt", "r", stdin);

#endif

    //makedata();

    std::ios::sync_with_stdio(), cin.tie();

    int n, x;

    cin >> n;

    int ans = ;

    for (int i = ; i < n; i++) {

        cin >> x;

        if (x > ) {

            if (!p[x]) ans++;

            p[x] = true;

        }

        if (x < ) {

            if (!q[-x]) ans++;

            q[-x] = true;

        }

    }

    cout << ans << endl;

    return ;

}

Nastya Studies Informatics

把y/x分解质因数，a和b各自占有一部分且不重复

#pragma comment(linker, "/STACK:102400000,102400000")

#ifndef ONLINE_JUDGE

#include "stdafx.h"

#else

#include<bits/stdc++.h>

#endif

using namespace std;

typedef long long lint;

typedef vector<int> VI;

typedef pair<int, int> PII;

typedef queue<int> QI;

typedef map<int, int> MII;

void makedata() {

    freopen("input.txt", "w", stdout);

    fclose(stdout);

}

bool f[];

int p[];

int main() {

#ifndef ONLINE_JUDGE

    freopen("input.txt", "r", stdin);

#endif

    //makedata();

    std::ios::sync_with_stdio(), cin.tie();

    memset(f, true, sizeof(f));

    f[] = f[] = false;

    for (int i = ; i < ; i++) {

        for (int j = i + i; j < ; j += i) f[j] = false;

    }

    int l, r, x, y;

    cin >> l >> r >> x >> y;

    if (y % x != ) {

        cout <<  << endl;

        return ;

    }

    int m = y / x, sz = ;

    for (int i = ; i < ; i++) {

        if (m == ) break;

        if (!f[i]) continue;

        if (m % i == ) {

            int tmp = ;

            while (m % i == ) {

                m /= i;

                tmp *= i;

            }

            p[sz++] = tmp;

        }

    }

    if (m != ) p[sz++] = m;

    m = y / x;

    int ans = ;

    for (int i = ; i < ( << sz); i++) {

        int a = , b;

        for (int j = ; j < sz; j++) {

            if (i & ( << j)) a *= p[j];

        }

        b = m / a;

        if (l <= a * x && a * x <= r && l <= b * x && b * x <= r) ans++;

    }

    cout << ans << endl;

    return ;

}

Nastya and a Wardrobe

每次x2-0.5

#pragma comment(linker, "/STACK:102400000,102400000")

#ifndef ONLINE_JUDGE

#include "stdafx.h"

#else

#include<bits/stdc++.h>

#endif

using namespace std;

typedef long long lint;

typedef vector<int> VI;

typedef pair<int, int> PII;

typedef queue<int> QI;

typedef map<int, int> MII;

void makedata() {

    freopen("input.txt", "w", stdout);

    fclose(stdout);

}

inline lint pow(lint a, lint b, lint p) {

    lint rtn = ;

    while (b) {

        if (b & ) rtn = rtn * a % p;

        a = a * a % p;

        b >>= ;

    }

    return rtn;

}

int main() {

#ifndef ONLINE_JUDGE

    freopen("input.txt", "r", stdin);

#endif

    //makedata();

    std::ios::sync_with_stdio(), cin.tie();

    lint x, k;

    cin >> x >> k;

    lint p = ;

    if (k == ) {

        cout << (x *  % p) << endl;

        return ;

    }

    if (x == ) {

        cout <<  << endl;

        return ;

    }

    lint a = pow(, k, p) * (x % p) % p, b = pow(, k - , p);

    //a-b+0.5->2a-2b+1

    cout << (( * a -  * b + ) % p + p) % p << endl;

    return ;

}

/*

2(2x - 0.5) - 0.5

2x - 0.5 1

4x - 1.5 2

8x - 3.5 4

16x - 7.5 8

32x - 15.5 16

*/

Nastya and a Game

枚举左端点然后依次往右找，对于一段连续的1可以根据范围直接判断。因为S的最大值不超过2*10^18，所以向右找的次数不超过120次。

#pragma comment(linker, "/STACK:102400000,102400000")

#ifndef ONLINE_JUDGE

#include "stdafx.h"

#else

#include<bits/stdc++.h>

#endif

using namespace std;

typedef long long lint;

typedef vector<int> VI;

typedef pair<int, int> PII;

typedef queue<int> QI;

typedef map<int, int> MII;

void makedata() {

    freopen("input.txt", "w", stdout);

    fclose(stdout);

}

lint a[], s[];

int r[];

double ln[];

double inf = log(1LL << );

int main() {

#ifndef ONLINE_JUDGE

    freopen("input.txt", "r", stdin);

#endif

    //makedata();

    std::ios::sync_with_stdio(), cin.tie();

    int n, k;

    cin >> n >> k;

    s[] = ;

    for (int i = ; i <= n; i++) {

        cin >> a[i];

        s[i] = s[i - ] + a[i];

        ln[i] = log(a[i]);

    }

    for (int i = n; i >= ; i--) {

        if (a[i] == ) {

            if (a[i + ] == ) r[i] = r[i + ];

            else r[i] = i;

        }

    }

    lint ans = ;

    if (k == ) ans = n;

    for (int i = ; i <= n; i++) {

        int j = i + ;

        lint m = a[i];

        double p = ln[i];

        while (j <= n) {

            if (a[j] == ) {

                if (m % k == ) {

                    lint tmp = m / k;

                    if (s[j] - s[i - ] <= tmp && tmp <= s[r[j]] - s[i - ]) ans++;

                }

                j = r[j] + ;

            } else {

                if (p + ln[j] >= inf) break;

                p += ln[j];

                m *= a[j];

                if (m == (s[j] - s[i - ])*k) ans++;

                j++;

            }

        }

    }

    cout << ans << endl;

    return ;

}

Nastya and King-Shamans

两个线段树，一个维护sum，一个维护max。对每个询问，如果a[1]=0直接输出1，否则令m=1，显然此时[1,m]里没有萨满王。对于m之后的，想成为萨满王其能力值至少为sum(1,m)，找到第一个满足条件的萨满p，判断p是不是萨满王，如果不是则令m=p，直到找到或确定没有。

#pragma comment(linker, "/STACK:102400000,102400000")

#ifndef ONLINE_JUDGE

#include "stdafx.h"

#else

#include<bits/stdc++.h>

#endif

using namespace std;

typedef long long lint;

typedef vector<int> VI;

typedef pair<int, int> PII;

typedef queue<int> QI;

typedef map<int, int> MII;

void makedata() {

    freopen("input.txt", "w", stdout);

    fclose(stdout);

}

lint a[];

int n, q;

template <typename T> class SegmentTree {

    /*

    type:

    0:sum

    1:max

    */

private:

    T *data, *lazy;

    int type;

    void pushup(int rt) {

        if (type == )

            data[rt] = data[rt << ] + data[rt <<  | ];

        else if (type == )

            data[rt] = max(data[rt << ], data[rt <<  | ]);

    }

    void pushdown(int rt, T m) {

        if (lazy[rt] == ) return;

        lazy[rt << ] += lazy[rt];

        lazy[rt <<  | ] += lazy[rt];

        if (type == ) {

            data[rt << ] += (m - (m >> )) * lazy[rt];

            data[rt <<  | ] += (m >> ) * lazy[rt];

        } else if (type == ) {

            data[rt << ] += lazy[rt];

            data[rt <<  | ] += lazy[rt];

        }

        lazy[rt] = ;

    }

public:

    SegmentTree(int n, int t) : data((T *)malloc((n << ) * sizeof(T))), lazy((T *)malloc((n << ) * sizeof(T))), type(t) {}

    void Build(T * base, int l, int r, int rt) {

        lazy[rt] = ;

        if (l == r) data[rt] = base[l];

        else {

            int mid = (l + r) >> ;

            Build(base, l, mid, rt << );

            Build(base, mid + , r, rt <<  | );

            pushup(rt);

        }

    }

    void Modify(int l, int r, int rt, int L, int R, T v) {

        if (L <= l && R >= r) {

            lazy[rt] += v;

            if (type == )

                data[rt] += v * (r - l + );

            else if (type == )

                data[rt] += v;

            return;

        }

        pushdown(rt, r - l + );

        int mid = (l + r) >> ;

        if (L <= mid)

            Modify(l, mid, rt << , L, R, v);

        if (R > mid)

            Modify(mid + , r, rt <<  | , L, R, v);

        pushup(rt);

    }

    T QueryPoint(int l, int r, int rt, int val) {

        if (l == r) return data[rt];

        pushdown(rt, r - l + );

        int mid = (l + r) >> ;

        T ret = ;

        if (val <= mid) ret = QueryPoint(l, mid, rt << , val);

        else ret = QueryPoint(mid + , r, rt <<  | , val);

        pushup(rt);

        return ret;

    }

    T QuerySegment(int l, int r, int rt, int L, int R) {

        pushdown(rt, r - l + );

        if (L == l && R == r) return data[rt];

        int mid = (l + r) >> ;

        if (R <= mid) return QuerySegment(l, mid, rt << , L, R);

        if (mid < L) return QuerySegment(mid + , r, rt <<  | , L, R);

        if (type == )

            return QuerySegment(l, mid, rt << , L, mid) + QuerySegment(mid + , r, rt <<  | , mid + , R);

        else if (type == )

            return max(QuerySegment(l, mid, rt << , L, mid), QuerySegment(mid + , r, rt <<  | , mid + , R));

    }

    int find(int l, int r, int rt, int p, T x) {

        if (r <= p) return -;

        if (data[rt] < x) return -;

        if (l == r) return l;

        int mid = (l + r) >> ;

        if (l > p) {

            if (data[rt << ] >= x) return find(l, mid, rt << , p, x);

            else return find(mid + , r, rt <<  | , p, x);

        }

        int rtn = find(l, mid, rt << , p, x);

        if (rtn != -) return rtn;

        return find(mid + , r, rt <<  | , p, x);

    }

};

SegmentTree<lint> Tsum(, ), Tmax(, );

int main() {

#ifndef ONLINE_JUDGE

    freopen("input.txt", "r", stdin);

#endif

    //makedata();

    std::ios::sync_with_stdio(), cin.tie();

    cin >> n >> q;

    for (int i = ; i <= n; i++) cin >> a[i];

    Tsum.Build(a, , n, );

    Tmax.Build(a, , n, );

    while (q--) {

        int p;

        lint x;

        cin >> p >> x;

        Tsum.Modify(, n, , p, p, x - a[p]);

        Tmax.Modify(, n, , p, p, x - a[p]);

        a[p] = x;

        if (a[] == ) {

            cout <<  << endl;

            continue;

        }

        int m = ;

        while () {

            lint sum = Tsum.QuerySegment(, n, , , m);

            int nex = Tmax.find(,n,,m,sum);

            if (nex == -) {

                cout << - << endl;

                break;

            }

            if (a[nex] == Tsum.QuerySegment(, n, , , nex - )) {

                cout << nex << endl;

                break;

            }

            m = nex;

        }

    }

    return ;

}

巴特西

[Codeforces]Codeforces Round #489 (Div. 2)

最新文章

热门文章