按照做题顺序

N-Fibonacci Sequence

ZRC

B-So Easy

LYF

I-Base62

ZRC 高精

A-Girls and Party

题意:

有一个游戏，给定一些卡牌，卡牌具有名称和颜色和分值power三个属性

对选定的五张卡牌的分值求和sum，每拥有一张特殊名称(共5个)的卡牌则bonus+=0.1，每拥有一张特殊颜色(共1个)卡牌则bonus+=0.2

ans=sum*(1+bonus)

n<=100000

LYF解：

比赛的时候听到说是分类讨论

ZRC补:

考虑每张卡牌最多bonus只有0.3，总bonus最多只有0.15。那么可以分组背包dp，f[i][j][k]表示从1到第i组，选j个，bonus为k的最大基础power

f[i][j][k]=max{f[i-1][j][k](不选),f[i-1][j-1][k-nowbonus]+nowpower}

复杂度n*6*16

写的时候一不小心在用for(auto to:x)时候出问题了，以前用迭代器的话修改是改在容器里面的，但是如果是for(auto to:x)就是新建一个变量拿出来的，改是改在局部变量。写完之后查了一查可以用for(auto &to:x)这样就是引用，可以修改到里面。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
const int maxn=111111;
int t,n,f[maxn][6][16];//i:1 to ith group j:how many chosen k:how many bonus points  value:max ans
struct DATA
{
    string name,color;
    int power,bonus;
}data[maxn];
unordered_map <string,vector<DATA>> m;
string bonusname[5],bonuscolor;
void init()
{
    memset(f,-1,sizeof(f));
    bonuscolor="";
    m.clear();
}
int main()
{
    read(t);
    while (t--)
    {
        init();
        read(n);
        rep(i,1,n) {cin>>data[i].name>>data[i].color>>data[i].power;data[i].bonus=0;}
        rep(i,0,4) cin>>bonusname[i];
        cin>>bonuscolor;
        rep(i,1,n) if (data[i].color==bonuscolor) data[i].bonus+=2;
        rep(i,1,n) m[data[i].name].push_back(data[i]);
        for (auto it1=m.begin();it1!=m.end();it1++)
        {
            rep(i,0,4)
                if (it1->first==bonusname[i])
                {
                    for (auto it2=it1->second.begin();it2!=it1->second.end();it2++) it2->bonus++;
                    break;
                }
        }
        int i=1;
        f[0][0][0]=0;
        for (auto it1:m)
        {
            rep(j,0,5) rep(k,0,15)
                f[i][j][k]=f[i-1][j][k];
            for (auto it2:it1.second)
            {
                rep(j,1,5) 
                    rep(k,it2.bonus,15)
                        if (f[i-1][j-1][k-it2.bonus]!=-1) f[i][j][k]=max(f[i][j][k],f[i-1][j-1][k-it2.bonus]+it2.power);
            }
            i++;
        }
        int ans=0;
        rep(k,0,15) ans=max(ans,f[i-1][5][k]*(10+k)/10);
        cout<<ans<<endl;
    }
    return 0;
}

G-Pot!!

题意：

设f(x)为x的最大质因数次数(例如f(8)=f(24)=3,f(9)=f(18)=2)

初始有一个初值均为1的有n≤105个数的数列。有两种操作，一种是区间乘一个小于等于10的值，一种是询问区间内f(a[i])的最大值，操作q≤105次

ZRC解：

注意到乘的是小于等于10的值

对于2 3 5 7各开一个线段树，做完了

没注意到这个特点的话这个数据范围没法做，或许换个数据范围可以树套树

F-Function!

题意：
n∑a=2(an∑b=a⌊logab⌋⋅⌈logba⌉)
n≤106

ZRC解,WD写：

注意到⌈logba⌉永远是1，所以推式子可以简化运算，显然可以把复杂度降到O(nlogn)

然后发现当a>106≥√n时，⌊logab⌋一定为1

故只需在106以下做暴力，以上利用公式计算。

复杂度O(√nlogn)

这个高中公式还是得记住啊…
n∑a=1a2=n(n+1)(2n+1)6
可能有更优的办法？可能对于⌊logab⌋为2、为3、为任意值时都可以推出公式，这样可能可以在O(logn)时间内求出答案？(暂时懒得想了)

补题

D-Easy Problem

WD

