A. 小苯的方格覆盖

猪猪王图拨号

最近迷上了华容道游戏，这天他找到了他的部下撤云猪猪

并给了他一个 3 行 n 列的矩阵。
图拨号希望撤云猪猪用一种 1×2 的小方格（可以旋转 90 度，即覆盖两个在同一行或同一列上相邻的格子）恰好填满这个矩阵，不能有空位，小方格之间也不能重叠。
只需要帮撤云猪猪判断是否可以用 1×2 的小方格填满这个 3 行 n 列的矩阵即可。
注意：1×2 的小方格可以旋转 90 度，变成 2×1 的小方格。

解题思路：只要列是偶数的都能用小方格进行填满

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void solve() {
    int n;
    cin>>n;
    if(n%2==0) cout<<"YES"<<'\n';
    else cout<<"NO"<<'\n';
}
int main() {
    int t=1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

B. 小苯的数字折叠

小苯发现了一种特殊的数字运算，称为“数字折叠”。对于一个正整数 x，定义其折叠操作为：
,∙将 x 的各位数字倒序排列并除去前导 0 得到 x′；
,∙计算 x+x′ 得到新数字；,∙重复这个过程直到得到一个回文数。
例如，对于 x=68，有：
,∙第一次折叠：68+86=154；
,∙第二次折叠：154+451=605；

第三次折叠：605+506=1111。
现在给定一个正整数 n 和最大操作次数 k，请判断：n 在最多 k 次折叠操作内（当然，也可以不操作）是否能变成回文数。如果能，输出最少操作次数得到的回文数和最少的操作次数；如果不能，输出第 kkk 次操作后的结果和 −1。

解题思路：模拟

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
bool fun(ll n){
    ll sum=n,tmp=0;
    while(n>0){
        tmp=tmp*10+n%10;
        n/=10;
    }
    if(tmp==sum) return true;
    else return false; 
}
ll fun_(ll n){
    ll tmp=0;
    while(n>0){
        tmp=tmp*10+n%10;
        n/=10;
    }
    return tmp;
}
void solve() {
    ll n,k;
    cin>>n>>k;
    int f=0;
    for(int i=0;i<k;i++){
        if(fun(n)){
            break;
        }else{
            f++;
            n+=fun_(n);
        }
    }
    if(fun(n)) cout<<n<<" "<<f<<'\n';
    else cout<<n<<" "<<-1<<'\n';
}
int main() {
//     int t=1;
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

C. 小苯的波浪加密器

小苯升级了她的数字波浪生成器，现在它变成了一个加密器。给定一个长度为 n−2 的数字序列 a3,a4,…,an 和两个区间 [L1,R1][L2​,R2​]。
数字波浪序列的生成过程如下：
,∙小苯从 [L1,R1] 区间中选择一个数字作为波浪序列的第一个数字 a1。
小苯从 [L2​,R2​] 区间中选择一个数字作为波浪序列的第二个数字 a2​。
,∙从第三个数字开始，每个数字都等于前面两个数字的乘积的个位数。
现在小苯给定了你 a3​ 到 an​ 的所有数字，请你还原出波浪序列对应的第一个和第二个数字 a1​ 和 a2。如果存在多个解，请输出使得整个波浪序列字典序最小的答案（即优先最小化 a1​，其次最小化 a2）。
注意，输入只保证 a5​ 到 an 满足上述关系；a3​、a4 给出但不一定与未知的 a1​、a2​ 一一对应，需求解时自行验证是否存在 a1​、a2​ 使得整个序列一致。如果无解，则输出两个固定的整数 −1。

解题思路：有用的只有个位数, a3,a4..an为前两个数乘积后模10, 所以取前10个数和后10个数的效果是一样, 但是题中要求最小化选出的a1和a2, 因此选择前10个数即可 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void solve() {
    ll n,L1,R1,L2,R2;
    cin>>n>>L1>>R1>>L2>>R2;
    vector<ll> a(n+1);
    for(ll i=3;i<=n;i++) cin>>a[i];
    R1=min(R1,L1+19);
    R2=min(R2,L2+10);
    bool f=false;
    for(a[1]=L1;a[1]<=R1;a[1]++){
        for(a[2]=L2;a[2]<=R2;a[2]++){
            if(a[3]==(a[1]*a[2])%10){
                if(n<4||(n>=4&&(a[2]*a[3])%10==a[4])){
                    f=true; break;
                }
            }
        }
        if(f) break;
    }
    for(ll i=3;i<=n;i++){
        if((a[i-2]*a[i-1])%10!=a[i]) { f=false; break; }
    }
    if(!f) cout<<"-1"<<" "<<"-1"<<'\n';
    else cout<<a[1]<<" "<<a[2]<<'\n';
}
int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

D, 小苯的数字变换

小苯最近在研究一种新型的数字变换游戏，名为“数字螺旋”。给定一个长度为 n 的数字序列 a1,a2,…,an，数字螺旋的生成规则如下：
,∙任意选择一个数字 ai​，将其替换为 ai⊕⌊ai2⌋,∙目标是通过最少的操作次数，使得整个序列变成一个回文序列。
现在，小苯需要你帮助他计算出最少需要的操作次数。如果无法达成目标，则输出 −1。
【名词解释】
按位异或（⊕）：对两个整数的二进制表示按位按位异或运算。
⌊x⌋：代表对 x 进行下取整操作，得到不超过 x 的最大整数。
回文序列：一个序列被称作回文序列，当且仅当这个序列从左往右读和从右往左读是相同的。换句话说，对于任意的 1≦i≦n，均有 ai=an−i+1 成立。

解题思路：对于你选择的数字ai, 经过与ai/2 , 按位异或后, 多次执行这个操作后, 会重新变回ai,所以原数字中的前后数对, 如果想成功匹配, 必须是在对方的循环里面的, 然后取最小值 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void solve() {
    int n; cin>>n;
    vector<int> a(n+1);
    for(int i=1;i<=n;i++) cin>>a[i];
    int ans=0;
    for(int i=1;i<=n/2;i++){
        int sum_1=0;
        int x=a[i],y=a[n+1-i];
        while(x!=y&&sum_1<32){
            x=x^x/2;
            sum_1++;
        }
        int sum_2=0;
        x=a[i],y=a[n+1-i];
        while(x!=y&&sum_2<32){
            y=y^y/2;
            sum_2++;
        }
        if(x==y) ans+=min(sum_1,sum_2);
        else { cout<<-1<<'\n'; return; }
    }
    cout<<ans<<'\n';
}
int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

E. 小苯的洞数组构造

一个正整数的“洞数”定义为：其所有数位的洞数之和。例如：299 的洞数是 0+1+1=2。
现在小苯给定了两个正整数 n,sum 希望你帮他构造一个数组 a，满足：
, a 的长度恰好是 n；
, a 中所有数字的值均介于 [1,10^10] 之间，即：1≦ai≦10^10；
, a 中所有数字的和不超过 sum，即：∑iai≦sum，注意是不超过，不是恰好；
,∙a 中所有数字的“洞数”之和尽可能地多。
请你帮他构造一个符合要求的数组 a 吧。

解题思路：通过手动模拟就会发现, 我们在从个位洞数增加的到十位洞数再到百位洞数的过程中只有1 4 8是最优的，类似于1, 4, 8, 48, 88, 488. 888....

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll arr[] = { 1, 4, 8, 48, 88, 488, 888, 4888, 8888, 48888, 88888, 488888, 888888, 4888888, 8888888, 48888888, 88888888, 488888888, 888888888, 4888888888, 8888888888};
void solve(){
    ll n,mx;
    cin>>n>>mx;
    vector<ll> a(n,1);
    if(n>mx){
        cout<<-1<<endl;
        return;
    }
    ll sum = n;
    for(int i=1;i<=20;i++){
        for(int j=0;j<=n-1;j++){
            ll cost = arr[i]-a[j];
            if(sum+cost>mx)break;
            a[j] = arr[i];
            sum+=cost;
        }
    }
    for(int i=0;i<=n-1;i++){
        cout<<a[i]<<" ";
    }
    cout<<endl;
}
int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

F. 小苯的数组计数

小苯认为一个长度为 m 的数组 b1,b2,…,bm​ 是美丽的，当且仅当其满足以下所有条件：
m≥3；, b1≠bm​；, 对于任意 1<i<m，均有：b1>bi 且 bi<bm​（即所有中间元素的数值都必须同时小于首位元素和末位元素）。
现在小苯给定了一个长度为 n 的序列 a1,a2,…,an​，他想知道 a 中有多少个子数组是美丽的，请你帮他数一数吧。
【名词解释】
子数组：从原数组中，连续的选择一段元素（可以全选、可以不选）得到的新数组。

解题思路：枚举右端点看有多少个合法的左端点, 这个合法的左端点是当前枚举的右端点左侧第一个大于当前数的数，左右端点中间的数都是小于右端点的，实现上是用单调栈

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll arr[] = { 1, 4, 8, 48, 88, 488, 888, 4888, 8888, 48888, 88888, 488888, 888888, 4888888, 8888888, 48888888, 88888888, 488888888, 888888888, 4888888888, 8888888888};
void solve(){
    int n;
    cin>>n;
    vector<ll> a(n+1);
    for(int i=1;i<=n;i++) cin>>a[i];
    int ans=0;
    vector<ll> stk;
    for(int i=1;i<=n;i++){
        bool f=0;
        while(stk.size()&&a[stk.back()]<=a[i]){
            f|=(a[stk.back()]==a[i]);
            stk.pop_back();
        }
        if(stk.size()&&stk.back()<i-1&&!f){
            ans++;
        }
        stk.emplace_back(i);
    }
    stk.clear();
    for(int i=n;i>0;i--){
        bool f=0;
        while(stk.size()&&a[stk.back()]<=a[i]){
            f|=(a[stk.back()]==a[i]);
            stk.pop_back();
        }
        if(stk.size()&&stk.back()>i+1&&!f){
            ans++;
        }
        stk.emplace_back(i);
    }
    cout<<ans<<'\n';
}
int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

 

感谢大家的点赞和关注，你们的支持是我创作的动力！