無關前置

最近同學都在打?？途W的比賽并且博主也在寫一下?？途W的題，博主就去看了看，打了一場，題目質量還是非常不錯的。我才不會告訴你我沒開long long錯了好久QWQ

---

• 212A-灰魔法師

題意簡述

給出長度為$n$的序列$a$, 求有多少對數對 $(i,j)(1\le i<j\le n)$ 滿足 $a_i+a_j$ 為完全平方數。

數據范圍：$1\le n,a\le 10^5$

---

這個簽到題吧，范圍十分的小，值域才$10^5$，開個數組記錄一下每個數字出現次數，然后$\sqrt{n}$的每次枚舉平方就好啦，復雜度$O(n\sqrt{n})$

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const int M=3e5+10; int n,maxv;ll ans; int A[M],B[M]; int main(){scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&A[i]),maxv=max(A[i],maxv);for(int i=1;i<=n;i++){for(int j=1;j*j<=(maxv<<1);j++){if(j*j-A[i]<0) continue;ans+=B[j*j-A[i]];}++B[A[i]];}printf("%lld\n",ans);return 0; }

---

• 212B-紫魔法師

題意簡述

給出一棵仙人掌(每條邊最多被包含于一個環，無自環，無重邊，保證連通)，要求用最少的顏色對其頂點染色，滿足每條邊兩個端點的顏色不同，輸出最小顏色數即可

數據范圍

$n\le 100000,m\le 200000$（$n$為點數，$m$為邊數）

---

這個稍微推一下就知道了，本來這個問題在一般的無向圖上，是非常難解決的，但是我們看，這是一個仙人掌，只有簡單環。所以對于所有的環，如果有奇數點環，那么至少用三種顏色；如果所有環點數都為偶數，那么至少用兩種顏色。由于是簡單環，深搜一遍即可統計答案。

#include<cstdio> #include<cstring> #include<algorithm>using namespace std; const int M=2e5+10; int n,m; struct ss{int to,last;ss(){}ss(int a,int b):to(a),last(b){} }g[M<<1]; int head[M],cnt; void add(int a,int b){g[++cnt]=ss(b,head[a]);head[a]=cnt;g[++cnt]=ss(a,head[b]);head[b]=cnt; } bool vis[M]; int dfn[M],tim,ans; void dfs(int a,int b){if(ans==3) return;dfn[a]=++tim;vis[a]=1;for(int i=head[a];i;i=g[i].last){if(g[i].to==b) continue;if(!vis[g[i].to]){dfs(g[i].to,a);}else{int now=dfn[a]-dfn[g[i].to]+1;if((now&1)&&ans<3)ans=3;if(!(now&1)&&!ans)ans=2;}} } int a,b; int main(){scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){scanf("%d%d",&a,&b);add(a,b);}if(!n){puts("0");return 0;}if(n==1){puts("1");return 0;}for(int i=1;i<=n;i++){if(!dfn[i]){dfs(i,i);if(ans>=3) break;}}printf("%d\n",ans);return 0; }

---

• 215C-藍魔法師

題意簡述

給出一棵$n$個點的樹，求有多少種刪邊方案，使得刪后的圖每個連通塊大小小于等于$k$，兩種方案不同當且僅當存在一條邊在一個方案中被刪除，而在另一個方案中未被刪除，答案對$998244353$取模

數據范圍：$2\le n,k\le 2000$

---

這個就是個裸的樹上背包問題，我們定義狀態$f[i][j]$，表示以$i$為根的子樹，連通塊大小為$j$的方案數，其中我們特殊規定當$j=0$時，表示$i$點不與上方父親結點連通的方案數，所以就深搜一遍，樹形$\mathrm{D}\mathrm{P}$，復雜度看似最壞為$n^3$，實際上由于每次枚舉不是枚舉所有的點數，所以復雜度大概算下來為$n^2～n^{\frac{5}{3}}$左右，是不會達到$n^3$的，所以完全能夠（具體的一些證明可以去網上找一些樹上背包的題的題解，里面可能有）。

