> 難得有一個round的題目我可以寫完ㄉ
## pA Escalator Conversations
分 case 去做討論
```cpp=
signed main(){
AC
int t;
cin>>t;
while(t--){
int n,m,k,h,x;
cin>>n>>m>>k>>h;
int ans = 0;
rep1(i,n){
cin>>x;
int d = abs(h-x);
if(d!=0&&d%k==0&&d/k<m){
ans++;
}
}
cout<<ans<<"\n";
}
}
```
## pB Parity Sort
將原始的序列由小到大排，然後 check 最後的位置上與原本位置的奇偶性是否相同
```cpp=
signed main(){
AC
int t;
cin>>t;
while(t--){
int n;
cin>>n;
vi v(n),vv(n);
rep(i,n){
cin>>v[i];
vv[i] = v[i];
}
sort(all(v));
bool ans = 1;
rep(i,n){
if(vv[i]%2!=v[i]%2){
ans = 0;
}
}
if(ans){
yes;
}
else{
no;
}
}
}
```
## pC Tiles Comeback
我們只需要去測試第一個顏色是否出現至少 k 次
k 次以後再去測試最後一個顏色往回走是否出現至少 k 次
要特判第一個顏色與最後一個顏色一樣的狀況 還好題目有給範測 不然我可能就會吃 WA 了QQ
```cpp=
signed main(){
AC
int t;
cin>>t;
while(t--){
int n,k;
cin>>n>>k;
vi v(n);
rep(i,n)cin>>v[i];
bool fs = 0;
int tt = 0;
int cnt = 0;
for(;tt<n;tt++){
if(v[tt]==v[0]){
cnt++;
if(cnt==k){
fs = 1;
break;
}
}
}
bool fc = 0;
cnt = 0;
for(;tt<n;tt++){
if(v[tt]==v[n-1]){
cnt++;
if(cnt==k){
fc = 1;
break;
}
}
}
if(v[0]==v[n-1]){
int ct = 0;
for(int i=0;i<n;i++){
if(v[i]==v[0])ct++;
}
if(ct>=k){
yes;
}
else{
if(fs&&fc){
yes;
}
else{
no;
}
}
continue;
}
if(fs&&fc){
yes;
}
else{
no;
}
}
}
```
## pD Prefix Permutation Sums
蠻有趣的一題，首先我在想的時候有分 case 討論
- case 1：
lose 掉的位置在第一個
- case 2：
lose 掉的位置在最後一個
- case 3：
lose 掉的位置在中間
然後再觀察到一件事情，一樣分case
- 如果前綴合陣列中的兩個數中間沒缺的話：
那麼兩數之差就會是 permutation 裡的其中一個數
- 如果有缺的話：
那麼兩數之差就會是miss掉的那個元素裡的兩個數的合!
這裡有更詳細的說明：
拿題目的 case 假設是 $[1,5,2,4,3]$，那麼前綴合就會是 $[1,6,8,12,15]$
發現一件事，$1-0 = 1,6-1 = 5...$
在完整的前綴合陣列內就可以知道剛剛前面所講的第一件事
少一項的狀況的話，我們拿$[1,6,12,15]$來解釋
把兩兩差算出來，分別是$[1,5,6,3]$ 然後對應到我們的permutation上，會發現我們已經拿到了 $1,3,5$ 所以剩下 $2,4$ 沒有拿到
又 $6$ 可以拆解成 $2,4$ 所以這個 case 有解!
但是實作上還是需要去注意到一些小細節：
如果把兩兩差算出來後有兩個數是一樣的，並且兩數都在permutation上。那跟剛剛的 6 一樣拿去測試能不能去拆成沒出現在 permutation 上的數字合。
如果不行的話，那一定就是 ```NO```
還有一個狀況就是出現超過兩次 那一定也是不行
另一個狀況就是出現一個大於 n 的數字(像是剛剛的 6)
那這種就是一定要拆開了
如果這時候又發現permutation 有數字出現兩次以上 那百分之百就是不行了
因為你這樣就需要拆兩個數字以上(一個數字是 大於 n 的那個，其他就是出現兩次以上 permutation 內的數)
又或是出現兩個以上大於 n 的數字也是不行，因為這樣你一定要拆兩個數字。
(下面那邊的```odd```是指大於 n 的數字)
寫成 code 就會長這樣：
```cpp=
int vis[200010];
signed main(){
AC
int t;
cin>>t;
while(t--){
int n,x,last,odd = 0;
cin>>n;
rep1(i,n)vis[i] = 0;
last = 0;
bool nk = 0;
for(int i=0;i<n-1;i++){
cin>>x;
int d = x-last;
last = x;
if(d>n){
if(odd){
nk = 1;
}
odd = d;
}
else vis[d]++;
}
int z = 0;
vi temp;
vi sec;
for(int i=1;i<=n;i++){
if(vis[i]==0){
temp.pb(i);
z++;
}
if(vis[i]==2){
sec.pb(i);
}
if(vis[i]>2)nk = 1;
}
if(nk||sec.size()>1||temp.size()>2){
no;
continue;
}
if(odd==0&&z==1){
yes;
continue;
}
else if(odd==0&&z==2&&sec.size()){
int tp = sec[0];
int ta = temp[0],tb = temp[1];
if(tp==ta+tb){
yes;
continue;
}
else{
no;
continue;
}
}
if(odd){
if(temp.size()<2){
no;
continue;
}
int ta = temp[0],tb = temp[1];
if(odd==ta+tb){
yes;
}
else{
no;
}
continue;
}
if(nk){
no;
}
else{
yes;
}
}
}
```
## pE Nastya and Potions
~~發現有 potion 那就是後悔貪心XD~~
這題就是 DAG 上的 DP
```cpp=
int dp[200010];
int cost[200010];
int deg[200010];
vi edge[200010],need[200010];
signed main(){
AC
int t;
cin>>t;
while(t--){
int n,k;
cin>>n>>k;
rep1(i,n)cin>>cost[i],dp[i] = cost[i],edge[i].clear(),need[i].clear();
int x;
rep1(i,k){
cin>>x;
cost[x] = 0;
dp[x] = 0;
}
rep1(i,n){
int m,k;
cin>>m;
deg[i] = m;
rep(j,m){
cin>>k;
need[i].pb(k);
edge[k].pb(i);
}
}
queue<int> q;
rep1(i,n){
if(deg[i]==0){
q.push(i);
}
}
while(q.size()){
int tp = q.front();q.pop();
int sum = 0;
for(int i:need[tp]){
sum+=dp[i];
}
if(need[tp].size()!=0)cmin(dp[tp],sum);
for(int i:edge[tp]){
deg[i]--;
if(deg[i]==0){
q.push(i);
}
}
}
rep1(i,n){
cout<<dp[i]<<" ";
}
cout<<"\n";
}
}
```
## pF Lisa and the Martians
觀察後就發現他的位元運算其實就是在找兩個數二進位下相同的位置合最多的，但我其實還是不能證明用 sort 會讓結果最好
orz
```cpp=
signed main(){
AC
int t;
cin>>t;
while(t--){
int n,k;
cin>>n>>k;
vii v(n);
rep(i,n){
cin>>v[i].F;
v[i].S = i+1;
}
sort(all(v));
int maxd = -INF,a,b,c;
for(int i=0;i<n-1;i++){
int res = 0 ,temp = 0;
rep(j,k){
if((v[i].F&(1<<j))==(v[i+1].F&(1<<j))){
if((v[i].F&(1<<j))==0){
temp|=(1<<j);
}
res|=(1<<j);
}
}
if(res>maxd){
maxd = res;
a = v[i].S,b = v[i+1].S;
c = temp;
}
}
cout<<a<<" "<<b<<" "<<c<<"\n";
}
}
```
## pG Vlad and the Mountains
可以用重力位能的想法去想(對 就是物理那個
然後這題我毒瘤了
反正我的做法就是建 MST 然後做 LCA 就可以了
反正還是過了 而且還一發入魂XD
```cpp=
int dsu[200010];
int ary[200010];
int lca[200010][20];
int pre[200010][20];
int dep[200010];
int vis[200010];
int fm[200010];
int md[200010];
int fp(int now){
if(dsu[now]==now)return now;
return dsu[now] = fp(dsu[now]);
}
vector<pair<int,pii>> v;
vii edge[200010];
void dfs(int now,int from){
dep[now] = dep[from]+1;
vis[now] = 1;
fm[now] = from;
for(pii i:edge[now]){
if(i.F==from||vis[i.F])continue;
md[i.F] = i.S;
dfs(i.F,now);
}
}
void solve(){
int n,m;
cin>>n>>m;
rep1(i,n)dsu[i] = i,vis[i] = 0,dep[i] = 0,edge[i].clear();
rep1(i,n)cin>>ary[i];
v.clear();
int a,b,c;
rep1(i,m){
cin>>a>>b;
c = max(ary[a],ary[b]);
v.pb({c,{a,b}});
}
sort(all(v));
rep(i,m){
int cost = v[i].F;
a = v[i].S.F,b = v[i].S.S;
int ppa = fp(a),ppb = fp(b);
if(ppa==ppb)continue;
dsu[ppa] = ppb;
edge[a].pb({b,cost});
edge[b].pb({a,cost});
}
rep1(i,n){
if(!vis[i]){
dep[i] = 0;
dfs(i,i);
}
lca[i][0] = fm[i];
pre[i][0] = max(ary[i],ary[fm[i]]);
}
for(int i=1;i<20;i++){
rep1(j,n){
lca[j][i] = lca[lca[j][i-1]][i-1];
pre[j][i] = max(pre[j][i-1],pre[lca[j][i-1]][i-1]);
}
}
int q;
cin>>q;
while(q--){
int a,b,c;
cin>>a>>b>>c;
if(fp(a)!=fp(b)){
no;
continue;
}
int maxeg = ary[a]+c;
if(dep[a]<dep[b])swap(a,b);
int d = dep[a]-dep[b];
int pans = 0;
for(int i=0;i<20;i++){
if((d&(1<<i))){
cmax(pans,pre[a][i]);
// cout<<pre[a][i];
a = lca[a][i];
}
}
if(a!=b){
// cout<<"!";
for(int i=19;i>=0;){
if(lca[a][i]!=lca[b][i]){
cmax(pans,pre[a][i]);
cmax(pans,pre[b][i]);
a = lca[a][i];
b = lca[b][i];
}
else{
i--;
}
}
cmax(pans,pre[a][0]);
cmax(pans,pre[b][0]);
}
if(maxeg<pans){
no;
}
else{
yes;
}
}
cout<<"\n";
}
```
其他人的做法是：
直接做 dsu 然後點由大到小新增上去 我燒雞
---
題外話
最後一題宣告了一堆東西忘記初始化 :TLEthinking:
Sign in with Wallet
Connect another wallet