前言

無敵！！第一次打Div3，因為之前打Div4賽時也就三四題，所以在打之前根本沒想到自己能做到賽時三題！！雖然第三題是離結束十幾秒的時候交的，沒想到判完題比賽結束了還不算賽時通過……TvT

A. Square Year

#include <bits/stdc++.h>
using namespace std;typedef long long ll;
typedef pair<int,int> pii;void solve()
{string s;cin>>s;int num=0;for(int i=0;i<4;i++){num=num*10+s[i]-'0';}int sq=sqrt(num);if(sq*sq==num){cout<<0<<" "<<sq<<endl;}else{cout<<-1<<endl;}
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t=1;cin>>t;while(t--){solve();    }return 0;
}

這個題說實話有點惡心，感覺一開始題意不是很明確，沒寫隨便輸出一個即可，所以還對著用例想了半天。

隨便輸出一個那就簡單了，那就是如果能開方就直接輸出0和開平方后的數，不能就直接-1即可。

B. Not Quite a Palindromic String

#include <bits/stdc++.h>
using namespace std;typedef long long ll;
typedef pair<int,int> pii;//賽時暴力解
void solve1()
{int n,k;cin>>n>>k;string s;cin>>s;int m=s.length();if(k>m/2){cout<<"NO"<<endl;return ;}int cnt=0,cntA=0,cntO=0,cntX1=0,cntX2=0;for(int i=0,j=m-1;i<=j;i++,j--){if(s[i]!=s[j]){if(s[i]=='1'){cntX1++;}else{cntX2++;}}else if(s[i]==s[j]){if(s[i]=='1'){cnt++;cntA++;            }else{cnt++;cntO++;}}}if(cnt==k){cout<<"YES"<<endl;return ;}if((k%2==0&&cnt%2==0)||(k%2==1&&cnt%2==1)){if(k<cnt){if(min(cntA,cntO)>=(cnt-k)/2){cout<<"YES"<<endl;return ;}else{cout<<"NO"<<endl;return ;}}else{if(max(cntX1,cntX2)>=(k-cnt)/2){cout<<"YES"<<endl;return ;}else{cout<<"NO"<<endl;return ;}}}else{cout<<"NO"<<endl;return ;}}//優化解
void solve2()
{int n,k;cin>>n>>k;string s;cin>>s;int m=s.length();//因為要求k對“00”或“11”，所以剩下的n/2-k對都是“01”//所以保證0和1的數量減去n/2-k是偶數即可//統計出現次數vector<int>cnts(2);for(int i=0;i<m;i++){cnts[s[i]-'0']++;}int zeros=cnts[0]-(n/2-k);int ones=cnts[1]-(n/2-k);if(zeros>=0&&zeros%2==0&&ones>=0&&ones%2==0){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t=1;cin>>t;while(t--){solve2();    }return 0;
}

這個題真的太草了，賽時完全想復雜了，雖然調了半天調出來了，但浪費了不少時間……

賽時想到的麻煩思路是，從要求的k和實際的cnt入手，分析兩者奇偶性對結果的影響。因為交換后必然是兩對兩對地增加，兩對兩對地減少，所以只有當k和cnt奇偶性一致時才有可能湊出來。（很妙，但沒用）

之后就去討論k和cnt的大小關系。當k小于cnt時，需要通過交換減少個數，那就只能讓“00”和“11”交換，一次消去兩對，所以就要分別統計“00”和“11”的個數。只有當這倆個數的最小值比k和cnt差值的兩倍大時才有可能湊出來。

當k大于cnt時，就需要通過交換增加個數，此時就需要讓“01”和“10”的組合交換。注意，在上一個情況里，必須是在同一側的兩數交換，才能減少個數，所以是兩者最小值。而這里，除了上述情況，還可以讓兩對“01”中其中一組的“0”和另一組的“1”交換，仍然可以消去一對。所以在這里就是取兩者的最大值，要注意的是，這里需要在一開始進行剪枝，先把k大于m/2的情況剪了才行。

優化解就簡單很多了，因為匹配的情況就是“00”和“11”兩種，不匹配就是“01”和“10”兩種，所以當要求有k對匹配時，不匹配的數量就是n/2-k。所以考慮先統計一遍0和1的詞頻，之后減去不匹配的數量就是需要的數量。當兩者都大于0且是偶數時，就可以被交換出來。

怎么說呢，感覺這個優化解的思路太需要觀察了……我賽時還想著怎么個調換法，這個直接從一般規律入手了，差距好大……

