（仅个人看法，对错未知，可以当做口胡QAQ）如有错误请大佬们指出，有更好做法欢迎留言！
A 幸运数
暴力判不多说了
B 有奖问答
看到很多搜的，提供一个dp做法
d
p
[
i
]
[
j
]
表示前
i
道题，答对
j
道的方案数
dp[i][j]表示前i道题，答对j道的方案数
dp[i][j]表示前i道题，答对j道的方案数
有转移式子，注意连续答对十道就无法继续了
d
p
[
i
]
[
j
]
−
>
d
p
[
i
+
1
]
[
j
+
1
]
,
0
≤
j
≤
9
,
当前答对了
dp[i][j]->dp[i+1][j+1],0\le j \le9,当前答对了
dp[i][j]−>dp[i+1][j+1],0≤j≤9,当前答对了
d
p
[
i
]
[
j
]
−
>
d
p
[
i
+
1
]
[
0
]
,
当前答错了
dp[i][j]->dp[i+1][0],当前答错了
dp[i][j]−>dp[i+1][0],当前答错了
C 平方差
标题也提示了平方差，那就展开一下
x
=
(
y
+
z
)
(
y
−
z
)
,
不妨设
y
≥
z
x =(y+z)(y-z),不妨设y\ge z
x=(y+z)(y−z),不妨设y≥z
可以发现x为奇数时，总能找到合法的y和z，令y = z + 1即可
x为偶数时，需要x为4的倍数才存在合法的y和z。
证明：
x为4的倍数时，把两个因子2分别分给y和z，这样y+z为偶数，y-z为偶数，有合法解
若x不为4的倍数，也就是x只有一个2因子，那y和z总有一个是奇数，y+z和y-z不为偶数，方程无解。
证毕
也可以打表前几项就能发现这个规律了，总的来说x为奇数或x为4的倍数，才存在合法yz。
D 更小的数
区间dp
f
[
l
]
[
r
]
,
表示
[
l
,
r
]
组成的子串是正着读大，还是正反读一样大，还是反着读大
,
分别用
1
,
0
,
−
1
表示
f[l][r],表示[l,r]组成的子串是正着读大，还是正反读一样大，还是反着读大,分别用1,0,-1表示
f[l][r],表示[l,r]组成的子串是正着读大，还是正反读一样大，还是反着读大,分别用1,0,−1表示
有转移方程
f
[
l
]
[
r
]
=
f
[
l
+
1
]
[
r
−
1
]
,
s
[
l
]
=
s
[
r
]
f[l][r]=f[l+1][r-1],s[l]=s[r]
f[l][r]=f[l+1][r−1],s[l]=s[r]
f
[
l
]
[
r
]
=
1
,
s
[
l
]
>
s
[
r
]
f[l][r]=1,s[l]>s[r]
f[l][r]=1,s[l]>s[r]
f
[
l
]
[
r
]
=
−
1
,
s
[
l
]
<
s
[
r
]
f[l][r]=-1,s[l]<s[r]
f[l][r]=−1,s[l]<s[r]
E 颜色平衡树
树上启发式合并
cnt[i]，表示颜色为i的点的数量
mutiset st 里维护cnt，对于以u为根的子树，子树里的点都扔进cnt和multiset后，当multiset里最小值==最大值时，说明当前子树合法。
赛时没想到更好的做法，只能打个dsu on tree暴力，时间复杂度
O
(
n
l
o
g
2
n
)
O(nlog^2n)
O(nlog2n)，1s有点危险，相信篮球杯机子（毕竟收了那么多钱，机子应该不烂吧😀）。
PS：看到有树剖做法似乎是1个log
发现赛时没写id数组😭😭😭应该0分g了,加了id数组后下面代码是对的（过了民间数据
const int N=2e5+10;
int n,m;
int Son;//目前的重儿子
std::vector<int> G[N];
int cnt[N],col[N],siz[N],son[N];
int sum,res;
int L[N],R[N],dfn,id[N];
multiset<int> st;
void dfs1(int x, int f){
L[x] = ++dfn;
id[dfn] = x;
siz[x] = 1;
for(int y:G[x]){
if( y== f ) continue;
dfs1(y,x);
siz[x] += siz[y];
//维护重儿子
if( !son[x] || siz[y] > siz[son[x]] ) son[x] = y;
}
R[x] = dfn;
}
void add(int x){
if( cnt[col[x]] ) st.erase(st.find(cnt[col[x]]));
cnt[col[x]]++;
st.insert(cnt[col[x]]);
}
void del(int x){
st.erase(st.find(cnt[col[x]]));
cnt[col[x]]--;
if( cnt[col[x]] ) st.insert(cnt[col[x]]);
}
void dfs2(int x, int f ,bool keep){
for(int y:G[x]){
if( y==f || y == son[x] ) continue;
dfs2(y,x,false);
}
if( son[x] ) dfs2(son[x],x,true);
for(int y:G[x]){
if( y==f || y == son[x] ) continue;
for(int i=L[y] ;i<=R[y] ;i++) add(id[i]);
}
add(x);
int mi = *st.begin();
int ma = *prev(st.end());
if( mi==ma ){
res++;
}
if( !keep )
for(int i=L[x] ;i<=R[x] ;i++) del(id[i]);
}
signed main(){
cin>>n;
_for(i,1,n){
cin>>col[i];
int x;cin>>x;
if( i ){
G[x].push_back(i);
G[i].push_back(x);
}
}
dfs1(1,0);
dfs2(1,0,0);
cout<<res;
}
F 买瓜
折半搜索
n为30，不难想到拆成两半暴力
然后这里每个瓜有三个状态：买，不买，取一半买，我用了三进制，
3
15
=
14348907
3^{15}=14348907
315=14348907，给了1s，感觉有点危险
具体来说
前一半，处理出每种状态，维护一个unordered_map<double,int> mp，表示重量为S最少的劈瓜次数
后一半，同理处理出每种状态，假设当前重量为K，目标重量为Tar，则ans = min(ans,mp[tar-k] + 当前劈瓜次数）
G 网络稳定性
赛时想到了克鲁斯卡尔重构树/虚树，没板子不会打（打ACM打的.jpg），遂打了离线询问+暴力，maybe能拿70分
群里看了讨论，正解大概是，先求最大生成树，然后再克鲁斯卡重构树，对于每个询问(u,v)求一下lca。
H 异或和之和
思维+前缀和
按位考虑，假设当前是第k位，做一下异或前缀和得到数组pre，我们枚举第i个数作为区间右端点，对于第i个数,有贡献
2
k
∗
c
n
t
[
p
r
e
[
i
]
⊕
1
]
,
其中
c
n
t
[
0
/
1
]
表示前缀和为
0
/
1
的数量
2^k*cnt[pre[i] \oplus1],其中cnt[0/1]表示前缀和为0/1的数量
2k∗cnt[pre[i]⊕1],其中cnt[0/1]表示前缀和为0/1的数量
I 像素放置
状压（口胡的）
对于每个位置(x,y)只要考虑周围8个位子的放置状态，用状压维护，这个过程感觉特别繁琐，应该有一车细节要考虑。遂本退役蒟蒻打了个暴力就扔了（文章来源：https://www.toymoban.com/news/detail-412417.html
J 翻转硬币
数论
打了个表，发现不合法的数都有平方因子，遂问题转化成求1~n中无平方因子数量，然后不会做了
群里问了佬，根号做法的式子是
∑
k
=
1
n
μ
(
k
)
∗
n
k
2
\sum_{k=1}^{\sqrt{n}} \mu(k)*\frac{n}{k^2}
∑k=1nμ(k)∗k2n，然后听群佬说下面是用杜教筛继续做，不会构造卷积式，卡住了不会做QAQ文章来源地址https://www.toymoban.com/news/detail-412417.html
到了这里，关于第十四届蓝桥杯省赛C++ A组浅析的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
