@TOC

前言

传送门 :

A. Treasure Hunt

观察题目给定的四个操作

首先是否能到达目的地 :

我们肯定要考虑 目的地 和 起点 他们之间是否 间隔整数倍 的值 (整数个 $x,y$

其次我们在模拟几次操作 :

$a+x,b-y$
$a+2x,b-2y || a-0x,b-2y$
$a+3x,b -1y||a+1x,b-3y$

我们会发现对于每次操作, $x,y$ 前面的系数都是 同奇偶的

因此这题答案如下 :

Mycode

const int N  = 1e5+10;
void solve()
{
    int x1,y1,x2,y2;
    cin>>x1>>y1>>x2>>y2;

    int x,y;
    cin>>x>>y;

    int dx = abs(x2 - x1);
    int dy = abs(y2 - y1);

    if(dx%x == 0  && dy%y == 0){
        if(dx/x  % 2 == dy/y % 2){
            cout<<"YES"<<endl;
            return;

        }
    }

    cout<<"NO"<<endl;


}

B. Makes And The Product

选出三个数,简单的分类讨论 + 组合数学

考虑 :
$a[1] == a[2] == a[3]$ 显然只能从$mp[a[1]]$中选
$a[2]!=a[1] \&\& a[2] == a[3]$ 显然只能从$mp[a[2]]$中选
$a[2]!=a[3]$ 显然只能从$mp[a[3]]$中选

没开$ll\ wa$了一发,然后括号太多写错了公式又$wa$了一发

Mycode

const int N  = 1e5+10;
int a[N],n;

void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        mp[a[i]] ++ ;
    }

    sort(a+1,a+1+n);

    /**
    1主打的情况
    **/
    if(a[1] == a[2] && a[2] == a[3]){
        cout<<mp[a[1]] * (mp[a[1]] - 1) * (mp[a[1]] - 2)/ 6<<endl;
        return;

    }

    /*
        1 只有一个的情况
    */

    if(a[3] == a[2]  && a[2]!=a[1]){
        cout<<mp[a[2]]*(mp[a[2]]- 1)/2<<endl;
        return;
    }
    /**
      2 只有一个的情况
    **/

    if(a[3]!=a[2]){
        cout<<mp[a[3]]<<endl;
        return;
    }
}

C. Really Big Numbers

看完这题之后还没有什么感想,因为数据量很大不清楚,所以考虑二分

但是中途 二分错误调了好多次,最后都有点怀疑了,然后证明了一下

满足二分的条件 :
如果 $x - sumd(x) >= s$ 那么就必须 $x+1 - sumd(x+1) >=s$

因为 $x - sumd(x) >= s$ 同时 $x+1 - sumd(x+1) >= x - sumd(x)$

因此$x+1 - sumd(x+1) >=s$ , 所以这题无疑使用二分答案来做

MyCode

const int N  = 1e5+10;
bool check(ll x,ll s ){
    ll t =  x;

    ll sumd =  0 ;
    while(x) {
        sumd +=  x%10;
        x/=10;
    }

    if(t - sumd  >= s )return true;
    else return false;

}
void solve()
{
    ll n,s;cin>>n>>s;
    ll l =  1 ,  r = n;
    while(l <= r){
        ll mid = (l+r)/2;
        if(check(mid,s)) r = mid-1;
        else l = mid + 1;


    }
    cout<<n-l+1<<endl;

}

D.

前天刚补,我们将当前的$a[i]$ 当作当前区间的最大值或者最小值,然后找到$a[i]$ 能影响到的区间 $L[i],R[i]$

最后计算即可,维护区间最大最小值使用单调栈

MyCode

typedef priority_queue<int,vector<int>,greater<int>>  Pri_m;
typedef pair<int,int> pii;
typedef vector<int> VI;
map<int,int> mp;

const int N  = 5e5+10;
int a[N],n;
int l[N],r[N];

stack<int> stk;
int ans = 0 ;

void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }

    for(int i=1;i<=n;i++){
        // 队列不空 并且当前元素大于要入栈元素
        while(!stk.empty() && a[stk.top()] >=a[i]) stk.pop();
        if(stk.empty()) l[i] =  i - 1;
        else  l[i] =  i - stk.top() - 1;
        stk.push(i);
    }
    while(!stk.empty()) stk.pop();

    for(int i = n ;i >= 1;i -- ){
        while(!stk.empty() && a[stk.top()] > a[i]) stk.pop();
        if(stk.empty()) r[i] = n - i;
        else r[i] = stk.top() - i - 1;
        stk.push(i);

    }


    for(int i=1;i<=n;i++){
        ans -= a[i]*(l[i]+1) * (r[i]+1);

    }

    while(!stk.empty()) stk.pop();
    for(int i=1;i<=n;i++){
        while(!stk.empty() && a[stk.top()] <= a[i]) stk.pop();
        if(stk.empty()) l[i] = i -1;
        else l[i] = i - stk.top() - 1;
        stk.push(i);
    }

    while(!stk.empty()) stk.pop();
    for(int i=n;i>=1;i  -- ){
        while(!stk.empty() && a[stk.top()] < a[i]) stk.pop();
        if(stk.empty())  r[i] = n-i ;
        else r[i] = stk.top() - i - 1;
        stk.push(i);
    }

    for(int i=1;i<=n;i++)
    ans += a[i]*(l[i] +1 ) * (r[i]+1);
    cout<<ans<<endl;




}
/**mYHeart is my algorithm**/
signed main()
{
    //int t;cin>>t;while(t -- )
    solve();
    return 0;
}