按照做题顺序
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 | const int maxn=111111; |
G-Pot!!
题意：
设f(x)为x的最大质因数次数(例如f(8)=f(24)=3,f(9)=f(18)=2)
初始有一个初值均为1的有$n\le 10^5$个数的数列。有两种操作，一种是区间乘一个小于等于10的值，一种是询问区间内f(a[i])的最大值，操作$q\le 10^5$次
ZRC解：
注意到乘的是小于等于10的值
对于2 3 5 7各开一个线段树，做完了
没注意到这个特点的话这个数据范围没法做，或许换个数据范围可以树套树
F-Function!
题意：
$$
\sum_{a=2}^{n}(a\sum_{b=a}^{n}\lfloor{\log_{a}{b}}\rfloor\cdot\lceil{\log_b{a}}\rceil)
$$
$n\le 10^6$
ZRC解,WD写：
注意到$\lceil{\log_b{a}}\rceil$永远是1，所以推式子可以简化运算，显然可以把复杂度降到$O(n\log n)$
然后发现当$a>10^6\ge\sqrt{n}$时，$\lfloor{\log_{a}{b}}\rfloor$一定为1
故只需在$10^6$以下做暴力，以上利用公式计算。
复杂度$O(\sqrt{n}\log{n})$
这个高中公式还是得记住啊…
$$
\sum_{a=1}^n{a^2}=\frac{n(n+1)(2n+1)}{6}
$$
可能有更优的办法？可能对于$\lfloor{\log_{a}{b}}\rfloor$为2、为3、为任意值时都可以推出公式，这样可能可以在$O(\log n)$时间内求出答案？(暂时懒得想了)
补题
D-Easy Problem
WD
给定$n,k,m,d$, 求
$$
\sum_{a_{i} \le m}(a_{1}a_{2}\dots a_{n})^{k}[gcd(a_{1}, a_{2}, \dots, a_{n}) = d]
$$
其中
$$
n \le 10^{100000}, m \le 10^{5}
$$
分析
一个基础的莫比乌斯反演.
令
$$
\ F(d) = ….[d|gcd(a_{1}, a_{2}, \dots, a_{n})]
$$
就是原来式子的 gcd 倍数可以得到
$$
F(d) = \sum_{a_{i} \le m, d | a_{i}}(a_{1}a_{2}\dots a_{n})^{k}
\ = d^{nk}\sum_{a_{i} = 1}^{\frac{m}{d}} (a_{1}a_{2}\dots a_{n})^{k}
\ = d^{nk}(\sum_{i = 1}^{\frac{m}{d}}i^{k})^{n}
$$
因为
$$
F(d) = \sum_{d|l}f(l)
\ f(d) = \sum_{d|l}\mu(\frac{l}{d})F(l)
$$
即
$$
f(d) = \sum_{d|l}\mu(\frac{l}{d}) l^{nk}(\sum_{i = 1}^{\frac{m}{l}}i^{k})^{n}
\ = d^{nk}\sum_{i = 1}^{\frac{m}{d}} \mu(i)i^{nk}(\sum_{j = 1}^{\frac{m}{di}}j^{k})^{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
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
分析
相当于对每个子树求
$$
\sum_{i=1}^m\sum_{j=1}^{i-1}(\sum_{l=0}^{31}b^i_l\cdot2^l\oplus b^j_l\cdot 2^l)^2
$$
$$
\sum_{i=1}^m\sum_{j=1}^{i-1}(\sum_{l=0}^{31}b_l^i\cdot2^l\oplus b^j_l\cdot2^l)(\sum_{k=0}^{31}b^i_k\cdot2^k\oplus b^j_k\cdot2^k)
$$
枚举两位, 找不一样的.
对于枚举到的两位, 一共有 00,01,10,11 四种. 统计这四种的数量就可以计算贡献了. 00 乘 11, 01乘 10
$$
\sum_{l = 0}^{31}\sum_{k = 0}^{31}2^{l + k}\sum_{i = 1}^{m}\sum_{j = 1}^{i - 1}[b_{i}^{l}\neq b_{j}^{l}][b_{i}^{k} \neq b_{j}^{k}]
$$
就是统计这两位不同的的对数. 有两种方法. 一种是用长链剖分维护四种情况的后缀和. 一种是暴力做….
暴力:
3.7s过
1 |
|
长链剖分
2.6s过, 可能因为少了删掉k+1层儿子的步骤.
1 |
|