给定n,k,m,d, 求
∑ai≤m(a1a2…an)k[gcd(a1,a2,…,an)=d]
其中
n≤10100000,m≤105

  • 分析

    一个基础的莫比乌斯反演.

    令
     F(d)=….[d|gcd(a1,a2,…,an)]
    就是原来式子的 gcd 倍数

    可以得到
    F(d)=∑ai≤m,d|ai(a1a2…an)k =dnkmd∑ai=1(a1a2…an)k =dnk(md∑i=1ik)n
    因为
    F(d)=∑d|lf(l) f(d)=∑d|lμ(ld)F(l)
    即
    f(d)=∑d|lμ(ld)lnk(ml∑i=1ik)n =dnkmd∑i=1μ(i)ink(mdi∑j=1jk)n
    然后这里指数得用扩展欧拉定理取个模. 后面的k 次幂的和预处理一下就行.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    #include <bits/stdc++.h>
    using namespace std;
    const int mod = 59964251;
    const int maxn = 1e5 + 5;
    int phi(int x)
    {
        int ans = 1;
        for (int i = 2; 1ll * i * i <= x; i++)
        {
            if (x % i == 0)
            {
                ans *= (i - 1);
                x /= i;
            }
            while (x % i == 0)
            {
                ans *= i;
                x /= i;
            }
        }
        if (x > 1)
            ans *= (x - 1);
        return ans;
    }

    long long qpow(long long a, long long b)
    {
        long long ans = 1;
        while (b)
        {
            if (b & 1)
                ans = ans * a % mod;
            a = a * a % mod;
            b /= 2;
        }
        return ans;
    }
    bool notprime[maxn];
    int mu[maxn];
    int prime[maxn];
    long long wd[maxn];
    void init()
    {
        mu[1] = 1;
        for (int i = 2; i < maxn; i++)
        {
            if (!notprime[i])
            {
                prime[++prime[0]] = i;
                mu[i] = -1;
            }
            for (int j = 1; j <= prime[0] && 1ll * prime[j] * i < maxn; j++)
            {
                notprime[i * prime[j]] = true;
                if (i % prime[j] == 0)
                {
                    mu[i * prime[j]] = 0;
                    break;
                }
                else
                {
                    mu[i * prime[j]] = -mu[i];
                }
            }
        }
    }

    int main()
    {
        int t;
        cin >> t;
        init();
        while (t--)
        {
            string b;
            cin >> b;
            long long m, d, k;
            cin >> m >> d >> k;
            long long p = phi(mod);
            long long bb = 0;
            bool flag = 0;
            for (int i = 0; i < b.size(); i++)
            {
                bb = bb * 10 + (b[i] - '0');
                if (bb >= p)
                {
                    flag = true;
                    bb %= p;
                }
            }
            if (flag)
                bb += p;
            long long dd = qpow(d, k);
            dd = qpow(dd, bb) % mod;
            long long res = 0;
            long long m1 = m / d;
            for (int i = 1; i <= m / d; i++)
                wd[i] = (wd[i - 1] + qpow(i, k)) % mod;
            for (int i = 1; i <= m / d; i++)
            {
                long long k1 = qpow(i, bb);
                k1 = qpow(k1, k);
                long long x1 = wd[m1 / i];
                x1 = qpow(x1, bb);
                res += mu[i] * k1 % mod * x1 % mod;
                res %= mod;
            }
            res = ((res % mod) + mod) % mod;
            res = res * dd % mod;
            cout << res << endl;
        }
        return 0;
    }

H-Delivery Route

题意：

给定一张图，保证负边一定不在环内，给定的边中有单向边和双向边，问某点出发的整张图的最短路距离

解：

SPFA!==Bellman-Ford

强连通分量缩点求出拓扑序，按照拓扑序处理各强连通分量，处理时强连通分量内用dijkstra，方法就是把已经更新过距离的点丢进堆里直接做

做完了！真简单！不写了！

E-XOR tree

WD

image-20201206105803051

分析

相当于对每个子树求

m∑i=1i−1∑j=1(31∑l=0bil⋅2l⊕bjl⋅2l)2

m∑i=1i−1∑j=1(31∑l=0bil⋅2l⊕bjl⋅2l)(31∑k=0bik⋅2k⊕bjk⋅2k)

枚举两位, 找不一样的.

对于枚举到的两位, 一共有 00,01,10,11 四种. 统计这四种的数量就可以计算贡献了. 00 乘 11, 01乘 10
31∑l=031∑k=02l+km∑i=1i−1∑j=1[bli≠blj][bki≠bkj]

就是统计这两位不同的的对数. 有两种方法. 一种是用长链剖分维护四种情况的后缀和. 一种是暴力做….

