A. 打怪

先求出每次打死一只怪需要掉多少血，然后就直接算出能夠打死多少只。

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #pragma GCC optimize(2) #include<iostream> #include<algorithm> using namespace std; int main() {IO;int T=1;cin>>T; while(T--){int h,a,H,A;cin>>h>>a>>H>>A;int cnt=(H+a-1)/a;int p=(cnt-1)*A;if(p) cout<<(h-1)/p<<'\n';else cout<<"-1\n";}return 0; }

B. 吃水果

不妨設$n<m$，如果我們先吃$k$次然后加倍一次能夠使得$m=n$那么需要滿足$2\times (n?k)=m?k$，得出$k=2n?m$，由此只需先讓加倍到$2n>=m$然后吃$k$次再次加倍然后在吃$m?k$次即可吃完，由此上面貪心一定最小。

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #pragma GCC optimize(2) #include<iostream> #include<algorithm> using namespace std; int main() {IO;int T=1;cin>>T;while(T--){int n,m;cin>>n>>m;if(n>m) swap(n,m);int res=m;while(n<m){res++;n*=2;}cout<<res<<'\n';} return 0; }

C. 四個選項

首先先用并查集統計出每個連通塊的數量，然后把每一個連通塊看成一個物品，跑一邊背包問題即可。
狀態表示：$f_{(i,j,k,l,r)}$考慮前$i$個物品，答案A選了$j$個，答案B選了$k$個，答案C選了$l$個，答案D選了$r$個的集合。
狀態轉移：考慮第$i$個物品放在哪個答案中不難寫出轉移。
感覺這方法有點暴力，但是思路應該還是非常好理解

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #pragma GCC optimize(2) #include<iostream> #include<algorithm> using namespace std; typedef long long ll; const int N=15; int p[N],sz[N]; ll f[N][N][N][N][N]; int find(int x) {return x==p[x]?x:p[x]=find(p[x]); } int main() {IO;int T=1;//cin>>T;while(T--){for(int i=1;i<=12;i++) p[i]=i,sz[i]=1;int a,b,c,d,m;cin>>a>>b>>c>>d>>m;vector<int> v;v.push_back(0);while(m--){int a,b;cin>>a>>b;int pa=find(a),pb=find(b);if(pa==pb) continue;sz[pb]+=sz[pa];p[pa]=pb;}for(int i=1;i<=12;i++) if(p[i]==i) v.push_back(sz[i]);f[0][0][0][0][0]=1;int n=v.size()-1;for(int i=1;i<=n;i++)for(int j=0;j<=a;j++)for(int k=0;k<=b;k++) for(int l=0;l<=c;l++)for(int r=0;r<=d;r++){if(j>=v[i]) f[i][j][k][l][r]+=f[i-1][j-v[i]][k][l][r];if(k>=v[i]) f[i][j][k][l][r]+=f[i-1][j][k-v[i]][l][r];if(l>=v[i]) f[i][j][k][l][r]+=f[i-1][j][k][l-v[i]][r];if(r>=v[i]) f[i][j][k][l][r]+=f[i-1][j][k][l][r-v[i]];}cout<<f[n][a][b][c][d]<<'\n';}return 0; }

D.最短路變短了

原圖跑一邊dijsktra算出dist1[i]表示1~i的最短距離，在跑一邊反圖算出dist2[i]表示i~n的最短距離。
考慮如果$u\to v$之間的邊取反能夠縮短$1\to n$的最短距離，那么說明目前最短路徑一定是$1\to ?\to v\to u\to ?\to n$，因此只需要判斷該條件是否成立即可得到答案（dist1[v]+dist2[u]+c<dist1[n]）

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #pragma GCC optimize(2) #include<cstring> #include<iostream> #include<algorithm> using namespace std; typedef long long ll; typedef pair<ll,int> pli; const int N=100010,M=400010; int h1[N],h2[N],e[M],ne[M],idx; ll w[M]; ll dist1[N],dist2[N]; bool st[N]; struct node {int u,v;ll w; }E[M]; int n,m,q; void add(int h[],int a,int b,ll c) {e[idx]=b;ne[idx]=h[a];w[idx]=c;h[a]=idx++; } void dijkstra(int start,int h[],ll dist[]) {memset(dist,0x3f,8*N);memset(st,0,sizeof st);priority_queue<pli,vector<pli>,greater<pli> >q;dist[start]=0;q.push({0,start});while(q.size()){int t=q.top().second;q.pop();if(st[t]) continue;st[t]=1;for(int i=h[t];i!=-1;i=ne[i]){int j=e[i];if(dist[j]>dist[t]+w[i]){dist[j]=dist[t]+w[i];q.push({dist[j],j});}}} } int main() {IO;int T=1;//cin>>T;while(T--){memset(h1,-1,sizeof h1);memset(h2,-1,sizeof h2);cin>>n>>m;for(int i=1;i<=m;i++){cin>>E[i].u>>E[i].v>>E[i].w;add(h1,E[i].u,E[i].v,E[i].w);add(h2,E[i].v,E[i].u,E[i].w);}dijkstra(1,h1,dist1);dijkstra(n,h2,dist2);cin>>q;while(q--){int id;cin>>id;int u=E[id].u,v=E[id].v,c=E[id].w;if(dist1[n]>dist1[v]+dist2[u]+c) cout<<"YES\n";else cout<<"NO\n";}}return 0; }

E.相似的子串

字符串哈希+二分
二分掃一遍序列即可，用哈希表記錄出現次數已經最后一次出現的位置。
時間復雜度$O(nlogn)$

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #pragma GCC optimize(2) #include<iostream> #include<algorithm> #include<unordered_map> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pii; const int N=200010,P=131; unordered_map<ull,pii> mp; ull h[N],p[N]; int n,k; char s[N]; ull get(int l,int r) {return h[r]-h[l-1]*p[r-l+1]; } bool check(int mid) {mp.clear();for(int i=mid;i<=n;i++){ull v=get(i-mid+1,i);if(mp[v].second<=i-mid) {mp[v].first++;mp[v].second=i;if(mp[v].first>=k) return 1;}}return 0; } int main() {IO;int T=1;//cin>>T;while(T--){cin>>n>>k;cin>>s+1;p[0]=1;for(int i=1;i<=n;i++){p[i]=p[i-1]*P;h[i]=h[i-1]*P+s[i]-'a'+1;}int l=0,r=n;while(l<r){int mid=l+r+1>>1;if(check(mid)) l=mid;else r=mid-1;}cout<<l<<'\n';}return 0; }

F.蘋果樹

點分治？待補?

總結

以上是生活随笔為你收集整理的牛客练习赛 61（待补F-点分治？）的全部內容，希望文章能夠幫你解決所遇到的問題。

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