「LibreOJ NOI Round #1」接竹竿
题目描述
一天，神犇和 LCR 在玩扑克牌。他们玩的是一种叫做“接竹竿”的游戏。
游戏规则是：一共有 nn 张牌，每张牌上有一个花色 cc 和一个点数 vv，花色不超过 kk 种。将这些牌依次放入一列牌的末端。若放入之前这列牌中已有与这张牌花色相同的牌，你可以选择将这张牌和任意一张花色相同的牌之间的所有牌全部取出队列（包括这两张牌本身），并得到与取出的所有牌点数和相同的分数。现在已知 LCR 把这 nn 张牌放入队列的顺序，求她最多能得多少分。
输入顺序即为 LCR 放入队列的顺序。即，c_ic**i 表示第 ii 张放入的牌的花色，v_iv**i 表示第 ii 张放入的牌的点数。
请注意，如果你知道类似的纸牌游戏，请尤其仔细地阅读规则，以免因为理解题意错误而出现不必要的问题。
输入格式
第一行两个整数 n,kn,k。
第二行，nn 个整数 c_1,c_2,…,c_nc1,c2,…,c**n 表示花色，满足 1\leq c_i\leq k1≤c**i≤k。
第三行，nn 个整数 v_1,v_2,…,v_nv1,v2,…,v**n 表示点数。
输出格式
输出一行一个整数，表示最多能得到的分数。
样例
样例输入 1
1 | 7 3 |
样例输出 1
1 | 13 |
样例解释 1
第 1 步，向队列加入 11。现在的队列：11
第 2 步，向队列加入 22。现在的队列：1,21,2
第 3 步，向队列加入 11。现在的队列：1,2,11,2,1
第 4 步，向队列加入 22，取出 2,1,22,1,2。现在的队列：11
第 5 步，向队列加入 33。现在的队列：1,31,3
第 6 步，向队列加入 22。现在的队列：1,3,21,3,2
第 7 步，向队列加入 33，取出 3,2,33,2,3。现在的队列：11
样例输入 2
1 | 18 5 |
样例输出 2
1 | 123 |
更多样例
见附加文件或备用网盘链接（提取码：a795）
数据范围与提示
对于 100\%100% 的数据，$1\leq n\leq 10^6,1\leq k\leq 10^6,1\leq v_i\leq 10^9$
| Subtask # | 分值 | n,kn,k 的限制 | 特殊限制 |
|---|---|---|---|
| 1 | 1515 | 1\leq n,k\leq 151≤n,k≤15 | c_i=v_ic**i=v**i |
| 2 | 1515 | 1\leq n,k\leq 3001≤n,k≤300 | c_i=v_ic**i=v**i |
| 3 | 3030 | 1\leq n,k\leq 30001≤n,k≤3000 | |
| 4 | 1515 | 1\leq n,k\leq 2\times 10^51≤n,k≤2×105 | |
| 5 | 1010 | 1\leq n,k\leq 10^61≤n,k≤106 | c_i=v_ic**i=v**i |
| 6 | 1515 | 1\leq n,k\leq 10^61≤n,k≤106 |
题解
挺不错的dp题。
先说我能想到的。一个线性dp
设$f(i)$表示加入第$i$张牌后点权最大值。
那么转移就是从前面所有和它同色的里找出最大$\sum{pos}^{now}b_i+f{pos-1}$
然后如果用vector存位置，对于$k$大的点能跑过去。。。所以就实现了$O(n^2)$过百万的奇迹！72pts到手
Code:
1 |
|
满分做法是前缀前缀优化+滚动数组。
暂时咕咕咕了。
回来补正解
我们的dp是
$fi = max(f{i-1} , max{j < i ~~ c_j = c_i}{s_i - s{j-1}+f_{j-1}})$
$fi = max(f{i-1} , si+max{j < i ~~ cj = c_i}{- s{j-1}+f_{j-1}})$
然后呢我们发现虽然我们已经把$f$和权值$v$做了前缀优化，但是max里的还可以前缀优化，所以我们对每个颜色都维护一个$-s{j-1}+f{j-1}$的前缀最值，然后$f$的转移就变成了每次$O(1)$
时间复杂度$O(n)$
Code:
1 |
|
3155: Preprefix sum
题面
题解
bzoj t4
本题可以有效地加深你对维护信息的理解，其实是入门题。
$\sum{i=1}^{k}\sum{j=1}^{i}Aj = \sum{i=1}^{k}(k-i+1)A_i$
$\sum{i=1}^{k}(k-i+1)A_i = k\sum{i=1}^{k}Ai - \sum{i=1}^{k}iAi + \sum{i=1}^{k}A_i$
两个树状数组分别维护即可。
Code：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
LL bit[2][maxn];
int n , m , a[maxn];
char s[maxn];
inline void upd(int num , int pos , LL v)
{
for( ; pos <= n ; pos += pos & -pos)
bit[num][pos] += v;
}
inline LL query(int num , int pos)
{
LL ans = 0;
for( ; pos ; pos -= pos & -pos)
ans += bit[num][pos];
return ans;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i = 1 ; i <= n ; ++i)
{
scanf("%d",&a[i]);
upd(0 , i , a[i]) , upd(1 , i , 1ll * a[i] * i);
}
for(int i = 1 ; i <= m ; ++i)
{
int x , y;
scanf("\n%s",s+1);
if(s[1] == 'M')
{
scanf("%d%d",&x,&y);
int det = y - a[x];
upd(0 , x , det) , upd(1 , x , 1ll * x * det);
a[x] = y;
}
if(s[1] == 'Q')
{
scanf("%d",&x);
printf("%lld\n",1ll*(x+1)*query(0,x) - query(1,x));
}
}
}
HDU5029—Relief grain
题意：
n个点构成的无根树，m次操作， 对于操作 x y z， 表示 x 到 y 路径上的 每个点 加一个 z 数字，可重复加。最后输出每个点 加的次数最多的那个数字，如果没有输出0.
题解
当时没有切掉。。
这道题还是很巧妙的。
用一颗权值线段树来维护剖分后的树。
我们把每个询问按重链拆分拆成$O(logn)$条路径。
这$O(logn)$个询问他们在线段树上的标号是连续的，设为$[x,y]$。所以我们把它们拆成两个：一个表示在$x$处时对这个修改的颜色$c$在权值线段树上加1 ， 另一个表示在$y+1$处对这个修改的颜色在线段树上-1。
最终我们只需要两个$O(n)$的vector数组来保存对于每个点的颜色端点（分别是开始和结束）。
然后按HPD的id顺序枚举每个点，完成它的所有修改并且查询线段树全局最大值获得它的答案。
显然由于id在重链上连续，所以枚举时能及时添加和删除影响。
总体来说，这是一道神仙题。
Code不需要，思维题要什么Code
一个小性质（称它为双整除根号分块）：对于$[n/k][m/k]$，取值个数不超过$O(\sqrt{n}+\sqrt{m})$
证明：由整除分块可知，左边有$O(\sqrt{n})$种取值，右边有$O(\sqrt{m})$种取值。
然后我们画一个数轴，由上可知值变化。
然后两根数轴一对齐，一共有$O(\sqrt{n}+\sqrt{m})$个小区间，小区间里$\frac{n}{k}$和$\frac{m}{k}$是相同的，自然乘积都相同。
原命题的证。
我很丢人的想了半天