C. Need More Arrays

#include <bits/stdc++.h>
using namespace std;typedef long long ll;
typedef pair<int,int> pii;void solve()
{int n;cin>>n;vector<int>a(n);for(int i=0;i<n;i++){cin>>a[i];}vector<int>b;b.push_back(a[0]);for(int i=1,j=0;i<n;i++){if(a[j]+1<a[i]){b.push_back(a[i]);j=i;}}cout<<b.size()<<endl;;
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t=1;cin>>t;while(t--){solve();    }return 0;
}

這個題純純貪心，本來以為沒戲了，沒想到最后二十分鐘真給我貪出來了，還是一發過。（驕傲）

根據原題意，其實就是要讓這個數組不連續。那么貪心的思路就是，從前往后遍歷這個數組，一旦發現有連續的部分就直接刪除靠后的元素，因為這樣只會導致后續可能對答案有增益，不會導致答案減少。（說實話，我都不知道我咋能想到這個貪心）

所以就是遍歷數組，設置指針j記錄上一個沒刪除的下標。然后如果連續就刪除，否則就加到新數組里，然后j來到當前位置，最后返回新數組的大小即可。

D. Come a Little Closer

#include <bits/stdc++.h>
using namespace std;typedef long long ll;
typedef pair<int,int> pii;void solve()
{int n;cin>>n;vector<vector<ll>>mon(n,vector<ll>(2));for(int i=0;i<n;i++){cin>>mon[i][0]>>mon[i][1];}//特判if(n==1){cout<<1<<endl;return ;}ll ans=1e18+100;multiset<ll>xs,ys;for(int i=0;i<n;i++){xs.insert(mon[i][0]);ys.insert(mon[i][1]);}//計算所有的面積ans=min(ans,(*xs.rbegin()-*xs.begin()+1)*(*ys.rbegin()-*ys.begin()+1));//枚舉每個移動的怪獸for(int i=0;i<n;i++){xs.erase(xs.find(mon[i][0]));ys.erase(ys.find(mon[i][1]));//統計可以縮小的答案ll tmp=(*xs.rbegin()-*xs.begin()+1)*(*ys.rbegin()-*ys.begin()+1);//剩余構成的長方形是滿的if(tmp==n-1){//加上長寬的最小值 -> 移動到周圍tmp+=min(*xs.rbegin()-*xs.begin()+1,*ys.rbegin()-*ys.begin()+1);}ans=min(ans,tmp);//放回去xs.insert(mon[i][0]);ys.insert(mon[i][1]);}cout<<ans<<endl;
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t=1;cin>>t;while(t--){solve();    }return 0;
}

這個題因為不知道multiset所以還卡了一會……

multiset就是允許存在重復元素的set，因為最多可以移動怪獸一次，所以肯定考慮枚舉每個怪獸，看看移動之后能否使答案減小。所以有了multiset就可以把所有點放到set里，然后每次根據set中的最小值和最大值把要刪除的整個格子抓出來。之后枚舉每個怪獸，每次先在set中刪除，接著統計答案，最后插回去即可。注意，若格子滿了，即面積等于怪獸的數量，那就讓當前怪獸去到長寬更小的那邊，需要增加的就是長寬的最小值。

E. Kirei Attacks the Estate

#include <bits/stdc++.h>
using namespace std;typedef long long ll;
typedef pair<int,int> pii;const int MAXN=200005;//鏈式前向星建樹
// int head[MAXN];
// int nxt[MAXN<<1];
// int to[MAXN<<1];
// int cnt=1;// void build(int n)
// {
//     fill(head,head+MAXN,0);
//     fill(nxt,nxt+(MAXN<<1),0);
//     fill(to,to+(MAXN<<1),0);
// }// void addEdge(int u,int v)
// {
//     nxt[cnt]=head[u];
//     to[cnt]=v;
//     head[u]=cnt++;
// }//dfs
void dfs(int u,int father,vector<vector<ll>>&ans,vector<ll>&weight,vector<vector<int>>&graph)
{ans[u][0]=max(weight[u],weight[u]-ans[father][1]);ans[u][1]=min(weight[u],weight[u]-ans[father][0]);// for(int ei=head[u],v;ei>0;ei=nxt[ei])// {//     v=to[ei];//     if(v!=father)//     {//         dfs(v,u,n,weight);//     }// }for(int cur:graph[u]){if(cur!=father){dfs(cur,u,ans,weight,graph);}}
}void solve()
{int n;cin>>n;vector<ll>weight(n+1);for(int i=1;i<=n;i++){cin>>weight[i];}//build(n);vector<vector<int>>graph(n+1);for(int i=1,u,v;i<=n-1;i++){cin>>u>>v;// addEdge(u,v);// addEdge(v,u);graph[u].push_back(v);graph[v].push_back(u);}//0:max  1:minvector<vector<ll>>ans(n+1,vector<ll>(2,0));dfs(1,0,ans,weight,graph);for(int i=1;i<=n;i++){cout<<ans[i][0]<<" ";}cout<<endl;
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t=1;cin>>t;while(t--){solve();    }return 0;
}

