题意：给出船的出发位置和目的地，给出四种移动方式。
思路：路程要被整除。横移纵移的奇偶性相同，如果不满足横或纵坐标缺少一截。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int x1,y1,x2,y2;
cin>>x1>>y1>>x2>>y2;
int x,y;
cin>>x>>y;
if(abs(x1-x2)%x==0&&abs(y1-y2)%y==0&&abs(x1-x2)/x%2==abs(y1-y2)/y%2)
cout<<"YES"<<'\n';
else cout<<"NO"<<'\n';
return 0;
}
题意：数列中选出三个数得到最小值的三个数的种类
思路：排序，分类讨论——前三小的数有多少种
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5+100;
int a[N];
signed main()
{
int n;
cin>>n;
for (int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+n+1);
if (a[1]==a[2]&&a[2]==a[3]){
int pos=0;
for (int i=1;i<=n;i++) if (a[i]==a[1]) pos++;
cout<<pos*(pos-1)*(pos-2)/6;
return 0;
}
if (a[1]==a[2]&&a[2]!=a[3]){
int pos=0;
for (int i=3;i<=n;i++) if (a[i]==a[3]) pos++;
cout<<pos;
return 0;
}
if (a[1]!=a[2]&&a[2]!=a[3]){
int pos=0;
for (int i=3;i<=n;i++) if (a[i]==a[3]) pos++;
cout<<pos;
return 0;
}
if (a[1]!=a[2]&&a[2]==a[3]){
int pos = 0;
for (int i=2;i<=n;i++) if (a[i]==a[2]) pos++;
cout<<pos*(pos-1)/2;
return 0;
}
return 0;
}
C. Really Big Numbers
题意：从1到n的范围中有多少个，自己减自己各个位数之和大于s的数
思路：递增，二分
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,s;
bool ok(ll x)
{
ll t=x,p=x;
while(p){
t-=(p%10);
p/=10;
}
return t>=s;
}
int main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>s;
ll l=1,r=n+1;
while(l+1<r)
{
ll m=(l+r)/2;
if(ok(m))r=m;
else l=m;
}
cout<<n-l<<endl;
return 0;
}
题意：求数组中每个连续子序列的的最大值-最小值之和。
思路：题意可以理解为加上每一个序列的最大值，减去每一个序列的最小值。每个数都可以作为某一连续子序列的最大值和最小值，所以可以枚举每一个数作为最值的区间，暴力枚举时间复杂度过高，所以利用单调栈找出每个数左边或右边第一个比本身小的数，这样该数就是区间中最小的数。同理也可以找该数为最大数的区间。比如1 4 1，第一个1最为最小值的时候会算一个1 4 1，第三个1最为最小值的时候也会算一个1 4 1。只有保持左开右闭就可以保证只算一次。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+100;
int a[N],l[N],r[N];
stack<int> s;
int main(){
ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
int n;
long long ans = 0;
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1;i<=n;i++){
while(!s.empty()&&a[s.top()]>a[i]) s.pop();
if(s.empty()) l[i] = 1;
else l[i] = s.top() + 1;
s.push(i);
}
while(!s.empty())
s.pop();
for(int i=n;i>=1;i--){
while(!s.empty()&&a[s.top()]>=a[i]) s.pop();
if(s.empty()) r[i] = n;
else r[i] = s.top() - 1;
s.push(i);
}
while(!s.empty())
s.pop();
for(int i=1;i<=n;i++)
ans -= 1LL * (i - l[i] + 1) * (r[i] - i + 1) * a[i];
for(int i=1;i<=n;i++){
while(!s.empty()&&a[s.top()]<a[i]) s.pop();
if(s.empty()) l[i] = 1;
else l[i] = s.top() + 1;
s.push(i);
}
while(!s.empty())
s.pop();
for(int i=n;i>=1;i--){
while(!s.empty()&&a[s.top()]<=a[i]) s.pop();
if(s.empty()) r[i] = n;
else r[i] = s.top() - 1;
s.push(i);
}
for(int i=1;i<=n;i++)
ans += 1LL * (i - l[i] + 1) * (r[i] - i + 1) * a[i];
cout<<ans<<'\n';
return 0;
}
E. Choosing The Commander字典树
F. MEX Queries线段树区间设值