所以直接打就好了，不要害怕超時。

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; int n,k; const int N=4010; const int Mod=998244353; struct ss{int to,last;ss(){}ss(int a,int b):to(a),last(b){} }g[N<<1]; int head[N],cnt; void add(int a,int b){g[++cnt]=ss(b,head[a]);head[a]=cnt;g[++cnt]=ss(a,head[b]);head[b]=cnt; } int dp[N][N],sze[N],sum[N],ls[N]; void dfs(int a,int b){sze[a]=1;dp[a][1]=1;for(int i=head[a];i;i=g[i].last){if(g[i].to==b) continue;dfs(g[i].to,a);for(int x=min(sze[a]+sze[g[i].to],k);x>=0;x--)ls[x]=0;for(int x=min(sze[a],k);x>=1;x--){for(int y=min(sze[g[i].to],k-x);y>=0;y--){ls[x+y]=(ls[x+y]+1ll*dp[a][x]*dp[g[i].to][y]%Mod)%Mod;}}sze[a]+=sze[g[i].to];for(int x=min(sze[a],k);x>=0;x--)dp[a][x]=ls[x];}for(int i=min(sze[a],k);i>=1;i--)dp[a][0]=(dp[a][0]+dp[a][i])%Mod; } int ans,a,b; int main(){scanf("%d%d",&n,&k);for(int i=1;i<n;i++){scanf("%d%d",&a,&b);add(a,b);}dfs(1,0);printf("%d\n",dp[1][0]);return 0; }

---

• 215D-綠魔法師

題意簡述

給你一個空的可重集，$n$次操作，每次操作給出$x,k,p$，執行以下操作：

在$S$中加入$x$

輸出$\sum _{y\in S}gcd(x,y{)}^k(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{p})$

$1\le n,x,k,p\le 10^5$

---

顯然暴力就為$O(n^{2}logn)$
但是我們這里考慮，$gcd$為最大公約數，所以一定為給出數字的因子，而在$10^5$內的一個數字的因子數量不會很多（可以自己用線性篩篩一遍看看），所以我們考慮將每個插入的數拆成因子插入，然后我們從大到小枚舉它的因子，因為對于一個它的因子，如果當前枚舉的肯定是較大的，當這個因子有的時候，那么肯定會成為答案，記這個因子為$a$，出現個數為$c$，那么貢獻為$c\times (a^k)$，然后統計完這個我們需要把這個因子的因子的個數全部減去$c$，因為包含該因子的數字我們已經算了，不能重復算，而后面只會枚舉比它小的數，所以只用減去它的因子的數。

我們每次$\sqrt{n}$的統計因子，然后記最多因子個數為$w$，每次$w^2$的統計答案，然后加一點常數優化和剪枝，就可以過了，復雜度$O(n\sqrt{n}\times w^2)$，但是注意這里的$w^2$是遠遠達不到的。

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<vector> #define int long long using namespace std; const int N=1e5+10; int n,p; int cnt[N],del[N]; vector <int> vec[N]; int fpow(int a,int b){int ans=1;for(;b;b>>=1,a=(1ll*a*a)%p){if(b&1)ans=(1ll*ans*a)%p;}return ans%p; } void add(int x){int a=sqrt(x);if(!vec[x].size()){for(int i=1;i<=a;i++){if(!(x%i)){vec[x].push_back(i);++cnt[i];if((x/i)!=i){vec[x].push_back(x/i);++cnt[x/i];}}}}else{for(int i=0,sz=vec[x].size();i<sz;i++)++cnt[vec[x][i]];} } void calc(int x){int a=sqrt(x);for(int i=1;i<=a;i++){if(!(x%i)){vec[x].push_back(i);if((x/i)!=i){vec[x].push_back(x/i);}}} } bool is_sort[N]; int query(int x,int k){memset(del,0,sizeof(del));int ans=0;if(!is_sort[x])is_sort[x]=1,sort(vec[x].begin(),vec[x].end());for(int i=vec[x].size()-1;i>=0;i--){int a=vec[x][i];if(cnt[a]<=del[a]) continue;ans=(ans+(cnt[a]-del[a])*fpow(a,k)%p)%p;if(!vec[a].size())calc(a);int now=cnt[a]-del[a];if(i)for(int j=0,sz=vec[a].size();j<sz;j++){if(vec[a][j]>a) break;del[vec[a][j]]+=now;if(i&&vec[a][j]==vec[x][i-1]&&cnt[vec[x][i-1]]<=del[vec[x][i-1]])--i;}}return ans; } int x,k; signed main(){scanf("%lld",&n);for(int i=1;i<=n;i++){scanf("%lld%lld%lld",&x,&k,&p);add(x);cout<<query(x,k)<<'\n';}return 0; }

