第十六届蓝桥杯C/C++大学B组省赛

C: 可分解的正整数

除了1无法分解，剩下正整数都能分解成形如-(n-1), -(n-2), ..., n的序列，使之相加为n

#include <iostream>
#define endl '\n'
using namespace std;
typedef long long ll;
typedef long double ld;

void solve() {
    ll ans=0,tmp,n;cin>>n;
    while(n--) {
        cin>>tmp;
        if(tmp!=1) ans++;
    }
    cout<<ans<<endl;
}

int main() {
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    solve();
}

D: 产值调整

一开始我认为这是一道斐波那契数列，想要通过求解通项公式去降低复杂度，赛后朋友提醒了，这个函数收敛得很快，循环到20次左右时候，就能看到a,b,c相等，所以其实并不复杂

#include <iostream>
#define endl '\n'
using namespace std;
typedef long long ll;
typedef long double ld;

void solve() {
    ll a,b,c,k;
    ll a1,b1,c1;
    cin>>a>>b>>c>>k;
    while(k--) {
        a1=(b+c)/2;
        b1=(a+c)/2;
        c1=(a+b)/2;
        a=a1,b=b1,c=c1;
        if(a&b&c==(a+b+c)/3) break;
    }
    cout<<a<<" ";
    cout<<b<<" ";
    cout<<c<<endl;
}

int main() {
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    ll t;cin>>t;
    while(t--) solve();
    //solve();
}

E: 画展布置

1. 平方差展开

2. 单调性与最优排列

若我们在 M 个选中的数中，将它们按非降序排列，则相邻差值(|B_{i+1}-B_i|)最小，且(B_{i+1}+B_i)也更平滑，不会出现跨大区间的跳跃。因此，对于任意给定的 M 个数，将它们排序后再排列，总能达到最小的L。

3. 窗口滑动选取

在全集排序后，若从已排序的数组中取出连续的 M 个数再计算L，得到的值一定不大于取不连续位置的组合。因为中间不插数时，相邻平方差只会更大。

综上，最优解必然是：

• 先对 A 排序，得到 A[0] ≤ A[1] ≤ … ≤ A[N–1]

• 枚举所有长度为 M 的连续子段 A[i..i+M–1]

• 计算该子段内相邻平方差之和，取最小值

#include <iostream>
#include <vector>
#include <algorithm>
#define endl '\n'
using namespace std;
typedef long long ll;
typedef long double ld;

void solve() {
    ll n,m;
    cin>>n>>m;
    vector<ll> a,s1,s2;
    for(ll i=0;i<n;i++) {
        ll tmp;cin>>tmp;
        a.push_back(tmp);
    }
    sort(a.begin(),a.end());
    for(ll i=0;i<n-1;i++) {
        ll i0 = a[i];
        ll i1 = a[i+1];
        ll tmp = abs((i1+i0)*(i1-i0));
        s1.push_back(tmp);
    }
    s2.push_back(0);
    for(ll i=0;i<s1.size();i++) {
        s2.push_back(s2.back()+s1[i]);
    }
    ll ans = s2.back();
    for(ll i=0;i<=s2.size()-m;i++) {
        ll tmp=s2[i+m-1]-s2[i];
        ans = tmp<ans?tmp:ans;
    }
    cout<<ans<<endl;
}

int main() {
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
//    ll t;cin>>t;
//    while(t--) solve();
    solve();
}

F: 水质检测

• 确定有效区间
  扫描两行，记录最左和最右出现“#”的列索引 L、R。如果全无“#”，直接输出 0。

• 构造状态数组
  对每列 i（0 ≤ i < n）生成 status[i] ∈ {0,1,2,3}，标记该列的“#”分布。

• 提取真实状态切换序列
  在 [L, R] 范围内，忽略状态 0（空列）和 3（已双行），仅保留状态 1/2，并去掉相邻重复，得到一个仅含 1、2 的序列 change[]。该序列表征从一行跳到另一行的必要切换点。

