（僅個人看法，對錯未知，可以當做口胡QAQ）如有錯誤請大佬們指出，有更好做法歡迎留言！
A 幸運數(shù)
暴力判不多說了
B 有獎問答
看到很多搜的，提供一個dp做法
d
p
[
i
]
[
j
]
表示前
i
道題，答對
j
道的方案數(shù)
dp[i][j]表示前i道題，答對j道的方案數(shù)
dp[i][j]表示前i道題，答對j道的方案數(shù)
有轉(zhuǎn)移式子，注意連續(xù)答對十道就無法繼續(xù)了
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
)
,
不妨設(shè)
y
≥
z
x =(y+z)(y-z),不妨設(shè)y\ge z
x=(y+z)(y?z),不妨設(shè)y≥z
可以發(fā)現(xiàn)x為奇數(shù)時，總能找到合法的y和z，令y = z + 1即可
x為偶數(shù)時，需要x為4的倍數(shù)才存在合法的y和z。
證明：
x為4的倍數(shù)時，把兩個因子2分別分給y和z，這樣y+z為偶數(shù)，y-z為偶數(shù)，有合法解
若x不為4的倍數(shù)，也就是x只有一個2因子，那y和z總有一個是奇數(shù)，y+z和y-z不為偶數(shù)，方程無解。
證畢
也可以打表前幾項就能發(fā)現(xiàn)這個規(guī)律了，總的來說x為奇數(shù)或x為4的倍數(shù)，才存在合法yz。
D 更小的數(shù)
區(qū)間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表示
有轉(zhuǎn)移方程
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 顏色平衡樹
樹上啟發(fā)式合并
cnt[i]，表示顏色為i的點的數(shù)量
mutiset st 里維護cnt，對于以u為根的子樹，子樹里的點都扔進cnt和multiset后，當multiset里最小值==最大值時，說明當前子樹合法。
賽時沒想到更好的做法，只能打個dsu on tree暴力，時間復雜度
O
(
n
l
o
g
2
n
)
O(nlog^2n)
O(nlog2n)，1s有點危險，相信籃球杯機子（畢竟收了那么多錢，機子應(yīng)該不爛吧??）。
PS：看到有樹剖做法似乎是1個log
發(fā)現(xiàn)賽時沒寫id數(shù)組??????應(yīng)該0分g了,加了id數(shù)組后下面代碼是對的（過了民間數(shù)據(jù)
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，不難想到拆成兩半暴力
然后這里每個瓜有三個狀態(tài)：買，不買，取一半買，我用了三進制，
3
15
=
14348907
3^{15}=14348907
315=14348907，給了1s，感覺有點危險
具體來說
前一半，處理出每種狀態(tài)，維護一個unordered_map<double,int> mp，表示重量為S最少的劈瓜次數(shù)
后一半，同理處理出每種狀態(tài)，假設(shè)當前重量為K，目標重量為Tar，則ans = min(ans,mp[tar-k] + 當前劈瓜次數(shù)）
G 網(wǎng)絡(luò)穩(wěn)定性
賽時想到了克魯斯卡爾重構(gòu)樹/虛樹，沒板子不會打（打ACM打的.jpg），遂打了離線詢問+暴力，maybe能拿70分
群里看了討論，正解大概是，先求最大生成樹，然后再克魯斯卡重構(gòu)樹，對于每個詢問(u,v)求一下lca。
H 異或和之和
思維+前綴和
按位考慮，假設(shè)當前是第k位，做一下異或前綴和得到數(shù)組pre，我們枚舉第i個數(shù)作為區(qū)間右端點，對于第i個數(shù),有貢獻
2
k
?
c
n
t
[
p
r
e
[
i
]
⊕
1
]
,
其中
c
n
t
[
0
/
1
]
表示前綴和為
0
/
1
的數(shù)量
2^k*cnt[pre[i] \oplus1],其中cnt[0/1]表示前綴和為0/1的數(shù)量
2k?cnt[pre[i]⊕1],其中cnt[0/1]表示前綴和為0/1的數(shù)量
I 像素放置
狀壓（口胡的）
對于每個位置(x,y)只要考慮周圍8個位子的放置狀態(tài)，用狀壓維護，這個過程感覺特別繁瑣，應(yīng)該有一車細節(jié)要考慮。遂本退役蒟蒻打了個暴力就扔了（文章來源：http://www.zghlxwxcb.cn/news/detail-412417.html
J 翻轉(zhuǎn)硬幣
數(shù)論
打了個表，發(fā)現(xiàn)不合法的數(shù)都有平方因子，遂問題轉(zhuǎn)化成求1~n中無平方因子數(shù)量，然后不會做了
群里問了佬，根號做法的式子是
∑
k
=
1
n
μ
(
k
)
?
n
k
2
\sum_{k=1}^{\sqrt{n}} \mu(k)*\frac{n}{k^2}
∑k=1n??μ(k)?k2n?，然后聽群佬說下面是用杜教篩繼續(xù)做，不會構(gòu)造卷積式，卡住了不會做QAQ文章來源地址http://www.zghlxwxcb.cn/news/detail-412417.html
到了這里，關(guān)于第十四屆藍橋杯省賽C++ A組淺析的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
