个人空间 - AcWing

schinapi

访客：9933

发消息

离线：4天前

题解 AcWing 244. 谜一样的牛

schinapi
1个月前

题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include<iostream>
#include<set>
using namespace std;

const int N = 1e5 + 10;
int a[N], tr[N], ans[N];
int n;

int lowbit(int x)
{
    return x & -x;
}
void add(int x, int c)//可以不用了；
{
    for (int i = x; i <= n; i += lowbit(i)) tr[i] += c;
}
int sum(int x)
{
    int res = 0;
    for (int i = x; i; i -= lowbit(i)) res += tr[i];
    return res;
}


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

    for (int i = 1; i <= n; i ++) tr[i] = lowbit(i);//初始化；

    for (int i = n; i; i --)
    {
        int k = a[i] + 1;

        int l = 1, r = n;
        while(l < r)
        {
            int mid = l + r >> 1;
            if (sum(mid) >= k) r = mid;
            else l = mid + 1;
        }
        ans[i] = l;
        add(l, - 1);
    }
    for (int i = 1; i <= n; i ++) cout << ans[i] << endl;
    return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

题解 AcWing 243. 一个简单的整数问题2

schinapi
1个月前

题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include<iostream>
using namespace std;

typedef long long LL;
const int N = 1e5 + 10;

int n, m;

LL a[N], tr[N], tri[N];

int lowbit(int x)
{
    return x & -x;
}

void add(int x, LL c)
{
    for (int i = x; i <= n; i += lowbit(i)) 
    {
        tr[i] += c;
        tri[i] += c * x;
    }
}

LL sum(int x)
{
    LL res = 0;
    for (int i = x; i; i -= lowbit(i))
        res += tr[i] * (x + 1) - tri[i];
    return res;
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++) cin >> a[i];
    for (int i = 1; i <= n; i ++) add(i, a[i] - a[i - 1]);

    while(m --)
    {
        char op[2];
        int l, r, c;
        scanf("%s%d%d", op, &l, &r);
        if(*op == 'Q')
        {
            cout << sum(r) - sum(l - 1) << endl;
        }
        else
        {
            scanf("%d", &c);
            add(l, c);
            add(r + 1, -c);
        }
    }
    return 0;
}

题解 AcWing 241. 楼兰图腾

schinapi
1个月前

题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

//对纵坐标y用线段树

#include<iostream>
#include<cstring>
using namespace std;

typedef long long LL;
const int N = 200010;
int a[N], tr[N], lower[N], bigger[N];
int n;

int lowbit(int x)
{
    return x & -x;
}

void add(int x, int c)//修改某个值
{
    for (int i = x; i <= n; i += lowbit(i)) tr[i] += c;
}

int sum(int x)//查询某一段的和
{
    int res = 0;
    for (int i = x; i; i -= lowbit(i)) res += tr[i];
    return res;
}

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

    for (int i = 1; i <= n; i ++)
    {
        int y = a[i];
        bigger[i] = sum(n) - sum(y);
        lower[i] = sum(y - 1);
        add(y, 1);
    }

    memset(tr, 0, sizeof tr);
    LL res1 = 0, res2 = 0;//赋初值；

    for (int i = n; i; i --)
    {
        int y = a[i];
        res1 += bigger[i] * (LL)(sum(n) - sum(y));
        res2 += lower[i] * (LL)sum(y - 1);
        add(y, 1);
    }
    cout << res1 << " " << res2 << endl;
    return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

题解 AcWing 237. 程序自动分析

schinapi
1个月前

题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include<iostream>
#include<unordered_map>
#include<vector>
using namespace std;

const int N = 2000010;

struct query{
    int a, b, type;
} query[N];
int p[N];
unordered_map<int, int> h;
int cnt, n;

