link
文章目录- E - Magic Square(签到,模拟)
- J. Taotao Picks Apples(二分,ST表)
- A. Character Encoding(容斥,组合数学)
- D. Parentheses Matrix(神仙构造)
- I - Make ZYB Happy(广义SAM模板)
- L.From ICPC to ACM(模拟贪心)
没什么好说的,模拟转转转就好了,自认为我写的还是比较简便的.
#includeJ. Taotao Picks Apples(二分,ST表)using namespace std; const int maxn = 3e5+10; int t,n; char a[101][101]; void rotate(int x,int y,int num) { for(int i=1;i<=num;i++) { char q = a[x][y], w = a[x][y+1], e = a[x+1][y+1], r = a[x+1][y]; a[x][y] = r, a[x][y+1] = q, a[x+1][y] = e, a[x+1][y+1] = w; } } int main() { cin >> t; while( t-- ) { cin >> n; for(int i=1;i<=3;i++) cin >> ( a[i]+1 ); while( n-- ) { string s; cin >> s; int type = ( s[1]=='C' )?1:3;//C就是顺时针转1次,否则顺时针转三次 if( s[0]=='1' ) rotate( 1,1,type ); else if( s[0]=='2' ) rotate( 1,2,type ); else if( s[0]=='3' ) rotate( 2,1,type ); else rotate( 2,2,type ); } for(int i=1;i<=3;i++) cout << ( a[i]+1 ) << endl; } }
题意
给定一个数组 h h h,其中 h i h_i hi表示第 i i i个苹果的高度.
首先第一个苹果必选,然后选择第 i i i个苹果当且仅当 h i h_i hi大于之前选的所有苹果
现在给出 m m m个独立的询问,每次给定 p , q p,q p,q,问若把 h p h_p hp改成 q q q,可以拿到几个苹果?
做法
预处理 p r e [ i ] pre[i] pre[i]表示在原始序列中 [ 1 , i ] [1,i] [1,i]拿到苹果的最大高度, a n s [ i ] ans[i] ans[i]表示拿到的数量
这个 O ( n ) O(n) O(n)扫一遍就好了
还需要处理 s u f [ i ] suf[i] suf[i]表示如果第 i i i个苹果被拿走,在 [ i , n ] [i,n] [i,n]区间能拿走几个苹果
转移为 s u f [ i ] = s u f [ l a s ] + 1 suf[i]=suf[las]+1 suf[i]=suf[las]+1
其中 l a s > = i & & h l a s > h i las>=i&&h_{las}>h_i las>=i&&hlas>hi且满足 l a s las las是索引最小的
这个简单,我们可以在 [ i + 1 , n ] [i+1,n] [i+1,n]二分一个 m i d mid mid,每次询问 [ i + 1 , m i d ] [i+1,mid] [i+1,mid]的最大值是否大于 h i h_i hi即可
这样就能得到最小索引的 l a s las las,使用 S T ST ST表处理区间最大值可以在 O ( n l o g ( n ) ) O(nlog(n)) O(nlog(n))处理 s u f suf suf数组
于是对于每个询问,分两种情况.
①.当 p r e [ p − 1 ] > = q pre[p-1]>=q pre[p−1]>=q时,那么第 p p p个苹果其实没有被选中,此时需要找到 [ p + 1 , n ] [p+1,n] [p+1,n]第一个大于 p r e [ p − 1 ] pre[p-1] pre[p−1]的 h l a s h_{las} hlas
答案为 a n s [ p − 1 ] + s u f [ l a s ] ans[p-1]+suf[las] ans[p−1]+suf[las]
②.当
p
r
e
[
p
−
1
]
<
q
pre[p-1] 答案为
a
n
s
[
p
−
1
]
+
s
u
f
[
l
a
s
]
+
1
ans[p-1]+suf[las]+1
ans[p−1]+suf[las]+1 时间复杂度为
O
(
n
l
o
g
(
n
)
)
O(nlog(n))
O(nlog(n)) 题意
n
,
m
,
k
<
=
1
0
5
n,m,k<=10^5
n,m,k<=105 正常写是不能够的,我们把
k
k
k看作
k
k
k个
1
1
1分成
m
m
m份,每份大小小于等于
n
−
1
n-1
n−1 这样使用隔板法方案数是
(
k
−
1
m
−
1
)
binom{k-1}{m-1}
(m−1k−1) 但是这样分出来每组至少有
1
1
1个
1
1
1,然后我们每份大小为
[
0
,
n
−
1
]
[0,n-1]
[0,n−1] 不妨默认给每份加上
1
1
1,那么相当于把
k
+
m
k+m
k+m分成
m
m
m份大小为
[
1
,
n
]
[1,n]
[1,n]的数字 方案数是
(
k
+
m
−
1
m
−
1
)
binom{k+m-1}{m-1}
(m−1k+m−1),当然这其中有不合法的方案(有些数字会大于
n
n
n) 我们使用容斥原理,也就是减去有一组大于
n
n
n的,加上两组大于
n
n
n的,减去三组大于
n
n
n的… 答案是
(
k
+
m
−
1
m
−
1
)
+
∑
i
=
1
(
−
1
)
i
∗
(
m
i
)
∗
(
k
+
m
−
1
−
n
∗
i
m
−
1
)
binom{k+m-1}{m-1}+sumlimits_{i=1}(-1)^i*binom{m}{i}*binom{k+m-1-n*i}{m-1}
(m−1k+m−1)+i=1∑(−1)i∗(im)∗(m−1k+m−1−n∗i) 题意 括号矩阵的每个元素都是
(
(
(或
)
)
) 括号矩阵的优秀度为符合合法括号序列的行数和列数 现在给定矩阵的长宽,构造一个最大优秀度的矩阵输出. 神仙题,想不到。
S
A
M
SAM
SAM的模板题 由于长度为
m
m
m的串包含长度为
[
1
,
m
−
1
]
[1,m-1]
[1,m−1]的子串的贡献和 所以预处理一个
r
e
s
[
i
]
res[i]
res[i]表示长度为
i
i
i的随机串的价值期望,做一遍前缀和即可 于是对
n
n
n个串建广义
S
A
M
SAM
SAM,然后对于每个字符串 遍历每个前缀节点,一直向上跳后缀链接,同时把这些节点的贡献乘上当前字符串的价值(设节点价值为
a
n
s
i
ans_i
ansi) 当然要记得打标记,不然会重复算 于是对节点
u
u
u来说,自身包含的长度为
[
l
f
a
u
+
1
,
l
u
]
[l_{fa_u}+1,l_u]
[lfau+1,lu]的子串的价值都是
a
n
s
u
ans_u
ansu 差分一下就好了 一共有ｋ个月 当月卖出的原材料和电脑不收存储费,没用完的原材料和电脑可以留到下个月,但需要收取当月费用 第
i
i
i个月能存放
e
i
e_i
ei台电脑价格为
E
i
E_i
Ei，存放原材料容量无限价格为
R
i
R_i
Ri 求满足这
k
k
k个月客户需求的最小成本 首先因为原材料可以无限存储,所以在第
i
i
i个月来说,最小的原材料代价其实是
min
k
=
1
i
{
c
k
+
∑
j
=
k
i
−
1
R
j
}
minlimits_{k=1}^i{c_k+sumlimits_{j=k}^{i-1}R_j}
k=1mini{ck+j=k∑i−1Rj} 既然原材料已经达到最小了,那就需要让之前存储的电脑的代价最小 不妨在之前的月份中,只要当月还能制造电脑就存入仓库 到了下个月若仓库大小不够,就弹出成本最大的那些电脑. 然后利用当月的最小代价原材料制作
p
i
p_i
pi台电脑加入仓库,如果超过容量就弹出最大的那些电脑 为此我们需要知晓当前代价最小的电脑和最大的电脑,使用一个
m
u
l
t
i
s
e
t
<
电
脑
代
价
,
电
脑
数
量
>
multiset<电脑代价,电脑数量>
multiset<电脑代价,电脑数量>的二元组即可 但是如何衡量成本?毕竟每个月的电脑存储成本都不同,都需要动态变化. 没关系,我们假设每台电脑都是从第一个月开始存储的,装入第
i
i
i个月生产的电脑在价格上减去
∑
j
=
1
i
−
1
E
j
sumlimits_{j=1}^{i-1}E_j
j=1∑i−1Ej,这样可以保证相对成本不变,真正算成本的时候再加上第一个月到当前月的所有存储费
#include
A. Character Encoding(容斥,组合数学)
在
[
0
,
n
−
1
]
[0,n-1]
[0,n−1]中选
m
m
m个数(重复选,考虑顺序),求和为
k
k
k的方案数
#include
#include
L.From ICPC to ACM(模拟贪心)
第
i
i
i个月原材料价格为
c
i
c_i
ci,制造一台电脑要花费一个原材料和
m
i
m_i
mi元,当月最多生产
p
i
p_i
pi台电脑客户需求
d
i
d_i
di台
#include
