文章目錄
傳送門
眾所周知ldxoildxoildxoi這種菜雞選手是不會(huì)寫HHH題的，因此該篇博客只有AAA題至GGG題的題解，實(shí)在抱歉。
A題
傳送門
題意簡述：給出b,kb,kb,k和a1,a2,...,aka_1,a_2,...,a_ka1?,a2?,...,ak?問bk?1a1+bk?2a2+...+akb^{k-1}a_1+b^{k-2}a_2+...+a_kbk?1a1?+bk?2a2?+...+ak?的奇偶性。
思路：分bbb的奇偶性討論下就好。
代碼：
#include<bits/stdc++.h>
#define ri register int
#define fi first
#define se second
using namespace std
;
typedef long long ll
;
typedef pair
<int,int> pii
;
const int mod
=998244353;
inline int add(const int&a
,const int&b
){return a
+b
>=mod
?a
+b
-mod
:a
+b
;}
inline int dec(const int&a
,const int&b
){return a
>=b
?a
-b
:a
-b
+mod
;}
inline int mul(const int&a
,const int&b
){return (ll
)a
*b
%mod
;}
inline int ksm(int a
,int p
){int ret
=1;for(;p
;p
>>=1,a
=mul(a
,a
))if(p
&1)ret
=mul(ret
,a
);return ret
;}
const int N
=1e5+5;
int b
,k
,a
[N
];
inline int read(){int ans
=0;char ch
=getchar();while(!isdigit(ch
))ch
=getchar();while(isdigit(ch
))ans
=(ans
<<3)+(ans
<<1)+(ch
^48),ch
=getchar();return ans
;
}
int main(){b
=read(),k
=read();int ans
=0;bool f
=b
&1;if(!f
){int x
;while(k
--)x
=read();cout
<<(x
&1?"odd":"even");}else{for(ri i
=k
-1;~i
;--i
)ans
+=read()&1;cout
<<(ans
&1?"odd":"even");}return 0;
}
B題
傳送門
題意簡述：給出一條長為mmm的木板，上面有nnn個(gè)洞，你可以用不超過kkk段木板去補(bǔ)洞問覆蓋的最小長度。
思路：
如果k≥nk\ge nk≥n直接輸出nnn。
否則先把所有的用一根木板補(bǔ)。
然后可以摳掉中間k?1k-1k?1段，于是我們把所有連續(xù)的兩個(gè)洞的距離放進(jìn)堆里取前k?1k-1k?1大減掉即可。
代碼：
#include<bits/stdc++.h>
#define ri register int
#define fi first
#define se second
using namespace std
;
typedef long long ll
;
typedef pair
<int,int> pii
;
const int mod
=998244353;
inline int add(const int&a
,const int&b
){return a
+b
>=mod
?a
+b
-mod
:a
+b
;}
inline int dec(const int&a
,const int&b
){return a
>=b
?a
-b
:a
-b
+mod
;}
inline int mul(const int&a
,const int&b
){return (ll
)a
*b
%mod
;}
inline int ksm(int a
,int p
){int ret
=1;for(;p
;p
>>=1,a
=mul(a
,a
))if(p
&1)ret
=mul(ret
,a
);return ret
;}
const int N
=1e5+5;
int n
,m
,k
,a
[N
];
inline int read(){int ans
=0;char ch
=getchar();while(!isdigit(ch
))ch
=getchar();while(isdigit(ch
))ans
=(ans
<<3)+(ans
<<1)+(ch
^48),ch
=getchar();return ans
;
}
int main(){n
=read(),m
=read(),k
=read();priority_queue
<int>q
;for(ri i
=1;i
<=n
;++i
)a
[i
]=read();sort(a
+1,a
+n
+1);for(ri i
=2;i
<=n
;++i
)q
.push(a
[i
]-a
[i
-1]-1);int delta
=a
[n
]-a
[1]+1;for(ri i
=1;i
<k
;++i
)delta
-=q
.top(),q
.pop();cout
<<delta
;return 0;
}
C題
傳送門
題意簡述：nnn次詢問（n≤2000n\le2000n≤2000），每次給一個(gè)a(2≤a≤225?1)a(2\le a\le2^{25}-1)a(2≤a≤225?1)，問對于所有滿足0<b<a0<b<a0<b<a的bbb，gcd(a&b,agcd(a\&b,agcd(a&b,a^b)b)b)的最大值是多少。
思路：
打表
打表代碼：#include<bits/stdc++.h>
using namespace std
;
int q
,a
,ans1
[55]={0,2,3,4,7,8,15,16,31,32,63,64,127,128,255,256,511,512,1023,1024,2047,2048,4095,4096,8191,8192,16383,16384,32767,32768,65535,65536,131071,131072,262143,262144,524287,524288,1048575,1048576,2097151,2097152,4194303,4194304,8388607,8388608,16777215,16777216,33554431,33554432,67108863};
int ans2
[55]={0,3,1,7,1,15,5,31,1,63,21,127,1,255,85,511,73,1023,341,2047,89,4095,1365,8191,1,16383,5461,32767,4681,65535,21845,131071,1,262143,87381,524287,1,1048575,349525,2097151,299593,4194303,1398101,8388607,178481,16777215,5592405,33554431,1082401,67108863,22369621};
inline int read(){int ans
=0;char ch
=getchar();while(!isdigit(ch
))ch
=getchar();while(isdigit(ch
))ans
=(ans
<<3)+(ans
<<1)+(ch
^48),ch
=getchar();return ans
;
}
int main(){q
=read();while(q
--) {a
=read();int loc
=upper_bound(ans1
+1,ans1
+51,a
)-ans1
;cout
<<ans2
[loc
-1]<<endl
;}return 0;
}
考慮到分aaa的情況討論 a?=2k?1a\not=2^k-1a??=2k?1那么取b=(2k?1)ab=(2^k-1)^ab=(2k?1)a即可，答案為2k?12^k-12k?1a=2k?1a=2^k-1a=2k?1，那么直接枚舉其最大質(zhì)因子，如果沒有就輸出111正解代碼：
#include<bits/stdc++.h>
#define ri register int
#define fi first
#define se second
using namespace std
;
typedef long long ll
;
typedef pair
<int,int> pii
;
const int mod
=998244353;
inline int add(const int&a
,const int&b
){return a
+b
>=mod
?a
+b
-mod
:a
+b
;}
inline int dec(const int&a
,const int&b
){return a
>=b
?a
-b
:a
-b
+mod
;}
inline int mul(const int&a
,const int&b
){return (ll
)a
*b
%mod
;}
inline int ksm(int a
,int p
){int ret
=1;for(;p
;p
>>=1,a
=mul(a
,a
))if(p
&1)ret
=mul(ret
,a
);return ret
;}
const int N
=1e5+5;
inline int read(){int ans
=0;char ch
=getchar();while(!isdigit(ch
))ch
=getchar();while(isdigit(ch
))ans
=(ans
<<3)+(ans
<<1)+(ch
^48),ch
=getchar();return ans
;
}
inline int lowbit(const int&x
){return x
&-x
;}
inline void solve1(const int&x
){int up
=1;while(up
<=x
)up
<<=1;cout
<<up
-1<<'\n';
}
inline void solve2(const int&x
){for(ri i
=2;i
*i
<=x
;++i
)if(x
%i
==0){cout
<<x
/i
<<'\n';return;}puts("1");
}
int main(){for(ri x
,tt
=read();tt
;--tt
){x
=read();if(lowbit(x
+1)!=x
+1)solve1(x
);else solve2(x
);}return 0;
}
D題
傳送門
題意簡述：給nnn張大小不超過mmm的紙牌(n,m≤1000000)(n,m\le1000000)(n,m≤1000000)。
現(xiàn)在允許把滿足任意一種條件的三張牌分為一組：
三張牌為連續(xù)自然數(shù)三張牌相同問分出來的最多的組數(shù)。
思路：
比賽的時(shí)候想了半天貪心發(fā)現(xiàn)是錯(cuò)的？手動(dòng)滑稽233
然后就涼了。
考慮dpdpdp。
對于連續(xù)的三個(gè)數(shù)x,x+1,x+2x,x+1,x+2x,x+1,x+2，如果我們分成三次(x,x+1,x+2)(x,x+1,x+2)(x,x+1,x+2)消耗的牌和分成(x,x,x),(x+1,x+1,x+1),(x+2,x+2,x+2)(x,x,x),(x+1,x+1,x+1),(x+2,x+2,x+2)(x,x,x),(x+1,x+1,x+1),(x+2,x+2,x+2)是等價(jià)的。
于是對于連續(xù)的三張牌最多只用分兩次(x,x+1,x+2)(x,x+1,x+2)(x,x+1,x+2)
于是我們定義狀態(tài)fi,t1,t2f_{i,t1,t2}fi,t1,t2?表示對于值為1?i1~i1?i的牌，我們分t1t1t1次(i?1,i,i+1)(i-1,i,i+1)(i?1,i,i+1)，分t2t2t2次(i,i+1,i+2)(i,i+1,i+2)(i,i+1,i+2)，然后枚舉fi+1,t2,t3f_{i+1,t2,t3}fi+1,t2,t3?轉(zhuǎn)移一下就行了，注意轉(zhuǎn)移的時(shí)候如果值為i+1i+1i+1的牌有剩的需要全部分成(i+1,i+1,i+1)(i+1,i+1,i+1)(i+1,i+1,i+1)
代碼：
#include<bits/stdc++.h>
#define ri register int
using namespace std
;
inline int read(){int ans
=0;char ch
=getchar();while(!isdigit(ch
))ch
=getchar();while(isdigit(ch
))ans
=(ans
<<3)+(ans
<<1)+(ch
^48),ch
=getchar();return ans
;
}
const int N
=1e6+5;
int f
[N
][3][3],a
[N
],n
,m
;
int main(){n
=read(),m
=read();for(ri i
=1;i
<=n
;++i
)++a
[read()];memset(f
,-1,sizeof(f
));f
[0][0][0]=0;for(ri i
=0;i
<m
+2;++i
){for(ri t1
=0;t1
<=2;++t1
){for(ri t2
=0;t2
<=2;++t2
){if(~f
[i
][t1
][t2
]){for(ri t3
=0;t3
<=2;++t3
){if(t1
+t2
+t3
>a
[i
+1])continue;f
[i
+1][t2
][t3
]=max(f
[i
+1][t2
][t3
],f
[i
][t1
][t2
]+t3
+(a
[i
+1]-t1
-t2
-t3
)/3);}}}}}cout
<<f
[m
+2][0][0];return 0;
}
E題
傳送門
題意簡述：給出兩個(gè)數(shù)列ana_nan?和bn(n≤100000)b_n(n\le100000)bn?(n≤100000)，可以對ai(2≤i≤n?1)a_i(2\le i\le n-1)ai?(2≤i≤n?1)進(jìn)行如下操作：ai=ai?1+ai+1?aia_i=a_{i-1}+a_{i+1}-a_{i}ai?=ai?1?+ai+1??ai?
問能否通過若干次操作使得a,ba,ba,b完全一樣。
思路：
定義ci=ai?ai?1(i≤2),c1=a1c_i=a_i-a_{i-1}(i\le2),c_1=a_1ci?=ai??ai?1?(i≤2),c1?=a1?
即ccc是aaa的差分?jǐn)?shù)組。
發(fā)現(xiàn)每次操作就是交換cic_ici?和ci+1c_{i+1}ci+1?
于是把兩個(gè)數(shù)列的差分?jǐn)?shù)列排序看是否一樣即可。
注意特判兩個(gè)數(shù)的情況，這個(gè)時(shí)候并不能移動(dòng)
代碼：
#include<bits/stdc++.h>
#define ri register int
#define fi first
#define se second
using namespace std
;
typedef long long ll
;
typedef pair
<int,int> pii
;
const int mod
=998244353;
inline int add(const int&a
,const int&b
){return a
+b
>=mod
?a
+b
-mod
:a
+b
;}
inline int dec(const int&a
,const int&b
){return a
>=b
?a
-b
:a
-b
+mod
;}
inline int mul(const int&a
,const int&b
){return (ll
)a
*b
%mod
;}
inline int ksm(int a
,int p
){int ret
=1;for(;p
;p
>>=1,a
=mul(a
,a
))if(p
&1)ret
=mul(ret
,a
);return ret
;}
const int N
=1e6+5;
inline int read(){int ans
=0;char ch
=getchar();while(!isdigit(ch
))ch
=getchar();while(isdigit(ch
))ans
=(ans
<<3)+(ans
<<1)+(ch
^48),ch
=getchar();return ans
;
}
int n
,m
,a
[N
],b
[N
],c
[N
],d
[N
];
int main(){n
=read();for(ri i
=1;i
<=n
;++i
)a
[i
]=read();for(ri i
=1;i
<=n
;++i
)c
[i
]=read();if(a
[1]!=c
[1]||a
[n
]!=c
[n
])puts("No"),exit(0);for(ri i
=1;i
<=n
;++i
)b
[i
]=a
[i
]-a
[i
-1],d
[i
]=c
[i
]-c
[i
-1];sort(b
+1,b
+n
+1),sort(d
+1,d
+n
+1);bool f
=1;for(ri i
=1;i
<=n
;++i
)if(b
[i
]^d
[i
])f
=0;if(f
)puts("Yes");else puts("No");return 0;
}
F題
傳送門
題意簡述：給一棵nnn個(gè)點(diǎn)的帶邊權(quán)樹,有qqq次詢問(n,q≤500000)(n,q\le500000)(n,q≤500000)，每次問你在所有dfsdfsdfs序在[l,r][l,r][l,r]之間的葉子結(jié)點(diǎn)跟xxx的最短距離。
思路：
考慮離線處理詢問，把所有詢問按照xxx歸類，于是只需動(dòng)態(tài)維護(hù)在dfsdfsdfs到某個(gè)節(jié)點(diǎn)的時(shí)候知道dfsdfsdfs序在一段區(qū)間的葉子到當(dāng)前點(diǎn)的距離最小值。
我們先按照題目中說的順序遍歷處理出dfsdfsdfs序（其實(shí)就是用vectorvectorvector存邊）以及每個(gè)點(diǎn)到根的distdistdist，然后把葉子結(jié)點(diǎn)的distdistdist放入線段樹里，這樣就處理出了所有點(diǎn)到根節(jié)點(diǎn)的答案，然后考慮一個(gè)點(diǎn)向兒子節(jié)點(diǎn)移動(dòng)的時(shí)候所有葉子結(jié)點(diǎn)到自己距離的變化，即兒子的子樹里的葉子整體減掉當(dāng)前邊邊權(quán)，其余的葉子加上當(dāng)前邊邊權(quán)即可。
代碼：
#include<bits/stdc++.h>
#define ri register int
#define fi first
#define se second
using namespace std
;
inline int read(){int ans
=0;char ch
=getchar();while(!isdigit(ch
))ch
=getchar();while(isdigit(ch
))ans
=(ans
<<3)+(ans
<<1)+(ch
^48),ch
=getchar();return ans
;
}
typedef pair
<int,int> pii
;
typedef long long ll
;
const int N
=5e5+5;
int n
,m
,fa
[N
],in
[N
],out
[N
],top
=0,tot
=0,q
[N
];
ll dis
[N
],ans
[N
];
vector
<pii
>e
[N
];
struct Node
{int l
,r
,id
;};
vector
<Node
>qry
[N
];
namespace SGT
{#define lc (p<<1)#define rc (p<<1|1)#define mid (l+r>>1)ll mn
[N
<<2],add
[N
<<2];inline void pushup(int p
){mn
[p
]=min(mn
[lc
],mn
[rc
]);}inline void pushnow(int p
,ll v
){mn
[p
]+=v
,add
[p
]+=v
;}inline void pushdown(int p
){if(add
[p
])pushnow(lc
,add
[p
]),pushnow(rc
,add
[p
]),add
[p
]=0;}inline void build(int p
,int l
,int r
){add
[p
]=0;if(l
==r
){mn
[p
]=dis
[q
[l
]];return;}build(lc
,l
,mid
),build(rc
,mid
+1,r
),pushup(p
);}inline ll
query(int p
,int l
,int r
,int ql
,int qr
){if(ql
<=l
&&r
<=qr
)return mn
[p
];pushdown(p
);if(qr
<=mid
)return query(lc
,l
,mid
,ql
,qr
);if(ql
>mid
)return query(rc
,mid
+1,r
,ql
,qr
);return min(query(lc
,l
,mid
,ql
,mid
),query(rc
,mid
+1,r
,mid
+1,qr
));}inline void update(int p
,int l
,int r
,int ql
,int qr
,ll v
){if(ql
>r
||qr
<l
)return;if(ql
<=l
&&r
<=qr
)return pushnow(p
,v
);pushdown(p
);if(qr
<=mid
)update(lc
,l
,mid
,ql
,qr
,v
);else if(ql
>mid
)update(rc
,mid
+1,r
,ql
,qr
,v
);else update(lc
,l
,mid
,ql
,mid
,v
),update(rc
,mid
+1,r
,mid
+1,qr
,v
);pushup(p
);}
}
inline int findl(const int&x
){return lower_bound(q
+1,q
+top
+1,x
)-q
;}
inline int findr(const int&x
){int ret
=lower_bound(q
+1,q
+top
+1,x
)-q
;return q
[ret
]>x
?ret
-1:ret
;}
void dfs1(int p
){in
[p
]=++tot
;for(ri i
=0,v
;i
<e
[p
].size();++i
)dis
[v
=e
[p
][i
].fi
]=dis
[p
]+e
[p
][i
].se
,dfs1(v
);out
[p
]=tot
;if(!e
[p
].size())q
[++top
]=p
;
}
void dfs2(int p
){for(ri i
=0,l
,r
;i
<qry
[p
].size();++i
)ans
[qry
[p
][i
].id
]=SGT
::query(1,1,top
,qry
[p
][i
].l
,qry
[p
][i
].r
);for(ri i
=0,l
,r
,v
,w
;i
<e
[p
].size();++i
){v
=e
[p
][i
].fi
,l
=findl(in
[v
]),r
=findr(out
[v
]),w
=e
[p
][i
].se
;SGT
::update(1,1,top
,l
,r
,-w
),SGT
::update(1,1,top
,1,l
-1,w
),SGT
::update(1,1,top
,r
+1,top
,w
);dfs2(v
);SGT
::update(1,1,top
,l
,r
,w
),SGT
::update(1,1,top
,1,l
-1,-w
),SGT
::update(1,1,top
,r
+1,top
,-w
);}
}
int main(){n
=read(),m
=read();for(ri i
=2;i
<=n
;++i
)fa
[i
]=read(),e
[fa
[i
]].push_back(pii(i
,read()));dfs1(1),SGT
::build(1,1,top
);for(ri i
=1;i
<=top
;++i
)q
[i
]=in
[q
[i
]];for(ri i
=1,x
,l
,r
;i
<=m
;++i
){x
=read(),l
=findl(read()),r
=findr(read());qry
[x
].push_back((Node
){l
,r
,i
});}dfs2(1);for(ri i
=1;i
<=m
;++i
)cout
<<ans
[i
]<<'\n';return 0;
}
G題
傳送門
題意簡述：給出一棵樹，上面有的點(diǎn)是白色的有的沒有涂色，現(xiàn)在兩個(gè)人輪流涂色，先手涂白色，后手涂黑色，當(dāng)某一方涂出了一條長度為333的路徑時(shí)宣告勝利，如果全部涂完都沒有滿足條件即是和局，問雙方都采取最優(yōu)策略的最終結(jié)果。
思路：顯然后手贏是不可能的 ，這輩子都不可能的
那么只需判斷先手能不能贏了。
這個(gè)初始局的白色很煩人，因此我們改改條件，對于一個(gè)初始為白色的點(diǎn)AAA，把它拓展成444個(gè)點(diǎn)：
然后其余的邊還是連向AAA點(diǎn)，這個(gè)時(shí)候我們假如涂AAA后手一定會(huì)涂BBB，就回到了跟初始是白色等價(jià)的情況。
于是我們成功把問題轉(zhuǎn)化成為了初始沒有涂色的情況。
現(xiàn)在考慮先手勝利的條件：
第一種：
第二種：
第三種：
這種注意，方法是放最靠中間的兩個(gè)：
這樣子先手必勝。
注意這種情況中間的直鏈的長度必須要是奇數(shù)才行（大家可以手玩感受一下）
代碼：
#include<bits/stdc++.h>
#define ri register int
using namespace std
;
inline int read(){int ans
=0;char ch
=getchar();while(!isdigit(ch
))ch
=getchar();while(isdigit(ch
))ans
=(ans
<<3)+(ans
<<1)+(ch
^48),ch
=getchar();return ans
;
}
const int N
=5e5+5;
int n
=0,du
[N
*4],cnt
[2];
vector
<int>e
[N
*4];
char s
[N
];
void dfs(int p
,int fa
,int dist
){if(e
[p
].size()>=3)++cnt
[dist
];for(ri i
=0,v
;i
<e
[p
].size();++i
)if((v
=e
[p
][i
])^fa
)dfs(v
,p
,dist
^1);
}
inline bool solve(const int&p
){if(du
[p
]>=4)return 1;if(du
[p
]<=2)return 0;int cnt
=0;for(ri i
=0;i
<e
[p
].size();++i
)if(du
[e
[p
][i
]]>1)++cnt
;return cnt
>=2;
}
inline void add(int u
,int v
){e
[u
].push_back(v
),++du
[u
];e
[v
].push_back(u
),++du
[v
];
}
int main(){for(ri tt
=read(),tot
;tt
;--tt
){for(ri i
=1;i
<=n
;++i
)e
[i
].clear(),du
[i
]=0;n
=read(),cnt
[0]=cnt
[1]=0;for(ri i
=1,u
,v
;i
<n
;++i
)u
=read(),v
=read(),add(u
,v
);scanf("%s",s
+1),tot
=n
;for(ri i
=1;i
<=n
;++i
)if(s
[i
]=='W'){++tot
;add(i
,tot
),add(tot
,tot
+1),add(tot
,tot
+2),tot
+=2;}n
=tot
,dfs(1,0,0);if(cnt
[0]>1||cnt
[1]>1){puts("White");continue;}bool flag
=0;for(ri i
=1;i
<=n
;++i
)flag
|=solve(i
);puts(flag
?"White":"Draw");}return 0;
}
轉(zhuǎn)載于:https://www.cnblogs.com/ldxcaicai/p/10367704.html
總結(jié)
以上是生活随笔為你收集整理的Codeforces 1110 简要题解的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。