---

• 215E-黃魔法師

題意簡述

給出 $n,k$，求一個長度為 $n$ 的數組 $a$, 滿足有恰好 $k$ 對數對 $(i,j)(1\le i<j\le n)$滿足 $a_i+a_j$為完全平方數。如果不存在，輸出 $?1$ 。

數據范圍: $n\le 10^5,k\le 10^{10}$

---

這個題非常的良心啊，第一題的標程就是它的檢驗器啊。

我們首先分析，對于無解的情況，當你無論如何都湊不到$k$個時就無解，所以對于一個長度為$n$的序列，它最多能組合出$\frac{n\times (n?1)}{2}$個完全平方數，所以當$k>\frac{n\times (n?1)}{2}$我們就可以判斷它無解。

然后對于有解的情況，由于只讓輸出一種方案，所以我們特殊構造即可，首先我們找幾個數字$x$，$x$要滿足$2x$為完全平方數，然后因為數字可以重復，所以如果我們放了$i$個$x$，那么它就會有$\frac{i\times (i?1)}{2}$的貢獻。

所以我們分類討論，對于$k$可以寫成$\frac{i\times (i?1)}{2}$的形式的情況，我們直接輸出$i$個$x$，然后找一個$y$，滿足$2y$和$x+y$都不為完全平方數，剩下的$n?i$個數字由這個數字填充即可。

然后對于$k$不能寫成$\frac{i\times (i?1)}{2}$的形式的情況，我們可以多選幾種$x$，然后先湊成近似$k$，剩下的我們找一個$w$，滿足$w+\text{其中一個}x$為完全平方數，而$2w$不為完全平方數，那么它就可以貢獻出選的那個$x$的個數那么多的完全平方數，不難發現，這樣一定能湊到$k$，剩下的同理選一個和其它已經選的$x$，還有自己都不能組成完全平方數的數字填充即可。

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const int M=1e5+10; ll n,k,top,p; ll ans[M];int main(){scanf("%lld%lld",&n,&k);if(n*(n-1)/2<k){puts("-1");return 0;}for(;top*(top-1)/2<=k;++top);--top;ll res=k-top*(top-1)/2;if(!res){for(int i=1;i<=top;i++)ans[++p]=2;while(p<n)ans[++p]=3;}else{for(int i=1;i<=top-res;i++)ans[++p]=98;for(int i=1;i<=res;i++)ans[++p]=2;ans[++p]=7;while(p<n)ans[++p]=5;}for(int i=1;i<=n;i++)printf("%lld ",ans[i]);return 0; }

• 215F-紅魔法師

題意簡述

一個空的二維平面上，每次加入或刪除一個整點。
求每次操作完之后滿足以下條件的三個點$p_1,p_2,p_3$的對數。

$p_1.y>p_2.y>p_3.y$

$p_1.x>max(p_2.x,p_3.x)$

令操作數為$n$，保證$n\le 60000,1\le x,y\le n$。
保證加入點的時候平面上沒有該點。
保證刪除點的時候平面上有該點。

這個題由于有點難寫以及比賽已經結束就沒有寫QWQ,所以這里口胡一下

---

暴力就不說了。

我們首先看統計的條件，十分特別，對于一個點，我們把它當做$p_1$，那么就只統計它的左下方的點對，且滿足$p_2.y>p_3.y$即可。

所以我們先用離線，排序，掃描線預處理，然后用三維或者二維偏序之類的統計答案即可。

比賽Rank1后面是切了這個題的，牛客網的代碼是公開的，所以想看代碼的可以去?？途W看。

---

End

沒有抽到T桖QAQ，雖然冬天，但是還是想要啊QWQ

總結

以上是生活随笔為你收集整理的牛客网比赛-Wannafly挑战赛27的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。