真的抽象，沒想到鏈式前向星性能會比鄰接表差好多，同樣思路鏈式前向星直接TLE了……不過很好的一點是思路自己在補題的時候想到了！！

這個題其實就是個樹型dp，觀察給出的式子就能發現，當前節點的威脅值其實就是兩種情況，自己單獨和自己節點減去父節點的威脅值。而又因為要求當前節點的威脅值最大，所以就要求減去的父節點的威脅值最小。那么就考慮用dfs往下扎，同時收集當前節點威脅值的最大值和最小值即可。

F. Small Operations

#include <bits/stdc++.h>
using namespace std;typedef long long ll;
typedef pair<int,int> pii;//最大公約數
int gcd(int a,int b)
{if(b>a){int tmp=b;b=a;a=tmp;}return b==0?a:gcd(b,a%b);
}//質因子
vector<int>factors(int n)
{vector<int>ans;for(int i=2;i*i<=n;i++){while(n%i==0){if(ans.empty()||ans.back()!=i){ans.push_back(i);}n/=i;}}if(n!=1){ans.push_back(n);}return ans;
}//約數
vector<int>divisors(int n)
{vector<int>ans;for(int i=n;i>=1;i--){if(n%i==0){ans.push_back(n/i);}}return ans;
}//把1乘到n的最小次數 -> 貪心是不對的，正解是按乘積bfs展開路徑
int check(int n,int k)
{if(n==1){return 0;}//往上乘的過程中，每一步的結果必然是n的約數vector<int>div=divisors(n);set<int>cur;//當前層結果cur.insert(1);for(int i=1;;i++){set<int>next;//下一層for(int x:cur){for(int y:div){if(y>k){break;}next.insert(x*y);}}if(next.find(n)!=next.end())//乘出n{return i;}cur=next;}return 0;
}void solve()
{int x,y,k;cin>>x>>y>>k;//先讓兩者同除一個最大公約數//之后先讓x變為1，然后再乘到yint t=gcd(x,y);x/=t;y/=t;//若兩者任意一個存在一個質因子大于k//那么不可能把x除到1或把1乘到y，所以必不可能完成for(int t:factors(y)){if(t>k){cout<<-1<<endl;return ;}}for(int t:factors(x)){if(t>k){cout<<-1<<endl;return ;}}int ans=check(x,k)+check(y,k);cout<<ans<<endl;
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t=1;cin>>t;while(t--){solve();    }return 0;
}

數學題拼盡全力無法戰勝了……

首先可以發現，上來可以求x和y的最大公約數，然后讓兩者同除這個最大公約數，然后考慮除完的結果，這樣不會對答案造成影響。之后的思路是先把x除到1，再從1乘到y。所以，對于無法完成的情況，那就是要分別取兩者的質因數，若存在一個質因子大于k，那么就必然不可能完成。判斷完之后，因為從一個數除到1和從1乘到這個數是對稱的，所以就是用一個check方法求x和y從1乘到該數的最小步數，加起來即可。

對于check方法，這里按k從大到小乘的貪心思路是不對的，正解是bfs展開路徑。觀察可以發現，在從1乘到該數的過程中，每一步的結果都必然是該數的因數，那么就可以先把該數的所有因數抓出來，接著用兩個set分別存當前步數里能乘出來的結果和下一步能乘出來的結果。然后每次遍歷當前層，若該數的因數沒有大于k，就讓該數的因數乘以當前層里的結果，然后存到下一層里。最后去找當前層里是否存在該數，有的話直接返回當前的步數，否則就讓cur來到下一層。

G. Build an Array

G題飯老師的講解沒聽懂……

總結

努力總會有回報！！加油！！再接再厲！！

END