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;
}
View Code
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;
}
View Code
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;
}
View Code
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;
}
View Code
标签：Summer,typedef,const,ve,Contest,int,SMU,stk,while From： https://www.cnblogs.com/bible-/p/17554470.html