SMU Summer 2023 Contest Round 2
A - Treasure Hunt
思路：判断 Δx 和 Δy 能否分别整除 x 和 y ，求出需要的步数，两者的步数须同奇或同偶
#include<bits/stdc++.h> using namespace std; //#define int long long typedef pair<int,int>PII; typedef pair<string,int>PSI; typedef pair<string,string>PSS; const int N=100+5,INF=0x3f3f3f3f,Mod=1e9+7; const double eps=1e-6; void solve(){ int x1,y1,x2,y2,x,y; cin>>x1>>y1>>x2>>y2>>x>>y; int dd1=abs(x2-x1),dd2=abs(y2-y1); int a,b;a=b=INF; if(dd1==0)a=0; else if(dd1%x==0)a=dd1/x; if(dd2==0)b=0; else if(dd2%y==0)b=dd2/y; if(a==INF||b==INF){ cout<<"NO";return; } if(a==0){ if(b%2)cout<<"NO"; else cout<<"YES"; return ; } if(b==0){ if(a%2)cout<<"NO"; else cout<<"YES"; return ; } if((abs(a-b))%2==0){ cout<<"YES";return ; } cout<<"NO";return; } signed main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int t=1; //cin>>t; while(t--){ solve(); } return 0; }
B - Makes And The Product
思路：对序列排序， ( i， j， k )的值为最小的三个数乘积，统计前三个数的个数情况即可求出所有可能
#include<bits/stdc++.h> using namespace std; #define int long long typedef pair<int,int>PII; typedef pair<string,int>PSI; typedef pair<string,string>PSS; const int N=100+5,INF=0x3f3f3f3f,Mod=1e9+7; const double eps=1e-6; void solve(){ int n; vector<int>ve; map<int,int>mp; cin>>n; for(int i=0,x;i<n;++i){ cin>>x; ve.push_back(x);mp[x]++; } sort(ve.begin(),ve.end()); if(ve[0]==ve[1]&&ve[1]==ve[2]){ int c=mp[ve[0]]; cout<<c*(c-1)*(c-2)/2/3;return ; } if(ve[0]!=ve[1]&&ve[1]!=ve[2]){ cout<<mp[ve[0]]*mp[ve[1]]*mp[ve[2]];return; } if(ve[0]!=ve[1]&&ve[1]==ve[2]){ cout<<mp[ve[0]]*mp[ve[2]]*(mp[ve[2]]-1)/2;return; } if(ve[0]==ve[1]&&ve[1]!=ve[2]){ int c=mp[ve[0]]; cout<<c*(c-1)/2*mp[ve[2]];return ; } } signed main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int t=1; //cin>>t; while(t--){ solve(); } return 0; }
C - Really Big Numbers
思路：f[i]表示每个数转换后的值，可以看出f[i]是递增的，二分求出大于s的即可
#include<bits/stdc++.h> using namespace std; #define int long long typedef pair<int,int>PII; typedef pair<string,int>PSI; typedef pair<string,string>PSS; const int N=100+5,INF=0x3f3f3f3f,Mod=1e9+7; const double eps=1e-6; int n,s; int l,r,mid; bool check(int x){ int sum=0,y=x; while(y){ sum+=y%10; y/=10; } x-=sum; return x>=s; } void solve(){ cin>>n>>s; l=1,r=n; while(l<=r){ mid=l+r>>1;//cout<<mid<<' '; if(check(mid))r=mid-1; else l=mid+1; } int ans=0; if(l<=n){ ans=n-l+1; } cout<<ans; } signed main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int t=1; //cin>>t; while(t--){ solve(); } return 0; }
D - Imbalanced Array
思路：求所有区间的最大值-最小值的和，可以转换为求所有数对区间的贡献，分别处理每个数对最大值和最小值的贡献，求和即可。
对于最大值的贡献，a[i]能贡献的范围在[l，r]，a[l-1]为i前第一个大于a[i]的数，a[r+1]为i后第一个大于a[i]的数。最小值同理。
对于某些相同的数会出现贡献范围重复的情况，那么向前取相同，后不取相同的即可（反着取也行...）
对于找出前后大于/小于a[i]的[l，r]，用单调队列维护即可。
#include<bits/stdc++.h> using namespace std; #define int long long typedef pair<int,int>PII; typedef pair<string,int>PSI; typedef pair<string,string>PSS; const int N=2e5+5,INF=0x3f3f3f3f,Mod=1e9+7; const double eps=1e-6; void solve(){ int n;cin>>n; vector<int>a(n+1); for(int i=1;i<=n;++i)cin>>a[i]; vector<int>mal(n+1),mar(n+1),mil(n+1),mir(n+1); stack<int>stk; for(int i=1;i<=n;++i){ while(stk.size()&&a[stk.top()]>a[i])stk.pop(); if(stk.size())mil[i]=stk.top()+1; else mil[i]=1; stk.push(i); } while(stk.size())stk.pop(); for(int i=n;i>=1;--i){ while(stk.size()&&a[stk.top()]>=a[i])stk.pop(); if(stk.size())mir[i]=stk.top()-1; else mir[i]=n; stk.push(i); } while(stk.size())stk.pop(); for(int i=1;i<=n;++i){ while(stk.size()&&a[stk.top()]<a[i])stk.pop(); if(stk.size())mal[i]=stk.top()+1; else mal[i]=1; stk.push(i); } while(stk.size())stk.pop(); for(int i=n;i>=1;--i){ while(stk.size()&&a[stk.top()]<=a[i])stk.pop(); if(stk.size())mar[i]=stk.top()-1; else mar[i]=n; stk.push(i); } int res=0; for(int i=1;i<=n;++i){ int ma=(i-mal[i]+1)*(mar[i]-i+1)*a[i]; int mi=(i-mil[i]+1)*(mir[i]-i+1)*a[i]; res+=(ma-mi); } cout<<res; } signed main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int t=1; //cin>>t; while(t--){ solve(); } return 0; }