A.小喬和小灰灰

前幾天剛剛學了序列自動機，這題直接也沒咋想暴力的做法，直接上序列自動機匹配子序列即可。

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #pragma GCC optimize(2) #include<iostream> #include<algorithm> using namespace std; const int N=1010; char s[N]; int ne[N][110],n; char p1[]="XiaoQiao"; char p2[]="XiaoHuiHui"; void build() {for(int i=n;i;i--){for(int j=0;j<100;j++)ne[i-1][j]=ne[i][j];ne[i-1][s[i]-'A']=i;} } int main() {IO;int T=1;//cin>>T;while(T--){cin>>s+1;n=strlen(s+1);build();bool ok1=1,ok2=1;for(int i=0,now=0;i<8;i++){now=ne[now][p1[i]-'A'];if(!now) {ok1=0;break;}}for(int i=0,now=0;i<10;i++){now=ne[now][p2[i]-'A'];if(!now) {ok2=0;break;}}if(ok1&&ok2) cout<<"Happy\n";else cout<<"emm\n";}return 0; }

B.牛能和小鎮

$$|x_i^2{y}_i?x_j^2{y}_j+y_i^2(y_i?2x_i)?y_j^2(y_j?2x_j)|$$
不難發現這個式子$i$和$j$之間的坐標沒有任何相關性我們做一步轉化
$$|x_i^2{y}_i+y_i^2(y_i?2x_i)?(x_j^2{y}_j+y_j^2(y_j?2x_j))|$$
發現要把每個點用一個坐標表示即可$x_i^2{y}_i+y_i^2(y_i?2x_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=100010; ll p[N]; int n; int main() {IO;int T=1;//cin>>T;while(T--){cin>>n;for(int i=1;i<=n;i++){ll x,y;cin>>x>>y;p[i]=x*x*y+y*y*(y-2*x);}sort(p+1,p+1+n);cout<<p[n]-p[1]<<'\n';}return 0; }

C.裝備合成

典型數學題目，直接像做高中線性規劃題做即可。

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #pragma GCC optimize(2) #include<set> #include<map> #include<cmath> #include<queue> #include<string> #include<vector> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<unordered_map> using namespace std; typedef long long ll; typedef pair<int,int> pii; typedef unsigned long long ull; const int N=100010; ll x,y; bool check(ll a,ll b) {return (2*a+4*b<=x)&&(3*a+b<=y); } int main() {IO;int T=1;cin>>T;while(T--){cin>>x>>y;ll a=(4*y-x)/10;ll b=(3*x-2*y)/10;if(a>=0&&b>=0){ll res=0;if(check(a,b)) res=max(res,a+b);if(check(a,b+1)) res=max(res,a+b+1);if(check(a+1,b)) res=max(res,a+b+1);if(check(a,b-1)) res=max(res,a+b-1);if(check(a-1,b)) res=max(res,a+b-1);cout<<res<<'\n';}else if(a<0)cout<<min(x/4,y)<<'\n';else if(b<0) cout<<min(x/2,y/3)<<'\n';else cout<<0<<'\n';}return 0; }

D.取石子游戲

暴力打表+總結規律+瞎胡搞
畢竟我也看不出啥規律啊~~

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #pragma GCC optimize(2) #include<set> #include<map> #include<cmath> #include<queue> #include<string> #include<vector> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<unordered_map> using namespace std; typedef long long ll; typedef pair<int,int> pii; typedef unsigned long long ull; const int N=100010; ll sg[N]; ll dfs(ll u) {if(sg[u]!=-1) return sg[u];if(u==1) return sg[u]=0;int a=dfs(u/2);int b=dfs((u+1)/2);for(int i=0;;i++)if(i!=a&&i!=b) return sg[u]=i; }ll f[N],s[N]; int sz; void init() {f[1]=1;f[2]=2;s[1]=1;s[2]=3;for(int i=3;;i++){f[i]=f[i-1]+s[i-2];if(i%2==0) f[i]++;s[i]=f[i]+s[i-1];if(s[i]>=1e18){sz=i;break;}} } int main() {IO;int T=1;cin>>T;//memset(sg,-1,sizeof sg);init();while(T--){ll n;cin>>n;int l=1,r=sz;while(l<r){int mid=l+r+1>>1;if(s[mid]<=n) l=mid;else r=mid-1;}if(s[l]<n) l++;if(l&1) cout<<"XiaoQiao\n";else cout<<"XiaoHuiHui\n";}// for(int i=1;i<=400;i++)// if(dfs(i)) cout<<i<<": "<<1<<endl;// else cout<<i<<": "<<0<<endl;return 0; }

E.石子搬運

$O(q{n}^{2}logn)$
首先考慮如果沒有修改操作，不難發現可以設計dp
狀態表示：$f_{(i,j)}$表示考慮前$i$堆石子，搬運$j$次能夠搬完
狀態轉移：只需要考慮最后當前這堆石子搬運多少次能夠將其搬完

由基本不等式可得，對于某一堆石子，搬運次數一定的，那么均分搬運石子代價一定最小。

如果考慮修改，我們用線段樹維護，對于區間合并直接暴力合并即可$O(n^2)$
單點修改時間復雜度$n^{2}log(n)$，總時間復雜度$q{n}^{2}log(n)$

// O(qn^2logn) #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; const int N=410; const ll INF=0x3f3f3f3f3f3f3f3f; int n,m,q; ll a[N]; // ll f[N][N]; struct node {int l,r;ll f[N]; }tree[N*4]; void pushup(int u) {for(int i=1;i<=m;i++) tree[u].f[i]=INF;for(int i=1;i<=m;i++)for(int j=1;j<=m-i;j++){if(tree[u<<1].f[i]==INF||tree[u<<1|1].f[j]==INF) continue;tree[u].f[i+j]=min(tree[u].f[i+j],tree[u<<1].f[i]+tree[u<<1|1].f[j]);} } void build(int u,int l,int r) {tree[u]={l,r};memset(tree[u].f,0x3f,8*N);if(l==r){for(int k=1;k<=min(m,(int)a[l]);k++){int x=a[l]/k;int p=a[l]%k;tree[u].f[k]=1ll*(x+1)*(x+1)*p+1ll*x*x*(k-p);}return;}int mid=l+r>>1;build(u<<1,l,mid);build(u<<1|1,mid+1,r);pushup(u); } void modify(int u,int pos,int val) {if(tree[u].l==tree[u].r){for(int k=1;k<=min(m,val);k++){int x=val/k;int p=val%k;tree[u].f[k]=1ll*(x+1)*(x+1)*p+1ll*x*x*(k-p);}return;}int mid=tree[u].l+tree[u].r>>1;if(pos<=mid) modify(u<<1,pos,val);else modify(u<<1|1,pos,val);pushup(u); } int main() {IO;int T=1;//cin>>T;while(T--){cin>>n>>m;for(int i=1;i<=n;i++) cin>>a[i];build(1,1,n);cin>>q;while(q--){int x,v;cin>>x>>v;modify(1,x,v);cout<<tree[1].f[m]<<'\n';}// 嘗試沒有修改用dp做法是否正確// memset(f,0x3f,sizeof f);// f[0][0]=0;// for(int i=1;i<=n;i++)// for(int j=0;j<=m;j++)// for(int k=1;k<=min(j,(int)a[i]);k++)// {// int x=a[i]/k;// int p=a[i]%k;// ll w=1ll*(a[i]/k+1)*(a[i]/k+1)*p+a[i]/k*a[i]/k*(k-p);// f[i][j]=min(f[i][j],f[i-1][j-k]+w);// }// cout<<f[n][m]<<'\n';}return 0; }

就會上面幾題~~

F-小松鼠吃松果

大佬題解

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #pragma GCC optimize(2) #include<set> #include<map> #include<cmath> #include<queue> #include<string> #include<vector> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; typedef long long ll; typedef pair<int,int> pii; typedef unsigned long long ull; const int N=100010; int n,m; int pos[N],h[N]; int hs[N]; struct node {int t,p,w;bool operator<(const node&o) const{return t==o.t?p<o.p:t<o.t;} }q[N]; ll tree[N]; int lowbit(int x) {return x&-x; } void add(int k,ll x) {for(;k<=n;k+=lowbit(k)) tree[k]=max(tree[k],x); } ll query(int k) {ll res=0;for(;k;k-=lowbit(k)) res=max(res,tree[k]);return res; } int main() {IO;int T=1;//cin>>T;while(T--){cin>>n>>m;for(int i=1;i<=m;i++) cin>>pos[i];for(int i=1;i<=m;i++) cin>>h[i];for(int i=1;i<=n;i++){cin>>q[i].t>>q[i].p>>q[i].w;q[i].t+=h[q[i].p];}for(int i=1;i<=n;i++){int x=q[i].t-pos[q[i].p];int y=q[i].t+pos[q[i].p];q[i].t=x,q[i].p=y;hs[i]=y;}sort(hs+1,hs+1+n);sort(q+1,q+1+n);ll res=0;for(int i=1;i<=n;i++){int k=lower_bound(hs+1,hs+1+n,q[i].p)-hs;ll dp=query(k)+q[i].w;res=max(res,dp);add(k,dp);}cout<<res<<'\n';}return 0;}

要加油哦~

總結

以上是生活随笔為你收集整理的牛客练习赛 59的全部內容，希望文章能夠幫你解決所遇到的問題。

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