• 扫描补全

  • 维护指针 c 指向 change 中当前期望的状态（初始为第一个元素）。

  • 对 i 从 L 到 R：

    • 若 status[i] == change[c]：说明该列已有所需的“#”，无需操作。

    • 否则：

      • 若 status[i] == 0：空列，需要在上下各行或切换行处新增一个“#”，ans++。

      • 若 status[i] ∈ {1,2} 且与 change[c] 不同（必然是两行切换场景），先在空白处新增一个“#”，使连通完成并切换行，ans++，同时 c++ 跳到下一个预期状态。

• 输出结果
  累加的 ans 即为最少新增检测器数量。

#include <iostream>
#include <vector>
#include <string>
#define endl '\n'
using namespace std;
typedef long long ll;
typedef long double ld;

void solve() {
    string s1,s2;
    cin>>s1>>s2;
    ll start=-1,end=-1;
    vector<ll> status,change;
    ll n = s1.length();
    for(ll i=0;i<n;i++) {
        string stu;
        stu+=s1[i],stu+=s2[i];
        if(stu!="..") {
            if(start == -1) start = i;
            end = i;
        }
        if(stu=="..") status.push_back(0);
        else if(stu==".#") status.push_back(1);
        else if(stu=="#.") status.push_back(2);
        else if(stu=="##") status.push_back(3);
    }
    if(start == -1) {
        cout<<0<<endl;
        return;
    }
    for(ll i=0;i<n;i++) {
        ll stu = status[i];
        if(stu != 0 && stu != 3) {
            if(change.empty()) change.push_back(stu);
            else if(change.back()!=stu) change.push_back(stu);
        }
    }
    ll c=0,ans=0;
    for(ll i=start;i<=end;i++) {
        ll stu = status[i];
        if(change[c]==stu) continue;
        if(stu==0) ans++;
        else if(change[c]*stu==2) ans++,c++;
    }
    cout<<ans<<endl;
}

int main() {
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
//    ll t;cin>>t;
//    while(t--) solve();
    solve();
}

H: 装修报价

题目分析
给定长度为 N负整数序列 A_1,A_2,\dots,A_N，在每对相邻元素之间插入运算符“⊕”（异或）、“+”或“−”，按“⊕”优先、“+、−”同优先、从左到右的顺序计算，系统会输出一个最终结果。我们需要枚举所有 $3^{N-1}$ 种可能的运算符组合，求它们对应结果之和（对10^9+7取模）。

直接暴力枚举对 N \le 10^5 是完全不可行的，需要进行数学归纳和计数优化。

假设有输入A,B,C按照题目要求运算，我们可以观察到如下现象：

(A-B-C) + (A-B+C）+(A+B-C) +(A+B+C)+(A-B\oplus C)+(A+B\oplus C) =6A \\ (A \oplus B -C) +(A \oplus B + C) = 2(A \oplus B) \\ (A \oplus B \oplus C)

可以看出，只有包含首项的连续异或项才不会被约去，那我们要做的就很简单了，只需要求出各项系数然后求和就好了

#include <iostream>
#include <vector>
#define endl '\n'
using namespace std;
typedef long long ll;
typedef long double ld;
const ll mod = 1e9 + 7;
vector<ll> memo={1};

ll pow3(ll n,ll m=mod) {
    ll res;
    if(n<memo.size() && !memo.empty()) res = memo[n];
    else if(n == 0) res = 1;
    else if(n == 1) res = 3;
    else if(n%2 == 1) res = (pow3(n/2) * pow3(n/2+1))%m;
    else res = (pow3(n/2) * pow3(n/2))%m;
    if(n==memo.size()) memo.push_back(res);
    return res;
}

void solve() {
    ll n,ans=0;cin>>n;
    vector<ll> a;
    for(ll i=0;i<n;i++) {
        ll tmp;cin>>tmp;
        if(a.empty()) a.push_back(tmp);
        else a.push_back(a.back()^tmp);
    }
    for(ll i=0;i<n;i++) {
        ll tmp=n-i-2;
        if(tmp>=0) ans += (a[i] * 2 * pow3(tmp))%mod;
        else ans += a[i];
        ans %= mod;
    }
    cout<<ans<<endl;
}

int main() {
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
//    ll t;cin>>t;
//    while(t--) solve();
    solve();
}