#单调栈 #构造 #贪心

• 单调栈过于久远，忘了

A

题意

• 用1*2和2*1的砖块填充3*n的矩形，判断能不能填充满

思路

• 签到，偶数可以，奇数不行

代码

void solve(){
    int n;
    cin >> n;
    if(n%2) cout << "NO" << endl;
    else cout << "YES" << endl; 
}

B

题意

• 给定x，最多进行k次操作，判断能不能使得操作后变为回文串
• 记y为x翻转并去除前导0，每次操作x=x+y

思路

• 直接模拟

代码

bool check(string s){
    for(int i=0,j=s.size()-1;i<=j;i++,j--){
        if(s[i]!=s[j]) return false;
    }
    return true;
}

long long deal(long long n){
    long long ans=0;
    while(n%10==0) n/=10;
    while(n){
        ans*=10;
        ans+=n%10;
        n/=10;
    }
    return ans;
}

void solve(){
    long long n,k;
    cin >> n >> k;
    bool ok=false;
    if(check(to_string(n))){
        cout << n << ' ' << 0 << endl;
        return ;
    }
    for(int i=1;i<=k;i++){
        n+=deal(n);
        if(check(to_string(n))){
            ok=true;
            cout << n << ' ' << i << endl;
            return ;
        }
    }
    if(!ok) cout << n << ' ' << -1 << endl;
}

C

• 这题读题的时候发病了，从[l,r]选一个数看成了从序列的[l,r]选一个，难绷

题意

• 给定一个序列，序列的每一位是前两位乘积的个位，给定前两个数的取值范围，和从第三位开始的n-2个数字，求解前两位，如果没有答案输出-1

思路

• 从第三位开始只有个位，暴力枚举前两位，枚举范围最大为10
• 要开long long

代码

void solve(){
    int n,l1,l2,r1,r2;
    cin >> n >> l1 >> r1 >> l2 >> r2;
    vector<int> a(n+10);
    for(int i=3;i<=n;i++){
        cin >> a[i];
    }
    bool ok=false;
    for(int a1=l1;a1<=min(l1+100,r1);a1++){
        for(int a2=l2;a2<=min(l2+100,r2);a2++){
            if(a1*a2%10!=a[3]||a2*a[3]%10!=a[4]) continue;
            ok=true;
            cout << a1 << ' ' << a2 << endl;
            return ;
        }
    }
    if(!ok) cout << -1 << ' ' << -1 << endl;
}

D

题意

• 长为n的序列，你可以将任何数 变为
• 输出将这个序列变为回文序列的最少操作数，如果无法变成，输出-1

思路

• 显然，对一个数的操作不会改变最高位的位置，所以对应位置如果最高位不同直接寄
• 可以证明，对于任何一个数，经过这个变换最多32次就会循环 。对于int范围的数，当 大于32，就一定会读到高位0，然后不发生变化

代码

int hibit(int x){
    int ans=0;
    while(x){
        x>>=1;
        ans++;
    }
    return ans;
}

void solve(){
    int n;
    bool ok=true;
    cin >> n;
    vector<int> a(n+10);
    vector<int> b(n+10);
    for(int i=1;i<=n;i++){
        cin >> a[i];
        b[i]=hibit(a[i]);
    }
    int ans=0;
    for(int i=1,j=n;i<=j;i++,j--){
        if(a[i]==a[j]) continue;
        if(b[i]!=b[j]){
            ok=false;
            break;
        }
        unordered_map<int,int> mi,mj;
        int cnti=0,cntj=0;
        while(mi.find(a[i])==mi.end()){
            mi[a[i]]=cnti++;
            a[i]^=(a[i]>>1);
        }
        while(mj.find(a[j])==mj.end()){
            mj[a[j]]=cntj++;
            a[j]^=(a[j]>>1);
        }
        int mn=INT_MAX;
        for(auto [x1,x2]:mi){
            for(auto [y1,y2]:mj){
                if(x1==y1) mn=min(x2+y2,mn);
            }
        }
        ans+=mn;
    }
    if(!ok) cout << -1 << endl;
    else cout << ans << endl;
}

E

题意

• 对于一个数他的洞数值指的是：每一个数位上的数字所含的闭合空间个数
• 给定n和sum，构造长为n，元素和不超过sum，洞数和最大的数组

思路

• 观察到能产生贡献的只有4和8
• 数的范围不超过1e10，每次确定一个数的一个数位，最多 的复杂度就能构造完

代码

void solve(){
    int n;
    ll sum;
    cin>>n>>sum;
    if(sum<n){
        cout<<-1<<"\n";
        return;
    }
    vector<ll>ans(n,1);
    ll rst=sum-n;
    for(int i=0;i<=9;i++){
        ll base=qpow(10,i);
        if(i==0){
            for(int j=0;j<n&&rst>=3;j++){
                ans[j]+=3;
                rst-=3;
            }
            for(int j=0;j<n&&rst>=4;j++){
                ans[j]+=4;
                rst-=4;
            }
        }else{
            ll c=4*base;
            for(int j=0;j<n&&rst>=c;j++){
                ans[j]+=c;
                rst-=c;
            }
            for(int j=0;j<n&&rst>=c;j++){
                ans[j]+=c;
                rst-=c;
            }
        }
    }
    for(int i=0;i<n;i++)cout<<ans[i]<< ' ';
    cout << endl;
}

F

题意

• 对于一个长为n的序列，计算其满足如下要求的连续片段个数
  1. 片段长度大于等于3
  2. 片段首尾不相等
  3. 片段中所有元素需要小于片段两端元素

思路

• 假设片段尾小于片段首，可以证明满足条件的答案至多有一个
• 如果有第二个，则片段中间的元素(上一个)就存在大于段尾的情况，而这个唯一合法的答案其实就是左侧第一个大于当前元素的元素，所以维护一个单调递减栈，同时判断长度够不够
• 对于另一种情况，只需要反向扫一遍序列即可

代码

#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    
    int T;
    cin >> T;
    while(T--){
        int n;
        cin >> n;
        vector<int> a(n+10);
        for(int i=1;i<=n;i++)cin >> a[i];
        long long cnt=0;
        stack<int> st;
        for(int i=1;i<=n;i++){
            bool ok=false;
            while(!st.empty()&&a[i]>a[st.top()]) st.pop();
            if(!st.empty()&&a[st.top()]==a[i]) ok=true;
            if(!ok&&!st.empty()&&st.top()!=i-1) cnt++;
            st.push(i);
        }
        while(!st.empty()) st.pop();
        for(int i=n;i>=1;i--){
            bool ok=false;
            while(!st.empty()&&a[i]>a[st.top()]) st.pop();
            if(!st.empty()&&a[st.top()]==a[i]) ok=true;
            if(!ok&&!st.empty()&&st.top()!=i+1) cnt++;
            st.push(i);
        }        
        cout << cnt << endl;
    }
    return 0;
}