暴力:

3.7s过

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
#define ull unsigned long long
int a[maxn];
int n, k;
vector<int> g[maxn];
vector<int> v[maxn];
ull val[maxn][4];
ull ans[maxn];
int f[maxn][30];
void dfs1(int x, int fa)
{
    f[x][0] = fa;
    for (int i = 1; i <= 25; i++)
        f[x][i] = f[f[x][i - 1]][i - 1];
    for (auto to : g[x])
        dfs1(to, x);
}

void dfs(int x, int l1, int l2)
{
    for (int i = 0; i < 4; i++)
        val[x][i] = 0;
    for (auto to : g[x])
    {
        dfs(to, l1, l2);
        for (int k = 0; k < 4; k++)
            val[x][k] += val[to][k];
    }
    int k = ((a[x] >> l1) & 1) * 2 + ((a[x] >> l2) & 1);
    val[x][k] += 1;
    ull y = 1;
    if (l1 != l2)
        y = 2;
    ans[x] += y * (val[x][0] * val[x][3] + val[x][1] * val[x][2]) * (1ull << (l1 + l2));
    for (auto to : v[x])
    {
        int k = ((a[to] >> l1) & 1) * 2 + ((a[to] >> l2) & 1);
        val[x][k] -= 1;
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 2; i <= n; i++)
    {
        int u;
        cin >> u;
        g[u].push_back(i);
    }
    dfs1(1, 0);
    for (int i = 1; i <= n; i++)
    {
        int l = k;
        int x = i;
        for (int i = 0; i <= 25; i++)
        {
            if ((l >> i) & 1)
                x = f[x][i];
        }
        v[x].push_back(i);
    }
    for (int i = 0; i <= 31; i++)
    {
        for (int j = 0; j <= i; j++)
            dfs(1, i, j);
    }
    for (int i = 1; i <= n; i++)
        cout << ans[i] << endl;
    return 0;
}

长链剖分

2.6s过, 可能因为少了删掉k+1层儿子的步骤.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
#define ull unsigned long long
int a[maxn];
int n, k;
vector<int> g[maxn];
ull ans[maxn];
int len[maxn], son[maxn], p[maxn];
int now;
ull num[maxn][4];
void dfs1(int x)
{
    for (auto to : g[x])
    {
        dfs1(to);
        if (len[to] + 1 > len[x])
        {
            len[x] = len[to] + 1;
            son[x] = to;
        }
    }
}

void dfs(int x, int l1, int l2)
{
    p[x] = ++now;
    for (int j = 0; j < 4; j++)
        num[p[x]][j] = 0;
    if (son[x])
    {
        dfs(son[x], l1, l2);
        for (int j = 0; j < 4; j++)
            num[p[x]][j] += num[p[son[x]]][j];
    }
    int y = ((a[x] >> l1) & 1) * 2 + ((a[x] >> l2) & 1);
    num[p[x]][y] += 1;
    for (auto to : g[x])
    {
        if (to == son[x])
            continue;
        dfs(to, l1, l2);
        for (int j = 0; j < 4; j++)
            num[p[x]][j] += num[p[to]][j];
        for (int i = 0; i <= len[to]; i++)
        {
            for (int j = 0; j < 4; j++)
                num[p[x] + i + 1][j] += num[p[to] + i][j];
        }
    }
    ull wd = 1 + (l1 != l2);
    if (len[x] > k)
    {
        ull y1 = 1ull * (num[p[x]][0] - num[p[x] + k + 1][0]) * (num[p[x]][3] - num[p[x] + k + 1][3]);
        ull y2 = 1ull * (num[p[x]][1] - num[p[x] + k + 1][1]) * (num[p[x]][2] - num[p[x] + k + 1][2]);
        ans[x] += wd * (y1 + y2) * (1ull << (l1 + l2));
    }
    else
        ans[x] += wd * (num[p[x]][0] * num[p[x]][3] + num[p[x]][1] * num[p[x]][2]) * (1ull << (l1 + l2));
}

int main()
{
    ios::sync_with_stdio(false);
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 2; i <= n; i++)
    {
        int u;
        cin >> u;
        g[u].push_back(i);
    }
    dfs1(1);
    for (int i = 0; i <= 31; i++)
    {
        for (int j = 0; j <= i; j++)
        {
            now = 0;
            dfs(1, i, j);
        }
    }
    for (int i = 1; i <= n; i++)
        cout << ans[i] << endl;
    return 0;
}