int find(int x)
{
    if (x != p[x])  p[x] = find(p[x]);
    return p[x];
}
int main()
{
    int T;
    cin >> T;
    while(T --)
    {
        scanf("%d", &n);
        cnt = 0;
        h.clear();
        for (int i = 0; i < n; i ++)
        {
            int a, b, e;
            scanf("%d%d%d", &a, &b, &e);

            if (!h.count(a)) h[a] = ++ cnt;
            if (!h.count(b)) h[b] = ++ cnt;

            query[i] = {h[a], h[b], e};
        }

        for (int i = 1; i <= cnt; i ++) p[i] = i;

        for (int i = 0; i < n; i ++)
            if (query[i].type == 1)
                p[find(query[i].a)] = find(query[i].b);

        bool flag = true;
        for (int i = 0; i < n; i ++)
        {
            if (query[i].type == 0 && find(query[i].a) == find(query[i].b))
            {
                flag = false;
                break;
            }
        }

        if (flag) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
    return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

题解 AcWing 1252. 搭配购买

schinapi
1个月前

题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include<iostream>
using namespace std;

const int N = 10010;

int p[N];
int cost[N], w[N];
int f[N];
int n, m, k;

int find(int a)
{
    if (p[a] != a) p[a] = find(p[a]);
    return p[a];
}
int main()
{
    cin >> n >> m >> k;

    for (int i = 1; i <= n; i ++) p[i] = i;

    for (int i = 1; i <= n; i ++)
    {
        int a, b;
        cin >> a >> b;
        cost[i] = a, w[i] = b;
    }
    for (int i = 1; i <= m; i ++)
    {
        int a, b;
        cin >> a >> b;
        a = find(a), b = find(b);
        if (a != b)
        {
            p[a] = b;
            w[b] += w[a];
            cost[b] += cost[a];
        }
    }
    int res = 0;

    for (int i = 1; i <= n; i ++)
        if (p[i] == i)
        {
            for (int j = k; j >= cost[i]; j --)
                f[j] = max(f[j - cost[i]] + w[i], f[j]);
        }
    cout << f[k] << endl;

    return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

题解 AcWing 1250. 格子游戏

schinapi
1个月前

题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include<iostream>
#include<cstring>
using namespace std;

const int N = 205;
int p[N * N] ;
int n, m;

int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n * n; i ++) p[i] = i;
    for (int i = 1; i <= m; i ++)
    {
        int x, y;
        char c;
        cin >> x >> y >> c;
        int a = (x - 1) * n + y;
        int b;
        if (c == 'D') b = x * n + y;
        else b = (x - 1) * n + y + 1;

        //cout << a << " " << b << endl;

        a = find(a), b = find(b);
        if (a == b)
        {
            cout << i;
            return 0;
        }
        p[a] = b;
    }
    cout << "draw";
    return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

题解 AcWing 1290. 越狱

schinapi
1个月前

题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

//m^n - m * (m - 1)^(n - 1);

#include<iostream>
using namespace std;

const int mod = 100003;

int qmi(int a, long long b)
{
    int res = 1;
    while(b)
    {
        if (b & 1) res = res * 1ll * a % mod;
        a = a * 1ll * a % mod;
        b >>= 1;
    }
    return res;
}

int main()
{
    int m;
    long long n;
    cin >> m >> n;

    cout << (qmi(m, n) - m * 1ll * qmi(m - 1, n - 1) % mod + mod) % mod;
    return 0;
}

题解 AcWing 1289. 序列的第k个数

schinapi
1个月前

题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include<iostream>
using namespace std;

const int mod = 200907;

int  qmi(int a, int b)
{
    int  res = 1;
    while(b)
    {
        if (b & 1) res = res * 1ll *  a % mod;
        a = a * 1ll * a % mod;
        b >>= 1;
    }
    return res;
}


int main()
{
    int T;
    cin >> T;
    while(T --)
    {
        int a1, a2, a3, k;
        cin >> a1 >> a2 >> a3 >> k;
        if (a2 - a1 == a3 - a2)
            cout << (a1 + (a2 - a1) * 1ll * (k - 1)) % mod << endl;
        else  cout << qmi(a2 / a1, k - 1) % mod * a1 % mod << endl;
    }
    return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

题解 AcWing 197. 阶乘分解

schinapi
1个月前

题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include<iostream>
using namespace std;
const int N = 1000010;

int n;
int primes[N], cnt;
bool st[N];

void init(int n)
{
    for(int i = 2; i <= n; i ++)
    {
        if(!st[i]) primes[cnt ++] = i;
        for (int j = 0; primes[j] * i <= n; j ++)
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

int main()
{
    cin >> n;
    init(n);
    //枚举每一个质数；
    for (int i = 0; i < cnt; i ++)
    {
        int p = primes[i], c = 0;
        long long  base = p;
        //for (int j = n; j; j /= p) c += j / p;

        while(base <= n)
        {
            c += n / base;
            base *= p;
        }
        cout << p << " " << c << endl;
    }
    return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

题解 AcWing 196. 质数距离

schinapi
1个月前

题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;
typedef long long LL;

const int N = 1000010;

int primes[N], cnt;
bool st[N];

void init(int n)
{
    memset(st, 0, sizeof st);
    cnt = 0;
    for (int i = 2; i <= n; i ++)
    {
        if (!st[i]) primes[cnt ++] = i;
        for (int j = 0; primes[j] * i <= n; j ++)
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

int main()
{
    int l, r;
    while(cin >> l >> r)
    {
        init(50000);
        memset(st, 0, sizeof st);

        for (int i = 0; i < cnt; i ++)
        {
            LL p = primes[i];
            for (LL j = max(p * 2, (l + p - 1) / p * p); j <= r; j += p)
                st[j - l] = true;
        }

        cnt = 0;
        for (int i = 0; i <= r - l; i ++)
        {
            if (!st[i] && i + l >= 2) 
                primes[cnt ++] = i + l;
        }

        if (cnt < 2) puts("There are no adjacent primes.");
        else
        {
            int maxv = 0, minv = 0;
            for (int i = 0; i + 1 < cnt; i ++)
            {
                int d = primes[i + 1] - primes[i];
                if (d > primes[maxv + 1] - primes[maxv]) maxv = i;
                if (d < primes[minv + 1] - primes[minv]) minv = i;
            }
            printf("%d,%d are closest, %d,%d are most distant.\n", primes[minv], primes[minv + 1], primes[maxv], primes[maxv + 1]);
        }
    }
    return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

题目描述

样例

算法1

(暴力枚举) $O(n^2)$

时间复杂度

参考文献

C++ 代码

算法2

(暴力枚举) $O(n^2)$

时间复杂度

参考文献

C++ 代码

评论列表：

题目描述

样例

算法1

(暴力枚举) $O(n^2)$

时间复杂度

参考文献

C++ 代码

算法2

(暴力枚举) $O(n^2)$

时间复杂度

参考文献

C++ 代码

评论列表：

题目描述

样例

算法1

(暴力枚举) $O(n^2)$

时间复杂度

参考文献

C++ 代码

算法2

(暴力枚举) $O(n^2)$

时间复杂度

参考文献

C++ 代码

评论列表：

题目描述

样例

算法1

(暴力枚举) $O(n^2)$

时间复杂度

参考文献

C++ 代码

算法2

(暴力枚举) $O(n^2)$

时间复杂度

参考文献

C++ 代码

评论列表：

题目描述

样例

算法1

(暴力枚举) $O(n^2)$

时间复杂度

参考文献

C++ 代码

算法2

(暴力枚举) $O(n^2)$

时间复杂度

参考文献

C++ 代码

评论列表：

题目描述

样例

算法1

(暴力枚举) $O(n^2)$

时间复杂度

参考文献

C++ 代码

算法2

(暴力枚举) $O(n^2)$

时间复杂度

参考文献

C++ 代码

评论列表：

题目描述

样例